-
-
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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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