如何利用Ruby简单模拟Lambda演算详解

前言

最近看一本叫做《计算的本质》的书，这本书主要说了一些底层计算方面的知识。可以说它刷新了我的三观，而当今天看到可以使用y组合子来实现递归的时候我的世界观基本崩塌了。故借着七夕来写一篇文章总结一些关于计算的一些基本认识。以便后续可以更好地学习。也借着ruby的语法来阐述一下关于lambda的一些故事。

0. 题外话

为了庆祝一下这个七夕节日，我提前关掉了lol，打开了emacs，敲下如下代码(这里顺便推广一下ruby的单件方法)

上面代码的运行结果是

很明显，情侣可以“虐”狗但狗不能“虐”情侣。因此第二句执行语句会报错。以上也是ruby优雅的地方，我可以直接在指定实例上定义方法，而不影响其他其他的同类的实例(以上实例都是字符串)。

1. 函数的一些基本认识

“题外话”有个卵子用？额， 说没用，它还是有一点作用的。我们今天的主题是用ruby来模拟lambda演算。lambda演算在wiki上面的解释是这样的

lambda演算可以被称为最小的通用程序设计语言。它包括一条变换规则（变量替换）和一条函数定义方式，lambda演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。

平时我们使用命令式的编程语言会更倾向于关注字符串， 数字，布尔 这些可以充当主语或者宾语的类型。而我们平时跟他们打交道更多会以变量的形式，就如同“题外话”中的"狗"和"情侣"。但这篇文章的重点放在"虐"这个词上，也就是我们常称的谓语。在计算机里面我们通常称他做方法 或者 函数。

既然wiki上也说了lambda是最小的通用程序设计语言，那我们有没有可能用lambda来模拟出数字， 字符串， 布尔等等的这些常用的数据类型呢？这就是接下来要讲的东西。

1) ruby中的函数

在ruby中，函数其实可以算是一等公民，只是它的锋芒往往被ruby强大的面向对象特征给掩盖掉了（它使得我们更多地关注类还有模块）。ruby里面有个十分简单的创建函数的方式

它返回了一个proc对象。其实这个对象，就类似于我们平时操作的函数对象。但是这里我们并没有给函数赋予名字，可以理解为它是一个匿名函数。那么这种函数如何调用呢？有一种很语义化的调用方式，我们甚至不需要用变量来接受这个函数就可以调用它。

ruby还提供了参数检测，如果传入的参数与定义该函数的时候不匹配的话，则会抛出argumenterror异常。此外，ruby还提供了一种语法糖，我们可以用proc#[]包裹参数来调用proc实例。

使用方式如下:

2) 柯里化

wiki 上的解释如下

在计算机科学中，柯里化（英语：currying），又译为卡瑞化或加里化，是把接受多个参数的函数变换成接受一个单一参数（最初函数的第一个参数）的函数，并且返回接受余下的参数而且返回结果的新函数的技术。
既然上面已经讲了ruby创建匿名函数的基本方式，那下面来看看如何用ruby来模拟一个柯里化的过程， 假设我有一个函数接收三个参数， 我定义如下

ps: 定义函数时参数用括号包裹是为了提高识别度，其实括号可加可不加，定义函数也可以写成 -> x, y, z { x + y + z }
上述函数如何柯里化？按照柯里化的定义，我们可以把多参数的函数写成嵌套返回多个单一参数函数的形式，为了方便阅读我把代码写在ruby脚本文件里面

运行结果

其实这个函数每次调用都返回了一个只带一个参数的函数，而且返回的函数会保存着调用当前函数时传入的参数，就是我们通常讲的闭包。直到最后一个函数被调用并返回的时候，才会真正得到期望的计算结果。

当然我们可以更简单的用proc#[]来调用(在文章的后半部分我会统一用这种方式，比较节省代码)

2. 模拟lambda演算

lambda既然是最小的通用编程语言，那么我们现在尝试一下用ruby的proc这个现成的lambda来演算一些东西。难的东西我自己都还接受不了，这里只能先来模拟一些最为简单的东西了。

1) 数字

首先尝试模拟一下数字。《计算的本质》一书中提供了一个比较直观的段子，以下是我概括的大意

我们如果没办法直接使用数字，而只能使用谓语(动作)，那么我们只能重复数这个动作来描述数字这个特征，而数这个动作其实就是我们需要写的lambda表达式

直观点讲当我们要表示0的时候就数0次，调用方法0次，表示1的时候就调用方法一次。

那我们简单地表示0~2就可以是

这样或许看起来有点迷糊，其实他们都用lambda演算出来的，他们都接受一个函数p(数数这个动作)以及一个基础值x作为参数，如果是zero就直接返回基础值x， 如果是one就以x这个基础值作为参数调用函数p表示数了一次。

这里我们并没有办法很好的表示这个基础值x，为了直观，我需要借用一下ruby内置的数字0 作为一个基础值，并且要另外定义数数这个动作。

其实数数的动作就是在原来的基础值上加1，最后我统一写脚本

在解析环境里面引入脚本并执行一些相关的语句，就能得到我们想要的结果了

虽然对于已经含有内置数字类型的ruby来说这种模拟完全没有任何实用价值，不过对于了解lambda演算这可以是一个不错的开始。

2) 布尔型

说完数字，再来简单说一下布尔类型吧，他们也算是比较基础的数据类型了。而且布尔型模拟起来还更简单些。毕竟布尔型，不是true就是false。我们可以分别写两个都接受两个参数的函数，一个代表true一个代表false。true函数就返回其中的第一个参数，false函数直接返回第二个参数。

我们再写一个解析脚本，作为验证。我记得在c这种没有布尔类型的语言中我们是用0代表false 用大于1代表true。这里我就简单用0和1作为基础值来验证我们的lambda演算是否正确

引入运行脚本试试

跟预期的一样，我们的模拟是正确的，false函数最后被解析成0， 而true函数最后被解析成1。

以上的警告是重复定义常量所致，这里可以暂时忽略。

3) 简单判断一个数是否为0

最后我们再做个简单的模拟，用到我们前面模拟的数字以及布尔两种类型来定义一个方法，判断传入的参数是否为0(是否我们定义的zero), 并返回一个布尔类型(true或者false)的模拟结果。算法很简单

那如何用lambda表示？我们前面都讲过了，zero这个函数会接收两个参数: 第一个参数是函数，第二个为基础值，如果传入的是zero函数的话，我们调用zero的时候，不管传入第一个参数是什么，调用结果都会直接返回第二个参数(也就是基础值)。

那我们回过头来想如果把true作为它第二个参数，把一个返回false的函数作为第一个参数，那当我们新函数接收的是zero函数并且调用它的时候不就会直接返回true了吗？而其他的方法，如one, two就会执行-> (x) { false }这个过程。

可以把代码写成

运行结果是

只有第一个zero是我们期望的值，最后返回了1(就是true)。其他的都不是我们需要的代表数值0的lambda表达式。

3. 尾声

这篇文章有点长，主要介绍了ruby里面的proc类，以及对函数柯里化和lambda表达式做了最基本的讲解。最后举了一些例子，用lambda表达式来模拟数字和布尔类型，另外使用我们模拟出来的类型作为基础来定义一个实用的方法is_zero。

本文没有涉及太多高深的东西，因为有很多高深的东西我还吸收不了，当吸收了之后会继续发文讲述。很感谢您的阅读。以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对的支持。