01 - Building Abstractions with Procedures

As no one is perfect, these notes won't be either.

1.1 - The Elements of Programming

Every powerful programming language (according to the authors) should give you three things:

• primitive elements: "stuff" to work with
• means of combination: ways to "combine" the stuff to make "new stuff"
• means of abstraction: ways to "name" the new stuff so we can refer to it later
  • (optionally) ways to name the "ways in which you create 'new stuff'" so you can use these later.

The authors then go on to explain why they chose lisp as the programming language. In part, because it provides mechanisms that satisfy each of these properties.

• primitive elements: numbers (1,2,12), operations (+, -, *, /)
• means of combination: you can combine operations through "nesting"

  (* (+ 1 2) (- 3 4))

• means of abstraction: you can use "define" to name a combination

  (define PI 3.14159)

  • (optionally) or a procedure

    (define (SQUARE x) (* x x))

Let's now look at each section briefly in turn. Note once again, I am mixing and matching topics. Part by accident, part on purpose.

• 1.1.1 Expressions: let us apply operations to elements.

• 1.1.2 Naming and the Environment: we can give these expressions names!

• 1.1.3 Evaluating Combinations: When we combine multiple expressions together via nesting, in what order do we evaluate?

  • Applicative Order: bias towards applying operations first.

      (+ (SQUARE 3) (SQUARE (+ 2 1)))
      (+ (SQUARE 3) (SQUARE 3))
      (+ (* 3 3) (* 3 3))
      (+ 9 9)
      18

    Notice that (+ 2 1) in the second operand is applied before we expand out the SQUARE procedure.
  • Normal Order: bias towards expansion

      (+ (SQUARE 3) (SQUARE (+ 2 1)))
      (+ (* 3 3) (* (+ 2 1) (+ 2 1)))
      (+ 9 (* 3 3))
      (+ 9 9)
      18

    Notice that we expand the SQUARE procedure before evaluating (+ 2 1).

  Lisp uses applicative order to avoid redundant computation and problems with mutation (discussed in later chapters).

• 1.1.4 Compound Procedures: we can tell our computer how to do something to a set of elements, and then give it a name.

• 1.1.5 The Substitution Model for Procedure Application: we intuitively used the substitution model in the evaluating combinations section. How do we do this for procedures? We "substitute" the arguments supplied to a procedure for ea. instance of a formal parameter in the body of the procedure. Then, we evaluate the altered procedure body.

• 1.1.6 Conditional Expressions and Predicates: if we want to change how a program behaves based on some condition, we need some mechanism to use in our procedures. The usual culprits show up here.

  • if, and, or, not, >, =, etc. cond lets you run a series of checks in sequence.

• 1.1.7 (Skipped): Only for note-taking don't worry. I did read it.

• 1.1.8 Procedures as Black Box Abstractions: each procedure should accomplish an identifiable task, and be usable as a module for building other procedures. The other procedures should not have to care about how a procedure does what it does, just that it does.

  • Accomplished Through:
    • Local Names: The names of variables don't "leak" out to surrounding scopes.
    • Lexical Scoping (Internal Definitions, Block Structure): Can encapsulate functionality within other procedures, makes them easier to write (less explicit parameter passing), and less likely to "leak" as well.