Mystery

Sadly, this is the last lec­ture. We hope you’ve enjoyed the show. Before you go, we have just one last trick to show you. Today we’ll talk about some top­ics that are close to our hearts.

A Taste of Lisp

This is the most beau­ti­ful pro­gram ever writ­ten. I encour­age you to watch Will Byrd’s amaz­ing talk on the same sub­ject. I will be pre­sent­ing a much abridged ver­sion. We’re going to write a Lisp inter­preter in Lisp. But first, let’s learn some Lisp.

Atoms.

5
#t
'foo

Lists.

(list 5)
(list 5 6)
(list (list 5) 6)

Appli­ca­tion.

(null? '())
(null? 5)

Quo­ta­tion.

(quote 5)
'(5 6)
'(null? 5)

Abstrac­tion.

+
(λ (x) x)
((λ (x) x) 5)

Bind­ing.

(define foo 'bar)
(define dou­ble (λ (x) (+ x x)))

Con­di­tions.

(if (null? 5)
    6
    7)

(match (list 3 4)
  [(list x y) (+ x y)])

Done.

Lisp in Lisp

We’re going to write a Lisp inter­peter in Lisp. First a sim­ple cal­cu­la­tor inter­preter as an appe­tizer.

(define eval-expr
  (λ (expr)
    (match expr
      [n #:when (num­ber? n) n]
      [(list 'add1 e)
       (add1 (eval-expr e))]
      [(list '+ e1 e2)
       (+ (eval-expr e1) (eval-expr e2))])))

Fine, but this is bor­ing. It isn’t Tur­ing-com­plete. When’s the main course?

(define eval-expr
  (λ (expr env)
    (match expr
      ;; bor­ing
      [n #:when (num­ber? n) n]
      [(list 'add1 e)
       (add1 (eval-expr e env))]
      [(list '+ e1 e2)
       (+ (eval-expr e1 env) (eval-expr e2 env))]

      ;; fun
      [(list rator rand)
       ((eval-expr rator env) (eval-expr rand env))]
      [x #:when (sym­bol? x) (env x)]
      [(list 'λ (list x) body)
       (λ (arg)
         (eval-expr body (λ (y)
                            (if (eq? x y)
                                arg
                                (env y)))))])))

I’m full, but if you aren’t you may want to have some dessert.

References

Learn­ing about Lisp and inter­preters is a life-long endeavor, but there are plenty resources to get started.