Comment by csense | Hacker News Reader

Comment by csense | Hacker News Reader

I've read a couple recent articles about the Y combinator on HN, and it seems like an interesting theoretical concept for e.g. showing that lambda calculus is Turing-complete.

But while it might be useful in minimalist contexts like the lambda calculus without much built-in functionality, what problem is it solving in this context?

It seems like a much more straightforward way to accomplish the same thing, without needing the Y combinator, would be (in Python syntax):

    def trace(f):
        def wrapper(*args):
            print("called with args", args)
            return f(*args)
        return wrapper

    fib_trace = trace(fib)

Why is the Y combinator needed for this? I don't get it.

It's because the generator recurses with:

    return fself(num - 1) + fself(num - 2);

instead of calling fib (or fib_gen) explicitly. fself is passed into the generator and it will need to be passed in again and again. That's what Y gets you. You could get tracing the way you suggest from something like:

    let fib f n =
        let n' = (* compute fib for n *) in
        f n'

and supply some f that will log (and return) the computed values, but that won't work with the motivating example: memoization. This really should have been clearer in TFA.

It's worth noting the memoization in the linked gist isn't pure. memo() allocates a cache and returns a function that references it. The cache is updated by mutating in place. After all the hoops we've jumped thorugh it's a bit of a let-down to end up here. (It's doable though.)

(Edit: improve clarity.)

Because fib is recursive, pretty sure you will only get one printout, not one for each call to fib.

As it is here, yeah, only once at the root level. But if you were to use it as a decorator on the original function, and reassign to the original name (as the decorator syntax does), it would print at every level, as the recursive call would bind to the decorated function.

Reply on news.ycombinator.com