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

前言

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

0. 题外话

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

subject = "情侣"
object = "狗"

def subject.do_something(who)
 "#{self} 虐 #{who}"
end

if __FILE__ == $0
 p subject.do_something(object)
 p object.do_something(subject)
end

上面代码的运行结果是

"情侣 虐 狗"
dog.rb:11:in `<main>': undefined method `do_something' for "狗":String (NoMethodError)

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

1. 函数的一些基本认识

“题外话”有个卵子用?额, 说没用,它还是有一点作用的。我们今天的主题是用Ruby来模拟Lambda演算。Lambda演算在Wiki上面的解释是这样的

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

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

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

1) Ruby中的函数

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

[1] pry(main)> -> x { x + 2 }
=> #<Proc:0x007fc171dc6010@(pry):1 (lambda)>

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

[2] pry(main)> -> x { x + 2 }.call(1000)
=> 1002
[3] pry(main)> -> x { x + 2 }.call(1000, 100000)
ArgumentError: wrong number of arguments (given 2, expected 1)
from (pry):3:in `block in __pry__'

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

使用方式如下:

[4] pry(main)> ADD_THREE = -> x { x + 3 }
=> #<Proc:0x007fd8341ffc48@(pry):4 (lambda)>
[5] pry(main)> ADD_THREE[1000]
=> 1003

2) 柯里化

Wiki 上的解释如下

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

[10] pry(main)> ADD_THREE_NUMBER = -> (x, y, z) { x + y + z}
=> #<Proc:0x007fd834aa4150@(pry):10 (lambda)>
[11] pry(main)> ADD_THREE_NUMBER.call(1,2,3)
=> 6

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

# currying.rb
ADD_THREE_NUMBER_NEW = -> (a) {
 -> (b) {
 -> (c) {
 a + b + c
 }
 }
}

if __FILE__ == $0
 p ADD_THREE_NUMBER_NEW.call(1).call(2).call(3)
end

运行结果

6

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

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

[1] pry(main)> require('./currying')
=> true
[2] pry(main)> ADD_THREE_NUMBER_NEW[1][2][3]
=> 6

2. 模拟Lambda演算

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

1) 数字

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

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

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

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

ZERO = -> (p) { -> (x) { x } }
ONE = -> (p) { -> (x) { p[x] } }
TWO = -> (p) { -> (x) { p[p[x]] } }

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

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

CALCULATE = -> (n) { n + 1 }

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

# coding: utf-8

# number.rb
ZERO = -> (p) { -> (x) { x } }
ONE = -> (p) { -> (x) { p[x] } }
TWO = -> (p) { -> (x) { p[p[x]] } }

def to_integer(proc)
 calculate = -> (n) { n + 1 }
 # 其中0是基础值
 proc[calculate][0]
end

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

[1] pry(main)> require('./number')
=> true
[2] pry(main)> to_integer(ZERO)
=> 0
[3] pry(main)> to_integer(ONE)
=> 1
[4] pry(main)> to_integer(TWO)
=> 2

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

2) 布尔型

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

TRUE = -> (x) { -> (y) { x }}
FALSE = -> (x) { -> (y) { y }}

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

# boolean.rb
TRUE = -> (x) { -> (y) { x }}
FALSE = -> (x) { -> (y) { y }}

def to_boolean(proc)
 proc[1][0]
end

引入运行脚本试试

[1] pry(main)> require('./boolean')
/Users/lan/Personal/Ruby/boolean.rb:1: warning: already initialized constant TRUE
/Users/lan/Personal/Ruby/boolean.rb:2: warning: already initialized constant FALSE
=> true
[2] pry(main)> to_boolean(FALSE)
=> 0
[3] pry(main)> to_boolean(TRUE)
=> 1

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

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

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

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

def zero?(n)
 if n == 0
 true
 else
 false
 end
end

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

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

可以把代码写成

require "./number"
require "./boolean"

IS_ZERO = -> (proc) {
 proc[-> (x) {FALSE}][TRUE]
}

if __FILE__ == $0
 p to_boolean(IS_ZERO[ZERO])
 p to_boolean(IS_ZERO[ONE])
 p to_boolean(IS_ZERO[TWO])
end

运行结果是

1
0
0

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

3. 尾声

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

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

(0)

相关推荐

  • Ruby中使用Block、Proc、lambda实现闭包

    闭包(Closure),是指未绑定到任何对象的自由代码,闭包中的代码与任何对象和全局变量无关,只与执行此段代码的上下文相关. 今天我们简要的看一下ruby中的闭包实现. Ruby中的闭包实现有:Block,Proc,Lambada. 首先,我们来看Block. 复制代码 代码如下: ary = [1,2,3,4] ary.collect! do |a| a*a end ary.each do |a| puts a end 这段代码,我们使用了Array对象的block方法,将ary中的每个元素平

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

    前言 最近看一本叫做<计算的本质>的书,这本书主要说了一些底层计算方面的知识.可以说它刷新了我的三观,而当今天看到可以使用Y组合子来实现递归的时候我的世界观基本崩塌了.故借着七夕来写一篇文章总结一些关于计算的一些基本认识.以便后续可以更好地学习.也借着Ruby的语法来阐述一下关于Lambda的一些故事. 0. 题外话 为了庆祝一下这个七夕节日,我提前关掉了LOL,打开了Emacs,敲下如下代码(这里顺便推广一下Ruby的单件方法) subject = "情侣" object

  • Python爬虫利用cookie实现模拟登陆实例详解

    Cookie,指某些网站为了辨别用户身份.进行session跟踪而储存在用户本地终端上的数据(通常经过加密). 举个例子,某些网站是需要登录后才能得到你想要的信息的,不登陆只能是游客模式,那么我们可以利用Urllib2库保存我们以前登录过的Cookie,之后载入cookie获取我们想要的页面,然后再进行抓取.理解cookie主要是为我们快捷模拟登录抓取目标网页做出准备. 我之前的帖子中使用过urlopen()这个函数来打开网页进行抓取,这仅仅只是一个简单的Python网页打开器,其参数也仅有ur

  • 利用curl 多线程 模拟 并发的详解

    首先,先了解下 php中的curl多线程函数: 复制代码 代码如下: # curl_multi_add_handle# curl_multi_close# curl_multi_exec# curl_multi_getcontent# curl_multi_info_read# curl_multi_init# curl_multi_remove_handle# curl_multi_select 一般来说,想到要用这些函数时,目的显然应该是要同时请求多个url,而不是一个一个依次请求,否则不如

  • 利用Pygame制作简单动画的示例详解

    目录 前言 计时器 绘制精灵 加载精灵 完整代码 前言 实现一个帧动画,使用的一个图,根据不同的时间显示不同的图. 使用的就是如下所示的一张图,宽度780 * 300 ,使用加载图片 260 * 150来实现. pygame.init() screen = pygame.display.set_mode((400, 300), 0, 32) pygame.display.set_caption("动画") while True: for event in pygame.event.ge

  • 利用Python计算KS的实例详解

    在金融领域中,我们的y值和预测得到的违约概率刚好是两个分布未知的两个分布.好的信用风控模型一般从准确性.稳定性和可解释性来评估模型. 一般来说.好人样本的分布同坏人样本的分布应该是有很大不同的,KS正好是有效性指标中的区分能力指标:KS用于模型风险区分能力进行评估,KS指标衡量的是好坏样本累计分布之间的差值. 好坏样本累计差异越大,KS指标越大,那么模型的风险区分能力越强. 1.crosstab实现,计算ks的核心就是好坏人的累积概率分布,我们采用pandas.crosstab函数来计算累积概率

  • Python+Selenium键盘鼠标模拟事件操作详解

    目录 元素的基本操作 鼠标键盘模拟事件操作 利用 Keys 模块模拟键盘操作事件 利用 Action 类模拟鼠标操作事件 当我们定位到具体的一个元素的时候就可以对这个元素进行具体的操作,比如之前章节所执行的 click 操作.这是最简单的操作,webdriver 还有其他的操作.比如元素的基本操作(点击.输入.清除),还有一些高级操作如鼠标键盘模拟事件.弹出框处理.多页面切换等… 这些都是需要我们了解的内容,也是在做自动化测试的时候经常遇到的一些基本场景.今天这一章节,我们就先来学习一下元素的基

  • C++ String部分成员模拟实现流程详解

    目录 string类的成员设计 普通构造函数的模拟 拷贝构造函数的模拟 赋值重载函数的模拟 String的析构函数模拟 补全上述的成员函数 迭代器的简单模拟 其他成员函数的模拟 string类的成员设计 class string { private: char* _str; int _size; int _capacity; }; 说明:以下的五个成员函数的模拟实现,均去除了_size 和_capacity成员变量,目的是为了更方便解释重点.在五个成员函数模拟后,会对string类的设计进行补全

  • C++ Boost Lambda表达式详解

    目录 lambda表达式格式 说明Boost.Lambda lambda表达式格式 lambda表达式的格式 [捕捉列表](参数列表)mutable->返回值类型{ 语句部分 }; 其中参数列表.返回值类型是可选的,捕捉列表.函数体可以为空. 先来看一个较为简单的lamda表达式 int main(void) { auto add = [](int a, int b)->int {return a + b; }; cout << add(1, 2) << endl; r

  • python3.7简单的爬虫实例详解

    python3.7简单的爬虫,具体代码如下所示: #https://www.runoob.com/w3cnote/python-spider-intro.html #Python 爬虫介绍 import urllib.parse import urllib.request from http import cookiejar url = "http://www.baidu.com" response1 = urllib.request.urlopen(url) print("

  • 利用二进制文件安装etcd的教程详解

    etcd组件作为一个高可用强一致性的服务发现存储仓库. etcd作为一个受到ZooKeeper与doozer启发而催生的项目,除了拥有与之类似的功能外,更专注于以下四点. 简单:基于HTTP+JSON的API让你用curl就可以轻松使用. 安全:可选SSL客户认证机制. 快速:每个实例每秒支持一千次写操作. 可信:使用Raft算法充分实现了分布式. 场景一:服务发现(Service Discovery)一个强一致性.高可用的服务存储目录.基于Raft算法的etcd天生就是这样一个强一致性高可用的

随机推荐