Problems with CPS'ing python functions

Steven Miale (smiale@cs.indiana.edu)
Fri, 27 May 1994 11:12:45 -0500

Both the following functions are attempts at writing a CPS'ed version of
a factorial function. (For non-Scheme programmers, CPS = Continuation
Passing Style).

def factcps(n, k):
if n==0:
return k(1)
else:
return factcps(n-1,lambda v:k(n*v))

def factcps2(n, k):
def cps(v):
return k(n*v)
if n==0:
return k(1)
else:
return factcps2(n-1,cps)

(for the record, equivalent Scheme code is:
(define fact-cps
(lambda (n k)
(if (zero? n)
(k 1)
(fact-cps (- n 1)
(lambda (v) (k (* n v)))))))
)

In both cases, accessing 'k' on the way back gives a NameError. In
other words, it gets to "return k(1)", but that return results in
calling k again ("return k(n*v)"), and neither k nor v are bound.

>From what I can gather, the local functions cps (in factcps2) and the
lambda (in factcps) are unable to access the environment of factcps2
and factcps, respectively.

Any ideas on how to solve the problem?

Thanks,

Steve

-- 
Steven Miale - smiale@cs.indiana.edu | Don't blame me - 
Indiana University, Bloomington, IN  | I voted Libertarian.