什么是多态lambda？

Question

lambdas(匿名函数)的概念对我来说非常清楚.而且我知道类的多态性,运行时/动态调度用于根据实例的派生类型调用适当的方法.但是lambda究竟能够多态化吗？我是另一个Java程序员,试图学习更多有关函数式编程的知识.

Answer 1

你会发现我在下面的答案中没有多谈羊羔.请记住,在函数式语言中,任何函数都只是一个绑定到名称的lambda,因此我对函数的说法转换为lambdas.

多态性

请注意,多态并不需要OO语言通过覆盖虚方法的派生类实现的"调度"类型.这只是一种特殊的多态,即子类型.

多态本身仅仅意味着函数不仅允许一种特定类型的参数,而且能够相应地对任何允许的类型起作用.最简单的例子:你没有为类型不在乎一切,只是把手放在任何或传递,使之不.挺那么微不足道,在一个单元素的容器包裹.您可以在C++中实现这样的功能:

template<typename T> std::vector<T> wrap1elem( T val ) {
  return std::vector(val);
}

但你不能把它作为一个lambda来实现,因为C++(写作时间:C++ 11)不支持多态lambda.

没有类型的值

......至少不是这样,那就是.C++模板以一种不同寻常的方式实现多态:编译器实际上为它遇到的所有代码中的任何人传递给函数的每种类型生成一个单态函数.这是必要的,因为C++的值语义:当传入一个值时,编译器需要知道确切的类型(它在内存中的大小,可能的子节点等),以便复制它.

在大多数较新的语言中,几乎所有东西都只是对某个值的引用,当你调用一个函数时,它不会获得参数对象的副本,而只是对已经存在的对象的引用.较旧的语言要求您将参数显式标记为引用/指针类型.

引用语义的一大优点是多态变得更容易:指针总是具有相同的大小,因此相同的机器代码可以处理对任何类型的引用.这非常丑陋¹,即使在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))

这里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;
}

显然,这是非常费力的.如果类型是双重怎么办？如果我们想要产品而不是总和呢？当然,我们可以手工编写每个案例.不太好的解决方案.

如果我们有一个通用函数将指令作为额外参数做什么,那么我们会更好!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));
}

除了仍然很麻烦之外,所有上述C代码都有一个巨大的问题:如果容器元素实际上具有正确的类型,则完全不受控制!来自*void任何类型的演员都会愉快地开火,但是毫无疑问,结果将是完整的垃圾².

类和继承

这个问题是OO语言解决的主要问题之一,它试图将您可能与对象中的数据一起执行的所有操作捆绑为方法.在编译类时,类型是单态的,因此编译器可以检查操作是否有意义.当您尝试使用这些值时,如果编译器知道如何找到该方法就足够了.特别是,如果你创建一个派生类,编译器知道"啊哈,即使在派生对象上也可以从基类调用该方法".

不幸的是,这意味着你通过多态实现的所有东西等同于合成数据并简单地在单个字段上调用(单态)方法.为了实际获得不同类型的不同行为(但可控制!),OO语言需要虚拟方法.这相当于基本上该类具有指向方法实现的指针的额外字段,非常类似于combine我在C示例中使用的函数的指针- 区别在于您只能通过添加派生类来实现重写方法,编译器再次知道所有数据字段的类型等,你是安全的.

复杂的类型系统,检查参数多态性

虽然基于继承的多态性显然有效,但我不禁说它 只是疯了傻³肯定有点限制.如果您只想使用一个恰好未作为类方法实现的特定操作,则需要创建一个完整的派生类.即使您只是想以某种方式改变操作,您也需要派生并覆盖稍微不同的方法版本.

让我们重新审视我们的C代码.从表面上看,我们注意到它应该完全可以使其类型安全,没有任何方法捆绑废话.我们只需要确保没有丢失类型信息 - 至少在编译期间不会丢失.想象一下_{(读∀T为"所有类型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那里的值,只是指向它们的指针.无需编译多个版本的代码:在运行时,不需要类型信息,我们只需处理通用指针.在编译时,我们知道类型,并可以使用函数头来确保它们匹配.即,如果你写的话

void evil_sumon (int* acc, double* x) { acc += *x; }

并试图做

vector<float> v; char acc;
accum_contents(v, evil_sumon, acc);

编译器会抱怨因为类型不匹配:在声明中声明accum_contents类型可能会有所不同,但所有出现的T都需要解析为相同的类型.

这正是参数多态在ML系列语言以及Haskell中的工作原理:函数实际上并不知道他们正在处理的多态数据.但他们被赋予了具有这种知识的专业运营商作为论据.

在像Java这样的语言中(在lambdas之前),参数多态性并没有给你带来太大的好处:因为编译器故意很难定义"只是一个简单的辅助函数"而只支持类方法,你可以简单地去推导从一流的方式马上.但在函数式语言中,定义小辅助函数是最容易想象的事情:lambdas!

所以你可以在Haskell中做出令人难以置信的简洁代码:

Prelude> foldr(+)0 [1,4,6]
11
Prelude> foldr(\ xy - > x + y + 1)0 [1,4,6]
14
Prelude> let f start = foldr(\ _(xl ,xr) - >(xr,xl))start
Prelude>:tf
f ::(t,t) - > [a] - >(t,t)
Prelude> f("left","right")[1 ]
("右","左")
前奏> f("左","右")[1,2]
("左","右")

注意如何我定义为一个帮手拉姆达f,我没有有关的任何类型的线索xl和xr,我只是想换这些元素这就需要类型是一个元组相同.所以这将是一个多态的lambda,与类型

\_ (xl, xr) -> (xr, xl)   ::  ? a t.  a -> (t,t) -> (t,t)

¹除了奇怪的显式malloc内容之外,输入安全性等:这样的代码在没有垃圾收集器的语言中非常难以使用,因为有人总是需要在不再需要时清理内存,但如果你不注意恰当地说,某人是否仍然拥有对数据的引用,实际上可能仍然需要它.在Java,Lisp,Haskell中你无需担心...

²对此有一种完全不同的方法:一种动态语言选择.在这些语言中,每个操作都需要确保它适用于任何类型(或者,如果不可能,则提出明确定义的错误).然后你可以任意组合多态操作,这一方面"非常无故障"(不像Haskell那样真正聪明的类型系统没有麻烦)但是OTOH会产生相当大的开销,因为即使是原始操作也需要类型决策和围绕它们的保障措施.

³我当然在这里不公平.OO范例不仅仅是类型安全的多态性,它还能实现许多东西,例如旧的ML,它的Hindler-Milner类型系统无法做到(ad-hoc多态:Haskell有类型类,SML有模块),甚至一些在Haskell中非常难的东西(主要是在可变大小的容器中存储不同类型的值).但是你越习惯于函数式编程,你对这些东西的需求就越少.