# Homework 8 Solutions

## Solution Files

You can find the solutions in hw08.scm.

Scheme is a famous functional programming language from the 1970s. It is a dialect of Lisp (which stands for LISt Processing). The first observation most people make is the unique syntax, which uses a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.

### Recommended VSCode Extensions

If you use VSCode as your text editor, we have found these extensions to be quite helpful for Scheme :)

Before:

After:

**Extensions**:

You may find it useful to try code.cs61a.org/scheme when working through problems, as it can draw environment and box-and-pointer diagrams and it lets you walk your code step-by-step (similar to Python Tutor). Don't forget to submit your code by submitting to the appropriate Gradescope assignment though!

### Scheme Editor

You can write your code by either opening the designated `.scm`

file in your text editor, or by typing directly in the Scheme Editor, which can also be useful for debugging. 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 while `python3 editor`

is still running and you should see it. If you choose to code directly in the Scheme Editor, don't forget to save your work before running Ok tests and before closing the editor. To stop running the editor and return to the command line, type `Ctrl-C`

.

Make sure to run `python3 ok`

in a separate tab or window so that the editor keeps running.

If you find that your code works in the online editor but not in your own interpreter, it's possible you have a bug in your code from an earlier part that you'll have to track down. Every once in a while there's a bug that our tests don't catch, and if you find one you should let us know!

# Required Questions

## Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

### Q1: Pow

Implement a procedure `pow`

for raising the number `base`

to the power of a
nonnegative integer `exp`

for which the number of operations grows logarithmically, rather than linearly (the number of recursive calls should be much smaller than the input `exp`

). For example, for `(pow 2 32)`

should take 5 recursive calls rather than 32 recursive calls. Similarly, `(pow 2 64)`

should take 6 recursive calls.

If you would like a quick refresher on Scheme syntax consider looking at the Scheme Specification and Scheme Built-in Procedure Reference (and the Lab 11 Scheme Refresher).

Hint:Consider the following observations:

- x
^{2y}= (x^{y})^{2}- x
^{2y+1}= x(x^{y})^{2}For example we see that 2

^{32}is (2^{16})^{2}, 2^{16}is (2^{8})^{2}, etc. 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 n) (* n n))
(define (pow base exp)
(cond ((= exp 0) 1)
((even? exp) (square (pow base (/ exp 2))))
(else (* base (pow base (- exp 1))))))
```

Use Ok to test your code:

`python3 ok -q pow`

The `else`

clause shows the basic recursive version of `pow`

that we've seen
before in class.

We save time in computation by avoiding an extra n/2 multiplications of the
base. Instead, we just square the result of `base^(exp/2)`

.

### Q2: Repeatedly Cube

Implement the following function, which cubes the given value `x`

some number `n`

times, based on the given skeleton.

Here are some examples of how `repeatedly-cube`

should behave:

```
scm> (repeatedly-cube 100 1) ; 1 cubed 100 times is still 1
1
scm> (repeatedly-cube 2 2) ; (2^3)^3
512
scm> (repeatedly-cube 3 2) ; ((2^3)^3)^3
134217728
```

For information on how to use

`let`

, see the scheme spec.

```
(define (repeatedly-cube n x)
(if (zero? n)
x
(let
((y (repeatedly-cube (- n 1) x))) (* y y y))))
```

Use Ok to test your code:

`python3 ok -q repeatedly-cube`

### Q3: Thane of Cadr

**Note:** *Scheme lists will be covered in lecture on Wednesday, April 12. If you are working ahead, consider looking at the Scheme Specification for details on using car and cdr.*

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)
(car (cdr s)))
(define (caddr s)
(car (cddr s)))
```

Following the given example of `cddr`

, defining `cadr`

and `caddr`

should be
fairly straightforward.

Just for fun, if this were a Python linked list question instead, the solution might look something like this:

```
cadr = lambda l: l.rest.first
caddr = lambda l: l.rest.rest.first
```

Use Ok to test your code:

`python3 ok -q cadr-caddr`