Homework 6: Scheme, Tail Recursion, and Macros

hw06.zip

Due by 11:59pm on Wednesday, 12/18

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

Readings: You might find the following references useful:

Scheme Editor

How to launch

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

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 new software! While we have tested it extensively, it probably has bugs. Please let us know on piazza if there is an issue.

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
)

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

Q3: Cons All

Implement cons-all, which takes in an element first and a list of lists rests, and adds first to the beginning of each list in rests:

scm> (cons-all 1 '((2 3) (2 4) (3 5)))
((1 2 3) (1 2 4) (1 3 5))

You may find it helpful to use the built-in map procedure.

(define (cons-all first rests)
  'replace-this-line)

Q4: List Change

Implement the list-change procedure, which lists all of the ways to make change for a positive integer total amount of money, using a list of currency denominations, which is sorted in descending order. The resulting list of ways of making change should also be returned in descending order.

To make change for 10 with the denominations (25, 10, 5, 1), we get the possibilities:

10
5, 5
5, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1

To make change for 5 with the denominations (4, 3, 2, 1), we get the possibilities:

4, 1
3, 2
3, 1, 1
2, 2, 1
2, 1, 1, 1
1, 1, 1, 1, 1

Therefore, your function should behave as follows for these two inputs

scm> (list-change 10 '(25 10 5 1))
((10) (5 5) (5 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1))
scm> (list-change 5 '(4 3 2 1))
((4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1))

You may want to use cons-all in your solution.

You may also find the built-in append procedure useful.

;; List all ways to make change for TOTAL with DENOMS
(define (list-change total denoms)
  'YOUR-CODE-HERE
  )

Tail Recursion

Q5: Replicate

Below is an implementation of the replicate function, which was seen in Discussion 08. 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 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.

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

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

Q6: Accumulate

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

combiner: a function of two arguments
start: a number with which to start combining
n: the number of natural numbers to combine
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
)

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
)

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
)

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.