斯坦福大学开放课程: 编程范式(Open Stanford Course : Programming Paradigms)

斯坦福大学开放课程: 编程范式,Open Stanford Course : Programming Paradigms,海报

c和c++高级内存管理特征。命令范式和面向对象范式的差别。函数范式--使用LISP和并发编程--使用c和c++。简单介绍一些其他流行的语言，如Python、Objective-C和C#。



课程前提要求：


抽象层次的编程和问题解决。未来的学生应该对c++有合理了解。你应该对数组、指针、引用、类、方法、动态内存分配、递归、链表、二叉搜索树、哈
希、迭代器和函数指针。你应该能够写出结构清晰、方便阅读的代码，并且意识到变量的良好命名、短函数和方法实现、必要的和清晰的评注。


Lecture1

主题：管理的细节，考试--时间限制，冲突，课程分数划分，作业细节--小作业，评分，缓交日期，课程
email，Newsgroup，Facebook/Twitter，邮件发送清单，课程前提要求，编程语言和范式--c++对比纯c，过程范式对比面向
对象编程，汇编，并发编程概况，并发编程数据共享问题的例子，scheme，函数范式的概况，Python简介，优势和常用法。



Lecture2

主题：c/c++
数据类型--解释，大小，位--字节怎么分成位，将字符的十进制值转化成位结构，短型--解释包含超过一个字节的数据，负数的表示，符号位，两个额外的实
现，char和short类型的转换，位代表如何转换，int和short转换，转换的符号扩展，浮点型，在整形和浮点型的转换。



Lecture3

主题：用指针在不同大小和位表示之间的转换，little Endian对比big
Endian，结构体：结构体的数据如何存储，获取结构体数据的获取，数组，数组的指针计算，将数组转换成其他类型的结果，结构体在内存的布局，c中
string的动态分配对比字符数组，使用strcpy修正结构体内部数据，字符数组和cout，c动态函数中使用内存和指针



Lecture4

创建一个任意大小数据结构的泛型交换函数，void*泛型指针类型，使用memcpy实现交换函数，交换泛型函数的界面，c泛型的优缺点对比
c++泛型，c泛型交换函数编译的不正常使用的结果，交换指针，使用泛型交换指针的陷阱，实现泛型线性搜索，使用cast和指针算术，用memcmp或比
较函数来比较内存块。



Lecture5

泛型L搜索--原型，比较函数，实现，将Void* S转换成Char*
S用于计算Byte便宜，泛型L搜索的客户端使用，比较函数比较整数的例子，更复杂的数据结构和L搜索--使用C-Strings的例子，比较两个C-
Strings的比较函数，带有表示Char**S的参数，关键字第一二参数是不同类型的比较函数，使用结构体的指针作为关键字来获取比较函数中的额外数
据，函数对比方法，C数据结构—实现整数的非泛型栈，c栈的接口，实现，内存预分配，c栈的客户端使用，栈内部内存的状态，栈变得很大时内存的增长，新建
栈的实现，断言。



Lecture6

主题：栈的实现—构造器和析构器，入栈实现，当用realloc栈过大时内存的重分配，使用realloc内存是怎么复制的，栈顶的实现，重新实
现栈接口作为泛型数据结构，新建栈的泛型实现，使用memcpy的入栈的泛型实现，栈增长的实现，静态（内部）函数，使用memcpy实现泛型出栈，这是
调用者的职责来分配存储的出栈元素的内存。



Lecture7

主题：内存拥有者的问题，析构栈的实现为什么不释放动态分配的数据，添加自由函数到栈的实现，重写栈析构来吸收，为C-Strings的栈写入自
由函数，写这些函数的陷阱，作业3的C库函数—Memmove（使用重叠的两个区域的可以复制的Memcpy），旋转函数的例子，C
Qsort函数，内存全局布局—栈段，堆段，堆管理者如何在堆上释放和分配内存，自由节点信息的基础链表。



Lecture8

主题：堆管理—分配信息是如何存在堆中，不正确释放内存的结果，堆分配的实际大小—2的最近的幂，通过在自由内存的块中存储地址来管理堆中的自由
块，选择自由块分配算法，当内存被释放后堆的自由链表如何更新，临近块如何被合并来避免碎片，使用Handles来压缩堆，通过减少栈指针在栈上分配本地
变量，在嵌套函数调用中的激活记录和栈指针状态，汇编代码和代码段，RAM，寄存器，和算术逻辑单元，算术表达式被转换为寄存器操作的例子。



Lecture9

主题：代码片如何被转换成汇编指令，存储，载入，和算术逻辑单元操作，4字节地址的汇编优化，上下文敏感的代码转换，重写汇编指令中默认的4字
节，将for循环转换为汇编，使用分支指令和PC寄存器，汇编中指针/数组计算，无条件分支指令（Jumps），4字节的汇编指令在内存中如何编码



Lecture10

主题：激活记录的更多细节—在函数调用中的内存分配，栈中函数返回地址如何存储，激活记录在栈中构建的例子，在栈中建立函数参数，使用call指
令跳到函数，在函数结束时清理与使用RET指令和存储的返回地址来返回原函数，激活信息的大致布局，激活信息的每个部分的建立，阶乘函数的汇编代码转换，
递归如何转换为汇编，在其他函数被调用时寄存器要重载的原因，阶乘函数汇编执行的动画展示。



Lecture11

主题：从c代码的产生到c++代码的产生：基本的交换例子，指针交换函数的代码产生，使用引用在c++版本的交换函数的代码产生，这被当做自动解
除指针引用，本地变量声明为引用，引用和指针的不同，在栈中空间声明类的效果，类方法，它把this指针隐式地当做第一个参数，this指针对类方法在激
活记录中的作用，静态类方法（独立函数）不包括this指针，编译和链接--#define和预处理。



Lecure12

主题：预处理指令 - #Define是一个很好的找到和替代的预处理宏 -
带参数的预处理指令，在容器中找到第n个元素地址的宏指令例子。断言的宏指令实现。断言是如何使用#ifdef和#define从最终产品脱离出去的。当
给出更多复杂参数时C宏的缺点。#include作为搜索和替代的操作，对比””,
在预处理后输出到编译器，如何使用gcc来查看预处理器的输出，如何使用#ifndef，#Define，#Endif来避免循环引用#include，
预处理结果的可视化展现，转换单元被传入编译器来创建a.o文件。一个展示简单脚本预处理和编译的例子。



Lecture13

主题：简单程序转换成a.o文件的编译过程的回顾。使用c标准库的效果。结果转换单元的.H文件。当没有找到或者.o文件没有改变时，Gcc如何引用一个原型。Gcc连接器在没有#

Include时，如何链接标准库文件，当使用预处理原型的.H文件没有被引入时的结果，如何使用.H文件创建不同的结果，断言是宏时在
Linker的失效，与断言是标准库中函数时的对比，编译链接时使用不正确数目参数时使用strlen的效果，在编译和链接时使用太少参数时调用
Memcmp的效果，C++在不同函数原型中消除歧义来避免前两个例子中出现的问题，调试信息 –
段错误(通常解除错误指针的引用)对比总线错误(检出没有对齐的数据的引用)，当整数数列溢出导致的无限循环调试例子。类似的列子在使用short类型数
组在Big-Endian系统和little-endian系统的对比。数组溢出覆盖了保存的PC和导致无限循环的脚本的例子。



Lecture14

主题：写入数组末尾导致函数返回地址被覆盖的例子，导致无限循环，在两种不同函数中数据不正常共享的例子，但由于激活记录结构（隧道）使得仍可以
被打印出来。Printf原型如何使用”…”,
这允许它使用可变数目的参数，为什么参数被从右到左入栈，查看打印时使用可变参数时的栈和函数，structs字段在内存中按顺序排列的原因，在使用相似
内部结构的不同structs间转换，顺序编程对比并发编程，在不相连的虚拟地址空间上运行多个不同进程的例子，虚拟地址映射到中心内存管理单元，如何让
并发编程（多进程）允许多个进程看上去在同时运行，多线程如何允许多个函数在一个进程中“同时”运行(例如打开微软office和在itune中下载歌
曲),可以使用线程建模的真实情景（一次能出售10张票的代理同时出售150张票）。



Lecture15

主题：在售票例子中从顺序编程到并发编程的转换，顺序模型的问题，线程接口，重写售票例子来使用，添加随机化的线程sleep调用让不同线程的时
间片更加随机，售票线程输出的例子，在非原子操作中一个线程如何被中断，通过允许一些源加载，一些源阻塞，多线程如何巨大地加速RSS News
Reader，允许每个票线程获取一个全局的线程池，而不是分配每个代理15张票，当线程同时尝试去获取共享数据时会导致的问题，如果通过使用信号量封闭
临界区来解决这个问题，信号量wait和信号量signal函数，修改售票函数来使用信号量保护共享数据，改变信号量的初始值如何会导致死锁或者允许过多
线程同时获取共享数据。



Lecture16

主题：回顾信号量语法，信号量signal和信号量wait，在多线程售票函数中的信号量使用（保护临界区），两个售票代理出售同一张票的竞争情
况的例子，当前运行线程被交换时栈和多个寄存器如何被保存，另外一个例子使用信号量建模internet和读写者线程，两个线程在没有保护下运行时的潜在
的危险，使用满缓冲和空缓冲的信号量来确保线程步调一致，不同的信号量模型 –
二元锁对比Rendezvous，改变空缓冲和满缓冲信号量的初始值的效果，如何检测死锁，使用多个读写者在线程同步的改变，哲学家就餐的问题 –
把每个哲学家当做一个线程的建模，死锁的结果，通过限制同时吃饭的哲学家数目来解决死锁。



Lecture17

主题：回顾哲学家就餐问题，把每个哲学家作为一个线程来建模，死锁的结果，通过限制同时吃饭的哲学家数目来解决死锁，使用全局变量和二元锁来记录
资源对比使用信号量，另外调用多个文件的FTP下载的线程例子，每个文件被分配给一个线程并且字节总数被返回，实现DownloadHelper用于下载
一个文件并且使用二元锁来安全更新下载的字节总数，通过使用Childrendone信号量，确保Downloadallfiles函数不能在所有文件被
其线程下载完成之前返回，Childrendone信号量如何确保函数在正确的时间返回，不论多个线程如何交叉存取，为下周建立一个冰欺凌店的并发例子。



Lecture18

主题：客座讲师，冰欺凌店建立客户、出纳员、职员和管理员线程，不同线程类型的限制，写出main函数，产生多个线程，使用检查结构处理管理员-
员工的交互，当员工准备好检查时使用信号量激活管理员，并且使用信号量确保职员要等待检查结束，写出管理员函数，当这个函数结束时执行每个检查和激活，写
出职员函数，这个函数一直做冰欺凌卷筒直到管理员检查并且同意；为什么需要添加一个额外的信号量来保护管理员函数，为什么刚才提到的所有信号量都是必须
的，写出顾客线程的函数，这个函数产生职员线程来交付冰欺凌蛋卷，然后等待所有工作完成，创建和保护line结构，用于按照顺序记录在出纳员前等待的顾
客，写出出纳员线程的函数，按顺序检查在line中等待的每个人，如果需要就等待。



Lecture19

主题：命令/过程范式（c）和面向对象的范式（c++），介绍函数的范式（Scheme），这个范式基于函数返回值的综合，一个转换摄氏温度到华
氏温度的Scheme函数定义的例子，Scheme环境（kawa）的细节，Scheme原语，Scheme的列表，表示函数和函数调用作为lists，
函数例子：，和scheme列表的操作，car和cdr，区分列表和带’的函数，car和cdr名字的起源，cons函数，通过把第一个参数加到第二个元
素（必须是一个列表）之前来构建一个新的列表，Append函数，链接两个或多个列表，定义自己的add函数，“Define”在Scheme中是有副作
用的一个操作，在scheme执行中的错误检查，写一个递归函数计算列表中所有数字之和。



Lecture20

主题：
car-cdr递归返回整数列表中的所有数字之和，scheme在运行时检测类型而不是在编译时检测，scheme中Fibonacci函数的递归实现，
运行时错误/类型检测对比编译时错误/类型检测的例子，写一个递归的精简函数删除列表中所有插入的括号，使用cond结构在精简函数中将多个递归例子用分
支表示，使用else声明来确保cond总是要返回一个值，写出一个整数列表中的排序函数，使用or函数来处理基本类型逻辑和使用cadr速写第二个元
素，在scheme中用多个参数来使用