Adrian Wilkins-Caruana

about résumé blog ~ rss

Pythagorean Triads, with Lambda Calculus, in Python

I implement a familiar program using an unfamiliar paradigm.

Published: August 29, 2021.

Intro

A common piece of advice for learning a new programming language is to focus on first implementing a useful and tangible program. This exercise familiarises the user with a selection of features of the language, but more importantly it instills a sense of accomplishment and newfound competence. I have a number of issues with this approach. First, it only really makes sense to do this if the applicability of the unfamiliar language to the task outweighs the inefficiencies of using a more familiar language. More importantly, though, this approach also assumes that you have the motivation and a task in the first place, which is not the situation I usually find myself in: "I should try and learn \(X\)."

Instead, my first step in a new programming language, beyond "Hello world!", is to implement a very familiar yet useless program: finding Pythagorean triads. I did this during undergrad to learn C, in Python the day before my starting my first full-time engineering role, and in the same role to learn VHDL.

This weekend, I set out to deepen my understanding of lambda calculus (\(\lambda\)). However, instead of trying to do this while simultaneously learning a functional programming language, I did so using Python. I confirmed first-hand that it is possible and absolutely suboptimal in every way, except for helping me understand \(\lambda\).

Groundwork

Computing concepts often have useful analogies to physical phenomena that aid in understanding the system. True is 'on', while False is 'off'. 00001101 is just base-2 for 13. However, I previously struggled to grasp \(\lambda\) due to a lack of such a comparison. Implementing \(\lambda\) in Python was crucial in helping me understand the fundamentals. Where I lacked physical analogies, I had analogies in Python's constructions.

# bool
ID = lambda x: x
TRUE = lambda x: lambda y: x
FALSE = lambda x: lambda y: y

ID just means to do nothing, this makes sense. Boolean's are a functional composition of two arguments – given two states, TRUE and FALSE uniquely represent each. From here, the foundations of a more complete computation system emerge.

# Logic
NOT = lambda x: x(FALSE)(TRUE)
AND = lambda x: lambda y: x(y)(x)
OR  = lambda x: lambda y: x(x)(y)
XOR = lambda x: lambda y: x(NOT(y))(y)
XNOR = lambda x: lambda y: NOT(XOR(x)(y))

Numerals and Arithmetic

The Church numerals are a way of representing numbers in \(\lambda\) via repeatedly 'doing-something'. For example, a number n can be understood as incrementing a value, say 0, n times.

# Church Numerals
ZERO   = lambda f: lambda x: x
ONE    = lambda f: lambda x: f(x)
TWO    = lambda f: lambda x: f(f(x))
THREE  = lambda f: lambda x: f(f(f(x)))
FOUR   = lambda f: lambda x: f(f(f(f(x))))

Arithmetic operations compose functions to adjust the number of times 'something-is-done'.

# Arithmetic
INC = lambda n: lambda f: lambda x: f(n(f)(x))
ADD = lambda m: lambda n: lambda f: lambda x: m(f)(n(f)(x))
MULT = lambda m: lambda n: lambda f: lambda x: m(n(f))(x)
EXP = lambda m: lambda n: n(m)
DEC = lambda n: lambda f: lambda x: n(lambda g: lambda h: h(g(f)))(lambda _: x)(ID)
SUB = lambda m: lambda n: n(DEC)(m)
DIFF = lambda m: lambda n: ADD(SUB(m)(n))(SUB(n)(m))

Comparison operations compare how many times 'something-is-done' to each argument.

# Compare
ISZERO = lambda x: x(lambda _: FALSE)(TRUE)
GTE    = lambda x: lambda y: ISZERO(SUB(y)(x))
LTE    = lambda x: lambda y: ISZERO(SUB(x)(y))
EQ     = lambda x: lambda y: AND(GTE(x)(y))(LTE(x)(y))

Data Structures

Pairs encapsulate two arguments with a function that takes a function argument.

# Pairs
PAIR = lambda x: lambda y: lambda z: z(x)(y)
FIRST = lambda p: p(TRUE)
SECOND = lambda p: p(FALSE)

Lists use nested pairs, with special pairs indicating the start and end of the list.

# Lists
LIST = PAIR(TRUE)(TRUE)
PREPEND = lambda xs: lambda x: PAIR(FALSE)(PAIR(x)(xs))

Y-Combinator

While Python has recursion, \(\lambda\) does not. The Y-combinator achieves recursion using \(\lambda\) by defining a function and mapping it to itself. When used with more than one argument, it can implement simple recursion and achieve imperative concepts like for loops.

# Y-Combinator
Y = lambda f: (
    (lambda x: f(lambda y: x(x)(y)))
    (lambda x: f(lambda y: x(x)(y)))
)

Pythagorean Triads

Pythagorean triads are the sides of a right-angled triangle \((a, b, c)\) where \(a\), \(b\), and \(c\) are integers. \((3, 4, 5)\) is a Pythagorean triad, and is the smallest possible example (Fig. 1). Below, we use the above constructions to find triads where \(a \leq n\).

To start, we construct a LIST of PAIR elements containing candidates for \(a\) and \(b\), and a function to compute \(a^2+b^2\).

CONCAT = Y(
    lambda f: lambda l0: lambda l1: EMPTY(l0)
    (lambda _: l1)
    (lambda _: PREPEND(f(DROP(ONE)(l0))(l1))(HEAD(l0)))
    (TRUE)
)
CANDIDATES = Y(
    lambda f: lambda i: lambda j: lambda stop: OR(GT(i)(stop))(GT(j)(i))
    # inner f(i)(INC(j))(i)
    # outer f(INC(i))(j)(stop)
    (lambda _: LIST)
    (lambda _: PREPEND(CONCAT(f(i)(INC(j))(i))(f(INC(i))(j)(stop)))(PAIR(i)(j)))
    (TRUE)
)
A2B2 = lambda x: ADD(EXP(FIRST(x))(TWO))(EXP(SECOND(x))(TWO))

Next, we define a look-up table of perfect squares. This avoids having to implement a square root function, something that is not so simple with integer-only arithmetic. The look-up table is comprised of a LIST of PAIR elements, where the FIRST element of the pairs are the numbers 1 to \(n\), and the SECOND element is the square of the first. To determine if a number is a perfect square, we simply check if it is the second element in any pair in the list.

LI_ZERO_TO_N = Y(
    lambda f: lambda n: EQ(n)(ZERO)
    (lambda _: LIST)
    (lambda _: PREPEND(f(DEC(n)))(n))
    (FALSE)
)
Z_LUT = (
    lambda n: 
    MAP
    (lambda x: PAIR(x)(EXP(x)(TWO)))
    (LI_ZERO_TO_N(n))
)
INT_SQRT = Y(
    lambda f: lambda a2b2: lambda z: OR(EMPTY(z))(GT(a2b2)(SECOND(HEAD(z))))
    (lambda _: ZERO)
    (lambda _: EQ(SECOND(HEAD(z)))(a2b2)(FIRST(HEAD(z)))(f(a2b2)(DROP(ONE)(z))))
    (TRUE)
)

Finally, we define a function to indicate which candidates are Pythagorean triads, and keep only the candidates that are.

GET_TRIADS = (
    lambda candidates:
    MAP
    (lambda x: PAIR(x)(INT_SQRT(A2B2(x))(Z_LUT(N))))
    (candidates)
)
TRIAD_LI = lambda triads: FILTER(lambda x: NOT(ISZERO(SECOND(x))))(triads)

Code

You can find the code on my Github here. Be warned, it takes Python's sluggishness to a new level.