Eval calls apply,
which just calls eval again!
When does it all end?
do_or_form-- simply return
False, rather than possibly returning one of the operand values.
do_let_star_form, fixed the call to
check_formals: previously, it checked for at least three expressionss, when it should have been only at least two expressions.
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 the byproduct of implementation decisions in interpreters and compilers.
You will also implement some small programs in Scheme, including the
count_change function that we studied in lecture. 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 the original 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.
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 of what you might create, 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
You can download all of the project code as a zip archive.
||The Scheme interpreter|
||A Tokenizer for scheme|
||Primitive Scheme data structures and procedures|
||A testing framework for Scheme|
||A collection of test cases written in Scheme that are designed to test your Scheme interpreter. You will be adding additional test cases to this file, in addition to defining several Scheme procedures.|
||Utility functions for 61A|
This is a three-part project. As in the previous project, you'll work in a team of two people, person A and person B. In each part, you will do some of the work separately, but most questions can be completed as a pair. Both partners should understand the solutions to all questions.
After completing the first (short) part, you will be able to read and parse Scheme expressions. In the second (long) part, you will develop the interpreter in stages:
Finally, in the third part, you will implement Scheme procedures that are similar to some exercises that you previously completed in Python.
There are 30 possible points, along with 4 extra credit points. The extra credit problems are a bit involved; we recommend that you complete them all, but only after you have the regular stuff working.
The project is due on Tuesday, August 7th at 11:59:59 PM. You will must turn in both an electronic and a paper copy. Paper copies are to be turned in at the turn-in boxes in 283 Soda. On each file that you submit, make sure you indicate your TA's name, and the name and logins of both Person A and Person B.
Before you begin working on the project, review what you have learned in lecture
about the Scheme
language. If you would like to experiment with a working Scheme interpreter, look
at Stk, which is installed on
instructional machines as
stk. You can also use the online wscheme REPL.
Read-Eval-Print. Run interactively, the interpreter reads Scheme expressions,
evaluates them, and prints the results. The interpreter uses
scm> as the prompt.
scm> 2 2
The starter code for your Scheme interpreter in
scheme.py can successfully evaluate this simple expression,
since it consists of a single literal numeral. The rest of the examples in this section
will not work until you complete various portions of the project.
load function differs from standard Scheme in that,
since we don't have strings, we use a symbol for the file name. For example
scm> (load 'problems.scm)
Turtle Graphics. Finally, to keep up the traditions of recent years, we've
added some simple routines for turtle graphics, described later,
that simply call functions in the Python
turtle package (whose documentation we suggest you see;
for one thing, it will let you try out turtle-graphics programs in Python).
turtle 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
your personal computer, or test on your class account.
The tests for this project are largely taken from the Scheme
textbook that 61A used for many years. Examples from relevant
chapters (and a few more examples to test various corner cases)
You can also compare the output of your interpreter to the expected output by
passing the file name to
# python3 scheme_test.py tests.scm
This is a rather useful script. As you'll see,
tests.scm contains Scheme
expressions interspersed with comments in the form:
(+ 1 2) ; expect 3
scheme_test.py will evaluate
(+ 1 2)
using your code in
scheme.py, and output a test failure
3 is not returned.
scheme_test script collects these expected outputs and compares
them with the actual output from the program, counting and reporting mismatches.
You can even test that your interpreter catches errors. The problem with error tests
is that there is no "right" output. Our script, therefore, only requires that error
messages start with "
Error". Any such line will match
; expect Error
Finally, as always, you can run the doctests by doing:
python3 -m doctest scheme.py
Don't forget to use the
trace decorator from the
module to follow the path of execution in your interpreter.
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 crash. 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 caught and changed into
exceptions, which are caught and printed as error messages by the Scheme
read-eval-print loop we've written for you. Python exceptions that "leak out" to the
user in raw form are errors in your interpreter (tracebacks are for implementors, not
This project is about modifying a complex piece of existing code. In such a
situation, it's good to take time at the outset to read what's provided, try to
understand what's there, and accumulate questions about parts you don't understand
before trying to mess around with it. Indeed, a lot of what you take away from
this project will simply be what you learn by reading all the code you don't
have to write. In many cases, you'll be able to experiment with parts of it in
isolation, simply by starting up an interactive Python session and using
import to get access to the parts you'd like to play with.
Take a look over all the files provided with this project (with your partner, of
course). Look particularly at
scheme_primitives.py, which defines the basic
data structures that Scheme programs manipulate, and at the starter
In the file
scheme.py, look at
read_eval_print, which is the top-level function that defines the
interpreter's actions. Look also at the class
represents environment frames (just like those in the text and in lecture). Look at the
run function and what it calls to see how the interpreter gets initialized
and how the global environment comes to be.
You won't have to modify
scheme_tokens.py, but since you will be modifying
the reader (and since we can ask you anything we want on tests), it might be a good
idea to understand the routines it provides and how they are used. At any given time,
the "current port" is a
buffer.py), which is used to provide a
continuous stream of tokens from a token source. See if you can figure out how to look
at the token stream produced for a small Scheme file.
Symbol Restrictions. For this project, your Scheme interpreter will only accept lower-case characters as valid characters in a symbol. For instance, the following is invalid in our Scheme:
scm> (define L '(1 2 3)) warning: invalid token: L scm> (define myList '(1 2 3)) warning: invalid token: myList
To run your Scheme interpreter in interactive mode, do:
# python3 scheme.py scm>Alternately, you can tell your Scheme interpreter to evaluate the lines of an input file by passing the file name as an argument to
# python3 scheme.py my_code.scmCurrently, your Scheme interpreter can handle a few simple expressions, such as:
scm> 1 1 scm> 42 42 scm> #t True scm> 'hi hiTo exit the Scheme interpreter, issue either
Ctrl-d. Once you've implemented primitive functions, you can also invoke the
exitprimitive function to exit the interpreter:
scm> (exit) #
scheme.py is intended to read in tokens
from the input source (such as a .scm file, or from the interactive
prompt) and return Scheme
expressions in our internal representation. In our Scheme interpreter,
we will represent Scheme data types in the following way:
|Scheme Data Type||Our Internal Representation|
|Numbers|| Python's built-in
|Symbols|| Python's built-in
| Booleans (
|| Python's built-in
At the moment, the
scheme_read can only handle atoms
(like numbers, symbols, and boolean values) and the quote form. In
can't handle pairs.
Problem 1 (2 pt). Your first task, with your partner, is to complete
scheme_read function. The
should repeatedly pop tokens from the
instance) until it is able to return an expression. For instance:
>>> scheme_read(Buffer(tokenize_lines(["42"]))) 42 >>> scheme_read(Buffer(tokenize_lines(["4 2 'hi"]))) 4 # The Buffer object is now ["2 'hi"] >>> scheme_read(Buffer(tokenize_lines(["(1 2 3) 'hi 4"]))) Pair(1, Pair(2, Pair(3, NULL))) >> scheme_read(Buffer(tokenize_lines(["'bagel"]))) Pair("quote", Pair("bagel", NULL)) # 'bagel is treated as (quote bagel)Note that, depending on the input,
scheme_readmay only have to pop one token from
input_port, or it may have to pop many tokens.
input_portcurrently refers to an atom, which are booleans, numbers, symbols, and NULL, then simply return the atom.
scheme_atompprocedure, defined in
'bagel), then treat the quoted symbol as the special-form
"(", then we are starting a new pair.
scheme_read, the first two cases (atoms, quotes)
are already handled for you. Your task is to handle the third
case, which deals with pairs.
The syntax for pairs and lists is a left parenthesis, followed by a "tail", defined as
The internal representation for Scheme's Null value that we will
use is the global variable
NULL, defined in
The provided (incomplete) nested function
should read the tail and return its value. For
example, the value that
scheme_read should return for "
(1 2 . 3)"
consists of the value of the tail "
1 2 . 3)", which is
1and the value of the tail "
2 . 3)", which is
2and the Scheme value
read_tailwould return is:
Pair(1, Pair(2, 3)).
As another example, the value returned for "
(1 2)" is the value of the
1 2)", which is
1and the value of the tail "
2)", which is
2and the value of the tail "
)", which is the empty list.
Pair(1, Pair(2, NULL)).
If you've completed
read_tail correctly, then the
following expressions should evaluate correctly in your Scheme
# python3 scheme.py scm> 42 42 scm> '(1 2 3) (1 2 3) scm> '() nil scm> '(1 (2 3) (4 (5))) (1 (2 3) (4 (5))) scm> '(1 (9 8) . 7) (1 (9 8) . 7) scm> '(hi there . (cs . (student))) (hi there cs student)The following expressions should throw a SchemeError:
scm> (lambda (x y . a b) (+ x y a b)) scm> (lambda (a b . c . d) (+ a b c d)) scm> '(1 2 . 3 4) scm> '(a b (5 6 . doh doh))Due to time limitations, here are a few cases that you do not have to throw errors for - your Scheme interpreter may behave in any way (i.e. throw mysterious errors, continue to operate strangely, etc.):
scm> (lambda (. x) (* x 2))Add more tests to the beginning of the
tests.scmto make sure that your reader is working correctly.
Note: Make sure that your
read_tail functions are indeed working correctly
before moving on. Because the subsequent exercises rely on
scheme_read to correctly process lines, any bugs in your
scheme_read function will cause strange and unexpected
errors in the
Now, we will implement an evaluator.
The main part of the evaluator is within
scheme_apply. Assuming Problem 1 has been done correctly,
your evaluator should be able to correctly handle atoms (except for
symbols), quoting, and lists.
However, function calls will not work yet -- the
is incomplete. In the next exercise, we will implement primitive procedures.
Problem 2. Read
scheme_apply. Notice that, for
scheme_apply calls the
procedure, which should apply a primitive procedure to the
provided arguments, with respect to some environment.
Scheme primitive procedures will be represented internally as instances
PrimitiveProcedure class, defined in
has two instance attributes:
self.fn-- The actual primitive function object (this is a
self.use_env-- A boolean flag that indicates whether or not this primitive procedure will expect the current environment to be passed in as the last argument.
scheme_primitives.pyfile -- any function definition with the
@primitivedecorator will be added to the globally-defined
apply_primitive procedure is incomplete. With both
you and your partner, complete
the definition so that the primitive procedure is applied to its
arguments. In particular,
also make sure that your
apply_primitive solution does the
True, then pass the current environment env as the last argument.
TypeErrorexception being thrown, then raise a
Note that, even after you complete
your Scheme interpreter will still not be able to apply primitive
procedures. This is because your Scheme interpreter still doesn't know
how to look up the values for the primitive procedure symbols (such as
In the next two steps, you and your partner will
implement symbol lookup and symbol definition.
Problem A2 (2 pt). In this step, you will get simple symbol evaluation and definition to work. Currently, your Scheme interpreter is unable to find the value of some defined symbol, even for the already-defined primitive procedures.
The main code that will deal with variable name lookups is located in
Frame class, in
instance has two instance attributes:
self.inner-- a dictionary that maps variable names to values.
self.parent-- a pointer to a parent
Frameinstance. By definition, the parent of the Global Frame is
findmethod is incomplete -- at the moment, it always raises an
"unknown identifier"error. The
findmethod should, given a symbol
sym, return the first
Framethat contains a definition for
findprocedure should behave in the following way:
symis defined in the current
Frame, then return the current
symis not defined in the current
findshould follow the
parentpointer until it finds some
Framethat contains a definition for
symis not found in the Global Frame, then the
findmethod should raise a
After you complete this problem, you should be able to ask for the
value of primitive procedures within the Scheme interpreter (such as
car). In particular,
you should be able to call primitive procedures!
scm> + <scheme_primitives.PrimitiveProcedure object at 0x2742d50> scm> (+ 1 2) 3 scm> (* 3 4 (- 5 2) 1) 36
Problem B2 (2 pt). There are two missing parts in the method
do_define_form, which handles the
construct. Here, we'll do just the first part: handling cases like
(define pi2 (* 2 3.1415926))where the defined symbol appears alone. Fill in the missing piece to make this work. First, you'll want to see how
do_define_formis called (it's called within
scheme_eval). Then, you'll want to take a look at the
Frame.definemethod. Some questions that you might want to answer are: what type of object is
vals? How do I get the symbol (i.e. variable name) from
vals, and how do I compute the value that I should bind the symbol to in the current environment
When combined with your partner's work on A2, you should now be able to do things like
scm> (define x 15) scm> (define y (* 2 x)) scm> y 30 scm> (+ y (* y 2) 1) 91 scm> (define x 20) scm> x 20
Now that you can created symbols and given them simple values, it should be easy to
come up with tests for A2 and B2. Add your tests to
At this point in the project, your Scheme interpreter should be be able to support the following features:
quoteform, such as
(define myval 42).
(+ (- 4 2) 5)
In our interpreter, user-defined functions will
be represented as instances of the
instance consists of the following instance attributes:
self.formals-- A Scheme list of the formal parameters that this lambda function expects.
self.body-- A single Scheme expression, consisting of the body of this function.
self.env-- The environment in which this function was created.
Problem 3 (2 pt). Before we can call user-defined functions, we need to implement
a piece of scheme syntax called
begin works as follows:
scm> (begin (+ 2 3) (+ 5 6)) 11 scm> (begin (display 3) (newline) (+ 2 3)) 3 5
beginexecutes all the statements given as arguments, and then returns what the last statement evaluates to.
scheme_eval evaluates one of
the conditional constructs (
case), notice that it calls
on the return value of the relevant
Take care that your Scheme interpreter doesn't inadvertantly call
scheme_eval on the same value twice, or else you might
get the following invalid behavior:
scm> (begin 30 'hello) Error: unknown identifier: hello
Problem A4 (2 pt). Before we can call
LambdaProcedures, we must
be able to create them. At the moment, the
do_lambda_form method, which
LambdaProcedure values, is incomplete. Once you
do_lambda_form, you can check
your work by typing in lambda expressions to the interpreter. You should see something
scm> (lambda (x y) (+ x y)) (lambda (x y) (+ x y))Remember that, in Scheme, it is legal to have function bodies with more than one expression:
STk> ((lambda (y) 42 (* y 2)) 5) 10In order to more-easily implement this behavior, your
do_lambda_formshould do the following. If
do_lambda_formdetects that the current lambda body has multiple expressions, then the
do_lambda_formfunction should place the expressions inside of an outer
(begin ...)expression, and replace the lambda's body with the
scm> (lambda (y) 42 (* y 2)) (lambda (y) (begin 42 (* y 2)))For an explanation of why the
beginis inserted, see the
__init__function for the
LambdaProcedureclass. This workaround will allow us to handle multi-expression function bodies in the same manner as single-expression function bodies.
Problem B4 (2 pt). Currently, your Scheme interpreter is able to define user-defined functions in the following manner (assuming that Problem A4 is done):
scm> (define f (lambda (x) (* x 2)))However, we'd like to be able to use the shorthand form of defining functions:
scm> (define (f x) (* x 2))
do_define_form function so that it correctly
handles the shorthand function definition form. Make sure that it can
handle multi-expression bodies.
Here's a tip. You can think of the short-hand form of defining functions as doing the following:
(define (square x) (* x x))Becomes:
(define square (lambda (x) (* x x)))
After you complete Problem A4 and Problem B4, you should be able to define user-defined functions. However, your interpreter can't actually call them yet. Next, you and your partner will extend your interpreter to allow the invocation of user-defined functions.
Problem A5 (3 pt). The
make_call_frame method of
Frame class is incomplete. Your task is to complete
make_call_frame method should simulate the
process of calling a user-defined function. Namely, this involves:
Don't forget the cases where the formal parameter list contains a trailing "varargs" entry, as in:
(define (format port form . args) ...)One unifying way to handle this case along with the simple lists-of-symbols is to consider the formals list as a kind of pattern that is matched against the list of argument values. That is, the formals list matches the argument list if you treat each symbol in the formals list as a pattern variable or wildcard that matches any expression. Thus, the list of values
(1 2 3)has the internal structure
Pair(number, Pair(number, Pair(number, NULL)))while the formals list
(a . b)has the structure
Pair(symbol a, symbol b)These have the same form if we match symbol
ato the number 1 and symbol
Pair(number, Pair(number, NULL))Likewise, the ordinary formals list
(a b c)has the structure
Pair(symbol a, Pair(symbol b, Pair(symbol c, NULL)))so it matches the argument list, too.
Problem B5 (3 pt). The function
checks the formals-list argument to
currently does nothing at the
moment. Fix it so that
check_formals raises a
SchemeError if the list of
In particular, make sure that it supports the following argument syntax:
scm> (lambda (x y z) (+ x y z)) scm> (lambda (x . nums) (* x (reduce + nums))) scm> (lambda nums (reduce * nums))Make sure that your interpreter rejects the following. Where your interpeter rejects the following is not important (i.e. in scheme_read or check_formals), as long as you are correctly raising some SchemeError. It is an error for your interpreter to raise a Python exception.
scm> (lambda (x (y) z) (* x y z)) scm> (define (fn x 2) (+ x 2))
Problem 6 (3 pt). Finally, both you and your partner
scheme_apply to correctly handle
user-defined functions. Complete the
function so that it does the following:
Frame, with all formal parameters bound to its associated evaulated arguments.
procedurewith respect to this new frame.
After you complete
functions (and lambda functions)
should work in your Scheme interpreter.
Be sure to add
tests for Problems 3–6 to
Problem 7. The basic Scheme conditional constructs are
cond. In the
next section, you and your partner will implement these conditional
Remember that the logical forms (
are short-circuiting. This means that not all arguments to an
or should be evaluated, depending on
and, your interpreter should evaluate each
argument from left-to-right, and if any argument evaluates to a
then you stop evaluating the
and and return
In particular, if all arguments are a true value, then
or, your interpreter should evaluate each
argument from left-to-right, and if any argument evaluates to a
true value, then you stop evaluating the
or and return
True. If all arguments are false values, then
Here are a few examples:
scm> (and 4 5 6) True ; all operands are true values scm> (or 5 2 1) True ; 5 is a true value scm> (and #t #f 42 (/ 1 0)) False ; short-circuiting behavior of and scm> (or 4 #t (/ 1 0)) True ; short-circuiting behavior of or
You might find the
scheme_true function useful,
Problem A7 (3 pt). Currently,
and forms don't work correctly (
and always evaluates
True). Fill in the
Make sure you correctly implement the short-circuiting behavior of
and, as described above. Add
test cases to
Note: For this project, we will only handle
expressions that contain three operands. The following
expressions should be correctly supported by your interpreter:
scm> (if (= 4 2) 'true 'false) false scm> (if (= 4 4) (* 1 2) (+ 3 4)) 2And the following expression should be rejected by your interpreter:
scm> (if (= 4 2) 'true) Error: too few operands in form
Problem B7 (3 pt). For the second half, fill in the implementations of
do_or_form. Make sure you
correctly implement the short-circuiting behavior of
as described above. Add test cases
In particular, make sure that your
correctly handles the following forms:
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)) 42For the last example, where the body of a
condhas multiple expressions, you might find it helpful to 'convert'
cond-bodies with multiple expression bodies into a single
scm> (cond ((= 4 4) 'here 42))Becomes:
scm> (cond ((= 4 4) (begin 'here 42)))
A few clarifications:
elseclauses must contain at least one expression, i.e. the following
condusage is invalid in our project:
scm> (cond ((= 4 3) 5) (else))
None(which signals an undefined expression. It is valid for your project code to issue an error in the following way:
scm> (cond ((= 4 5) 1)) Error: Cannot evaluate an undefined expression.
Problem 8 (3 pt). The
let special form introduces local
variables, giving them their initial values. For example,
scm> (define x 'hi) scm> (define y 'bye) scm> (let ((x 42) (y (* 5 10))) (list x y)) (42 50) scm> (list x y) (hi bye)Implement the
do_let_formmethod to have this effect and (need we say it at this point?) test it, by adding test cases to
tests.scm. Make sure your
letcorrectly handles multi-expression bodies:
scm> (let ((x 42)) x 1 2) 2
As a reminder, you can think of the
let form as
doing the following:
scm> (let ((x 42) (y 16)) (+ x y)) 58Becomes:
scm> ((lambda (x y) (+ x y)) 42 16) 58Thus, a
letform implicitly creates a new
letbindings) which extends the current environment, and evaluates the body of the
letwith respect to this new
Frame. This is very much exactly like a user-defined function call. Note that, in your project code, you don't have to actually create a
LambdaProcedureand call it - instead, you can create a new
Frame, add the necessary bindings, and evaluate the expressions of the
letbody with respect to the new
Frame(indeed, the provided skeleton code points you towards this approach).
Reminder: the bindings created by a
let are not
able to refer back to previously-declared bindings from the same
STk> (let ((var1 42) (var2 (+ var1 2))) (+ var1 var2)) *** Error: unbound variable: xMake sure your interpreter behaves in this way too.
Extra Credit 1. (2 pt). The
let* construct is like
let, except that each initialization expression "sees" the definitions
that have gone before. Essentially,
(let* ((x 10) (y (+ x 5))) (list x y))is the same as
(let ((x 10)) (let ((y (+ x 5))) (list x y)))and therefore has the value
(10 15). Implement this special form (and, yes, test it).
Extra Credit 2 (2 pt). The
case construct is a fancy conditional
similar to the Java and C/C++
switch statement. Here are some examples
from the Scheme reference manual:
scm> (case (* 2 3) ((2 3 5 7) 'prime) ((1 4 6 8 9) 'composite)) composite scm> (case (car '(c d)) ((a e i o u) 'vowel) ((w y) 'semivowel) (else 'consonant)) consonant scm> (define x 3) (define y 10) scm> (case (car '(+ * /)) ((+ add) (+ x y)) ((* mult) (* x y)) ((/ div) (/ x y))) 13
The first operand is evaluated, but the first element of each of the subsequent
operands is not evaluated (it's implicitly quoted). As for
remaining items in the matching operand are evaluated, and the value of the last is the
value of the
case. Implement and test this special form.
For this project, we will slightly differ from the behavior of
STk's implementation of
case. In our Scheme
interpreter, assume that the correct syntax for the
(case <expr> (<lst_0> <expr_0>) ... (<lst_N> <expr_N>)) or: (case <expr> (<lst_0> <expr_0>) ... (<lst_N> <expr_N>) (else <expr_else>))There must be at least one
(<lst_i> <expr_i>)operand. Each
<lst_i>is a list of symbols or literals:
<lst_i> := (sym_0 ... sym_N)An empty
<lst_i>should be accepted by your interpreter (even though that case will never be taken), such as:
scm> (case 2 (() 'never-get-here) (else 'good)) good
If no cases of a
case expression are taken, and an
else is not present, then
scm> (case 42 ((1 2 3) 'case-a) (('a 'b 'c) (* 2 3))) False
In particular, make sure that the all operands in the
case are correctly formed. If any operands are ill-formed
(according to our syntax),
(case 2 (2 'a) (else 'b)), then raise
SchemeError with a meaningful error message.
You should have been adding tests to
tests.scm as you did each problem.
In any case, make sure you have a reasonably complete set, since the readers will be
looking at it. Your program should pass all your tests when you (or the autograder) run
# python3 scheme_tests.py tests.scm
Your Scheme interpreter implementation is now complete.
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 at the bottom of
along with some calls and expected results.
Problem A9 (3 pt). Implement the
filter procedure, which takes
two arguments, a procedure name and a list and returns a list that
contains all elements of the input list for which applying the named procedure outputs
a true value (i.e., something other than
Problem B9 (3 pt). Implement the
reverse procedure, which takes
a list and returns the reverse of that list.
Problem 10 (2 pt). Implement the
count-change procedure, which
counts all of the ways to make change for a
total amount, using coins with
various denominations (
denoms), but never uses more than
max-coins in total. Write your implementation in
The procedure definition line is provided, along with U.S. denominations.
Problem 11 (2 pt) Implement the
which counts all the ways to partition a positive integer
total using only
pieces less than or equal to another positive integer
5 has 5 partitions using pieces up to a
Problem 12 (3 pt). Implement the
which lists all of the ways to partition a positive integer
total into at
max-pieces pieces that are all less than or equal to a positive
max-value. Hint: Define a helper function to construct
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 (3 pt). Create a visualization of an iterative or recursive process of your choosing, using turtle graphics. Your implementation must be written entirely in Scheme, using STk (or the interpreter you have built (however, no extending the interpreter to do your work in Python)).
Prizes 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 (in homework 14). 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.
Submission instructions for each category are included in the Homework 13 specifications.
Contest submissions are due next Saturday (August 4th, 2012). Note that this is before the project itself is due. In the following Tuesday's homework, you will vote on your favorite drawing.