Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Tail end recursion

 [1/21] from: gedb01::yahoo::co::uk at: 8-Oct-2003 23:10


Thanks Ingo and Andrew. -c does the trick. Another quick question: does Rebol optimise tail end recursion like Lisp and Scheme? Thanks.

 [2/21] from: greggirwin:mindspring at: 8-Oct-2003 18:14


Hi Ged, GB> Another quick question: does Rebol optimise tail end GB> recursion like Lisp and Scheme? Nope. -- Gregg

 [3/21] from: maarten:vrijheid at: 9-Oct-2003 8:35


> Another quick question: does Rebol optimise tail end > recursion like Lisp and Scheme? >
No, but I wrote a function that does this. Only for tail recursive functions though. And gives you good insight in cracking some REBOL nuts ;-) See below.... ---------------------------------------- REBOL [] tail-func: func [ {Returns a function that handles tail-recursion transparently.} args [block!] body [block!] /local _*meta-func _*meta-spec _*meta-body _*statement _*comm _*p1 _*p2 _*r _*w ] [ _*meta-spec: append/only copy [] args _*meta-body: append/only copy [] body ;matches refinements and copies refinements to our command _*p1: [ set _*r refinement! (either get bind to-word _*r '_*comm [append _*comm mold _*r _*ref-mode: on][ _*ref-mode: off ])] ;matches words and copies their values to the statement if ref-mode on _*p2: [ set _*w word! (if _*ref-mode [ append/only _*statement get bind to-word _*w '_*comm])] _*meta-func: copy [ ;The use context is accessible from the wrapper function that ;eliminates tail recursion. It plays the role of a stack frame ;it implements a goto like behaviour in case of tail recursion use [ _*loop-detected _*myself _*innerfunc _*loops _*myspec _*myspec2 _*mycall] [ ;some static initialization of the use context varaiables _*loops: 0 _*loop-detected: false _*mycall: copy [] _*innerfunc: func (_*meta-spec) (_*meta-body) _*myspec: copy first :_*innerfunc _*myspec2: either found? find _*myspec /local [append copy _*myspec [_*ref-mode _*p1 _*p2 _*r _*w _*comm _*statement _*ret]] [append copy _*myspec [/local _*ref-mode _*p1 _*p2 _*r _*w _*comm _*statement _*ret]] insert/only _*myspec2 [catch] ;The function that is returned from the use context _*myself: func _*myspec2 [ ;How deep in a loop am I? _*loops: _*loops + 1 ;These parse rules extract how I am called ;(which refinements and so) _*p1: [(_*p1)] _*p2: [(_*p2)] _*ref-mode: on ;Our initial call _*comm: copy {_*innerfunc} ;Our initial statement _*statement: copy [] ;Generate our statement and call parse _*myspec [ any [ _*p1 | _*p2 ]] insert _*statement to-path _*comm ;Copy it in the use context so it survives ;a loop (_*mycall is the 'goto args) _*mycall: copy _*statement if _*loops = 2 [ _*loops: 1 _*loop-detected: true return ] ;Until we are no longer in loop-detection mode until [ _*loop-detected: false set/any '_*ret do bind _*mycall '_*loops not _*loop-detected ] ;Use context cleanup _*loops: 0 _*loop-detected: false _*mycall: copy [] ;return our value return get/any '_*ret ];_*myself: func ... ];use context ];meta-func ;return our function.... do compose/deep _*meta-func ] ;example usage f: tail-func [x][x: x + 1 print x f x]

 [4/21] from: gedb01:yah:oo at: 9-Oct-2003 10:17


Thanks for that. I look forward to the day that I can understand it :) --- Maarten Koopmans <[maarten--vrijheid--net]> wrote: >

 [5/21] from: maximo:meteorstudios at: 9-Oct-2003 8:22


sorry if I'm not versed in lisp but what exactly is a tail end recursion? -MAx --- You can either be part of the problem or part of the solution, but in the end, being part of the problem is much more fun.

 [6/21] from: hkalka:t-online at: 9-Oct-2003 14:59


Es tut mir sehr leid ich verstehe kein Englich Mit freundlichen Grüßen H.Kalka

 [7/21] from: maarten:vrijheid at: 9-Oct-2003 15:13


Max, See the sample F: func [x][x: x + 1 print x f x] Tail recursive is calling yourself as the last thing you do in a function. This will normally blow up the stack. But... you can eliminate this by replacing a call to yourself by saving the parameters, throwing the current stack frame away, and then execute again. --Maarten

 [8/21] from: maarten:vrijheid at: 9-Oct-2003 15:18


> Thanks for that. I look forward to the day that I can > understand it :)
Well, it took some time to write it ;-) It is a very powerful demonstration of REBOLs ability to do most things you want if *you* are up to it. What does this script do? It creates a "hidden" context using the 'use construct. The value returned from the code block of 'use is a function that has access to all these words/values. So... the use context can act as an extra stack frame. This is exactly what it does: it sets a flag for a function (metafunc) to inidicate recursive calling. Innerfunc is inside metafunc and is your actual code. Metafunc simply counts and implements a goto with throwing away the current stack frame (local words). All the p1 and p2 stuff is to pass/count refinements. Enjoy your headache ;-) --Maarten

 [9/21] from: bry:itnisk at: 9-Oct-2003 15:19


To put it simply tail-end recursion is where the recursion is the last action that occurs, i.e. no further processing occurs after recursion to (i+1), I think statistics show that most uses of recursion are in fact tail-end. Functional programming tends to rely on heavy use of recursion, and thus on heavy use of tail-end recursion.

 [10/21] from: gedb01:yaho:o at: 9-Oct-2003 14:29


You probably know that recursion is when a function calls itself. With tail end recursion LISP ensures that recursion is as efficient as iteration [1]. Instead of iteration: repeat count 3 [ print ["count: " count] ] You would use: recursive: func [count target][ print ["recursive count: " count] if count < target [recursive count + 1 target] ] recursive 1 3 In this simple example iteration looks much better. The recursive approach looks complicated and difficult to understand. So why is tail end recursion desirable? Well, consider a alogrithm for Longest Common Subsequence [2]. As link 2 shows, the initial recursive form is very easy to derive and understand, but you have to work a lot harder to get a decent iterative solution. [1] http://mathcs.holycross.edu/~mule/labs/prelabs/RecursionLambdaLab.htm [2] http://www.ics.uci.edu/~eppstein/161/960229.html

 [11/21] from: maximo:meteorstudios at: 9-Oct-2003 9:29


warum Antwort auf Deutsch? -MAx --- You can either be part of the problem or part of the solution, but in the end, being part of the problem is much more fun.

 [12/21] from: maximo:meteorstudios at: 9-Oct-2003 9:45


so basically its like using recursion to do a loop? something: does [print "."] forever [ do something ] is somewhat equivalent to?: something: does [ something ] in F: func [x][x: x + 1 print x f x] but how does tail-end recursion stop? how does F ever end? -MAx --- You can either be part of the problem or part of the solution, but in the end, being part of the problem is much more fun.

 [13/21] from: joel:neely:fedex at: 9-Oct-2003 10:22


Hi, Maxim, and all Maxim Olivier-Adlhoch wrote:
> so basically its like using recursion to do a loop? >
...
> but how does tail-end recursion stop? >
Recursion and looping are just two ways of expressing that something is to be repeated. In both cases one needs a terminating condition (unless the process is to run forever...) The example given earlier was a tad to trivial to make that point, but consider instead the slightly more complete example: forr-count: func [limit [integer!]] [ for i 0 limit 1 [print i] ] As we all know, this is just syntactic sugar for: while-count: func [limit [integer!] /local i] [ i: 0 while [i <= limit] [ print i i: i + 1 ] ] Notice that this version clearly states the initial "state" (I = 1), the condition for continuing the computation (I <= LIMIT), and the evaluation to occur for each continued case (PRINT and increment). Those same three ingredients are required to write an equivalent recursive function: rec-count: func [limit [integer!] /local .rec-count] [ do .rec-count: func [ i [integer!] .limit [integer!] ][ if i <= .limit [ print i .rec-count i + 1 .limit ] ] 0 limit ] Notice that every evaluation path through the inner function (.REC-COUNT) either terminates the computation or ends with a recursive call on itself, and every call to the inner function is the last thing in an execution path. (There's one of each.) In such cases, some languages/implementations can avoid the state-saving/restoration normally associated with beginning a subordinate evaluation -- in other words, they transform the recursive inner function above into a loop. REBOL does not. Sometimes the clearest/simplest specification for how to solve some problem is based on a divide-and-conquer strategy, where the sub-problems are either trivial to solve or are smaller cases similar to the original problem. In these cases, it is often easier to write a recursive solution. If the state management of the recursive implementation is too costly, one can (attempt to! ;-) formally transform the recursive solution into an iterative one; sometimes that's easy and sometimes not. (*) For more on this subject, please see http://www.rebolforces.com/articles/ria/ and for more on why recursion isn't complicated, see http://www.rebolforces.com/articles/metaphors/ HTH! -jn- (*) For an example of a problem that's easy to solve recursively, but which takes a bit of thought to solve iteratively (or in closed form! ;-), consider the old Fibonacci numbers. The original problem can be framed as follows: Begin a pair of new-born rabbits (one male, one female). When a pair of rabbits reaches age one month, they begin breeding, with a one-month gestation period, and breeding again immediatly after birth. Each breeding produces a pair of rabbits (one mail, one female). How many pairs of rabbits does one have each month (assuming that rabbits are immortal, food is infinitely available, etc...) Classify them as mature (at least one month old, breeding every month) and immature (just born, not mature for one more month). This give us the following population chart (in pairs): Month Mature Immature Total ----- ------ -------- ----- 1 0 1 1 2 1 0 1 3 1 1 2 4 2 1 3 5 3 2 5 etc... In other words, all pairs (immature or mature) which were alive last month are still alive, and all mature pairs from last month have produced new pairs. But the mature pairs last month are just the total population the month before! Finally, during the first two months we only have the original pair (immature or mature), so we get rfib1: func [n [integer!]] [ either n < 3 [1] [(rfib1 n - 1) + (rfib1 n - 2)] ] A little "programming algebra" produces the equivalent iterative form ifib1: func [n [integer!] /local a b] [ a: 0 b: 1 loop n [ a: (b: b + a) - a ] a ] But it takes a bit more mathematics to produce the equivalent closed form solution cfib1: func [n [integer!] /local r] [ r: square-root 5 ((1 + r / 2) ** n) - ((1 - r / 2) ** n) / r ] So recursion and iteration both have their places! ;-) -- ---------------------------------------------------------------------- Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446 Counting lines of code is to software development as counting bricks is to urban development.

 [14/21] from: maarten:vrijheid at: 9-Oct-2003 17:23


> so basically its like using recursion to do a loop? >
Nope.
> something: does [print "."] > forever [
<<quoted lines omitted: 7>>
> but how does tail-end recursion stop? > how does F ever end?
F: tail-func [x][if x > 1000 [ return x ] x: x + 1 print x f x] Which shows the difference with your example. I use tail-func to recursively traverse a tree structure that is mapped to a table in a relational database, updating the number of leafs per node. So I traverse the tree passing in the tree, updating the counters, and then calling itself with the rest of the tree (subtree). --Maarten

 [15/21] from: gedb01::yahoo at: 9-Oct-2003 16:52


Hi Max, --- Maxim Olivier-Adlhoch <[maximo--meteorstudios--com]> wrote: >
> so basically its like using recursion to do a loop? > something: does [print "."]
<<quoted lines omitted: 8>>
> but how does tail-end recursion stop? > how does F ever end?
You stop by having a condition, and only calling again if that condition is true. So while [keepGoing] [do something] is equivalent to something: func [keepgoing][if [keepgoing][do something[keepgoing]]]

 [16/21] from: ingo:2b1 at: 9-Oct-2003 23:31


This is for the list ... Dipl.Ing.Henryk Kalka wrote:
> Es tut mir sehr leid ich verstehe kein Englich > Mit freundlichen Grüßen > H.Kalka
Translation: I'm sorry, but I don't understand english. Kind regards, H. Kalka And for Mr. Kalka ... Hallo Herr Kalka, Irgendwie haben Sie eine Email erhalten, die an eine englischsprachige Email-Liste gerichtet war. Falls es sich um einen einzelnen Irrläufer gehandelt hat, sollte sich das für Sie erledigt haben, falls nicht, dann sendes Sie bitte eine Email an [rebol-request--rebol--com] mit dem Subject: unsubscribe danach sollten Sie aus der Liste wieder ausgetragen sein. Mit freundlichen Grüßen, Ingo Hohmann

 [17/21] from: hkalka:t-online at: 9-Oct-2003 16:59


Ich bin in Deutschland und das war meine erste versuch etwas informieren vo Rebol. Ich bin nicht in der lage diskutieren mit freundlichen Grüßen H.Kalka

 [18/21] from: gchiu:compkarori at: 24-Dec-2003 22:39


On Wed, 8 Oct 2003 23:10:10 +0100 (BST) Ged Byrne <[gedb01--yahoo--co--uk]> wrote:
>Another quick question: does Rebol optimise tail end >recursion like Lisp and Scheme?
Here's the long answer from Holger Kruse - see the bottom http://www.compkarori.com/vanilla/display/continuations -- Graham Chiu http://www.compkarori.com/vanilla

 [19/21] from: gedb01:yah:oo at: 10-Oct-2003 10:04


Thanks Graham, that was a very interesting. --- Graham Chiu <[gchiu--compkarori--co--nz]> wrote: >

 [20/21] from: lmecir:mbox:vol:cz at: 11-Oct-2003 17:04


I think, that my version looks different/shorter, but uses the same basic principle. It is at: http://www.fm.vslib.cz/~ladislav/rebol/tailfunc.r -L

 [21/21] from: gchiu:compkarori at: 24-Dec-2003 22:40


For those interested in further reading on this, Joe Marshall sent me a rebuttal of Holger's comments, and I've posted them here: http://www.compkarori.com/vanilla/display/Language+Theory -- Graham Chiu http://www.compkarori.com/vanilla/

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted