Metatheory.jl is a general purpose metaprogramming and algebraic computation library for the Julia programming language, designed to take advantage of the powerful reflection capabilities to bridge the gap between symbolic mathematics, abstract interpretation, equational reasoning, optimization, composable compiler transforms, and advanced homoiconic pattern matching features. The core feature of Metatheory.jl is e-graph rewriting, a fresh approach to term rewriting achieved through an equality saturation algorithm.
Intuitively, Metatheory.jl transforms Julia expressions in other Julia expressions and can achieve such at both compile and run time. This allows Metatheory.jl users to perform customized and composable compiler optimization specifically tailored to single, arbitrary Julia packages. Our library provides a simple, algebraically composable interface to help scientists in implementing and reasoning about semantics and all kinds of formal systems, by defining concise rewriting rules in pure, syntactically valid Julia on a high level of abstraction. Our implementation of equality saturation on e-graphs is based on the excellent, state-of-the-art technique implemented in the egg library, reimplemented in pure Julia.
- The Metatheory.jl introductory paper gives a brief high level overview on the library and its functionalities.
- The Julia Manual metaprogramming section is fundamental to understand what homoiconic expression manipulation is and how it happens in Julia.
- An introductory blog post on SIGPLAN about
eggand e-graphs rewriting. - egg: Fast and Extensible Equality Saturation contains the definition of E-Graphs on which Metatheory.jl's equality saturation rewriting backend is based. This is a strongly recommended reading.
If you'd like to give us a hand and contribute to this repository you can:
- Find a high level description of the project architecture in ARCHITECTURE.md
- Read the contribution guidelines in CONTRIBUTING.md
If you enjoy Metatheory.jl and would like to help, please also consider a tiny donation. It can help me a lot in actively developing this project.
Please note that Metatheory.jl is in an experimental alpha stage and many things are going to change
You can install the stable version:
julia> using Pkg; Pkg.add("Metatheory")Or you can install the developer version (recommended by now for latest bugfixes)
julia> using Pkg; Pkg.add(url="https://github.com/0x0f0f0f/Metatheory.jl")Since Metatheory.jl relies on RuntimeGeneratedFunctions.jl, you have to call @metatheory_init in the module where you are going to use Metatheory.
using Metatheory
using Metatheory.EGraphs
@metatheory_initNarrative and API documentation for Metatheory.jl is available here
If you use Metatheory.jl in your research, please cite our works.