Lab 11: Scheme

Table of Contents

Deadline

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.

Introduction to 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.

Downloading Scheme

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.

Primitives and Functions

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
?

Defining Functions

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

Question 1

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

Control

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

Question 2

Try defining 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. 
; 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
    )
  )
)

Using Conditionals

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

Question 3

Remember your old friend fizz buzz from lab03? Write it now as a procedure in Scheme! The procedure fizzbuzz takes a number and outputs the word fizz if the number is divisible by 3, buzz if it's divisible by 5, fizzbuzz if it's divisible by both 3 and 5, and otherwise, the number itself. You may find remainder useful. Make sure to test your code in the interpreter. 
(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)
  )
)

Recursion

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!

Question 4

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

Lambda

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)

Question 5

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
) 

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

Question 6

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
)

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

Lists

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:

rlist

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

Question 7

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.

rlist

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

Question 8

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

Optional Section — More Lists

Question 9

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

Question 10

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