Due by 11:59pm on Tuesday, August 4

Instructions

Download hw07.zip. Inside the archive, you will find a file called hw07.scm, along with a copy of the ok autograder.

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:

• Scheme Specification
• Scheme Built-in Procedure Reference
• Section 3.2
• Section 3.5

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 3 points.

Scheme Editor

How to launch

In your hw07 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 hw07.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.

Required Questions

Scheme

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 num and returns -1 if num is negative, 0 if num is zero, and 1 if num is positive.

(define (sign num)
  '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 x to the power of a nonnegative integer y for which the number of operations grows logarithmically (as opposed to linearly).

Hint: Consider the following observations:

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

You may use the built-in predicates even? and odd?. Scheme doesn't support iteration in the same manner as Python, so consider another way to solve this problem.

(define (square x) (* x x))

(define (pow x y)
  'YOUR-CODE-HERE
)

Use Ok to unlock and test your code:

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

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

Tail Recursion

Q5: Replicate

Below is an implementation of the replicate function, which was seen in discussion. replicate takes in an element x and an integer n, and returns a list with x repeated n times.

(define (replicate x n)
	(if (= n 0)
		nil
		(cons x (replicate x (- n 1)))))

Update this implementation of replicate to be tail recursive. It should have identical functionality to the non-tail recursive version.

If you're running into an recursion depth exceeded error and you're using the staff interpreter, it's very likely your solution is not properly tail recursive.

We test that your solution is tail recursive by calling replicate with a very large input. If your solution is not tail recursive and does not use a constant number of frames, it will not be able to successfully run.

You may wish to use the built-in append procedure in your solution.

(define (replicate x n)
  'YOUR-CODE-HERE
  )

Watch the hints video below for somewhere to start:

Use Ok to test your code:

python3 ok -q replicate

Q6: Accumulate

Fill in the definition for the procedure accumulate, which combines the first n natural numbers according to the following parameters:

1. combiner: a function of two arguments
2. start: a number with which to start combining
3. n: the number of natural numbers to combine
4. term: a function of one argument that computes the nth term of a sequence

For example, we can find the product of all the numbers from 1 to 5 by using the multiplication operator as the combiner, and starting our product at 1:

scm> (define (identity x) x)
scm> (accumulate * 1 5 identity)  ; 1 * 1 * 2 * 3 * 4 * 5
120

We can also find the sum of the squares of the same numbers by using the addition operator as the combiner and square as the term:

scm> (define (square x) (* x x))
scm> (accumulate + 0 5 square)  ; 0 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
55
scm> (accumulate + 5 5 square)  ; 5 + 1^2 + 2^2 + 3^2 + 4^2 + 5^2
60

You may assume that the combiner will always be commutative: i.e. the order of arguments do not matter.

(define (accumulate combiner start n term)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q accumulate

Q7: Tail Recursive Accumulate

Update your implementation of accumulate to be tail recursive. It should still pass all the tests for "regular" accumulate!

You may assume that the input combiner and term procedures are properly tail recursive.

If your implementation for accumulate in the previous question is already tail recursive, you may simply copy over that solution (replacing accumulate with accumulate-tail as appropriate).

If you're running into an recursion depth exceeded error and you're using the staff interpreter, it's very likely your solution is not properly tail recursive.

We test that your solution is tail recursive by calling accumulate-tail with a very large input. If your solution is not tail recursive and does not use a constant number of frames, it will not be able to successfully run.

(define (accumulate-tail combiner start n term)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q accumulate-tail

Macros

Q8: List Comprehensions

Recall that list comprehensions in Python allow us to create lists out of iterables:

[<map-expression> for <name> in <iterable> if <conditional-expression>]

Use a macro to implement list comprehensions in Scheme that can create lists out of lists. Specifically, we want a list-of macro that can be called as follows:

(list-of <map-expression> for <name> in <list> if <conditional-expression>)

Calling list-of will return a new list constructed by doing the following for each element in <list>:

• Bind <name> to the element.
• If <conditional-expression> evaluates to a truth-y value, evaluate <map-expression> and add it to the result list.

Here are some examples:

scm> (list-of (* x x) for x in '(3 4 5) if (odd? x))
(9 25)
scm> (list-of 'hi for x in '(1 2 3 4 5 6) if (= (modulo x 3) 0))
(hi hi)
scm> (list-of (car e) for e in '((10) 11 (12) 13 (14 15)) if (list? e))
(10 12 14)

Hint: You may use the built-in map and filter procedures. Check out the Scheme Built-ins reference for more information.

You may find it helpful to refer to the for loop macro introduced in lecture. The filter expression should be transformed using a lambda in a similar way to the map expression in the example.

(define-macro (list-of map-expr for var in lst if filter-expr)
  'YOUR-CODE-HERE
)

Watch the hints video below for somewhere to start:

Use Ok to test your code:

python3 ok -q list-comp

Optional (not graded): Recall also that the if <conditional> portion of the Python list comprehension was optional. Modify your macro so that the Scheme list comprehension does not require a conditional expression.

Refer to the macro form in the Scheme Specification for an explanation of how to do optional macro parameters.

Submit

Make sure to submit this assignment by running:

python3 ok --submit