内容简介:大家好,我是历小冰,也是张狗蛋,原为了获得留言功能,更好地与大家进行交流,我对原微信公众号进行了迁移。今后,大家可以直接在文章尾部给我留言,反馈文章的错误或者进行技术问题交流。新的微信公众号叫程序员历小冰,历冰是我在蚂蚁金服实习时的花名,也是我比较喜欢电视连续剧中主角的化名。可怜的张狗蛋,他一定会再回来的。: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由来?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Making Things See
Greg Borenstein / Make / 2012-2-3 / USD 39.99
Welcome to the Vision Revolution. With Microsoft's Kinect leading the way, you can now use 3D computer vision technology to build digital 3D models of people and objects that you can manipulate with g......一起来看看 《Making Things See》 这本书的介绍吧!
html转js在线工具
html转js在线工具
RGB CMYK 转换工具
RGB CMYK 互转工具