About This Book
Structure and Interpretation of Computer Programs
(also named as SICP
) is a textbook about the principles of computer programming,such as abstraction in programming, metalinguistic abstracion, recursion, interpreters, and modular programming. It is widely considered a classic text in computer science. SCIP focuses on finding general patterns from specific problem and building software tools that embody each pattern.
How to Start Learning This Book
 Get this book.
 Get Scheme dialect of Lisp.
 Get all code of this book.
You can get all of those above from https://mitpress.mit.edu/sicp/
How to Use Edwin
When I first tried to learn Sheme, I had a lot of problem about how to use the interpreter. One of the main reason is that Edwin is an Emacslike editor, which is not easy for beginner to use. Therefore, I want to give an outline of Edwin.
Edwin is an Emacelike editor, that is, all the usages of Edwin are almost same as Emacs. Emacs is a famous editor in Linux platforms, and almost all the commands used by Emacs are begin with Ctrl key or Alt key.Now I give some the most used commands to help beginner to use Edwin. In the following, the prefix C
refers to the Ctrl key. For example, Cx
means to simultaneously press the Ctrl key and the x key.
command  means 

Cx c  close Edwin and back to interpreter 
Mz  evalute the expression 
Ci  auto indent 
M/  auto complete 
Cx Cs  save this file 
Cx Cf  open a new file 
Cx o  switching windows 
Cx 0  close this windows 
For more commands, You can read the article written by me <<Edwin笔记>>
Building Abstractions with Procedures
The Elements of Programming
Every powerful language has three mechanisms for accomplishing this:
 primitive expressions, which represent the simplest entities the language is concerned with.
 means of combinatoin, by which compound elements are built form simpler ones.
 means of abstraction, by which compound elements can be named and manipulated as units.
In programming, we deal with two kinds of elements: procedures and data. Thus any powerful programming language should be able to describle primitive data and primitive procedures and should have methonds for combining and abstracting procedures and data.
For example, in Java language, basic statements and basic number are primitive procedures and primitive data, and functions and classes are methonds for combining and abstracting procedures and data. When we defined a class in Java, we can manipulate it as an unit.
Expressions
 There are some examples about based expressions in Scheme.
1  486 
 Expressions such as these,formed by delimiting a list of expresions within parentheses in order to denote procedure applicartion, are called combinations.
 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.
 The convention of placing the operator to the left of the operands is konwn as prefix notation.
 Prefix notation has several advantages
 it can accommodate procedures that may take an arbitray number of arguments.
 it extends in a straightforward way to allow combinations to be nested,that is, to have combinatons whose elements are themselver combinations
1  (+ 137 248 342 23) 
 There is no limit to the depth of such nesting and to the overall complexity of the expressions that the Lisp interpreter can evaluate.
 We can use a formatting convention known as prettyprinting, in which each long combination is written so that the operands are aligned vertically.
1  (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ ( 10 7) 6)) 
ReadEvalPrint Loop
 The interpreter always operates in the same basic cycle
 read an expression from the terminal
 evaluate the expression
 print the result
 This mode of operation is often expressed by saying that the interpreter runs in a readevalprint loop(REPL).
Naming
 A critical aspect of a programming language is the means it provides for using names to refer to computational objects.
 In the Scheme dialect of Lisp, we name things with define.
1  (define size 2) 
Evaluating Combinations
 To evaluate a combination, do the following:
 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 value of the other subexpressions(the operands).
Evaluating Combinations
Applicative order
 To evaluate a combination, do the following:
 Evaluate the subexpressions of the combination.
 Apply the proceduce that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions.
Normal order
 To evaluate a combination, do the following:
 Not evaluate a combination until its value was needed.
 substitute operand expressions for parameters until it obtained an expression involving only primitive operators,and would then preform the evaluation.
Which is used in Scheme?
 Lisp uses applicativeorder evaluation,partly because of the additional efficiency obtained from avoiding multiple evaluation of ecpressions.
 normalorder evaluation becomes much more complicated to deal with when we leave the realm of procedures that can be modeled by substitution.
 On the other hand, normalorder evaluation can be an extremely valuable tool.
Compound Procedures
We can use a much more powerful abstraction technique by which a compound operation can be given a name and then referred to as a unit.
1 

The Substitution Model for Procedure Application
The iterpreter follows much the samme process as for combinations whose operator name primitive procedures. To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.
1  ; we can try to evaluate the combination 
The purpose of the substitution is to help us think about procedure application, not to provide a description of how the interpreter really works. But it is still an important model whicn can explain many question.
Condtional Expressions and Predicates
1  ;General Form 
 Conditional expressions are evaluated as follows.
 The predicate
<p1>
is evaluated first. If its value is false, then<p2>
is evaluated.  If
<p2>
‘s value is also false, then<p3>
is evaluated.  This process continues until a predicate is found whose value is true, in which case the interpreter returns the value of the corresponding consequent expression.
 If none of the
<p>
‘s value is true, the value of the cond is undefined.
 The predicate
 If expressions are evaluated as follows.
 The interpreter starts by evaluating the
<predicate>
part of expression.  If the
<predicate>
evaluates to a true value,the interpreter then evaluates the<consequent>
and return its values  Otherwise it evaluates the
<alternative>
and return its values.
 The interpreter starts by evaluating the
 Attention: Conditional expression and If expression are special form, that is, this expression can’t be replaced by an ordinary procedure.
Why If Expression Must Be a Special Form
We can just try to define a funtion to replace if expression, for example
1  (define (newif predicate thenclause elseclause) 
If we use this newif like this:
1  (newif (= 2 3) 0 5) 
It is seems that newif can work euqally. But if we use newif in a more complicated procedure, we will find a tiny difference of if expression and newif. The difference is also the reason why if expression must be a special form.
1  (define (iter guess x) 
If we use if expression
, interpreter print the value 3 as we expected. But if we use newif,interpreter tell us maximum recursion depth exceeded. In fact, we can use the Substitution Model to analyze this question
1  (iter 10 3) 
In order to evaluate the value of newif, we must first evaluate the value of (= 10 3)
and (iter ( 10 1) x)
. In order to evaluate the value of (iter ( 10 1) x)
, we must fisrt evaluate the value of the newif. This leads to an infinite recursion.
However, if expression is different from newif, if expression only evaluate a subexpression when predicate is decided. Therefore if we overwrite the iter by if expression and use the Substitution Model again, we can get the value we want finally.
1  (iter 10 3) 
Logic
1  ;General Form 
An Example of Block Structure
1  (define (sqrt x) 
We hava already learned the basic usages of those function. And there are two new usages
 Internal definitions and block structure. It allows a procedure to have internal definitions that are local to that procedure.
 lexical scoping. It allows x to be a free variable in the internal definitions. Thus, it is not necessary to pass x explicitly to each of these procedures.
The idea of block structure originated with the programming language Algol 60. It appears in most advanced programming languages and is an important tool for helping to organize the construction of large programs.
An Example of Exponentiation
1  (define (fastexpt b n) 
HigherOrder Procedures
Procedures that manipulate procedures are called higherorder proceduces. It can accept procedures as arguments or return proceduces as value.For example, we can define a procedure which computer the sum of the f(i)
from i=a
tp i=b
.
1  (define (sum f a next b) 
Constructing Procedures Using Lambda
In general, lambda is uesd to create procedures in the same way as define
, except that no name is specified for the procedure
1  ;General Form 
Like any expression that has a procedure as its value, a lambda expression can be used as the operator in a combination such as
1  ((lambda (x y z) (+ x ( y z))) 1 3 2) 
Use let
to create local variables
1  ;General Form 
The fisrt part of the let
expression is a list of nameexpression pairs. When the let
is evaluated, each name is associated with the value of the corresponding expression. The body of the let
is evaluated with these names bound as local variables. The way this happens is that the let
expression is interpreted as an alternate synatax for
1  ((lambda (<var1> ... <varn>) 
No new mechanism is required in the interpreter in order to provide local variables. A let
expression is simply syntactic sugar for the underlying lambda
application. We can see from this equivalence that the scope of a variable specified by a let
expression is the body of the let
Procedures as Returned Values
1  (define tolerance 0.00001) 
Notice how this formulation makes explicit the three idesa in the method: fixedpoint search, average damping, and the fuction y > x/y
. It is instructive to compare this formulation of the suqareroot method with the original version. Bear in mind that these procedures express the same process, and notice how much clearer the idea becomes when we express the process in terms of these abstractions.
Pair
Scheme provides a compoind structure called a pair
, which can be constructed with the primitive procedure cons
. This procedure take two arguments and returns a compound data object that contains the two arguments as pairs. Given a pair, we can extract the parts using the primitive procedures car
and cdr
. Thus, we can use cons
,car
, and cdr
as follows:
1  (define x (cons 1 2)) 
Pair is an abstract conception. Therefor the implemention of pair is not importan. For example we can give a solution like this
1  (define (cons x y) 
we can verify this implemention by Substitution Model
Abstraction Barriers
In gerneral, the underlying idea of data abstracion is to identify for each type of data object a basic set of operations in terms of which all manipulations of data objects of that type will be expressed, and then to use only those operations in manipulating the data.
We can also find this idea in the other programming paradigms,such as OOP. This idea can reduce the complexity of programming. We know that the complexity is the major obstacle to build large program. Therefore this idea is widely use in programming paradigms.
最后更新： 2024年09月11日 19:21
版权声明：本文为原创文章，转载请注明出处
原始链接： https://lizec.top/2017/09/01/%E3%80%8ASICP%E3%80%8B%E8%AF%BB%E4%B9%A6%E7%AC%94%E8%AE%B0/