sicp

• Procedures as building blocks
• Recursion
• Procedural abstraction
• Data abstraction
• Symbols
• Mutation and the environment model
  • Data mutation
  • environment model
• Interpretation and evaluation
  • interpretation and interpreter
• Debugging
• Language design and implementation
• Continuations
• Lazy evaluation
• Streams
• Concurrency
• Garbage collection
• 6.001 in perspective
• Lambda Calculus

6.037 crash sicp

Procedures as building blocks¶

• Primitives: numbers, strings, booleans

• Built-in procedures, value, primitives

• Lambda: the value of a lambda expression is a procedure.

(lambda (x) (* x x))
;(lambda (parameter list) (body))
(define sth toSth)

• Modularity
• controlling the process:

;(if predicate consequent alternative)

• Test
  • rules for evaluation : sustitution model

Recursion¶

• Recursion vs. iteration

  pending operations?

  • Recurse: reduce problems to smaller subproblems
  • Iterative: constant space, based on the form of data
    • 需要一个范围，起点是什么，终点是什么

Procedural abstraction¶

• Type of a procedure is a contract: 输入和输出的类型是确定的，如果输出不是此类型，那么：the behavior is undefined
• patterns across procedures
• Higher-order procedures take a procedure as a argument, or return one as a value
• 一个方程可以合在一起写，也可以分开写。

"argument"
(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a) (sum term (next a) next b))))
(define (new-sum-integers a b)
  (sum (lambda (x) x) a (lambda (x) (+ x 1) b))
  
"return procedures"
(define incrementby (lambda (n) ...))

(define add1 (incrementby 1)) ;;type: number -> (number -> number)

Data abstraction¶

• types
• Compound data
  • a way of gluing data together
  • a way of getting the pieces back out
  • a contract between glue and unglue
  • Property: closure: treated as a primitive object
• Cons and friends
  • Pairs (cons cell)
    • a data abstraction
  • abstractions have two communities: builders and users
    • Constructor + accessors + contract + operations
    • ----- abstraction barrier-----
    • Implementation
• ex: rational number -> list -> map
  • scheme list is a linked list

(cons <a> <b>) -> <p> ;;cons:construct
(car <p>) -> <a-val>
(cdr <p>) -> <b-val>

Symbols¶

• Data types in scheme
  • Conventional: numbers, characters and strings, booleans, vectors
  • Scheme- specific
    • procedures
    • pairs and lists
    • Symbols
• All data types are first class (scheme)
  • Symbols -> procedures -> value of procedures -> store in data structures
• referring to symbols: quote
  • Object or expression to be evaluated
• operations
  • symbol? has type anytype -> boolean: (symbol? 'foo) -> #t
  • eq? tests the equality of symbols
• tagged data
  • benefits
    • Data-directed programming:
    • defensive programming

(define (make-point x y)
  (list 'point x y))

(define (point? thing)
  (and (pair? thing)
       (eq? (car thing) 'point)))

(define (...)
  (if (point? thing)
      (....)
      (.....))
  (if (not (point? pt)) ;;非需要的类型，更好地说明错误在哪
      .....))

Mutation and the environment model¶

Data mutation¶

• Mutators

  • mutate 指的是改变pointer指向的对象。不只是substitution model。
  • Enable new and efficient data structures

• syntax: Expression sequences

  • Begin: do sth and then return a value
  • Lambda,let, cond accept sequence
  • mutating compound data
    • Only side-effect: type is changed to undef

• Semantics: related to environment model

"primitive data"
(define x 1)
(set! x 2) ;;mutate, for names; set-car!, set-cdr! for pairs.

(begin 
 (set! x 2)
 (set! y 3)
 4)

• Sharing, equivalence, and identity

  • Same object: eq?
  • Look the same: equal?

• functional programming vs imperative programming

  • 函数式编程：计算函数，no assignments, easy to understand(代入求解都不会么？)
  • 命令式编程：relies heavily on assignment, introduce new classes of bugs
    • be able to modify local state

• queue implementation

  • Simple -> better(attach a type tag to maintain queue identity)
  • 单向链表到双向链表，就是语法不一样

environment model¶

New model of mutation for closures

• what

  • Name-rule
  • define-rule
  • Set!-rule
  • Lambda-rule: creates a procedure in the same EM
  • application

• view on computation

  • Variable, place to store things
  • Procedure, object with inherited context
  • Expressions, 不只与环境有关

• 组成

  • Frame: a table of bindings
  • Environment: a sequence of frames
    • enclosing environment pointer

• evalutation in the environment model

  • Global environment
  • to evaluate a combination: evaluate the subexpressions in the current environment
  • Capture state in local frames & procedures

• Let special form

  (let ( (<name1> <expr1>)
  		 (<name2><expr2>)...) 
  	<body>) ;;body are evaluated in the new frame generated from current frame; hidden lambda
  
  Ex: (let ((z (/ (- x2 x1) num-steps)))
  		(square z))
  
  (define make-counter
    (lambda (n)
      (lambda () (set! n (+ n 1))
        n
        )))

• Lambda captures the frame, which can be used to store local state.

• people make rules to allow computer following, not themselves. (没想到是这样的EM)

Interpretation and evaluation¶

interpretation and interpreter¶

• interpreter
  • lexical analyzer: break up input str into words called tokens
  • parser: convert to a tree
  • evaluator
    • Convert tree to a value
    • read and modify the environment
  • Printer

Debugging¶

Language design and implementation¶

Continuations¶

Lazy evaluation¶

Streams¶

Concurrency¶

Garbage collection¶

6.001 in perspective¶

Lambda Calculus¶