*Due at 11:59pm on 04/02/2015.*

Download lab09.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

By the end of this lab, you should have submitted the lab with
`python3 ok --submit`

. You may submit more than once before the
deadline; only the final submission will be graded.

- To receive credit for this lab, you must complete questions 3, 4, 5, 6, and 7 in lab09.scm and submit through OK.
- Questions 8, 9, 10, 11, and 12 are
*extra practice*. They can be found in the lab09-extra.scm file. It is recommended that you complete these problems on your own time.

Our course uses a custom version of Scheme (which you will build for project 4). You can download it here (it is already included with the starter ZIP archive). To start it, use the following command:

`python3 scheme`

To close the Scheme interpreter, you can type `(exit)`

.

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

Let's take a look at the primitives in Scheme. Open up the Scheme
interpreter in your terminal with `python3 scheme`

to see what Scheme
would print.

```
scm> 1 ; Anything following a ';' is a comment
______1
scm> 1.0
______1.0
scm> -27
______-27
scm> #t
______True
scm> #f
______False
scm> "A string"
______"A string"
scm> 'symbol
______symbol
scm> nil
______()
```

Of course, what kind of programming language would Scheme be if it
didn't have any functions? Scheme uses Polish prefix notation, where
the operator comes before the operands. For example, to evaluate ```
3 +
4
```

, we would type into the Scheme interpreter:

`(+ 3 4)`

Notice that to *call* a function we need to enclose it in parentheses,
with its arguments following. Be careful about this, as while in
Python an extra set of parentheses won't hurt, in Scheme, it will
interpret the parentheses as a function call. Evaluating `(3)`

results
in an error because Scheme tries to call a function called `3`

that
takes no arguments, which would result in an error.

Let's familiarize ourselves with some of the built-in functions in Scheme. Try out the following in the interpreter:

```
scm> (+ 3 5)
______8
scm> (- 10 4)
______6
scm> (* 7 6)
______42
scm> (/ 28 2)
______14
scm> (+ 1 2 3 4 5 6 7 8 9)
______45
scm> (quotient 29 5)
______5
scm> (remainder 29 5)
______4
```

```
scm> (= 1 3)
______False
scm> (> 1 3)
______False
scm> (< 1 3)
______True
scm> (or #t #f)
______True
scm> (and #t #t)
______True
scm> (and #t #f (/ 1 0)) ; Short-Circuiting
______False
scm> (not #t)
______False
```

```
scm> (define x 3) ; Defining Variables
______x
scm> x
______3
scm> (define y (+ x 4))
______y
scm> y
______7
```

To write a program, we need to write functions, so let's define one. The syntax for defining a function in Scheme is:

```
(define ([name] [args])
[body])
```

For example, this is how we would define the `double`

function:

```
(define (double x)
(+ x x))
```

Lets try it out! Define a function which cubes an input.

```
(define (cube x)
'YOUR-CODE-HERE
(* x x x))
```

To load a file into Scheme, you can use the following command (replace

`name_of_file`

with the name of your file):`python3 scheme -load name_of_file.scm`

This is like

`python3 -i name_of_file.py`

.As with other labs, you can run OK to test your function by providing the name of the function. This time, however, you will first have to unlock the tests.

`python3 ok -q cube -u python3 ok -q cube`

So far, we can't do much in our functions so let's introduce control statements to allow our functions to do more complex operations! The if-statement has the following format:

```
(if [condition]
[true_result]
[false_result])
```

For example, the following code written in Scheme and Python are equivalent:

```
; Scheme
(if (> x 3)
1
2)
# Python
if x > 3:
1
else:
2
```

Notice that the if-statement has no `elif`

case. If want to have
multiple cases with the if-statement, you would need multiple branched
if-statements:

```
; Scheme
(if (< x 0)
'negative ; returns the symbol negative
(if (= x 0)
'zero ; returns the symbol zero
'positive ; returns the symbol positive
)
)
# Python Equivalent
if x < 0:
print('negative')
else:
if x == 0:
print('zero')
else:
print('positive')
```

Define a function `over-or-under`

which takes in an `x`

and a `y`

and
returns the the following:

- return -1 if
`x`

is less than`y`

- return 0 if
`x`

is equal to`y`

- return 1 if
`x`

is greater than`y`

```
(define (over-or-under x y)
'YOUR-CODE-HERE
(if (= x y)
0
(if (> x y)
1
-1)))
```

These nested 'if' statements get messy as more cases are needed,
so alternatively, we also have the `cond`

statement, which has a
different syntax:

```
(cond ([condition_1] [result_1])
([condition_2] [result_2])
...
([condition_n] [result_n])
(else [result_else])) ; 'else' is optional
```

With this, we can write control statements with multiple cases neatly and without needing branching if-statements.

```
(cond ((and (> x 0) (= (modulo x 2) 0)) 'positive-even-integer)
((and (> x 0) (= (modulo x 2) 1)) 'positive-odd-integer)
((= x 0) 'zero)
((and (< x 0) (= (modulo x 2) 0)) 'negative-even-integer)
((and (< x 0) (= (modulo x 2) 1)) 'negative-odd-integer))
```

Ah yes, you thought you were safe, but we can also write `lambda`

functions in Scheme!

As noted above, the syntax for defining a procedure in Scheme is:

```
(define ([name] [args])
[body]
)
```

Defining a `lambda`

has a slightly different syntax, as follows:

```
(lambda ([args])
[body]
)
```

Notice how the only difference is the lack of function name. You can create and call a lambda procedure in Scheme as follows:

```
; defining a lambda
(lambda (x) (+ x 3))
; calling a lambda
((lambda (x) (+ x 3)) 7)
```

Write the procedure `make-adder`

which takes in an initial number,
`num`

, and then returns a procedure. This returned procedure takes in a
number `x`

and returns the result of `x + num`

.

```
(define (make-adder num)
'YOUR-CODE-HERE
(lambda (x) (+ x num)))
```

In Scheme, lists are composed similarly to how Linked Lists that we had
worked with in Python were implemented. Lists are made up of pairs, which
can point to two objects. To create a pair, we use the `cons`

function,
which takes two arguments:

```
scm> (define a (cons 3 5))
a
scm> a
(3 . 5)
```

Note the dot between the `3`

and `5`

. The dot indicates that this is a
pair, rather than a sequence (as you'll see in a bit).

To retrieve a value from a pair, we use the `car`

and `cdr`

functions
to retrieve the first and second elements in the pair.

```
scm> (car a)
3
scm> (cdr a)
5
```

Look familiar yet? Like how Linked Lists are formed, lists in Scheme are
formed by having the first element of a pair be the first element of
the list, and the second element of the pair point to another pair
containing the rest of list, or to `nil`

to signify the end of the
list. For example, the sequence (1, 2, 3) can be represented in Scheme
with the following line:

`scm> (define a (cons 1 (cons 2 (cons 3 nil))))`

which creates the following object in Scheme:

We can then of course retrieve values from our list with the `car`

and
`cdr`

function.

```
scm> a
(1 2 3)
scm> (car a)
1
scm> (cdr a)
(2 3)
scm> (car (cdr (cdr a)))
3
```

This is not the only way to create a list though. You can also use the
`list`

function, as well as the quote form to form a list as well:

```
scm> (list 1 2 3)
(1 2 3)
scm> '(1 2 3)
(1 2 3)
scm> '(1 . (2 . (3)))
(1 2 3)
```

There are a few other built-in functions in Scheme that are used for lists:

```
scm> (define a '(1 2 3 4))
______a
scm> (define b '(4 5 6))
______b
scm> (define empty '())
______empty
scm> (append '(1 2 3) '(4 5 6))
______(1 2 3 4 5 6)
scm> (length '(1 2 3 4 5))
______5
scm> (null? '(1 2 3)) ; Checks whether list is empty.
______False
scm> (null? '())
______True
scm> (null? nil)
______True
```

Create the structure as defined in the picture below.

```
(define structure
'YOUR-CODE-HERE
(cons (cons 1 '())
(cons 2
(cons (cons 3 4)
(cons 5 '())))))
```

Implement a function `(remove item lst)`

that takes in a list and
returns a new list with all instances of `item`

removed from `lst`

.

```
(define (remove item lst)
'YOUR-CODE-HERE
(cond ((null? lst) '())
((equal? item (car lst)) (remove item (cdr lst)))
(else (cons (car lst) (remove item (cdr lst))))))
```

The following questions are for **extra practice** — they can be found
in the lab09-extra.scm file. It is recommended that
you complete these problems on your own time.

Write the procedure `composed`

, which takes in procedures `f`

and `g`

and outputs a new procedure. This new procedure takes in a number `x`

and outputs the result of calling `f`

on `g`

of `x`

.

```
(define (composed f g)
'YOUR-CODE-HERE
(lambda (x) (f (g x))))
```

Let us revisit a familiar problem: finding the greatest common divisor of two numbers. Let's try writing this problem recursively in Scheme!

Write the procedure `gcd`

, which computes the gcd of numbers `a`

and
`b`

. Recall that the *greatest common divisor* of two positive integers
`a`

and `b`

is the largest integer which evenly divides both numbers
(with no remainder). Euclid's algorithm states that the greatest common
divisor is

- the smaller value if it evenly divides the larger value, OR
- the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value

In other words, if `a`

is greater than `b`

and `a`

is not divisible by
`b`

, then

`gcd(a, b) == gcd(b, a % b)`

You may find the provided functions `min`

and `max`

helpful. You can
also use the built-in `modulo`

function.

```
(define (max a b) (if (> a b) a b))
(define (min a b) (if (> a b) b a))
(define (gcd a b)
'YOUR-CODE-HERE
(if (not (or (= a 0) (= b 0)))
(if (= (modulo (max a b) (min a b)) 0)
(min a b)
(gcd (min a b) (modulo (max a b) (min a b))))
(max a b)))
```

Create a function `(filter f lst)`

, which takes a predicate function `f`

and a
list `lst`

, and returns a new list containing only elements of the list that
satisfy the predicate.

```
(define (filter f lst)
'YOUR-CODE-HERE
(cond ((null? lst) '())
((f (car lst)) (cons (car lst) (filter f (cdr lst))))
(else (filter f (cdr lst)))))
```

Implement a function `(all-satisfies lst pred)`

that returns `True`

if all of
the elements in `lst`

satisfy `pred`

.

```
(define (all-satisfies lst pred)
'YOUR-CODE-HERE
(= (length (filter pred lst)) (length lst)))
```

Fill in the definition for the procedure `accumulate`

, which takes the
following parameters:

`combiner`

: a function of two arguments`start`

: a number with which to start combining`n`

: the number of terms to combine`term`

: a function of one argument that computes the*n*th term of the sequence

`accumulate`

should return the result of combining the first `n`

terms
of the sequence.

```
(define (accumulate combiner start n term)
(if (= n 0)
start
'YOUR-CODE-HERE
(combiner (accumulate combiner
start
(- n 1)
term)
(term n)) ))
```