-
-
Save divs1210/d218d4b747b08751b2a232260321cdeb to your computer and use it in GitHub Desktop.
| import types | |
| # Helpers | |
| # ======= | |
| def _obj(): | |
| '''Dummy object''' | |
| return lambda: None | |
| _FILLER = _obj() | |
| # API | |
| # === | |
| def Y(g): | |
| '''Y combinator - makes recursive lambdas | |
| ex: Y(lambda fact: | |
| lambda n: | |
| 1 if n < 2 else n * fact(n - 1))(5) | |
| gives: 120 | |
| ''' | |
| exp = lambda f: g(lambda arg: f(f)(arg)) | |
| return (exp)(exp) | |
| def COND(cond_body_pairs, _else=lambda: None): | |
| '''Functional if-elif-...-else expression | |
| ex: COND((1==0, lambda: 'a', | |
| 2==0, lambda: 'b', | |
| 3==0, lambda: 'c'), | |
| _else= lambda: 'd') | |
| gives: 'd' | |
| Note: All conditions are evaluated immediately! | |
| For conditions that should be evaluated only | |
| when required, use IF. | |
| ''' | |
| if len(cond_body_pairs) == 0: | |
| return _else() | |
| cond, body = cond_body_pairs[:2] | |
| if cond: | |
| return body() | |
| else: | |
| return COND(cond_body_pairs[2:], _else) | |
| def IF(cond, then, _else=lambda: None): | |
| '''Functional if-then-else expression | |
| ex: IF(1==0, lambda: 'a', | |
| _else= lambda: 'b') | |
| gives: 'b' | |
| ''' | |
| return COND((cond, then), _else) | |
| def LET(bindings, body, env=None): | |
| '''Introduce local bindings. | |
| ex: LET(('a', 1, | |
| 'b', 2), | |
| lambda o: [o.a, o.b]) | |
| gives: [1, 2] | |
| Bindings down the chain can depend on | |
| the ones above them through a lambda. | |
| ex: LET(('a', 1, | |
| 'b', lambda o: o.a + 1), | |
| lambda o: o.b) | |
| gives: 2 | |
| ''' | |
| if len(bindings) == 0: | |
| return body(env) | |
| env = env or _obj() | |
| k, v = bindings[:2] | |
| if isinstance(v, types.FunctionType): | |
| v = v(env) | |
| setattr(env, k, v) | |
| return LET(bindings[2:], body, env) | |
| def FOR(bindings, body, env=None): | |
| '''Clojure style List comprehension. | |
| ex: FOR(('a', range(2), | |
| 'b', range(2)), | |
| lambda o: (o.a, o.b)) | |
| gives: [(0, 0), (0, 1), (1, 0), (1, 1)] | |
| Bindings down the chain can depend on | |
| the ones above them through a lambda | |
| like in LET. | |
| Special bindings take lambdas as values | |
| and can be used any number of times: | |
| * ':LET' - Temporary bindings | |
| * ':IF' - don't produce a value if this | |
| returns a falsey value | |
| * ':WHILE' - break out of the innermost | |
| loop if this returns a falsey value | |
| ''' | |
| if len(bindings) == 0: | |
| tmp = body(env) | |
| return [] if tmp is _FILLER else [tmp] | |
| env = env or _obj() | |
| k, v = bindings[:2] | |
| if k == ':IF': | |
| cond = v(env) | |
| return FOR(bindings[2:], | |
| lambda e: body(e) if cond else _FILLER, | |
| env) | |
| elif k == ':LET': | |
| return LET(v, | |
| lambda e: FOR(bindings[2:], body, e), | |
| env) | |
| elif k == ':WHILE': | |
| if v(env): | |
| return FOR(bindings[2:], body, env) | |
| else: | |
| return [] | |
| elif isinstance(v, types.FunctionType): | |
| v = v(env) | |
| res = [] | |
| for x in v: | |
| setattr(env, k, x) | |
| res += FOR(bindings[2:], body, env) | |
| delattr(env, k) | |
| return res | |
| # Tests | |
| # ===== | |
| ## LET form | |
| assert LET(('a', 2, | |
| 'b', lambda o: o.a * 3), | |
| lambda o: o.b - 1) == 5 | |
| ## Y combinator (recursive lambda) and IF form | |
| assert Y(lambda fact: | |
| lambda n: | |
| IF(n < 2, lambda: 1, | |
| _else= lambda: n * fact(n - 1)))(5) == 120 | |
| ## FOR comprehension | |
| assert FOR(('a', range(3)), | |
| lambda o: o.a + 1) == [1, 2, 3] | |
| ## Chained FOR comprehension | |
| assert FOR(('a', range(3), | |
| ':IF', lambda o: o.a > 0, | |
| 'b', lambda o: range(3 - o.a), | |
| ':LET', ('res', lambda o: [o.a, o.b]), | |
| ':WHILE', lambda o: o.a < 2), | |
| lambda o: o.res) == [ | |
| # filtered a == 0 | |
| [1, 0], [1, 1], | |
| # stopped at a == 2 | |
| ] |
Brilliant! I had been replacing my need for let x = ... ,,, with ((lambda x ,,,) ...), producing monsters like this (a fast memoized Fibonacci when fed to a 2-arg Y combinator):
ff_e = (lambda f:
(lambda a:
(lambda n:
(a, 1) if n < 2 else
((lambda n_1:
(a, a[n_1]) if n_1 in a else
((lambda fim1:
((lambda m1:
((lambda r1:
((lambda a1:
((lambda n_2:
(a1, r1 + a1[n_2]) if n_2 in a1 else
((lambda fim2:
((lambda m2:
((lambda r2:
((lambda a2:
(a2, r1 + r2))
(m2[0] | {n_2: r2})))
(m2[1])))
(fim2(n_2))))
(f(a1))))
(n - 2)))
(m1[0] | {n_1: r1})))
(m1[1])))
(fim1(n_1))))
(f(a))))
(n - 1)))))
ouch, that's gnarly! 😅
glad to be of help!
It's from this fully-typed development of Y https://github.com/rebcabin/rebcabin.github.io/blob/main/PythonYCombinators.ipynb . I'm working my way through "Lambda, the Ultimate Imperative" as part of a new Python compiler https://lpython.org
@rebcabin Nice!
I can't seem to find much to read about LCompilers or ASR online, though.
Could you point me to some literature?
@rebcabin Would love to know more about the ASR stuff!
I had gone through the LCompilers website and github, but didn't find much info.
Went through the LFortran page this time, and saw some more details.
We will never extend a language, but we may subset it for speed.
This seems to not be true for LFortran, with the extended global scope and type inference.
Could I be of help in some way? Would love to contribute to LPython!
I have seen two different ways of speeding up Python using PE - PyPy tracing JIT and Graal's self-modifying AST.
The ASR stuff looks like a variant of PE from afar, correct me if I'm wrong!
Yes, I will get back to you here with some info on contributing to LPython!
BTW, I am running with one of your ideas to build a Schemulation of Python's imperatives so that we are sure we know what we're doing when we design ASR.
@divs1210 we would love any contributions. You are welcome to send a PR, you can join us at the Zulip chat (https://lfortran.zulipchat.com/, we use it for LPython as well for now), and I am also happy to meet with you to get you up and running.
Check out similar exercises: