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!
Many Scheme implementations allow 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
Recall that a dot is used to specifiy the second component of a pair. Thus, formal 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
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, as you did
for normal quoting. Use the
In addition, the following changes are required:
"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.
scheme_appendto actually do the splicing.
Macros allow the language itself to be extended by the user. Simple macros
can be provided with the
define-macro special form. This must be
used like a function definition, and it creates a procedure just
define. However, this procedure has a special evaluation
rule: it is applied to its arguments without first evaluating them. Then the
result of this application is evaluated.
Here is a simple example:
scm> (define-macro (when test . branch) (list 'if test (cons 'begin branch))) when scm> (when (< 3 4) (print 1) (print 2)) 1 2 okay
The code above defines a macro
when that evaluates all the
expressions in its body when the predicate expression is true. (You'll need to
have implemented variable argument lists for this particular example to
In order to implement
define-macro, introduce a new
represent them. Add another
do_*_form function to
handle macro definitions. To avoid duplicating code, you can add an
optional parameter to
do_define_form that indicates
that a macro is being defined, with a default value
False. If this parameter is true, raise an error if
function definition shorthand is not used, and create a
Finally, you'll have to work out how to define your new
so that (1) it doesn't evaluate its arguments and (2) the result that it
computes is treated as a program and evaluated in the environment of the
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
If you are really ambitious, you might try getting
to work when the target variable is a call-by-name parameter. This should
only be allowed when the actual parameter is a simple variable.
This takes a bit of doing (one reason that call-by-name didn't catch on
in other programming languages after Algol).
First, the interpreter will have to look at the prior value of the target
variable before assigning to it, which is not otherwise necessary.
You'll have to enhance your
Macro class so that it supports an assignment operation
when the actual parameter is a variable. It's all quite a bit of work,
so you might instead simply choose to have assignment to a by-name
parameter convert that parameter to an ordinary value, or to cause an error.
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:
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
scheme_apply. Instead, keep track of the last known
procedure call in
scheme_eval, and add an entry for
that to your Scheme trace when the frame corresponds
do_*_formfunction, then add an entry to your Scheme trace with the name of the form and its original arguments.
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?