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 .

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

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

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 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!
- Implement a function (remove item lst) that takes in a list and returns a new list with item removed from 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.
- Implement a function (all_satisfies lst pred) that returns #t if all of the elements in the list satisfy pred.

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