I had a picnic this weekend and at it I gave Phil a pen plot that I had been meaning to for a while:

I want to explain it here because I think it's cool! This was drawn with a pen plotter, which is a kind of robotic arm that you can place a pen in, and program to draw very precisely. The result is that you can get crisper lines, that were drawn with a pen instead of inkjet (which also means you can get different kinds of inks).

As a piece of art, what I like about it is that while its structure is very nonobvious (you probably could not tell what the different diagrams represent without being told), it's fairly clear that there is a structure to it. Looking at the first one, in the top right, it's fairly clear that that's the "first" of something, compared to the final one in the bottom right, which seems like the "last" of something. If you've looked at enough enumerations of objects, you can probably tell that this is one.

This set of 60 diagrams represents all closed, linear lambda calculus expressions with exactly three variables. That is:

• Closed: there are no free variables,
• Linear: every variable is referenced exactly once,
• Three variables: there are exactly three lambda abstractions in the expression (because of linearity, this is equivalent to there being three variables).

Some expressions like this include:

(\a.(\b.(\c.((c b) a))))
(\a.(\b.(a (b (\c.c)))))
(\a.(a ((\b.b) (\c.c))))

Some things you might observe about these is that since every abstraction/variable reference introduces an object, and every application removes an object, and we want a single value at the end, we must have exactly two applications (this corresponds to how every diagram has three blue circles and two red squares).

So, there are two kinds of objects: abstractions and applications.

Abstractions have:

• an "upwards" output which corresponds to their return value,
• a "downards" output which corresponds to the variable they introduce,
• an input which corresponds to their return value, which they pass through to their output.

Applications have: * a "left" input, which is the function being applied, * a "right" input, which is the value that the function is being applied to, * an output, which corresponds to the result of the application.

So, given an expression like this:

Where the square represents application, we can annotate the flow of data like this:

Once we've done this, we no longer actually need the names of the variables any more; the arrows totally capture the structure of the expression:

Then we can just rotate the image 90 degrees, and rearrange some of the operations to look a little cleaner, then we get the final diagrams.

I saw this construction, or something roughly similar, like, 10 years ago, on reddit or something. I tried to find it again when I was reminded of it recently and was unsuccessful. If you or someone you know knows that post I'd love to see it again.

Maybe it's slightly surprising that there are only 60 such expressions, but it's a nice number of them to render in an image like this. Less surprisingly, the number grows quite quickly with the number of lambda abstractions, it's A062980 on OEIS.

Generating the set of lambdas is also simple:

import copy

class Var:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return self.name

class App:
    def __init__(self, left, right):
        self.left = left
        self.right = right

    def __repr__(self):
        return f"({self.left} {self.right})"

class Abs:
    def __init__(self, v, body):
        self.v = v
        self.body = body

    def __repr__(self):
        return f"(\\{self.v}.{self.body})"

# print(Abs("a", Abs("b", App(Var("a"), Var("b")))))

def partitions(a):
    if len(a) == 0:
        yield [[], []]
    else:
        for [l, r] in partitions(a[1:]):
            yield [[a[0]] + l, r]
            yield [l, [a[0]] + r]

def run(state):
    if len(state["unused"]) == 0 and len(state["scope"]) == 1:
        yield Var(state["scope"][0])
    if len(state["unused"]) > 0:
        used_v = state["unused"][0]
        new_state = { "scope": state["scope"] + [used_v], "unused": state["unused"][1:] }
        for expr in run(new_state):
            yield Abs(used_v, expr)
    for i in range(0, len(state["unused"])+1):
        left_unused = state["unused"][:i]
        right_unused = state["unused"][i:]
        for [left_scope, right_scope] in partitions(state["scope"]):
            left_state = { "unused": left_unused, "scope": left_scope }
            right_state = { "unused": right_unused, "scope": right_scope }
            if left_state == state or right_state == state:
                continue
            for left in run(left_state):
                for right in run(right_state):
                    yield App(left, right)


lambdas = [r for r in run({
    "unused": ["a", "b", "c"],
    "scope": [],
})]

Doing the layout is left as an exercise to the reader, though.