sicp

programming › functional programming

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.

1
2
3
(lambda (x) (* x x))
;(lambda (parameter list) (body))
(define sth toSth)
  • Modularity
  • controlling the process:
1
;(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
  • 一个方程可以合在一起写，也可以分开写。
1
2
3
4
5
6
7
8
9
10
11
12
"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
1
2
3
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(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

1
2
3
4
5
6
7
8
"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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    (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