Lab 09: Scheme
Due at 11:59pm on Friday, 03/23/2018.
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.
Submission
By the end of this lab, you should have submitted the lab with
python3 ok --submit
. You may submit more than once before the
deadline; only the final submission will be graded.
Check that you have successfully submitted your code on
okpy.org.
- To receive credit for this lab, you must complete Question 1 through 4 in lab09.scm and submit through Ok.
- Questions 5 through 11 are extra practice. They can be found in the lab09_extra.scm file. It is recommended that you complete these problems on your own time.
Topics
Note: We're diving into a new programming language today! As such, the Topics section is lengthier than usual and covers a lot of fundamentals that will help you build a good foundation for understanding the Scheme material in this course. We recommend that you thoroughly read this section before beginning the problems.
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)
.
You may find it useful to try scheme.cs61a.org 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!
Expressions
Primitives
Just like in Python, primitive, or atomic, expressions in Scheme take a single step to evaluate. These include numbers, booleans, names, and 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 string, but not exactly. For now, just be aware that you can represent a string of valid Scheme characters as a symbol.
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> 1234 ; integer
1234
scm> 123.4 ; real number
123.5
scm> true ; alias for built-in true value
#t
scm> 'a ; symbol
a
scm> 'hello-world!
hello-world!
Call expressions
All expressions that aren't atomic expressions are either call expressions or special forms. Both are written as Scheme lists. A call expression has the following syntax:
(<operator> <operand1> <operand2> ...)
Like Python, the operator 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 mathematical operators:
scm> (+ 1 2)
3
scm> (* 3 4)
12
scm> (- 10 (/ 6 2))
7
Special forms
A special form in Scheme has the exact same syntax as a call expression:
(<special-form> <operand1> <operand2> ...)
What makes them "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
In Scheme, an if
expression is a special form with the following syntax:
(if <condition> <true-result> <false-result>)
Note the similar syntax to a call expression: the if
keyword precedes the 3
operands in a space separated list. The rules for evaluating the if
special
form are as follows:
- Evaluate
<condition>
. - If
<condition>
evaluates to a truth-y value, the wholeif
expression evaluates to the value of<true-result>
. Otherwise, it evaluates to the value of<false-result>
.
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.
The following blocks of code written in Scheme and Python are roughly equivalent:
Scheme | Python |
---|---|
|
|
The reason these blocks of code are not exactly equivalent is that a Scheme
if
expression actually evaluates to a value whereas a Python if
statement
simply directs the flow of the program. In this case, the Scheme code actually
evaluates to 1
or 2
, while the Python code just prints the values.
Moreover, it's possible to add even more lines of code into the suites of the
Python if
statement besides the print statements, while a Scheme if
expression expects just a single expression for each of the true result and the
false result.
Another 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 -- an expression whose
value is interpreted as either True
or False
. 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. - The
cond
expression evaluates to the value of the<ei>
corresponding to the first true<pi>
expression. - 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 |
---|---|
|
|
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.)
Pairs
A pair is a built-in data type in Scheme that holds two values. To create a
pair, use the cons
procedure, which takes in two arguments:
scm> (cons 3 5)
(3 . 5)
Elements in a pair are displayed as separated by a dot. We can use the car
and cdr
procedures to retrieve the first and second elements in the pair,
respectively.
scm> (car (cons 3 5))
3
scm> (cdr (cons 3 5))
5
It's possible to nest cons
calls such that an element within a pair is
another pair!
scm> (cons (cons 1 2) 3)
((1 . 2) . 3)
scm> (cons 1 (cons 2 3))
(1 2 . 3)
You may be wondering why the first dot disappeared in the value of the second
expression (i.e., why isn't it displayed as (1 . (2 . 3))
?). This is because
when Scheme sees a dot followed by an open parenthesis, it will remove the dot,
the open parenthesis, and the corresponding close parenthesis:
(a . ( ... )) -> (a ...)
Read on to find out how to make a list without any dots!
Well-formed 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.
A well-formed Scheme list is a list in which the cdr
is either another
well-formed list or nil
, an empty list. A well-formed list is displayed in
the interpreter with no dots. To understand this, first observe the following
pair construction:
scm> (cons 1 (cons 2 3))
(1 2 . 3)
This is what's known as a malformed list, one where the cdr
is not either a
well-formed list or nil
. Note that you can still see the dot. Now, take a
look at this pair construction:
scm> (cons 1 (cons 2 (cons 3 nil)))
(1 2 3)
Here, we've created a well-formed list by ensuring that the second argument
of each cons
expression is another cons
expression or nil
. Yay, no more
dots! Here is the box-and-pointer diagram for this list:
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
scm> a
(1 2 3)
scm> (car a)
1
scm> (cdr a)
(2 3)
scm> (car (cdr (cdr a)))
3
list
Procedure
There are a few other ways to create lists. The list
procedure takes in an
arbitrary number of arguments and constructs a well-formed 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 2) 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> '(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))
scm> '(1 . (2 3 4)) ; Removes dot/parentheses when possible
(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 list is empty
______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
Defining procedures
To define procedures, we use the special form define
, which has the following
syntax:
(define (<name> <param1> <param2> ...)
<body>
)
This expression defines a function with the given parameters and body and assigns it to the given name in the current environment.
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 return the value of the last expression
in the body.
This expression 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.
Lambdas
Ah yes, you thought you were safe, but we can also write lambda procedures in
Scheme! A lambda
expression has the following syntax:
(lambda (<param1> <param2> ...) <body>)
Notice how the only difference between this expression and a define
expression is the lack of procedure name. This expression will create and
return a function, but will not alter the current environment. This is very
similar to the difference between a def
statement and 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
Required Questions
What Would Scheme Display?
Q1: 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 2)
______(1 . 2)
scm> (cons 1 (cons 2 nil))
______(1 2)
scm> (car (cons 1 (cons 2 nil)))
______1
scm> (cdr (cons 1 (cons 2 nil)))
______(2)
scm> (list 1 2 3)
______(1 2 3)
scm> (list 1 (cons 2 3))
______(1 (2 . 3))
scm> '(1 2 3)
______(1 2 3)
scm> '(2 . 3)
______(2 . 3)
scm> '(2 . (3)) ; Recall dot rule for pairs
______(2 3)
scm> (equal? '(1 . (2 . 3)) (cons 1 (cons 2 (cons 3 nil)))) ; Recall how boolean values are displayed
______#f
scm> (equal? '(1 . (2 . 3)) (cons 1 (cons 2 3)))
______#t
scm> (equal? '(1 . (2 . 3)) (list 1 (cons 2 3)))
______#f
scm> (cons 1 '(list 2 3)) ; Recall quoting
______(1 list 2 3)
scm> (cons (list 2 (cons 3 4)) nil)
______((2 (3 . 4)))
scm> (car (cdr '(127 . ((131 . (137))))))
______(131 137)
scm> (equal? '(1 . ((2 . 3))) (cons 1 (cons (cons 2 3) nil)))
______#t
scm> '(cons 4 (cons (cons 6 8) ()))
______(cons 4 (cons (cons 6 8) ()))
Coding Questions
Q2: Over or Under
Define a procedure over-or-under
which takes in an x
and a y
and
returns the the following:
- return -1 if
x
is less thany
- return 0 if
x
is equal toy
- return 1 if
x
is greater thany
(define (over-or-under x y)
'YOUR-CODE-HERE
(cond
((< x y) -1)
((= x y) 0)
(else 1)))
;;; Tests
(over-or-under 1 2)
; expect -1
(over-or-under 2 1)
; expect 1
(over-or-under 1 1)
; expect 0
Use Ok to unlock and test your code:
python3 ok -q over-or-under -u
python3 ok -q over-or-under
Q3: Filter
Write a procedure filter
, which takes a predicate f
and a list lst
, 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.
(define (filter f lst)
'YOUR-CODE-HERE
(cond ((null? lst) '())
((f (car lst)) (cons (car lst) (filter f (cdr lst))))
(else (filter f (cdr lst)))))
;;; Tests
(define (even? x)
(= (modulo x 2) 0))
(filter even? '(0 1 1 2 3 5 8))
; expect (0 2 8)
Use Ok to unlock and test your code:
python3 ok -q filter -u
python3 ok -q filter
Q4: 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 x
and returns the result of x + num
.
(define (make-adder num)
'YOUR-CODE-HERE
(lambda (x) (+ x num)))
;;; Tests
(define adder (make-adder 5))
(adder 8)
; expect 13
Use Ok to unlock and test your code:
python3 ok -q make-adder -u
python3 ok -q make-adder
Optional Questions
The following questions are for extra practice -- they can be found in the the lab09_extra.scm file. It is recommended that you complete these problems on your own time.
Q5: Make a List
Create the list with the following box-and-pointer diagram:
(define lst
'YOUR-CODE-HERE
(cons (cons 1 '())
(cons 2
(cons (cons 3 4)
(cons 5 '())))))
Use Ok to unlock and test your code:
python3 ok -q make-list -u
python3 ok -q make-list
Q6: 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
(lambda (x) (f (g x))))
Use Ok to unlock and test your code:
python3 ok -q composed -u
python3 ok -q composed
Q7: Remove
Implement a procedure remove
that takes in a list and returns a new list with
all instances of item
removed from lst
. You may assume the list will only
consist of numbers and will not have nested lists.
Hint: You might find the filter
procedure useful.
(define (remove item lst)
'YOUR-CODE-HERE
(cond ((null? lst) '())
((equal? item (car lst)) (remove item (cdr lst)))
(else (cons (car lst) (remove item (cdr lst))))))
(define (remove item lst)
(filter (lambda (x) (not (= x item))) lst))
;;; Tests
(remove 3 nil)
; expect ()
(remove 3 '(1 3 5))
; expect (1 5)
(remove 5 '(5 3 5 5 1 4 5 4))
; expect (3 1 4 4)
Use Ok to unlock and test your code:
python3 ok -q remove -u
python3 ok -q remove
Q8: Greatest Common Divisor
Let's revisit a familiar problem: finding the greatest common divisor of two numbers.
Write the procedure gcd
, which computes the gcd of numbers a
and b
.
Recall that the greatest common divisor of two positive integers a
and b
is the largest integer which evenly divides both numbers (with no remainder).
Euclid's
algorithm states
that the greatest common divisor is
- 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
and max
helpful. You can
also use the built-in modulo
procedure.
(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
(cond ((zero? a) b)
((zero? b) a)
((= (modulo (max a b) (min a b)) 0) (min a b))
(else (gcd (min a b) (modulo (max a b) (min a b))))))
;;; Tests
(gcd 24 60)
; expect 12
(gcd 1071 462)
; expect 21
Use Ok to unlock and test your code:
python3 ok -q gcd -u
python3 ok -q gcd
Q9: No Repeats
Implement no-repeats
, which takes a list of numbers s
as input and returns
a list that has all of the unique elements of s
in the order that they first
appear, but no repeats. For example, (no-repeats (list 5 4 5 4 2 2))
evaluates to (5 4 2)
.
Hints: To test if two numbers are equal, use the =
procedure. To test if
two numbers are not equal, use the not
procedure in combination with =
.
You may find it helpful to use the filter
procedure.
(define (no-repeats s)
'YOUR-CODE-HERE
(if (null? s) s
(cons (car s)
(no-repeats (filter (lambda (x) (not (= (car s) x))) (cdr s))))))
Use Ok to unlock and test your code:
python3 ok -q no-repeats -u
python3 ok -q no-repeats
Q10: Substitute
Write a procedure substitute
that takes three arguments: a list s
, an old
word, and a new
word. It returns a list with the elements of s
, but with
every occurrence of old
replaced by new
, even within sub-lists.
Hint: The built-in pair?
predicate returns True if its argument is a cons
pair.
Hint: The =
operator will only let you compare numbers, but using equal?
or eq?
will let you compare symbols as well as numbers. For more information,
check out the
Scheme Primitives Reference.
Use Ok to unlock and test your code:
python3 ok -q substitute -u
python3 ok -q substitute
(define (substitute s old new)
'YOUR-CODE-HERE
(cond ((null? s) nil)
((pair? (car s)) (cons (substitute (car s) old new)
(substitute (cdr s) old new)))
((equal? (car s) old) (cons new
(substitute (cdr s) old new)))
(else (cons (car s) (substitute (cdr s) old new)))))
Remember that we want to use equal?
to compare symbols since =
will only
work for numbers!
If the input list is empty, there's nothing to substitute. That's a pretty straightforward base case. Otherwise, our list has at least one item.
We can break the rest of this problem into roughly two big cases:
Nested list here
This means that (car s)
is a pair. Since you can assume that the list is
well-formed, (list? (car s))
is also an adequate check. In this case, we have
to dig deeper and recurse on (car s)
since there could be symbols to replace
in there. We must recurse on (cdr s)
as well to handle the rest of the list.
No nested list here
This is the case if (car s)
is not a pair. Of course, there could still be
nesting later on in the list, but we'll rely on our recursive call to handle
that.
If (car s)
matches old
, we'll make sure to use new
in its place.
Otherwise, we'll use (car s)
without replacing it. In both cases, we must
recurse on the rest of the list.
Video walkthrough: https://youtu.be/LAr-_twxXao
Q11: Sub All
Write sub-all
, which takes a list s
, a list of old
words, and a
list of new
words; the last two lists must be the same length. It returns a
list with the elements of s
, but with each word that occurs in the second
argument replaced by the corresponding word of the third argument. You may use
substitute
in your solution.
(define (sub-all s olds news)
'YOUR-CODE-HERE
(if (null? olds)
s
(sub-all (substitute s (car olds) (car news))
(cdr olds)
(cdr news))))
Solving sub-all
means just repeatedly doing the substitute operation we wrote
earlier. If this were Python, we might iterate over the list of olds and news,
calling substitute
and saving the result for the next call. For example, it
might look something like this:
def sub_all(s, olds, news):
for o, n in zip(olds, news):
s = substitute(s, o, n)
return s
If that approach makes sense, then the only tricky part now is to translate that
logic into Scheme. Since we don't have access to iteration, we have to reflect
our progress in our recursive call to sub-all
. This means shortening the list
of olds
and news
, and most importantly, feeding the result of substitute
into the next call.
Therefore, the base case is if we have nothing we want to replace in olds
.
Checking if news
is empty would also be ok, since olds
and news
should be
the same length.
What doesn't work, however, is checking if s
is an empty list. While this
won't make your solution wrong on its own, it's an insufficient base case.
Remember that we're passing in s
with elements replaced into the recursive
call, which means it won't become any shorter.
Video walkthrough: https://youtu.be/avYPLlaBtj0
Use Ok to unlock and test your code:
python3 ok -q sub-all -u
python3 ok -q sub-all