SICP 读书笔记

发布于 2017-08-02 09:52:57

SICP keywords index

I’m using the second edition of SICP, which use Schema as the language of instuction.

  1. The code inline is the Schema language keyword or some other keyword.
  2. The sentences in parentheses are my comments.

据我自己统计，SICP 里面涉及到的知识有：

  1. 向量
  2. 矩阵
  3. 各种数学公式（求平方根、立方根、导数、不动点、微积分……）
  4. 数字电路
  5. 数理逻辑
  6. 机器语言
  7. 并发
  8. 解释器
  9. 编译器

Chapter 1: Building abstraction with procedures

  • primitive expression
    • prefix notation
    • operator and operand
      • numerals
      • built-in operators
      • naming, value and environment
        • built-in operators are special case in the “global envritonment”
  • combination
    • subexpressions and apply
    • recursion
    • tree accumulation: percolate values upward the tree representation of combination
    • special forms of general evaluation rule
      • define
        • procudure name and formal parameters (parameters(name) and arguments(value))
      • syntactic sugar: cause cancer of the semicolon
    • substitution (like algebra in mathematics)
      • In general, when modeling phenomena in science and engineering, we begin with simplified, incomplete models.
      • two ways:
        • normal-order evaluation: “fully expand and then reduce”
          • also can be a extemely valuable tool, such as stream processing
        • applicative-order evaluation(the interpreter actually uses): “evaluate the arguments and then apply”
          • may avoid multiple evaluations of expressions
  • abstraction
  • procedure and data
  • read-eval-print loop
  • case analysis, conditional expression
    • cond, if
    • clauses
      • predicate expression
      • consequent expression
    • primitive predicates, such as <, =, >
    • logical composition operations, and, or, not
  • scope
    • bound variable
    • free variable
    • internal definitions
    • block structure
    • lexical scoping
  • shape of procedure
    • recursion and iteration
    • defered operations
    • tail recursion
    • tree recursion
    • tabulation or memorization
    • orders of growth

Exercise 1.5

If use applicative-order evaluation, will return 0, and (p) will not be evaluate. Otherwise the procedure will be trapped in the infinite dead loop!

1.1.7 Square Roots by Newton’s Method

Proving of the recursion formula:

#!/bin/env python
r = -1.5

def f(x):
    # the key point
    return (x**2+2)/x/2

def get():
    global r
    n = 8
    while n > 0:
        n -= 1
        r = f(r)
        # print r
    print r

def init():
    import random
    global r
    r = random.randint(-200, 200)*1.0
    print 'r =', r

for _ in range(10):
    init()
    get()

Results(n=8):

r = 13.0
1.41421356237
r = 128.0
1.42412699238
r = 135.0
1.42752253385
r = -53.0
-1.41421684995
r = 139.0
1.42975619717
r = 161.0
1.44606826302
r = -7.0
-1.41421356237
r = 126.0
1.42327281788
r = -141.0
-1.43095530531
r = 73.0
1.41435265939
  • 费马小定理
    • 是欧拉定理的特殊情况
    • 是卡迈克尔函数的特殊情况，卡迈克尔函数比欧拉函数更小
  • higher-order procedures
  • lambda

Chapter 2: Building abstractions with data

  • compound data
  • data abstraction
  • abstraction barriers
  • techniques for representing sequences and trees.
    • closure
    • conventional interfaces
    • symbolic expressions
    • generic operations
    • data-directed programming
    • selectors
    • constructors
  • some abstract data
    • pair: implemented by the procedures cons 
      (define (cons x y)
    (define (dispatch m)
        (cond ((= m 0) x)
              ((= m 1) y)
              (else (error "Argument not 0 or 1: CONS" m))))
    dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))
      • car: Contents of Address part of Register
      • cdr: pronounced “could-er”, Contents of Decrement part of Register
      • newline and display
      • box-and-pointer notation
      • closure property of cons
    • hierarchical structures
      • Sequence of data
        • cons
        • list
      • “cons up”
      • list operations
        • list-ref
        • length
          • null?
          • base case
        • mapping over lists: map
        • filter
    • dotted-tail notation
    • design principle: sequences as conventional interfaces
    • stratified design
  • symbolic data
    • the meaning of the single quote character is to quote the next object
    • using list to represent:
      • set (unordered or ordered)
      • binary tree

Exercise 2.4: one kind of pair struct implementation

; construction
(define (cons x y)
    (lambda (m) (m x y)))
; deconstruction
(define (car z)
    (z (lambda (p q) p)))
(define (cdr z)
    (z (lambda (p q) q)))

Exercise 2.6: Church numerals

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
    (lambda (f) (lambda (x) (f ((n f) x)))))

(define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
comments powered by Disqus