Structure and Interpretation of Computer Programs

1 Building Abstractions with Procedures

1.1 The Elements of Programming

1.1.1 Expressions

• Start with simple Lisp expressions.

1.1.2 Naming and the Environment

• Using definitions

1.1.3 Evaluating Combinations

• Evaluate subexpressions and apply operator to operands

1.1.4 Compound Procedures

• Define procedures

1.1.5 The Substitution Model for Procedure Application

• Describe substitution model
• Distinguish applicative oder from normal order

1.1.6 Conditional Expressions and Predicates

• Define conditional expressions
  • Use predicate case-based predicates
  • Use else clause
  • Use special form if
• Use logical compound operations

Exercises 1.1 – 1.5

• Exercise 1.1
• Exercise 1.2
• Exercise 1.3
• Exercise 1.4
• Exercise 1.5

1.1.7 Example: Square Roots by Newton's Method

• Compute square roots to illustrate procedures

Exercises 1.6 - 1.8

• Exercise 1.6
• Exercise 1.7
• Exercise 1.8

1.1.8 Procedures as Black-Box Abstractions

• Consider procedural abstractions with sqrt
• Illustrate local names and bound variables
• Discuss internal definitions and block structures

1.2 Procedures and the Processes They Generate

1.2.1 Linear Recursion and Iteration

• Implement linear recursive process to compute factorial
• Implement linear iterative process to compute factorial

Exercises 1.9 - 1.10

• Exercise 1.9
• Exercise 1.10

1.2.2 Tree Recursion

• Introduce tree recursion with Fibonacci numbers
• Example: Counting change