Looking at the most beautiful program ever written

Looking at the most beautiful program ever written - part 1

I am going to have a look at what William Byrd presented as The most beautiful program ever written.

Beauty here refers to computer programs, specifically about Lisp. There might be errors as this is something I wrote to make sense of that interpreter, proceed at your own risk.

Thanks a lot to Carl J. Factora for the help.

The program

Have a look and see if you like it. The original code could be found here, while pmatch could be found here I've slightly modified it to be run by the Racket interpreter, you could find the complete code here.

Also, Racket has been wonderfully helping me with its features, REPL and (require racket/trace) over the rest.

(define eval-expr
  (lambda (expr env)
    (pmatch expr
      [`,x (guard (symbol? x))
        (env x)]
      [`(lambda (,x) ,body)
        (lambda (arg)
          (eval-expr body (lambda (y)
                            (if (eq? x y)
                                arg
                                (env y)))))]
      [`(,rator ,rand)
       ((eval-expr rator env)
        (eval-expr rand env))])))

where pmatch is a pattern match macro, and , is unquote, which works this way:

`(1 2 ,(+ 1 1 1)) ;; `(1 2 3))

'(1 2 ,(+ 1 1 1)) ;; '(1 2 (+ 1 1 1))

` is called quasiquote.

Each part

We pattern match expr on three different cases.

symbol?

[`,x (guard (symbol? x))
  (env x)]

If x is a symbol then look it up in the environment. The environment is a poor man's implementation of a hashmap, whenever you see the construct

(lambda (y)
  (if (eq? x y)
      arg
      (env y)))

it means lookup y, if you don't find it look deeper. (this concept took me several hours to understand)

function?

[`(lambda (,x) ,body)
  (lambda (arg)
    (eval-expr body (lambda (y)
                      (if (eq? x y)
                          arg
                          (env y)))))]

If expr is a lambda then return a new lambda that when invoked calls the interpreter once again, with the body of the function as expr argument and yet another lambda as environment, let's focus on that, because it's the key passage. To do so I will take a simple example and work through it.

operator and operand

[`(,rator ,rand)
 ((eval-expr rator env)
  (eval-expr rand env))])))

The last case, the one that splits expr further down into its base parts it's pretty strightforward, for example if you where to match '((lambda (n) n) 42) then '(lambda (n) n) would be rator and '42 would be rand.

Simple example

I'm going to go through each passage when the interpreter is called with

(eval-expr '((lambda (n) n) hello)
           (lambda (arg)
             (if (eq? arg 'hello)
                 'hello
                 (environment arg))))

where environment is defined as

(define environment
  (lambda (y) (error "oops")))

this is how it would look like when first called

(eval-expr '((lambda (n) n) hello)
           (lambda (arg)
             (if (eq? arg 'hello)
                 'hello
                 (environment arg))))

it evaluates to

((eval-expr '(lambda (n) n)
            (lambda (arg)
              (if (eq? arg 'hello)
                  'hello
                  (environment arg))))
((lambda (arg)
   (if (eq? arg 'hello)
       'hello
       (environment arg))) 'hello))

and then evaluates to the following, observe how the second part just evalutes to 'hello while the first goes on expanding the environment

((lambda (arg)
   (eval-expr 'n (lambda (y)
                   (if (eq? 'n y)
                       arg
                       ((lambda (arg)
                          (if (eq? arg 'hello)
                              'hello
                              (environment arg))) y)))))
 'hello)

now we apply the lambda to 'hello thank to the surrounding parens which means subsituting 'hello to the first arg, removing the surrounding parens and the surrounding lambda

(eval-expr 'n (lambda (y)
                (if (eq? 'n y)
                    'hello
                    ((lambda (arg)
                       (if (eq? arg 'hello)
                           'hello
                           (environment arg))) y))))

this matches the symbol, so the env, which is the crazy thing on the right has to be applied to 'n

((lambda (y)
   (if (eq? 'n y)
       'hello
       ((lambda (arg)
          (if (eq? arg 'hello)
              'hello
              (environment arg))) y))) 'n)

which means substituting 'n to every y

(if (eq? 'n 'n)
    'hello
    ((lambda (arg)
       (if (eq? arg 'hello)
           'hello
           (environment arg))) 'n))

now we can apply the lambda to 'n

(if (eq? 'n 'n)
    'hello
    (if (eq? 'n 'hello)
        'hello
        (environment 'n)))

which expands to the error in the else branch

(if (eq? 'n 'n)
    'hello
    (if (eq? 'n 'hello)
        'hello
        (error "oops")))

and proceed to figure out that the result value is 'hello. Yas. That was quite long but hopefully I made some sense here and there.

If you were to call the interpreter this way instead:

(eval-expr '(identity hello)
           (lambda (arg)
             (if (eq? arg 'hello)
                 'hello
                 (environment arg))))

You would get the "oops" error because identity is not bound in the environment! Neat right? Right? lol.

So what?

So all the interpreter is doing is eventually evaluating symbols in an environment.

The most important bit IMHO is this:

the blu part is the environment, which is going to be expanded at each recursive step, with a new entry
the green circled expressions are referring to the same thing, the argument of the lambda passed as input is going to end up in that position in the environment
the pink circled expressions are referring to the same thing too, same for the red ones which are going to be same thing whenever the symbol base case hits: the environment (on the right) is applied to body
I've used a dotted red circle for arg meaning that ultimately is similar to y as it receives the body when the base case hits

I am going to defer a more complete example to part 2, if I manage to understand it.

lazywithclass/blog-post.md