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

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

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

That's a bit stupid. The function language is a small subset of the POV 
language. You can implement iterative and recursive algroithms in "the 
POV-Ray language", just not in functions.

-- 
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

Christopher James Huff <cja### [at] earthlinknet> wrote:
> Can you give an example of one of these?

  I don't remember any. (Can quicksort be made iteratively?)

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

  There are algorithms which need a stack (which size is proportional
to the amount of loops done). These are recursive algorithms which can't
be done iteratively.

-- 
#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

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

> Christopher James Huff <cja### [at] earthlinknet> wrote:
> > Can you give an example of one of these?
> 
>   I don't remember any. (Can quicksort be made iteratively?)

Can you remember any special terms I could use to look for information 
on these?


> > How about a slight modification: You can make an iterative version of 
> > any recursive algorithm that can be executed by a computer.
> 
>   There are algorithms which need a stack (which size is proportional
> to the amount of loops done). These are recursive algorithms which can't
> be done iteratively.

They can be done iteratively, you just need a stack. The problem may be 
the definitions we're using: by "iterative" I mean an implementation 
using a loop instead of recursive functions. I'm talking about the 
implementation in a language that supports loop structures (not POV 
functions) and/or recursion (also not POV functions). You can use 
recursion, or you can use loops and stacks. A VM or CPU are iterative, 
though you could mathematically define them as recursive. I don't know 
if this is any kind of standard definition, so don't take this as expert 
counsel.

BTW, something semi-related: I've got a working VM for Amber and am 
working on the compiler, and recently made some improvements to 
Sapphire, which should see another preview release soon. (After this 
semester ends...I haven't had much time to work on either.)
Among the improvements: objects now use copy-on-write. Actually, a kind 
of dual copy-on-write: methods and data are copied separately, and at 
another level the members are copied when used individually. 
Unfortunately, this means 3 integers overhead for reference counts, so 
objects aren't very memory efficient if you have lots of unique objects. 
That's what Amber is for, though, Sapphire just isn't designed for 
efficiency (though it is still much faster than a directly interpreted 
language like POV script).

-- 
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

Christopher James Huff <cja### [at] earthlinknet> wrote:
> Can you remember any special terms I could use to look for information 
> on these?

  Nope.

> They can be done iteratively, you just need a stack.

  If you need a stack (which size depends on the amount of loops performed),
it's not iterative.

-- 
#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 wrote:
> 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.

You are absolutely right!  However, a Turing machine may run
forever, and it never runs out of memory.  Thus, the concept
of computable functions or numbers may be more appealing to
mathematicians than it is to computer programmers...

I have an example for you - The Ackermann function A(m, n):

for m = 0           A(0, n) = n+1
     m > 0, n = 0    A(m, 0) = A(m-1, 1)
     m > 0, n > 0    A(m, n) = A(m-1, A(m, n-1))

( http://www.kosara.net/thoughts/ackermann.html
or http://www-users.cs.york.ac.uk/~susan/cyc/a/ackermnn.htm )

Although it *is* of course a (Turing) computable function,
it is not primitive recursive, thus cannot be coded using
just for- or while-loops (or "iteratively").

( http://www-users.cs.york.ac.uk/~susan/cyc/p/primrec.htm
and http://mathworld.wolfram.com/PrimitiveRecursiveFunction.html )

>[...]
> 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
 >[...]

This makes complete sense; however, a fractal does not
necessarily have to be the result of a recursive function
(as is also being stated on 
http://www.wikipedia.org/w/wiki.phtml?search=fractal&go=Go ,
the first link you mentioned).

And this definition lacks the exit condition, so neither a
turing machine nor a computer would ever return a result,
if the algorithm is implemented according to just the formula.
( - Would it be correct to call it non-computable in this case?)

>[...]
> 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.
 >[...]

Agreed.  Again, because I think as a programmer, I try to
keep it simple, fast and efficient.  So I avoid recursion,
if possible.

Thanks for the links; the first one
( http://www.wikipedia.org/w/wiki.phtml?search=fractal&go=Go )
is very interesting!


I see that a long time has passed since I learned about that
stuff; I forgot a lot...  Luckily, I get my programs running
properly mostly without thinking about Mr. Turing or primitive
recursion. :)


-- 
I'm pretty sure I'm seeing einsteinian light bending around
the local gravitational increase caused by programs that use
Date::Manip. :-) -- Randal L. Schwartz
++++++++++++++++ http://www.psico.ch/ ++++++++++++++++

Post a reply to this message

Hi,

You can "fake" iteration/recursion as in the following code (fix the line
wraps).  Best implemented with a scripting language to implement the include
file.

Bye,
Hans Mikelson

mandelbrot.inc

#declare mandloop18 = function(x,y,z,zr,zi) {18};
#declare mandloop17 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop18(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),17)}
;
#declare mandloop16 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop17(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),16)}
;
#declare mandloop15 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop16(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),15)}
;
#declare mandloop14 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop15(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),14)}
;
#declare mandloop13 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop14(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),13)}
;
#declare mandloop12 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop13(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),12)}
;
#declare mandloop11 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop12(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),11)}
;
#declare mandloop10 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop11(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),10)}
;
#declare mandloop09 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop10(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),9)};
#declare mandloop08 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop09(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),8)};
#declare mandloop07 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop08(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),7)};
#declare mandloop06 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop07(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),6)};
#declare mandloop05 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop06(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),5)};
#declare mandloop04 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop05(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),4)};
#declare mandloop03 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop04(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),3)};
#declare mandloop02 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop03(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),2)};
#declare mandloop01 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop02(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),1)};
#declare mandloop00 = function(x,y,z,zr,zi)
{select(zr*zr-zi*zi+2*zr*zi-4,mandloop01(x,y,z,zr*zr-zi*zi+x,2*zr*zi+z),0)};
#declare mandlbrot = function {mandloop00(x,y,z,0,0)*.05};

#declare T_Mandel =
texture {
    pigment {
        function {mandlbrot(x,y,z) }
        //turbulence .1
        //octaves 5
        //omega 1.1
        //lambda 2.0
      color_map {
        [0.00 color rgbt<.10, .00,  .00, .0>]
        [0.40 color rgbt<.80, .40,  .00, .0>]
        [0.50 color rgbt<.40, .00,  .00, .0>]
        [0.60 color rgbt<.80, .40,  .00, .0>]
        [1.00 color rgbt<.10, .00,  .00, .0>]
      }
    }
    finish {
        ambient 1.0
        diffuse 0.0
    }
}

#include "mandelbrot.inc"

camera {location <0,4,0>  look_at <0,0,0>}
global_settings { ambient_light rgb 1}
background { color rgb <0,0,0> }

plane { y, -1 hollow on texture {T_Mandel scale 1}}

Post a reply to this message

"Hans Mikelson" <hlj### [at] werewolfnet> wrote in
news:3eff4d42$1@news.povray.org: 

> Hi,
> 
> You can "fake" iteration/recursion as in the following code (fix the
> line wraps).  Best implemented with a scripting language to implement
> the include file.
...

An interesting idea...

This led me to read a little about the Mandelbrot set today.

Then I wrote a macro that uses your idea. (See my code below.)

Tor Olav



// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

// By Tor Olav Kristensen

#version 3.5;

#include "functions.inc"

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

#macro MandelbrotFunction(MaxIterations)

  #local MaxDistance = 100;
  #local Functions = array[MaxIterations]
  #local Functions[0] = function(Cr, Ci, Zr, Zi) { 1 }
  #local Cnt = 1;
  #while (Cnt < MaxIterations)
    #local IterationValue = 1 - Cnt/(MaxIterations - 1);
    #local Functions[Cnt] =
      function(Cr, Ci, Zr, Zi) {
        select(
          f_r(Zr, 0, Zi) - MaxDistance,
          Functions[Cnt - 1](Cr, Ci, Zr*Zr - Zi*Zi - Cr, 2*Zr*Zi - Ci),
          IterationValue
        )
      }
    #local Cnt = Cnt + 1;
  #end // while

  function { Functions[MaxIterations - 1](-x, y, 0, 0) }

#end // macro MandelbrotFunction

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

#declare MandelbrotTexture =
  texture {
    pigment {
//      mandel 60 exponent 2 interior 0, 1 exterior 1, 1
      MandelbrotFunction(60)
      color_map {
        [ 0.0 color rgb <1.0, 1.0, 1.0> ]
/*
        [ 0.2 color rgb <1.0, 0.7, 0.0> ]
        [ 0.4 color rgb <0.7, 0.5, 0.0> ]
        [ 0.6 color rgb <0.5, 0.3, 0.0> ]
        [ 0.8 color rgb <0.3, 0.0, 0.0> ]
*/
        [ 1.0 color rgb <0.0, 0.0, 0.0> ]
      }
    }
  }

plane {
  -z, 0
  texture {
    MandelbrotTexture
//    translate <-0.43, 0.3415, 0>
//    scale 800
    finish {
      ambient color rgb <1, 1, 1> // *4
      diffuse 0
    }
  }
}

camera {
  orthographic
  location -z
  right 1.33*x
  up y 
  direction z
  scale <1, 1, 1>*2.5
  translate -0.5*x
}

// ===== 1 ======= 2 ======= 3 ======= 4 ======= 5 ======= 6 ======= 7

Post a reply to this message