SICP 课程总结 & 复习
小作文
有赖于那个终极的、伟大的、命定的教务系统，我选上了这门课：SICP，Structure and Interpret of Computer Programs，计算机程序的构造与解释。
作为一门编程课，SICP颇有一种包罗万象的气质：讲授三种编程语言；涉及一众编程范式；更由于冯新宇、李樾两位老师都是程序设计语言（Programming Languages）界的大牛，这门课同样包含了许多考试范围外的 PL 概念。如果你常常在课程群里提问，甚至还能了解到如何证明TSP可以在多项式时间内验证之类的问题。总之是洋洋大观。
由于上课的时候说到许多概念都是英文，所以具体内容我也用英文写一下吧（
The curriculum SICP concentrates on the idea of abstraction, using Python, Scheme and SQL three languages to reveal various programming paradigm including imperative, declarative, functional, object-oriented and generic programming, and to cover numerous advanced concepts like higher-order function, closure, macro, polymorphism, metaclass and so on.
一般的评论都认为南大的SICP是一门实验性、革新性的课程。
先说实验性：
首先，今年也就刚刚是SICP第二年开课。按冯新宇老师的比喻，我们也就算是黄埔二期生，很有实验性。
其次，计算机系的后续课程都是基于C/C++的，而SICP很有实验性色彩地，全然不涉及C/C++内容。因此，虽然SICP和程序设计基础（讲授C/C++的传统课程）是二选一的平行课，基本没有学生会单选SICP，应该也只有我这样的转专业抽签倒霉蛋例外了。
如果还要再说一点的话，SICP破天荒地用了五位助教。五位助教老师一方面高山仰止、尽职尽责，一方面和大家打成一片，骚话连篇。几位助教在群里耐心解答各类问题，还会额外地讲一些类型系统、复杂度分析的知识，进一步扩充了SICP的课程内容，总之就是非常地好。
然后是革新性：
革新性其一就在之前说到的课程内容。据说SICP涉及的一些概念，比如闭包（closure），在南大甚至国内高校的其他所有课程中都是不会讲到的。而且就编程教育而言，面向无基础初学者的SICP，竟然涉及了如此多难懂甚至晦涩的概念，纵然是蜻蜓点水、浅尝辄止式地涉及，对初学者来说无疑是一种挑战。
革新性其二，在于我们这门课的两位老师：冯新宇、李樾。两位在 PL 届都是赫赫有名的大佬。据说国内计算机系有 PL 方向的高校都是凤毛麟角，按樾哥的说法，让他俩来讲课也多少有宣传PL方向的意思。
期中以前的内容
寒假想起来再写吧，期末不考啊（
期中以后的内容
Lecture-15: Python Inheritance
Attributes: Look up & Assignment
简单说来，Attribute 有两个类型：class attribute & instance attribute。
做 Attribute Look up 时，会优先找 instance attribute，找不到时再找 class attribute，如果还是没有找到，就继续上诉到父类，直到找到为止。如果最终还是找不到，就返回一个 attribute error 。
做 Attribute Assignment 时，考虑 dot expression 的两个部分：
<expression>.<name>
如果 <expression> 是一个 instance，那么就创建或修改对应的 instance attribute
如果 <expression> 是一个 class，那么就创建或修改对应的 class attribute
当然，class attribute 和 instance attribute 是有可能重名的，于是情况就会变得稍迷惑一些。
考点都在这个例子里，大概：
class Account:
interest = 0.02
def __init__(self, name_str):
self.name = name_str
jim_account = Account('Jim')
tom_account = Account('Tom')
###################################
>>> tom_account.interest
0.02
>>> jim_account.interest
0.02
>>> Account.interest = 0.04
>>> tom_account.interest
0.04
>>> jim_account.interest
0.04
>>> jim_account.interest = 0.08
>>> tom_account.interest
0.04
>>> jim_account.interest
0.08
>>> Account.interest = 0.05
>>> tom_account.interest
0.05
>>> jim_account.interest
0.08
Inheritance, Multiple Inheritance
Inheritance 写法上很简单：
class <Name>(<Base Class>):
<suite>
子类会顾名思义地继承父类的 class attributes，包括所有的 methods。
可以在 <suite> 部分任意的覆写父类的内容，也当然可以加入新的。没有覆写的attributes一律默认使用父类的。
Multiple Inheritance 同样很容易写：
class <Name>(<Base1>, <Base2>, ...):
<suite>
当然，这里不可避免地会涉及 Diamond Problem。Python的处理办法是Method Resolution Order，说实话我觉得相当迷惑。还是 C++ 写起来安心（
樾哥提到 Python 并不适合大规模的开发使用，写一点精短的小程序的话，这样的设计应该也还受用吧。
这个应该不是重点。
Quiz
难倒是不难，但是这是人写的代码吗……
class A:
z = -1
def f(self, x):
return B(x - 1)
class B(A):
n = 4
def __init__(self, y):
if y:
self.z = self.f(y)
else:
self.z = C(y + 1)
class C(B):
def f(self, x):
return x
Quesion:
-
>>> C(2).n ??? -
>>> a.z == C.z ??? -
>>> a.z == b.z ??? -
Which evaluates to an integer?
b.z b.z.z b.z.z.z b.z.z.z.z
答案是 4, True, False, b.z.z.z
Extensions:
-
The definition of expressions
-
Metaclass, duck type and other things about type system
Python中的
type就是一个 metaclass ，也就是可以创建其它 class 的，一种更加形而上的 class。>>>type(jim_account) <class 'Account'> >>>type(Account) <class 'type'>而如果你试图用 Python 研究类型系统，得到
>>>type(type) <class 'type'>也不必惊讶，这是 duck type 的缘故，参见
-
Inheritance, composition and mixin
Inheritance 是个很恐怖的东西。课件里写到，Inheritance helps code reuse but NOT for code reuse。继承的有两个主要的坏处，一是破坏封装，你不得不上溯父类；二是可能会继承冗余的信息。我印象中网上关于继承和耦合性还有很多有意思的钓鱼文。
实际上在做和 class 有关 code reuse 的时候，inheritance, composition 和 mixin 都是可能的选项。
可以参见
https://naildrivin5.com/blog/2012/12/19/re-use-in-oo-inheritance.html
说实话mixin的理解还是有点难度的。
-
Diamond Problem
Lecture-16: Special Methods
Special Methods
简单地说就是两个函数 str() 和 repr() ，传进某个 instance 就会给出一个显式的字符串表达。
其中 str() 的返回结果更加 human readable，而 repr() 很大程度上是给解释器看的。
譬如说
>>> from fractions import Fraction
>>> half = Fraction(1, 2)
>>> repr(half)
'Fraction(1, 2)'
>>> str(half)
'1/2'
特别地，如果没有实现 str() 的话调用会默认返回 repr() 的结果。
这两个函数就有多态（ Polymorphism ）的性质。
实现上很简单：
class Ratio:
def __init__(self, numerator, denominator):
self.n = numerator
self.d = denominator
def __repr__(self):
return "Ratio({0}, {1})".format(self.n, self.d)
def __str__(self):
return "{0}/{1}".format(self.n, self.d)
实现重载操作符也是类似可行的：
class Ratio:
def __init__(self, numer, denom):
from math import gcd
self.n, self.d = numer // gcd(numer, denom), \
denom // gcd(numer, denom)
def __repr__(self):
return "Ratio({0}, {1})".format(self.n, self.d)
def __str__(self):
return "{0}/{1}".format(self.n, self.d)
def __add__(self, other):
self = Ratio(self.n * other.d + self.d * other.n,\
self.d * other.d )
重载操作符的时候常常会遇到 <class A> + <class B> 能用，<class B> + <class A> 就不行了的情况。这时候只需要添加一行 __radd__ = __add__ 就可以了。
Extensions
-
Polymorphism
分成三类 Ad Hoc Polymorphism, Parametric Polymorphism & Inclusion Polymorphism。课间上破天荒给了C++代码示例：
// Ad Hoc Polymorphism foo(int) {} foo(string) {} // Parametic Polymorphism Template<typename T> T foo(T x, T y) { return (x > y)? x: y; } foo<int>(3, 7) foo<char>('h', 'k') // Inclusion Polymorphism T v; // T has many types v.foo();在这恐怖的课堂看见C++，就像回家了一样（
参见
https://en.wikipedia.org/wiki/Polymorphism_(computer_science)
Lecture-17: Linked Lists & Trees
就是实现两个类：链表和树
感觉没啥可写的，这节课说实话没啥信息量，放在这里应该是做一个 class 和 OOP 的总结，然后引入链表给 Scheme 开个头吧。