Draft: [#750] Untyped optimizer prototype

Description

This is an early prototype for an untyped optimizer. The primary reason for this MR is to facilitate discussion.

Some design decisions:

• Keeping the typed rules turned out to be somewhat complicated and/or computationally expensive, so all rules are converted to untyped
• For now, testing individual rules is done with doctests. This is suboptimal for a few reasons, the primary being, there's no guarantee the tests are testing what they're supposed to. At this point, I'm considering whether we could rethink how we're specifying substitution rules in the first place. Namely, perhaps it would be easier to define substitutions using raw Michelson syntax inside quasi-quotes or something like that, which could at least in part be automatically checked for correctness. The issue is, we need some pattern matching capabilities, so we'd need to introduce some named holes into the AST for this to work. #283 and #649 seem relevant here.
• The main rule application algorithm may need a bit of work. It always arrives at a fixpoint, but I didn't do any complexity analysis or optimization. Also, the current implementation favours brevity over robustness, so it uses catchall pattern matches, which in the long run is probably a bad idea.

I think if we find a reasonable strategy for checking the rules for sanity at compile-time, or at least to auto-generate tests, it's very much worth it. This comment seems relevant to the discussion.

FWIW, I did also prototype how this affects Indigo, and the update is a bit annoying due to SingI proliferation, but perfectly doable, see indigo@734d0c1b. I might've missed some edge case where we need to pass ParamNotes, but homebase-lite seems to work fine with these changes.

Related issue(s)

Related to #750. This also happens to be related to #300 (closed), #299 (closed), partially #665 (closed), partially #663 (closed).

✅ Checklist for your Merge Request

Related changes (conditional)

• Tests (see short guidelines)

  • If I added new functionality, I added tests covering it.
  • If I fixed a bug, I added a regression test to prevent the bug from silently reappearing again.

• Documentation

  • I checked whether I should update the docs and did so if necessary:
    • Root README and other README.md files
    • Haddock
    • docs/
  • I updated changelog files of all affected packages released to Hackage if my changes are externally visible.

Stylistic guide (mandatory)

• My commits comply with the following policy.
• My code complies with the style guide.