Project 1: Build a Lisp Interpreter | Racket Projects

Code on GitHub: All examples from this tutorial are available at racket-programming-series/projects/lisp-interpreter — clone the repo and follow along!

"If you don't know how compilers work, then you don't know how computers work." — Steve Yegge.

Racket makes writing interpreters easy because its own syntax (S-expressions) is processed using the same tools we will use to process our language.

The Goal: "Mini-Scheme"

We will support:

• Arithmetic: (+ 1 2)
• Definition: (define x 10)
• Conditionals: (if (> x 5) 1 0)
• Functions: (lambda (x) (+ x 1))

The Environment

We need a way to store variables.

#lang racket

(define env (make-hash))
(hash-set! env '+ +)
(hash-set! env '* *)
(hash-set! env '> >)

The Evaluator (eval)

This is the heart of the beast.

(define (my-eval exp)
  (match exp
    ; 1. Symbols (Variables)
    [(? symbol?) (hash-ref env exp)]
    
    ; 2. Numbers (Self-evaluating)
    [(? number?) exp]
    
    ; 3. Define
    [(list 'define var val)
     (hash-set! env var (my-eval val))]
    
    ; 4. If
    [(list 'if test conseq alt)
     (if (my-eval test)
         (my-eval conseq)
         (my-eval alt))]
    
    ; 5. Lambda (Functions)
    [(list 'lambda (list param) body)
     (lambda (arg)
       (hash-set! env param arg)
       (my-eval body))]
    
    ; 6. Function Application
    [(list f arg)
     ((my-eval f) (my-eval arg))]
     
    [else (error "Unknown expression" exp)]))

Running It

(my-eval '(define x 10))
(my-eval '(if (> x 5) 100 0)) ; Returns 100

Note: This basic implementation has a bug with closures (scope). Can you spot it? We share one global env. Real interpreters create a new environment for each function call!

Summary

In 30 lines, we built a calculator that processes logic. This is the foundation of structure and interpretation of computer programs.