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