Warning - dangerous nerdery ahead!

[pmb]

def voodoo(f):
    def A(x):
        def B(y):
            return x(x)(y)
        return f(B)
    return A(A)

def hypothetical_fact(factorial):
    def f(n):
        if n == 0:
            return 1
        else:
            return n * factorial(n-1)
    return f

fact = voodoo(hypothetical_fact)

print fact(30)

The Z combinator is messed up. Anybody want to explain the above code to me?

Comments

I'll give it a shot...

[stereotype441.livejournal.com]

The Little Schemer calls "voodoo" the applicative-order Y combinator.

The purpose of the "voodoo" function (as you no doubt have gathered) is to transform a non-recursive function f into a recursive function g, where g is equivalent to f(g). But it does it without using any recursive functions.

If you've read GEB, it should not surprise you that the trick do doing that is to use quining. We need to come up with a function A such that A(A) is g. In other words, we need A(A) to be equivalent to f(A(A)). That's very straightforward: define A(x) to be f(x(x)).

In a language with normal-order (i.e. lazy) evaluation, we would be done now. The code would read:

def voodoo(f):
    def A(x):
        return f(x(x))
    return A(A)

Unfortunately, in a language like Python, which has applicative-order (i.e. strict) evaluation, this doesn't work, because voodoo tries to evaluate A(A), and A(A) tries to evaluate f(A(A)), which in turn requires evaluating A(A), and presto chango, your stack explodes.

So we need to do one more trick. In the function A, instead of passing x(x) to f, we need to pass a function that is equivalent to x(x), but that doesn't bother computing x(x) until it is actually invoked.

That function is B:

define B(y):
    return x(x)(y)

The only difference between B and x(x) is the order in which things get evaluated. In a sense B is a lazy version of x(x). If we use B in place of x(x), then voodoo can actually get around to returning the function g. x(x) won't get evaluated until f attempts to call its argument.

Put that all together and you get:

def voodoo(f):
    def A(x):
        def B(y):
            return x(x)(y)
        return f(B)
    return A(A)

Re: I'll give it a shot...

[stereotype441.livejournal.com]

Hmm... On second reading, I don't think I got that second paragraph exactly right. Instead of saying "But it does it without using any recursive functions" I should have said "But it does it without using any self-referential functions". Oops.

Re: I'll give it a shot...

[coldtortuga.livejournal.com]

I tried out pmb's nifty-looking code. Then, whilst attempting to grok it with much aid from stereotype441's explanations, I tried adding some execution-tracing outputs -- and that led to a whole foray into writing a Python class which emulated a function *BUT* also supplied recursive traces of its execution *AND* evaluated its arguments in a lazy call-by-need fashion. Mostly this was done by making all functions into generators, which would first yield their result, and then yield their execution-trace.

... [pause for a moment, to emulate the passage of time] ...

Okay, that didn't pan out so well for this Y-combinator stuff (difficulties with functions of functions which evaluate to other functions which then get applied to arguments). But now I *do* own both The Little Schemer and The Seasoned Schemer, and I've got PLT-Scheme installed at work, and I've managed to write/debug Scheme functions which take arbitrary sexp's and return depth- or breadth-first continuation-based iterators.

If my boss finds out, I'm billing my hours to you two :-)

---

Oh -- "stereo type" -- HAH! I just got the pun :) "Stop the violins!"

[neonelephant.livejournal.com]

I don't think I ever got to the point where combinators didn't break my head. I don't think I took enough DEs.