Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 38 ยท Projects and Practice

Project: A Mini Scheme Interpreter

Build a small Scheme interpreter: tokenizer, parser, environments, closures, if, define, let and tail calls. Racket version read-only, a full runnable JavaScript version included.

The best way to understand a language is to write one. A Scheme interpreter is famously small because the language has so little syntax: numbers, symbols and parenthesized lists. In this project you build a mini Scheme with arithmetic, define, if, lambda, let, quote and recursion, including a loop that survives a million iterations thanks to tail-call handling.

The core is an evaluator that takes an expression and an environment (a mapping from names to values) and returns a value. You already know every piece: lists as code (quote and code as data), closures, tail calls and error handling. We write the working version in JavaScript so it runs here, and show how the Racket version looks.

Racket itself cannot run on this site. The Racket sketch is read-only. The JavaScript interpreter is a complete, runnable program written for this lesson; it is not Racket, but it implements a Scheme subset.

The design

flowchart LR
  S["source text"] --> T["tokenize"]
  T --> P["parse: tokens to nested lists"]
  P --> E["evaluate with environment"]
  E --> V["value"]

Four small steps: text to tokens, tokens to data, data to value.

  1. Tokenize: put spaces around parentheses, split on whitespace.
  2. Parse: build nested arrays; numbers become JavaScript numbers, everything else is a symbol (a string).
  3. Environments: a chain of scopes. A new scope is created for each function call; lookup walks outward.
  4. Evaluate: self-evaluating numbers, variable lookup, special forms (quote, if, define, lambda, let, begin, set!), and procedure application.

A Racket sketch

In Racket the evaluator is shorter, because the reader already parses and match destructures the forms. This is a sketch of the same design (read-only):

RACKET
#lang racket

(define (eval-expr expr env)
  (match expr
    [(? number?) expr]
    [(? symbol?) (hash-ref env expr)]
    [`(quote ,datum) datum]
    [`(if ,test ,then ,else)
     (if (eval-expr test env) (eval-expr then env) (eval-expr else env))]
    [`(lambda ,params ,body)
     (lambda args
       (eval-expr body (for/fold ([e env]) ([p params] [a args])
                         (hash-set e p a))))]
    [`(,f . ,args)
     (apply (eval-expr f env) (map (lambda (a) (eval-expr a env)) args))]))

It uses Racket's own lambda to represent closures, which is a shortcut. In our JavaScript version we build closures explicitly, so you can see exactly what a closure is: parameters, a body and the environment where it was created.

The runnable interpreter

Read the code in order: tokenize, parse, Env, evaluate. The evaluator is a loop so that calls in tail position replace the current expression instead of recursing, which gives the same constant-stack guarantee Scheme requires.

JS A mini Scheme interpreter in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Three things are worth noticing. First, sum-to runs a million iterations without a stack overflow: tail calls in if, begin, let and closure application replace expr and env and continue, so JavaScript's own stack never grows. Second, make-counter proves closures work: each call to (make-counter) has its own count, kept alive by the Env the closure captured. Third, fact is not tail recursive, so it uses a JavaScript stack frame per level, and (fact 100000) would overflow here even though a real Scheme would handle it by growing the stack.

Ideas for extending it

Each extension teaches a concept from this course:

  • More primitives and cond (add cond as a macro-like rewrite into nested if: a first taste of macros).
  • Strings and display for output.
  • define with function syntax, (define (f x) ...), rewritten to lambda while parsing.
  • Error messages with positions, so users see where the mistake is.
  • call/cc escapes, using the technique from call/cc and Escapes: throw a unique token and catch it in the call/cc primitive.
  • A REPL that reads line by line and prints each result.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a closure need to remember?

    The captured environment lets the body find non-local variables later, even after the creating call has returned.
  2. 2. Why does the evaluator use a loop with continue for if, begin, let and calls?

    Replacing expr and env and looping means a tail call is a jump, not a nested recursive call.
  3. 3. How is a variable looked up?

    Each scope has an outer link; find follows it until the name is found or an error is raised.
  4. 4. Why is fact not safe for a huge n in this interpreter?

    (* n (fact ...)) leaves work after the call, so evaluating it nests JavaScript calls.

Summary

  • A Scheme interpreter is tokenizer + parser + environments + a small evaluator.
  • Closures pair parameters and body with the environment of their creation.
  • Looping on tail positions gives constant-stack tail calls.
  • Special forms control evaluation; primitives are ordinary host functions.
  • Extending the interpreter is the best way to learn macros, continuations and error handling.

Next: Project: A Pattern Matcher