gyumni | Aug. 16, 2019, 1:26 a.m.



因为练习1.20,看The normal-order-evaluation rule again1.1.5  The Substitution Model for Procedure Application

,from 1.1.3  Evaluating Combinations,look tree of evaluation process,

Figure 1.1:

1.1  The Elements of Programming

 primitive data and primitive procedures    

1.1.1  Expressions

numerals  evaluating operator  operands  prefix   pretty-printing  read-eval-print loop  (The leftmost element in the list is called the operator, and the other elements are called operands. The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands)

1.1.2  Naming and the Environment

name Define circumference  name-object  (Lisp program usually consists of a large number of relatively simple procedures )global environment    

1.1.3  Evaluating Combinations

procedurally       recursive       10    tree accumulation      evaluation rule

Peter Landin  syntactic sugar    (evaluation takes place will play an important role in our understanding of program execution.)

special forms

  Lisp has a very simple syntax; that is, the evaluation rule for expressions can be described by a simple general rule together with specialized rules for a small number of special forms.11


1.1.4  Compound Procedures

 procedure definitions   pronoun procedure  

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

(use square as a building block in defining other procedures)

(Compound procedures are used in exactly the same way as primitive procedures)built into



1.1.5  The Substitution Model for Procedure Application

(evaluate a combination whose operator names a compound procedure) 

That is, the interpreter evaluates the elements of the combination and applies the procedure (which is the value of the operator of the combination) to the arguments (which are the values of the operands of the combination).

substitution model for procedure application

We will discuss this more fully in chapters 3 and 4 when we examine the implementation of an interpreter in detail.

literature of logic and programming semantics



Applicative order versus normal order

An alternative evaluation model would not evaluate the operands until their values were needed. 


first substitute operand expressions for parameters until it obtained an expression involving only primitive operators,


fully expand and then reduce' 



in contrast to the ``evaluate the arguments and then apply'' method that the interpreter actually uses, which is called applicative-order evaluation


normal-order and applicative-order evaluation do not give the same result




1.1.6  Conditional Expressions and Predicates

 case analysis    cond     predicate    special form if

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

compound predicates

 and or Notice that and and or are special forms, not procedures, because the subexpressions are not necessarily all evaluated. Not is an ordinary procedure.


1.1.3  Evaluating Combinations


 symbol cond followed by parenthesized pairs of expressions (<p> <e>) called clauses

the interpreter returns the value of the corresponding consequent expression <e> of the clause as the value of the conditional expression.


1.1.7  Example: Square Roots by Newton's Method

the definition does not describe a procedure. Indeed, it tells us almost nothing about how to actually find the square root of a given number



guess 的层级和 iter -term 的第一次介绍迭代

c和lisp的区别是什么,python的高级whatis的how to


say, C or Pascal. This might seem surprising, since we have not included in our language any iterative (looping) constructs that direct the computer to do something over and over again.

It will not help matters to rephrase this definition in pseudo-Lisp:

 20The idea is to make interpreters sophisticated enough so that, given ``what is'' knowledge specified by the programmer, they can generate ``how to'' knowledge automatically. This cannot be done in general, but there are important areas where progress has been made. We shall revisit this idea in chapter 4.

demonstrates how iteration can be accomplished using no special construct other than the ordinary ability to call a procedure.24


1.1.8  Procedures as Black-Box Abstractions








Internal definitions and block structure

 recursive   circular  black box.  procedural abstraction  25



(define (square x) (* x x))

(define (square x) 
  (exp (double (log x))))

(define (double x) (+ x x))

Local names

This principle -- that the meaning of a procedure should be independent of the parameter names used by its author -- seems on the surface to be self-evident, but its consequences are profound. 

A formal parameter of a procedure has a very special role in the procedure definition

bound variable

the procedure definition binds its formal parameters


 If a variable is not bound, we say that it is free.

If we renamed guess to abs we would have introduced a bug by capturing the variable absIt would have changed from free to bound.)


auxiliary procedures   successive approximations   block structure  auxiliary procedures  we allow x to be a free variable in the internal definitions, 


enclosing procedure This discipline is called lexical scoping.27

Algol 60

computing square roots breaks up naturally into a number of subproblems

The importance of this decomposition strategy is not simply that one is dividing the program into parts. After all, we could take any large program and divide it into parts -- the first ten lines, the next ten lines, the next ten lines, and so on. Rather, it is crucial that each procedure accomplishes an identifiable task that can be used as a module in defining other procedures. 






The set of expressions for which a binding defines a name is called the scope of that name.


 In a procedure definition, the bound variables declared as the formal parameters of the procedure have the body of the procedure as their scope. 

abs names a procedure for computing the absolute value of a numbe


1.2  Procedures and the Processes They Generate

local evolution  


overall global, behavior of a process whose local evolution has been specified by a procedure.

process evolution

 It specifies how each stage of the process is built upon the previous stage.       


 oversimplified prototypical patterns


1.2.1  Linear Recursion and Iteration

   1.3. linear iterative process   1.4.  The substitution model reveals a shape of expansion followed by contraction indicated by the arrow in figure 1.3.  

deferred    recursive process

linear recursive process 

 lterative process  state variables  linear iterative process

his type of process, characterized by a chain of deferred operations, is called a recursive process.  

 additional ``hidden'' information, maintained by the interpreter and not contained in the program variables, which indicates ``where the process is'' in negotiating the chain of deferred operations. The longer the chain, the more information must be maintained.30


One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C)


iteration can be expressed using the ordinary procedure call (mechanism), so that special iteration constructs are useful only as syntactic sugar.31





1.2.2  Tree Recursion

 figure 1.5.

(define (fib n)

  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

evolved process looks like a tree

Thus, the process uses a number of steps that grows exponentially with the input


The number of ways to change amount a using n kinds of coins equals



  • the number of ways to change amount a using all but the first kind of coin, plus


  • the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin


34tabulation or memoization

  Fib(n) is the closest integer to n /5

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      (fib-iter (+ a b) a (- count 1))))

he difference in number of steps required by the two methods -- one linear in n, one growing as fast as Fib(n) itself


Example: Counting change


(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(Count-change generates a tree-recursive process with redundancies similar to those in our first implementation of fib.)


1.2.3  Orders of Growth

 order of growth   R(n) might measure the number of internal storage registers used, the number of elementary machine operations performed,

 For an exponential process, each increment in problem size will multiply the resource utilization by a constant factor.



1.2.4  Exponentiation

(define (expt b n)

  (if (= n 0)
      (* b (expt b (- n 1)))))

 The difference between (log n) growth and (n) growth becomes striking as n becomes large




1.2.5  Greatest Common Divisors

rational-number arithmetic   

Lamé's Theorem


 Euclid's Algorithm.42

(define (gcd a b)
  (if (= b 0)
      (gcd b (remainder a b))))


This generates an iterative process, (看形状,是iterative)whose number of steps grows as the logarithm of the numbers involved.


The fact that the number of steps required by Euclid's Algorithm has logarithmic growth bears an interesting relation to the Fibonacci numbers:

Exercise 1.20

1.2.6  Example: Testing for Primality

 checking the primality of an integer n


Searching for divisors

smallest integral divisor

divisibility by successive integers starting with 2

The Fermat test

Fermat's Little Theorem

If n is a prime number and a is any positive integer less than n, then a raised to the nth power is congruent to a modulo n.

Probabilistic methods

47 Carsichael numbers 

 probabilistic algorithms




08/24/2019/6:26:06 AMand 1.3   1.3  Formulating Abstractions with Higher-Order Procedures

a method


particular numbers

primitives in the language (multiplication, in this case) 

particular operations 

higher-level operations.

common patterns



 include mechanisms for defining procedures

 build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly.


 Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts,  construct procedures that can accept procedures as arguments or return procedures as values


 1.3.1  Procedures as Arguments

 summation of a series

 49 This series, usually written in the equivalent form (/4) = 1 - (1/3) + (1/5) - (1/7) + ···, is due to Leibniz. We'll see how to use this as the basis for some fancy numerical tricks in section 3.5.3.sigma notation

formulate general results about sums that are independent of the particular series being summed

 e132special cases of a still more general notion

   1.3.2  Constructing Procedures Using Lambda

 awkward      higher-order procedure

 names bound as local 

 let. variables. A let expression is simply syntactic sugar for the underlying lambda application.

 internal procedures.54


1.3.3  Procedures as General Methods

 we can make a new guess that is not as far from y as x/y by averaging y with x/y,



 Exercise 1.37.  a. continued fraction


k-term finite continued fraction

1.3.4  Procedures as Returned Values

 subtle consideration,

  procedures whose returned values are themselves procedures.