These are notes on *Structure and Interpretation of Computer Programs*.

# Building Abstractions with Procedures

## Combinations

Lisp ** combinations** are written using

**:**

*prefix form*```
(operator operand1 operand2 ...)
```

The operator and operands above may themselves be combinations or perhaps
** atoms** (

*e.g.*numbers, symbols, procedures). Every combination "reduces" to an atom.

For example, the mathematical expression

may be represented as follows:

```
;; Evals to -37 / 150
(/
(+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5)))))) ;; numerator
(* 3 (* (- 6 2) (- 2 7)))) ;; denominator
```

(*Exercise 1.2*)

## Symbols, Evaluations

Defining symbols is done using the `define`

operator

```
(define <sym> <expr>)
```

Whenever a combination involving `sym`

is * evaluated*,

`sym`

is replaced by
`expr`

. Since `expr`

may itself involve symbols, this process continues until
only primitives exists. This is the "expansion phase".
The application of operators on evaluated operands will also result in a lisp expression. This is the "reduction phase".

** Normal-order evaluation** fully expands (but not evaluates)
all expressions before reduction.

** Applicative-order evaluation** fully evaluates each expression before reduction.

## Branching

Lisp/Scheme provides two branching operators, `if`

and `cond`

```
(if <boolexpr> <branch1> <branch2>)
```

The above combination evaluates to `branch1`

if `boolexpr`

evaluates to `#t`

("true").
Else, it evaluates to `branch2`

.

`cond`

works similarly:

```
(cond
(<boolexpr1> <branch1>)
(<boolexpr2> <branch2>)
...)
```

If nonte of the above boolean expressions (or ** predicates** are defined), then
the

`cond`

combination is undefined.
## Procedures

Procedures are connstructed using the `lamdba`

operator.

```
(lambda (<sym1> <sym2> ...) <expr>)
```

Lambda expressions themselves produce operators. When applied to operands and
evaluated, those operands are substituted for the above symbol list (the ** arguments**)
are substituted in

`expr`

(the **).**

*body*Lambdas may have any number of arguments, including zero.

Lambdas are first-class objects in Lisp. This means:

- They can be named
- They can be used as arguments to procedures
- They can be returned from procedures
- They can be members of data structures

Naming lambdas can be done using `define`

in two ways

```
;; using define in the typical manner
(define <name> (lambda (<arg1> <arg2> ...) <body>))
;; syntax sugar for above
(define (<name> <arg1> <arg2> ...) <body>)
```

For example, the following `sos-largest-numbers`

procedure takes three numerical
arguments and returns the sum of the square of the largest two:

```
(define (sos-largest-numbers x y z)
(- (+ (sq x) (+ (sq y) (sq z)))
(sq (min3 x y z))))
(define (sq x) (* x x))
(define (min3 x y z)
(min2 (min2 x y) z))
(define (min2 x y)
(if (> x y) y x))
(sos-largest-numbers 3 8 7) ;; => 113
```

(*Exercise 1.3*)

This example exhibits the ** black box** principle of software design. The

`sos-largest-numbers`

function was written before `sq`

and `min3`

. It didn't
matter *how*these functions were implemented, provided that they were implemented

*correctly*with regards to their expected behavior. If this so, then these procedures could even be delegated to different programmers.

## Recursion, Iteration

Procedures can reference themselves. This is known as ** recursion**.

Consider the following two procedures, one to calculate the factorial of a positive integer, the other to calculate a term in the fibonacci sequence:

```
(define (factorial1 n)
(if (= n 1)
1
(* n (factorial1 (- n 1)))))
(define (factorial2 n)
(define (iter prod cnt max-cnt)
(if (> cnt max-cnt)
prod
(iter (* cnt prod) (+ cnt 1) max-cnt)))
(iter 1 1 n))
(- (factorial1 6) (factorial2 6)) ;; => 0
```

Evaluating `factorial1`

requires $O(n)$ expansions. And thus the interpreter must account for $O(n)$ variables. In contrast,
`factorial2`

only needs $O(1)$ variables to evaluate. This is called
an ** iterative process**. Note the difference between process and
procedures. Both procedures are recursive.

Not all recursive procedures can be easily translated to iterative processes. For example, the following inefficiently calculates fibonacci numbers:

```
(define (fib n)
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
```

This takes exponential time (rather, $O(\text{fib}(n))$ time).

## Higher-Order Procedures

Lambdas may be supplied input arguments or returned from other lambdas. When a
lambda does both, it is called a ** higher-order procedure**.

For example, the following defines a `integrate`

procedure that calculates the
via simpson's rule. It used layers of higher-ordered functions.

```
(define (integrate fn a b)
(simpsons-rule fn a b 1000))
(define (simpsons-rule fn a b n)
(define (incr n) (+ n 1))
(define (term n) ;; 1,4,2,1,4,2,...
(define m (modulo n 3))
(cond
((= m 1) 1)
((= m 2) 4)
((= m 3) 2)))
(define h (/ (- b a) n))
(* (/ h 3) (sum term 1 incr n)))
;; sums up term(n) for n ranging from a, next(a), next(next(a)), ... up to b.
(define (sum term a next b)
(accumulate + 0 term a next b))
;; iterative function fo accumulating a "combiner" function
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner result (term a)))))
(iter a null-value))
;; test
(define (cube x) (* x (* x x))) ;; anti-derivative = 1/4 x^4
(integrate cube 0 2) ;; => ~ 81/4
```

(*Exercise 1.32* and *Exercise 1.29*)

`let`

construct

TODO