[SICP-ch1] Building Abstractions with Procedures

SICP ch-1 Building Abstractions with Procedures

We are about to study the idea of computational process


1.1 The Elements of Programming

Language combine simple ideas to form complex ideas by three mechanisms

  1. primitive expression
  2. means of combination
  3. means of abstraction

1.1.1 Expressions

  • you type an expression, the interpreter responds by displaying the result of its evaluating that expression ( 486 )

Combinations

  • Expressions formed by delimiting a list of expressions within parentheses ( + 137 349 )
  • operator, operands

1.1.2 Naming and the Environment

Naming

  • language provides the means of using names ( variable ) to refer to computational objects ( value )
  • Associating values with symbols

Environment

  • The memory that interpreter must maintain to keeps track of the name-object pairs. ( ch-3 )
  • Determine the meaning of the symbols in expressions.

1.1.3 Evaluating Combinations

Interpreter is itself following a procedure

  1. Evaluate the subexpressions 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).

Thus, the evaluation rule is recursive in nature.


Special Forms

  • Exceptions to the general evaluation rule. ( apply operator to operands )
  • Each special form has its own evaluation rule.
  • define, cond, if, and, or,

1.1.4 Compound Procedures

Procedure definitions

1
2
(define (<name> <formal parameters>)
  <body>)

1.1.5 The Substitution Model for Procedure Application

Evaluate a combination

  • evaluates the elements of the combination
  • applies the procedure to the arguments

Substitution Model

  • To apply a compound procedure to arguments, evaluate the body of he procedure with each formal parameter replaced by the corresponding argument.
  • Typical interpreters do not evaluate procedure by substitute values, but using a local environment for the formal parameters ( ch-3 )
  • This model breaks down when we address procedures with “mutable data” ( ch-3 set! )

Normal Order

fully expand and then reduce (x)

Applicative Order

evaluate the arguments and then apply


1.1.6 Conditional Expressions and Predicates

Predicate

  • an expression whose value is interpreted as either true or false.
1
2
3
4
5
6
7
8
9
10
11
12
(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

(if <predicate>
    <consequent>
    <alternative>)

(and <e1> ... <en>)
(or <e1> ... <en>)
(not <e>)

1.1.7 Example: Square Roots by Newton’s Method

1.1.8 Procedures are Black-Box Abstractions

bound variables

  • In procedure definition, it doesn’t matter what name the formal parameter has.

free variables

the scope of that name


1.2 Procedures and the Processes They Generate

Procedure

  • A procedure is a pattern for the local evolution of a computational process.
  • It specifies how each stage of the process is built upon the previous stage.

1.2.1 Linear Recursion and Iteration

Recursive procedure

  • syntactic fact that the procedure definition refers to the procedure itself

Recursive process

  • The process that characterized by a chain of deferred operations
  • Requires interpreter keep track of operations to be performed later on.

Iterative process

  • one whose state can be summarized by a fixed number of state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state and an (optional) end test.

Tail Recursive

  • An implementation with the property of: “An iterative process will be executed in constant space, even if it is described by a recursive procedure.”

1.3 Formulating Abstractions with Higher-Order Procedures

Procedures are abstractions that describe compound operations

Higher-order procedures

  • procedures that manipulate procedures

1.3.1 Procedures as Arguments

1.3.2 Constructing Procedures Using lambda

In general, lambda is used to create procedures in the same way as
define , except that no name is specified for the procedure

1
2
(lambda (<formal parameters>)
  <body>)

using lambda creating local variables

1
2
3
4
5
(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ...
      (<varn> <expn>))
  <body>)

1.3.3 Procedures as General Methods

finding roots

finding fixed point

1.3.4 Procedures as Returned Values

return values are themselves procedures


Abstractions and first-class procedures

programming languages impose restrictions on the ways in which computational elements can be manipulated

First-class status

  • elements with fewest restrictions
  • They may be named by 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.

Lisp awards procedures full first-class status, which poses challenges for efficient implementation, but the resulting gain in expressive power is enormous.