Scheme! What is it? It's a programming language, just like Python. Scheme is a dialect of Lisp, an extremely popular language that was developed in the 1950's (in comparison, Python only appeared in 1991). By dialect, we mean that on the outside Scheme has some of its own quirks and variations, but at heart maintains all the important features and ideas that define Lisp.

In this lab, we will be playing around with Scheme syntax to get ourselves familiar with the language. Luckily, most people find it easier to learn than Python. Scheme will be an important part of Project 4, so make sure you are comfortable with the language before then. Let's go!

Fire up the Scheme interpreter by typing 'stk' into the terminal. Predict the result before you try each of the following examples. If you don't understand what Scheme actually does, ask for help! Don't waste your time by just typing this in without paying attention to the results. Keep in mind that unlike in Python, spaces and tabs don't matter in Scheme.

STk> (define trick 3) _______ STk> (+ trick 3) _______ STk> (+) _______ STk> + _______ STk> '+ _______ STk> '(dia de los muertos) _______ STk> (define treat (+ trick 1)) _______ STk> (+ trick treat (* trick treat)) _______ STk> (= trick treat) _______ STk> (if (and (> treat trick) (< treat (* trick treat))) treat trick) _______ STk> (cond ((= trick 4) 6) ((= treat 4) (+ 6 7 trick)) (else 25)) _______ STk> (+ 2 (if (> treat trick) treat trick)) _______ STk> (* (cond ((> trick treat) trick) ((< trick treat) treat) (else -1)) (+ trick 1)) _______ STk> ((if (< trick treat) + -) trick treat) _______

Here is how you define procedures in Scheme:

(define (<name> <formal parameters>) <body>)

As an example, we can define a procedure that squares a number as follows:

(define (square x) (* x x))

Then call it like this:

(square 4)

Like Python, Scheme also has a way to define anonymous procedures using the special form lambda. The structure of a lambda in Scheme looks like this:

(lambda (<formal-parameters>) <body>)

For each of the following expressions, determine what f must be in order for the evaluation of the expression to succeed without causing an error. For each expression, give a definition of f such that evaluating the expression will not cause an error, and say what the expression's value will be, given your definition.

f1 (f2) (f3 3) ((f4)) (((f5)) 3)

So we know how to define functions, but what about local variables? That's where the special form ` let `

comes in.

The general form of a let expression is:

(let ((<var1> <exp1>) (<var2> <exp2>) ... (<varn> <expn>)) <body>)

which can be thought as saying:

let <var1> have the value <exp1> and <var2> have the value <exp2> and ... <varn> have the value <expn> in <body>

The first part of the let expression is a list of name-expression pairs. The body of the let is evaluated with these names bound as local variables. Here's an example:

(define (roots a b c) (let ((d (sqrt (- (* b b) (* 4 a c)))) (-b (- b)) (2a (* 2 a))) (list (/ (+ -b d) 2a) (/ (- -b d) 2a))))

In this example we bind three local variables `d`

, `-b`

, and `2a`

to three expressions inside the procedure `roots`

, and use these names in the body of the let. Can you tell what the function does?

What is important to know is that all `let`

expressions are simply lambdas in disguise (lambda dressed up as let for Halloween). Convince yourself that the general expression for lets above can be rewritten as follows:

((lambda (<var1> <var2> ... <varn>) <body>) <exp1> <exp2> ... <expn>)

We say that a let expression is *syntactic sugar* for the underlying lambda application. Make sure you understand how this works before moving on.

Rewrite the following procedure by replacing the let with its lambda equivalent.

(define (sf sweep) (let ((giants 4) (tigers 0)) (lambda () (sweep giants tigers))))

Make sure your new version works the same as the original version.

A subtle fact about `let`

expressions is that within a single let, all of the expressions are evaluated before any of the names are bound (like multiple assignment in Python). To illustrate, try typing in the following code into the interpreter:

(define (november) (let ((election 7) (president (+ election 5))) (* president election)))

In this case, the name `election`

is not yet bound to a value when we try to evaluate `(+ election 5)`

, so the program errors. To solve this, we can nest let statements within one another:

(define (november) (let ((election 7)) (let ((president (+ election 5))) (* president election))))

Write a procedure `letters`

that takes in an integer `x`

and creates three local variables `a`

, `b`

, `c`

, with `a`

bound to twice the value of `x`

, and each subsequent name bound to a value twice as large as the one before it -- `b`

should be twice as large as `a`

, and `c`

twice as large as `b`

. The body of the function should compute the sum of the three local variables.

Scheme provides us building blocks to create pairs. As we know, once we have a representation for pairs, we can use it create more complicated data structures like Rlists and trees.

To create a pair in Scheme, we use the built-in procedure **cons**. Given a pair, we use **car** to select the first element, and **cdr** to select the second element. Here are some examples:

STk> (define x (cons 4 5)) x STk> (car x) 4 STk> (cdr x) 5 STk> (define y (cons 'world (cons 'series 'champions))) y STk> (define z (cons x y)) z STk> (car (cdr z)) world STk> (car (cdr (cdr z))) series

Scheme also has a built-in `list`

type, but underneath the hood Scheme lists are simply Rlists! That means we can use **car** and **cdr** to access their elements just like any other pair. To prove this, let's use equal? (same as == in Python) to compare a list built using the list constructor and one built using cons.

STk> (equal? (list 1 2) (cons 1 (cons 2 nil)) #t

Keep in mind that nil represents the empty list, and prints out as `()`

.

In general, when printing a pair on the screen, Scheme puts a dot in between the two elements of the pair. If, however, the pair ** represents a well-formed Rlist**, then the dot is left out. In other words, when a dot would normally be followed by a left paranthesis, both the dot and the left parenthesis are not printed; when a left parenthesis is not printed, its matching right parenthesis is also not printed. Let's look at some examples:

STk> (cons 4 5) (4 . 5) STk> (cons 4 nil) (4) STk> (cons 2 (cons 3 nil)) (2 3)

Predict what the following statements will print in the Scheme interpreter.

STk> (cons 1 (cons 2 3)) ___________ STk> (cons (list 1 2) (cons 3 4)) ___________ STk> (cons (cons 3 4) (list 1 2)) ___________ STk> (cons (cons 1 2) nil) ___________ STk> (list 1 (cons 2 (cons 1 nil)) (cons 1 'a)) ___________

Rewrite the reverse function in Scheme that we've seen in Python, which takes a list and returns a new list containing the contents of the original list reversed.

STk> (reverse (list 1 2 3 4)) (4 3 2 1)

Hint: The built-in procedure `append`

takes in two lists and appends them together.

Define a function `differences`

, that takes a list of integers as its argument and returns a list of the differences between numbers that are adjacent in the given list.

STk> (differences (list 30 16 21 9 42)) (-14 5 -12 33) STk> (differences (list 30)) ()

Define a procedure `sum_of_digits`

that takes in a positive integer and returns the sum of all digits in that integer.

STk> (sum_of_digits 14673) 21

Hint: You may find the built-in procedures `remainder`

and `quotient`

useful.

Modify your reverse procedure from Q6 to produce `deep-reverse`

. This procedure takes a list as an argument and returns a list with the original elements reversed, and with all sublists deep-reversed as well.

STk> (define x (list (list 1 2) (list 3 4))) STk> x ((1 2) (3 4)) STk> (reverse x) ((3 4) (1 2)) STk> (deep-reverse x) ((4 3) (2 1))

Fun fact: The name LISP derives from "LISt Processing"

Happy Scheming!