您会发现我在下面的答案中并没有过多谈论 lambda。请记住,在函数式语言中,任何函数都只是绑定到名称的 lambda,因此我所说的函数可以翻译为 lambda。
多态性
请注意,多态性实际上并不需要 OO 语言通过重写虚拟方法的派生类实现的那种“调度”。那只是一种特殊的多态性,子类型化 http://en.wikipedia.org/wiki/Polymorphism_(computer_science)#Subtyping.
多态性本身只是意味着函数不仅允许一种特定类型的参数,而且能够针对任何允许的类型。最简单的例子:你根本不关心类型,而只是传递传入的任何内容。或者,让它不quite如此琐碎,将其包装在单个元素容器中。例如,您可以用 C++ 实现这样的函数:
template<typename T> std::vector<T> wrap1elem( T val ) {
return std::vector(val);
}
但你无法实现它作为 lambda,因为 C++ (撰写时间:C++11) 不支持多态 lambda。
无类型值
……至少不是这样。 C++ 模板以一种相当不寻常的方式实现多态性:编译器实际上为任何人传递给函数的每个类型(在它遇到的所有代码中)生成一个单态函数。这是必要的,因为 C++'值语义:当传入一个值时,编译器需要知道确切的类型(它在内存中的大小、可能的子节点等),以便复制它。
在大多数较新的语言中,几乎所有内容都只是参考到某个值,并且当您调用函数时,它不会获得参数对象的副本,而只是获得对已存在对象的引用。较旧的语言要求您将参数显式标记为引用/指针类型。
A big advantage of reference semantics is that polymorphism becomes much easier: pointers always have the same size, so the same machine code can deal with references to any type at all. That makes, very uglily1, a polymorphic container-wrapper possible even in C:
typedef struct{
void** contents;
int size;
} vector;
vector wrap1elem_by_voidptr(void* ptr) {
vector v;
v.contents = malloc(sizeof(&ptr));
v.contents[0] = ptr;
v.size = 1;
return v;
}
#define wrap1elem(val) wrap1elem_by_voidptr(&(val))
Here, void*
只是一个指向任何未知类型。由此产生的明显问题是:vector
不知道它“包含”什么类型的元素!所以你不能真正用这些对象做任何有用的事情。除非你知道它是什么类型!
int sum_contents_int(vector v) {
int acc = 0, i;
for(i=0; i<v.size; ++i) {
acc += * (int*) (v.contents[i]);
}
return acc;
}
显然,这是极其费力的。如果类型是 double 呢?如果我们想要怎么办product,不是总和?当然,我们可以手写每个案例。这不是一个好的解决方案。
如果我们有一个通用函数,我们会更好指示做什么作为额外的参数! C 有函数指针:
int accum_contents_int(vector v, void* (*combine)(int*, int)) {
int acc = 0, i;
for(i=0; i<v.size; ++i) {
combine(&acc, * (int*) (v.contents[i]));
}
return acc;
}
然后可以像这样使用
void multon(int* acc, int x) {
acc *= x;
}
int main() {
int a = 3, b = 5;
vector v = wrap2elems(a, b);
printf("%i\n", accum_contents_int(v, multon));
}
Apart from still being cumbersome, all the above C code has one huge problem: it's completely unchecked if the container elements actually have the right type! The casts from *void
will happily fire on any type, but in doubt the result will be complete garbage2.
类和继承
这个问题是 OO 语言解决的主要问题之一,它试图将您可能执行的所有操作与对象中的数据捆绑在一起,如下所示:methods。在编译类时,类型是单态的,因此编译器可以检查操作是否有意义。当您尝试使用这些值时,如果编译器知道如何找到这些值就足够了method。特别是,如果您创建派生类,编译器就会知道“啊哈,即使在派生对象上也可以从基类调用该方法”。
不幸的是,这意味着通过多态性实现的所有功能都相当于组合数据并简单地在单个字段上调用(单态)方法。实际上得到不同的行为(但是有控制地!)对于不同的类型,OO语言需要虚方法。这基本上意味着该类有额外的字段指向方法实现的指针,很像指向combine
我在 C 示例中使用的函数 - 不同之处在于您只能通过添加派生类来实现重写方法,为此编译器再次知道所有数据字段等的类型,并且您是安全的。
复杂的类型系统,检查参数多态性
While inheritance-based polymorphism obviously works, I can't help saying it's just crazy stupid3 sure a bit limiting. If you want to use just one particular operation that happens to be not implemented as a class method, you need to make an entire derived class. Even if you just want to vary an operation in some way, you need to derive and override a slightly different version of the method.
Let's revisit our C code. On the face of it, we notice it should be perfectly possible to make it type-safe, without any method-bundling nonsense. We just need to make sure no type information is lost – not during compile-time, at least. Imagine (Read ∀T as "for all types T")
∀T: {
typedef struct{
T* contents;
int size;
} vector<T>;
}
∀T: {
vector<T> wrap1elem(T* elem) {
vector v;
v.contents = malloc(sizeof(T*));
v.contents[0] = &elem;
v.size = 1;
return v;
}
}
∀T: {
void accum_contents(vector<T> v, void* (*combine)(T*, const T*), T* acc) {
int i;
for(i=0; i<v.size; ++i) {
combine(&acc, (*T) (v[i]));
}
}
}
观察如何,即使签名看起来很像这篇文章顶部的 C++ 模板(正如我所说,它实际上只是自动生成的单态代码),执行实际上几乎只是普通的 C。没有T
那里的值,只是指向它们的指针。无需编译多个版本的代码:atruntime,不需要类型信息,我们只处理通用指针。编译时,我们确实知道类型并且可以使用函数头来确保它们匹配。即,如果你写了
void evil_sumon (int* acc, double* x) { acc += *x; }
并尝试去做
vector<float> v; char acc;
accum_contents(v, evil_sumon, acc);
编译器会抱怨,因为类型不匹配:在声明中accum_contents
它说类型可能会有所不同,但所有出现的T
确实需要解决the same type.
这正是参数多态性在 ML 系列语言以及 Haskell 中的工作原理:函数实际上对它们正在处理的多态数据一无所知。但他们被赋予了具有这些知识的专业操作员,作为参数.
在像 Java(lambda 之前)这样的语言中,参数多态性并没有给你带来太多好处:因为编译器故意让定义“只是一个简单的辅助函数”变得困难,而只支持类方法,所以你可以简单地使用派生函数- 立即下课。但在函数式语言中,定义小型辅助函数是可以想象到的最简单的事情:lambda!
所以你可以在 Haskell 中编写令人难以置信的简洁代码:
前奏>foldr (+) 0 [1,4,6]
11
前奏>foldr(\x y -> x+y+1) 0 [1,4,6]
14
前奏> let f start =foldr(\_ (xl,xr) -> (xr, xl)) start
前奏> :t f
f :: (t, t) -> [a] -> (t, t)
前奏> f(“左”,“右”)[1]
(“右左”)
前奏> f(“左”,“右”)[1, 2]
(“左右”)
请注意我如何在 lambda 中将其定义为助手f
,我对类型没有任何线索xl
and xr
,我只是想交换这些元素的元组,这需要类型the same。所以这将是一个多态 lambda,其类型为
\_ (xl, xr) -> (xr, xl) :: ∀ a t. a -> (t,t) -> (t,t)
1Apart from the weird explicit malloc
stuff, type safety etc.: code like that is extremely hard to work with in languages without garbage collector, because somebody always needs to clean up memory once it's not needed anymore, but if you didn't watch out properly whether somebody still holds a reference to the data and might in fact need it still. That's nothing you have to worry about in Java, Lisp, Haskell...
2There is a completely different approach to this: the one dynamic languages choose. In those languages, every operation needs to make sure it works with any type (or, if that's not possible, raise a well-defined error). Then you can arbitrarily compose polymorphic operations, which is on one hand "nicely trouble-free" (not as trouble-free as with a really clever type system like Haskell's, though) but OTOH incurs quite a heavy overhead, since even primitive operations need type-decisions and safeguards around them.
3I'm of course being unfair here. The OO paradigm has more to it than just type-safe polymorphism, it enables many things e.g. old ML with it's Hindler-Milner type system couldn't do (ad-hoc polymorphism: Haskell has type classes for that, SML has modules), and even some things that are pretty hard in Haskell (mainly, storing values of different types in a variable-size container). But the more you get accustomed to functional programming, the less need you will feel for such stuff.