# CS 61A: Structure and Interpretation of Computer Programs¶

**ðŸ“– COURSE-STARTED-AT**: 2023-11-14

**ðŸ”® COURSE-FINISHED-AT**: 2023-12-4

**ðŸ”— COURSE-SITE**: inst.eecs.berkeley.edu/~cs61a/su20

In CS 61A, we are interested in teaching you about programming, not about how to use one particular programming language. We consider a series of techniques for controlling program complexity, such as functional programming, data abstraction, and object-oriented programming.

â€”â€”CS 61A

The course website I followed is a bit old (I realized it when I almost finished the course). You can find the latest version at cs61a.org.

## Higher-Order Functions¶

### HW 02 Q4: Church numerals¶

The homework HW 02 Q4: Church numerals introduced a very interesting concept called *Church numerals*. I'd like to note it down.

The logician Alonzo Church invented a system of representing non-negative integers entirely using functions. The purpose was to show that functions are sufficient to describe all of number theory: if we have functions, we do not need to assume that numbers exist, but instead we can invent them.

Using \(\lambda\)-functions in python, we have the following definitions:

```
def zero(f):
return lambda x: x
def successor(n): # n is a church numeral
return lambda f: lambda x: f(n(f)(x))
```

Both `zero(f)`

and `successor(n)`

are *higher-order functions*, they take functions as arguments and return functions as results.

The `successor(n)`

function may look scary, but it's actually pretty straight-forward. `n`

is a function that takes `f`

in and returns another function that takes `x`

in. So `n`

is technically the same as `lambda f: lambda x: n(f)(x)`

. What `successor(n)`

does is just to wrap another layer of `f`

to `n`

.

From the explanation above, we see that the number of `f`

s is simply the corresponding integer. Rather than defining `one(f)`

as `successor(zero)`

and `two(f)`

as `successor(one)`

, we can also use:

Then it's easy to implement `church_to_int(n)`

function:

Let's examine how to add two Church numerals together. For example, by adding `two(f)(x) = f(f(x))`

and `one(f)(x) = f(x)`

together, we should get `three(f)(x) = f(f(f(x)))`

. The answer is to take `one`

and plug it into `x`

of `two(f)(x)`

: `two(f)(one(f)(x))`

. The code would be:

Then we try multiplication. The idea is to plug `n`

into `f`

of `m(f)(x)`

.

The most challenging task is to implement power.

You can verify this by plugging in some numbers.

### HW 03 Q6: Anonymous factorial¶

Another interesting quiz I found is HW 03 Q6: Anonymous factorial.

The recursive factorial function can be written as a single expression by using a conditional expression.

Note that this implementation relies on the *fact* that `fact`

has a name. Is there a way to define `fact`

recursively without giving it a name?

The task is to implement an anonymous function that computes the factorial of `n`

using **only** call expressions, conditional expressions, and lambda expressions (no assignment or def statements). You may also use `-`

and `*`

operators.

How the non-anonymous factorial function works is that inside each layer of recursion, the function `fact`

itself can always be called. Thus, we come up with the idea to **pass the function itself as an argument** to the function.

So the answer would be:

The logic behind this quiz is something called *Y Combinator*. Y Combinator is a method to turn a non-anonymous recursive function into an anonymous one. Here's one example:

```
def Y(f):
return (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))
fact = Y(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))
fact(5) # 120
```

A full introduction to Y Combinator can be found in Y Combinator Notes, you may need to read Introduction to Lambda Calculus first.

## Data Abstraction¶

The way to implement data abstraction in python is way easier than in C++. Here's an example to construct a tree (which is actually nested lists):

```
def tree(label, branches = []):
for branch in branches:
assert is_tree(branch)
return [label] + list(branches)
def label(tree):
return tree[0]
def branches(tree):
return tree[1:]
def is_tree(tree):
if type(tree) != list or len(tree) < 1:
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return True
def is_leaf(tree):
return not branches(tree)
```

To construct a Fibonacci tree, we simply use:

```
def fib_tree(n):
if n == 0 or n == 1:
return tree(n)
left = fib_tree(n - 2)
right = fib_tree(n - 1)
fib_n = label(left) + label(right)
return tree(fib_n, [left, right])
```

That's it. A newly-baked Fibonacci tree, in a few lines. (I'm lovin' python)

## Mutation¶

Here's a piece of code, pay attention how `a`

behaves.

You may expect `a`

to be `[1, 2]`

, but it's not. The reason is that `a`

and `b`

are both *names* that refer to the same *object*. When we call `b.append(3)`

, we are actually ** mutating** the object that

`a`

refers to. Thus, `a`

is also changed.Using mutations, we can do some magic:

The `magic`

function above behaves pretty C-ish, compare it with the following C code:

```
void magic(int x[]) {
x[0] = 1;
}
int main() {
int a[] = {0, 2};
magic(a);
printf("{%d, %d}", a[0], a[1]); // {1, 2}
}
```

In python, types are classified into two categories:

- Mutable types:
`list`

,`dict`

,`set`

,`bytearray`

, etc. - Immutable types:
`int`

,`float`

,`bool`

,`str`

,`tuple`

,`frozenset`

,`bytes`

, etc.

Note that `tuple`

is immutable, but it *can* contain mutable objects.

`is`

operator can be used to check whether two names refer to the same object. And `==`

checks whether two objects are equal.

```
>>> a = [1, 2, 3]
>>> b = [1, 2, 3]
>>> c = a
>>> a == b # True
>>> a == c # True
>>> a is b # False
>>> a is c # True
```

In this case, `a`

and `b`

are two different objects that *happened* to hold the same value, while `a`

and `c`

are literally the same object.

Mutable objects can be used as dictionary keys, but immutable objects cannot.

Mutable default arguments are dangerous. Consider the following code:

The default argument `x = []`

is evaluated only once, when the function is defined. Thus, every time we call `f()`

, we are actually appending `0`

to the same list.

## Nonlocal¶

The `nonlocal`

statement is used to indicate that a variable is defined in the parent's local scope. Consider the following code:

The error is caused by the fact that `n`

is not defined in the local scope of `f`

. To fix this, we use `nonlocal`

:

Such statement is very useful for implementing *closures*.

```
>>> def make_inc(n):
... def inc(k):
... nonlocal n
... n += k
... return n
... return inc
...
>>> inc = make_inc(0)
>>> inc(10)
10
>>> inc(10)
20
>>> inc(10)
30
```

## Iterators & Generators¶

### Iterators¶

`iter`

function takes an *iterable* object and returns an *iterator*. `next`

function takes an iterator and returns the next item in the iterable object. When there's no more item, `next`

raises a `StopIteration`

exception.

```
>>> t = iter([1, 2])
>>> s = t
>>> next(t)
1
>>> next(s) # Iterators are mutable.
2
>>> next(t) # StopIteration
```

Some built-in functions like `map`

, `filter`

, `zip`

return iterators.

```
>>> t = map(lambda x: x ** 2, [1, 2, 3])
>>> next(t)
1
>>> next(t)
4
>>> next(t)
9
>>> next(t) # StopIteration
```

Note that such functions are *lazy*, they don't compute the whole list at once. Instead, they compute the next item only when it's needed.

```
>>> def check(x):
... print("Checking", x)
... return x * x >= 10
...
>>> t = filter(check, range(6)) # No output yet
>>> next(t)
Checking 0
Checking 1
Checking 2
Checking 3
Checking 4
4
>>> next(t)
Checking 5
5
>>> next(t) # StopIteration
```

### Generators¶

A *generator* is a function that returns an *iterator*. It looks like a normal function, but it contains `yield`

statements.

```
>>> def naturals():
... n = 0
... while True:
... yield n
... n += 1
...
>>> t = naturals()
>>> next(t)
0
>>> next(t)
1
>>> next(t)
2
```

Generators are also *lazy*. This is why `naturals`

doesn't run into an infinite loop.

`yield from`

is another special syntax that allows a generator to yield all values from another generator. You can consider it a syntax sugar for nested loops. For example,

is equivalent to:

### HW 05 Q6: Remainder Generator¶

The homework HW 05 Q6: Remainder Generator asks us to implement `remainders_generator`

. This is an easy task but it helps to understand iterators and generators.

`remainders_generator`

takes in an integer`m`

, and yields`m`

different generators. The first generator is a generator of multiples of`m`

, i.e. numbers where the remainder is 0. The second is a generator of natural numbers with remainder 1 when divided by`m`

. The last generator yields natural numbers with remainder`m - 1`

when divided by`m`

.

In short, `remainders_generator`

yields all the congruence classes of `m`

.

For instance, `remainders_generator(4)`

should yield:

```
>>> for r in remainders_generator(4):
... print([next(r) for _ in range(5)])
...
[4, 8, 12, 16, 20]
[1, 5, 9, 13, 17]
[2, 6, 10, 14, 18]
[3, 7, 11, 15, 19]
```

Here is my implementation:

```
def remainders_generator(m):
def remainder(r):
if r == 0: r += m
while True:
yield r
r += m
for r in range(m):
yield remainder(r)
```

## Scheme¶

Scheme is a dialect of Lisp. For the syntax and language features, refer to Scheme notes.

The task is to build a Scheme interpreter, in python. I won't go into details here, but I'd like to note down some important parts.

Interpreting a piece of code follows the following procedures:

- Input
- Tokenize
- Parse
- Evaluate

```
Input = '(even? (* (+ 1 2) 3 4))'
Token = ['(', 'even?', '(', '*', '(', '+', '1', '2', ')', '3', '4', ')', ')']
Parsed = CallExpr(Name('even?'),
[CallExpr(Name('*'),
[CallExpr(Name('+'),
[Literal(1), Literal(2)]),
Literal(3), Literal(4)])])
Evaluation = True
Print = '#t'
```

Another thing to mention is that Scheme also have environment frames. When evaluating an expression, the current environment frame should be passed to the `eval`

function.

## SQL¶

I skipped this part since I would like to learn it systematically in database courses.

Created: 2023-11-14