Helanic Abyss

今天把Haskell的Typeclass Eq和Ord在C++中用CRTP做了个简单的实现, 写完了才想起来boost里也有类似的(更强大)实现.

最近在看[Real World Haskell], 非常有意思的Haskell启蒙书, 只是有些知识点有点散.

今天看完Typeclass这一章, 怎么都感觉它像个template, 又像是个abstract class(因为方法可以有默认的实现, 但是这里的方法又不是成员方法).
看到P138的Eq的实现时感觉好像在哪里见过, 当时没想起来.

然后看到这篇文章, 感觉自己的直觉还是挺靠谱的.
还有一篇很长的文章也是讲Typeclass和C++ template之间的关系的.

这里只谈谈Eq和Ord, 在这里和这里可以看到两个实现. 其中Eq是这样的:

class  Eq a  where
    (==), (/=)       :: a -> a -> Bool

        -- Minimal complete defintion:
        --      (==) or (/=)
    x /= y           =  not (x == y)
    x == y           =  not (x /= y)

这里的”Minimal complete defintion”意思是实现了”==”或者”/=”任意一个运算符就满足了Eq的要求.
对于Ord也类同.(要求实现”<="或者compare)

Typeclass相当于一个接口, 一种约束, 那么在C++里是不是也能用template实现这种约束呢? 答案是肯定的.

为了让子类, 或者说接口的实现能够用最少的实现来满足接口施加的约束, 我们需要Template Method模式, 也就是说让父类调用一个没有实现(或者具有默认实现)的方法, 让子类来实现它. 而一旦有若干模板方法之间出现了循环依赖, 子类有时只需要提供其中某个方法的实现即可让环中的其它方法的默认实现工作起来.

用虚函数的话可以轻易实现Eq和Ord, 但是大多数时候我们手头已有的类型信息足以让我们把方法的分派(dispatch)提前到编译期, 从而降低执行期的开销.

利用CRTP我们可以在一定程度上用编译期多态替代执行期多态, 从而减少一次虚函数调用的开销, 但是它也仅仅能够满足仅要求编译期多态的调用者的需求, 简单说来就是这样的调用者:

template<class Eq>
void foo(const Eq &arg);

而不是下面这样依赖于执行期多态的调用者:

class Eq;
void foo(const Eq &arg);

下面就来着手实现它, 先定义一个crtp基类, 提供一些向下cast的辅助方法.

template<class Derived>
class crtp {
protected:
    const Derived & cast() const {
        return *static_cast<const Derived*>(this);
    }
    Derived & cast() {
        return *static_cast<Derived*>(this);
    }
};

Eq的实现就跟Haskell里的一样简单明了:

template<class Derived>
struct eq : crtp<Derived> {
    friend bool operator ==(const eq &lhs, const eq &rhs) {
        return !(lhs.cast() != rhs.cast());
    }
    friend bool operator !=(const eq &lhs, const eq &rhs) {
        return !(lhs.cast() == rhs.cast());
    }
};

这里的cast是为了告诉编译器: 如果子类有实现, 就优先使用子类的实现, 否则就用我的默认实现.

而Ord的代码也几乎就是Haskell的一个翻译, 让它继承于Eq, 并把Derived传递给Eq, 说明Derived同时受到Ord和Eq两个接口的约束.

template<class Derived>
struct ord : eq<Derived> {
    friend bool operator <(const ord &lhs, const ord &rhs) {
        return !(lhs.cast() >= rhs.cast());
    }
    friend bool operator >(const ord &lhs, const ord &rhs) {
        return !(lhs.cast() <= rhs.cast());
    }
    friend bool operator <=(const ord &lhs, const ord &rhs) {
        return lhs.cast() < rhs.cast() || lhs.cast() == rhs.cast();
    }
    friend bool operator >=(const ord &lhs, const ord &rhs) {
        return lhs.cast() > rhs.cast() || lhs.cast() == rhs.cast();
    }
};

现在假设bar是某个需要具有ord接口的算法, 而foo实现了ord接口, 我们来做个测试(为了测试方便, 假定bar里就是一些assert):

struct foo : public ord<foo> {
    int n;
    friend bool operator ==(const foo &lhs, const foo &rhs) {
        return lhs.n == rhs.n;
    }
    friend bool operator <(const foo &lhs, const foo &rhs) {
        return lhs.n < rhs.n;
    }
};

template<class T>
void bar(const ord<T> &lhs, const ord<T> &rhs) {
    assert(lhs != rhs);
    assert(!(lhs == rhs));
    assert(lhs < rhs);
    assert(!(lhs > rhs));
    assert(lhs <= rhs);
    assert(!(lhs >= rhs));
}

int main() {
    foo lhs, rhs;
    lhs.n = 1;
    rhs.n = 2;
    bar(lhs, rhs);
    return 0;
}

注意, 这样的约束是完全"免费"的, 没有任何执行期开销, 并且你只需要在"=="和"!="中选择一个实现, 并且在"<", ">", "<=", ">="选择另一个实现即可满足这个约束. 这里我把关于ord的选择空间放大了, 不仅限于"<=".

写完这个我才想起来, boost::operators就是做这个的. 不过它似乎有更加巧妙的地方, 它的CRTP竟然不要求public继承...

Related posts

• 任意下标范围的多维数组 (0)
• PIMPL & Const & Pointer (2)
• boost::implicit_cast (1)
• A Quiz of C++ const (1)