# Discussion 9: Scheme, Scheme Lists

# Introduction

In the next part of the course, we will be working with the **Scheme**
programming language. In addition to learning how to write Scheme programs, we
will eventually write a Scheme interpreter in Project 4!

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 a prefix notation and (often many) nested parentheses (see http://xkcd.com/297/). Scheme features first-class functions and optimized tail-recursion, which were relatively new features at the time.

# Primitives and Defining Variables

Scheme has a set of **atomic** primitive expressions. Atomic means
that these expressions cannot be divided up.

```
scm> 123
123
scm> #t
True
scm> #f
False
```

Unlike in Python, the only primitive in Scheme that is a false value is
`#f`

and its equivalents, `false`

and `False`

. **This means that 0 is not false.**

The `define`

special form defines variables and procedures by binding a
value to a variable, just like the assignment statement in Python. When a
variable is defined, the `define`

special form returns a symbol of its
name. A procedure is what we call a function in Scheme.

The syntax to define a variable and procedure are:

`(define <variable name> <value>)`

`(define (<function name> <parameters>) <function body>))`

Special forms are types of expressions with unique evaluation rules that
can do a variety of things. Often times, speical forms are analagous to
statements in Python, such as assignment statements, `if`

statements,
and `def`

statements. However, all special forms in Scheme evaluate to a value.
We'll learn more about special forms later in the discussion.

## Questions

`scm> (define a 1)`

`scm> a`

`scm> (define b a)`

`scm> b`

`scm> (define c 'a)`

`scm> c`

# Call Expressions

Call expressions apply a procedure to some arguments.

`(<operator> <operand1> <operand2> ...)`

Call expressions in Scheme work exactly like they do in Python. To evaluate them:

- Evaluate the operator to get a procedure.
- Evaluate each of the operands from left to right.
- Apply the value of the operator to the evaluated operands.

For example, consider the call expression `(+ 1 2)`

. First, we evaluate
the symbol `+`

to get the built-in addition procedure. Then we evaluate
the two operands `1`

and `2`

to get their corresponding atomic
values. Finally, we apply the addition procedure to the values `1`

and
`2`

to get the return value `3`

.

Operators may be symbols, such as `+`

and `*`

, or more
complex expressions, as long as they evaluate to procedure values.

```
scm> (- 1 1) ; 1 - 1
0
scm> (/ 8 4 2) ; 8 / 4 / 2
1
scm> (* (+ 1 2) (+ 1 2)) ; (1 + 2) * (1 + 2)
9
```

Some important built-in functions you'll want to know are:

`+`

,`-`

,`*`

,`/`

`=`

,`>`

,`>=`

,`<`

,`<=`

`quotient`

,`modulo`

,`even?`

,`odd?`

,`null?`

## Questions

What would Scheme display? As a reminder, the built-in `quotient`

function performs floor division.

`scm> (define a (+ 1 2))`

`scm> a`

`scm> (define b (- (+ (* 3 3) 2) 1))`

`scm> (+ a b)`

`scm> (= (modulo b a) (quotient 5 3))`

# Special Forms

Special form expressions contain a **special form** as the operator.
Special form expressions *do not* follow the same rules of evaluation as
call expressions. Each special form has its own rules of evaluation -- that's
what makes them special!

## If Expression

An `if`

expression looks like this:

`(if <predicate> <if-true> [if-false])`

`<predicate>`

and `<if-true>`

are required expressions and
`[if-false]`

is optional.

The rules for evaluation are as follows:

- Evaluate
`<predicate>`

. - If
`<predicate>`

evaluates to a truth-y value, evaluate`<if-true>`

and return its value. Otherwise, evaluate`[if-false]`

if provided and return its value.

This is a special form because not all operands will be evaluated! Only one of the second and third operands is evaluated, depending on the value of the first operand.

Remember that only `#f`

is a false-y value in Scheme; everything else
is truth-y.

```
scm> (if (< 4 5) 1 2)
1
scm> (if #f (/ 1 0) 42)
42
```

## Boolean operators

Like Python, Scheme also has the boolean operators `and`

,
`or`

, and `not`

. `and`

and `or`

are
special forms because they are short-circuiting operators.

`and`

takes in any amount of operands and evaluates these operands from left to right until one evaluates to a false-y value. It returns that first false-y value. If there are no false-y values, it returns the value of the last expression (or`#t`

if there are no operands)`or`

also evaluates any number of operands from left to right until one evaluates to a truth-y value. It returns that first truth-y value. If there are no truth-y values, it returns the value of the last expression (or`#f`

if there are no operands)`not`

takes in a single operand, evaluates it, and returns its opposite truthiness value. Note that`not`

is a regular procedure and not a special form.

*Important note: the only false-y value in scheme is #f. In particular, 0 is truth-y!*

```
scm> (and 25 32)
32
scm> (or 1 (/ 1 0)) ; Short-circuits
1
scm> (not (odd? 10))
#t
```

## Questions

What would Scheme display?

`scm> (if (or #t (/ 1 0)) 1 (/ 1 0))`

`scm> ((if (< 4 3) + -) 4 100)`

# Lambdas and Defining Functions

All Scheme procedures are lambda procedures. One way to create a procedure is
to use the `lambda`

special form.

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

This expression creates a lambda function with the given parameters and body,
but does not evaluate the body. Just like in Python, the body is not
evaluated until the function is called and applied to some argument
values. The fact that neither operand is evaluated is what makes
`lambda`

a special form.

Another similarity to Python is that lambda expressions do not assign the
returned function to any name. We can assign the value of an expression to a
name with a `define`

special form.

For example, `(define square (lambda (x) (* x x)))`

creates a lambda
procedure that squares its argument and assigns that procedure to the name
`square`

.

The second version of the `define`

special form is a shorthand for this
function definition:

`(define (<name> <param1> <param2 ...>) <body>)`

This expression creates a function with the given parameters and body
*and* binds it to the given name.

```
scm> (define square (lambda (x) (* x x))) ; Bind the lambda function to the name square
square
scm> (define (square x) (* x x)) ; Equivalent to the line above
square
scm> square
(lambda (x) (* x x))
scm> (square 4)
16
```

## Questions

### Q1: Factorial

Write a function that returns the factorial of a number.

Run in 61A Code### Q2: Fibonacci

Write a function that returns the `n`

-th Fibonacci number.

```
scm> (fib 0)
0
scm> (fib 1)
1
scm> (fib 10)
55
```

# Pairs and Lists

All lists in Scheme are linked lists. Scheme lists are composed of two element pairs. We define a list as being either

- the empty list,
`nil`

- a pair whose second element is a list

As in Python, linked lists are recursive data structures. The base case is the empty list.

We use the following procedures to construct and select from lists:

`(cons first rest)`

constructs a list with the given first element and rest of the list. For now, if`rest`

is not a pair or`nil`

it will error.`(car lst)`

gets the first item of the list`(cdr lst)`

gets the rest of the list

To visualize Scheme lists, you can use the `draw`

function in code.cs61a.org.
The list from the example below is loaded here.

```
scm> nil
()
scm> (define lst (cons 1 (cons 2 (cons 3 nil))))
lst
scm> lst
(1 2 3)
scm> (car lst)
1
scm> (cdr lst)
(2 3)
scm> (car (cdr lst))
2
scm> (cdr (cdr (cdr lst)))
()
```

The rule for displaying lists is very similar to that for the `Link`

class from earlier in the class's `__str__`

method. It prints out the elements in the linked list as if the list has no nested structure. The only difference is that `Link.__str__`

uses angle brackets `<>`

and scheme uses parentheses `()`

.

Try drawing out the lists below yourself, then check your answer.

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

Two other common ways of creating lists is using the built-in `list`

procedure or the `quote`

special form:

- The
`list`

procedure takes in an arbitrary amount of arguments. Because it is a procedure, all operands are evaluated when`list`

is called. A list is constructed with the values of these operands and is returned. - The
`quote`

special form takes in a single operand. It returns this operand exactly as is, without evaluating it. Note that this special form can be used to return any value, not just a list.

```
scm> (define x 2)
scm> (define y 3)
scm> (list 1 x 3)
(1 2 3)
scm> (quote (1 x 3))
(1 x 3)
scm> '(1 x 3) ; Equivalent to the previous quote expression
(1 x 3)
scm> '(+ x y)
(+ x y)
```

## =, eqv?, equal?

`=`

can only be used for comparing numbers.`eqv?`

behaves like`==`

in Python for comparing two non-pairs (numbers, booleans, etc.). Otherwise,`eqv?`

behaves like the Python`is`

operator.`equal?`

compares pairs by determining if their`car`

s are`equal?`

and their`cdr`

s are`equal?`

(that is, they have the same contents). Otherwise,`equal?`

behaves like`eqv?`

.

```
scm> (define a '(1 2 3))
a
scm> (= a a)
Error
scm> (equal? a '(1 2 3))
#t
scm> (eqv? a '(1 2 3))
#f
scm> (define b a)
b
scm> (eqv? a b)
#t
```

## Questions

### Q3: Warm-up

These short questions are meant to help refresh your memory of topics covered in lecture and lab this week before tackling more challenging problems.

Describe the difference between the following two Scheme expressions. (Hint: which defines a new procedure?)

Expression A:

`(define x (+ 1 2 3))`

Expression B:

`(define (x) (+ 1 2 3))`

Write an expression that selects the value 3 from the list below.

`(define s '(5 4 (1 2) 3 7))`

### Q4: List Making

Let's make some Scheme lists. We'll make the same list with `list`

, `quote`

, and `cons`

.

The following list was visualized using the `draw`

feature of code.cs61a.org.

First, use `list`

:

Now use `quote`

. What differences are there?

Now try with `cons`

. For convenience, we've defined a `helpful-list`

and `another-helpful-list`

:

### Q5: List Concatenation

Write a function which takes two lists and concatenates them.

Notice that simply calling `(cons a b)`

would not work because it will
create a deep list. Do not call the builtin procedure `append`

, since it
does the same thing as `list-concat`

should do.

```
scm> (list-concat '(1 2 3) '(2 3 4))
(1 2 3 2 3 4)
```

### Q6: List Duplicator

Write a Scheme function that, when given a list, such as `(1 2 3 4)`

,
duplicates every element in the list (i.e. `(1 1 2 2 3 3 4 4)`

).

### Q7: List Insert

Write a Scheme function that, when given an element, a list, and an index, inserts the element into the list at that index. You can assume that the index is in bounds for the list.

Run in 61A Code# Exam Prep

### Reminder about eval

A very useful special form in scheme is eval, which when given a scheme list, evaluates it as if it were scheme source code.

```
scm> (eval (list 'cons 1 (list 'cons 2 '())))
(1 2)
scm> (eval '(+ 1 2))
3
scm> (define a 'b)
a
scm> (define b 'c)
b
scm> (define c 5)
c
scm> (eval 'a)
b
scm> (eval (eval 'a))
c
scm> (eval (eval (eval 'a)))
5
```

You will find understanding how eval works useful for the problems below.

### Q8: Directions - Fall 2014 Final Q4(c)

**Difficulty:** ⭐⭐

Implement the Scheme procedure `directions`

, which takes a number `n`

and a symbol `sym`

that is
bound to a nested list of numbers. It returns a Scheme expression that evaluates to `n`

by repeatedly applying
`car`

and `cdr`

to the nested list. Assume that `n`

appears exactly once in the nested list bound to `sym`

.

**Hint:** The implementation searches for the number `n`

in the nested list `s`

that is bound to `sym`

. The returned
expression is built during the search.

```
scm> (define a ’(1 (2 3) ((4))))
scm> (directions 1 ’a )
(car a)
scm> (directions 2 ’a)
(car (car (cdr a)))
```

Run in 61A Code
### Q9: Group by Non-Decreasing

**Difficulty:** ⭐⭐⭐

Define a function `nondecreaselist`

, which takes in a scheme list of numbers and outputs a list of lists, which overall has the same numbers in the same order, but grouped into lists that are non-decreasing.

For example, if the input is a stream containing elements

`(1 2 3 4 1 2 3 4 1 1 1 2 1 1 0 4 3 2 1)`

the output should contain elements

`((1 2 3 4) (1 2 3 4) (1 1 1 2) (1 1) (0 4) (3) (2) (1))`

**Hint:** You might want to review the nesting list structure in partition options from examprep 07

**Note:** The skeleton code is just a suggestion; feel free to use your own structure if you prefer.