A Scheme Interpreter in OCaml

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

Scheme

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.

OCaml

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))

References

• 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