This seems like a very verbose, kinda-sorta continuation passing approach. Except that he's building the eventual continuation as a list of primitive functions instead of a complex function.
Ok, so a CPS transform starts by adding a new parameter, c, which I read "myReturn" or more likely, "returnapotamus". Then, you find the returns in the function and look at the expressions therein. An expression inside cost(...) is left alone, but the expression outside the application of cost is turned into an expression and then to a function that includes a call to returnapotamus, c:
def cost2(s, c=lambda s: s):
if s <= 1:
return c(0)
elif s % 2 == 0:
return cost2(s // 2, lambda s: c(s + 1))
else:
return cost2(s - 1, lambda s: c(min(1 + s, 5)))
def cost3(s):
cont = [ lambda s: s ]
while s > 1:
if s % 2 == 0:
cont.append(lambda s: s + 1)
s = s // 2
else:
cont.append(lambda s: min(s + 1, 5))
s = s - 1
result = 0
while len(cont) > 0:
result = cont.pop()(result)
return result
def cost5(s):
cont = lambda s: s
while s > 1:
if s % 2 == 0:
cont = lambda s, c=cont: c(s + 1)
s = s // 2
else:
cont = lambda s, c=cont: c(min(s + 1, 5))
s = s - 1
return cont(0)