By the end of this lab, you should have submitted the
`lab11`

assignment using the command `submit lab11`

.

**This lab is due by 11:59pm on 7/31/2014.**

Here is a lab11.scm starter file for this lab.

**Note that Scheme will be on the exam, but you will not have a
homework on Scheme. As a result, we have made this lab longer than
usual so that you get enough practice with Scheme.**

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 parenthesis. (See: http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.

Our course uses a custom version of Scheme called STk. Use these instructions to set up STk on your own computer. If you are working on a lab machine, STk is already installed and you can skip installation for now, but make sure to install STk when you get home! You can download STk here. Make sure to choose the correct operating system (most likely Mac OSX, Windows, or Linux).

If you are using Windows, open up your Cygwin terminal (it should be on your desktop).
To navigate to your libraries where you store your lab, first type in `cd /cygdrive/c/Users`

.
Then type `ls`

: this will give you a list of all the users on your computer. You should then `cd`

into your user (for example `cd sally`

). From here, you can navigate to your lab file as you
usually do.

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

, and try typing in
the following expressions to see what Scheme would print.

```
STk> 1 ; Anything following a ';' is a comment
?
STk> 1.0
?
STk> -27
?
STk> #t ; True
?
STk> #f ; False
?
STk> "A string"
?
STk> 'symbol
?
STk> 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:

`STk> (+ 3 4)`

Notice that to *call* a function we need to enclose it in parenthesis,
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

```
STk> (+ 3 5)
?
STk> (- 10 4)
?
STk> (* 7 6)
?
STk> (/ 28 2)
?
STk> (+ 1 2 3 4 5 6 7 8 9) ;Arithmetic operators allow a variable number of arguments
?
STk> (abs -7) ;Absolute Value
?
STk> (quotient 29 5)
?
STk> (remainder 29 5)
?
STk> (= 1 3)
?
STk> (> 1 3)
?
STk> (< 1 3)
?
STk> (or #t #f)
?
STk> (and #t #t)
?
STk> (and #t #f (/ 1 0)) ;Short-Circuiting
?
STk> (not #t)
?
STk> (define x 3) ;Defining Variables
STk> x
?
STk> (define y (+ x 4))
STk> y
?
STk> nil
?
```

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

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

For example, let's define the `double`

function:

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

Try it yourself! Define a function which cubes an input. You can load
your definitions into Scheme by entering `stk -load filename.scm`

in
your terminal, or if you have the interpreter already opened up ```
(load
"filename.scm")
```

.

```
; Cubes the input x
(define (cube x)
'YOUR-CODE-HERE
)
; Doctests for cube
; cube test 1
(assert-equal 1 "cube" (cube 2) 8)
; cube test 2
(assert-equal 2 "cube" (cube 3) 27)
; cube test 3
(assert-equal 3 "cube" (cube 1) 1)
; cube test 4
(assert-equal 4 "cube" (cube 45) 91125)
```

```
(define (cube x)
(* x x x)
)
```

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')
```

`over_or_under`

which takes in an `x`

and a `y`

and returns the symbols 'under', 'equals', or 'over' depending on whether x is
less than, greater than, or equal to y.
```
; Outputs a symbol for whether x is equals, over, or under y
(define (over-or-under x y)
'YOUR-CODE-HERE
)
; Doctests for over-or-under
; over-or-under test 1
(assert-equal 1 "over-or-under" (over-or-under 5 5) 'equals)
; over-or-under test 2
(assert-equal 2 "over-or-under" (over-or-under 4 5) 'over)
; over-or-under test 3
(assert-equal 3 "over-or-under" (over-or-under 5 3) 'under)
```

```
(define (over-or-under x y)
(if (= x y)
'equal
(if (> x y)
'greater
'less
)
)
)
```

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]) ;This else clause is optional
)
```

With this, we can write control statements with multiple cases neatly and without needing staggered 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)
)
```

```
(define (fizzbuzz x)
'YOUR-CODE-HERE
)
; Doctests for fizzbuzz
; fizzbuzz test 1
; multiple of three and five
(assert-equal 1 "fizzbuzz" (fizzbuzz 15) 'fizzbuzz)
; fizzbuzz test 2
; multiple of three but not a multiple of five
(assert-equal 2 "fizzbuzz" (fizzbuzz 3) 'fizz)
; fizzbuzz test 3
; multiple of three but not a multiple of five
(assert-equal 3 "fizzbuzz" (fizzbuzz 9) 'fizz)
; fizzbuzz test 4
; multiple of five but not a multiple of three
(assert-equal 4 "fizzbuzz" (fizzbuzz 5) 'buzz)
; fizzbuzz test 5
; not a multiple of three or five
(assert-equal 5 "fizzbuzz" (fizzbuzz 14) 14)
```

```
(define (fizzbuzz x)
(cond ((= (modulo x 15) 0) 'fizzbuzz)
((= (modulo x 3) 0) 'fizz)
((= (modulo x 5) 0) 'buzz)
(else x)
)
)
```

Now that we have control statements in Scheme, let us revisit a familiar problem: turning the greatest common divisor algorithm into code. Let's try writing this problem recursively in Scheme!

Write the procedure `gcd`

, which computes the gcd of numbers
`a`

and `b`

. Look to `lab03`

if you need a reminder of how to
implement the algorithm.

```
(define (gcd a b)
'YOUR-CODE-HERE
)
; Doctests for gcd
; gcd test 1
(assert-equal 1 "gcd" (gcd 0 4) 4)
; gcd test 2
(assert-equal 2 "gcd" (gcd 8 0) 8)
; gcd test 3
(assert-equal 3 "gcd" (gcd 34 19) 1)
; gcd test 4
(assert-equal 4 "gcd" (gcd 39 91) 13)
; gcd test 5
(assert-equal 5 "gcd" (gcd 20 30) 10)
; gcd test 6
(assert-equal 6 "gcd" (gcd 40 40) 40)
```

```
(define (gcd a b)
(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)
)
)
```

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

`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
)
; Doctests for make-adder
(define add-two (make-adder 2))
(define add-three (make-adder 3))
; make-adder test 1
(assert-equal 1 "make-adder" (add-two 2) 4)
; make-adder test 2
(assert-equal 2 "make-adder" (add-two 3) 5)
; make-adder test 3
(assert-equal 3 "make-adder" (add-three 3) 6)
; make-adder test 4
(assert-equal 4 "make-adder" (add-three 9) 12)
```

```
(define (make-adder num)
(lambda (x) (+ x num))
)
```

`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
)
; Doctests for composed
; composed test 1
; (+ (+ x 1) 1)
(assert-equal 1 "composed" ((composed add-one add-one) 2) 4)
; composed test 2
; (* (* x 2) 2)
(assert-equal 2 "composed" ((composed multiply-by-two multiply-by-two) 2) 8)
; composed test 3
; (+ (* x 2) 1)
(assert-equal 3 "composed" ((composed add-one multiply-by-two) 2) 5)
; composed test 4
; (* (+ x 1) 2)
(assert-equal 4 "composed" ((composed multiply-by-two add-one) 2) 6)
; composed test 5
; (+ (+ (+ x 1) 1) 1)
(assert-equal 5 "composed" ((composed (composed add-one add-one) add-one) 2) 5)
; composed test 6
; (+ (+ (* x 2 ) 1) 1)
(assert-equal 6 "composed" ((composed (composed add-one add-one) multiply-by-two) 2) 6)
; composed test 7
; (* (+ (+ x 1) 1) 2)
(assert-equal 7 "composed" ((composed multiply-by-two (composed add-one add-one)) 2) 8)
```

```
(define (composed f g)
(lambda (x) (f (g x)))
)
```

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

function,
which takes two arguments:

```
STk> (define a (cons 3 5))
a
STk> 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 retrive a value from a pair, we use the `car`

and `cdr`

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

```
STk> (car a)
3
STk> (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:

`STk> (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.

```
STk> a
(1 2 3)
STk> (car a)
1
STk> (cdr a)
(2 3)
STk> (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:

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

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

```
STk> (define a '(1 2 3 4))
a
STk> (define b '(4 5 6))
b
STk> (define empty '())
empty
STk> (append '(1 2 3) '(4 5 6))
(1 2 3 4 5 6)
STk> (length '(1 2 3 4 5))
5
STk> (null? '(1 2 3)) ;Checks whether list is empty.
#f
STk> (null? '())
#t
STk> (null? nil)
#t
```

Try the following out in your interpreter!

```
STk> (define a (cons 1 2))
?
STk> (define b '(4 5 6))
?
STK> (define c '(7 8))
?
STk> (append b c)
?
STk> (append a b)
?
STk> (cons a b)
?
STk> (length b)
?
STk> (length a)
?
```

Create the structure as defined in the picture below. Check to make
sure that your solution is correct! You should be using `cons`

and/or
`append`

to create this structure.

`(define structure (cons (cons 1 '()) (cons 2 (cons (cons 3 4) (cons 5 '())))))`

Create a function `(filter f lst)`

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

```
(define (filter f lst)
'YOUR-CODE-HERE
)
; Doctest for filter
; filter test 1
(assert-equal 1 "filter" (filter greater-than-zero? '(1 2 3)) '(1 2 3))
; filter test 2
(assert-equal 2 "filter" (filter greater-than-zero? '()) '())
; filter test 3
(assert-equal 3 "filter" (filter greater-than-zero? '(-2 -2 4 -8)) '(4))
; filter test 4
(assert-equal 4 "filter" (filter even? '(2 3 5 1 6)) '(2 6))
```

```
(define (filter f lst)
(cond ((null? lst) '())
((f (car lst)) (cons (car lst) (filter f (cdr lst))))
(else (filter f (cdr lst)))
)
)
```

Implement a function `(remove item lst)`

that takes in a list and
returns a new list with `item`

removed from lst.

```
(define (remove item lst)
'YOUR-CODE-HERE
)
; Doctests for remove
; remove test 1
(assert-equal 1 "remove" (remove 1 '(2 5 1 3)) '(2 5 3))
; remove test 2
(assert-equal 2 "remove" (remove 1 '()) '())
; remove test 3
; remove removes all occurences of the element
(assert-equal 3 "remove" (remove 1 '(1 1 1 1)) '())
; remove test 4
(assert-equal 4 "remove" (remove 1 '(2 5 1 6 1 2)) '(2 5 6 2))
```

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

Implement a function `(all_satisfies lst pred)`

that returns #t if all
of the elements in the list satisfy pred.

```
(define (all-satisfies lst pred)
'YOUR-CODE-HERE
)
; Doctests for all-satisfies
; all_satisfies test 1
(assert-equal 1 "all-satisfies" (all-satisfies '(1 2 3 4) greater-than-zero?) #t)
; all_satisfies test 2
(assert-equal 2 "all-satisfies" (all-satisfies '(1 2 -1 4) greater-than-zero?) #f)
; all_satisfies test 3
(assert-equal 3 "all-satisfies" (all-satisfies '(1 2 -1 4) even?) #f)
; all_satisfies test 4
(assert-equal 4 "all-satisfies" (all-satisfies '( 2 -2 4) even?) #t)
```

```
(define (all-satisfies lst pred)
(= (length (filter pred lst)) (length lst)))
```