Eval calls apply,
which just calls eval again!
When does it all end?
In this project, you will develop an interpreter for a subset of the Scheme language. As you proceed, 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. The subset of the language used in this project is described in the functional programming section of Composing Programs.
You will also implement some small programs in Scheme. Scheme is a simple but powerful functional language. You should find that much of what you have learned about Python transfers cleanly to Scheme as well as to other programming languages. To learn more about Scheme, you can read Structure and Interpretation of Computer Programs online for free. Examples from Chapters 1 and 2 are included as test cases for this project. Language features from Chapters 3, 4, and 5 are not part of this project, but of course you are welcome to extend your interpreter to implement more of the language. Since we only include a subset of the language, your interpreter will not exactly match the behavior of other interpreters such as STk.
The project concludes with an open-ended graphics contest that challenges you to produce recursive images in only a few lines of Scheme. As an example, the picture above abstractly depicts all the ways of making change for $0.50 using U.S. currency. All flowers appear at the end of a branch with length 50. Small angles in a branch indicate an additional coin, while large angles indicate a new currency denomination. In the contest, you too will have the chance to unleash your inner recursive artist.
This project includes several files, but all of your changes will be made to
the first four: scheme.py
, scheme_reader.py
, questions.scm
, and
tests.scm
. You can download all of the project code as a zip
archive, which contains the following files:
scheme.py |
The Scheme evaluator |
scheme_reader.py |
The Scheme syntactic analyzer |
questions.scm |
A collection of functions written in Scheme |
tests.scm |
A collection of test cases written in Scheme |
scheme_tokens.py |
A tokenizer for Scheme |
scheme_primitives.py |
Primitive Scheme procedures |
scheme_test.py |
A testing framework for Scheme |
buffer.py |
A buffer implementation |
ucb.py |
Utility functions for 61A |
ok |
Autograder software |
tests |
A directory of tests used by ok |
You'll work in a team of two people, Partner A and Partner B. In each part, you will do some of the work separately and some together with your partner. For example, if a problem is marked 5A, then it is a solo problem for Partner A. Both partners should read, think about, and understand the solution to all questions. Feel free to help each other on the solo questions. If you choose to work on the whole project alone, you must complete all questions yourself.
In Parts I and II, you will develop the interpreter in these stages:
In Part III, you will implement Scheme procedures.
There are 27 possible correctness points and 3 composition points. The composition score in this project will evaluate the clarity of your code and your ability to write tests that verify the behavior of your interpreter.
Submit the project by running python3 ok --submit
. Only partner A should
submit with this command.
In addition to submitting the project via this command, create a group on the ok website. A video walkthrough of this process is available here.
We also ask that you submit your final version through the homework submission
system by copying scheme.py
, scheme_reader.py
, tests.scm
, and
questions.scm
to your class account and running submit proj4
. This
secondary submission will be used to resolve any issues with the ok
system.
Read-Eval-Print. The interpreter reads Scheme expressions, evaluates them, and displays the results.
scm> 2
2
scm> (((lambda (f) (lambda (x) (f f x)))
(lambda (f k) (if (zero? k) 1 (* k (f f (- k 1)))))) 5)
120
The starter code for your Scheme interpreter in scheme.py
can successfully
evaluate the first expression above, since it consists of a single number. The
second (a computation of 5 factorial) will not work just yet.
Load. Our load
procedure differs from standard Scheme in that we use a
symbol for the file name. For example, to load tests.scm
, evaluate the
following call expression.
scm> (load 'tests)
Symbols. Unlike some implementations of Scheme, in this project numbers and boolean values cannot be used as symbols. Also, symbols are always lowercased. This is illustrated in the following example, which won't work until a little bit later:
scm> (define 2 3)
Traceback (most recent call last):
0 (#define 2 3)
Error: bad argument to define
scm> 'Hello
hello
Turtle Graphics. In addition to standard Scheme procedures, we include
procedure calls to the Python turtle
package. This will come in handy in Part
IV, for the contest.
You can read the turtle module documentation online.
Note: Theturtle
Python module may not be installed by default on your
personal computer. However, the turtle
module is installed on the
instructional machines. So, if you wish to create turtle graphics for this
project (i.e. for the contest), then you'll either need to setup turtle
on
your personal computer or use university computers.
Testing. The tests.scm
file contains a long list of example Scheme
expressions and their expected values.
(+ 1 2)
; expect 3
(/ 1 0)
; expect Error
You can compare the output of your interpreter to the expected output by running:
python3 scheme_test.py
For the example above, scheme_test.py
will evaluate (+ 1 2)
using your code
in scheme.py
, then output a test failure if 3
is not returned as the value.
The second example tests for an error (but not the specific error message.
Only a small subset of tests are designated to run by default because
tests.scm
contains an (exit)
call near the beginning, which halts testing.
As you complete more of the project, you should move or remove this call.
Note: your interpreter doesn't know how to exit
until Problems 3 and 4 are
completed; all tests will run until then.
Important: As you proceed in the project, add new tests to the top of
tests.scm
to verify the behavior of your implementation. Your composition
score for this project will depend on whether or not you have tested your
implementation in ways that are different from the ok
tests.
As always, you can run the doctests for the project:
python3 -m doctest scheme.py scheme_reader.py
We've included an autograder which includes tests for each question. You will have to unlock some of the tests first before you can use them to test your implementations. To unlock tests for question 1, run the following command from your terminal:
python3 ok -u -q 1
Once you have unlocked the tests, you can run the tests for question 1 as follows:
python3 ok -q 1
You can also invoke the autograder for all problems at once using:
python3 ok
The tests
directory is used to store autograder tests, so make sure not to
modify it. You may lose all your unlocking progress if you do. If you need to
get a fresh copy, you can download the zip archive and copy it
over, but you will need to start unlocking from scratch.
If you have any problems logging in or communicating with the server, use the
--local
flag to inhibit any server communication.
Note that the tests we provide you through the autograder are not
comprehensive. To ensure that your interpreter is correct and bug-free, you
will have to add your own tests to tests.scm
, and ensure that they cover as
many cases as possible.
Debugging. If you're stuck, try using the trace
decorator from the ucb
module to follow the path of execution in your interpreter.
You can also use ok
to help with debugging, by adding the -i
flag to start
an interactive session:
python3 ok -q 1 -i
If you get stuck, try this guide to debugging.
Exceptions. As you develop your Scheme interpreter, you may find that Python
raises various uncaught exceptions when evaluating Scheme expressions. As a
result, your Scheme interpreter will halt. Some of these may be the results of
bugs in your program, and some may be useful indications of errors in user
programs. The former should be fixed (of course!) and the latter should be
handled, usually by raising a SchemeError
. All SchemeError
exceptions are
handled and printed as error messages by the read_eval_print_loop
function in
scheme.py
. Ideally, there should never be unhandled Python exceptions for any
input to your interpreter.
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
Currently, your Scheme interpreter can handle a few simple expressions, such as:
scm> 1
1
scm> 42
42
scm> #t
True
To exit the Scheme interpreter, press either Ctrl-c
or Ctrl-d
or evaluate
the exit
procedure (after completing questions 3 and 4):
scm> (exit)
The function scheme_read
in scheme_reader.py
parses a Buffer
(see
buffer.py
) instance that returns valid Scheme tokens when its current
and
pop
methods are invoked. It returns the next full Scheme expression in the
src
buffer, using this representation:
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 . |
Complete the scheme_read
function in scheme_reader.py
by adding support for
quotation. This function selects behavior based on the type of the next token:
src
is the string "nil"
, return the nil
object.
(provided)'bagel
), then return a quote special form (such as (quote bagel)
)."("
, return the result of
read_tail
. (provided)Test your understanding and implementation before moving on:
python3 ok -q 1 -u
python3 ok -q 1 -i
Complete the read_tail
function in scheme_reader.py
by adding support for
dotted lists. A dotted list in Scheme is not necessarily a well-formed list, but
instead has an arbitrary second
attribute that may be any Scheme value.
The read_tail
function expects to read the rest of a list or dotted list,
assuming the open parenthesis of that list has already been popped by
scheme_read
.
Consider the case of calling scheme_read
on input "(1 2 . 3)
". The
read_tail
function will be called on the suffix "1 2 . 3)
", which is
1
and the value of the tail "2 .
3)
", which is2
and the Scheme value 3
.Thus, read_tail
would return Pair(1, Pair(2, 3))
.
Hint: In order to verify that only one element follows a dot, after
encountering a '.'
, read one additional expression and then
check to see that a closing parenthesis follows.
Test your understanding and implementation before moving on:
python3 ok -q 2 -u
python3 ok -q 2 -i
You should also run the doctests for scheme_reader.py
and test your parser
interactively by running 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.
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))))
All further changes to the interpreter will be made in scheme.py
. For each
question, add a few tests to the top of tests.scm
to verify the behavior of
your implementation.
In the implementation given to you, the scheme_eval
function is complete, but
most of the functions or methods it uses are not implemented. In fact, the
evaluator can only evaluate self-evaluating expressions: numbers, booleans, and
nil
.
Implement apply_primitive
, which is called by scheme_apply
. Primitive
procedures are applied by calling a corresponding Python function that
implements the procedure.
Scheme primitive procedures are represented as instances of the
PrimitiveProcedure
class, defined in scheme_primitives.py
. A
PrimitiveProcedure
has two instance attributes:
fn
is the Python function that implements the primitive Scheme
procedure.use_env
is a boolean flag that indicates whether or not this primitive
procedure will expect the current environment to be passed in as the last
argument. The environment is required, for instance, to implement the primitive
eval
procedure.To see a list of all Scheme primitive procedures used in the project, look in
the scheme_primitives.py
file. Any function decorated with @primitive
will
be added to the globally-defined _PRIMITIVES
list.
The apply_primitive
function takes a PrimitiveProcedure
instance, a Scheme
list of argument values, and the current environment. Your implementation
should:
procedure.use_env
is True
, then add the current environment env
as the last argument.procedure.fn
on those arguments (Hint: use * notation).TypeError
exception being thrown, then
raise a SchemeError
instead.Test your understanding and implementation before moving on:
python3 ok -q 3 -u
python3 ok -q 3 -i
The doctest for apply_primitive
should now pass. However, your Scheme
interpreter will still not be able to apply primitive procedures, because your
Scheme interpreter still doesn't know how to look up the values for built-in
symbols (such as +
, *
, and car
). Let's fix that.
Implement the lookup
method of the Frame
class. It takes a symbol (Python
string) and returns the value bound to that name in the first Frame
of the
environment in which that name is found. A Frame
represents an environment
via two instance attributes:
bindings
is a dictionary that maps Scheme symbol keys (represented as
Python strings) to Scheme values.parent
is the parent Frame
instance. The parent of the Global Frame is
None
.Your lookup
implementation should:
self.bindings
if it exists.lookup
that symbol in the parent
if the parent
exists.SchemeError
. (provided)After you complete this problem, you should be able to evaluate primitive procedure calls, giving you the functionality of the Calculator language and more.
scm> +
#[primitive]
scm> (+ 1 2)
3
scm> (* 3 4 (- 5 2) 1)
36
scm> (odd? 31)
True
Test your understanding and implementation before moving on:
python3 ok -q 4 -u
python3 ok -q 4 -i
There are two missing parts in the do_define_form
function, which handles the
(defineĀ ...)
special forms. Implement just the first part, which binds
names to values but does not create new procedures. do_define_form
should
return the name after performing the binding.
scm> (define tau (* 2 3.1415926))
tau
Test your understanding and implementation before moving on:
python3 ok -q 5 -u
python3 ok -q 5 -i
You should now be able to give names to values and evaluate symbols to those values.
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
Implement the do_quote_form
function, which evaluates the quote
special
form.
Test your understanding and implementation before moving on:
python3 ok -q 6 -u
python3 ok -q 6 -i
You should now be able to 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
At this point in the project, your Scheme interpreter should be be able to support the following features:
quote
special form,(+ (- 4 2) 5)
.User-defined procedures are represented as instances of the LambdaProcedure
class, defined in scheme.py
. A LambdaProcedure
instance has three instance
attributes:
formals
is a Scheme list of the formal parameters (symbols) that name the
arguments of the procedure.body
is a single Scheme expression; the body of the procedure.env
is the environment in which the procedure was defined.First, implement the begin
special form, which includes a list of one or more
sub-expressions that are each evaluated 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)
Hint: When scheme_eval
evaluates one of the LOGICAL_FORMS
in
scheme.py
, it calls scheme_eval
on the returned value. Take care that
your Scheme interpreter doesn't inadvertently call scheme_eval
on the same
value twice, or else you might have the following incorrect behavior:
scm> (begin 30 'hello)
Error: unknown identifier: hello
Test your understanding and implementation before moving on:
python3 ok -q 7 -u
python3 ok -q 7 -i
Implement the do_lambda_form
method, which creates LambdaProcedure
instances
by evaluating lambda
expressions. While you cannot call a user-defined
procedure yet, you can verify that you have read the procedure correctly by
evaluating a lambda expression:
scm> (lambda (x y) (+ x y))
(lambda (x y) (+ x y))
In Scheme, it is legal to have function bodies with more than one expression.
In order to implement this feature, your do_lambda_form
should detect when
the body of a lambda expression contains multiple expressions. If so, then
do_lambda_form
should place those expressions inside of a (begin ...)
form,
and use that begin
expression as the body:
scm> (lambda (y) (print y) (* y 2))
(lambda (y) (begin (print y) (* y 2)))
Test your understanding and implementation before moving on:
python3 ok -q 8 -u
python3 ok -q 8 -i
Currently, your Scheme interpreter is able to define user-defined procedures in the following manner:
scm> (define f (lambda (x) (* x 2)))
f
However, we'd like to be able to use the shorthand form of defining procedures:
scm> (define (f x) (* x 2))
f
Modify the do_define_form
function so that it correctly handles the shorthand
procedure definition form above. Make sure that it can handle multi-expression
bodies.
Test your understanding and implementation before moving on:
python3 ok -q 9 -u
python3 ok -q 9 -i
You should now find that defined procedures evaluate to lambda procedures.
scm> (define (square x) (* x x))
square
scm> square
(lambda (x) (* x x))
Implement the make_call_frame
method of the Frame
class, which:
Frame
instance, the parent of which is self
. (provided)Test your understanding and implementation before moving on:
python3 ok -q 10 -u
python3 ok -q 10 -i
Implement the check_formals
function to raise an error whenever the Scheme
list of formal parameters passed to it is invalid. Raise a SchemeError
if
the list of formals
is not a well-formed list of symbols or if any symbol is
repeated.
Hint: The scheme_symbolp
function in scheme_primitives.py
returns whether
a value is a Scheme symbol.
Test your understanding and implementation before moving on:
python3 ok -q 11 -u
python3 ok -q 11 -i
Implement scheme_apply
to correctly apply user-defined LambdaProcedure
instances. (The case for MuProcedure
is handled later in the project). It
should:
Frame
, with all formal parameters bound to their argument
values and the correct parent Frame
,body
of procedure
in the environment represented by this new
frame, andprocedure
.Test your understanding and implementation before moving on:
python3 ok -q 12 -u
python3 ok -q 12 -i
After you complete scheme_apply
, user-defined functions (and lambda
functions) should work in your Scheme interpreter. Now is an excellent time to
revisit the tests in tests.scm
and ensure that you pass the ones that involve
definition (Sections 1.1.2 and 1.1.4). You should also add additional tests
of your own at the top of tests.scm
to verify that your interpreter is
behaving as you expect.
Logical special forms include if
, and
, or
, and cond
. These expressions
are special because not all of their sub-expressions may be evaluated.
In Scheme, only #f
is a false value. All other values are true values. You
can test whether a value is a true value or a false value using the provided
Python functions scheme_true
and scheme_false
, defined in
scheme_primitives.py
. Note that, in our interpreter, like in STk, false
and
False
can be used in place of #f
. Similarly, true
and True
can be used
in place of #t
.
Implement do_if_form
so that if
expressions are evaluated correctly. This
function should return either the second (consequent) or third (alternative)
expression of the if
expression, depending on the value of the first
(predicate) expression.
scm> (if (= 4 2) #t #f)
False
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) #t)
okay
Test your understanding and implementation before moving on:
python3 ok -q 13 -u
python3 ok -q 13 -i
Implement do_and_form
and do_or_form
so that and
and or
expressions are
evaluated correctly.
The logical forms and
and or
are short-circuiting. For and
, your
interpreter should evaluate each sub-expression from left to right, and if any
of these evaluates to a false value, then False
is returned. If all but the
last sub-expressions evaluate to true values, return the last sub-expression
from do_and_form
.
For or
, evaluate each sub-expression from left to right. If any evaluates to
a true value, then quote
that value and return it. The return value must
be quoted because it will be evaluated as an expression in scheme_eval
. If
all but the last sub-expression evaluate to a false value, return the last
sub-expression from do_or_form
without quoting it.
scm> (and)
True
scm> (or)
False
scm> (and 4 5 6) ; all operands are true values
6
scm> (or 5 2 1) ; 5 is a true value
5
scm> (and #t #f 42 (/ 1 0)) ; short-circuiting behavior of and
False
scm> (or 4 #t (/ 1 0)) ; short-circuiting behavior of or
4
Test your understanding and implementation before moving on:
python3 ok -q 14 -u
python3 ok -q 14 -i
Implement do_cond_form
so that it returns the first result sub-expression
corresponding to a true predicate, or the sub-expression corresponding to
else
. Your implementation should match the following examples and the
additional tests in tests.scm
.
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 42)
(else 'wat 0))
42
For the last example, where the body of a cond
case has multiple expressions,
you might find it helpful to replace cond
-bodies with multiple expression
bodies into a single begin
expression, i.e., the following two expressions are
equivalent.
(cond ((= 4 4) 'here 42))
(cond ((= 4 4) (begin 'here 42)))
If the body of a cond
case is empty, then do_cond_form
should quote the
value of the predicate and return it, if the predicate evaluates to a true
value.
scm> (cond (12))
12
scm> (cond ((= 4 3))
('hi))
hi
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
.
Test your understanding and implementation before moving on:
python3 ok -q 15 -u
python3 ok -q 15 -i
The let
special form introduces local variables, 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)
Implement the do_let_form
method to have this effect and test it, by adding
test cases to the top of tests.scm
. Make sure your let
correctly handles
multi-expression bodies:
scm> (let ((x 42)) x 1 2)
2
A let
form creates a new Frame
(containing the let
bindings) which
extends the current environment and evaluates the body of the let
in this
new environment.
Test your understanding and implementation before moving on:
python3 ok -q 16 -u
python3 ok -q 16 -i
Implement do_mu_form
to evaluate the mu
special form, 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. The
MuProcedure
class has been provided for you.
Additionally, complete scheme_apply
to call MuProcedure
procedures using
dynamic scoping. Calling a LambdaProcedure
uses lexical scoping: the parent
of the new call frame is the environment in which the procedure was defined.
Calling a MuProcedure
created by a mu
expression uses dynamic scoping: the
parent of the new call frame is the environment in which the call expression was
evaluated. As a result, a MuProcedure
does not need to store an
environment as an instance attribute. It can refer to names in the environment
from which it was called.
scm> (define f (mu (x) (+ x y)))
f
scm> (define g (lambda (x y) (f (+ x x))))
g
scm> (g 3 7)
13
To test yourself, figure out what the expression (g 3 7)
would evaluate to if
the function f
were instead a lambda function.
Test your understanding and implementation before moving on:
python3 ok -q 17 -u
python3 ok -q 17 -i
Your Scheme interpreter implementation is now complete. You should have been
adding tests to the top of tests.scm
as you did each problem. These tests
will be evaluated as part of your composition score for the project.
Not only is your Scheme interpreter itself a tree-recursive program, but it is
flexible enough to evaluate other recursive programs. Implement the following
procedures in Scheme in the questions.scm
file.
Implement the zip
procedure, which takes in a list of pairs and converts it
into a pair of lists, where the first list contains all of the first elements
of the original pairs, and the second list contains all of the second elements.
The "pairs" in the input are well-formed two-element lists, not Scheme pairs.
scm> (zip '((1 2)))
((1) (2))
scm> (zip '((1 2) (3 4) (5 6)))
((1 3 5) (2 4 6))
Test your understanding and implementation before moving on:
python3 ok -q 18 -u
python3 ok -q 18 -i
Implement the list-partitions
procedure, which lists all of the ways to
partition a positive integer total
into at most max-pieces
pieces, where
all of the pieces are less than or equal to a positive integer max-value
.
Hint: Define a helper procedure to construct partitions.
The number 5 has 4 partitions using pieces up to a max-value
of 3 and a
max-pieces
of 4:
3, 2 (two pieces)
3, 1, 1 (three pieces)
2, 2, 1 (three pieces)
2, 1, 1, 1 (four pieces)
Test your understanding and implementation before moving on:
python3 ok -q 19 -u
python3 ok -q 19 -i
In Scheme, source code is data. Every non-primitive expression is a list, and we can write procedures that manipulate other programs just as we write procedures that manipulate lists.
Re-writing programs can be useful: we can write an interpreter that only
handles a small core of the language, and then write a procedure analyze
that
converts other special forms into the core language before a program is passed
to the interpreter.
For example, the let
special form is equivalent to a call expression that
begins with a lambda
expression. Both create a new frame extending the
current environment and evaluate a body within that new environment.
(let ((x 42) (y 16)) (+ x y))
;; Is equivalent to:
((lambda (x y) (+ x y)) 42 16)
We can use this rule to rewrite all let
special forms into lambda
expressions. We prevent evaluation of a program by quoting it, and then pass it
to analyze
:
scm> (analyze '(let ((a 1) (b 2)) (+ a b)))
((lambda (a b) (+ a b)) 1 2)
scm> (analyze '(let ((a 1)) (let ((b a)) b)))
((lambda (a) ((lambda (b) b) a)) 1)
In order to handle all programs, analyze
must be aware of Scheme syntax.
Since Scheme expressions are recursively nested, analyze
must also be
recursive. In fact, the structure of analyze
looks like that of
scheme_eval
:
(define (analyze expr)
(cond ((atom? expr) <Analyze atom>)
((quoted? expr) <Analyze quoted>)
((lambda? expr) <Analyze lambda>)
((define? expr) <Analyze define>)
((let? expr) <Analyze let>)
(else <Analyze other>)))
Implement the analyze
procedure, which takes in an expression and converts
all of the let
special forms in the expression into their equivalent lambda
expressions.
Hint: You may want to use the provided apply-to-all
procedure and the 'zip'
procedure from Q18.
Test your understanding and implementation before moving on:
python3 ok -q 20 -u
python3 ok -q 20 -i
Note: We used let
while defining analyze
. What if we want to run
analyze
on an interpreter that does not recognize let
? We can pass
analyze
to itself to compile itself into an equivalent program that does
not use let
:
;; The analyze procedure
(define (analyze expr)
...)
;; A list representing the analyze procedure
(define analyze-code
'(define (analyze expr)
...))
;; An analyze procedure that does not use 'let'
(define analyze-without-let
(analyze analyze-code))
Implement the hax
procedure that draws the following recursive illustration
when passed two arguments, a side length d
and recursive depth k
. The
example below is drawn from (hax 200 4)
.
To see how this illustration is constructed, consider this annotated version that gives the relative lengths of lines of the component shapes in the figure.
Complete the function scheme_optimized_eval
in scheme.py
. This alternative
to scheme_eval
is properly tail recursive. That is, the interpreter will
allow an unbounded number of active tail
calls in constant space.
Instead of recursively calling scheme_eval
for tail calls, logical special
forms, and let
, replace the current expr
and env
with different
expressions and environments. For call expressions, this change only applies to
calling user-defined procedures.
Once you finish, uncomment the following line in scheme.py
:
scheme_eval = scheme_optimized_eval
Test your understanding and implementation before moving on:
python3 ok -q 22 -u
python3 ok -q 22 -i
Congratulations! You have finished the final project for 61A! Assuming your tests are good and you've passed them all, consider yourself a proper computer scientist!
Now, get some sleep. You've earned it!
We've added a number of primitive drawing procedures that are collectively
called "turtle graphics". The turtle represents the state of the drawing
module, which has a position, an orientation, a pen state (up or down), and a
pen color. The tscheme__x_
functions in scheme_primitives.py
are the
implementations of these procedures, and show their parameters with a brief
description of each.
The Python documentation of the turtle module contains more detail.
Contest: Create a visualization of an iterative or recursive process of your
choosing, using turtle graphics. Your implementation must be written entirely in
Scheme using the interpreter you have built. However, you may add primitive
procedures to interface with Python's turtle
or math
modules. Other than
that all computation must be done in Scheme. If you do add new primitives,
then make sure to submit scheme_primitives.py
in addition to contest.scm
.
Prizes, as well as 3 extra credit points, will be awarded for the winning entry in each of the following categories.
Entries (code and results) will be posted online, and winners will be selected by popular vote as part of a future homework. The voting instructions will read:
Please vote for your favorite entry in this semester's 61A Recursion Exposition contest. The winner should exemplify the principles of elegance, beauty, and abstraction that are prized in the Berkeley computer science curriculum. As an academic community, we should strive to recognize and reward merit and achievement (translation: please don't just vote for your friends).
To improve your chance of success, you are welcome to include a title and descriptive haiku in the comments of your entry, which will be included in the voting.
Entries that do not construct an image iteratively or recursively may be disqualified. This includes just drawing a preexisting image, even if the drawing function is iterative or recursive.
Submission instructions are posted.
We have implemented a significant subset of Scheme in this project, but our interpreter can be extended with more features by following the extension instructions.