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

[REBOL] Re: Tail end recursion

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]