CS61A Lab 5b: Scheme

July 24, 2013

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/). Odd as the syntax may seem, it allows us to write, with relative ease, something very beautiful, called a metacircular evaluator. We will see this later in the course. Scheme also features first-class functions and optimized tail-recursion, which were relatively new features at the time.

We have provided a starter file, which you can copy into your directory with the command:

cp ~cs61a/lib/lab/lab05b/lab05b.scm .

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 Python 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> (magnitude -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
?

So far, we've only been using Scheme as calculator rather than a programming language. To write a program, we need our own 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").

(define (cube x)
        0)          ;Replace the 0 with your code

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

Control and Recursion

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)
    (display "Negative")
    (if (= x 0)
        (display "Zero")
        (display "Positive"))

#Python Equivalent
if x < 0:
    print('Negative')
else:
    if x == 0:
        print('Zero')
    else:
        print('Positive')

But this gets 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)) (display "Positive Even Integer"))
      ((and (> x 0) (= (modulo x 2) 1)) (display "Positive Odd Integer"))
      ((= x 0) (display "Zero"))
      ((and (< x 0) (= (modulo x 2) 0)) (display "Negative Even Integer"))
      ((and (< x 0) (= (modulo x 2) 1)) (display "Negative Odd Integer")))

Now that we have control statements in Scheme, let us revisit a familiar problem: factorial. We will write it using a recursive procedure, but with both recursive and iterative processes. Read section 1.2.1 of this link to see what we mean by this. In short, an iterative process is summarized by state variables (for example, a counter and a sum), and update and termination rules. The iterative process can still use an underlying recursive procedure.

Write factorial with a recursive process.
Write factorial with an iterative process. The procedure should still make a recursive call!

In the iterative case, most programming languages consume memory proportional to the number of procedure calls. However, Scheme "will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive." We see then that syntax such as "for" and "while" loops are not necessary in Scheme; they are merely "syntactic sugar".

1.)
(define (factorial_recursive x)
    (if (= x 0)
        1
        (* x (factorial_recursive (- x 1)))))
2.)
(define (factorial_iterative x)
    (fact_iter_helper 1 1 x))

(define (fact_iter_helper prod count max)
    (if (> count max)
        product
        (fact_iter_helper (* prod count) (+ count 1) max)))

Lists

In Scheme, lists are composed similarly to how Rlists that we had worked with 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 Rlists 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)))

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

Create the structure as defined in the picture below. Check to make sure that your solution is correct!

(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)
    (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 and a list, and returns a new list containing only elements of the list that satisfy the predicate.

(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 the list satisfy pred.

(define (all_satisfies lst pred)
        (= (length (filter pred lst)) (length lst)))

More Scheme

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. Try typing these into the interpretter!

STk> '(1 . 3)
?
STk> '(1 . (2 . (3)))
?
STk> '(1 . (2 . 3))
?
STk> (+ 1 2 3)
?
STk> (+ . (1 . (2 . (3))))
?
STk> (define (foo a b) (display b))
STk> (foo 2 3)
?
STk> (foo 2 3 4 5 6 7)
?
STk> (define (bar a . b) display b))
STk> (bar 2 3)
?
STk> (bar 4 5 6 7)
?
STk> (bar 10)
?
STk> (first "string")
?
STk> (last "string")
?
STk> (butfirst "string")
?
STk> (butlast "string")
?
STk> (begin (define x 1) (display x) (newline) (define x (+ x 1)) (display x) (newline))
?
STk> (define (filter f lst)
        (if (null? lst)
            lst
            (let ((first (car lst)) (rest (filter f (cdr lst))))
                  (if (f first)
                      (cons first rest)
                      rest))))
STk> (filter (lambda (x) (> x 5)) '(3 4 5 6 7))
?