Lambda 微积分——使用 Mocking Bird 表达的函数似乎应该是递归的，但不是

Question

使用JavaScript。让我们定义以下内容：

M = f => f(f)  // Mocking Bird
I = a => a  // Identity

假设现在我们写这个表达式

M( f => M( x => f) )

这似乎是递归的并且会达到最大调用堆栈。让我们展开一次

( f => M( x => f) )  (f => M( x => f) )

我们看到我们可以继续前进

(f => (x => f)( x => f))(f => (x => f)( x => f))

(x => (f => (x => f)( x => f)))(x => (f => (x => f)( x => f)))

...等等。但在浏览器或节点中，这不是递归的。它是一个行为类似于 Identity

的函数

I('foobar')
// returns 'foobar'

M( f => M( x => f) )('foobar')
// returns 'foobar'

(x => (f => (x => f)( x => f)))(x => (f => (x => f)( x => f))) ('foobar')
// returns 'foobar'

请解释为什么该函数在达到最大调用堆栈之前不会继续调用自身，而是 returns 一个行为类似于 Identity

的函数

同样的现象可以用Python

来表达

M = lambda f: f(f)
I = lambda a: a

M( lambda f: M(lambda x: f)) ('foobar')
# returns 'foobar'

I('foobar')
# returns 'foobar'

更新

开始于

M( f => M( x => f) )

如果我们写出内层M( x => f)

M( f => ( x=> f )(x => f) )

我们看到传递给 (x => f)(x => f) 的内容并不重要，x 被忽略，returns 只是 f

M( f => f )

简直就是

f => f

Answer 1

 M(/*a*/ f => M( /*b*/ x => f) )('foobar')

a 被调用 f = a :

M(/*b*/ x => *a*)

b 被称为 x 是 b 它 returns a :

/*a*/ f => M(/*b*/ x => f)

用"foobar"调用，所以f是“foobar”：

M(/*b*/ x => "foobar")

返回“foobar”

基本上它是有效的，因为：

M( x => f)

总是returnsf，所以整个等于

M( f => f )

然后：

(f => f)(f => f)

也就是

f => f

Lambda 微积分——使用 Mocking Bird 表达的函数似乎应该是递归的，但不是

Lambda Calculus -- function expressed using Mocking Bird seems like it should be recursive but is not

javascript

python

recursion

functional-programming

lambda-calculus

更新