Homework 7:

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

Instructions

Download hw07.zip.

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:

Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.

Topics

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

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

This consists 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. There is also a boolean value #t. In the 61A Scheme interpreter, False and #f can be used interchangeably.

Conditional expressions are evaluated as follows:

  • The predicates <p1>, <p2>, ..., <pn> are evaluated in that order until one of them evaluates to a true value (anything but False).
  • If some predicate, such as <p2>, evaluates to a true value, then the following sequence of consequent expressions, such as <el2>, is evaluated, and its final expression provides the value of the whole cond expression.
  • Otherwise, if an else clause is present, then the sequence of else-expressions is evaluated, and its final expression provides the value of the whole cond expression.
  • If no clause has a true predicate and there is no else clause, then the value of the cond is unspecified and should not be used.

Questions

Q1: Thane of Cadr

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
)

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

Use Ok to unlock and test your code:

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

Q2: Sign

Using a cond expression, define a procedure sign that takes in one parameter x and returns -1 if x is negative, 0 if x is zero, and 1 if x is positive.

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

Use Ok to unlock and test your code:

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

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

Q4: Ordered

Implement a procedure called ordered?, which takes a list of numbers and returns True if the numbers are in nondescending order, and False otherwise. Numbers are considered nondescending if each subsequent number is either larger or equal to the previous, that is:

1 2 3 3 4

Is nondescending, but:

1 2 3 3 2

Is not.

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

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

Use Ok to unlock and test your code:

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