fully-homomorphic-encryption VS egg

Secure computing. This includes Fully Homomorphic Encryption AKA FHE, of which there is a language/compiler which just got released and Google's older FHE compiler. FHE is probably more "compiler" than "type system", e.g. Google's compiler works on C++. Also Security Type Systems which include Oblivious data structures and Oblivious ADTs.

I don't have any advice for you, but I do work on homomorphic encryption at Google and we have an FHE compiler project [1] (though it is likely going to change a lot in the coming year). I happen to have a math PhD, so the transition to this field was not a huge stretch, but before that I worked in supply chain optimization for data centers, and just decided this was too exciting to pass up.

[1]: https://github.com/google/fully-homomorphic-encryption/issue...

+1, and some compilers already exist to do that for you. See, e.g., Google's compiler (which I work on). https://github.com/google/fully-homomorphic-encryption

Once the tools are written, you should be able to take a program written in some language foo and transpile it to a FHE version of foo. See Google's C++ to FHE-C++ transpiler. Thus, you can test/debug your application without FHE before transpiling to something that is FHE.

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/