Homework5

PB12011022
桑榆扬
FOPL

1. Existential Halting Problem

HaltPN P n =
    let P0 n0 = if (n0==n) then (P n) else endless_function
    in (Halt P0)

2. Visitor Design Pattern

a. 1个，添加一个ProductExp类

class ProductExp : public Expression
{
    virtual void parenPrint();
    virtual void evaluate();
//...
}

b. n+1个，Expression和它的n个子类都要添加输出语法树的方法
c. m+2个，添加一个productExp类，Visitor和它的m个子类都要添加visitProductExp方法

class ProductExp : public Expression
{
    virtual void accept(Visitor *vis)
    { lhs->accept(vis); vis->visitProductExp(this); rhs->accept(vis); }
    //...
}

d. 1个，添加一个DrawVisitor类
e. 当对类的操作种类较少，并且开发阶段不会增减操作时，可以使用standard design
f. 当对类的操作种类较多，或者开发阶段可能大量增减操作，并且类的种类比较固定，可以使用Visitor Design Pattern

3. Simula Inheritance and Access Links

a.
b. 顺着access link找到(2)Point Part of cp，取出此处的x
c. 顺着access link找到(3)ColorPt(...)，找不到x，所及继续顺着access link向上找到(2)Point Part of cp，取出此处的x
d. 因为distance方法定义在Point类里，而不是它的子类ColorPt，所以编译时即可确定它的access link指向(2)，这种优化可以减少调用方法的时间
e. 我不会将活动记录放在栈上，因为如果子类重写了父类的方法，最好活动记录里直接保存重写后的方法的指针，所以需要活动记录可以任意改变大小。

4. Delegation-Based OO Languages

a.
b.
c. 先创建一个对象A，它拥有x:,y:,move，再创建A的子对象B，它拥有x,y，父指针指向A，然后复制B为C。这样A有4条记录，B有3条记录，C有3条记录，共10条记录
d. 因为父对象的指针可任意修改，所以不能在编译阶段就确定一个对象的属性、方法是否合法。

5. Multiple Inheritance and Thunks

a. offsets和thunks都不需要，因为调用函数时直接查vtable就能找到对应的地址，不需要this指针。
b. 需要2n个条目。使用多继承与不使用多继承是有区别的，因为前者需要用到offset域。
c. 需要加上计算offset的时间
d. 条目数量没有变化，但是时间变了，因为多继承时还要调用thunk
e. 如果第二个编译器使用offsets，则不能链接，因为它们使用的vtable格式不一样。
如果第二个编译器使用thunks，则可以链接，因为vtable格式一样，A生成的vtable在第二个编译器眼中就和普通的单继承一样。

6. Java Interfaces and Multiple Inheritance

a.
b. Sausage和Ham都是Pizza的子类，但是它们又都是是MeatLover的父类，构成了Diamond inheritance，处理这种状况下的继承相当复杂。Pizza,Ham,Pineapple,Hawaiian也构成了Diamond inheritance
c.
d. C++的类可以多继承，这样写代码方便，而且子类不用重新实现父类的方法，但是编译器难以处理Diamond inheritance的问题。Java只能通过interface实现多继承，这样写比较清晰，避免了Diamond inheritance问题，但是需要写较多的重复代码。