Hacker News new | past | comments | ask | show | jobs | submit login

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



...re-reading this I realize the comments are a bit of a mess... basically, it's a decorator that uses the y-combinator to get around the recursion depth problem by "suspending" the evaluation at each step (I'm sure there's some technical term for this... thunking?), then later performing each evaluation inside a while loop. I tested it a bunch and it seemed to work on anything.

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.


Reminds me of javascript trampoline http://raganwald.com/2013/03/28/trampolines-in-javascript.ht... . Was it an inspiration or did you recreate it from scratch ?


It was cobbled together more or less from scratch mainly based on stackoverflow questions and wikipedia articles. To be honest, it was still somewhat opaque to me (hence the extraordinarily long comments--trying to explain it to myself) but the javascript link makes things much clearer! Thanks




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: