A 7-line interpreter in Scheme can implement a Turing-equivalent functional programming language based on the lambda calculus, demonstrating that language implementation can be both simple and educational. The interpreter, which takes about 3 minutes to write, uses the eval/apply design pattern from Structure and Interpretation of Computer Programs and operates on s-expressions parsed by Scheme’s built-in read function.
Overview
The core language is the untyped lambda calculus, which consists of only three constructs: variable references, anonymous functions (written as (λ v . e)), and function application (written as (f e)). Despite its minimalism, the lambda calculus is Turing-equivalent through Church encodings (for data types like booleans and numbers) and the Y combinator (for recursion). A non-terminating program known as Omega—((λ f . (f f)) (λ f . (f f)))—illustrates that the system can express infinite computation.
What it does
The interpreter defines two central functions:
eval: Takes an expression and an environment, returning a value.apply: Takes a function (as a closure) and an argument, then evaluates the function body in an extended environment.
Environments are represented as association lists mapping variables to values. Closures pair a lambda expression with its defining environment, enabling proper lexical scoping.
The full interpreter in R5RS Scheme is:
(define (eval e env)
(cond
((symbol? e) (cadr (assq e env)))
((eq? (car e) 'λ) (cons e env))
(else (apply (eval (car e) env) (eval (cadr e) env)))))
(define (apply f x)
(eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))
(display (eval (read) '()))
(newline)
A cleaner version using Racket’s match construct improves readability while preserving the same logic.
A bigger language
The same eval/apply architecture scales to a 100-line interpreter in Racket that supports:
- Numeric and boolean literals
- Primitive operations (
+,-,<=, etc.) - Conditionals, sequencing, and variable mutation via
set! - Local bindings with
letand recursive bindings withletrec - Top-level definitions using
define
This extended interpreter includes a test harness and transforms top-level define forms into a single letrec expression for uniform evaluation. It uses hash tables with mutable cells to model environments, allowing mutation and recursion.
When to use it
This approach is ideal for learning language design, experimenting with semantics, or prototyping new language features. By separating syntax (via external parsing to s-expressions) from semantics, developers can explore alternative grammars without rewriting the core interpreter. The minimal foundation makes it suitable for educational use or embedding domain-specific languages.
Bottom line: Implementing a programming language doesn’t require complex tooling. With just a few lines of code, developers can build and extend functional languages grounded in formal computation theory.