search

egraphs-good / eggcc

MIT License
51 stars 11 forks source link

[tree in context] Function inlining #376

Closed kirstenmg closed 7 months ago

kirstenmg commented 8 months ago

Currently, function inlining passes the provided tests when in_context is not saturated. However, with recursive functions, function inlining blows up too much and causes the in_context to take forever to saturate, so the tests do not terminate even after a minute.

Marking as draft until the timeout is resolved - either by modifying how context propagates, or limiting inlining.

kirstenmg commented 8 months ago

Yes, I will need to replace all (FuncScope) in f-output with (LetScope). This means f-output may contain old InContexts with (FuncScope) args, so function inlining may rely on substitution now to replace these old contexts?

yihozhang commented 8 months ago

Yeah, we need to do something like this.

On Tue, Feb 27, 2024 at 8:24 PM kirstenmg @.***> wrote:

Yes, I will need to replace all (FuncScope) in f-output with (LetScope). This means f-output may contain old InContexts with (FuncScope) args, so function inlining may rely on substitution now to replace these old contexts?

— Reply to this email directly, view it on GitHub https://github.com/egraphs-good/eggcc/pull/376#issuecomment-1968191269, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADEKPFF2CG6K3DV3CRY5HZ3YV2WOPAVCNFSM6AAAAABDUBITWGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTSNRYGE4TCMRWHE . You are receiving this because your review was requested.Message ID: @.***>

oflatt commented 8 months ago

I'll be working on a substitution that can replace arguments that refer to the function scope

oflatt commented 8 months ago

I believe this is now un-blocked by #392

kirstenmg commented 7 months ago

I needed to update the type analysis for it to work for the function inlining tests: In type_analysis.egg, I added a rule for GreaterThan and removed a line from the Call type rule that prevented recursive functions from getting typed (added to HasType). In typechecker.rs, I added a more informative error message for a call to a nonexistent function. This was useful for debugging.

I included these changes in this PR, rather than their own PR, since the function inlining tests serve as tests for these changes.