SICP Note Chapter 1
1. Substitution model
并不指实际中使用的，而是用于方便理解的一个较为粗糙的syntax
analysis模型
其中代换分为正则序代换(normal-order
evaluation, 把所有procedure 展开成基本运算符 最后运算) 以及应用序代换(applicative-order evaluation
先计算最外层procedure里的运算数的值 然后再展开procedure)
2. SICP里对递归和迭代的解释
递归：
(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)))
This
type of process, characterized by a chain of deferred operations, is called a
recursive process. Carrying out this process requires that the interpreter keep
track of the
operations
to be performed later on. In the computation of n!, the length
of
the chain of deferred multiplications, and hence the amount of information
needed
to keep track of it, grows linearly with n (is proportional
to
n), just like the number of steps. Such a process is called a linear recursive
process.
递归过程中，解释器不断的track即将被执行的操作。在求n的阶乘时，这些信息随着n线性增长。
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. In this case there is some
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.
另外在迭代过程中，其实每一步都包含了这一步相对于完整过程的所有信息。如果我们在其中一步中断，那我们只要给解释器提供那三个变量（当前结果 计数器 计数终点），我们就能继续下去。然而递归的话，有些信息隐藏的，这些信息由解释器来保有，他们并不在程序变量里面。并且递归的程度越深，这些信息就越多。
厉害的算法：closed form expression for Fibonacci numbers
厉害的证明过程：http://www.billthelizard.com/2009/12/sicp-exercise-113-fibonacci-and-golden.html
3.素性检查
利用费马小定理（以及他的变体）来进行素性检查
费马小定理(Fermat Theory)是数论中的一个重要定理，其内容为： 假如p是质数，且gcd(a,p)=1，那么a (p-1)≡1（mod p）
4.Lisp中过程作为一等公民
在lisp中，貌似javascript也是，允许把过程（方法/函数）看作是一个变量，可以在过程内部定义过程，可以把它作为参数，传入到另一个过程中。貌似这样写有很好的内聚性。当不想命名内部过程的时候可以用lambda表达式来描述规则。
//自己又开一坑= = 但愿能更完 机智如我反立flag
Comments
Post a Comment