Adrian Wilkins-Caruana

about résumé blog ~ rss

Cursed (lambda) For Loops

C-style for loops using Lambda Calculus in Python

Published: August 9, 2022.

Intro

Today, I read a great blog post by Tushar Sadhwani where they implemented C-style for loops in python. Something like:

with _for(i := var(0), i < 10, i + 2):
    print(i)

Sadhwani discusses 3 different implementations, each impressive and disgusting in their own right. If you haven’t read their post yet, go ahead and read it first.

Now that your eyes are bleeding from having seeing Python do things it was never meant to be used for, let’s revisit my own brain-melting Python abuse: lambda calculus (\(\lambda\)). Let’s begin.

Lambda Calculus in Python

Last year, I implemented some \(\lambda\) primitives in Python, and composed them to make a program that computes pythagorean triads. A gross misuse of Python? Yes. But that’s what we’re here for.

Again, if you’re not familiar with this exercise, I recommend you read that blog post before proceeding.

C-style For Loops in \(\lambda\)

Here’s what we’re going for:

FOR(i := ZERO)(LTE(i)(TEN))(ADD(i)(ONE))(
    print(i)
)

We can see that a C-style for loop has four parts:

• A loop variable. In the example, the loop variable is i, but let’s call it VAR.
• A comparison operation, where the VAR is compared to another value. In the example above, this is LTE and the comparison value is 10. Let’s call this comparison COMP.
• An increment operation that changes the value of VAR at the end of each iteration. In the example above, this the operation is ADD, and 1 is the second operand (the first is i). Let’s call this operation INC.
• Finally, the loop also has a body. This is the meat of the loop that is executed at each iteration. In the example above, the body is print(i), but let’s refer to it as BODY.

Operations like LTE and ADD are already implemented, and the Church numerals up to TEN have also been implemented. We can just import them:

from _lambdas import LTE, ADD

Next, we need a way to use our INC and ADD operations such that we can repeatedly keep one of the operands the same without having to carry around the operand throughout the loop, while also being able to keep the other operand free to be called with any value of VAR.

This is quite simple with ADD:

from _lambdas import ONE
ADD(ONE)

This returns a new function that always adds ONE to the first argument.

Next, we need to do COMP. An issue here is that LTE is not associative (i.e., the order of the operands matters). What we can do is create another version of the LTE operation, with the order of the arguments reversed so that we can keep VAR as the final argument:

RLTE = lambda a: lambda b: LTE(b)(a)

This will work, but it’s a bit backwards. To understand what RLTE does, imagine swapping the \(\leq\) sign in the operation. That’s just \(\geq\)! Okay, so what we’ve just created is exactly GTE, so we could equivalently just use that instead.

Next, we must implement FOR. There are two main components of FOR. Firstly, FOR needs some kind of IF statement. If COMP doesn’t hold we need to break out of the loop, otherwise continue onto the next iteration.

In \(\lambda\), boolean primitives (e.g., TRUE and FALSE) are essentially IF statements – they are functions that take two arguments, with one argument being executed if the boolean is TRUE and the other argument being executed if the boolean is FALSE. It looks something like this:

BOOL(exp if true)(exp if false)

The second requirement of the \(\lambda\) FOR is a mechanism that allows looping. The Y-combinator is what we will use to do this since it implements recursion in \(\lambda\). What we need to do now is define a for-loop in a functional, recursive style.

from _lambdas import Y

FOR = Y(
    lambda f: lambda arg: (  # f is this fn (FOR), and arg is its argument
        BOOL  # This is the break condition
        (lambda _: exp_if_true())  # If TRUE, call exp_if_true
        (lambda _: exp_if_false())  # If FALSE, call exp_if_false
        (TRUE)  # This has no effect
    )
)

The final stretch! To implement FOR, we need a recursive function (FOR, aka f) that takes 4 arguments VAR, COND, INC, and BODY. Of the two expression arguments of COND, one needs to simply return (which will break the loop), while the other needs to recursively call FOR (f).

from _lambdas import NOT

FOR = Y(
    lambda f: lambda VAR: lambda COND: lambda INC: lambda BODY: (
        NOT(COND(VAR))  # This is the break clause
        (lambda _: VAR)  # If the break clause is TRUE, return VAR
        # This is where the for-loop executes. We need to do 3 things:
        # - Execute the body of the loop: BODY(...)
        # - Increment VAR: INC(...)
        # - Proceed to the next iteration: f(next i)(COND)(INC)(BODY)
        # Note that the first argument to the Y-Combinator is the function 
        # itself. I.e., f == FOR
        (lambda _: f(INC(BODY(VAR)))(COND)(INC)(BODY))
        (TRUE)
    )
)

That’s it!

Using the for loop

The final thing to do is implement BODY. Let’s run it with ID, a function that does nothing, and print the result:

from _helpers import decode_natural
from _lambdas import ID

BODY = ID

result = FOR(ZERO)(RLEQ(TEN))(ADD(ONE))(
    BODY
)
decode_natural(result)

11

Surprised? Well, there’s a few things going on:

• Firstly, we didn’t print anything during the loop (more on that later), so you’d be forgiven for being surprised without seeing what the intermediate results were.
• Secondly, we’re using the loop variable (in this case, result) outside the context of the loop. This isn’t something that’s possible in C, since the loop variable is constrained to the context of the loop. Knowing what the value of the loop variable is outside the loop context is not something that many people would have an intuition for.

In C, the loop is broken after the last iteration, where VAR is incremented and the break condition is activated, so the incremented value is never seen. But, in our implementation, FOR returns the VAR, and it does this after INC has been run, something which is necessary to activate the break condition! So, essentially what we’re seeing is the value that triggered COND.

What if we want to do something more useful within the loop? To do this, we have two options. If all we want to manipulate other variables, they would need to be passed to FOR as additional arguments, so FOR would need to be modified to accommodate this. Alternatively, if we want to, say, print values inside the for loop, then we need to venture beyond the walls of stateless \(\lambda\).

In this post, I’m going to go with the latter, since I (as evidenced by this post) have no aversion to using code in ways that it wasn’t supposed to.

Here, I’m going to use the python syntax to define a stateful BODY function:

from _lambdas import LIST, APPEND
from _helpers import decode_list

LI = LIST

def BODY(x):
    # Since we're not modifying FOR to take additional arguments,
    # if we want to modify LI, we need to access it via a global
    global LI
    LI = APPEND(LI)(x)
    print(list(map(decode_natural, decode_list(LI))))
    return x

FOR(ZERO)(RLEQ(TEN))(ADD(ONE))(
    BODY
)

[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Code

You can find the code the cursed \(\lambda\) FOR, as well as the pythagorean triads example on my Github here.