Lab 10: Scheme, Tail Calls
Due by 11:59pm on Thursday, July 27.
Starter Files
Download lab10.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Topics
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
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, typepython3 scheme -i <file.scm>
. To exit the Scheme interpreter, type(exit)
.
Recommended VSCode Extensions
If you use VSCode as your text editor, we have found these extensions to be quite helpful for Scheme :)
Before:
After:
Extensions:
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 by submitting to the appropriate Gradescope assignment though!
Scheme Editor
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 Ctrl-C
.
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!
Expressions
Primitive Expressions
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
Symbols
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!
Booleans
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 0
).
Our particular version of the Scheme interpreter allows you to write True
and
False
in place of #t
and #f
. This is not standard.
scm> #t
#t
scm> #f
#f
Call Expressions
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
Special Forms
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 if
, cond
,
define
, and lambda
forms. Read their corresponding sections below to find
out what their rules of evaluation are!
Control Structures
if
Expressions
The 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 #t
or #f
.
The rules for evaluating an if
special form expression are as follows:
- Evaluate
<predicate>
. - If
<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
if
expression will only evaluate two of its operands, the conditional expression and either<true-result>
or<false-result>
. Because we don't evaluate all the operands in anif
expression, it is a special form.
Let's compare a Scheme if
expression with a Python if
statement:
Scheme | 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 if
expression expects just a single expression for each of the true result and the
false result.
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
branched if
expressions:
Scheme | Python |
---|---|
|
|
cond
Expressions
Using nested 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: (<p>
<e>)
.
(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
optional else
clause has no predicate.
The rules of evaluation are as follows:
- Evaluate the predicates
<p1>
,<p2>
, ...,<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
else
clause, evaluate and return<else-expression>
.
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):
Scheme | Python |
---|---|
|
|
Defining Names
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
use the define
form with the following syntax:
(define <name> <expression>)
The rules to evaluate this expression are
- Evaluate the
<expression>
. - Bind its value to the
<name>
in the current frame. - Return
<name>
.
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
<body>
. - Bind the procedure to the
<name>
in the current frame. - Return
<name>
.
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
example, <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 define
expression.
Lambda Functions
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
Let's look at the equivalent expressions in Python:
>>> lambda x, y: x + y
>>> (lambda x, y: x + y)(3, 4)
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 return
statement in Scheme. The function will simply return the value of the last
expression in the body.
Lists
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.)
Lists
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 Link
objects, a Scheme list is constructed with a series of pairs, which are created
with the constructor cons
.
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
another cons
expression or nil
.
We can retrieve values from our list with the car
and cdr
procedures, which
now work similarly to the Python Link
's first
and rest
attributes.
(Curious about where these weird names come from? Check out their
etymology.)
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
error:
scm> (cons 1 2)
Error
list
Procedure
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
arguments:
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.
Quote Form
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 '
is
not evaluated.
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
Tail Calls
When writing a recursive procedure, it's possible to write it in a tail recursive way, where all of the recursive calls are tail calls. A tail call occurs when a function calls another function as the last action of the current frame.
Consider this implementation of factorial
that is not tail recursive:
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
The recursive call occurs in the last line, but it is not the last expression
evaluated. After calling (factorial (- n 1))
, the function still needs to
multiply that result with n
. The final expression that is evaluated is
a call to the multiplication function, not factorial
itself. Therefore,
the recursive call is not
a tail call.
Here's a visualization of the recursive process for computing (factorial 6)
:
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
The interpreter first must reach the base case and only then can it begin to calculate the products in each of the earlier frames.
We can rewrite this function using a helper function that remembers the temporary product that we have calculated so far in each recursive step.
(define (factorial n)
(define (fact-tail n result)
(if (= n 0)
result
(fact-tail (- n 1) (* n result))))
(fact-tail n 1))
fact-tail
makes a single recursive call to fact-tail
, and
that recursive call is the last expression to be evaluated, so it is a tail
call. Therefore, fact-tail
is a tail recursive process.
Here's a visualization of the tail recursive process for computing (factorial 6)
:
(factorial 6)
(fact-tail 6 1)
(fact-tail 5 6)
(fact-tail 4 30)
(fact-tail 3 120)
(fact-tail 2 360)
(fact-tail 1 720)
(fact-tail 0 720)
720
The interpreter needed less steps to come up with the result, and it didn't need to re-visit the earlier frames to come up with the final product.
In this example, we've utilized a common strategy in implementing tail-recursive procedures which is to pass the result that we're building (e.g. a list, count, sum, product, etc.) as a argument to our procedure that gets changed across recursive calls. By doing this, we do not have to do any computation to build up the result after the recursive call in the current frame, instead any computation is done before the recursive call and the result is passed to the next frame to be modified further. Often, we do not have a parameter in our procedure that can store this result, but in these cases we can define a helper procedure with an extra parameter(s) and recurse on the helper. This is what we did in the factorial
procedure above, with fact-tail
having the extra parameter result
.
Tail Call Optimization
When a recursive procedure is not written in a tail recursive way, the interpreter must have enough memory to store all of the previous recursive calls.
For example, a call to the (factorial 3)
in the non tail-recursive version
must keep the frames for all the numbers from 3 down to the base case,
until it's finally able to calculate the intermediate products and forget those frames:
For non tail-recursive procedures, the number of active frames grows proportionally to the number
of recursive calls. That may be fine for small inputs, but imagine calling factorial
on a large number like 10000. The interpreter would need enough memory for all 1000 calls!
Fortunately, proper Scheme interpreters implement tail-call optimization as a requirement of the language specification. TCO ensures that tail recursive procedures can execute with a constant number of active frames, so programmers can call them on large inputs without fear of exceeding the available memory.
When the tail recursive factorial
is run in an interpreter with tail-call optimization,
the interpreter knows that it does not need to keep the previous frames around,
so it never needs to store the whole stack of frames in memory:
Tail-call optimization can be implemented in a few ways:
- Instead of creating a new frame, the interpreter can just update
the values of the relevant variables in the current frame (like
n
andresult
for thefact-tail
procedure). It reuses the same frame for the entire calculation, constantly changing the bindings to match the next set of parameters. - How our 61A Scheme interpreter works: The interpreter builds a new frame as usual, but then replaces the current frame with the new one. The old frame is still around, but the interpreter no longer has any way to get to it. When that happens, the Python interpreter does something clever: it recycles the old frame so that the next time a new frame is needed, the system simply allocates it out of recycled space. The technical term is that the old frame becomes "garbage", which the system "garbage collects" behind the programmer's back.
Tail Context
When trying to identify whether a given function call within the body of a function is a tail call, we look for whether the call expression is in tail context.
Given that each of the following expressions is the last expression in the body of the function, the following expressions are tail contexts:
- the second or third operand in an
if
expression - any of the non-predicate sub-expressions in a
cond
expression (i.e. the second expression of each clause) - the last operand in an
and
or anor
expression - the last operand in a
begin
expression's body - the last operand in a
let
expression's body
For example, in the expression (begin (+ 2 3) (- 2 3) (* 2 3))
,
(* 2 3)
is a tail call because it is the last operand expression to be
evaluated.
Required Questions
Getting Started Videos
These videos may provide some helpful direction for tackling the coding problems on this assignment.
To see these videos, you should be logged into your berkeley.edu email.
Scheme Functions
Q1: Make Adder
Write the procedure make-adder
which takes in an initial number,
num
, and then returns a procedure. This returned procedure takes in a
number inc
and returns the result of num + inc
.
Hint: To return a procedure, you can either return a
lambda
expression ordefine
another nested procedure. Remember that Scheme will automatically return the last clause in your procedure.You can find documentation on the syntax of
lambda
expressions in the 61A scheme specification!
(define (make-adder num)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q make_adder
Q2: Compose
Write the procedure composed
, which takes in procedures f
and g
and outputs a new procedure. This new procedure takes in a number x
and outputs the result of calling f
on g
of x
.
(define (composed f g)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q composed
Scheme Lists
Q3: My Filter
Write a procedure my-filter
, which takes a predicate pred
and a list s
, and
returns a new list containing only elements of the list that satisfy the
predicate. The output should contain the elements in the same order that they
appeared in the original list.
Note: Make sure that you are not just calling the built-in filter
function in Scheme - we are asking you to re-implement this!
(define (my-filter pred s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q filter -u
python3 ok -q filter
Tail Calls
For a refresher on the concepts behind tail call optimization and an example of its implementation, check out the Tail Calls topic section above.
Q4: Exp
We want to implement the exp
procedure. So, we write the following
recursive procedure:
(define (exp-recursive b n)
(if (= n 0)
1
(* b (exp-recursive b (- n 1)))))
Try to evaluate
(exp-recursive 2 (exp-recursive 2 10))
You will notice that it will cause a maximum recursion depth error. To fix this, we need to use tail recursion! Implement the exp
procedure using tail recursion:
(define (exp b n)
;; Computes b^n.
;; b is any number, n must be a non-negative integer.
(define (helper n so-far) ;; since b never changes, we can use the b from the outer function
(helper n 1)
)
Use Ok to test your code:
python3 ok -q exp
Submit
Make sure to submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. For a refresher on how to do this, refer to Lab 00.
Optional Questions
Q5: Interleave
Implement the function interleave
, which takes a two lists lst1
and lst2
as
arguments. interleave
should return a new list that interleaves the elements
of the two lists. (In other words, the resulting list should contain elements
alternating between lst1
and lst2
.)
If one of the input lists to interleave
is shorter than the other, then
interleave
should alternate elements from both lists until one list has no
more elements, and then the remaining elements from the longer list should be
added to the end of the new list.
(define (interleave lst1 lst2)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q interleave -u
python3 ok -q interleave
Q6: Pow
Implement a procedure pow
for raising the number base
to the power of a
nonnegative integer 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.
If you would like a quick refresher on Scheme syntax consider looking at the Scheme Specification and Scheme Built-in Procedure Reference (and the Lab 10 Scheme Refresher).
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
even?
andodd?
. 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 test your code:
python3 ok -q pow