We are about to study the idea of computational process
Language combine simple ideas to form complex ideas by three mechanisms
- primitive expression
- means of combination
- means of abstraction
- you type an expression, the interpreter responds by displaying the result of its evaluating that expression ( 486 )
- Expressions formed by delimiting a list of expressions within parentheses ( + 137 349 )
- operator, operands
1.1.2 Naming and the Environment
- language provides the means of using names ( variable ) to refer to computational objects ( value )
- Associating values with symbols
- 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
- Evaluate the subexpressions of the combination
- 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.
- 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
(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
- 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! )
fully expand and then reduce (x)
evaluate the arguments and then apply
1.1.6 Conditional Expressions and Predicates
- 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
- In procedure definition, it doesn’t matter what name the formal parameter has.
the scope of that name
- 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
- syntactic fact that the procedure definition refers to the procedure itself
- The process that characterized by a chain of deferred operations
- Requires interpreter keep track of operations to be performed later on.
- 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.
- An implementation with the property of: “An iterative process will be executed in constant space, even if it is described by a recursive procedure.”
Procedures are abstractions that describe compound operations
- 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
(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 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
- 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.