非递归lambda演算因子函数

Question

如何在不使用lambda演算的递归的情况下编写阶乘函数？这意味着数学符号不能在任何特定的编程语言中实现.

Answer 1

我没有说什么我不是故意的

通过"不使用递归",你必须意味着"没有一个函数自称为名字 "

无论如何,让我们写下因子

fact := ?n. zero? n one (mult n (fact (dec n)))

现在,我们并不特别在意zero?,mult,dec,甚至one在这个例子中,你可以自己实现这些 - 我们只想删除粗体,按名称递归,

... fact (dec n)

最简单的方法是将lambda应用于自身 - 遇到U组合器

U := ?f. f f

现在,我们可以将原始表达式包装在lambda中,然后应用 U

fact := U (?f. ?n. zero? n one (mult n (??? (dec n))))

但是我们用什么代替fact？- 回想一下,这f是对外部lambda本身的引用,所以为了在下一个"迭代"中使它成为相同的情况,我们必须适用f于它自己,就像你做的那样 - 事实上,你可以把U视为一个一种镜子,你的功能可以反射回那个镜子,以便重现; 只有这一次,没有使用名称^ _ ^

fact := U (?f. ?n. zero? n one (mult n (f f (dec n))))

是的,是的,但更精明的是会注意到你也可以直接在lambda里面使用镜子(U)

fact := U (?f. ?n. zero? n one (mult n (U f (dec n))))

没有你扩大

我们知道如何扩展内心 - 我们第一次就这样写了

fact := U (?f. ?n. zero? n one (mult n (f f (dec n))))

现在扩展外部U.

fact := (?f. ?n. zero? n one (mult n (f f (dec n)))) (?f. ?n. zero? n one (mult n (f f (dec n))))

它有用吗？

所有教堂数字都表示为#N

fact := U ?f. ?n. zero? n #1 (mult n (U f (dec n)))

fact #4

U (?f. ?n. zero? n #1 (mult n (U f (dec n))) #4

(?f. f f) (?f. ?n. zero? n #1 (mult n (U f (dec n))) #4

(?f. ?n. zero? n #1 (mult n (U f (dec n))) (?f. ?n. zero? n #1 (mult n (U f (dec n))) #4

(?n. zero? n #1 (mult n (U (?f. ?n. zero? n #1 (mult n (U f (dec n))) (dec n))) #4

zero? #4 #1 (mult #4 (U (?f. ?n. zero? n #1 (mult n (U f (dec n))) (dec #4)))

zero? #4 #1 (mult #4 (U (?f. ?n. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// (zero? #4); false; returns second argument
(mult #4 (U (?f. ?n. zero? n #1 (mult n (U f (dec n))) (dec #4)))

// which is #4 * ...
(U (?f. ?n. zero? n #1 (mult n (U f (dec n))) (dec #4))

// which is ...
(U (?f. ?n. zero? n #1 (mult n (U f (dec n))) #3)

// which is equivalent to...
fact #3

// so ...
(mult #4 (fact #3))

// repeating this pattern ...
(mult #4 (mult #3 (fact #2))
(mult #4 (mult #3 (mult #2 (fact #1)))
(mult #4 (mult #3 (mult #2 (mult #1 (fact #0))))
(mult #4 (mult #3 (mult #2 (mult #1 #1))))
(mult #4 (mult #3 (mult #2 #1)))
(mult #4 (mult #3 #2))
(mult #4 #6)
#24

在javascript中演示

继续用您自己的眼球观察U组合器的力量!

const U =
  f => f (f)
  
const fact =
  U (f => n =>
    n === 0 ? 1 : n * U (f) (n - 1))
    
console.log (fact (4)) // 24

再次作为纯粹的lambda表达

console.log (
  (f => n => n === 0 ? 1 : n * f (f) (n - 1))
    (f => n => n === 0 ? 1 : n * f (f) (n - 1))
      (4)
) // 24

相互递归

上面的代码片段展示了这个递归过程的一个非常重要的属性:它是相互递归的.正如您所看到的,实际上有两个(尽管是相同的)函数驱动递归; 调用B,B调用A - 但是在U组合器的情况下,只有一个函数可以应用于自身,因此它确实实现了直接递归 - lambda使用其参数而不是其名称来调用自身( lambdas没有名字可以打电话)

是吗？

因为我说过

U组合器有点麻烦,因为它希望用户"反映"函数以便重复 - 如果我们可以为外部lambda提供一个镜像本身的功能呢？

U := ?f. f f
Y := ?g. U (?f. g (U f))

我将再次向你展示相同的定义,但在两条线上,你可以看到"镜子"和它们的位置

          / g, user's function
         /
        /  / outer reflection
       /  /
Y := ?g. U (?f.   ...   )
                g (U f)
                 \
                  \ call g with inner reflection

所以现在,每当你应用于Y任何lambda(g)时,它的参数就成为计算lambda本身的函数 - fact改为

fact := Y (?f. ?n. zero? n one (mult n (f (dec n))))

扩大Y.

Y := ?g. U (?f. g (U f))             // expand inner U
Y := ?g. U (?f. g (f f))             // expand outer U
Y := ?g. (?f. g (f f)) (?f. g (f f))

这是你在维基百科中看到的定义; 只是alpha重命名

我刚才有一个深刻的发现

从U上面得到Y,我看到了一些我以前从未见过的东西 - 一个隐藏的B

Y := ?g. U (?f. g (U f))

B := ?f. ?g. ?x. f (g x)

Y' := ?g. U (B g U)

我见过的最美丽的东西之一 - 它也有效 ; 不是我们应该有任何理由认为它不会......

#lang lazy

(define B (? (f)
            (? (g)
              (? (x)
                (f (g x))))))

(define U (? (f)
            (f f)))

(define Y (? (g)
            (U ((B g) U))))

(define fact (Y (? (f)
                  (? (n)
                    (if (= n 0)
                        1
                        (* n (f (sub1 n))))))))

(fact 4) ;; 24

Haskellers

你见过Y表达过吗？

Y = U . (. U)
  where U f = f f