Lab 7: Scheme Basics
Due at 11:59pm on Friday, 07/13/2018.
Starter Files
Download lab07.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.
- Questions 1-3 must be completed in order to receive credit for this lab.
Starter code for problems 1-3 is in
lab07.scm
. - Questions 4-6 are optional. Starter code for these problems can be found in
lab07_extra.scm
. 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!
Atomic 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.5
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; an 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
Combinations
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
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 form expressions
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 |
---|---|
|
|
lambda
expressions
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 return
statement in Scheme. The function will simply return the value of the last
expression in the body.
define
expressions
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.
Required Questions
What Would Scheme Display?
Q1: 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)
______6
scm> (* 7 6)
______42
scm> (+ 1 2 3 4)
______10
scm> (/ 8 2 2)
______2
scm> (quotient 29 5)
______5
scm> (modulo 29 5)
______4
scm> (= 1 3) ; Scheme uses '=' instead of '==' for comparison
______#f
scm> (< 1 3)
______#t
scm> (or #t #f) ; or special form short circuits
______#t
scm> (and #t #f (/ 1 0))
______#f
scm> (not #t)
______#f
scm> (define x 3)
______x
scm> x
______3
scm> (define y (+ x 4))
______y
scm> y
______7
scm> (define x (lambda (y) (* y 2)))
______x
scm> (x y)
______14
scm> (if (print 1) (print 2) (print 3))
______1
2
scm> (* (if (> 3 2) 1 2) (+ 4 5))
______9
scm> (define foo (lambda (x y z) (if x y z)))
______foo
scm> (foo 1 2 (print 'hi))
______hi
2
scm> ((lambda (a) (print 'a)) 100)
______a
Coding Questions
Q2: Over or Under
Define a procedure over-or-under
which takes in a number x
and a number y
and returns the following:
- -1 if
x
is less thany
- 0 if
x
is equal toy
- 1 if
x
is greater thany
(define (over-or-under x y)
'YOUR-CODE-HERE
(cond
((< x y) -1)
((= x y) 0)
(else 1))
Video walkthrough: https://youtu.be/UJ37SCaM3cQ?t=35m46s)
;;; 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: 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))
Video walkthrough: https://youtu.be/UJ37SCaM3cQ?t=47m4s)
;;; 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
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
.
(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
Q5: Intersect
Implement intersect
, which takes two single-argument procedures f1
and f2
and returns a procedure that takes one argument x
. This returned procedure
will return #t
if f1
and f2
return equal values when called on argument
x
and #f
otherwise.
Assume that the input procedures f1
and f2
always take and return numbers.
Test for equality using the =
procedure.
(define (intersect f1 f2)
'YOUR-CODE-HERE
(lambda (x) (= (f1 x) (f2 x))))
;;; Tests
; (add-two 2) evaluates to 4, (square 2) also evaluates to 4
((intersect add-two square) 2)
; expect #t
; (add-two 3) evaluates to 5, (square 3) instead evaluates to 9
((intersect add-two square) 3)
; expect #f
((intersect (lambda (x) (* 5 x)) square) 5)
; expect #t
((intersect (lambda (x) x) square) 1)
; expect #t
((intersect square (lambda (x) x)) 1)
; expect #t
((intersect (lambda (x) x) square) 5)
; expect #t
((intersect (lambda (x) (/ x 1)) (lambda (x) x)) -1)
; expect #t
Use Ok to unlock and test your code:
python3 ok -q intersect -u
python3 ok -q intersect
Q6: Greatest Common Divisor
Let's revisit a familiar problem: finding the greatest common divisor of two numbers. We examined this problem in Python in Lab 3, so you can take a look to see how we've approached this problem before.
Write the procedure gcd
, which computes the GCD of numbers a
and b
.
Recall that Euclid's Algorithm tells us 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
(cond ((zero? a) b)
((zero? b) a)
((= (remainder (max a b) (min a b)) 0) (min a b))
(else (gcd (min a b) (remainder (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