Here's a bit of exercise for your programming muscles!
In this series, we will implement just enough of a Scheme interpreter to define a fibonacci function and then call that function.
Specifically, this is the final test case in this course:
(define fib
(lambda (x)
(if (< x 2)
x
(+ (fib (+ x -1)) (fib (+ x -2))))))
(fib 10)A language interpreter consists of two major parts:
- Parsing the source code into a syntax tree
- Evaluating the syntax tree
While both of these parts present challenging problems to solve, parsing is a bit more tedious and less fun than implementing an evaluator.
Accordingly, we're going to skip our vegetables and jump straight to dessert by focusing on the evaluator and using a provided parser.
We'll do this by representing the syntax tree in JSON format, so that nearly any language can be used to implement the evaluator.
This course is based on Scheme for one reason: it has the least complex syntax of any language, consisting of just atoms and lists.
This will keep our JSON syntax tree representation simple and avoid unnecessarily complicating the evaluator implementation.
Each step of this course will add additional language features to the evaluator. Unit tests are included to verify and/or test-drive your work.
This step will focus on:
- Reading in the JSON syntax tree from standard input or a file
- Evaluating (numeric) literals
Your interpreter will be capable of evaluating statements like:
42
-3
1.618This step will focus on:
- Symbols
- The environment
- Built-in environment bindings
- Lists
- Built-in functions
- Function invocation
Your interpreter will be capable of evaluating statements like:
pi
(+ 1 2)
(+ 1 (+ 2 3) 4)This step will focus on:
- Booleans
- Truthiness
- Conditionals
- Branching
Your interpreter will be capable of evaluating statements like:
#t ; the true boolean literal
#f ; the false boolean literal
(< 1 2)
(if (< 1 2) 3 4)This step will focus on:
- User-defined functions
Your interpreter will be capable of evaluating statements like:
(lambda () 1) ; a function which takes no arguments and returns 1
(lambda (x) x) ; the identity function
(lambda (x) (if (< x 0) (- 0 x) x)) ; the absolute value functionThis step will focus on:
- User-defined environment bindings (a.k.a. assignment)
Your interpreter will be capable of evaluating statements like:
(define x 42)
(define y x)
(define abs (lambda (x) (if (< x 0) (- 0 x) x)))
(define fib (lambda (x) (if (< x 2) x (+ (fib (+ x -1)) (fib (+ x -2))))))
(fib 10)Your evaluator will operate on a JSON syntax tree. Here's the format:
A (Scheme) source code program is a sequence of statements, so the outermost JSON component will be an array.
Each statement in the array will be a JSON object of the form:
[
{
"type": <number, symbol, or list>
"value": <a literal or an array>
}
]-1.618
[
{
"type": "number",
"value": -1.618
}
]+
[
{
"type": "symbol",
"value": "+"
}
](+ 1 2)[
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "+"
},
{
"type": "number",
"value": 1
},
{
"type": "number",
"value": 2
}
]
}
](define x 1)
(define y 2)
(define max (lambda (a b) (if (< a b) b a)))
(max x y)[
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "define"
},
{
"type": "symbol",
"value": "x"
},
{
"type": "number",
"value": 1
}
]
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "define"
},
{
"type": "symbol",
"value": "y"
},
{
"type": "number",
"value": 2
}
]
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "define"
},
{
"type": "symbol",
"value": "max"
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "lambda"
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "a"
},
{
"type": "symbol",
"value": "b"
}
]
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "if"
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "<"
},
{
"type": "symbol",
"value": "a"
},
{
"type": "symbol",
"value": "b"
}
]
},
{
"type": "symbol",
"value": "b"
},
{
"type": "symbol",
"value": "a"
}
]
}
]
}
]
},
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "max"
},
{
"type": "symbol",
"value": "x"
},
{
"type": "symbol",
"value": "y"
}
]
}
]A rudimentary Scheme-to-JSON parsing script is included. You can use it to test your evaluator without having to write a bunch of JSON by hand:
echo '(+ 1 2)' | ./parser.py | ./evaluator
A series of tests are included to help verify your implementation.
Each test comes in the form of three files:
- The input source code (Scheme)
- The corresponding JSON syntax tree
- The expected evaluator output
Additionally, a Bash script is included which runs all of the tests.
$ ./run-tests.sh
👉 test100
✅
👉 test101
✅
👉 test102
✅
If your evaluator produces incorrect output, a diff will be displayed:
If your language doesn't support JSON natively (i.e. C), it may be easier to operate
on Scheme input rather than JSON input. Pass the --scm option to do this.
For some type systems, JSON in which the top-most structure is an array is problematic.
To wrap the top-level array in an object ({ "lines": [ ...), pass the --wrap-arrays option.
The run-tests.sh script expects an interpreter executable named evaluator.
If your evaluator is named something else, pass that as the last argument to run-tests.sh.
If you are new to Scheme, it can be helpful to have a real Scheme interpreter available
to check your implementation against. The CHICKEN interpreter csi is a convenient choice.
On macOS, brew install chicken, then run csi.