Most Beautiful Program Ever

William E. Byrd explores what he considers to be the most beautiful program ever written – a Lisp interpreter written in Lisp – and a few of the many amazing ideas related to this metacircular interpreter.

YOUTUBE OyfBQmvr2Hc The Most Beautiful Program Ever Written, William Byrd

# install chez scheme interpreter (on macos) brew install chezscheme # working directory mkdir most-beautiful cd most-beautiful # download the pmatch library curl -O https://raw.githubusercontent.com/webyrd/quines/master/pmatch.scm # launch scheme chez

# lisp interpreter written in scheme # several functions defined to support factorial: # numbers # zero? # sub1 # * # if # symbols (variable lookup) # "the beautiful part" starts with symbol lookup (load "pmatch.scm") (define eval-expr (lambda (expr env) (pmatch expr [,n (guard (number? n)) n] [(zero? ,e) (zero? (eval-expr e env))] [(sub1 ,e) (sub1 (eval-expr e env))] [(* ,x ,y) (* (eval-expr x env) (eval-expr y env))] [(if ,t ,c ,a) (if (eval-expr t env) (eval-expr c env) (eval-expr a env))] [,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)) ] )))

See `pmatch` library github raw

# initial environment function returns a lookup error (lambda (_) (error 'lookup "unbound")) # for example: (eval-expr 'x (lambda (_) (error 'lookup "unbound"))) Exception in lookup: unbound

# (eval-expr ...) simple examples # (*) (eval-expr '(* 3 4) (lambda (_) (error 'lookup "unbound"))) 12 # (sub1) (eval-expr '(sub1 16) (lambda (_) (error 'lookup "unbound"))) 15 # (lambda) application (eval-expr '((lambda (x) (* x x)) 4) (lambda (_) (error 'lookup "unbound"))) 16

# factorial of 5 implemented in scheme # using "the poor man's y-combinator" (((lambda (!) (lambda (n) ((! !) n))) (lambda (!) (lambda (n) (if (zero? n) 1 (* n ((! !) (sub1 n))))))) 5))

# the big finish: # evaluating 5! in our interpreter (eval-expr '(((lambda (!) (lambda (n) ((! !) n))) (lambda (!) (lambda (n) (if (zero? n) 1 (* n ((! !) (sub1 n))))))) 5) (lambda (_) (error 'lookup "unbound")))

.

Alan Kay was also inspired by Church's original lisp interpreter in lisp.

At about 1hr, Byrd "takes the equal sign seriously" to show how a few more abstractions turn the interpreter into a solver – pretty amazing incantations.

TODO:

- [ ] Explore Lambda Way and Lambdatalk

- [ ] revisit and transcribe some solvers

- [ ] copy `pmatch.scm` & above examples to assets - [ ] change the runbook part to curl assets & run

- [ ] find (again) the lisp-like plugin in the federation - [ ] maybe recreate Byrd's scheme example to that lisp-like dialect so we can run these in the browser?