- Submission
- Scheme
- Interactive Interpreter
- Downloading Scheme
- Question 1: Primitives
- Question 2: Expressions
- Question 3
- Control and Recursion
- Question 4
- Using Conditionals
- Question 5
- Lambdas
- Question 6
- Question 7
- Lists
- Question 8
- Question 9
- Question 10
- Question 11
- More Scheme
- Question 12
- Question 13: Abstraction with data

**This lab is due at 11:59pm on 11/05/2014.**

Please start at the beginning of the lab and work your way through, working and talking over Scheme's behavior in the conceptual questions with your classmates nearby. These questions are designed to help you experiment with the concepts on the Scheme interpreter. They are good tests for your understanding.

When you are done with lab, submit Questions 3, 4, 6, 7, 8 and 12 to receive
credit for this lab. The rest are questions that are considered **extra
practice** — they can downloaded by clicking on the button below. It is
recommended that you complete these problems on your own time.

You can choose to do this lab either in your terminal or on this webpage. If you
choose to run this in your terminal, you can first download the `lab08.scm`

file
by clicking on `Generate Submission`

and work on it using STk. If you choose to
complete the lab on this webpage, click on `Generate Submission`

after you
finish typing your solutions to download a file with your work in it.

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

`lab08`

assignment using the command`submit lab08`

. You can check if we received your submission by running`glookup -t`

. Click here to see more complete submission instructions.

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.

You can also solve the following exercises with an interactive Scheme
interpreter right in the browser! Simply type Scheme code and press
`Ctrl-Enter`

. Give it a try below:

(+ 1 2)

If you choose to do this lab on your own computer, you can use the instructions below to install STk on your computer.

Our course uses a custom version of Scheme called STk. You can follow
these instructions to set up STk on your own computer. If you are
working on a lab machine (either physically or through `ssh`

), STk is
already installed.

You can also download STk for your own computer. Make sure to choose the correct operating system (most likely Mac OSX, Windows, or Linux). For more information on installations specific to your OS, check Piazza for pinned posts!

If you are using Windows, the Scheme installer will install Cygwin, a UNIX-style terminal. To navigate to your files, do the following:

- Open up your Cygwin terminal (it should be on your desktop).
- Navigate to your libraries where you store your lab by typing
`cd /cygdrive/c/Users`

. Type`ls`

to see a list of users on your computer, then`cd`

into your user. (e.g.`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 into the web interpreter to see what
Scheme would print.

```
> 1 ; Anything following a ';' is a comment
________
> 1.0
________
> -27
________
> #t ; True
________
> #f ; False
________
> "A string"
________
> 'symbol
________
> nil
________
```

; Click here and test the above expressions!

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

```
> (+ 3 5)
________
> (- 10 4)
________
> (* 7 6)
________
> (/ 28 2)
________
> (+ 1 2 3 4 5 6 7 8 9)
________
> (abs -7)
________
> (quotient 29 5)
________
> (remainder 29 5)
________
```

; Click here and test the above expressions!

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

; Click here and test the above expressions!

```
> (define x 3) ; Defining Variables
________
> x
________
> (define y (+ x 4))
________
> y
________
```

; Click here and test the above expressions!

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

When you define functions, you can load your definitions into Scheme by
entering `stk -load filename.scm`

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

, which will load in all definitions into your environment.
Alternatively, you can always use our Scheme Web Interpreter
here to test your functions
individually, just make sure to also paste in other dependencies you might need.

We've embedded the web interpreter into this lab so you can run your code
here. When you download `lab8.scm`

above, all the code you typed into the
interpreters below will be in that file for you to submit.

In addition, we also define a testing function `assert-equal`

, which tests whether an
`expression`

evaluates to an expected `value`

, which will allow us to run doctests
on the functions we write today.

; Don't edit! Used for tests!
(define (assert-equal test-num func-name actual-result expected-result)
(if (not (equal? expected-result actual-result))
(begin
(display "Testing case ")
(display test-num)
(display (string-append " for " func-name ": Test failed. "))
(display "Expected: ")
(display expected-result)
(display " Got: ")
(display actual-result)
(newline))
(begin (display "Ok") (newline))))

(define (cube x)
'your-code-here
)

When you are finished, running the following code (`Ctrl + Enter`

) will run
all the doctests.

; Tests for cube
(if (not (equal? (cube 0) 'your-code-here))
(begin
(assert-equal 1 "cube" (cube 2) 8)
(assert-equal 2 "cube" (cube 3) 27)
(assert-equal 3 "cube" (cube 1) 1)
(assert-equal 4 "cube" (cube 45) 91125))
(display "cube not implemented!"))

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

Define a function `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.

(define (over-or-under x y)
'your-code-here
)

When you're done, run the following doctests!

; Tests for over-or-under
(if (not (equal? (over-or-under 0 0) 'your-code-here))
(begin
(assert-equal 1 "over-or-under" (over-or-under 5 5) 'equals)
(assert-equal 2 "over-or-under" (over-or-under 5 4) 'over)
(assert-equal 3 "over-or-under" (over-or-under 3 5) 'under))
(display "over-or-under not implemented!"))

```
(define (over-or-under x y)
(if (= x y)
'equals
(if (> x y)
'over
'under)))
```

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

Now that we have control statements in Scheme, 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)`

(define (gcd a b)
'your-code-here
)

; Tests for gcd
(if (not (equal? (gcd 0 0) 'your-code-here))
(begin
(assert-equal 1 "gcd" (gcd 0 4) 4)
(assert-equal 2 "gcd" (gcd 8 0) 8)
(assert-equal 3 "gcd" (gcd 34 19) 1)
(assert-equal 4 "gcd" (gcd 39 91) 13)
(assert-equal 5 "gcd" (gcd 20 30) 10)
(assert-equal 6 "gcd" (gcd 40 40) 40))
(display "gcd not implemented!"))

```
(define (max a b) (if (> a b) a b))
(define (min a b) (if (> a b) b a))
(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)
```

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
)

; Tests for make-adder
(define add-two (make-adder 2))
(define add-three (make-adder 3))
(if (not (equal? (make-adder 1) 'your-code-here))
(begin
(assert-equal 1 "make-adder" (add-two 2) 4)
(assert-equal 2 "make-adder" (add-two 3) 5)
(assert-equal 3 "make-adder" (add-three 3) 6)
(assert-equal 4 "make-adder" (add-three 9) 12))
(display "make-adder not implemented!"))

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

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
)

Again, we have provided a few doctests for you to check your work!

; Tests for composed
(define (add-one a) (+ a 1))
(define (multiply-by-two a) (* a 2))
(if (not (equal? (composed + +) 'your-code-here))
(begin
; (+ (+ x 1) 1)
(assert-equal 1 "composed" ((composed add-one add-one) 2) 4)
; (* (* x 2) 2)
(assert-equal 2 "composed" ((composed multiply-by-two multiply-by-two) 2) 8)
; (+ (* x 2) 1)
(assert-equal 3 "composed" ((composed add-one multiply-by-two) 2) 5)
; (* (+ x 1) 2)
(assert-equal 4 "composed" ((composed multiply-by-two add-one) 2) 6)
; (+ (+ (+ x 1) 1) 1)
(assert-equal 5 "composed" ((composed (composed add-one add-one) add-one) 2) 5)
; (+ (+ (* x 2 ) 1) 1)
(assert-equal 6 "composed" ((composed (composed add-one add-one) multiply-by-two) 2) 6)
; (* (+ (+ x 1) 1) 2)
(assert-equal 7 "composed" ((composed multiply-by-two (composed add-one add-one)) 2) 8))
(display "composed not implemented!"))

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

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:

```
> (define a (cons 3 5))
a
> 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.

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

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

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

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

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

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

Create the structure as defined in the picture below. You can enter your code here to check if it is correct.

(define structure
'your-code-here
)

```
(define structure
(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 `item`

removed from `lst`

.

(define (remove item lst)
'your-code-here
)

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

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
)

```
(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 `(all-satisfies lst pred)`

that returns `#t`

if all
of the elements in `lst`

satisfy `pred`

.

(define (all-satisfies lst pred)
'your-code-here
)

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

There's a lot to Scheme, which is perhaps too much for this lab. Scheme takes a bit of time to get used to, but it's really not much different from any other language. The important thing is to just try different things and learn through practice!

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

(define (square x) (* x x))
(define (id x) x)
(define (add-one x) (+ x 1))
(if (not (equal? (accumulate + 0 4 id) 'your-code-here))
(begin
; 0 + 1^2 + 2^2 + 3^2 + 4^2 = 30
(assert-equal 1 "accumulate" (accumulate + 0 4 square) 30)
; 3 * 1 * 2 * 3 * 4 * 5 = 360
(assert-equal 2 "accumulate" (accumulate * 3 5 id) 360)
; 0 + (1 + 1) + (2 + 1) + (3 + 1) = 9
(assert-equal 3 "accumulate" (accumulate + 0 3 add-one) 9))
(display "accumulate not implemented!"))

```
(define (accumulate combiner start n term)
(if (= n 0)
start
(combiner (accumulate combiner
start
(- n 1)
term)
(term n))))
```

Remember the tree data structure that we built in discussion:

(define (make-btree entry left right)
(cons entry (cons left right)))
(define test-tree
(make-btree 2
(make-btree 1
nil
nil)
(make-btree 4
(make-btree 3
nil
nil)
nil)))
; Represents:
; 2
; / \
; 1 4
; /
; 3
(define (entry tree)
(car tree))
(define (left tree)
(car (cdr tree)))
(define (right tree)
(cdr (cdr tree)))

(entry test-tree)
(entry (left test-tree))
(entry (right test-tree))

Write a procedure `num-leaves`

that counts the number of leaves in a
tree.

(define (num-leaves tree)
'your-code-here
)
(if (not (equal? (num-leaves nil) 'your-code-here))
(begin
(assert-equal 1 "num-leaves" (num-leaves test-tree) 2)
(assert-equal 2 "num-leaves" (num-leaves (right test-tree)) 1)
(assert-equal 3 "num-leaves" (num-leaves nil) 0))
(display "num-leaves not implemented!"))

```
(define (num-leaves tree)
(cond ((null? tree) 0)
((and (null? (left tree))
(null? (right tree)))
1)
(else (+ (num-leaves (left tree))
(num-leaves (right tree))))))
```