gyumni  Aug. 16, 2019, 1:26 a.m.
08/16/2019
因为练习1.20,看The normalorderevaluation rule again1.1.5 The Substitution Model for Procedure Application
，from 1.1.3 Evaluating Combinations,look tree of evaluation process,
chartreuse 
1.1 The Elements of Programming 
primitive data and primitive procedures  
1.1.1 Expressions 
numerals evaluating operator operands prefix prettyprinting readevalprint 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 nameobject （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 orderAn 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 applicativeorder evaluation
normalorder and applicativeorder 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. lisp1.1.3 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
mathematics guess 的层级和 iter term 的第一次介绍迭代 c和lisp的区别是什么，python的高级whatis的how to 到1～3结束要重新做一遍答案（再看一遍书） 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 pseudoLisp: ^{20}The 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 BlackBox Abstractions
Internal definitions and block structure 
recursive circular black box. procedural abstraction ^{25}
(define (square x) (* x x)) (define (square x) Local namesThis principle  that the meaning of a procedure should be independent of the parameter names used by its author  seems on the surface to be selfevident, 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 abs. It 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 
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} stack. One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) tailrecursive 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) 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
^{34}tabulation or memoization 
Fib(n) is the closest integer to ^{n} /5 (define (fib n) 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 (countchange amount) (Countchange generates a treerecursive 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) 
The difference between (log n) growth and (n) growth becomes striking as n becomes large

Exercise1.1.7第一次做出来了，第二次我纠结于log把题想歪了，看来做题是要，立即做，并且有顺序 
1.2.5 Greatest Common Divisors 
rationalnumber arithmetic Lamé's Theorem

Euclid's Algorithm.^{42} (define (gcd 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 divisorssmallest integral divisor divisibility by successive integers starting with 2 The Fermat testFermat'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 Adleman 


08/24/2019/6:26:06 AMand 1.3 1.3 Formulating Abstractions with HigherOrder Procedures 
a method
particular numbers primitives in the language (multiplication, in this case) particular operations higherlevel operations. common patterns abstractions Procedures include mechanisms for defining procedures 
build abstractions by assigning names to common patterns and then to work in terms of the abstractions directly. Procedures 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. 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 higherorder 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, 1/2T 

Exercise 1.37. a. continued fraction truncation kterm finite continued fraction 
1.3.4 Procedures as Returned Values 
subtle consideration, 
procedures whose returned values are themselves procedures. 




