- toc {:toc}

primitive expression

- number:
`486`

- primitive operators (are also procedures):
`< = > and or not`

- number:
compound expression

- application of some
**procedure**to some**arguments**:`(+ 1 2)`

- application of some

naming: assign name to something ("object")

- value:
`(define foo 1)`

- procedure:
`(define (bar arg1) (+ 1 2))`

- value:
environment: memory of name-object pairs

- a computation may involve multiple environments

steps of "applicative order"

- evaluate every subexpressions
- apply the leftmost subexpression ("operator") to the values of the other subexpressions ("operands")

- general form of procedure definition:

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

`The `<body>' part may contain multiple expressions. The value of the final expression becomes the value of the procedure application.`

evaluate the body of procedure with the formal parameters replaced by the corresponding arguments

is presented to help think about the process of application, and

**is not**how interpreter worksorder of execution

- normal order: "fully expand and then reduce"
- applicative order: "evaluate the arguments and then apply"
- lisp uses applicative order evaluation.

if

`if`

is a special form and not a procedure. It only evalutes the predicate and**one of**the consequent / alternative expression.`(if (> 1 0) #t #f)`

cond

`cond`

is a special form and not a procedure. It only evalutes the predicates till the correct branch, and that corresponding branch.`(cond ((= a 1) 1) ((= a 2) 3))`

code

`(define (newton-sqrt aim) (define (guess-till-good-enough current next-guess good-enough?) (if (good-enough? current) current (guess-till-good-enough (next-guess current) next-guess good-enough?))) (define (small-enough? delta) (< delta 1e-5)) (define (close-enough? current) (small-enough? (abs (- (* current current) aim)))) (define (better-approximation-of-sqrt current) (/ (+ current (/ aim current)) 2)) ;; << the ``Newton'' part (define initial-guess 1.1) (guess-till-good-enough initial-guess better-approximation-of-sqrt close-enough?)) (display (newton-sqrt 2.0)) ; => 1.4142`

The definition suppresses the details.

The user of a procedure does not need to know the internal.

Local names

- The formal parameters are
**local**to the body. AKA "bound variable" or "captured variable" - e.g.
`(define (square x) (* x x))`

contains a bound variable`x`

and a free variable`*`

. - The name of formal parameters can be arbitrary.

- The formal parameters are
Internal definitions (refer to previous

`newton-sqrt`

procedure)- One can localize subprocedures with nested
`define`

. - The free variable in inner procedure get its value from the bound variable of outer procedure, AKA
**lexical scoping**. - Example of lexical scoping:
`aim`

in`(define (close-enough? current <body>)`

.

- One can localize subprocedures with nested

Recursive computation of factorial

`(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))`

Iterative computation of factorial

`(define (factorial n) (define (factorial-iter cumulative-product current max) (if (> max current) cumulative-product (factorial-iter (* cumulative-product current) (+ current 1) max))) (factorial-iter 1 1 n))`

The preceding 2 procedures produce different

**shape of computation**.

Example: recursive definition of

`(fib n)`

Example: counting change

`(define (change coins rest) (cond ((< rest 0) 0) ((= rest 0) 1) ((= (length coins) 0) 0) (else (+ (change coins (- rest (car coins))) (change (cdr coins) rest))))) (display (change (list 50 25 10 5 1) 100)) ; => 292`

- refer to
**shape of computation**

implement

`(power base exp)`

with linear recursionimplement

`(power base exp)`

with log recursion- exercise 1.19: implement
`(fib n)`

with log recursion (let ((a 1)) (+ a 2))

- Euclid’s Algorithm

code

`(define (prime? n) (define (find-first-divisor current) (cond ((= (remainder n current) 0) current) ((> (* current current) n) #f) (else (find-first-divisor (+ 1 current))))) (define first-divisor (find-first-divisor 2)) (if (and first-divisor (not (= n first-divisor))) #f #t))`

`map`

`sum`

,`integral`

One can create (anonymous) procedures with the special form

`lambda`

usage

`(lambda (formal-parameters) <body>)`

example

`(map (lambda (x) (* x x)) '(1 2 3))`

One can use

`lambda`

to bind local variables, but the special form`let`

makes it more convenient.usage

`(let ((<name> <expression>)+) <body>)`

"is but syntactic sugar of underlying lambda expression"

The name-expression pairs in

`let`

are parallel. One expression cannot refer to another name.

Example: finding zero-point with the half-interval method

Example: finding fixed-point

- rights of
**first-class**elements- can be assigned a name
- can be passed as argument
- can be returned by procedure
- can be included in data structures