# Study Guide: Scheme

## Instructions

This is the companion guide to Quiz 8 with links to past lectures, assignments, and handouts, as well as isomorphic quiz problems and additional practice problems to assist you in learning the concepts.

**Assignments**

**Handouts**

**Lectures**

**Readings**

# Guides

Computer science is not just about writing programs, but also understanding how they behave. We learned in the first week of class about the Python programming language and its expressive syntax. We saw how we could pose questions to the Python interpreter and how we could define functions that teach Python how to solve more and more complex problems.

Underlying all of the evaluation rules, we also learned about several different programming paradigms in Python by composing functions together, creating compound values and data abstractions with lists and dictionaries, and modeling those data abstractions using object-oriented programming.

But these aren't the only programming paradigms that exist and Python isn't the only language that we use to solve problems. We learn about Scheme to help answer both of these questions: what are the ways of thinking that transfer between languages, and how a computer understands programs.

## Scheme

Scheme is like Python in some ways and unlike it in others. Like Python, Scheme is an interpreted language so we can always ask questions in the interpreter.

```
scm> 1
1
scm> #t
#t
scm> 'symbol
symbol
```

Like Python, Scheme has a similar set of familiar data types like numbers,
booleans, strings, and an unfamiliar type, *symbols*. There are also call
expressions, which evaluate using the same evaluation procedure as in Python.

```
scm> (+ 1 2)
3
scm> (not #t)
#f
```

An expression enclosed in parentheses is called a *combination*, but not all
combinations are call expressions!

```
scm> (if (= 1 2)
(/ 1 0)
#f)
#f
```

Some combinations, like the `if`

special form, look like call expressions, but
have very unique logic. If `if`

were a call expression, we would the operator
and each operand, which isn't what happens here. Instead, the `if`

special form
follows its own set of evaluation rules by first evaluating the condition and
then chooses the corresponding consequent based on the truth value of the
condition.

### Pairs

Scheme has a simple data type for representing compound values, the `pair`

. Any
value can go in the first or second field of a pair and we can compose pairs
together to create *nested data types* (like trees!) and *lists*.

```
scm> (cons 1 2)
(1 . 2)
```

What's going on here? `cons`

creates a pair where 1 is the first and 2 is the
second value of the pair. Scheme then needs to figure out how to display this
pair back to the interpreter. Just like how the Python interpreter calls the
`__repr__`

method to determine what to show to the user, Scheme follows a
similar procedure to determine how to represent the pair structure.

In general, a pair is displayed in the following format.

```
scm> (cons 'first 'second)
(first . second)
```

The dot separates the two values in the pair. Nested pairs are also nested in their representation.

```
scm> (cons (cons 'first 'second) 'third)
((first . second) . third)
```

...except if the nesting happens in the second field, because the resulting
structure is considered a *list* so we instead use a more streamlined notation.

```
scm> (cons 'first (cons 'second 'third))
(first second . third)
```

We can think of this as a simplification of the following representation.

`(first . (second . third)) -> (first second . third)`

We can also play around with how we compose pairs to get yet other examples.

```
scm> (cons (cons 'first 'second) (cons 'third 'fourth))
((first . second) third . fourth)
```

### Problem-Solving

Code-writing in Scheme follows the same overarching problem-solving strategy
we've been honing all semester long, just with additional rules. Scheme
encourages us to write programs in a *functional style* by composing together
several small programs, each solving a single problem, but which combine to
solve a larger problem. Think of this as yet another form of *abstraction*,
except now at the scale of how we organize programs as a whole!

Practically-speaking, there are a couple of restrictions we need to be cognizant of when writing Scheme programs as they'll require us to change the way we solve problems.

One part will require us to grapple with how we come up with *algorithms*, or
step-by-step solutions.

- Scheme data types are (mostly) immutable. The values of compound data types like pairs can't be easily changed.
- Scheme does not support iteration. We use recursion and helper procedures instead.

The other will affect how we convert the algorithm or idea into code.

Scheme prefers a composition of function calls. Scheme syntax is all expressions, which means that even special forms like

`if`

can be nested and composed in useful ways. (Remember that in Python, we can't drop an`if`

block statement in the middle of a function call!)scm> (define x 1) x scm> (+ 1 (if (= x 1) 1 2)) 2

We'll usually define several small procedures. The procedures we define tend to have a well-defined domain and range, and their behavior can be explained in simple words.

We might, for example, want to remove all the duplicate values in a list. Based on the algorithm restrictions, we know we can't mutate the original list, so our only other option is to return a new list containing the unique values. We can use recursion to traverse down the list, checking each item to see whether or not it's a unique value. From here, the idea can vary in two directions depending on whether we want to filter the remaining values, or check backwards and add to our growing list of unique values if it's not already there.

# Practice Problems

## Easy

### Q1: all-satisfies

Implement a function `(all-satisfies lst pred)`

that returns `True`

if all of
the elements in `lst`

satisfy `pred`

.

```
(define (all-satisfies lst pred)
'YOUR-CODE-HERE
(if (null? lst)
True
(and (pred (car lst))
(all-satisfies (cdr lst) pred))))
;;; Tests
(all-satisfies nil even?)
; expect True
(all-satisfies '(2 4 6) even?)
; expect True
(all-satisfies '(2 3 6) even?)
; expect False
(all-satisfies '((1 2) (3 4 5) (6)) pair?)
; expect True
```

## Medium

### Q2: Interleave

Implement the function interleave, which takes a two lists as arguments. interleave will return a new list that interleaves the elements of the two lists, with list1 starting first. Refer to the tests for sample input/output.

```
(define (interleave list1 ist2)
; BEGIN SOLUTION
(if (or (null? list1) (null? list2))
(append list1 list2)
(cons (car list1)
(cons (car list2)
(interleave (cdr list1) (cdr list2))))))
; END SOLUTION
(interleave (list 1 3 5) (list 2 4 6))
; expect (1 2 3 4 5 6)
(interleave (list 1 3 5) nil)
; expect (1 3 5)
(interleave (list 1 3 5) (list 2 4))
; expect (1 2 3 4 5)
```

### Q3: Matching

Implement `num-adjacent-matches`

, which takes as input a list of
numbers `s`

and returns the number of adjacent elements that are equal.

```
(define (num-adjacent-matches s)
'YOUR-CODE-HERE
(if (or (null? s) (null? (cdr s)))
0
(+ (num-adjacent-matches (cdr s))
(if (= (car s) (cadr s)) 1 0))))
;;; Tests
; no pairs
(num-adjacent-matches '(1 2 3 4))
; expect 0
; one pair of 1's
(num-adjacent-matches '(1 1 2 3))
; expect 1
; one pair of 1's, one pair of 2's
(num-adjacent-matches '(1 1 2 2))
; expect 2
; three pairs of 1's
(num-adjacent-matches '(1 1 1 1))
; expect 3
(num-adjacent-matches '(6 6 6 1 6 1))
; expect 2
(num-adjacent-matches '(6))
; expect 0
(num-adjacent-matches '(6 1))
; expect 0
(num-adjacent-matches '(6 1 6 1 6 1))
; expect 0
(num-adjacent-matches '(6 6))
; expect 1
(num-adjacent-matches '(6 6 6 1 6 1))
; expect 2
(num-adjacent-matches '(0 1 6 6 6 1))
; expect 2
(num-adjacent-matches '(4 4 3 3 2 2 1 1))
; expect 4
```

Our base cases are when our input list `s`

is too short to have any adjacent
matches. We call `num-adjacent-matches`

recursively on `(cdr s)`

to count the
adjacent matches in the rest of the list `s`

, then add 0 or 1 depending on
whether the first and second elements of `s`

are equal.

### Q4: Split

Implement `split-at`

, which takes a list `lst`

and a positive number `n`

as
input and returns a pair `new`

such that `(car new)`

is the first `n`

elements of `lst`

and `(cdr new)`

is the remaining elements of `lst`

. If `n`

is
greater than the length of `lst`

, `(car new)`

should be `lst`

and `(cdr new)`

should be `nil`

.

```
(define (split-at lst n)
'YOUR-CODE-HERE
(cond ((= n 0) (cons nil lst))
((null? lst) (cons lst nil))
(else (let ((rec (split-at (cdr lst) (- n 1))))
(cons (cons (car lst) (car rec)) (cdr rec))))))
```

Use Ok to test your code:

`python3 ok -q split-at`