Chapter Notes

 

Chapter 1

Feel free to get this note section started! Questions, comments, insights - all of it's good!

 

Building Abstrations with Procedures -

 

1.1 The Elements of Programming

 

• primitive expressions - the simplest entities the language is concerned with
• means of combination - compound elements are built from simpler ones
• means of abstraction - compound elements can be named and manipulated as units

Two kinds of elements - procedures and data (not really so different).

 

 

 

1.1.1 Expressions

 

One type of primitive experssion is a number. Experssions representing numbers can be combined with a primitive procedure expersion (+ * - /) to form a compound expression.

 

Examples:

(+ 5 4)

9

 

(* 5 5 )

25

 

These compound expressions are a list delimited by parentheses and are called combinations.

 

The leftmost element in the combination is the operator and the rest of the elements are the operands. 

 

Prefix notation is the convention of placing the operator to the left of the operands.

 

 

1.1.2 Naming and the Environment

 

A name identifies a variable whose value is the object.

 

In Scheme you name things with define.

 

Define is Scheme's simplest means of abstraction and allows the use of simple names for compound operations.

 

 

 

1.1.3 Evaluating Combinations

 

• To evaluate a combination, do the following:

1. Evaluate the subexperssions of the combination.
2. Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

1.1.4 Compound Porocedures

 

procedure definitions - abstraction technique by which a compound operation can be given a name and then referred to as a unit.

 

Example: (define (square x) (* x x))

 

Used exactly the same way as primitive procedures:

(square 5)

25

 

1.1.5 The Substitution Model for Procedure Application 

 

• To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

For example, these procedures being defined:

(define (sum-of-squares x y)

    (+ (square x) (square y)))

(define (f a)

    (sum-of-squares (+ a 1) (* a 2)))

 

The procedure

(f 5)

reduces to

(sum-of-squares (+ 5 1) (* 5 2))

(+ (square 6) (square 10))

(+ (* 6 6) (* 10 10))

(+ 36 100)

136

 

We can use the substitution model to think about procedure application.

Applicative order versus normal order