非递归 lambda 演算阶乘函数 [英] non recursive lambda calculus factorial function

问题描述

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

How to write a factorial function without use of recursion using lambda calculus? Meaning just the math notation not implementation in any particular programming language.

推荐答案

如果不使用递归"是指没有一般递归和因此，没有固定点(或自我应用)，我们可以简单地观察到阶乘函数是原始递归的(即本质上是迭代的)，并且通过迭代有一个非常通用和简单的原始递归编码(由教堂提供)数字)和对.我将讨论很有启发性的一般情况.让 <M,N > 是一些对的编码，让 fst 和 snd 是关联的预测.例如，您可以定义

If by "without the use of recursion" you mean without general recursion and hence without fixpoints (or self applications), we can simply observe that the factorial function is primitive recursive (that is, iterative, in essence), and there is a very general and simple encoding of primitive recursion by means of iteration (provided by church numerals) and pairs. I will discuss the general case that is quite instructive. Let < M,N > be some encoding of pairs, and let fst and snd be the associated projections. For instance, you can define

<M,N> = λz. z M N
fst = λp. p (λxy.x)
snd = λp. p (λxy.y)

假设有一个原始递归定义(不带参数，为简单起见)

Suppose to have a primitive recursive definition (without parameters, for the sake of simplicity)

f(0) = a
f(x+1) = h(x,f(x))

其中已经定义了 a 和 h.

where a and h have been already defined.

大体思路是使用一个辅助函数f'，其中

The general idea is to use an auxiliary function f', where

                       f'(x) = <x,f(x)>

所以，f'(0) = <0, a>, 并且给定对 p = <x,f(x) > = f'(x)，我们建立下一对 <x+1, f(x+1) > 通过计算第一个分量的后继并将 h 应用于这对参数(即，利用我们的对的编码，简单地说就是将延续 h 作为输入传递给对 p)

So, f'(0) = < 0, a>, and given the pair p = < x,f(x) > = f'(x), we build the next pair < x+1, f(x+1) > by computing the successor on the first component and applying h to the pair of arguments (that, taking advantage of our encoding of pairs, simply amounts to pass the continuation h as input to the pair p).

总结，

next = λp.< succ (fst p), p h>

最后，为了计算 f(n)，我们需要对函数进行 n 次迭代从 < 开始0，a>，然后取第二个分量:

Finally, to compute f(n) we need to iterate n times the function next starting from < 0, a>, and then take the second component:

 f = λn. snd (n next <0,a>)

这篇关于非递归 lambda 演算阶乘函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！