Skip to content

Instantly share code, notes, and snippets.

@johnynek
Last active March 3, 2019 16:21
Show Gist options
  • Save johnynek/d4a2c2680dbfe479b0e641c3dd35b0a2 to your computer and use it in GitHub Desktop.
Save johnynek/d4a2c2680dbfe479b0e641c3dd35b0a2 to your computer and use it in GitHub Desktop.
Here is a port of this example y-combinator code: https://rosettacode.org/wiki/Y_combinator#Python except manually rewriting the lambdas into top-level functions accessing dictionaries to create closures.
def make_lambda(captured, fn, arity):
return {
"cap": captured,
"fn": fn,
"arity": arity,
"applied": [],
}
def apply_lambda(lam, arg):
app0 = lam["applied"]
app1 = app0 + [arg]
if len(app1) == lam["arity"]:
return lam["fn"](lam["cap"], app1)
else:
lam1 = dict(lam)
lam1["applied"] = app1
return lam1
def inner_lift(cap, args):
y = cap["y"]
app = apply_lambda(y, y)
return apply_lambda(app, args[0])
def arg_lift(cap, y):
f = cap["f"]
inner_lam = make_lambda({"y": y[0]}, inner_lift, 1)
return apply_lambda(f, inner_lam)
def y_lift(cap, f):
arg_lam = make_lambda({"f": f[0]}, arg_lift, 1)
return apply_lambda(arg_lam, arg_lam)
Y = make_lambda({}, y_lift, 1)
def fac_inner_lift(cap, arg):
f = cap["f"]
n = arg[0]
return 1 if n < 2 else n * apply_lambda(f, n - 1)
def fac_lift(cap, args):
f = args[0]
return make_lambda({"f": f}, fac_inner_lift, 1)
fac = make_lambda({}, fac_lift, 1)
yfac = apply_lambda(Y, fac)
print [ apply_lambda(yfac, i) for i in range(10) ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment