Scheme Interpreter Extensions
There are many ways to extend our Scheme interpreter. A few suggestions are below, and the Wikipedia page for Scheme is a good place to start to learn more about the language itself.
We recommend that you submit the final version of your project before attempting any of these extensions. We are not responsible if you break the required components of your interpreter and Scheme code.
Scheme allows procedures to take in a variable number
of arguments, which get placed into a list before being bound to a parameter.
(Compare to Python, where variable arguments are placed into a tuple.) This is
specified by preceding the last parameter with a dot (much like
scm> (define (add . args) (apply + args)) add scm> (add 3 7 2 1) 13
A dot is used to specifiy the second component of a pair. Thus, formals lists can now be ill-formed.
In order to implement this, you will need to change the following:
check_formalsshould not reject a formal list that is just a symbol or terminated by a symbol rather than
Frame.make_call_frameshould bind the remaining list of values to the symbol that terminates
formals, if it is not terminated by
Quasiquote and Unquote
Quoting prevents the interpreter from evaluating an expression. Often times,
we might want to evaluate part of an expression but not the rest. For example,
the following constructs a list containing the symbol
a and its
scm> (define a 3) a scm> `(a , a) (a 3)
The backquote (`) specifies a quasiquote, which
can evaluate parts of an expression. A comma (
an unquote, which specifies that the next expression should be
evaluated. Finally, a comma followed by an at symbol (
an unquote-splicing, meaning that it evaluates the next
expression, which must evaluate to a list, and then splices that list into the
scm> `(a ,@ '(1 2 3) 4) (a 1 2 3 4)
Quasiquotes can be nested, and an unquoted expression should only be evaluated if it is at the same nesting level as the outermost quasiquote. The nesting level increases by one in each quasiquotation and decreases by one in each unquote/unquote-splicing.
Here are some examples from the Scheme R5RS reference manual:
scm> `(list ,(+ 1 2) 4) (list 3 4) scm> (let ((name 'a)) `(list ,name ',name)) (list a (quote a)) scm> `(( foo ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons))) ((foo 7) . cons) scm> `(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f) (a (quasiquote (b (unquote (+ 1 2)) (unquote (foo 4 d)) e)) f) scm> (let ((name1 'x) (name2 'y)) `(a `(b ,,name1 ,',name2 d) e)) (a (quasiquote (b (unquote x) (unquote (quote y)) d)) e)
The tokenizer already handles quasiquotes and unquotes. However, you will
need to modify
scheme_read to handle them as well, like you did
for normal quoting. Use the
In addition, the following changes are required:
- Add special forms for
"quasiquote": call a new
do_quasiquote_formfunction. You may also want to check for
"unquote-splicing"here, raising an error that they are being used outside of a quasiquote.
- You will need to process a quasiquote recursively. If a value is a list that starts with either unquote at the right nesting level, then the list should contain only one more value, which should be evaluated in the current environment and returned. Otherwise the value should be returned without being evaluated.
- Splicing is a bit more complicated, since the splicing needs to be done
by the caller. You may want to add another return value to specify whether
or not splicing should be done. Use
scheme_appendto actually do the splicing.
Like Python, Scheme has non-local assignment. In particular,
set! special form takes in a name and another expression and
rebinds that name to the value of the expression in the first frame in which
the name exists. Unlike Python, this frame can be the local or global
In order to implement
set!, add a method to
that rebinds a name to a new value in the first frame in which the name is
found. An error should be raised if the name does not exist in any frame. You
will also need to add a
do_set_form function and a case for
Pairs can be mutated using
These can be easily implemented as primitive procedures
Many standard Scheme procedures can be implemented in Scheme itself, as
library code. Add a mechanism to your interpreter to load up a library file on
scheme_lib.scm). Then provide useful procedures in
scheme_lib.scm, such as
c*r variants up to four applications of
Currently, when an error occurs while attempting to evaluate an expression, the interpreter only prints out an error message, with no backtrace. This makes it difficult to determine the source of an error.
In order to provide a useful backtrace, start by adding names to primitive
procedures and procedures defined using the special
Use default names, such as
[lambda], for procedures with unknown
Now write a new function to handle an exception and call it from the first
except clause in
read_eval_print_loop. A Python exception
contains information about every frame between the one that raised the
exception and the one that handled it. If
e is an exception,
e.__traceback__ is a
traceback object that
contains this information. A
traceback is a recursive list
frames. Read more about
A Python exception contains information at the Python level, but a user is
interested in information at the Scheme level. So you should translate the
Python-level information to Scheme-level information by extracting the latter
frame. You can read the local variables in
frame, and you can obtain its associated
object to get the name of the Python function for that
Some suggestions on what to do with a Python frame:
If the frame corresponds to
scheme_apply, then add an entry to your Scheme trace for the associated procedure call. Use the name attribute that you added previously, and include the arguments.
If you did the tail recursion optimization, you will not call
scheme_apply. Instead, keep track of the last known procedure call in
scheme_optimized_eval, and add an entry for that to your Scheme trace when the frame corresponds to
- If the frame corresponds to a
do_*_formfunction, then add an entry to your Scheme trace with the name of the form and its original arguments.
- Number the entries in your trace and display them in whichever order you prefer.
Here are some sample traces without the tail recursion optimization:
scm> (define (foo x) (/ 1 x)) foo scm> (define (bar x) (foo x) 3) bar scm> (define (baz x) (if (= x 0) (bar x) (baz (- x 1)))) baz scm> (foo 0) Traceback (most recent call last): 0 (foo 0) 1 (/ 1 0) Error: division by zero scm> (bar 0) Traceback (most recent call last): 0 (bar 0) 1 (#begin (foo x) 3) 2 (foo 0) 3 (/ 1 0) Error: division by zero scm> (baz 3) Traceback (most recent call last): 0 (baz 3) 1 (baz 2) 2 (baz 1) 3 (baz 0) 4 (bar 0) 5 (#begin (foo x) 3) 6 (foo 0) 7 (/ 1 0) Error: division by zero
With the tail recursion optimization:
scm> (foo 0) Traceback (most recent call last): 0 (foo 0) 1 (/ 1 0) Error: division by zero scm> (bar 0) Traceback (most recent call last): 0 (bar 0) 1 (#begin (foo x) 3) 2 (foo 0) 3 (/ 1 0) Error: division by zero scm> (baz 3) Traceback (most recent call last): 0 (bar 0) 1 (#begin (foo x) 3) 2 (foo 0) 3 (/ 1 0) Error: division by zero
Feel free to implement any other features of Scheme that you want. You can
read the full reference manual
Examples include named
do loops, strings,
and vectors. (If you really want a challenge, then try to
call-with-current-continuation, which isn't even
handled correctly by STk.) How close can you get to what STk provides?