斯坦福大学开放课程: 编程范式(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中用多个参数来使用

推荐阅读