Due at 11:59pm on 7/26/2016.

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.

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.

  • To receive credit for this lab, you must complete Question 1 and Questions 2 through 4 in lab10.scm and submit through OK.
  • Questions 5 through 10 are extra practice. They can be found in the lab10_extra.scm file. It is recommended that you complete these problems on your own time.

Helpful Hints

OK has a new feature for the "What would Python display?" questions. As you go through the question's prompts OK may give you a hint based on your wrong answers. Our hope is these hints will help remind you of something important or push you in the right direction to getting the correct answer. For example:

Foo > Suite 1 > Case 1
(cases remaining: 1)

What would Python display? If you get stuck, try it out in the Python
interpreter!

>>> not False or False
? False

-- Helpful Hint --
What about the | not |?
------------------

-- Not quite. Try again! --

? 

Topics

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, type python3 scheme -i <file.scm>. To exit the Scheme interpreter, type (exit).

One of the TA's, Jack Thakar, has written an online Scheme interpreter that can also draw environment diagrams and box-and-pointer diagrams, or debug your code by step-by-step. It's available at scheme.cs61a.org. Don't forget to submit your code through OK though!

Control Structures

If Expressions

Let's introduce control expressions to allow our procedures to do more complex operations! The if-expression has the following format:

(if <condition>
    <true_result>
    <false_result>)

For example, the following code written in Scheme and Python are equivalent:

Scheme Python
scm> (if (> x 3)
         1
         2)
>>> if x > 3:
...     return 1
... else:
...     return 2

In Scheme, you cannot write elif cases. If want to have multiple cases with the if-expression, you would need multiple branched if-expressions:

Scheme Python
scm> (if (< x 0)
         'negative       ; returns the symbol negative
         (if (= x 0)
             'zero       ; returns the symbol zero
             'positive   ; returns the symbol positive
         )
 )
>>> if x < 0:
...     print('negative')
... else:
...     if x == 0:
...         print('zero')
...     else:
...         print('positive')

Cond Expressions

Using nested if-expression 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 conditional expression in Python.

(cond
    (<p1> <e1>)
    (<p2> <e2>)
    ...
    (<pn> <en>)
    (else <else-expression>))

It consists of the symbol cond followed by pairs of expressions enclosed in parentheses (<p> <e>) called clauses. The first expression in each pair is a predicate: an expression whose value is interpreted as either True or False. The second expression is the return expression corresponding to its predicate.

The following code is equivalent:

Scheme Python
scm> (cond
        ((> x 0) 'positive)
        ((< x 0) 'negative)
        (else 'zero))
>>> if x > 0:
...     print('positive')
... elif x < 0:
...     print('negative')
... else:
...     print('zero')

Lists

Scheme Pairs

Scheme lists are very similar to the linked lists we've been working with in Python. Scheme lists are made up of pairs, which can point to two objects. To create a pair, we use the cons procedure, which takes in two arguments:

scm> (define a (cons 3 5))
a
scm> a
(3 . 5)

We can use the car and cdr procedures to retrieve the first and second elements in the pair, respectively.

scm> (car a)
3
scm> (cdr a)
5

Just like linked lists in Python, lists in Scheme are formed by having the first element of a pair be the first element of the list, and the second element of the pair point to another pair containing the rest of the list. The second element of a pair can be nil to signify the end of the list. For example, the sequence (1 2 3) can be represented in Scheme with the following line:

scm> (cons 1 (cons 2 (cons 3 nil)))

which creates the following object in Scheme:

linked list

We can then of course retrieve values from our list with the car and cdr procedures. (Curious about where these weird names come from? Check out their etymology.)

scm> a
(1 2 3)
scm> (car a)
1
scm> (cdr a)
(2 3)
scm> (car (cdr (cdr a)))
3

list

There are a few other ways to create lists. We can pass a sequence of arguments into the list procedure, which quickly constructs a well-formed list (one in which the cdr of every pair is either another pair or nil):

scm> (list 1 2 3)
(1 2 3)

Quote Form

We can also use the quote form to create a list, which performs much the same functionality as the list procedure. Unlike list, we can use the quote form to construct a malformed list. Notice that we can use a dot to separate the car and the cdr of a pair, but Scheme will only show us the dot if the list is malformed:

scm> '(1 2 3)
(1 2 3)
scm> '(1 . (2 . (3)))
(1 2 3)
scm> '(1 . (2 . 3))
(1 2 . 3)

Built-In Procedures for Lists

There are a few other built-in procedures in Scheme that are used for lists. Try them out!

scm> (null? nil)
______
True
scm> (append '(1 2 3) '(4 5 6))
______
(1 2 3 4 5 6)
scm> (cons '(1 2 3) '(4 5 6))
______
((1 2 3) 4 5 6)
scm> (list '(1 2 3) '(4 5 6))
______
((1 2 3) (4 5 6))
scm> (length '(1 2 3 4 5))
______
5

Lambdas

Ah yes, you thought you were safe, but we can also write lambda procedures in Scheme!

As noted above, the syntax for defining a procedure in Scheme is:

(define (<name> <params>)
        <body>
)

Defining a lambda has a slightly different syntax, as follows:

(lambda (<params>)
        <body>
)

Notice how the only difference is the lack of procedure name. You can create and call a lambda procedure in Scheme as follows:

; defining a lambda
(lambda (x) (+ x 3))
; calling a lambda
((lambda (x) (+ x 3)) 7)

Required Questions

What Would Scheme Display?

Question 1: WWSD: Lists

Use OK to test your knowledge with the following "What Would Scheme Display?" questions:

python3 ok -q wwsp-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 notation rule
______
(2 3)
scm> (equal? '(1 . (2 . 3)) (cons 1 (cons 2 (cons 3 nil))))
______
False
scm> (list 1 2 3)
______
(1 2 3)
scm> (equal? '(1 . (2 . 3)) (list 1 (cons 2 3)))
______
False
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)))
______
True
scm> '(cons 4 (cons (cons 6 8) ()))
______
(cons 4 (cons (cons 6 8) ()))

Coding Questions

Question 2: 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 than y
  • return 0 if x is equal to y
  • return 1 if x is greater than y
(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

Question 3: 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.

(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

Question 4: 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 lab10_extra.scm file. It is recommended that you complete these problems on your own time.

Question 5

Implement a procedure pow for raising the number b to the power of integer n that runs in Θ(log n) time.

Hint: Consider the following observations:

  1. b2k = (bk)2
  2. b2k+1 = b(bk)2

You may use the built-in predicates even? and odd?.

(define (square x) (* x x))

(define (pow b n)
'YOUR-CODE-HERE
(cond ((= n 0) 1) ((even? n) (square (pow b (/ n 2)))) (else (* b (pow b (- n 1)))))
)

Use OK to unlock and test your code:

python3 ok -q pow -u
python3 ok -q pow

Question 6: Make a List

Create the list with the following box-and-pointer diagram:

linked list

(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

Question 7: 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

Question 8: 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 consists 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

Question 9: 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) (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

Question 10: 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 implement the filter procedure, which takes in a predicate and a list and returns a new list containing only elements of the list that satisfy the predicate.

(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

Question 11

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.

(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))))
)

Use OK to unlock and test your code:

python3 ok -q substitute -u
python3 ok -q substitute

Question 12

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.

(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)))
)

Use OK to unlock and test your code:

python3 ok -q sub-all -u
python3 ok -q sub-all