gimi <gim### [at] psicoch> wrote:
> What du you need recursion for?

  POV-Ray functions do not support iterative control structures. The only
way of making a loop with functions is using recursion (as in any functional
language).

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Christopher James Huff <cja### [at] earthlinknet> wrote:
> You can make an iterative version of any recursive algorithm.

  Not true. It has been proved that there are recursive algorithms which
can't be implemented as iterative ones.
  (The difference between recursive and iterative algorithms is the
amount of memory they require: If the amount of memory required by the
algorithm is directly proportional to the amount of loops performed
(typically when you need a stack) then it's recursive. If the amount of
memory needed is constant, ie. doesn't depend on the amount of loops,
then it's iterative.)

-- 
plane{-x+y,-1pigment{bozo color_map{[0rgb x][1rgb x+y]}turbulence 1}}
sphere{0,2pigment{rgbt 1}interior{media{emission 1density{spherical
density_map{[0rgb 0][.5rgb<1,.5>][1rgb 1]}turbulence.9}}}scale
<1,1,3>hollow}text{ttf"timrom""Warp".1,0translate<-1,-.1,2>}//  - Warp -

Post a reply to this message

Warp wrote:
> gimi <gim### [at] psicoch> wrote:
>>What du you need recursion for?
> 
>   POV-Ray functions do not support iterative control structures. The only
> way of making a loop with functions is using recursion (as in any functional
> language).

I see that now...  I have just tried to do that
fractal pigment function thing myself.  What a pity! :(

<sulk>
Now I just feel like never calling the POV-Ray language
a "programming language" again!!
</sulk> ;)

g.

-- 
Be very careful to never use Date::Manip twice in the same
program, or you could form a black hole! :-)
  -- Randal L. Schwartz
++++++++++++++++ http://www.psico.ch/ ++++++++++++++++

Post a reply to this message

Warp wrote:
>   POV-Ray functions do not support iterative control structures. The only
> way of making a loop with functions is using recursion (as in any functional
> language).

One more thing: Neither does it support conditional
structures like "#if ... #else ... #end" nor "(C ? A : B)",
AFAICS in the docs.  So, One would have to workaround this
using "select"; now I understand why Christopher mentioned
that..!


Thanks,

g.

-- 
++++++++++++++++ http://www.psico.ch/ ++++++++++++++++

Post a reply to this message

gimi <gim### [at] psicoch> wrote:
> One more thing: Neither does it support conditional
> structures like "#if ... #else ... #end" nor "(C ? A : B)",
> AFAICS in the docs.

  It does. It's called 'select'. 'select' is not a workaround, it's a
conditional structure.

  In theory adding the support for recursive function calling should
be easy (AFAIK you could simply remove the existing check which stops
the parsing if recursion is detected). The problem is that there seems
to be cases where it doesn't work ok, and fixing it to work always may
need severe work. For simple recursive functions it should work ok (at
least according to prototype tests).
  (I don't know if it would be a good idea to enable recursion in a patched
version of povray because of the detected instability, but a personal
version would be interesting to try.)

-- 
#macro N(D)#if(D>99)cylinder{M()#local D=div(D,104);M().5,2pigment{rgb M()}}
N(D)#end#end#macro M()<mod(D,13)-6mod(div(D,13)8)-3,10>#end blob{
N(11117333955)N(4254934330)N(3900569407)N(7382340)N(3358)N(970)}//  - Warp -

Post a reply to this message

Warp wrote:
> gimi <gim### [at] psicoch> wrote:
>>One more thing: Neither does it support conditional
>>structures like "#if ... #else ... #end" nor "(C ? A : B)",
>>AFAICS in the docs.
[And gimi also wrote:]
 >> So, One would have to workaround this using "select";
 >> now I understand why Christopher mentioned that..!
 >
>   It does. It's called 'select'. 'select' is not a workaround, it's a
> conditional structure.

Of course 'select' isn't a workaround in itself, but its
use as a conditional *structure*.  In a practical sense,
it is of course the same, but I would be careful not to
speak of a "structure" if it's in fact a function or
operator.  After all, there must be a reason why there
*are* conditional structures, and not just functions,
in programming languages!?

It is listed as a float function in the docs, and I
prefer to put it in the same drawer together with the
signum function, or even the '<=>' operator (Perl).

Or would you call "if ... then ... else" a function?

However, as far as POV-Ray is concerned, I don't know
how these different statements are implemented, nor if
it means anything whether it's called a function or
not...

>   In theory adding the support for recursive function calling should
> be easy (AFAIK you could simply remove the existing check which stops
> the parsing if recursion is detected). The problem is that there seems
> to be cases where it doesn't work ok, and fixing it to work always may
> need severe work. For simple recursive functions it should work ok (at
> least according to prototype tests).

I can't help getting the feeling that this POV-language
design or implementation is a little messy...

>   (I don't know if it would be a good idea to enable recursion in a patched
> version of povray because of the detected instability, but a personal
> version would be interesting to try.)

It certainly would!  OTOH, I think that this would better
be accompanied with some major redesign... - SCNR ;)


Have a nice weekend, I'm off...

gimi

-- 
"What right does Congress have to go around making laws
just because they deem it necessary?" -- Marion Barry
++++++++++++++++ http://www.psico.ch/ ++++++++++++++++

Post a reply to this message

gimi <gim### [at] psicoch> wrote:
> After all, there must be a reason why there
> *are* conditional structures, and not just functions,
> in programming languages!?

  Have you taken a look to a (purely) functional language?

  Purely functional languages do not have loops (or other things like
assignment to a variable).

-- 
#macro M(A,N,D,L)plane{-z,-9pigment{mandel L*9translate N color_map{[0rgb x]
[1rgb 9]}scale<D,D*3D>*1e3}rotate y*A*8}#end M(-3<1.206434.28623>70,7)M(
-1<.7438.1795>1,20)M(1<.77595.13699>30,20)M(3<.75923.07145>80,99)// - Warp -

Post a reply to this message

Warp wrote:
> gimi <gim### [at] psicoch> wrote:
>>After all, there must be a reason why there
>>*are* conditional structures, and not just functions,
>>in programming languages!?
> 
>   Have you taken a look to a (purely) functional language?

Yes, several.

>   Purely functional languages do not have loops (or other things like
> assignment to a variable).

True.  But we're talking POV-Ray, not Gofer nor Miranda...

And now that you mention it, I'd prefer "Pure Functional
POV-Ray" to what is available now..! ;)


Ok, now I'm gone. - Really! :)
(Unless I'm urged to get the final word again :D)

g.

-- 
++++++++++++++++ http://www.psico.ch/ ++++++++++++++++

Post a reply to this message

In article <3eb3dcbc@news.povray.org>, gimi <gim### [at] psicoch> wrote:

> AFAIK this is only proven to be true for end-recursive algorithms
> (though /many/ of the functions with a single recursion call can
> be made end-recursive; but you will usually run into trouble if
> the algorithm has multiple recursive calls).

By multiple recursions, you mean multiple recursions from a single 
level, like branches on a tree? Those aren't a problem. And you don't 
need them to be tail-recursive, though some languages can optimize those 
into a more efficient iterative form automatically.
Here's a very simple proof: computer processors are iterative. Recursive 
functions are mimicked by using a chunk of memory as a stack. Turing 
machines are iterative, and I've never heard of a recursive function 
that could not be represented with a Turing machine.


> > However, the recursive version is often much simpler, 
> 
> I agree, but it depends on how you look at it.  For people
> not too familiar with the concept, an iterative function
> is far easier to grasp. - And, as I mentioned before, it's
> faster (and more efficient) in almost every case

Conceptually, a recursive definition is the most accurate description of 
many fractals, including the Mandelbrot set. Fractals come out naturally 
from recursive functions, but not from iterative ones. For example, the 
Mandelbrot set's mathematical definition:
z -> z^2 + c


> (Note that I speak as a programmer here, not as a mathematician).

Well, mathematically, iteration is a subset of recursion. In practical 
computer programming though, recursion is done with stacks and iteration.


>  > and most fractals are mathematically defined as recursive
>  > because of the self-similar nature of fractals.
> 
> Can you elaborate on this kind of definition?

http://www.wikipedia.org/w/wiki.phtml?search=fractal&go=Go
http://www.everything2.com/index.pl?node=fractal
http://www.fractalwisdom.com/FractalWisdom/fractal.html
http://www.google.com/ (just search for anything involving "fractal" and 
"recursive" or "recursion")

More info:
http://mathworld.wolfram.com/MandelbrotSet.html
http://mathworld.wolfram.com/Fractal.html


>    I don't doubt this, I just think that one can as well
> define them by iterative means ("As long as the conditions
> are not fulfilled, do repeat...").

As I've said, the recursive version is often much cleaner and simpler. 
Just look at a few examples. The iterative version can be faster to 
compute (especially when function calls are computationally expensive), 
but is usually derived from a recursive mathematical definition.


>    However, I doubt that the relation between recursion and
> self-similarity is as strong as you think.  Recursion is
> often (ab-)used in order to make code look slick, when in
> fact it isn't.

Look at pretty much anything ever written about fractals. The 
relationship between fractals and recursion predates computers. 
Mandelbrot and Leibniz used the exact term "recursive self similarity" 
to describe these shapes. Recursion is very, very important in the 
mathematics of fractals.


> You mean "does not support loops" because there is no
> proper stack to store (local) variables on?  In this
> case, yes; but I'd prefer to solve (not "imitate") this
> by implementing one - *if* I *really* need to... ;)

It has nothing to do with a stack...you don't need that for loops anyway 
(though the POV-Ray function VM does have one). There is no loop 
construct for functions, making iterative functions very awkward to do. 
You can use a chain of select() calls, but that limits complexity, is 
inefficient, and can only be done when you have a fairly small known 
maximum number of iterations. (infinite loops aren't possible)


> BTW, Christopher, what is your profession?

College student. Majoring in computer science (applied mathmatics), 
minoring in physics.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message

In article <3eb3eab4@news.povray.org>, Warp <war### [at] tagpovrayorg> 
wrote:

>   Not true. It has been proved that there are recursive algorithms which
> can't be implemented as iterative ones.

Can you give an example of one of these?

How about a slight modification: You can make an iterative version of 
any recursive algorithm that can be executed by a computer.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: chr### [at] tagpovrayorg
http://tag.povray.org/

Post a reply to this message