Due by 11:59pm on Tuesday, July 26.
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.
Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type
python3 scheme. To run a Scheme program interactively, type
python3 scheme -i <file.scm>. To exit the Scheme interpreter, type
(exit). You may find it useful to try code.cs61a.org/scheme when working through problems, as it can draw environment and box-and-pointer diagrams and it lets you walk your code step-by-step (similar to Python Tutor). Don't forget to submit your code through Ok though!
You can write your code by either opening the designated
.scm file in your text editor, or by typing directly in the Scheme Editor, which can also be useful for debugging. To run this editor, run
python3 editor. This should pop up a window in your browser; if it does not, please navigate to localhost:31415 while
python3 editor is still running and you should see it. If you choose to code directly in the Scheme Editor, don't forget to save your work before running Ok tests and before closing the editor. To stop running the editor and return to the command line, type
Make sure to run
python3 ok in a separate tab or window so that the editor keeps running.
If you find that your code works in the online editor but not in your own interpreter, it's possible you have a bug in your code from an earlier part that you'll have to track down. Every once in a while there's a bug that our tests don't catch, and if you find one you should let us know!
Just like in Python, atomic, or primitive, expressions in Scheme take a single step to evaluate. These include numbers, booleans, symbols.
scm> 1234 ; integer 1234 scm> 123.4 ; real number 123.4
Out of these, the symbol type is the only one we didn't encounter in Python. A symbol acts a lot like a Python name, but not exactly. Specifically, a symbol in Scheme is also a type of value. On the other hand, in Python, names only serve as expressions; a Python expression can never evaluate to a name.
scm> quotient ; A name bound to a built-in procedure #[quotient] scm> 'quotient ; An expression that evaluates to a symbol quotient scm> 'hello-world! hello-world!
In Scheme, all values except the special boolean value
#f are interpreted
as true values (unlike Python, where there are some false-y values like
Our particular version of the Scheme interpreter allows you to write
False in place of
#f. This is not standard.
scm> #t #t scm> #f #f
Like Python, the operator in a Scheme call expression comes before all the operands. Unlike Python, the operator is included within the parentheses and the operands are separated by spaces rather than with commas. However, evaluation of a Scheme call expression follows the exact same rules as in Python:
- Evaluate the operator. It should evaluate to a procedure.
- Evaluate the operands, left to right.
- Apply the procedure to the evaluated operands.
Here are some examples using built-in procedures:
scm> (+ 1 2) 3 scm> (- 10 (/ 6 2)) 7 scm> (modulo 35 4) 3 scm> (even? (quotient 45 2)) #t
The operator of a special form expression is a special form. What makes a special form "special" is that they do not follow the three rules of evaluation stated in the previous section. Instead, each special form follows its own special rules for execution, such as short-circuiting before evaluating all the operands.
Some examples of special forms that we'll study today are the
lambda forms. Read their corresponding sections below to find
out what their rules of evaluation are!
if special form allows us to evaluate one of two expressions based on a
predicate. It takes in two required arguments and an optional third argument:
(if <predicate> <if-true> [if-false])
The first operand is what's known as a predicate expression in Scheme, an
expression whose value is interpreted as either
The rules for evaluating an
if special form expression are as follows:
<predicate>evaluates to a truth-y value, evaluate and return the value if the expression
<if-true>. Otherwise, evaluate and return the value of
[if-false]if it is provided.
Can you see why this expression is a special form? Compare the rules between a
regular call expression and an
if expression. What is the difference?
Step 2 of evaluating call expressions requires evaluating all of the operands in order. However, an
ifexpression will only evaluate two of its operands, the conditional expression and either
<false-result>. Because we don't evaluate all the operands in an
ifexpression, it is a special form.
Let's compare a Scheme
if expression with a Python
Although the code may look the same, what happens when each block of code is
evaluated is actually very different. Specifically, the Scheme expression,
given that it is an expression, evaluates to some value. However, the Python
if statement simply directs the flow of the program.
Another difference between the two is that it's possible to add more lines of
code into the suites of the Python
if statement, while a Scheme
expression expects just a single expression for each of the true result and the
One final difference is that in Scheme, you cannot write
elif cases. If you
want to have multiple cases using the
if expression, you would need multiple
if expressions doesn't seem like a very practical way to take
care of multiple cases. Instead, we can use the
cond special form, a general
conditional expression similar to a multi-clause if/elif/else conditional
expression in Python.
cond takes in an arbitrary number of arguments known as
clauses. A clause is written as a list containing two expressions:
(cond (<p1> <e1>) (<p2> <e2>) ... (<pn> <en>) [(else <else-expression>)])
The first expression in each clause is a predicate. The second expression in
the clause is the return expression corresponding to its predicate. The
else clause has no predicate.
The rules of evaluation are as follows:
- Evaluate the predicates
<pn>in order until you reach one that evaluates to a truth-y value.
- If you reach a predicate that evaluates to a truth-y value, evaluate and return the corresponding expression in the clause.
- If none of the predicates are truth-y and there is an
elseclause, evaluate and return
As you can see,
cond is a special form because it does not evaluate its
operands in their entirety; the predicates are evaluated separately from their
corresponding return expression. In addition, the expression short circuits
upon reaching the first predicate that evaluates to a truth-y value, leaving
the remaining predicates unevaluated.
The following code is roughly equivalent (see the explanation in the if expression section):
The special form
define is used to define variables and functions in Scheme.
There are two versions of the
define special form. To define variables, we
define form with the following syntax:
(define <name> <expression>)
The rules to evaluate this expression are
- Evaluate the
- Bind its value to the
<name>in the current frame.
The second version of
define is used to define procedures:
(define (<name> <param1> <param2> ...) <body> )
To evaluate this expression:
- Create a lambda procedure with the given parameters and
- Bind the procedure to the
<name>in the current frame.
The following two expressions are equivalent:
scm> (define foo (lambda (x y) (+ x y))) foo scm> (define (foo x y) (+ x y)) foo
define is a special form because its operands are not evaluated at all! For
<body> is not evaluated when a procedure is defined, but rather when
it is called.
<name> and the parameter names are all names that should not be
evaluated when executing this
All Scheme procedures are lambda procedures. To create a lambda procedure, we
can use the
lambda special form:
(lambda (<param1> <param2> ...) <body>)
This expression will create and return a function with the given parameters and
body, but it will not alter the current environment. This is very similar to a
lambda expression in Python!
scm> (lambda (x y) (+ x y)) ; Returns a lambda function, but doesn't assign it to a name (lambda (x y) (+ x y)) scm> ((lambda (x y) (+ x y)) 3 4) ; Create and call a lambda function in one line 7
A procedure may take in any number of parameters. The
<body> may contain
multiple expressions. There is not an equivalent version of a Python
statement in Scheme. The function will simply return the value of the last
expression in the body.
As you read through this section, it may be difficult to understand the differences between the various representations of Scheme containers. We recommend that you use our online Scheme interpreter to see the box-and-pointer diagrams of pairs and lists that you're having a hard time visualizing! (Use the command
(autodraw)to toggle the automatic drawing of diagrams.)
Scheme lists are very similar to the linked lists we've been working with in
Python. Just like how a linked list is constructed of a series of
objects, a Scheme list is constructed with a series of pairs, which are created
with the constructor
Scheme lists require that the
cdr is either another list or
nil, an empty list.
A list is displayed in the interpreter as a sequence of values (similar to the
__str__ representation of a
Link object). For example,
scm> (cons 1 (cons 2 (cons 3 nil))) (1 2 3)
Here, we've ensured that the second argument of each
cons expression is
cons expression or
We can retrieve values from our list with the
cdr procedures, which
now work similarly to the Python
(Curious about where these weird names come from? Check out their
scm> (define a (cons 1 (cons 2 (cons 3 nil)))) ; Assign the list to the name a a scm> a (1 2 3) scm> (car a) 1 scm> (cdr a) (2 3) scm> (car (cdr (cdr a))) 3
If you do not pass in a pair or nil as the second argument to
cons, it will
scm> (cons 1 2) Error
There are a few other ways to create lists. The
list procedure takes in an
arbitrary number of arguments and constructs a list with the values of these
scm> (list 1 2 3) (1 2 3) scm> (list 1 (list 2 3) 4) (1 (2 3) 4) scm> (list (cons 1 (cons 2 nil)) 3 4) ((1 2) 3 4)
Note that all of the operands in this expression are evaluated before being put into the resulting list.
We can also use the quote form to create a list, which will construct the exact
list that is given. Unlike with the
list procedure, the argument to
scm> '(1 2 3) (1 2 3) scm> '(cons 1 2) ; Argument to quote is not evaluated (cons 1 2) scm> '(1 (2 3 4)) (1 (2 3 4))
Built-In Procedures for Lists
There are a few other built-in procedures in Scheme that are used for lists. Try them out in the interpreter!
scm> (null? nil) ; Checks if a value is the empty list True scm> (append '(1 2 3) '(4 5 6)) ; Concatenates two lists (1 2 3 4 5 6) scm> (length '(1 2 3 4 5)) ; Returns the number of elements in a list 5
What Would Scheme Display?
Q1: WWSD: Combinations
Let's familiarize ourselves with some built-in Scheme procedures and special forms!
Use Ok to unlock the following "What would Scheme print?" questions:
python3 ok -q combinations -u
scm> (- 10 4) scm> (* 7 6) scm> (+ 1 2 3 4) scm> (/ 8 2 2) scm> (quotient 29 5) scm> (modulo 29 5)
scm> (= 1 3) ; Scheme uses '=' instead of '==' for comparison scm> (< 1 3) scm> (or 1 #t) ; or special form short circuits scm> (and #t #f (/ 1 0)) scm> (not #t)
scm> (define x 3) scm> x scm> (define y (+ x 4)) scm> y scm> (define x (lambda (y) (* y 2))) scm> (x y)
scm> (if (not (print 1)) (print 2) (print 3)) scm> (* (if (> 3 2) 1 2) (+ 4 5)) scm> (define foo (lambda (x y z) (if x y z))) scm> (foo 1 2 (print 'hi)) scm> ((lambda (a) (print 'a)) 100)
Q2: WWSD: Lists
Use Ok to test your knowledge with the following "What Would Scheme Display?" questions:
python3 ok -q wwsd_lists -u
scm> (cons 1 (cons 2 nil))______(1 2)scm> (car (cons 1 (cons 2 nil)))______1scm> (cdr (cons 1 (cons 2 nil)))______(2)scm> (list 1 2 3)______(1 2 3)scm> '(1 2 3)______(1 2 3)scm> (cons 1 '(list 2 3)) ; Recall quoting______(1 list 2 3) <!-- scm> (cons 1 `(list 2 3)) ; Quasiquotes also work as quotes! (1 list 2 3) -->scm> '(cons 4 (cons (cons 6 8) ()))______(cons 4 (cons (cons 6 8) ()))scm> (cons 1 (list (cons 3 nil) 4 5))______(1 (3) 4 5)
Q3: Over or Under
Define a procedure
over-or-under which takes in a number
num1 and a number
and returns the following:
- -1 if
num1is less than
- 0 if
num1is equal to
- 1 if
num1is greater than
Challenge: Implement this in 2 different ways using
(define (over-or-under num1 num2) 'YOUR-CODE-HERE )
Use Ok to test your code:
python3 ok -q over_or_under
Write the procedure
composed, which takes in procedures
and outputs a new procedure. This new procedure takes in a number
and outputs the result of calling
(define (composed f g) 'YOUR-CODE-HERE )
Use Ok to test your code:
python3 ok -q composed
Implement a procedure
pow for raising the number
base to the power of a
exp for which the number of operations grows logarithmically, rather than linearly (the number of recursive calls should be much smaller than the input
exp). For example, for
(pow 2 32) should take 5 recursive calls rather than 32 recursive calls. Similarly,
(pow 2 64) should take 6 recursive calls.
Hint: Consider the following observations:
- x2y = (xy)2
- x2y+1 = x(xy)2
For example we see that 232 is (216)2, 216 is (28)2, etc. You may use the built-in predicates
odd?. Scheme doesn't support iteration in the same manner as Python, so consider another way to solve this problem.
(define (square n) (* n n)) (define (pow base exp) 'YOUR-CODE-HERE )
Use Ok to unlock and test your code:
python3 ok -q pow -u python3 ok -q pow
Implement a procedure called
ascending?, which takes a list of numbers
True if the numbers are in nondescending order, and
otherwise. Numbers are considered nondescending if each subsequent number is
either larger or equal to the previous, that is:
1 2 3 3 4
Is nondescending, but:
1 2 3 3 2
Hint: The built-in
null?function returns whether its argument is
(define (ascending? lst) 'YOUR-CODE-HERE )
Use Ok to unlock and test your code:
python3 ok -q ascending -u python3 ok -q ascending
Make sure to submit this assignment by running:
python3 ok --submit