search

giovinazzo-kevin / Ergo

Other
4 stars 0 forks source link

Warren Abstract Machine #11

Closed giovinazzo-kevin closed 9 months ago

giovinazzo-kevin commented 2 years ago

While Ergo is expressed rather idiomatically in C#, it would be beneficial to study the WAM and to figure out what sorts of optimizations are available. This would extend to the task of compiling Ergo to IL.

giovinazzo-kevin commented 1 year ago

See #30 for musings.

giovinazzo-kevin commented 11 months ago

Now I'm in a position to say that there's probably no need to implement a full WAM in C#. In fact it would be counter-productive.

The sane approach here is to compile Ergo queries by emitting IL that is structured around the same execution model as the interpreter, but optimized to do as little redundant work as possible, leveraging the benefits of static analysis and implementing a stack-based algorithm instead of the mutually recursive one used by the interpreter. The result would be a callable that can be parametrized, much like SQL queries, and that yields solutions.

This would make it possible to compile hooks, which is what Fiero hinges upon if I want performant scripts.

giovinazzo-kevin commented 10 months ago

A proof of concept compiler has been implemented. It creates an execution graph that can be optimized. It is much more efficient than the interpreted case, but it's still somewhat higher-level than proper virtual machine.

giovinazzo-kevin commented 10 months ago

And now proper IL is being emitted, though only the simplest cases work so far.

The new execution mode is effectively based on a stack machine, similar to the WAM but much higher-level as expected. For example, the term types are the same that the interpreter uses -- but they do support IL emission so that, in the future, a more optimized representation can be used instead. Abstract terms can emit their own IL, and if they don't they will revert to their base class in the compiled code. If the base class is AbstractTerm, they will revert to being their canonical form. This is mostly fine but obviously removes any custom unification logic, unless IL emission is implemented to properly serialize the abstract term.

BuiltIns are now able to generate their own IL, and if they don't, they are called dynamically preserving the old behavior. Goals that prove tough to compile can still be handled by the solver in interpreted mode, similar to built-ins that don't emit IL.

There are some issues related to #74, and all future compiler/related work will be discussed there, so this issue has officially become stale.

giovinazzo-kevin commented 9 months ago

At the end of the day IL emission was not necessary. The new ErgoVM runs on delegates, which makes sense since those are already fairly optimized.