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!