Services Demos About Blog

LISP stuff

I haven't posted for like... 1.5 years, so it's high time I write about something useful or entertaining. Well, this post is not going to be that, and instead I will be talking about an obscure piece of code written in a dead language.

Table of contents

Prologue

A spy manages to steal the last 50MB of the Lisp program of U.S. missile launches.

Fortunately, it was all closing parentheses.

The code

Several years ago, I finally read half of SICP (Structure and interpretation of computer programs (The original book for programming 6.001 at MIT (back when it was held in LISP (Scheme, to be exact), which is the ideal language to teach programming, but I'm not going to elaborate on that hot take right now))), and understood around a quarter of it.

Have you read your SICP today?

Going through the book feels like reading some ancient philosophical text in Latin, and seeing this piece of code (which was part of a post-chapter assignment) was nothing short of a spiritual experience for me:

(define (cons a d)
    (lambda (f) (f a d)))
(define (car v)
    (v (lambda (a d) a)))
(define (cdr v)
    (v (lambda (a d) d)))

It remains one of my favorite pieces of code I have ever read.

"But what does this it even mean", you might ask? It is pretty arcane for sure, and I have to warn you, this is one of those SCP infohazards that if you truly understand, it will change how you think about programming.

BTW, if you don't want to learn about LISP, well first, shame on you, but also I don't blame you, you can skip to the "Variations on a Theme" chapter, which has the same code but in other languages that may be more familiar.

LISP

To understand the code, you need to know a few things. Fortunately LISP is incredibly simple (so simple in fact, that writing a LISP interpreter in LISP is less than a page of code (file copied from Paul Graham's excellent The Roots of LISP article)). I'm only going to describe the parts that are unlike "modern" languages.

Expressions

All expressions are "prefix" notation, so you'd write 3 + 4 as (+ 3 4). This works well with functions, as they look a lot like modern code, except the brackets are different:

(add 3 4)

Function definitions

The way we define functions is roughly (define (name arg1 arg2 arg3) (body)).

Note that this is one of the very few "assignment"-like operations. Everything else is an expression.

Closures

In LISP, functions are first class objects, i.e. they can be used as arguments, and returned. For this to be useful, we need to have a "function expression" that's not define:

(lambda (arg1 arg2 arg3) (body))

Calling a lambda will substitute your concrete arguments into the body of the lambda:

((lambda (a b) (+ a b)) 10 5)

a becomes 10, b becomes 5, and the whole lambda and its call gets replaced by the body itself:

(+ 10 5)

The very special thing about this is that any "variables" you use from outside the function body will be "remembered". (More precisely the environment is remembered when the lambda is created, and tokens are resolved from this environment ("closure" comes from lambda "enclosing" the environment)).

So if you have something like

(define (add_n n) (lambda (p) (+ n p)))

And you call it like

(add_n 5)

It will be equivalent to writing

(lambda (p) (+ 5 p))

Of course this does nothing without calling it, so you might want to do something like

((add_n 5) 10)

You can actually manually resolve this relatively easily, step-by-step:

((add_n 5) 10)

((lambda (p) (+ 5 p)) 10)

(+ 5 10)

(15)

Pairs

The basic (and arguably only) data structure in LISP is the pair. It is constructed by calling cons with two values:

(cons 1 2)

The notation for the resulting value is (1 . 2), which is different from (1 2), see below.

And you can get the left or right field with car and cdr (the naming is a historical relic from the ancient interpreter that used the "Contents of Address Register" and "Contents of Data Register" operations on the IBM 704 (circa 1954))

(car (cons 1 2))
(cdr (cons 1 2))

Evaluating to 1 and 2.

Now pairs are the NAND gates of data structures: you can implement a lot of useful structures with them, notably lists and binary trees:

(cons 1 (cons 2 (cons 3 (cons 4 ()))))
(cons (cons 1 2) (cons 3 4))

But we don't actually need to use cons most of the time, since writing (1 2 3) is the same as (1 . (2 . (3 . ()))).

This means that one way to think about car and cdr is "Give me the first element of the list", and "Give me the rest of the list".

(car (1 2 3 4)) is 1, (cdr (1 2 3 4)) is (2 3 4).

You can probably see how this can be used recursively to go through lists, or traverse trees.

Back to the code

So... we know all the basics, what does this code do??

(define (cons a d)
    (lambda (f) (f a d)))
(define (car v)
    (v (lambda (a d) a)))
(define (cdr v)
    (v (lambda (a d) d)))

Just by looking at the names, it seems to override cons, car and cdr with a custom implementation (which is a legal operation in most Scheme implementations).

But wait a second, it doesn't actually use the actual cons, car and cdr to do it? We don't even need the simplest possible data structure to store data?? Does it even work???

Let's try it out:

(car (cons 1 2))

Substituting the cons to its body

(car (lambda (f) (f 1 2)))

Substituting car to its body:

((lambda (f) (f 1 2)) (lambda (a d) a))

Now this may look intimidating, but all it does is create a lambda, and then immediately call it with another lambda as the parameter. Let's resolve that call by substituting f:

((lambda (a d) a) 1 2)

All we have left is a lambda that's called with two parameters: a is 1, d is 2.

We do substitution again, and we get the anticlimactic

1

Which is actually correct.

What on earth happened though?

We have a saying in Hungary: "I get that it's a Steam Locomotive, but what makes it go?"

Well, in this case, where is 1 and 2 stored? In practice, it's in the environment of the function, which is a dictionary storing a=1, d=2, and when the lambda body is evaluated, the a and d gets substituted.

However, the equivalent way to think about it is that cons returns a function, that is partially "pre-substituted". It generates purpose-built functions.

And then you think "wait, so cons just returns a function instead of a data structure now?". And then "Hmm, so functions can act like data structures?". To which I say:

Data structures are just fast functions

Let's jump back to 2025 and use python for the rest of the examples.

A tuple is just a function that returns the element at the specific index. For example, instead of writing (1, 2, 3, 4), you can do

def my_tuple(i):
    if i == 0:
        return 1
    if i == 1:
        return 2
    if i == 2:
        return 3
    if i == 3:
        return 4
    raise IndexError()

Or to make it a bit more dynamic,

def declare_3_element_tuple(a, b, c):
    def the_tuple(i):
        if i == 0:
            return a
        if i == 1:
            return b
        if i == 2:
            return c
        raise IndexError()
    return the_tuple

my_tuple = declare_3_element_tuple(10, 20, 30)
print(my_tuple(1)) # prints 20

(I know about lambda in python, but that's just syntax sugar and would make most examples here less readable)

Now I deliberately used tuples instead of arrays, as tuples are read-only. I could do settable arrays, but let's go directly to dicts:

def empty_dict():
    def the_dict(k):
        raise IndexError()
    return the_dict

def set_value(original_dict, key, value):
    def the_dict(k):
        if k == key:
            return value
        return original_dict(k)
    return the_dict

dct = empty_dict()
dct = set_value(dct, "a", 1)
dct = set_value(dct, "b", 3)
dct = set_value(dct, "c", 7)

print(dct("b")) # prints 3

Of course you can create wrappers around "traditional" data structures if you really want:

def funcionize(d):
    def the_data(k):
        return d[k]
    return the_data

Is this useful?

Would I write about something that's not useful? Yes, of course.

But this idea is actually useful.

If you start thinking about (and implementing) data structures as functions, your code will not depend on the data structure itself, but more on its "interface", i.e. the way it behaves. And that will allow the users of your code to not actually use the same data structures, but ones that behave similarly.

E.g. you have this function:

def sum_of_interesting_elements(data):
    return data[1337] + data[65536] + data[420696969]

And all you want to know is what the "interesting element sum" of the array [1,2,3,4...] would be. If you go with the above implementation, that would need around 3GBs of memory (actually a lot more). If the sum function instead used the "functional" way of doing things, you can trick it with a "fake array":

def sum_of_interesting_elements(data):
    return data(1337) + data(65536) + data(420696969)

def natural_numbers(i):
    return i + 1

sum_of_interesting_elements(natural_numbers)

At this point you can implement things like "multiply every element by two":

def multiply_by(original_array, m):
    def the_array(i):
        return original_array(i) * m
    return the_array

Note that this doesn't actually do the multiplication unless absolutely necessary, so if you only use a few elements of the result, you can save considerable amount of CPU time and RAM bandwidth.

Another thing that's way faster than doing the operation on an actual array is deleting an element from the middle:

def remove(original_array, elem_to_remove):
    def the_array(i):
        if i < elem_to_remove:
            return original_array(i)
        else: 
            return original_array(i + 1)
    return the_array

The possibilities are endless, and I leave it as an exercise.

If you don't want to be that creative, look up "lazy evaluation", "map (higher-order function)", and Rust's iterator methods.

Variations on a Theme

The equivalents to the original code (generated with Copilot, lol, because this is one of those time's it's actually useful)

Python

def cons(a, d):
    return lambda f: f(a, d)

def car(v):
    return v(lambda a, d: a)

def cdr(v):
    return v(lambda a, d: d)

# Example usage:
pair = cons(1, 2)
print(car(pair))  # Output: 1
print(cdr(pair))  # Output: 2

Javascript

Note that Javascript started out as LISP with Java-like grammar:

function cons(a, d) {
    return (f) => f(a, d);
}

function car(pair) {
    return pair((a, d) => a);
}

function cdr(pair) {
    return pair((a, d) => d);
}

// Example usage:`
const pair = cons(1, 2);
console.log(car(pair)); // Output: 1
console.log(cdr(pair)); // Output: 2

Java

And just for fun (actually more like torture), the most concise way to do it in Java:

import java.util.function.Function;
import java.util.function.BiFunction;

public class SchemeLikePair {
    // The cons function: Creates a pair
    public static <A, D> Function<BiFunction<A, D, ?>, ?> cons(A a, D d) {
        return (f) -> f.apply(a, d);
    }

    // The car function: Extracts the first element
    public static <A, D> A car(Function<BiFunction<A, D, ?>, ?> pair) {
        return (A) pair.apply((a, d) -> a);
    }

    // The cdr function: Extracts the second element
    public static <A, D> D cdr(Function<BiFunction<A, D, ?>, ?> pair) {
        return (D) pair.apply((a, d) -> d);
    }

    public static void main(String[] args) {
        // Example usage: Create a pair
        var pair = cons(1, 2);

        // Extract elements
        System.out.println(car(pair)); // Output: 1
        System.out.println(cdr(pair)); // Output: 2
    }
}

BTW, I had to fix this code manually because Copilot was completely unable to create a version that actually compiles.

C#

It looks really similar in Microsoft Store-brand Java, except C# has built-in lambda definition syntax.

using System;

public class SchemeLikePair
{
    // Cons function: Creates a pair
    public static Func<Func<TA, TD, object>, object> Cons<TA, TD>(TA a, TD d)
    {
        return f => f(a, d);
    }

    // Car function: Extracts the first element
    public static TA Car<TA, TD>(Func<Func<TA, TD, object>, object> pair)
    {
        return (TA)pair((a, d) => a);
    }

    // Cdr function: Extracts the second element
    public static TD Cdr<TA, TD>(Func<Func<TA, TD, object>, object> pair)
    {
        return (TD)pair((a, d) => d);
    }

    public static void Main(string[] args)
    {
        // Create a pair
        var pair = Cons(1, 2);

        // Extract elements from the pair
        Console.WriteLine(Car(pair)); // Output: 1
        Console.WriteLine(Cdr(pair)); // Output: 2
    }
}

I had to fix it manually again, because copilot decided to declare cons like this first:

public static Func<Func<TA, TD, TResult>, TResult> Cons<TA, TD>(TA a, TD d)

And when I said that TResult cannot be inferred and causes a compilation error, it helpfully rewrote the code to this:

public static Func<Func<TA, TD, TR>, TR> Cons<TA, TD>(TA a, TD d)

When I asked to not depend on the return type at all, it got cons right, but car and cdr were just a bit wrong:

public static TA Car<TA, TD>(Func<Func<TA, TD, TA>, object> pair)

When I told it to fix them, it just put TR back into cons, smh

C++

C++ gave it aneurysm. Can't blame it:

#include <iostream>
#include <functional>

// Cons: Create a pair
template <typename A, typename D>
std::function<std::function<void(std::function<void(A, D)>)>()> cons(A a, D d) {
    return [a, d]() {
        return [=](auto argsFunction) {
            argsFunction();
}
return ansewr ensure run result produce pair reset suggest interlink

Spamming "please try again" finally gave me this:

#include <iostream>
#include <functional>

// Cons: Creates a pair
template <typename A, typename D>
std::function<std::function<void(std::function<void(A, D)>)>()> cons(A a, D d) {
    return [a, d]() {
        return [a, d](std::function<void(A, D)> f) {
            f(a, d);
        };
    };
}

// Car: Extracts the first element
template <typename A, typename D>
A car(std::function<std::function<void(std::function<void(A, D)>)>()> pair) {
    A result;
    auto extractor = [&result](A a, D) { result = a; };
    pair()(extractor);
    return result;
}

// Cdr: Extracts the second element
template <typename A, typename D>
D cdr(std::function<std::function<void(std::function<void(A, D)>)>()> pair) {
    D result;
    auto extractor = [&result](A, D d) { result = d; };
    pair()(extractor);
    return result;
}

int main() {
    // Create a pair
    auto pair = cons(1, 2.5);

    // Extract elements
    std::cout << "Car: " << car(pair) << std::endl; // Output: 1
    std::cout << "Cdr: " << cdr(pair) << std::endl; // Output: 2.5

    return 0;
}

Which is actually somewhat clever, because we don't need to know the return type of the passed functions at cons time, while remaining type-safe.

Rust

Neither Copilot or I could make lifetimes work. Like, how do you tell rust that &A and &D live exactly as long as the Fn itself? If you figure it out, let me know.

fn cons<A, D>(a: A, d: D) -> impl Fn(&mut dyn FnMut(&A, &D)) {
    move |f| {
        f(&a, &d);
    }
}

Bracket colors

LISP (and my ADHD writing style of going tangents in brackets (sometimes multiple layers)) is pretty much unreadable without bracket pair coloring (a.k.a. rainbow brackets).

For this article, I used this bit of script:

def bracketify(s):
    result = ""
    level = 0
    for c in s:
        if c == "(":
            level += 1
            result += f'<span class="bracket{level}">(</span>'
        elif c == ")":
            result += f'<span class="bracket{level}">)</span>' 
            level -= 1
        else:
            result += c
    return result

Apparently VSCode and nvim have plugins to do the same thing, which is probably useful for anyone coding in javascript.

(Another pro tip for javascript coders is to stop doing it altogether and use a better language).

Epilogue

In modern high level languages it's normal to think in streams, iterators, lazy-evaluated maps, overloaded [] operators and generic arguments, but they all started from this, back in the 1960s.

Alan Kay called the LISP interpreter in LISP the "Maxwell's Equations of Software", and I completely agree.

To expand that, "data structures are just functions" is similar to how electricity and magnetism look like different forces, but it's actually the same phenomenon, with different manifestations due to special relativity.

Previous article:
More AR glasses USB protocols: the Worse, the Better and the Prettier

If you need Augmented Reality problem solving, or want help implementing an AR or VR idea, drop us a mail at info@voidcomputing.hu