<commit_before>---
layout: post
permalink: /smallest-lambda-eval/
title: The smallest lambda interpreter in JavaScript
date: 2018-01-25 00:21
---

This post is heavily inspired by
[<NAME>: Programming with noting][1],
[<NAME> on "The Most Beautiful Program Ever Written"][2],
[Guowei LV -- The Most Beautiful Program Ever Written][3].

When I first learned about [Lambda calculus][4], I was amazed by a strong mathematical basis for anonymous functions used in many languages.

Then I wondered: what's the simplest way to represent lambda functions as data?

<!-- more -->

## Representation

Lambda expressions, such as `λa.λb.(a b)` have three parts: Variables (`a`, `b`), Application (`(a b)`) and Abstraction (or creating a function) `(λa.a)`.

The question of representing code as data would be incomplete without mentioning LISP, where code *is* data that can be transformed.
[The Most Beautiful Program Ever Written][3] dives into that topic, and into the question of evaluation.

All of the features in lambda expressions are available in LISP and have a straightforward representation.
However, LISP AST has quite complex data structures: symbols, strings, linked lists... we need to go simpler.

First, let's use [De Bruijn indices][5] -- instead of variable symbols.
TL;DR -- replace variable names with the number of the nested lambda's argument you want to look up.
For example, an implementation of the K combinator `λa.λb.a` becomes `λλ2`, where 2 means "the argument of the second lambda, going up from this position".

Second, note that the lambda notation has a binary operation -- function application, and a single argument syntax for creating a lambda, the argument being lambda body.

Let's use the following representation:

- variable lookup is a positive integer number which represents a De Bruijn index.
- creating a function is a tuple of zero and function body. `λa.a` becomes `[0, 1]` in JS notation.
- function application is a tuple of two values. `λa.λb.(a b)` becomes `[0, [0, [2, 1]]]`.

## Environment

Since variable are represented as indicies, the most straightforward way to represent environment as linked lists. Or a JS tuple `[head, tail]`.

Why not a stack or an array?  Because multiple scopes could reference the same parent scope, with possibly changing values.

Constructing an environment becomes as simple as constructing a tuple `[currentValue, parentEnv]`.

## Evaluation

It's easy to construct a simple evaluator once you've seen one:

```javascript
function Eval(prog, env) {
    if (typeof prog === 'number') {
        // lookup a variable
        while(--prog) { env = env[1]; }
        return env[0];
    } else if (prog[0] === 0) {
        // constructing a new lambda
        return (arg) => Eval(prog[1], [arg, env]);
    } else {
        // function application
        return Eval(prog[0], env)(Eval(prog[1], env));
    }
}
```

The code mangled to 140 characters or less, for no particular [reason](https://twitter.com/):

```javascript
Eval = function E(p, e) {
 if (typeof p=='number'){while(--p){e=e[1]}return e[0]}
 return p[0]==0?(a)=>E(p[1],[a,e]):E(p[0],e)(E(p[1],e))
}
```

And of course, translated to Common LISP for completeness:

```lisp
(defun Eval (prog env)
 (cond
  ((numberp prog)     (nth (1- prog) env))<commit_msg>change language for racket so that highlighter knows how to highlight<commit_after>---
layout: post
permalink: /smallest-lambda-eval/
title: The smallest lambda interpreter in JavaScript
date: 2018-01-25 00:21
---

This post is heavily inspired by
[Tom Stuart: Programming with noting][1],
[<NAME> on "The Most Beautiful Program Ever Written"][2],
[Guowei LV -- The Most Beautiful Program Ever Written][3].

When I first learned about [Lambda calculus][4], I was amazed by a strong mathematical basis for anonymous functions used in many languages.

Then I wondered: what's the simplest way to represent lambda functions as data?

<!-- more -->

## Representation

Lambda expressions, such as `λa.λb.(a b)` have three parts: Variables (`a`, `b`), Application (`(a b)`) and Abstraction (or creating a function) `(λa.a)`.

The question of representing code as data would be incomplete without mentioning LISP, where code *is* data that can be transformed.
[The Most Beautiful Program Ever Written][3] dives into that topic, and into the question of evaluation.

All of the features in lambda expressions are available in LISP and have a straightforward representation.
However, LISP AST has quite complex data structures: symbols, strings, linked lists... we need to go simpler.

First, let's use [De Bruijn indices][5] -- instead of variable symbols.
TL;DR -- replace variable names with the number of the nested lambda's argument you want to look up.
For example, an implementation of the K combinator `λa.λb.a` becomes `λλ2`, where 2 means "the argument of the second lambda, going up from this position".

Second, note that the lambda notation has a binary operation -- function application, and a single argument syntax for creating a lambda, the argument being lambda body.

Let's use the following representation:

- variable lookup is a positive integer number which represents a De Bruijn index.
- creating a function is a tuple of zero and function body. `λa.a` becomes `[0, 1]` in JS notation.
- function application is a tuple of two values. `λa.λb.(a b)` becomes `[0, [0, [2, 1]]]`.

## Environment

Since variable are represented as indicies, the most straightforward way to represent environment as linked lists. Or a JS tuple `[head, tail]`.

Why not a stack or an array?  Because multiple scopes could reference the same parent scope, with possibly changing values.

Constructing an environment becomes as simple as constructing a tuple `[currentValue, parentEnv]`.

## Evaluation

It's easy to construct a simple evaluator once you've seen one:

```javascript
function Eval(prog, env) {
    if (typeof prog === 'number') {
        // lookup a variable
        while(--prog) { env = env[1]; }
        return env[0];
    } else if (prog[0] === 0) {
        // constructing a new lambda
        return (arg) => Eval(prog[1], [arg, env]);
    } else {
        // function application
        return Eval(prog[0], env)(Eval(prog[1], env));
    }
}
```

The code mangled to 140 characters or less, for no particular [reason](https://twitter.com/):

```javascript
Eval = function E(p, e) {
 if (typeof p=='number'){while(--p){e=e[1]}return e[0]}
 return p[0]==0?(a)=>E(p[1],[a,e]):E(p[0],e)(E(p[1],e))
}
```

And of course, translated to Common LISP for completeness:

```racket
(defun Eval (prog env)
 (cond
  ((numberp prog)     (nth (1- prog) env))
{'fraction_non_alphanumeric': 0.11024331631120457, 'fraction_numerical': 0.01321718233703815, 'mean_word_length': 4.014307228915663, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 12, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3941246', 'n_tokens_mistral': 1965, 'n_tokens_neox': 1838, 'n_words': 902}