Skip to content

Instantly share code, notes, and snippets.

@lazywithclass
Last active April 26, 2024 18:22
Show Gist options
  • Save lazywithclass/6af94f652cd59796e9592a5ea5772d17 to your computer and use it in GitHub Desktop.
Save lazywithclass/6af94f652cd59796e9592a5ea5772d17 to your computer and use it in GitHub Desktop.
Looking at the most beautiful program ever written - part 1

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:

oh hai

  • 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.

@adam-singer
Copy link

awesome blog post! qq, what are you using to generate http://lazywithclass.github.io/ from gists? Is this some fancy feature built into github or do you parse your gists and then compile some page from them?

@lazywithclass
Copy link
Author

@adam-singer I've just seen your comment, sorry. I don't usually get any feedback so I didn't bother setting up any notification!
It's really simple and probably wrong: I just write a post as gist and link it manually in the blog

@ibehnam
Copy link

ibehnam commented Aug 14, 2023

Hi, I found your explanation of this program useful. I'm just wondering, what are the deeper implications of this? I believe a lot of programming languages can be written in themselves. What's so special about Lisp in this case? In other words, what's the big deal about "Lisp can be written in Lisp?"

@FranciscoSerrano
Copy link

FranciscoSerrano commented Apr 23, 2024

@ibehnam thats a great question! The big idea about all of this is that Lisp makes no distinction between code and data. Because the code is itself a list, lisp can interpret code like any other data. It's pretty magical. Other programming languages make hard distinctions between code and data and in Lisp they are the same thing.

@ibehnam
Copy link

ibehnam commented Apr 24, 2024

@FranciscoSerrano Thanks for your reply! I know Python also has eval and exec functions. They receive raw strings though, and since there's no s-expressions in Python, it's not easy to parse those strings. I think that's the main difference between Lisp and other languages: with Lisp, it's much easier to parse the string with ,, ```, etc.

@lazywithclass
Copy link
Author

@ibehnam The word is "homoiconic", see https://stackoverflow.com/a/6492824 for a brief explanation.

I believe this is an exercise showing how to write a small interpreter, showing some of Lisp syntax and capabilities during the process (like the homoiconicity property), while keeping it visually similar to what the interpreted program can look like.

This was my first look at an interpreter back then and was baffled by the concept, so it might not be that special to someone accustomed to interpreters :D

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment