Homework 4: Scheme

hw04.zip

Due by 11:59pm on Tuesday, 7/17

Instructions

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:

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.

Q0: Midsummer Survey

Congratulations on making it to Week 4 of the course! Please fill out this survey to give feedback on the course so far. Once you complete the survey, you will receive a passphrase in the confirmation screen. Assign that passphrase as a string to the name passphrase in the hw04.py file. For example, if the code at the end of the survey was scheme, the assignment statement should look like this:

passphrase = 'scheme'

Use Ok to test your code:

python3 ok -q survey

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

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

b^2k = (b^k)²

b^2k+1 = b(b^k)²

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

Q3: Cadr and Caddr

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

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

Q5: No Dots!

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

)

Use Ok to unlock and test your code:

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

Sets as Ordered Lists

A set is a type of collection that stores unique elements. The main operation associated with sets is checking whether a given value is in a set.

There is no such built-in set data type in Scheme, but 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. Specifically, we will represent sets using Scheme lists ordered from least to greatest with no repeated elements.

Q6: Add

First, 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.

We've provided a function empty? which returns #t if the given set s has no elements.

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

(define (add s v)
    'YOUR-CODE-HERE
    )

Use Ok to unlock and test your code:

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

Q7: Contains

Next, define contains?, which returns whether a set s contains value v.

; Sets as sorted lists
(define (contains? s v)
    'YOUR-CODE-HERE
    )

Use Ok to unlock and test your code:

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

Q8: Intersect and Union

Finally, define intersect, which returns a set containing only values that appear in both sets s and t, and union, which returns a set containing all values that appear in either set s or t.

Your implementation for both functions should run in linear time in the length of the input sets.

(define (intersect s t)
    'YOUR-CODE-HERE
    )

(define (union s t)
    'YOUR-CODE-HERE
    )

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