Chapter 1: Building Abstractions with Procedures

• 1.1: The Elements of Programming
• 1.3: Formulating Abstractions with Higher-Order Procedures

---

1.1 The Elements of Programming

My Summary:

This first section of chapter 1 introduces the basic building blocks of a computer language, and how the interpreter evaluates a given program. Primitive and compounds expressions, primitive and compound procedures, along with a few special forms are all that's necessary to create functional programs. We then turn to how the interpreter evaluates a program, starting with the basic general evaluation rules, which turns compound expressions into primitive expressions in order to evaluate the program. One useful way to think about evaluation is the substitution model, where we continually substitute compound expressions and procedures with simpler entities until we arrive at constructs that provide a value. Further extending this are two different ways to evaluate compound procedures: applicative order and normal order. The former immediately evaluates an expression if it can do so, while the latter waits until everything is expanded, and then reduces it. Most of the time they produce the same results, but not always; they also have different efficiencies.

The chapter concludes with a discussion of thinking of procedures as black boxes, which ties together the overall purpose of this chapter: building complex programs up from simple procedures that abstractions.

This course is about mastering complexity:

• Mastering Abstraction is our biggest tool: it's when you take a complex system and think of it as one whole thing, give it a name, and don't worry about the underlying details.
• Programming Paradigms: Broad ideas about how to organize whole programs in order to take advantage of our abstractions.

1.1.1 Expressions

• Primitive expressions, compound expressions
• Compound expressions made up of an operator and one or more operands

1.1.2 Naming and the environment

• The define special form
• Note the difference between built-in (primitive) procedures or compound (defined) procedures

1.1.3 Evaluating Combinations

• Scheme is built-on simple evaluation rules. There is nothing special about primitive procedures, such as +. They can easily be re-defined. Special forms are the only syntax that uses evaluation rules that differ.
• The interpreter evaluates combinations with an evaluation rule.
• Compound expressions can be modeled as trees. Normally, the operator is the node and the operands are the subnodes, but the operator itself can be an expression, and thus is a tree itself.

1.1.4 Compound Procedures

• Compound procedures allow us to give a name to a compound operation, in other words, create an abstraction.
• General form of a procedure definition, consisting of a name, formal parameters and a body.

1.1.5 The Substitution Model for Procedure Application

• This model is used by the interpreter in the general Evaluation Rule.
• You can sequentially substitute compound procedures with their values in parallel to perform an evaluation.
• There are two simplified evaluation orders: Applicative Order and Normal Order

1.1.6 Conditional Expressions and Predicates

• Boolean values: #t and #f; Boolean operators: and, or, not
• if and cond are special forms

1.1.7 Example: Square Roots by Newton's Method

1.1.8 Procedures as Black Box Abstractions

• Variables to a procedure are locally scoped to its body

1.3 Formulating Abstractions with Higher-Order Procedures

My Summary

This section is all about using procedures to build higher-levels of abstraction. Higher-order procedures are those that either accept a function as an argument or return a function. What this allows us to do is better create abstractions. For example, you can create separate functions for calculating the areas of shapes. But by generalizing the pattern and realizing the only difference in the calculations is the constant you multiply by, you can create a single function that calculates any shape. One level higher is realizing the difference in a pattern is a function. For example, a function that calculates the sum of a series is similar, whether the terms are simply added or squared before they're added. But realizing the difference in the pattern is a function, you can create a higher-order procedure that takes in a function and sums any series.

This technique of building abstractions was the most important concept of this section, but we also extended the discussion of higher-order procedures to those that return functions themselves. The derivative is a great example of this, as are functions that compose other functions.

The overall concept was treating procedures/functions as first class objects:

• They may be named variables
• They may be passed as arguments to procedures
• They may be returned as the results of procedures
• They may be included in data structures
• They may be unnamed

As a programmer, it is essential to build procedures at the right level of abstraction. It is often useful to create specific procedures to solve problems, such as calculating a sum of a series, but only in making the pattern more easily recognizable. Once you see the pattern, abstract the pattern into higher-order procedures. And be on the look-out for even higher-level abstractions.