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 2
第二十课
运行时类型错误检查 (runtime type checking)
上节末尾引入了 sum-list procedure:
(
define
(
sum-list
num-list
)
(
if
(
null?
num-list
)
0
(
+
(
car
num-list
)
(
sum-list
(
cdr
num-list
)))))
>
(
sum-list
'(
1
2
3
4
5
))
15
>
(
sum-list
'())
0
表达式存在类型错误时,如:
>
(
sum-list
'(
"hello"
1
2
3
4
5
))
string cannot be + with number
Scheme 会正常执行这个语句,直到最后执行 (+ "hello" 15) 时发现 "hello" 与 15 并不能直接相加,进而抛出类型不匹配的错误。与 C 等静态类型语言不同,Scheme 在编译的过程中主要做语法解析而没有做类型检查,只有到运行时环境下具体执行类型不匹配的操作时才抛出错误。
>
(
if
(
zero?
0
)
4
(
+
"hello"
4.5
'(
8
2
)))
4
如上表达式,if 语句的 alternative 表达式可以顺利通过语法解析,但在运行时由于在逻辑上它不会被执行,因此整条语句在解释器 evaluate 的时候不会抛错。
Recursion in Scheme
用 recursion 可以以逻辑十分清晰的方式构建程序
fibonacci
(
define
(
fib
n
)
(
if
(
zero?
n
)
0
(
if
(
=
n
1
)
1
(
+
(
fib
(
-
n
1
))
(
fib
(
-
n
2
))))))
; 或者
(
define
(
fib
n
)
(
if
(
or
(
=
n
0
)
(
=
n
1
)
n
(
+
(
fib
(
-
n
1
))
(
fib
(
-
n
2
)))))
>
(
fib
0
)
0
>
(
fib
1
)
1
>
(
fib
2
)
1
>
(
fib
3
)
2
flatten
flatten 的功能如下所示:
>
(
flatten
'(
1
2
3
4
)
(
1
2
3
4
)
>
(
flatten
'(
1
(
2
3
)
4
((
5
))))
(
1
2
3
4
5
)
>
(
flatten
'(
1
(
2
"3"
)
"4"
((
5
))))
(
1
2
"3"
"4"
5
)
如果用 C 语言来实现这样的函数,我们首先需要考虑使用链表来作为底层数据结构,并且链表中的元素需要兼容不同的数据类型。有了链表后再以此为基础来构建算法,最终的代码可能有 50% 的篇幅花在内存管理,50%的篇幅花在构建算法。使用 Scheme 来实现,则可以省去内存管理代码,直接把时间花在算法的构建上。
; '()
; '(1 ...)
; '((1 2) ...)
(
define
(
flatten
sequence
)
(
cond
((
null?
sequence
)
'())
((
list?
(
car
sequence
))
(
append
(
flatten
(
car
sequence
))
(
flatten
(
cdr
sequence
))))
(
else
(
cons
(
car
sequence
)
(
flatten
(
cdr
sequence
))))))
sorted?
检查 num-list 是否按升序排列
>
(
sorted?
'(
1
2
2
4
7
))
#t
>
(
sorted?
'(
1
0
4
7
10
))
#f
当 num-list 的元素少于两个时,这个 num-list 已经按升序排列完成;当元素大于或等于两个时,这个 num-list 需要同时满足:
第一个元素小于或等于第二个元素
num-list 去掉第一个元素剩下的元素按升序排列好
; '()
; '(1)
; '(x y ...)
(
define
(
sorted?
num-list
)
(
or
(
<
(
length
num-list
)
2
)
(
and
(
<=
(
car
num-list
)
(
cadr
num-list
))
(
sorted?
(
cdr
num-list
)))))
general sorted?
与前几课介绍的 C 语言的 general sort 函数相似,我们也希望 sorted? procedure 可以接受类似函数指针一样的东西来指导排序的过程。
>
(
sorted?
'(
1
2
3
4
)
<=
)
#t
>
(
sorted?
'(
"a"
"b"
"d"
"c"
)
string<?
)
#f
在 Scheme 中不需要 procedure 指针,procedure 本身可以被作为参数传入别的 procedure 中:
(
define
(
sorted?
seq comp
)
(
or
(
<
(
length
seq
)
2
)
(
and
(
comp
(
car
seq
)
(
cadr
seq
))
(
sorted?
(
cdr
seq
)
comp
))))
参考
Stanford-CS107-lecture-20
Stanford-CS107 - Previous
函数式编程 - Scheme 1
Next - Stanford-CS107
函数式编程 - Scheme 3
Last modified
3yr ago
Copy link
Outline