Draft: MIR: initial rough prototype

Context

This is a rough prototype for MIR, primarily intended as a proof of concept, and testing grounds for exploring possible designs. At the time of writing, large parts of Michelson are not implemented, but it can run some basic code.

Some design notes:

• We're using the trees that grow idiom, adapted to Rust, to be able to attach arbitrary metadata to AST nodes at different stages of execution. The primary motivation for this is tzt, which, if we're going to support it, requires being able to specify wildcards as part of the expected output. There are various approaches to that, but TTG allows us to have wildcards as part of the AST if we need to, which seems like the most straightforward approach. Aside from that, it's simply convenient, although admittedly adds some boilerplate. The prototype typechecker and interpreter are not strictly speaking extensible at this stage, mostly due to time constraints, but the intent is to make them so at some point.

• We chose a more functional style for implementing typechecker and interpreter, meaning instructions are represented as a sum type (enum in Rust speak), and both typechecker and interpreter are implemented as functions matching on that. This style ultimately allows for less boilerplate.

• Typechecked values are represented as a sum type with the same variant names as the type representation. This allows for more efficient implementation of storage of typechecked values than if we simply attached types to raw ("untyped") Michelson values instead. The cost is relatively minor code duplication. We did briefly consider dynamic typing via traits, but ultimately decided the added indirection and associated overhead aren't worth it.

• There are some obvious optimization avenues, e.g. recursive types (i.e. pair, option, or, etc) could store properties (i.e. comparability, packability, etc) as metadata to avoid full traversal during typechecking. The implementation is straightforward, but I decided to skip it in this prototype for the time being, mostly for time. A similar optimization is used for typed values wrt comparability as a proof of concept (also there it arguably has more impact)

• There is almost no automatic testing. This wasn't an explicit goal, but the primary reason, at this stage, tests end up being very verbose, and we're somewhat pressed for time. The plan is to eventually make a small macro-based EDSL for tests to make constructing them a bit more pleasant.

Closes #6212 (closed) #6213 (closed)

Depends on !9906 (merged)

Manually testing the MR

You can run code from src/lib_mir/test/fixtures/, although the prototype can't parse tzt files (it wasn't a goal). In order to run those, assuming you have Rust toolchain installed, you can do something like this:

pcregrep -o1 --multiline 'code\s*{((?:\n|.)*?)}\s*;\ninput' ../test/fixtures/factorial.tzt | cargo run nat 30

Checklist

• Document the interface of any function added or modified (see the coding guidelines)
• Document any change to the user interface, including configuration parameters (see node configuration)
• Provide automatic testing (see the testing guide).
• For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, CHANGES.rst at the root of the repository for everything else).
• Select suitable reviewers using the Reviewers field below.
• Select as Assignee the next person who should take action on that MR