yet another question about python continuations

Question

all trying to work out how continuations work in python. i have the following code to calculate fibonacci using a python cps implementation ( i realize that it is building a stack, but for this question i am hoping this code will be sufficient ).

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)))

My question is:

• in the output below, the lambda variable "v" attains a value of 1
• this occurs as a result of the previous function returning k(1)
• SO: what is the mechanism by which "v=1" happens?

Not sure if this is my lack of understanding of lambda's specifically in python or in general.

Execution with trace:

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

"in" is a file containing repeated "s" and "a" debug inputs to step/display variables repeatedly

s
a
....

In the "out" file below, i have indicated the spot for my question by bounding it with a line of asterisks.

"out" is the output for the trace:

> /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

thanks v much for your time on this mr

Answer 1

PS my initial thought is that python is equating "k(1)" with "lambda v: k(vn)" and the resulting value for "v" is obtained by inferring that the value (1) is equal to (vn), and applying the value n=1, result t/f is v=1.

but i dont believe this is what is happening, and there is something that i am not seeing here.

Answer 2

I'm not completely sure what your question is. But the definition of your function fact_cps(n, k) is that it returns k(n!).

• If n = 1, then it just calls k(1) directly.
• If n > 1, then it calls fact_cps(n, xxx), where xxx is a function that multiplies the return result by n, and then calls k on that new value. The recursive call will return n * (n - 1)! = n!, and then we call k on that.

The net result is that each call of fact_cps with n > 1 calls fact_cps with a smaller value of n, and the final result is k(n!). Your outer call sets k to be the identity function, so you get n!

---

Based on the comments you've made below, I'm starting to believe that you don't completely understand what a lambda function is. A lambda lets you write a quick function without naming it.

Your code behaves exactly as if you had written:

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)

Perhaps this will help you see where the v is coming from