市面上有一堆“最小”的计算模型：图灵机、λ微积分、PowerPoint(Wildenhain 2017)等。这些都是非常简单的语言，但图灵是完全的，理论上彼此“一样强大”。其中，lambda演算无疑是我最喜欢用来实际编写程序的演算：它是最接近从图灵油罐中爬出来的演算。
然而，就实现而言，这远不是一件简单的事情。Lambda演算有变量，这给解释器带来了巨大的复杂性：特别是如果你想对程序进行任何形式的推理，这种复杂性是一个问题。我们可能想要研究一些比λ微积分更低层次的东西：这就是组合子微积分的用武之地。
您可能听说过ski Combinator微积分：它是微积分中“最简单的”，但实际上并不是很容易理解，尝试使用绝对是谋杀。所以我们将从BCKW开始，这是一种更为晦涩难懂的微积分，实际上是由哈斯克尔·库里(Haskell Curry)发明的。
BCKW中有4个组合符：B、C、K和W(令人震惊，我知道)。您可以将这些组合符视为操作字符串开头的函数：
让我们使用一些示例来了解这些组合符是如何工作的。
大写字母是组合符，小写字母是变量。是的，是的，我知道我说过组合演算不需要变量，现在也不需要！我在这里只是用它们来解释每个组合子是如何工作的。如果你真的想变得书生气十足，你可以把小写字母想象成符号占位符，意思是“任何给定的组合符”。它们不会存在于我们编写的任何实际程序中。
最简单的组合符是K：它实际上等同于来自Haskell的const函数。它丢弃第二个参数，并返回第一个参数。如果为组合器提供的参数比它通常接受的参数多，则只需在输出中保留额外的参数即可：
接下来我们有C：，这相当于Haskell函数的翻转。它交换了第二个和第三个参数：
下面是一个使用C、K和W的表达式的小型求值器。您可以编辑表达式，然后按Enter键逐步执行。
您可以自己编写括号：隐式地说，所有表达式都是左关联的。这意味着以下各项都是相等的：
这里有一个开始展示你的组合器技能的难题：SKI组合器演算中的一个组合子是i，它是恒等式函数。
尝试仅使用BCKW组合符编写一个功能与I相同的表达式。使用以下求值器尝试并弄清楚如何执行此操作：在λ>；之后编写一个表达式，其功能与I相同。
到目前为止，我们定义的每个组合子的工作方式都有些奇怪：它们似乎跳过了第一个参数，而在第二个参数上工作。事实上，还有另一种等价的组合子演算没有这种特性：
在这个微积分中B保持不变，但是其余的组合子被换成了看似更简单的形式。K转到A1：
这并不是一个巨大的变化。我们看到真正不同之处的是另外两个。W已替换为M：
你们可以看到，W基本上和M做了同样的事情，但是通过了它的第一个参数。T和C之间的区别相似：
所以，首先，很简单地证明BCKW包含所有的BAMT组合子。尝试找到一种仅使用BCKW组合符来编写T的方法(提示：您可能希望使用BCKW编写I时使用先前的答案)。
因此，实际上，所有更改后的BAMT组合符都可以使用BCKW进行编码，方法是在相应的BCKW组合符后面加上i(或CKC或其他任何内容)。换言之：
那么，从BCKW到BAMT相当容易。然而，要走另一条路是极其困难的。在这里，试着用BAMT来写K(这相当困难，不要指望能得到它！)：
因此，这就是我们暂时坚持使用BCKW的原因：BAMT使用起来太痛苦了。
BCKW拥有的关于SKI的一件事是，每个组合器代表一种具体的功能。特别是K和W：没有这些组合子，我们既不能复制变量，也不能丢弃变量。这使得没有其中一种或两种都没有的语言变得有趣(尽管不是完全的图灵)。
如果我们说我们不能使用W，我们知道不会重复任何输入。事实上，如果编码得当，我们知道程序只能通过执行来减小其大小。BCK系统实际上是当今流行的仿射逻辑的编码。Rust使用仿射类型来保证内存安全：通过防止重复引用，您可以知道，无论何时查看变量，您都可以自由地修改它，或者在必要时销毁它(显然，Rust比我在这里描述的稍微复杂一些，但是BCK确实是系统的基本基础，就像SK可以作为任何编程语言的基础一样)。
如果我们去掉K，我们就得到了线性语言。这方面的限制甚至更多，但目前的研究也相当活跃：例如，线性类型已被用来构造用于不同隐私的语言。
BC有一个小问题：它没有(严格地说)等同于I。您可以编写一个接近的表达式，但它只有在应用于至少3个参数时才能实际计算。看看你能不能找到。
%s是我们还没有见过的唯一一个Combinator。它有点像是B、C和W的组合：
它可以插入、重新排序和复制。这使得它可以是强大的，只有在添加K的情况下才能完成图灵。尝试首先构造I，仅给出S和K：
当然，要证明SK是通用的，我们需要证明它包含其他通用系统之一。我们不会在这里详细说明，但首先试着找出B和W：
下一个任务是对Y组合符进行编码。这是一个合并器，计算结果如下：
如您所见，它对递归进行编码。与Haskell中的FIX函数一样，此组合器允许我们在没有显式自引用的情况下进行递归。当然，我们可以使用我们以前见过的组合子来定义这个组合子，因为我们的语言是图灵完成的。一种编码是BM(CBM)：
如您所见，bm(Cbm)，当应用于f时，产生f(M(Cbmf))，相当于f(bm(Cbm)f)(B只是没有在f中应用)。所以这确实是一个合适的递归组合器。
在lambada演算中，为了编码数字，我们通常使用教会数字：这也是我们在这里要做的。表示某个数字n n的教会数字是一个函数，它接受两个参数，并将第一个参数应用于第二个n次。以下是哈斯克尔的一些教会数字：
零：：(a->；a)->；a->；Azerfx=xone：：(a->；a)->；a->；aone f x=f xTwo：：(a->；a)->；a->；atwo f x=f(Fx)三：：(a->；a)->；a->；atrifx=f(f(Fx))
在组合符中对这些数字进行编码稍微困难一些。0和1是显而易见的：它们分别是A和I。试着算出2和3：
WB SB(WB)事实证明，使用二进制编码，在相对较小的空间内对数字进行编码是相当容易的。首先，教会数字上的乘法就是简单的合成：所以这就是我们的合并器上的B。我们已经定义了2，所以二进制编码的下一件事是后继函数。我们知道这是什么，从答案到3！
这意味着我们可以在𝒪(Logn)\数学{O}(\logn)空间中编码正态数(尽管计算仍然需要线性时间)。下面的repl允许使用数字：
如果我们考虑非正规形，我们可以占用更少的空间。例如，4可以这样编码：
但是我们通常更喜欢将我们的编码保持在标准形式：否则，当我们使用它们时，我们必须支付一些额外的评估费用。
曾几何时，SKI组合器被用作函数编译器的目标：Haskell的前身Miranda被编译成一组包含SKI的组合器。如今，Haskell被编译成“无刺无标记的G-机器”：它的编译技术在80年代末取代了组合器，从那以后一直是主导形式。显然，原因在于，在当前大多数计算机的体系结构上，基于组合器的编译目标不够快。它们会产生太多的垃圾：因此，切换到STG会带来大约40%的加速。
David Graunke(2016)的“Combinator编译器和图形缩减机简介”(A Introduction To Combinator Compilers And Graph Reducing Machines)，它回顾了Combinator编译器的高级历史和解释，以及我们为什么放弃它们。这次演讲中一个非常有趣的花絮是，一些人开始制作定制的硬件来更好地处理组合子演算。更有趣的是，这些天我们到处都是FPGA，所以也许重新引入组合器编译器的时机已经成熟了？
Edward Kmett(2018)的“Combinator Revisked”一书更详细地介绍了Combinator编译器的问题，并提到了一些我们非常接近使Combinator编译工作的地方。
因此，合并器的编译曾经是一个非常活跃的研究领域，但后来由于我们目前的硬件无法有效地评估它，它已经有点半途而废了。不过，这对我们来说意味着有大量的工作是关于如何将lambda术语编译成组合子的！
我们使用以下基本组合器集进行编译：SKIBC。S在这里是最重要的：当然我们只需要它和K，但是我们使用i是因为它极大地简化了我们生成的表达式，我们使用B和C是因为它们是S的特例，我们稍后会看到。翻译是这样进行的：
\x.e1 e2->；S(\x.e1)(\x.E2)\x.x->；i\x.e->；K e。
翻译工作是自下而上的。我们只对删除lambdas感兴趣：毕竟Combinator演算确实有应用程序，所以在这种情况下我们不需要做任何事情。因此，该算法通常被称为“抽象消除”，并且它也是无点.io用来自动执行无点Haskell表达式的算法。
抽象有三种形式：抽象为表达式(即应用程序)、抽象(返回其参数)和抽象(返回参数以外的内容)。在第一种情况下，我们使用S向下传递抽象的每个分支的参数。在第二种情况下，我们只使用I，在第三种情况下，我们使用K来忽略参数。我们永远得不到\x\y，因为算法是自下而上工作的，所以在查看\x\y之前，\y会被去掉。
B和C的工作方式类似于S的特殊情况：当我们在第一种情况下向应用程序的两个分支传递x时，有时这项工作是不必要的。有时其中一个分支不使用传递的变量：在本例中，我们使用B或C，具体取决于哪个分支忽略该变量。
\x.e1 e2，x∉e1->；B e1(\x.E2)\x.e1 e2，x∉e2->；C(\x.e1)e2。
这种方法有一个问题：它产生的组合子表达式的阶为𝒪(N3)\mathcal{O}(n^3)，比相应的lambda表达式大。通过一些技巧(比如我们使用C和B)，我们可以将其简化为𝒪(N2)\mathcal{O}(n^2)，但这仍然是一个非常令人不快的大小增加。
问题是我们基本上将参数作为单链表传递，其中简单的访问是𝒪(𝓃2)\mathcal{O(n^2)}，而更复杂的访问是𝒪(N)\mathcal{O}(N)。
奥列格·基塞廖夫(Oleg Kiselyov)写了一篇论文(2018年)，内容是将这一点归结为𝒪(N)\Mathcal{O}(N)，并附上了一些备忘录。还有一篇博客文章(Lynn2018)，描述了如何在𝒪(Nlogn)\Mathcal{O}(n\logn)时间内获得转换而不需要记忆，并在这里提供了一个在线实现。
这就是这篇文章的全部内容！将来我可能会写更多关于组合子的文章：它们是一个非常有趣的主题，像拼图一样非常有趣。有一件事我没有提到，那就是组合符和串联语言之间的联系：事实证明，这两件事几乎是一回事！也许我会在以后的帖子里看看。
格朗克，大卫。2016年。“组合器编译器和图形缩减机简介。”圣路易斯。Https://www.youtube.com/watch?v=GawiQQCn3bk.。
基塞廖夫，奥列格。2018年。“从语义上讲，λ\lambda表示滑雪。”在函数式和逻辑程序设计中，由。约翰·P·加拉格尔和马丁·苏兹曼，33胜50负。计算机科学讲义。查姆：斯普林格国际出版社。网址：90686-7_3.http://okmij.org/ftp/tagless-final/ski.pdf.。
林恩，这是本。2018年。“本·林恩的网上垃圾：倒数第二个兰姆达。”本·林恩的网上垃圾。Https://benlynn.blogspot.com/2018/11/lambda-penultimate_16.html.。
如果你想在其他地方查找这些组合符，这是你唯一找不到的：它比K少见得多，在我发现它的地方，人们只叫它K，所以我不得不选一个不同的字母来区分它↩︎