Zachary W. Huang

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.

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