编程范式
这门课学什么
课程讲程序在底层怎样运行：C 指针与内存布局、简化汇编模型、线程与信号量并发，再讲 Scheme 函数式编程和 Python。
内容摘要
这门课讲程序在机器层面怎样运行，然后横向比较几种编程范式。2008 年版共 27 讲，先修课是 CS106B。讲师 Jerry Cain 习惯在黑板上画内存图，把每个字节放在哪里讲得很具体。
第 1 阶段（第 1–8 讲）讲 C 语言和内存：整数的位表示、字节序、结构体和指针运算。然后用 void* 写通用的 swap、lsearch 和栈，最后讲堆分配器怎样管理内存。第 2 阶段（第 9–14 讲）用一个简化的汇编模型，讲 C 和 C++ 代码怎样翻译成机器指令。内容包括栈帧、函数调用、预处理、编译和链接。
第 3 阶段（第 15–18 讲）讲并发：线程、信号量、竞争条件和死锁。这部分用售票、哲学家就餐、冰淇淋店 3 个模拟例子展开。第 4 阶段（第 19–27 讲）讲函数式编程：Scheme 的递归、map、lambda 和内存模型。之后讲 Python 的多范式写法和 XML 处理，最后一讲是 Haskell 客座讲座。
课程有 8 个编程作业：RSG 随机句子生成器、Six Degrees 六度分隔、通用 Vector 和 HashSet、RSS 新闻搜索、Raw Memory、多线程版 RSS、Where am I? 和 Python 作业。作业规模明显大于 CS106 系列。学完后，你能看懂指针和内存错误的根源，能写多线程 C 程序，也能用函数式风格思考问题。
为什么值得学
Jerry Cain 把内存和调用栈讲得非常具体。在一门课里对比多种编程范式，在入门课程中少见。
课程信息
- 学校
- 斯坦福（Stanford）
- 课程号
- CS107
- 讲师
- Jerry Cain
- 学期
- 2008 (SEE)
- 平台
- Stanford Engineering Everywhere
- 费用
- 免费
- 难度
- 中级
- 学时
- 27 讲
- 先修
- 需要 CS106B 程度的编程基础。
- 材料
- 视频、讲义、作业、考试
- 许可证
- CC BY-NC-SA 4.0（SEE 站声明）
课程大纲 · 共 27 节
大纲依据：SEE 2008 版讲次列表（27 讲，按每讲 Topics 概括）（查看原始页面 ↗）
- 1课程导论与编程范式概览Course Overview and Programming Paradigms
介绍课程安排和评分。预告本课涉及的语言，并区分过程式范式和面向对象范式。
- 2数据表示：位、字节与补码Data Representation: Bits, Bytes and Two's Complement
讲 char、short、int 在内存中的位模式。讲负数的表示和补码加法。
- 3类型转换、字节序、结构体与数组Type Conversion, Endianness, Structs and Arrays
用指针强制转换观察不同类型的位模式。讲大端与小端、结构体布局和数组的指针运算。
- 4C 的泛型编程：void* 与 swapGeneric Programming in C: void* and swap
用 void* 和 memcpy 写任意类型的 swap。比较 C 泛型和 C++ 模板，并列出误用 swap 的错误。
- 5通用线性查找Generic Linear Search
写泛型 lsearch 和比较函数。用 C 字符串数组练习指向指针的指针。
- 6通用栈的实现Generic Stack Implementation
先写 int 栈，并用 realloc 扩容。再把它改写成任意类型的泛型栈。
- 7内存所有权与释放函数Memory Ownership and Free Functions
讨论栈中元素指向的堆内存由谁释放。给栈加入释放函数，并分析常见错误。
- 8堆内存管理Heap Management
讲堆怎样记录每次分配的大小、怎样管理空闲块。讲错误 free 的后果和选择空闲块的策略。
- 9从 C 到汇编：读取、存储与跳转From C to Assembly: Loads, Stores and Branches
用一个简化汇编模型翻译 C 代码。讲 load、store、ALU 运算，以及 for 循环怎样翻译成跳转指令。
- 10活动记录与函数调用Activation Records and Function Calls
讲函数调用时栈帧的布局。讲参数入栈、返回地址和 call 指令。
- 11C++ 的代码生成：引用与方法Code Generation for C++: References and Methods
比较指针版和引用版 swap 的汇编。说明引用就是自动解引用的指针。
- 12预处理器与宏The Preprocessor and Macros
讲 #define 和带参数的宏。讲 assert 宏的实现，以及发布版怎样去掉断言。
- 13编译与链接Compilation and Linking
讲源文件怎样变成 .o 文件。讲缺少函数原型时 gcc 的推断和链接器的行为。
- 14内存错误与栈Memory Bugs and the Stack
用数组越界覆盖返回地址的例子讲栈的布局。演示两个函数意外共享数据的现象。
- 15并发入门：线程Introduction to Concurrency: Threads
用售票例子从顺序程序转到多线程程序。介绍线程接口和时间片。
- 16信号量与竞争条件Semaphores and Race Conditions
用信号量保护售票程序的临界区。讲竞争条件，以及线程切换时栈和寄存器怎样保存。
- 17哲学家就餐问题与死锁Dining Philosophers and Deadlock
把每个哲学家建模成线程，展示死锁怎样产生。用信号量限制同时就餐人数来消除死锁。
- 18冰淇淋店模拟（客座讲座）Ice Cream Store Simulation (Guest Lecture)
用顾客、收银员、店员、经理 4 类线程模拟冰淇淋店。讲多类线程之间的同步约束。
- 19函数式编程入门：SchemeIntroduction to Functional Programming: Scheme
对比命令式、面向对象和函数式范式。介绍 Scheme 和 Kawa 环境，写第一个 Scheme 函数。
- 20Scheme 中的递归与类型检查Recursion and Type Checking in Scheme
用 car/cdr 递归处理列表。比较运行时类型检查和编译时类型检查。
- 21在列表上映射函数Mapping Functions over Lists
讲 Kawa 环境的使用和 map 操作。把函数映射到嵌套列表和多个列表上。
- 22幂集、lambda 与 letPower Set, Lambda and Let
用 lambda 和 map 写递归的幂集函数。用 let 绑定减少重复递归。
- 23Scheme 的内存模型The Scheme Memory Model
讲 Scheme 怎样在底层构造链表。比较有内存别名和无别名的两种布局，并讲可变参数函数。
- 24Python 入门Introduction to Python
介绍 Python 作为多范式脚本语言的特点。讲动态类型、缩进和基本语句。
- 25Python 的多种范式与字典Python Paradigms and Dictionaries
用 Python 同时以 3 种范式重写 RSG。讲 Python 对象和字典的实现。
- 26用 Python 处理 XMLXML Processing in Python
比较两种 XML 处理模型。用 Python 解析网络上的 RSS 源。
- 27客座讲座：HaskellGuest Lecture: Haskell (Sasha Rush)
介绍 Haskell 的历史、类型系统和惰性求值。用一行代码写出斐波那契数列。