今天准备开始研究下SICP，学习下函数式编程的基本思想，也拓展下自己的视野。这本书是MIT的本科生教材，一共就五章，希望能坚持读完。
第一章：Building Abstractions with Procedures
Lisp is an acronym for LISt Processing, was designed to provide symbol-manipulation capabilities for attacking programming problems such as the symbolic differentiation and integration of algebraic expressions.The dialect of Lisp used in this book is called Scheme.
If Lisp is not a mainstream language, why are we using it as the framework for our discussion of programming? Because the language possesses unique features that make it an excellent medium for studying important programming constructs and data structures and for relating them to the linguistic features that support them. The most significant of these features is the fact that Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data.The importance of this is that there are powerful program-design techniques that rely on the ability to blur the traditional distinction between ``passive'' data and ``active'' processes.
1.1 The Elements of Programming
A powerful programming language is more than just a means for instructing a computer to perform tasks . The language also serves as a framework within which we organize our ideas about processes. Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for accomplishing this:
primitive expressions, which represent the simplest entities the language is concerned with,
means of combination, by which compound elements are built from simpler ones, and
means of abstraction, by which compound elements can be named and manipulated as units.
1.1.1 Expressions
486 (+ 12 34) (* 21 23) (* 3 5 7 12)
(+ (* 3 5) (/ 6 2))
1.1.2 Naming and the Environment
A critical aspect of a programming language is the means it provides for using names to refer to computational objects. We say that the name identifies a variable whose value is the object.
eg:
(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159
(define circumference (* 2 pi radius))circumference
62.8318
It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).
1.1.3 Evaluating Combinations
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).
1.1.4 Compound Procedures
(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
1.1.5 The Substitution Model for Procedure Application
This alternative ``fully expand and then reduce'' evaluation method is known as normal-order evaluation, in contrast to the ``evaluate the arguments and then apply'' method that the interpreter actually uses, which is called applicative-order evaluation.
1.1.6 Conditional Expressions and Predicates
eg1:
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
eg2:
(define (abs x)
(cond ((< x 0) (- x))
(else x)))
eg3:
(define (abs x)
(if (< x 0)
(- x)
x))
eg4:
(and <e1> ... <en>) (or <e1> ... <en>) (not <e>)
local names:
A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn't matter what name the formal parameter has. Such a name is called a bound variable, and we s;≠r‘®´‘ººęƒ¬ay that the procedure definition binds its formal parameters. If a variable is not †® boº und, we say that it is free.
Internal definitions and block structures
(define (sqrt x)
(define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001))
(define (improve guess x) (average guess (/ x guess)))
(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
(sqrt-iter 1.0 x))
1.2 Procedures and Processes They Generate
Linear Recursion and Iteration
The contrast between the two processes can be seen in another way. In the iterative case, the program variables provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three program variables. Not so with the recursive process.
(define (factorial n)
(if (= n 1) 1 (* n (factorial (- n 1)))))
(define (factorial n) (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
(if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
Tree Recursion
Thus, the process uses a number of steps that grows exponentially with the input. On the other hand, the space required grows only linearly with the input, because we need keep track only of which nodes are above us in the tree at any point in the computation. In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.
1.3 Formulating Abstractions with Higher-Order Procedures
Yet even in numerical processing we will be severely limited in our ability to create abstractions if we are restricted to procedures whose parameters must be numbers. Often the same programming pattern will be used with a number of different procedures. To express such patterns as concepts, we will need to construct procedures that can accept procedures as arguments or return procedures as values. Procedures that manipulate procedures are called higher-order procedures.
Constructing procedures using Lambda
(lambda (x) (+ x 4)) (lambda (x) (/ 1.0 (* x (+ x 2))))
(define (plus4 x) (+ x 4)) is equivalent to (define plus4 (lambda (x) (+ x 4)))
Finding roots of equations by the half-interval method
Procedures As Return Values
