Zero to Fibonacci: A Scheme interpreter crash course
Zero to Fibonacci: A Scheme interpreter crash course in five parts
Here’s a bit of exercise for your programming muscles!
Goal: Fibonacci
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)
Approach: Focus on the evaluator
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.
Why Scheme?
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.
Structure: Five incremental test-driven steps
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.
Step 1: Literals
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.618
Step 2: Function calls
This 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)
Step 3: Branching
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)
Step 4: User-defined functions
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 function
Step 5: Assignment
This 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)
The JSON syntax tree format
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>
}
Numeric literals
-1.618
{
"type": "number",
"value": -1.618
}
Symbols
+
{
"type": "symbol",
"value": "+"
}
Lists
(+ 1 2)
{
"type": "list",
"value": [
{
"type": "symbol",
"value": "+"
},
{
"type": "number",
"value": 1
},
{
"type": "number",
"value": 2
}
]
}
A complete program
(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"
}
]
}
]
The parser
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
The tests
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.
$ ./test.sh
? test10
✅
? test11
✅
? test12
✅
If your evaluator produces incorrect output, a diff will be displayed: