Zachary W. Huang

Home Projects Blog Guides Resume

A Scheme Interpreter in OCaml

All of the code can be found here: zack466/OScheML.


Scheme is a functional programming langauge in the family of langauges known as Lisp. Lisps are most notable for their many parentheses - everything in Lisp is an S-expression (sexpr for short), or a parenthesized list. Applying a function f is as simple as (f arg1 arg2 arg3).

Scheme is a more minimal Lisp (compared to Common Lisp or Clojure), but it is still powerful. My implementation took inspiration from the R5RS specification of Scheme.


I used OCaml, a multi-paradigm langauge from the ML family, to implement Scheme.

OCaml’s algebraic data types (variants and records) are very well-suited to modeling abstract syntax trees (AST), which makes it very easy to specify programming languages.

In addition, OCaml has a strict compiler that ensures I don’t forget about a case when pattern matching or apply a function to an incorrect type.

Scheme + OCaml = OScheML

I implemented most of the important parts of Scheme:

  • List operations/predicates: cons, car, cdr, list?, pair?
  • Arithmetic and logic: +, -, /, *, and, or, not, if
  • Equality predicates: eq?, eqv?, equal?
  • Builtins: define, lambda, apply
  • Quoting: ', quote

An example Scheme program that my interpreter can run is shown below:

; calculates square roots using newton's method

(define y 1.0) ; initial guess
(define x 100.0) ; square of target
(define dx 0.0001)

(define (abs x)
  (if (< x 0) (- x) x))

(define (sqrt x)
  (define (good-enough? y dx)
    (> dx (abs (- x (* y y)))))
  (define (improve guess)
    (* 0.5 (+ guess (/ x guess))))
  (define (rec guess)
    (if (good-enough? guess 0.0001) guess (rec (improve guess))))
  (rec 1.0))

(display (sqrt 1234))


  • Structure and Interpreation of Computer Programs
  • Revised^5 Report on the Algorithmic Language Scheme (R5RS)
  • Revised^7 Report on the Algorithmic Language Scheme (R7RS)
  • Crafting Interpreters
RSS icon github logo linkedin logo

Zachary W. Huang © 2021-2024