Arthur Nunes-Harwitt's Compiler Thingy

This is based on "Eager Evaluation Isn't Eager Enough: A Transformation Based Approach to Semantics-Directed Code Generation" by Arthur Nunes-Harwitt.

He show a fascinating technique for "staging an interpreter so that it generates a compiler". He used a linear version of power() with two inputs, but he mentions that you could do the same thing with the version that does repeated squaring. Let's do that now.

But first we need a helper function to tell us whether an integer is odd or not.

odd = lambda n: bool(n & 1)

(In Python we could just return 1 or 0 but I like my Boolean predicates to return actual bools.)

Okay, we're going to make a version of power() that does less work using a while loop and an accumulator:

def power(n, b):
    p = 1
    while n:
        if odd(n):
            p *= b
        n >>= 1
        b *= b
    return p

By decomposing the number n into it's binary representation and using that to guide squaring (doubling the power of b) We get the correct number of multiplications of b by itself. When n is large this is far more efficient (approximately O(log2).)

Anyway, let's change that to a functional programming style:

def powerW(n, b):
    return powerW_(n, 1, b)

def powerW_(n, p, b):
    if n == 0:
        return p
    if odd(n):
        pp = p * b
    else:
        pp = p
    return powerW_(n >> 1, pp, b * b)

The powerW() functions sets the inital value of p for a recursive powerW_() function that performs the same logic and math.

Curry

The first step is to curry the function.

The p and b parameters are "dynamic" and n is "static"

def powerW(n, b):
    return powerW_(n)(1)(b)
    

def powerW_(n):
    def pw_p(p):
        def pw_b(b):
            if n == 0:
                return p
            if odd(n):
                pp = p * b
            else:
                pp = p
            return powerW_(n >> 1)(pp)(b * b)
        return pw_b
    return pw_p

Lambda lowering

Next we pull out the conditional based on n:

def powerW_(n):
    if n == 0:
        fn = lambda p: lambda b: p
    elif odd(n):
        fn = lambda p: lambda b: powerW_(n >> 1)(p * b)(b * b)
    else:
        fn = lambda p: lambda b: powerW_(n >> 1)(p)(b * b)
    return fn

Expression lifting

Next the expression based on n is lifted out of the lambdas:

This is a recursive call to the function (which returns a function.)

def powerW_(n):
    if n == 0:
        return lambda p: lambda b: p

    f = powerW_(n >> 1)

    if odd(n):
        fn = lambda p: lambda b: f(p * b)(b * b)
    else:
        fn = lambda p: lambda b: f(p)(b * b)
    return fn

Code via Quoting

Now all that remains is to change the return values to quoted forms of the output functions, and dequote the recursive call's output (f -> ({f}) the parenthesis are so that the scoping of the lambdas (which will of course all use the same variable names) remains clear to the Python interpreter, and the curly brackets are the de-quoting mechanism of Python's "f-strings".)

def compile_power(n):
    if n == 0:
        return 'lambda p: lambda b: p'

    f = compile_power(n >> 1)

    if odd(n):
        fn = f'lambda p: lambda b: ({f})(p * b)(b * b)'
    else:
        fn = f'lambda p: lambda b: ({f})(p)(b * b)'

    return fn

You would use it like this (note the initialization of p to 1. That only has to be done once when the function is first used, and it's a separate stage than compiling the source code. You get the source code for a power-to-the-nth function, "compile" that source with the Python eval() function to get a function of the form: lambda p: lambda b: ..., and then call that function with p=1 to initialize it and return a function of the form: lambda b: ..., which is our actual "to-the-nth" function.)

source = compile_power(5)
pow5 = eval(source)(1)
two_to_the_fifth_power = pow5(2)

The generated source code:

lambda p: lambda b: (lambda p: lambda b: (lambda p: lambda b: (lambda p: lambda b: p)(p * b)(b * b))(p)(b * b))(p * b)(b * b)

Let's reformat that a little to make it more clear:

lambda p: lambda b: (
lambda p: lambda b: (
lambda p: lambda b: (
lambda p: lambda b: p
)(p * b)(b * b)
)(p)    (b * b)
)(p * b)(b * b)

It becomes clear that b is squared on each iteration but p is multiplied by b only on the first and third iterations (as expected by the binary form of 5: 101) (the final, fourth iteration just returns p.) So we get b**1 * b**4 = b**5. Each iteration squares b doubling the coefficient:

• 1 b**1
• 2 b**2
• 3 b**4
• 4 b**8

and so on...

We use the n parameter as a list of Boolean values that tell us when to multiply our current power of b onto (into?) our running product p.

Pretty cool, eh?

(I don't like this function though because as nice as it is it always does one extra multiplication (of b * b) and then throws it away at the end. I'd like to circle back to this someday and figure out a nice way to avoid that.)

Teaser: in another paper he shows how to use this technique to derive a Prolog compiler!