提前祝元宵节快乐，分享最近看的一点有意思的东西
51 views
Skip to first unread message
bruce li
Feb 11, 2014, 3:04:13 PM2/11/14
to cn-cl...@googlegroups.com
提前祝大家元宵节好（在米帝读书，时间和国内不一致，提前发祝福以免忘记了）。
最近看程序语言的书，看到一个比较有意思的问题，拿来和大家分享一下，就当是过节的小品吧。(各位大神如果早知道了，请带走祝福，然后无视掉内容）。另这里有些内容是自己理解的，不当之处请指出。
首先提出一个问题:
给一个lambda函数，如何实现递归？要求不能使用recur关键词，不能产生side effects，以及不能给lambda函数命名，即不能使用(fn f [x] ...) 这种形式。
===================== 分割线 ======================
关于这个问题，先说说Russell悖论: 设P为所有不包含自己的集合的集合，P是否包含P?
在传统的集合论前提下，这个是无解的。而动态语言的类型系统和这个相似。假设一个函数F代表一个集合，F(x)返回True 表示x在这个集合内，返回 False表示x不在这个集合内。这样，集合{1,2,3}用函数表示就是: F(x) = (x==1 OR x==2 OR x==3).
那么前文提到的P用函数表示出来是: P(x) = Not (x x). 现在运行 P(P)， 这个程序会无限执行下去，即，无解。这里顺带说说我的理解，在计算理论里面有一个断言: x不属于Wx（x表示一个Godel Number，可以理解成把所有可计算的函数排列起来的一个编码，Wx表示编码为x这个函数的定义域), 这是不可计算问题。个人感觉和P(P) 有相似的地方，不知道对不对... 对于像Haskell之类的静态语言，它们定义了自己的类型系统，在它们的类型系统下，上文提到的P不能被定义。
接下来就是前文说的问题了，假设这个函数是sum 从n 到 0的所有数. 不考虑其他边界因素，这个函数的普通定义如下:
(defn sum [arg]
(if (= arg 0)
0
(+ arg (sum (- arg 1)))))
满足前文条件的函数可以定义为:
(def sum (fn [this]
(fn [arg]
(if (= arg 0)
0
(+ arg ((this this) (- arg 1)))))))
调用的时候，需要call: ((sum sum) 10)
这样通过函数把自己作为参数传递进去，达到了和递归一样的效果。
上面sum的定义，可以进一步被抽象出来，这就有了Y-combinator. 一种Y-combinator的定义可以是:
(def Y (fn [body]
(let [f (fn [this]
(fn [arg]
((body this) arg)))]
(f f))))
关于Y-combinator, 推荐看这个文章:
haosdent
Feb 16, 2014, 1:17:25 AM2/16/14
to cn-cl...@googlegroups.com
知乎上有一个与此相关的问答~http://www.zhihu.com/question/20115649
--
中文社区博客：http://blog.clojure.cn/
中文问答网站：http://ask.clojure.cn/
中文邮件列表：https://groups.google.com/d/forum/cn-clojure?hl=zh-CN
---
您收到此邮件是因为您订阅了 Google 网上论坛的“CN-Clojure”论坛。
要退订此论坛并停止接收此论坛的电子邮件，请发送电子邮件到 cn-clojure+...@googlegroups.com。
要向此网上论坛发帖，请发送电子邮件至 cn-cl...@googlegroups.com。
通过以下网址访问此论坛：http://groups.google.com/group/cn-clojure。
要查看更多选项，请访问 https://groups.google.com/groups/opt_out。
Best Regards,
Haosdent Huang
dennis zhuang
Feb 16, 2014, 2:26:22 AM2/16/14
to cn-cl...@googlegroups.com
可以看负暄琐话的这个系列：
也可以看看pongba的这篇文章：
Reply all
Reply to author
Forward
0 new messages