automerge VS egg

I'm not aware of any usable CRDT implementations for Dart, my plan is to use the flutter_rust_bridge to make use of automerge v2, which is a full CRDT implementation written in Rust that has the advantage of having a very simple API to work with (basically a key/value store).

Yes. I asked the devs about ideas for this in this ticket and got an interesting response. It's aimed towards server-side handling, but the same ideas apply to local storage as well.

There are a lot of implementations of CRDTs out there. In JavaScript, for instance, we have Y.js (https://github.com/yjs/yjs) and automerge (https://github.com/automerge/automerge). There’s also a Y.js demo (https://demos.yjs.dev/prosemirror/prosemirror.html) that allows you to play around with them and have your own collaborative app running in just a few seconds. All messages are exchange via webRTC and manages the state via CRDTs. This can be a great sandbox to understand how CRDTs work and see.

Anyone unsure of what a CRDT is, this is the perfect intro: https://www.inkandswitch.com/peritext/

The two most widely used CRDT implementations (combining JSON like general purpose types and rich text editing types) are:

- Automerge https://github.com/automerge/automerge

- Yjs https://github.com/yjs/yjs

For instance, practicing "local first web" using automerge with all it's Distributed Persistence Primitives on CRDT's and Vector Clocks - i.e. when the Browser View is treated like a Database replica, essentially; or adopting a real data mapper that's giving you an API from your database Schema, using Prisma or Hasura... or even implementing a custom codegenereted one, as a babel plugin, on top of TSED and Micro-ORM.

Maybe program optimization?

https://egraphs-good.github.io/

For semantic analyzers, check out egg and egglog. They're custom data structures for representing compiler rewrite rules in a non-destructive way.

E-graphs are pretty awesome, and worth keeping in your back pocket. They're like union-find structures, except they also maintain congruence relations (i.e. if `x` and `y` are in the same set, then `f(x)` and `f(y)` must likewise be in the same set).

https://egraphs-good.github.io/

(Incidentally, union-find structures are also great to know about. But they're not exactly "new".)

I would add that Equality saturation/E-graphs has become quite a hot topic recently, since their POPL21 paper, with workshops dedicated to applications of e-graphs. They have even recently been added to Cranelift as an IR for optimizations.

Egraphs solve the rewrite ordering problem quite nicely. https://egraphs-good.github.io/

Note that one solution to this problem is to use equality saturation (which, coincidentally, has a great implementation in rust!).

Have you thought about trying to parallelize e-graphs? This way you can do a bunch of rewrite rules in parallel and then extract your desired graph at the end instead of having conflicts.

I think the equality saturation papers are a good start. A good start is egg. They have a presentation, a research paper and code you can play with. I think ultimately you want to translate arithmetic operations into logical operation that can be understood by the fpga. So I think it would be good to research how adders and multipliers are implemented in logic and ultimately include equalities between adders/multipliers with their logical counterpart. Note the this translation also depends on the representations of your numbers and their bit width.

For rewriting, you may also find interesing equality saturation: https://egraphs-good.github.io/