|
|
|
|
|
|
by _callcc
4104 days ago
|
|
|
I noticed the implicit y combinator as well... here's something I wrote in python some time ago to play with the idea: def tco(fn):
"""
tco
---
Usage:
Functions should have the following form:
>>> recursive_fn = lambda fn: lambda x: fn(x+1) if x < 1000000 else x
or
>>> def recursive_fn(fn):
... def recursive_fn_cc(x):
... return fn(x+1) if x < 1000000 else x
... return recursive_fn_cc
The notable difference is that called on their own, these
functions aren't recursive at all. For example,
>>> recursive_fn(lambda x: x)(1)
2
This is easier to see in the anonymous-style definition:
>>> lambda fn: lambda x: fn(x+1) if condition(x) else x
So we go from
>>> def recur(x):
... ( function body modifying x )
... if not base_case_reached:
... return recur(x)
... else:
... return x
to
>>> @tco
... def recur(fn):
... def _lambda(x):
... ( function body modifying x )
... if not base_case_reached:
... return fn(x)
... else:
... return x
... return _lambda
Then call as usual like
>>> recur(x)
Functions need to take this form as it exposes the fixed-point,
namely the recursive `fn`. We need a fixed-point for the modified
y-combinator. The modified combinator is the same, only where the
evaluation step would normally take place, each evaluation is
suspended or "thunked" by wrapping in a `lambda`. The thunks
are then looped over and called in a while-loop, sidestepping
the recursion depth issue.
TODO: save the kwargs; eliminate the need to write the functions
as continuations (i.e. `recur = lambda fn:lambda x: ...`) by creating
new function objects from bytecode, replacing instances of `LOAD_GLOBAL`
with `LOAD_DEREF`, may need to build temp function in order to create
closure so `fn` can be added in `co_freevars`. See e.g.
http://nbviewer.ipython.org/github/bravegnu/python-byte- code/blob/master/Python%20Byte%20Code%20Hacking.ipynb
"""
# y combinator with evaluation step wrapped in throwaway lambda
# which suspends the evaluation step;
# important to give `_t_c_o_` or some other highly unlikely keyword
# argument so we can signal to the loop when stop evaluating;
# want to be able to *return* a function as well, so checking for
# '__call__' in directory is not enough.
# Could also check that argcount is zero, and no other keywords exist;
# if we're really nuts, generate a uuid or timestamp, then assign
# it to `_t_c_o_`
Y = (lambda f: (lambda x: x(x))(
lambda y: f(lambda *args: lambda _t_c_o_=None: y(y)(*args))))(fn)
def tco_cc(*args):
_fn = Y(*args)
while ('__call__' in dir(_fn)) and ('_t_c_o_' in _fn.__code__.co_varnames):
_fn = _fn()
return _fn
return tco_cc
|
|
|
I recall being convinced keyword arguments could be made to work, and also that some byte code hacking would get around the "non-user friendly" bit where recursive functions need to be written as "functionals" in order to expose the recursive function itself as a fixed point.