内容简介:大家好,我是历小冰,也是张狗蛋,原为了获得留言功能,更好地与大家进行交流,我对原微信公众号进行了迁移。今后,大家可以直接在文章尾部给我留言,反馈文章的错误或者进行技术问题交流。新的微信公众号叫程序员历小冰,历冰是我在蚂蚁金服实习时的花名,也是我比较喜欢电视连续剧中主角的化名。可怜的张狗蛋,他一定会再回来的。:grin::grin:
大家好,我是历小冰,也是张狗蛋,原 张狗蛋的技术之路的博主 。
为了获得留言功能,更好地与大家进行交流,我对原微信公众号进行了迁移。今后,大家可以直接在文章尾部给我留言,反馈文章的错误或者进行技术问题交流。
新的微信公众号叫 程序员 历小冰,历冰是我在蚂蚁金服实习时的花名,也是我比较喜欢电视连续剧中主角的化名。可怜的张狗蛋,他一定会再回来的。:grin::grin:
接下来,我还是会持续关注后端开发技术,为大家带来更具阅读价值的文章。
文章太短,拿一篇很久之前我写的文章,介绍一下神奇的丘奇数,它能让你思考计算机中的”数“到底是什么。当时我对这些”奇技淫巧“还是很感兴趣的,一本《SICP》看了好久,可惜最终还是没有看完。:joy::joy:
原文发布在CSDN上,链接在文末中有。以下在原文的基础上略加修改。
最近一直在阅读《SICP》,然后下午做其中的习题2.6,对其题意很不理解,于是搜索了相关资料,不禁如题设所说感到如雷灌顶,特此记录下来,以供大家阅读和交流。
题目
请考虑,在一个可以对程序做各类操作的语言中,我们完全可以没有数(至少是没有整数,比如说0,1,2)的情况下,可以将 zero 和加一操作实现为:
上述语言是LISP,同学们不必了解其语法,也能大致了解语句的含义。下一小节中会做出具体的解释。
这一表现形式称为 Church 计数,也就是丘奇数,名字来源于其发明人数理学家 Church,请直接定义 one 和 two(不使用 zero 和 add-1 )(提示:利用代换法去求值)。请给出加法过程 + 的一个直接定义(不要反复应用 add-1 )
丘奇数
说实话,我一直没有看懂题目中关于 zero 和 add-1 的定义,于是我搜索了相关资料。下边就结合资料谈一下它的概念。
首先要明确的是丘奇数中的 zero,one 并不等同于数值上的 0, 1, 2。你可以理解为它是零概念的一种表现形式。换句话说,它就是零的函数式表现形式,而整数0则是零的数值表现形式。我们先来看一下丘奇数中 zero,one 和 two 的表现形式。
我们会发现 zero,one 和 two 都是一个函数,它接收 (f) 作为参数,其返回结果是一个接收 (x) 作为参数的函数。大家可能需要注意的是,(f) 在这里显然也是一个函数,在 LISP 中函数是可以作为输入参数的。然后我们会发现 zero,one 和 two 的区别好像就是 (f) 函数被使用的次数。 zero 中 (f) 没有被使用,one 中 (f) 使用了一次,two 中 (f) 使用了两次。 丘奇数 就是用这个次数来表示 0, 1, 2 的概念。
我们可以实验一下检验一下
我们定义一个过程 inc 就是数值意义上的加一,然后使用 zero, one和 add-1 发现确实如同我们所想的,zero 表示 inc 过程不会被使用,返回原数值;one 表示 inc 被使用一次,返回加一的数值。
替换法求one
我们来使用替换法通过 add-1 和 zero 来求解 one 吧,求解 two 的过程类似。
加法定义
首先我们要明白丘奇数加法的含义,我们先记其加法为 add-church ,那么如下代码所示,最后一个过程得出的值应该是多少呢?
根据猜测,应该是4吧。因为 one 表示 incr 对 1 这个数值使用一次,two 标示使用两次,那么将二者加起来,那么就应该是 three 的含义啦,就是表示 incr 对 1 这个数值使用 3 次,那么就是 4 啦。
add-church 的实现如下
如果你将其与 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
以上所述就是小编给大家介绍的《历小冰的由来和神奇的丘奇数》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- WebAssembly 的由来
- Service Mesh 的由来
- 科普 | 价值互联网的由来
- 简单说说访问者模式的由来
- WebSocket的故事(一)—— WebSocket的由来
- Android(IPC)进程间通讯1:详解Binder由来?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Kotlin实战
【美】Dmitry Jemerov(德米特里·詹莫瑞福)、【美】 Svetlana Isakova(斯维特拉娜·伊凡诺沃) / 覃宇、罗丽、李思阳、蒋扬海 / 电子工业出版社 / 2017-8 / 89.00
《Kotlin 实战》将从语言的基本特性开始,逐渐覆盖其更多的高级特性,尤其注重讲解如何将 Koltin 集成到已有 Java 工程实践及其背后的原理。本书分为两个部分。第一部分讲解如何开始使用 Kotlin 现有的库和API,包括基本语法、扩展函数和扩展属性、数据类和伴生对象、lambda 表达式,以及数据类型系统(着重讲解了可空性和集合的概念)。第二部分教你如何使用 Kotlin 构建自己的 ......一起来看看 《Kotlin实战》 这本书的介绍吧!