Due by 11:59pm on Thursday, 4/6

Instructions

Download hw07.zip.

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

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:

Hinting

Homework 7 includes a hinting sytem that generates hints specifically for your submitted code. If you ever find yourself stuck, you can ask for hints by using adding the --hint flag to the ok command.

$ python3 ok -q pow --hint
...
Hint: There are extra parentheses on line ...

The system tries to generate hints specific to your program by applying multiple techniques, including:

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

Implement a procedure pow for raising the number b to the power of a nonnegative 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
)

Use OK to unlock and test your code:

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

Question 4

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 5

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 6

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 7

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 8

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

Question 9: Survey

Please fill out the midsemester survey. You will receive a passphrase after finishing the survey to submit with the homework.

(define (survey)
     'passphrase-here
      )

Use OK to unlock and test your code:

python3 ok -q survey -u
python3 ok -q survey