Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Atomic expressions (also called atoms) are expressions without sub-expressions, such as numbers, boolean values, and symbols.

scm> 1234    ; integer
1234
scm> 123.4   ; real number
123.4
scm> #f      ; the Scheme equivalent of False in Python
#f

A Scheme symbol is equivalent to a Python name. A symbol evaluates to the value bound to that symbol in the current environment. (They are called symbols rather than names because they include + and other arithmetic symbols.)

scm> quotient      ; A symbol bound to a built-in procedure
#[quotient]
scm> +             ; A symbol bound to a built-in procedure
#[+]

In Scheme, all values except #f (equivalent to False in Python) are true values (unlike Python, which has other false values, such as 0).

scm> #t
#t
scm> #f
#f

Scheme uses Polish prefix notation, in which the operator expression comes before the operand expressions. For example, to evaluate 3 * (4 + 2), we write:

scm> (* 3 (+ 4 2))
18

Just like in Python, to evaluate a call expression:

1. Evaluate the operator. It should evaluate to a procedure.
2. Evaluate the operands, left to right.
3. Apply the procedure to the evaluated operands.

Here are some examples using built-in procedures:

scm> (+ 1 2)
3
scm> (- 10 (/ 6 2))
7
scm> (modulo 35 4)
3
scm> (even? (quotient 45 2))
#t

Define: The define form is used to assign values to symbols. It has the following syntax:

(define <symbol> <expression>)

scm> (define pi (+ 3 0.14))
pi
scm> pi
3.14

To evaluate the define expression:

1. Evaluate the final sub-expression (<expression>), which in this case evaluates to 3.14.
2. Bind that value to the symbol (symbol), which in this case is pi.
3. Return the symbol.

The define form can also define new procedures, described in the "Defining Functions" section.

If Expressions: The if special form evaluates one of two expressions based on a predicate.

(if <predicate> <if-true> <if-false>)

The rules for evaluating an if special form expression are as follows:

1. Evaluate the <predicate>.
2. If the <predicate> evaluates to a true value (anything but #f), evaluate and return the value of the <if-true> expression. Otherwise, evaluate and return the value of the <if-false> expression.

For example, this expression does not error and evaluates to 5, even though the sub-expression (/ 1 (- x 3)) would error if evaluated.

scm> (define x 3)
x
scm> (if (> (- x 3) 0) (/ 1 (- x 3)) (+ x 2))
5

The <if-false> expression is optional.

scm> (if (= x 3) (print x))
3

Let's compare a Scheme if expression with a Python if statement:

• In Scheme:

    (if (> x 3) 1 2)

• In Python:

    if x > 3:
        1
    else:
        2

The Scheme if expression evaluates to a number (either 1 or 2, depending on x). The Python statement does not evaluate to anything, and so the 1 and 2 cannot be used or accessed.

Another difference between the two is that it's possible to add more lines of code into the suites of the Python if statement, while a Scheme if expression expects just a single expression in each of the <if-true> and <if-false> positions.

One final difference is that in Scheme, you cannot write elif clauses.

Cond Expressions: The cond special form can include multiple predicates (like if/elif in Python):

(cond
    (<p1> <e1>)
    (<p2> <e2>)
    ...
    (<pn> <en>)
    (else <else-expression>))

The first expression in each clause is a predicate. The second expression in the clause is the return expression corresponding to its predicate. The else clause is optional; its <else-expression> is the return expression if none of the predicates are true.

The rules of evaluation are as follows:

1. Evaluate the predicates <p1>, <p2>, ..., <pn> in order until one evaluates to a true value (anything but #f).
2. Evalaute and return the value of the return expression corresponding to the first predicate expression with a true value.
3. If none of the predicates evaluate to true values and there is an else clause, evaluate and return <else-expression>.

For example, this cond expression returns the nearest multiple of 3 to x:

scm> (define x 5)
x
scm> (cond ((= (modulo x 3) 0) x)
            ((= (modulo x 3) 1) (- x 1))
            ((= (modulo x 3) 2) (+ x 1)))
6

Lambdas: The lambda special form creates a procedure.

(lambda (<param1> <param2> ...) <body>)

This expression will create and return a procedure with the given formal parameters and body, similar to a lambda expression in Python.

scm> (lambda (x y) (+ x y))        ; Returns a lambda procedure, but doesn't assign it to a name
(lambda (x y) (+ x y))
scm> ((lambda (x y) (+ x y)) 3 4)  ; Create and call a lambda procedure in one line
7

Here are equivalent expressions in Python:

>>> lambda x, y: x + y
<function <lambda> at ...>
>>> (lambda x, y: x + y)(3, 4)
7

The <body> may contain multiple expressions. A scheme procedure returns the value of the last expression in its body.

The define form can create a procedure and give it a name:

(define (<symbol> <param1> <param2> ...) <body>)

For example, this is how we would define the double procedure:

scm> (define (double x) (* x 2))
double
scm> (double 3)
6

Here's an example with three arguments:

scm> (define (add-then-mul x y z)
        (* (+ x y) z))
scm> (add-then-mul 3 4 5)
35

When a define expression is evaluated, the following occurs:

1. Create a procedure with the given parameters and <body>.
2. Bind the procedure to the <symbol> in the current frame.
3. Return the <symbol>.

scm> (define add (lambda (x y) (+ x y)))
add
scm> (define (add x y) (+ x y))
add

As you read through this section, it may be difficult to understand the differences between the various representations of Scheme containers. We recommend that you use our online Scheme interpreter to see the box-and-pointer diagrams of pairs and lists that you're having a hard time visualizing! (Use the command (autodraw) to toggle the automatic drawing of diagrams.)

Lists

Scheme lists are very similar to the linked lists we've been working with in Python. Just like how a linked list is constructed of a series of Link objects, a Scheme list is constructed with a series of pairs, which are created with the constructor cons.

Scheme lists require that the cdr is either another list or nil, an empty list. A list is displayed in the interpreter as a sequence of values (similar to the __str__ representation of a Link object). For example,

scm> (cons 1 (cons 2 (cons 3 nil)))
(1 2 3)

Here, we've ensured that the second argument of each cons expression is another cons expression or nil.

We can retrieve values from our list with the car and cdr procedures, which now work similarly to the Python Link's first and rest attributes. (Curious about where these weird names come from? Check out their etymology.)

scm> (define a (cons 1 (cons 2 (cons 3 nil))))  ; Assign the list to the name a
a
scm> a
(1 2 3)
scm> (car a)
1
scm> (cdr a)
(2 3)
scm> (car (cdr (cdr a)))
3

If you do not pass in a pair or nil as the second argument to cons, it will error:

scm> (cons 1 2)
Error

list Procedure

There are a few other ways to create lists. The list procedure takes in an arbitrary number of arguments and constructs a list with the values of these arguments:

scm> (list 1 2 3)
(1 2 3)
scm> (list 1 (list 2 3) 4)
(1 (2 3) 4)
scm> (list (cons 1 (cons 2 nil)) 3 4)
((1 2) 3 4)

Note that all of the operands in this expression are evaluated before being put into the resulting list.

Quote Form

We can also use the quote form to create a list, which will construct the exact list that is given. Unlike with the list procedure, the argument to ' is not evaluated.

scm> '(1 2 3)
(1 2 3)
scm> '(cons 1 2)           ; Argument to quote is not evaluated
(cons 1 2)
scm> '(1 (2 3 4))
(1 (2 3 4))

Built-In Procedures for Lists

There are a few other built-in procedures in Scheme that are used for lists. Try them out in the interpreter!

scm> (null? nil)                ; Checks if a value is the empty list
True
scm> (append '(1 2 3) '(4 5 6)) ; Concatenates two lists
(1 2 3 4 5 6)
scm> (length '(1 2 3 4 5))      ; Returns the number of elements in a list
5