In this project, we will develop an interpreter for a subset of the Scheme language. As we proceed, we think about the issues that arise in the design of a programming language; many quirks of languages are byproducts of implementation decisions in interpreters and compilers.
We will also implement some small programs in Scheme. Scheme is a simple but powerful functional language. Since we only include a subset of the language, our interpreter will not exactly match the behaviour of other interpreters such as STk.
To test scheme reader:
$ python3 scheme_reader.py
Every time you type in a value into the prompt, both the str and repr values of the parsed expression are printed. e.g.:
read> 42
str : 42
repr: 42
read> '(1 2 3)
str : (quote (1 2 3))
repr: Pair('quote', Pair(Pair(1, Pair(2, Pair(3, nil))), nil))
read> nil
str : ()
repr: nil
read> '()
str : (quote ())
repr: Pair('quote', Pair(nil, nil))
read> (1 (2 3) (4 (5)))
str : (1 (2 3) (4 (5)))
repr: Pair(1, Pair(Pair(2, Pair(3, nil)), Pair(Pair(4, Pair(Pair(5, nil), nil)), nil)))
read> (1 (9 8) . 7)
str : (1 (9 8) . 7)
repr: Pair(1, Pair(Pair(9, Pair(8, nil)), 7))
read> (hi there . (cs . (student)))
str : (hi there cs student)
repr: Pair('hi', Pair('there', Pair('cs', Pair('student', nil))))
scm> +
#[+]
scm> odd?
#[odd?]
scm> display
#[display]
scm> (+ 1 2)
3
scm> (* 3 4 (- 5 2) 1)
36
scm> (odd? 31)
True
scm> (define x 15)
x
scm> (define y (* 2 x))
y
scm> y
30
scm> (+ y (* y 2) 1)
91
scm> (define x 20)
x
scm> x
20
scm> (eval (define tau 6.28))
6.28
It can also evaluate quoted expressions:
scm> 'hello
hello
scm> '(1 . 2)
(1 . 2)
scm> '(1 (2 three . (4 . 5)))
(1 (2 three 4 . 5))
scm> (car '(a b))
a
scm> (eval (cons 'car '('(1 2))))
1
A begin expression is evaluated by evaluating all sub-expressions in order. The value of the begin expression is the value of the final sub-expression:
scm> (begin (+ 2 3) (+ 5 6))
11
scm> (define x (begin (display 3) (newline) (+ 2 3)))
3
x
scm> (+ x 3)
8
scm> (begin (print 3) '(+ 2 3))
3
(+ 2 3)
Lambda expressions:
scm> (lambda (x y) (+ x y))
(lambda (x y) (+ x y))
User-defined procedures:
scm> (define f (lambda (x) (* x 2)))
f
However, we'd like to be able to use the shorthand form of defining named procedures:
scm> (define (f x) (* x 2))
f
This function should evaluate either the second (consequent) or third (alternative) expression of the if
expression, depending on whether the value of the first (predicate) expression is true.
scm> (if (= 4 2) 'a 'b)
b
scm> (if (= 4 4) (* 1 2) (+ 3 4))
2
It is legal to pass in just two expressions to the if
special form. In this case, you should return the second expression if the first expression evaluates to a true value. Otherwise, return the special okay
value, which represents an undefined value.
scm> (if (= 4 2) 'a)
okay
The logical forms and
and or
are short-circuiting. For and
, the interpreter should evaluate each sub-expression from left to right, and if any of these evaluates to a false value, then False
is returned. Otherwise, it should return the value of the last sub-expression. If there are no sub-expressions in an and
expression, it evaluates to True
.
scm> (and)
True
scm> (and 4 5 6) ; all operands are true values
6
scm> (and 4 5 (+ 3 3))
6
scm> (and True False 42 (/ 1 0)) ; short-circuiting behavior of and
False
For or
, evaluate each sub-expression from left to right. If any sub-expression evaluates to a true value, return that value. Otherwise, return False
. If there are no sub-expressions in an or
expression, it evaluates to False
.
scm> (or)
False
scm> (or 5 2 1) ; 5 is a true value
5
scm> (or False (- 1 1) 1) ; 0 is a true value in Scheme
0
scm> (or 4 True (/ 1 0)) ; short-circuiting behavior of or
4
cond
form returns the value of the first result sub-expression corresponding to a true predicate, or the sub-expression corresponding to else
.
scm> (cond ((= 4 3) 'nope)
((= 4 4) 'hi)
(else 'wait))
hi
scm> (cond ((= 4 3) 'wat)
((= 4 4))
(else 'hm))
True
scm> (cond ((= 4 4) 'here (+ 40 2))
(else 'wat 0))
42
The value of a cond
is undefined if there are no true predicates and no else
. In such a case, do_cond_form
should return okay
.
scm> (cond (False 1) (False 2))
okay
The let
special form binds symbols to values locally, giving them their initial values. For example:
scm> (define x 'hi)
x
scm> (define y 'bye)
y
scm> (let ((x 42)
(y (* 5 10)))
(list x y))
(42 50)
scm> (list x y)
(hi bye)
do_mu_form
is a non-standard Scheme expression type. A mu
expression is similar to a lambda
expression, but evaluates to a MuProcedure
instance that is dynamically scoped:
scm> (define f (mu (x) (+ x y)))
f
scm> (define g (lambda (x y) (f (+ x x))))
g
scm> (g 3 7)
13
The enumerate
procedure takes in a list of values and returns a list of two-element lists, where the first element is the index of the value, and the second element is the value itself.
scm> (enumerate '(3 4 5 6))
((0 3) (1 4) (2 5) (3 6))
scm> (enumerate '())
()
The list-change
procedure lists all of the ways to make change for a positive integer total
amount of money, using a list of currency denominations, which is sorted in descending order. The resulting list of ways of making change should also be returned in descending order.
To make change for 10 with the denominations (25, 10, 5, 1), we get the possibliites:
10
5, 5
5, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1
To make change for 5 with the denominations (4, 3, 2, 1), we get the possibilities:
4, 1
3, 2
3, 1, 1
2, 2, 1
2, 1, 1, 1
1, 1, 1, 1, 1
Scheme Data Type | Our Internal Representation |
---|---|
Numbers | Python's built-in int and float data types. |
Symbols | Python's built-in string data type. |
Booleans (#t , #f ) |
Python's built-in True , False values. |
Pairs | The Pair class, defined in scheme_reader.py . |
nil |
The nil object, defined in scheme_reader.py . |
Files in this project:
scheme.py
: the Scheme evaluatorscheme_reader.py
: the Scheme syntactic analyserquestions.scm
: a collection of functions (User-defined procedures) written in Schemetests.scm
: a collection of test cases written in Schemescheme_tokens.py
: a tokenizer for Schemescheme_primitives.py
primitive Scheme proceduresbuffer.py
: a buffer implementationucb.py
: utility functions for 61A
To run your Scheme interpreter in an interactive session, type:
$ python3 scheme.py
You can use your Scheme interpreter to evaluate the expressions in an input file by passing the file name as a command-line argument to scheme.py
:
$ python3 scheme.py tests.scm
To exit the Scheme interpreter, press Ctrl-d
or evaluate the exit
procedure:
scm> (exit)
To test scheme reader, yvery time you type in a value into the prompt, both the str and repr values of the parsed expression are printed:
$ python3 scheme_reader.py