Lab 9: Scheme
Due by 11:59pm on Thursday, July 25.
Starter Files
Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Scheme Introduction
The 61A Scheme interpreter is included in each Scheme assignment. To start it,
type python3 scheme
in a terminal. To load a Scheme file called f.scm
, type python3 scheme -i f.scm
. To exit the Scheme interpreter, type
(exit)
.
Scheme Editor
All Scheme assignments include a web-based editor that makes it easy to run ok
tests and visualize environments. Type python3 editor
in a terminal, and the
editor will open in a browser window (at http://127.0.0.1:31415/
). Whatever
changes you make here will also save to the original file on your computer!
To stop running the editor and return to the command line, type Ctrl-C
in the
terminal where you started the editor.
The Run
button loads the current assignment's .scm
file and opens a Scheme
interpreter, allowing you to try evaluating different Scheme expressions.
The Test
button runs all ok tests for the assignment. Click View Case
for a
failed test, then click Debug
to step through its evaluation.
Recommended VS Code Extensions
If you choose to use VS Code as your text editor (instead of the web-based editor), install the vscode-scheme extension so that parentheses are highlighted.
Before:
After:
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.
Consult the drop-downs below if you need a refresher on Scheme. It's okay to skip directly to the questions and refer back here should you get stuck.
Atomic expressions (also called atoms) are expressions without sub-expressions, such as numbers, boolean values, and symbols.
scm> 1234 ; integer
1234
scm> 123.4 ; real number
123.4
scm> #f ; the Scheme equivalent of False in Python
#f
A Scheme symbol is equivalent to a Python name. A symbol evaluates to the value bound to that symbol in the current environment. (They are called symbols rather than names because they include +
and other arithmetic symbols.)
scm> quotient ; A symbol bound to a built-in procedure
#[quotient]
scm> + ; A symbol bound to a built-in procedure
#[+]
In Scheme, all values except #f
(equivalent to False
in Python) are true
values (unlike Python, which has other false values, such as 0
).
scm> #t
#t
scm> #f
#f
Scheme uses Polish prefix notation, in which the operator expression comes before
the operand expressions. For example, to evaluate 3 * (4 + 2)
, we write:
scm> (* 3 (+ 4 2))
18
Just like in Python, to evaluate a call expression:
- 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
Define:
The define
form is used to assign values to symbols. It has the following syntax:
(define <symbol> <expression>)
scm> (define pi (+ 3 0.14))
pi
scm> pi
3.14
To evaluate the define
expression:
- Evaluate the final sub-expression (
<expression>
), which in this case evaluates to3.14
. - Bind that value to the symbol (
symbol
), which in this case ispi
. - Return the symbol.
The define
form can also define new procedures, described in the "Defining Functions" section.
If Expressions:
The if
special form evaluates one of two expressions based on a predicate.
(if <predicate> <if-true> <if-false>)
The rules for evaluating an if
special form expression are as follows:
- Evaluate the
<predicate>
. - If the
<predicate>
evaluates to a true value (anything but#f
), evaluate and return the value of the<if-true>
expression. Otherwise, evaluate and return the value of the<if-false>
expression.
For example, this expression does not error and evaluates to 5, even though the
sub-expression (/ 1 (- x 3))
would error if evaluated.
scm> (define x 3)
x
scm> (if (> (- x 3) 0) (/ 1 (- x 3)) (+ x 2))
5
The <if-false>
expression is optional.
scm> (if (= x 3) (print x))
3
Let's compare a Scheme if
expression with a Python if
statement:
- In Scheme:
(if (> x 3) 1 2)
- In Python:
if x > 3:
1
else:
2
The Scheme if
expression evaluates to a number (either 1 or 2, depending on
x
). The Python statement does not evaluate to anything, and so the 1 and 2
cannot be used or accessed.
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 in each of the <if-true>
and
<if-false>
positions.
One final difference is that in Scheme, you cannot write elif
clauses.
Cond Expressions:
The cond
special form can include multiple predicates (like if/elif in Python):
(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 is optional; its <else-expression>
is the return expression if none of
the predicates are true.
The rules of evaluation are as follows:
- Evaluate the predicates
<p1>
,<p2>
, ...,<pn>
in order until one evaluates to a true value (anything but#f
). - Evalaute and return the value of the return expression corresponding to the first predicate expression with a true value.
- If none of the predicates evaluate to true values and there is an
else
clause, evaluate and return<else-expression>
.
For example, this cond
expression returns the nearest multiple of 3 to x
:
scm> (define x 5)
x
scm> (cond ((= (modulo x 3) 0) x)
((= (modulo x 3) 1) (- x 1))
((= (modulo x 3) 2) (+ x 1)))
6
Lambdas:
The lambda
special form creates a procedure.
(lambda (<param1> <param2> ...) <body>)
This expression will create and return a procedure with the given formal
parameters and body, similar to a lambda
expression in Python.
scm> (lambda (x y) (+ x y)) ; Returns a lambda procedure, 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 procedure in one line
7
Here are equivalent expressions in Python:
>>> lambda x, y: x + y
<function <lambda> at ...>
>>> (lambda x, y: x + y)(3, 4)
7
The <body>
may contain multiple expressions. A scheme procedure returns the
value of the last expression in its body.
The define
form can create a procedure and give it a name:
(define (<symbol> <param1> <param2> ...) <body>)
For example, this is how we would define the double
procedure:
scm> (define (double x) (* x 2))
double
scm> (double 3)
6
Here's an example with three arguments:
scm> (define (add-then-mul x y z)
(* (+ x y) z))
scm> (add-then-mul 3 4 5)
35
When a define
expression is evaluated, the following occurs:
- Create a procedure with the given parameters and
<body>
. - Bind the procedure to the
<symbol>
in the current frame. - Return the
<symbol>
.
The following two expressions are equivalent:
scm> (define add (lambda (x y) (+ x y)))
add
scm> (define (add x y) (+ x y))
add
All non-primitive expressions in Scheme are known as combinations and have the following syntax:
(<operator> <operand1> <operand2> ...)
Combinations are expressions that combine multiple expressions. Here,
<operator>
, <operand1>
, and <operand2>
. are all expressions. The number
of operands depends on the operator. There are two types of combinations:
- A call expression, whose operator evaluates to a procedure
- A special form expression, whose operator is a special form
Scheme Basics
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: Over or Under
Define a procedure over-or-under
which takes in a number num1
and a number num2
and returns the following:
- -1 if
num1
is less thannum2
- 0 if
num1
is equal tonum2
- 1 if
num1
is greater thannum2
NOTE. Remember that every parenthesis in Scheme makes a function call. For example, just typing
0
in the Scheme interpeter will return0
. However, typing(0)
will cause an Error because0
is not a function.Challenge: Implement this in 2 different ways using
if
andcond
!
(define (over-or-under num1 num2)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q over_or_under
Q3: 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.Note:
define
doesn't return the function, butlambda
does.Hint: 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
Q4: 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
.
NOTE. Remember to use Scheme syntax when calling functions. That is, in the form of
(func arg)
, notfunc(arg)
.
(define (composed f g)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q composed
Q5: Repeat
Write the procedure repeat
, which takes in a procedure f
and a number n
, and outputs a new procedure. This new procedure takes in a number x
and outputs the result of applying f
to x
a total of n
times. For example:
scm> (define (square x) (* x x))
square
scm> ((repeat square 2) 5) ; (square (square 5))
625
scm> ((repeat square 3) 3) ; (square (square (square 3)))
6561
scm> ((repeat square 1) 7) ; (square 7)
49
Hint: The
composed
function you wrote in the previous problem might be useful.
(define (repeat f n)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q repeat
Q6: Greatest Common Divisor
The GCD is the the greatest common divisor of two positive integers.
Write the procedure gcd
, which computes the GCD of numbers a
and b
using
Euclid's algorithm, which uses the fact that the GCD of two values is either of
the following:
- the smaller value if it evenly divides the larger value, or
- the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value
In other words, if a
is greater than b
and a
is not divisible by
b
, then
gcd(a, b) = gcd(b, a % b)
You may find the provided procedures
min
andmax
helpful. You can also use the built-inmodulo
andzero?
procedures.scm> (modulo 10 4) 2 scm> (zero? (- 3 3)) #t scm> (zero? 3) #f
(define (max a b) (if (> a b) a b))
(define (min a b) (if (> a b) b a))
(define (gcd a b)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q gcd
Scheme Lists
Q7: List Duplicator
Write a Scheme function, duplicate
that, when given a list, such as (1 2 3 4)
,
duplicates every element in the list (i.e. (1 1 2 2 3 3 4 4)
).
(define (duplicate lst)
'YOUR-CODE-HERE
)
(expect (duplicate '(1 2 3)) (1 1 2 2 3 3))
(expect (duplicate '(1 1)) (1 1 1 1))
Use Ok to test your code:
python3 ok -q list_duplicate
Q8: Deep Map
Write the function deep-map
, which takes a function fn
and a nested list
s
. A nested list is a list where each element is either a number or a list
(e.g. (1 (2) 3)
where 1
, (2)
, and 3
are the elements). It returns a list
with identical structure to s
, but replacing each non-list element by the
result of applying fn
on it, even for elements within sub-lists. For example:
scm> (define (double x) (* 2 x))
double
scm> (deep-map double '(2 (3 4)))
(4 (6 8))
Assume that the input has no dotted (malformed) lists.
Hint: You can use the function
list?
, which checks if a value is a list.
(define (deep-map fn s)
'YOUR-CODE-HERE
)
Use Ok to test your code:
python3 ok -q deep-map
Check Your Score Locally
You can locally check your score on each question of this assignment by running
python3 ok --score
This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.
Submit Assignment
Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.
In addition, all students who are not in the mega lab must submit the attendance form for credit. Ask your section TA for the link! Submit this form for each section, whether you attended lab or missed it for a good reason. The attendance form is not required for mega section students.