search

chatziko / lci

A lambda calculus interpeter
https://www.chatzi.org/lci/
GNU General Public License v2.0
64 stars 7 forks source link

Performance Optimizations #6

Closed HalosGhost closed 3 years ago

HalosGhost commented 5 years ago

I have not thoroughly gone through the standard library, but I did spot an opportunity for a performance optimization:

-If = \z.\x.\y.z x y;
+If = I;

Because If takes “three” arguments and applies them in-order, it is effectively identical to the identity function.

Is this kind of change interesting to you / would it be accepted if I were to go through the std lib and make this kind of optimization?

In my mind, this is roughly the same as how 1 resolves to \f.f instead of \f.\z.f z.

chatziko commented 3 years ago

Fixed in master (together with lots of good stuff, check the ChangeLog, I felt like working on lci after a long time :smile: ).

I also changed the printer to show I instead of \x.x, looks good especially given that 1 reduces to I.

Btw, I see that you have lots of commits in your branch, feel free to group them and send PRs (rebased on the current master). I should be doing a 1.0 release soon (lci deserves it :smile: )

HalosGhost commented 3 years ago

I appreciate the invitation! I did a lot of strange things (e.g., I changed the list encoding to use foldr-encoded lists rather than pairwise lists, and updated the pretty-printer somewhat accordingly).

So, I'm not sure how much of what I did would actually mesh well with your vision for what lci should be. If you'd ever like to have a call or an email thread talking about what you'd like to see lci become (or, indeed a separate GH issue thread as a meta discussion if you'd prefer), I'd very much enjoy that; and that would help me figure out what might make sense to clean up and PR.