前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >历小冰的由来和神奇的丘奇数

历小冰的由来和神奇的丘奇数

作者头像
程序员历小冰
发布2019-12-06 12:19:15
8300
发布2019-12-06 12:19:15
举报
文章被收录于专栏:程序员历小冰

大家好,我是历小冰,也是张狗蛋,原张狗蛋的技术之路的博主。

为了获得留言功能,更好地与大家进行交流,我对原微信公众号进行了迁移。今后,大家可以直接在文章尾部给我留言,反馈文章的错误或者进行技术问题交流。

新的微信公众号叫程序员历小冰,历冰是我在蚂蚁金服实习时的花名,也是我比较喜欢电视连续剧中主角的化名。可怜的张狗蛋,他一定会再回来的。??

接下来,我还是会持续关注后端开发技术,为大家带来更具阅读价值的文章。

文章太短,拿一篇很久之前我写的文章,介绍一下神奇的丘奇数,它能让你思考计算机中的”数“到底是什么。当时我对这些”奇技淫巧“还是很感兴趣的,一本《SICP》看了好久,可惜最终还是没有看完。??

原文发布在CSDN上,链接在文末中有。以下在原文的基础上略加修改。

最近一直在阅读《SICP》,然后下午做其中的习题2.6,对其题意很不理解,于是搜索了相关资料,不禁如题设所说感到如雷灌顶,特此记录下来,以供大家阅读和交流。

题目

请考虑,在一个可以对程序做各类操作的语言中,我们完全可以没有数(至少是没有整数,比如说0,1,2)的情况下,可以将 zero 和加一操作实现为:

代码语言:javascript
复制
(define zero (lambda (f) (lambda (x) x)))  # 定义zero
(define (add-1 n)
    (lambda (f) (lambda (x) (f ((n f) x))))) # 定义加一操作

上述语言是LISP,同学们不必了解其语法,也能大致了解语句的含义。下一小节中会做出具体的解释。

这一表现形式称为 Church 计数,也就是丘奇数,名字来源于其发明人数理学家 Church,请直接定义 one 和 two(不使用 zero 和 add-1 )(提示:利用代换法去求值)。请给出加法过程 + 的一个直接定义(不要反复应用 add-1 )

丘奇数

说实话,我一直没有看懂题目中关于 zero 和 add-1 的定义,于是我搜索了相关资料。下边就结合资料谈一下它的概念。

首先要明确的是丘奇数中的 zero,one 并不等同于数值上的 0, 1, 2。你可以理解为它是零概念的一种表现形式。换句话说,它就是零的函数式表现形式,而整数0则是零的数值表现形式。我们先来看一下丘奇数中 zero,one 和 two 的表现形式。

代码语言:javascript
复制
(define zero
  (lambda (f) (lambda (x) x)))
(define one
  (lambda (f) (lambda (x) (f x))))
(define two
  (lambda (f) (lambda (x) (f (f x)))))

我们会发现 zero,one 和 two 都是一个函数,它接收 (f) 作为参数,其返回结果是一个接收 (x) 作为参数的函数。大家可能需要注意的是,(f) 在这里显然也是一个函数,在 LISP 中函数是可以作为输入参数的。然后我们会发现 zero,one 和 two 的区别好像就是 (f) 函数被使用的次数。 zero 中 (f) 没有被使用,one 中 (f) 使用了一次,two 中 (f) 使用了两次。丘奇数就是用这个次数来表示 0, 1, 2 的概念。

我们可以实验一下检验一下

代码语言:javascript
复制
(define (inc n) (+ n 1)) ;inc是加一操作,作为zero的参数,返回一个函数,作用于数字0
> ((zero inc) 0)  
0 
> ((zero inc) 1)
1
> ((one inc) 1)
2
> (((add-1 one) inc) 1)
3

我们定义一个过程 inc 就是数值意义上的加一,然后使用 zero, one和 add-1 发现确实如同我们所想的,zero 表示 inc 过程不会被使用,返回原数值;one 表示 inc 被使用一次,返回加一的数值。

替换法求one

我们来使用替换法通过 add-1 和 zero 来求解 one 吧,求解 two 的过程类似。

代码语言:javascript
复制
(add-1 zero) 
;展开add-1定义
(lambda (f) (lambda (x) (f ((zero f) x))))

; 替换zero
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))

; 简化,因为((lambda (x) x) x)就等于x
(lambda (f) (lambda (x) (f x)))
加法定义

首先我们要明白丘奇数加法的含义,我们先记其加法为 add-church ,那么如下代码所示,最后一个过程得出的值应该是多少呢?

代码语言:javascript
复制
> ((one incr) 1)
2
> ((two incr) 1)
3
> (((add-church one two) incr) 1)
?

根据猜测,应该是4吧。因为 one 表示 incr 对 1 这个数值使用一次,two 标示使用两次,那么将二者加起来,那么就应该是 three 的含义啦,就是表示 incr 对 1 这个数值使用 3 次,那么就是 4 啦。

add-church 的实现如下

代码语言:javascript
复制
(define (add-church m n)
   (lambda (f) (lambda (x) ((m f) ((n f) x)))))
(define (add-1 n)
    (lambda (f) (lambda (x) (f ((n f) x))))) # 定义加一操作

如果你将其与 add-1 进行对比,你会发现 add-1 中的 f 变成了(m f) ,如果把 add-1 中的 f 记住(one f),你可能就会更加理解。

比如 (f) 为 incr 函数,(n incr) 的结果就是一个进行 n 次 incr 的函数,(incr ((n incr) x)) 就是在 (n incr) 的基础上再进行一次 incr,所以就表示了 add-1 操作。所以((m incr) ((n incr) x))就代表在 (n incr) 的基础上再进行 m 次 incr,所以就是 add-church 操作。

那么大家思考一下, add-m 应该如何表示呢?

参考资料

  • https://pfmiles.wordpress.com/2009/11/12/%E9%80%90%E6%AD%A5%E7%90%86%E8%A7%A3%E4%B8%98%E5%A5%87%E6%95%B0%E4%B8%80/
  • http://www.billthelizard.com/2010/10/sicp-26-church-numerals.html
  • CSDN上的原文:https://blog.csdn.net/u012422440/article/details/51291403
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-06-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员历小冰 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 丘奇数
  • 替换法求one
  • 加法定义
  • 参考资料
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档