1

所有人都试图弄清楚延续在 python 中是如何工作的。我有以下代码来使用 python cps 实现计算斐波那契（我意识到它正在构建一个堆栈，但对于这个问题，我希望这段代码就足够了）。

def fact_cps(n, k):
    print("n:%s" %(n))
    if n == 1:
        return k(1)
    else:
        return fact_cps(n - 1, lambda v: k(v * n) )

if __name__ == "__main__":
  print(fact_cps(3, (lambda i : i)))

我的问题是：

  • 在下面的输出中，lambda 变量“v”的值为 1
  • 这是由于前一个函数返回 k(1)
  • SO：“v = 1”发生的机制是什么？

不确定这是否是我对 lambda 的理解不足，特别是在 python 中或一般情况下。

跟踪执行：

python2 -m pdb python-cps-fact.py  < in > out

“in”是一个文件，包含重复的“s”和“a”调试输入，以重复步进/显示变量

s
a
....

在下面的“out”文件中，我用一行星号标出了我的问题的位置。

“out”是跟踪的输出：

> /home/mrostron/work/prolog/python-cps-fact.py(1)<module>()
-> def fact_cps(n, k):
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(8)<module>()
-> if __name__ == "__main__":
(Pdb) (Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(9)<module>()
-> print(fact_cps(3, (lambda i : i)))
(Pdb) (Pdb) --Call--
> /home/mrostron/work/prolog/python-cps-fact.py(1)fact_cps()
-> def fact_cps(n, k):
(Pdb) n = 3
k = <function <lambda> at 0x7fd438fe3aa0>
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(2)fact_cps()
-> print("n:%s" %(n))
(Pdb) n = 3
k = <function <lambda> at 0x7fd438fe3aa0>
(Pdb) n:3
> /home/mrostron/work/prolog/python-cps-fact.py(3)fact_cps()
-> if n == 1:
(Pdb) n = 3
k = <function <lambda> at 0x7fd438fe3aa0>
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(6)fact_cps()
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) n = 3
k = <function <lambda> at 0x7fd438fe3aa0>
(Pdb) --Call--
> /home/mrostron/work/prolog/python-cps-fact.py(1)fact_cps()
-> def fact_cps(n, k):
(Pdb) n = 2
k = <function <lambda> at 0x7fd438fe3ed8>
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(2)fact_cps()
-> print("n:%s" %(n))
(Pdb) n = 2
k = <function <lambda> at 0x7fd438fe3ed8>
(Pdb) n:2
> /home/mrostron/work/prolog/python-cps-fact.py(3)fact_cps()
-> if n == 1:
(Pdb) n = 2
k = <function <lambda> at 0x7fd438fe3ed8>
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(6)fact_cps()
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) n = 2
k = <function <lambda> at 0x7fd438fe3ed8>
(Pdb) --Call--
> /home/mrostron/work/prolog/python-cps-fact.py(1)fact_cps()
-> def fact_cps(n, k):
(Pdb) n = 1
k = <function <lambda> at 0x7fd438fe3d70>
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(2)fact_cps()
-> print("n:%s" %(n))
(Pdb) n = 1
k = <function <lambda> at 0x7fd438fe3d70>
(Pdb) n:1
> /home/mrostron/work/prolog/python-cps-fact.py(3)fact_cps()
-> if n == 1:
(Pdb) n = 1
k = <function <lambda> at 0x7fd438fe3d70>
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(4)fact_cps()
-> return k(1)
(Pdb) n = 1
k = <function <lambda> at 0x7fd438fe3d70>
*************************************** HERE
(Pdb) --Call--
> /home/mrostron/work/prolog/python-cps-fact.py(6)<lambda>()
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) v = 1
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(6)<lambda>()
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) v = 1
************************************************************
(Pdb) --Call--
> /home/mrostron/work/prolog/python-cps-fact.py(6)<lambda>()
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) v = 2
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(6)<lambda>()
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) v = 2
(Pdb) --Call--
> /home/mrostron/work/prolog/python-cps-fact.py(9)<lambda>()
-> print(fact_cps(3, (lambda i : i)))
(Pdb) i = 6
(Pdb) > /home/mrostron/work/prolog/python-cps-fact.py(9)<lambda>()
-> print(fact_cps(3, (lambda i : i)))
(Pdb) i = 6
(Pdb) --Return--
> /home/mrostron/work/prolog/python-cps-fact.py(9)<lambda>()->6
-> print(fact_cps(3, (lambda i : i)))
(Pdb) i = 6
(Pdb) --Return--
> /home/mrostron/work/prolog/python-cps-fact.py(6)<lambda>()->6
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) v = 2
(Pdb) --Return--
> /home/mrostron/work/prolog/python-cps-fact.py(6)<lambda>()->6
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) v = 1
(Pdb) --Return--
> /home/mrostron/work/prolog/python-cps-fact.py(4)fact_cps()->6
-> return k(1)
(Pdb) n = 1
k = <function <lambda> at 0x7fd438fe3d70>
(Pdb) --Return--
> /home/mrostron/work/prolog/python-cps-fact.py(6)fact_cps()->6
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) n = 2
k = <function <lambda> at 0x7fd438fe3ed8>
(Pdb) --Return--
> /home/mrostron/work/prolog/python-cps-fact.py(6)fact_cps()->6
-> return fact_cps(n - 1, lambda v: k(v * n) )
(Pdb) n = 3
k = <function <lambda> at 0x7fd438fe3aa0>
(Pdb) 6
--Return--
> /home/mrostron/work/prolog/python-cps-fact.py(9)<module>()->None
-> print(fact_cps(3, (lambda i : i)))
(Pdb) (Pdb) --Return--
> <string>(1)<module>()->None

非常感谢您花时间在这个先生上

4

2 回答 2

1

我不完全确定你的问题是什么。但是你的函数的定义fact_cps(n, k)是它返回k(n!).

  • 如果 n = 1，那么它只是直接调用 k(1)。
  • 如果 n > 1，则调用fact_cps(n, xxx)，其中 xxx 是将返回结果乘以 的函数，n然后调用k该新值。递归调用将返回 n * (n - 1)！= n!，然后我们调用k它。

最终结果是每次调用fact_cpsn > 1 调用fact_cps具有较小值的n，最终结果是k(n!)。您的外部调用将 k 设置为恒等函数，因此您得到 n！

根据您在下面所做的评论，我开始相信您并不完全了解 lambda 函数是什么。lambda 让您无需命名即可编写快速函数。

您的代码的行为与您编写的完全一样：

def fact_cps(n, k):
    print("n:%s" %(n))
    if n == 1:
        return k(1)
    else:
        def inner(v):
            return k(v * n)
        return fact_cps(n - 1, inner)

def identity(i):
    return i

if __name__ == "__main__":
  print(fact_cps(3, identity)

也许这将帮助您了解v来自哪里

于 2021-01-03T02:03:14.297 回答
0

PS我最初的想法是python将“k（1）”等同于“lambda v：k（v n）”，并且“v”的结果值是通过推断值（1）等于（v n )，并应用值 n=1，结果 t/f 为 v=1。

但我不相信这是正在发生的事情，而且我在这里没有看到一些东西。

于 2021-01-03T01:49:21.313 回答