Due by 11:59pm on Friday, 7/28

Instructions

Submission: When you are done, submit with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on okpy.org. See Lab 0 for more instructions on submitting assignments.

Using OK: If you have any questions about using OK, please refer to this guide.

Readings: You might find the following references useful:

Homework Questions

Scheme

Question 1

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively:

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)
  'YOUR-CODE-HERE
  nil
)

(define (caddr s)
  'YOUR-CODE-HERE
  nil
)

Use OK to unlock and test your code:

python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr

Conditional expressions

The cond special form is a general conditional expression, similar to a multi-clause conditional statement in Python. The general form of a conditional expression is:

(cond
    (<p1> <el1>)
    (<p2> <el2>)
    ...
    (<pn> <eln>)
    (else <else-expressions>))

consisting of the symbol cond followed by sequences of expressions (<p> <el>) called clauses. The first expression in each pair is a predicate: an expression whose value is interpreted as either being true or false. In Scheme, all values except the special boolean value #f are interpreted as true values (unlike Python). (Our particular version of the Scheme interpreter allows you to write True and False in place of #t and #f, and prints boolean values as True and False. This is not standard.)

Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is #f, then <p2> is evaluated. If <p2>'s value is also #f, then <p3> is evaluated. This process continues until the first predicate <pi> is found whose value is true, in which case the interpreter returns the result of evaluating each of the corresponding list of consequent expressions <eli> and returning the last value as the value of the whole conditional expression. The else keyword, if present, is taken to be true, so that if none of the <p>'s is found to be true, the interpreter evaluates the else-expressions and returns the last value. If no clause has a true predicate, the result is an "unspecified value". Unless some of the consequent expressions have side-effects, there is no point in having more than one in a list <eli>.

This is a somewhat simplified version of the semantics of cond, covering the cases we usually encounter.

Question 2

Using cond, define a procedure sign that returns -1 for negative arguments, 0 for zero, and 1 for positive arguments:

(define (sign x)
  'YOUR-CODE-HERE
  nil
)

Use OK to unlock and test your code:

python3 ok -q sign -u
python3 ok -q sign

Question 3

Implement a procedure called ordered?, which takes a list of numbers and returns True if the numbers are in nondescending order, and False otherwise.

Hint: The built-in null? function returns whether its argument is nil.

(define (ordered? s)
  'YOUR-CODE-HERE
  nil
)

Use OK to unlock and test your code:

python3 ok -q ordered -u
python3 ok -q ordered

Question 4

Implement the procedure nodots, which takes a nested list of numbers that may not be well-formed and returns a nested list with the same content and structure, but which does not have any dots when displayed. Lists are not well-formed if they do not properly terminate in a null list. In such cases, the list will print with a dot before the final item to indicate that its last two items are contained in a single pair. For example,

(cons 1 (cons 2 3))

would print as

(1 2 . 3)

for which nodots should substitute

(1 2 3)

You may find the built-in null? and pair? predicates useful.

(define (nodots s)
  'YOUR-CODE-HERE
  nil
)

Use OK to unlock and test your code:

python3 ok -q nodots -u
python3 ok -q nodots

Sets as Ordered Lists

One way to represent a set is by using an ordered list, where the ordering is used to speed up search (although only by a constant factor). The following few questions explore this idea, assuming a "set" is a Scheme list with no repeated elements that is already ordered from least to greatest.

Question 5

Define contains?, which returns whether a set s contains value v. The Python implementation of this procedure is provided for your reference.

; Sets as sorted lists

(define (empty? s) (null? s))

(define (contains? s v)
    (cond ((empty? s) false)
          'YOUR-CODE-HERE
          (else nil) ; replace this line
          ))

; Equivalent Python code, for your reference:
;
; def empty(s):
;     return s is Link.empty
;
; def contains(s, v):
;     if empty(s):
;         return False
;     elif s.first > v:
;         return False
;     elif s.first == v:
;         return True
;     else:
;         return contains(s.rest, v)

Use OK to unlock and test your code:

python3 ok -q contains -u
python3 ok -q contains

Question 6

Define add, which takes a set s and a value v as arguments. It returns a representation of a set containing the values in s and the value v. There should be no repeated elements in the return value.

(define (add s v)
    (cond ((empty? s) (list v))
          'YOUR-CODE-HERE
          (else nil) ; replace this line
          ))

Use OK to unlock and test your code:

python3 ok -q add -u
python3 ok -q add

Question 7

Define intersect, which returns a set containing only values that appear in both sets s and t. Your implementation should run in linear time in the length of the input sets. A Python implementation of this procedure is provided for your reference.

Also, define union, which returns a set containing all values that appear in either set s or t.

(define (intersect s t)
    (cond ((or (empty? s) (empty? t)) nil)
          'YOUR-CODE-HERE
          (else nil) ; replace this line
          ))

; Equivalent Python code, for your reference:
;
; def intersect(set1, set2):
;     if empty(set1) or empty(set2):
;         return Link.empty
;     else:
;         e1, e2 = set1.first, set2.first
;         if e1 == e2:
;             return Link(e1, intersect(set1.rest, set2.rest))
;         elif e1 < e2:
;             return intersect(set1.rest, set2)
;         elif e2 < e1:
;             return intersect(set1, set2.rest)

(define (union s t)
    (cond ((empty? s) t)
          ((empty? t) s)
          'YOUR-CODE-HERE
          (else nil) ; replace this line
          ))

Use OK to unlock and test your code:

python3 ok -q intersect -u
python3 ok -q intersect
python3 ok -q union -u
python3 ok -q union

Tail-Calls in Scheme

Recall from lecture that Scheme supports tail-call optimization. The example we used was factorial (shown in both Python and Scheme):

# Python
def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

# Scheme
(define (fact n)
    (if (= n 0)
        1
        (* n (fact (- n 1)))))

Notice that in this version of factorial, the return expressions both use recursive calls, and then use the values for more "work." In other words, the current frame needs to sit around, waiting for the recursive call to return with a value. Then the current frame can use that value to calculate the final answer.

As an example, consider a call to fact(5) (Shown with Scheme below). We make a new frame for the call, and in carrying out the body of the function, we hit the recursive case, where we want to multiply 5 by the return value of the call to fact(4). Then we want to return this product as the answer to fact(5). However, before calculating this product, we must wait for the call to fact(4). The current frame stays while it waits. This is true for every successive recursive call, so by calling fact(5), at one point we will have the frame of fact(5) as well as the frames of fact(4), fact(3), fact(2), and fact(1), all waiting for fact(0).

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Keeping all these frames around wastes a lot of space, so our goal is to come up with an implementation of factorial that uses a constant amount of space. We notice that in Python we can do this with a while loop:

def fact_while(n):
    total = 1
    while n > 0:
        total = total * n
        n = n - 1
    return total

However, Scheme doesn't have for and while constructs. No problem! Everything that can be written with while and for loops and also be written recursively. Instead of a variable, we introduce a new parameter to keep track of the total.

def fact(n):
    def fact_optimized(n, total):
        if n == 0:
            return total
        return fact_optimized(n - 1, total * n)
    return fact_optimized(n, 1)

(define (fact n)
    (define (fact-optimized n total)
        (if (= n 0)
            total
            (fact-optimized (- n 1) (* total n))))
    (fact-optimized n 1))

Why is this better? Consider calling fact(n) on based on this definition:

(fact 5)
(fact-optimized 5   1)
(fact-optimized 4   5)
(fact-optimized 3  20)
(fact-optimized 2  60)
(fact-optimized 1 120)
(fact-optimized 0 120)
120

Because Scheme supports tail-call optimization (note that Python does not), it knows when it no longer needs to keep around frames because there is no further calculation to do. Looking at the last line in fact_optimized, we notice that it returns the same thing that the recursive call does, no more work required. Scheme realizes that there is no reason to keep around a frame that has no work left to do, so it just has the return of the recursive call return directly to whatever called the current frame.

Therefore the last line in fact_optimized is a tail-call.

Question 8: 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 case 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.
)

Use OK to unlock and test your code:

python3 ok -q test-exp -u
python3 ok -q test-exp

Question 9: Filter

Write a function filter, which takes in a predicate and a Scheme list and returns a Scheme list whose elements are the elements from the inputted Scheme list that satisfy the predicate.

Make sure filter is tail recursive!

Hint: Try writing the function iteratively in Python, then convert into a tail recursive Scheme function.

You will also find the built-in append function useful. append concatenates two Scheme lists, much like the + operator in Python.

(define (filter pred lst)
  'YOUR-CODE-HERE
)

Use OK to unlock and test your code:

python3 ok -q test-filter -u
python3 ok -q test-filter

Homework 8

Instructions

Homework Questions

Scheme

Question 1

Conditional expressions

Question 2

Question 3

Question 4

Sets as Ordered Lists

Question 5

Question 6

Question 7

Tail-Calls in Scheme

Question 8: Exp

Question 9: Filter