| HN Mirror

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