T*******x
发帖数: 8565 | 1 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
把任何递归程序以非递归的形式写出来。
我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
的讲法，所以写下来。
先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
为非递归形式。
比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
(def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
到括号结束的一堆字符，其中把w虚位，可以写成
f = (fn [n] (if (= n 0) 1 (* n (? (- n 1)))))
f(w)就是把问号换成w。f可以写成高阶函数的形式，
(def f (fn [w] (fn [n] (if (= n 0) 1 (* n (w (- n 1)))))))
f是递归函数w的“形式”，它本身不是递归函数。我们的目标是定义一个函数Y，或者
叫变换Y，使得Y(f)=w，这样我们就通过Y和f，两个非递归函数，复原了w这个递归函数
，达到了目标。
从w=f(w)这个形式，我们也可以说，w是f这个变换的不动点，fixed-point。所以我们
的目标也是找f的不动点，或者说是找一个变换，这个变换把f变为f的不动点，也就是Y
(f)=w。
这里最重要的一个trick是，定义一个函数u，such that，u(x):=f(x(x))。如果这样定
义了，那么代入u本身，
u(u)=f(u(u))，不动点有了，看得更清楚一点，令w=u(u)，那么w=f(w)。所以w=u(u)就
是f的不动点。所以Y变换也有了，Y(f)=u(u)。
来我们检查一下这是不是一个well defined function。首先给定任意递归函数的“形
式”f，它本身不是递归的，然后定义u，such that u(x):=f(x(x))，这个函数是well
define的吧？呵呵，数学上它肯定不是，这只是Clojure里well defined。好吧，既然u
是well defined，那么u(u)也是well defined，因此Y这个把f变成w=u(u)的变换也是
well defined。
先写到这，怕丢了。函数Y的形式一会再写。写出来发现只剩一点点了，就合到这里。
f是给定函数，不需要写。先写u，
(def u (fn [x] (f (x x))))
再写w，
(def w (u u))
再写Y，
(def Y (fn [f] w))
合在一起，
(def Y (fn [f] ((fn [x] (f (x x))) (fn [x] (f (x x))))))
哦！u的定义有问题，(x x)这个形式在Clojure里编译的时候会出现stack overflow，
因为它要展开，这个地方我还没完全想明白。总之这里需要另一个trick，使编译器
defer 展开，(x x)其结果应该是一个函数，是函数就可以写成等价形式，
(x x) = (fn [y] ((x x) y))
用这个等价形式替换(x x)的出现（两次），就得到
(def Y (fn [f] ((fn [x] (f (fn [y] ((x x) y)))) (fn [x] (f (fn [y] ((x x) y)
)))))) |
x***4
发帖数: 1815 | 2 paul graham 写了很多lisp 书和文章。后来开了家vc就叫ycombinator。
【在 T*******x 的大作中提到】
: 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
: 把任何递归程序以非递归的形式写出来。
: 我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
: 的讲法，所以写下来。
: 先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
: 为非递归形式。
: 比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
: (def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
: 这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
: 到括号结束的一堆字符，其中把w虚位，可以写成
|
c*******v
发帖数: 2599 | 3 For people who may interest:
(1)
https://dl.acm.org/citation.cfm?id=358210
The "Stage I" is a fixed point in C.
(2)
Explained in javascript
http://kestas.kuliukas.com/YCombinatorExplained/
【在 T*******x 的大作中提到】
: 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
: 把任何递归程序以非递归的形式写出来。
: 我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
: 的讲法，所以写下来。
: 先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
: 为非递归形式。
: 比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
: (def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
: 这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
: 到括号结束的一堆字符，其中把w虚位，可以写成
|
T*******x
发帖数: 8565 | 4 用factorial的那个f试一下，
(def factorial (Y f))
然后
(factorial 10)，
好使。
用跳马问题改一下，
(def moves [[1 2] [2 1] [-1 2] [2 -1] [1 -2] [-2 1] [-1 -2] [-2 -1]])
(def dim 5)
(defn possible-pos [path]
(let [seen (set path) pos (last path)]
(->> moves
(map #(map + pos %))
(filter (fn [[x y]] (and (>= x 0) (>= y 0) (< x dim) (< y dim))))
(remove #(seen %)))))
(defn jump+ [jump-]
(fn [path]
(if (= (count path) (* dim dim))
(list path)
(for [pos (possible-pos path)
fpath (jump- (conj path pos))]
fpath))))
(defn Y [f] ((fn [x] (f (fn [y] ((x x) y)))) (fn [x] (f (fn [y] ((x x) y))))
))
(def jump (Y jump+))
(jump [[0 0]])
也好使。
【在 T*******x 的大作中提到】
: 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
: 把任何递归程序以非递归的形式写出来。
: 我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
: 的讲法，所以写下来。
: 先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
: 为非递归形式。
: 比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
: (def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
: 这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
: 到括号结束的一堆字符，其中把w虚位，可以写成
|
c*******v
发帖数: 2599 | 5 编译器就是把递归程序写成非递归。
汇编语言里只有mov，jump，inc，没有递归。
所以fixed point和编译器的代数性质类似。
【在 T*******x 的大作中提到】
: 用factorial的那个f试一下，
: (def factorial (Y f))
: 然后
: (factorial 10)，
: 好使。
: 用跳马问题改一下，
: (def moves [[1 2] [2 1] [-1 2] [2 -1] [1 -2] [-2 1] [-1 -2] [-2 -1]])
: (def dim 5)
: (defn possible-pos [path]
: (let [seen (set path) pos (last path)]
|
d*******r
发帖数: 3299 | 6 所以看标题，我以为你们在讲融资了
【在 x***4 的大作中提到】
: paul graham 写了很多lisp 书和文章。后来开了家vc就叫ycombinator。
|
T*******x
发帖数: 8565 | 7 Thompson那个演讲不错，有意思。图2.1，2.2标记错了。看来bug无处不在啊。：）
【在 c*******v 的大作中提到】
: For people who may interest:
: (1)
: https://dl.acm.org/citation.cfm?id=358210
: The "Stage I" is a fixed point in C.
: (2)
: Explained in javascript
: http://kestas.kuliukas.com/YCombinatorExplained/
|
T*******x
发帖数: 8565 | 8 经过几次变换，Y变成这样了，
(defn Y [f] (#(% %) #(f (fn [x] ((% %) x)))))
最短，但是只有编译器能懂了。：）
【在 T*******x 的大作中提到】
: 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
: 把任何递归程序以非递归的形式写出来。
: 我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
: 的讲法，所以写下来。
: 先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
: 为非递归形式。
: 比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
: (def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
: 这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
: 到括号结束的一堆字符，其中把w虚位，可以写成
|
h*i
发帖数: 3446 | 9 这个trick还是挺有用的，主要是不用函数名字，这样就可以干很多优化的事情。
【在 T*******x 的大作中提到】
: 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
: 把任何递归程序以非递归的形式写出来。
: 我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
: 的讲法，所以写下来。
: 先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
: 为非递归形式。
: 比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
: (def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
: 这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
: 到括号结束的一堆字符，其中把w虚位，可以写成
|
T*******x
发帖数: 8565 | 10 不用函数名字就可以干很多优化的事情，这是什么原理啊？
【在 h*i 的大作中提到】
: 这个trick还是挺有用的，主要是不用函数名字，这样就可以干很多优化的事情。
|
|
|
h*i
发帖数: 3446 | 11 函数不用名字，就可以随意被wrapper来替换，而这些wrapper可以干各种优化的事情，
比如他们举例说的memoize，加cache，加各种附属信息，等等。
这个是我觉得的主要有用的地方。
【在 T*******x 的大作中提到】
: 不用函数名字就可以干很多优化的事情，这是什么原理啊？
|
C*****l
发帖数: 1 | 12 It is a fixed point in C, but C can not run itself.
【在 c*******v 的大作中提到】
: For people who may interest:
: (1)
: https://dl.acm.org/citation.cfm?id=358210
: The "Stage I" is a fixed point in C.
: (2)
: Explained in javascript
: http://kestas.kuliukas.com/YCombinatorExplained/
|
N*****r
发帖数: 94 | 13
这玩意儿属于函数式编程的基础知识吧
居然要在网上才发现
【在 T*******x 的大作中提到】
: 最近折腾Clojure递归程序，在网上发现一个东西叫Y-Combinator，挺神奇的，号称能
: 把任何递归程序以非递归的形式写出来。
: 我看了一个blog，又引到另一个blog，讲的还行，但是不直接，我发现了一个比较直接
: 的讲法，所以写下来。
: 先定义一下问题。目标是定义一个Clojure函数Y，把任何给定的Clojure递归程序转化
: 为非递归形式。
: 比如一个factorial函数吧，我们命名它为w。它的递归程序是这样的，
: (def w (fn [n] (if (= n 0) 1 (* n (w (- n 1))))))
: 这个定义可以写成这个形式：w=f(w)。其中f就是程序“形式”，也就是从括号fn开始
: 到括号结束的一堆字符，其中把w虚位，可以写成
|
j*****w
发帖数: 1 | 14 汇编语言有递归，call 指令。
所谓递归就是堆栈增长，用同样的指令操作不同的堆栈帧。
【在 c*******v 的大作中提到】
: 编译器就是把递归程序写成非递归。
: 汇编语言里只有mov，jump，inc，没有递归。
: 所以fixed point和编译器的代数性质类似。
|
g****t
发帖数: 31659 | 15 你说的对。我都全忘光了。
: 汇编语言有递归，call 指令。
: 所谓递归就是堆栈增长，用同样的指令操作不同的堆栈帧。
【在 j*****w 的大作中提到】
: 汇编语言有递归，call 指令。
: 所谓递归就是堆栈增长，用同样的指令操作不同的堆栈帧。
|
T*******x
发帖数: 8565 | 16 最近还是在玩functional programming。碰到了一个递归替换的问题，Java里的，还没
有完全解决。但是发现用Java也能写Y-Combinator。主要借助于Object这个universal
type。挺麻烦的，写完之后我都看不懂了。也用Python实现了一下，非常容易。 |
