open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  1. MIT - 6.001 - SICP

Symbol

Symbol

  • Say your favorite color — value associated with a name (symbol)

  • Say "your favorite color" — symbol

; define a symbol
(define alpha 27)
(quote alpha)
'alpha
;; ' is a shorthand for quote

; retrieve the value associated with symbol
alpha

; reference the symbol
(quote alpha)
'alpha

; operations
(symbol? (quote alpha)) ; test whether an object is a symbol
(eq? 'alpha 'alpha)     ; test equality of two symbols

由前面的章节,我们知道 Scheme 在对表达式解析时,会先判断表达式类型。比如 lambda 表达式,那么 Scheme 的 evaluator 会认为这是一种特殊表达式,它的评价方式是创建一段对应的程序,然后返回指向该程序的指针,这时候我们就会看到 #[compound-…] 这样的打印输出结果。

同样的道理,Scheme 如果遇到 quote 表达式,它也会认为这是一种特殊表达式,它的评价方式就是为表达式中的第二个子表达式创建内部表示 (internal representation) 并返回,这时候 Scheme 会把对应的内部表示打印出来 — 即 beta。

我们可以像使用其他原始类型数据一样使用 Symbol

(list (quote delta) (quote delta))

但 Scheme 的解释器内部实际上会记住过往的 symbols,因此解释器内部不会存在两个一模一样的 symbol,即这个 symbol 是全局唯一的。因此上文中的表达式实际上在解释器内部表示如下图所示:

(define x 20)

(+ x 3) 				; => 23
'(+ x 3)				; => (+ x 3)
(list (quote +) x '3)	; => (+ 20 3)
(list '+ x 3) 			; => (+ 20 3)
(list + x 3)			; => ([procedure #...] 20 3)

Symbol 提高 Scheme 语言表达力

例:Symbolic Derivatives

; (deriv <expr> <with-respect-to-var>) ==> <new-expr>
;
; syntax
; Expr = SimpleExpr | CompoundExpr
; SimpleExpr = number | symbol
; CompoundExpr = pair< (+|*), pair<Expr, pair<Expr, null> >>

; usage
; (deriv '(+ x 3) 'x) 			; => 1
; (deriv '(+ (* x y) 4) 'x)		; => y
; (deriv '(* x x) 'x) 			; => (+ x x)

; implementation
(define simple-expr? (lambda (e)
  (not (pair? e))))

(define deriv (lambda (expr var)
  (if (simple-expr? expr)
      (if (number? expr) 0
          (if (eq? expr var) 1 0))
      (if (eq? (car expr) '+)
          (list '+
                (deriv (cadr expr) var)
                (deriv (caddr expr) var))
          <handle product expression>
      )
  ))
)

; 缺点
; 1. 可读性差 			 <- 没有明确的函数名告诉读者每段程序在做什么
; 2. 对新操作的扩展性差 		 <- 因为目前的代码假设只有两种操作,利用嵌套 if 语句来完成
; 3. 对表达式的表示形式不可变       <- 如果我们要改变表达式的表示形式,比如 '(x + 3),代码将发生巨大改变,因为我们依赖了 list 结构,以及它的选择器, car, cdr, cadr ... 而没有抽象出 Expr 这种抽象数据类型。

; 改进
; 1. 使用 cond 而不是嵌套if
(define sum-expr? (lambda (e)
  (and (pair? e) (eq? (car e) '+))))
(define variable? (lambda (e)
  (and (not (pair? e)) (symbol? e))))
; 2. 使用数据抽象
(define make-sum (lambda (e1 e2)
  (list '+ e1 e2)))
(define addend (lambda (sum) (cadr sum)))
(define augend (lambda (sum) (caddr sum)))

; deriv
(define deriv (lambda (expr var)
  (cond
    ((number? expr) 0)
    ((variable? expr) (if (eq? expr var) 1 0))
    ((sum-expr? expr)
      (make-sum (deriv (addend expr) var)
                (deriv (augend expr) var)))
    ((product-expr? expr)
      <handle product expression>)
    (else
       (error "unknown expression type" expr))
   )
))

; 此时 (deriv (make-sum 'x 'y) 'x) => '(+ 1 0),但我们希望得到的是约减过的表达式 '1,为了得到后者
(define make-sum
  (lambda (e1 e2)
    (cond ((number? e1)
           (if (number? e2)
               (+ e1 e2)
               (list '+ e1 e2)))
          ((number? e2)
           (list '+ e2 e1))
          (else (list '+ e1 e2)))))

参考

Previous高阶函数Next数据驱动编程与防御式编程

Last updated 6 years ago

然后再对这些列表进行评价。而评价 quote 这种特殊表达式时,就将 quote 后面的整个列表返回而不作任何额外评价,因此最后打印出来的返回信息就是该表达式本身。更多例子举例如下:

Youtube: SICP-2004-Lecture-9
MIT6.006-SICP-2005-lecture-notes-9