Skip to content

Add fix to the AST #6577

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
effectfully opened this issue Oct 16, 2024 · 2 comments
Closed

Add fix to the AST #6577

effectfully opened this issue Oct 16, 2024 · 2 comments
Assignees
Labels
AST Evaluation Low priority Doesn't require immediate attention status: triaged

Comments

@effectfully
Copy link
Contributor

Currently we use the Z combinator for singly recursive functions and this for mutually recursive functions, but this is really inefficient. Adding fix to the AST to handle at least singly recursive functions should improve performance substantially. But what about mutual recursion?

  1. Do we add PIR-style letrec that can handle both singly recursive and mutually recursive functions? This would significantly complicate the AST.
  2. Do we just give up on supporting efficient mutual recursion and tell people to encode it using single recursion like this?
  3. Do we add fixBy as an AST node as well? Or, given the above point, do we even need fixBy at all?

I think I personally prefer the second option.

@robpangilinanioi
Copy link

Wait until we garner more numbers.

@effectfully
Copy link
Contributor Author

Implemented in #6793. The numbers are rather disappointing:

Yet, even with such a performance-focused design the results are very underwhelming: nofib isn't detectably faster (do we have other benchmarks that get recompiled every time?). The lists benchmarks are faster by up to 14.5%, which is normally a very welcome improvement, but given that we're adding an entire new AST node (with very non-trivial evaluation rules), is it worth it?

I no longer think this is a good idea to do this and I don't know anyone who does, so I'm closing the PR and this issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
AST Evaluation Low priority Doesn't require immediate attention status: triaged
Projects
None yet
Development

No branches or pull requests

2 participants