open-courses
Search…
公开课笔记
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
高阶函数
Scheme 中的类型
程序中的各种结构,如
变量
、
表达式
、
函数
等都有一种属性叫做类型,而制定类型规则的系统称为类型系统 (Type System) 。类型系统能够通过规定程序中不同部分之间接口类型,同时检查接口的使用是否遵守既定规则,来减少 bug 出现的可能。此外,在程序编译时进行类型检查的语言称为
静态类型语言
;在程序运行时进行类型检查的语言称为
动态类型语言
。
Scheme 的基本数据类型包括:
1.
Number
2.
String
3.
Boolean
4.
Names (symbols)
Scheme 的复合数据类型包括:
1.
Pair<A, B>
2.
List<A>= Pair<A, List<A>or nil>
Scheme 的程序类型包括参数的数量、类型以及结果的类型,举例如下:
1.
square: number -> number
2.
>: number, number -> boolean
3.
+: number, number -> number
当类型不符合程序本身的类型定义时,运行程序就会报错:
>
(
+
"hello"
"world"
)
Exception in +:
"hello"
is not a number
类型帮助我们提高思考程序的效率:
1.
减少常见 bug
2.
为算法分析与优化建立基础
从类型到高阶函数
例1:求和
计算过程中,我们会遇到这些计算模式:运用前几节课的知识,可以用程序段描述它们:
(
define
(
sum-integers
a b
)
(
if
(
>
a b
)
0
(
+
a
(
sum-integers
(
+
a
1
)
b
))))
(
define
(
sum-squares
a b
)
(
if
(
>
a b
)
0
(
+
(
square
a
)
(
sum-squares
(
+
a
1
)
b
))))
(
define
(
pi-sum
a b
)
(
if
(
>
a b
)
0
(
+
(
square
(
/
1
a
))
(
pi-sum
(
+
a
2
)
b
))))
描述的过程中容易发现,这三段程序的计算模式非常相近,除了两个地方:
1.
每次累加的项 (term):
sum-integers:
a
sum-squares:
(square a)
pi-sum:
(+ (square (/ 1 a)))
2.
进入下一步 (next):
sum-integers:
(+ a 1)
sum-squares:
(+ a 1)
pi-sum:
(+ a 2)
尽管三段程序的 term 和 next 具体形式不尽相同,但不同的 term 、不同的 next 类型一致,因此我们容易构造出以下计算模式。
(
define
(
sum
term a next b
)
(
if
(
>
a b
)
0
(
+
(
term
a
)
(
sum
term
(
next
a
)
next b
))))
; 类型:(number -> number, number, number -> number, number) -> number
于是,利用上述计算模式,可以得到
(
define
(
sum-integers
a b
)
(
sum
(
lambda
(
x
)
x
)
a
(
lambda
(
x
)
(
+
x
1
))
b
))
(
define
(
sum-squares
a b
)
(
sum
square a
(
lambda
(
x
)
(
+
x
1
))
b
))
(
define
(
pi-sum
a b
)
(
sum
(
lambda
(
x
)
(
/
1
(
square
x
)))
a
(
lambda
(
x
)
(
+
x
2
))
b
))
这里的 sum 就是传说中的**高阶程序 **(higher-order procedure)。
例2:导函数
对于简单的函数,我们可以根据基本导函数的推导规则推导得到:
这里的 D 实际上有如下近似公式:

用程序来描述即:
(
define
deriv
(
lambda
(
f
)
(
lambda
(
x
)
(
/
(
-
(
f
(
+
x epsilon
))
(
f
x
))
epsilon
))))
例3:list operators
list transformation
; list contract
(
define
(
adjoin
ele lst2
)
(
cons
ele lst2
))
(
define
(
first
lst
)
(
car
lst
))
(
define
(
rest
lst
)
(
cdr
lst
))
; list transformation
(
define
(
square-list
lst
)
(
if
(
null?
lst
)
'()
(
adjoin
(
square
(
first
lst
))
(
square-list
(
rest
lst
)))))
(
define
(
double-list
lst
)
(
if
(
null?
lst
)
'()
(
adjoin
(
*
2
(
first
lst
))
(
double-list
(
rest
lst
)))))
**square-list **与 **double-list **同样结构十分相似,不同的地方在于对每个元素所做的转换。尽管这些转换的形式不同,但它们具有相同的类型,因此我们可以用 MAP 描述这种更加泛化的计算模式:
; 这里用 MAP 而不是 map 原因在于 map 是内置函数
(
define
(
MAP
proc lst
)
(
if
(
null?
lst
)
'()
(
adjoin
(
proc
(
first
lst
))
(
MAP
proc
(
rest
lst
)))))
(
define
(
square-list
lst
)
(
MAP
square lst
))
(
define
(
double-list
lst
)
(
MAP
(
lambda
(
x
)
(
*
2
x
))
lst
))
list filtering
过滤程序的不同点在于谓词的不同,但谓词具有相同类型 (number -> Boolean),因此我们可以将过滤泛化。
; list filtering
(
define
(
filter
pred lst
)
(
cond
((
null?
lst
)
'())
((
pred
(
first
lst
))
(
adjoin
(
first
lst
)
(
filter
pred
(
rest
lst
))))
(
else
(
filter
pred
(
rest
lst
)))))
; (number -> Boolean), list -> list
(
filter
even?
(
list
1
2
3
4
5
6
))
list accumulation
累加程序的不同点在于累加操作和初始值的不同,但累加操作有相同类型 (number, number -> number),初始值也有相同类型 (number),因此我们可以将累加泛化:
; 这里是 FOLD-RIGHT 而不是 fold-right 原因在于后者是内置函数
(
define
(
FOLD-RIGHT
op init lst
)
(
if
(
null?
lst
)
init
(
op
(
first
lst
)
(
FOLD-RIGHT
op init
(
rest
lst
)))))
(
define
(
add-up
lst
)
(
FOLD-RIGHT
+
0
lst
))
(
define
(
mul-all
lst
)
(
FOLD-RIGHT
*
1
lst
))
假设我们想要计算一种特殊的累加:

(
define
(
generate-interval
a b
)
(
if
(
>
a b
)
'()
(
cons
a
(
generate-interval
(
+
1
a
)
b
))))
(
define
(
sum
f start inc terms
)
(
FOLD-RIGHT
+
0
(
MAP
(
lambda
(
x
)
(
f
(
+
start
(
*
x inc
))))
(
generate-interval
0
terms
))))
上文中提到的特殊的累加,其实就是对积分过程的抽象描述,不论是对什么类型的函数进行积分,只要把函数传入积分过程中,描述积分过程的不需要关注传入的函数细节。这里不再援引课程中的例子。
例4: 不动点
当一个函数的定义域中存在一个点,使得函数的输出点与之相同,我们称该点为不动点。计算平方根的另一个思路就是计算以下函数的不动点:
找不动点的过程可以概括如下:
1.
产生一个猜测点 x
2.
计算 f(x),如果不够接近 x 本身,回到第一步
(
define
(
close?
u v
)
(
<
(
abs
(
-
u v
))
0.0001
))
(
define
(
fixed-point
f i-guess
)
(
define
(
try
g
)
(
if
(
close?
(
f
g
)
g
)
(
f
g
)
(
try
(
f
g
))))
(
try
i-guess
))
如此一来,我们可以用它来计算平方根,黄金分割点
; 平方根
(
fixed-point
(
lambda
(
x
)
(
/
2
x
))
1
)
; 黄金分割点
(
fixed-point
(
lambda
(
x
)
(
+
1
(
/
1
x
)))
1
)
但如果我们利用上述方式来求 2 的平方根,可以看到猜测点在 1 和 2 之间来回震荡,因此我们需要某种方式来抑制震荡,常用的一种抑制震荡方式是平均抑制震荡 (average-damp):
(
define
(
average-damp
f
)
(
lambda
(
x
)
(
average
x
(
f
x
))))
; (number -> number) -> (number -> number)
(
define
(
sqrt
x
)
(
fixed-point
(
average-damp
(
lambda
(
y
)
(
/
x y
)))
1
))
如此一来,我们将求平方根的过程拆分成了求不动点和抑制震荡两个过程,同时隐藏了抑制震荡的细节,这使得程序员更能把注意力集中到问题本身。
高阶函数的作用
高阶函数极大地增强了语言的表达能力,它帮助我们在描述复杂过程时隐藏不必要的细节,从而实现对更复杂系统的把控。这很像交流过程中用到专业术语,使用专业术语时,人们可以隐去对不必要的细节的描述,从而利用更精简的语句描述复杂的过程。
小结
从类型到高阶函数,让 Scheme 有了更强大的表达能力,帮助我们:
1.
描述复杂过程时忽略暂时不必关注的细节,专注问题本身
2.
分析进程的演化过程,确定每个计算阶段所需的输入
参考
MIT6.006-SICP-2005-lecture-notes-6
Youtube: SICP-2004-lecture-6
MIT - 6.001 - SICP - Previous
数据抽象
Next - MIT - 6.001 - SICP
Symbol
Last modified
3yr ago
Copy link
Outline