Homework 6: Scheme

Due by 11:59pm on Friday, April 3

Instructions

Download hw06.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:

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. There is a homework recovery policy as stated in the syllabus. This homework is out of 2 points.

Scheme Editor

How to launch

In your hw06 folder you will find a new editor. To run this editor, run python3 editor. This should pop up a window in your browser; if it does not, please navigate to localhost:31415 and you should see it.

Make sure to run python3 ok in a separate tab or window so that the editor keeps running.

Features

The hw06.scm file should already be open. You can edit this file and then run Run to run the code and get an interactive terminal or Test to run the ok tests.

Environments will help you diagram your code, and Debug works with environments so you can see where you are in it. We encourage you to try out all these features.

Reformat is incredibly useful for determining whether you have parenthesis based bugs in your code. You should be able to see after formatting if your code looks weird where the issue is.

By default, the interpreter uses Lisp-style formatting, where the parens are all put on the end of the last line

(define (f x)
    (if (> x 0)
        x
        (- x)))

However, if you would prefer the close parens to be on their own lines as so

(define (f x)
    (if (> x 0)
        x
        (- x)
    )
)

you can go to Settings and select the second option.

Warning

The editor will neither back up nor submit on your behalf. You still need to run python ok -u to unlock cases from the terminal as well as python ok --submit.

Reporting bugs

This is relatively new software! While we have tested it extensively, it probably has bugs. Please let us know on piazza if there is an issue.

Questions

Q1: Survey

Please fill out the survey at this link and fill in hw06.py with the token. The link might not work if you are logged into some google account other than your Berkeley account, so either log out from all other accounts or open the link in a private/incognito window and sign in to your Berkeley account there.

To check that you got the correct token run

Use Ok to test your code:

python3 ok -q survey

Scheme

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

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

Q4: Pow

Implement a procedure pow for raising the number b to the power of a nonnegative integer n for which the number of operations grows logarithmically (as opposed to linearly).

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

Q5: Unique

Implement unique, which takes in a list s and returns a new list containing the same elements as s with duplicates removed.

scm> (unique '(1 2 1 3 2 3 1))
(1 2 3)
scm> (unique '(a b c a a b b c))
(a b c)

Hint: you may find it useful to use the built-in filter procedure. See the built-in procedure reference for more information.

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

Use Ok to test your code:

python3 ok -q unique

Submit

Make sure to submit this assignment by running:

python3 ok --submit