3 ms·
This sounds really interesting, but I'm getting a bit confused trying to apply it to a simpler problem. Say I start with this recursive function to filter a lis
by peconn 7y ago
This sounds really interesting, but I'm getting a bit confused trying to apply it to a simpler problem. Say I start with this recursive function to filter a list:
def my_filter_recursive(l, f):
if l:
x, *xs = l
if f(x):
return [x] + my_filter_recursive(xs, f)
else:
return my_filter_recursive(xs, f)
else:
return []
In Continuation Passing Style it becomes:
def my_filter_cps(l, f, kont):
if l:
x, *xs = l
if f(x):
my_filter_cps(xs, f, lambda y: kont([x] + y))
else:
my_filter_cps(xs, f, lambda y: kont(y))
else:
kont([])
Then I think with defunctionalisation it becomes:
def my_filter_defun(l, f, kont):
if l:
x, *xs = l
if f(x):
my_filter_defun(xs, f, KontAdd(x, kont))
else:
my_filter_defun(xs, f, KontSkip(kont))
else:
kont.apply([])
class KontAdd:
def __init__(self, var, kont):
self.var = var
self.kont = kont
def apply(self, acc):
self.kont.apply([self.var] + acc)
class KontSkip:
def __init__(self, kont):
self.kont = kont
def apply(self, acc):
self.kont.apply(acc)
class KontPrint:
def apply(self, acc):
print(acc)
Is that right? It seems that we've basically just moved the recursion from one place to another.
- chongli 7y agoIt seems that we've basically just moved the recursion from one place to another. Yes, the point is to move the recursion from the code into the data structures. These data structures can then be stored and retrieved conveniently. It's a technique for making micro eDSLs to solve common problems. Having said that, it's a lot more applicable to some languages than others. Python, lacking algebraic data types and static typing, does not make it very convenient to use this technique.
- elricto 7y agoHello peconn, This is right, although you could replace KontSkip(kont) with just kont. Defunctionalization does not just "move the recursion from one place to another." Rather, it doesn't change the recursion at all. Also, your example is actually harder than the one in the talk, because it can involve an arbitrary amount of work after the last call to my_filter_recursive. Like in the example in the talk, you still need merge the various calls to apply, and use tail-call elimination. Merging: def apply(kont, acc): if isinstance(kont, KontAdd): apply(kont.kont, [kont.var] + acc) else: print(acc) You will now actually need two levels of tail-call elimination because there are two recursions, rather than one as in the example in the talk. apply becomes this: def apply(kont, acc): while True: if isinstance(kont, KontAdd): kont = kont.kont acc = [kont.var] + acc else: print(acc) break You can then inline this into my_filter_cps and do tail-call elimination again. def my_filter_defun(l, f, kont): while True: if l: x, *xs = l if f(x): l = xs kont = KontAdd(x, kont) else: l = xs else: acc = [] while True: if isinstance(kont, KontAdd): kont = kont.kont acc = [kont.var] + acc else: print(acc) break
- mamcx 7y agoOne little beef with CPS (for an interpreter) is that use it cause a hit on performance. Defunctionalization could be use to improve on that?