egg
Agda
egg | Agda | |
---|---|---|
25 | 27 | |
1,239 | 2,378 | |
2.7% | 0.6% | |
6.8 | 9.8 | |
10 days ago | 7 days ago | |
Rust | Haskell | |
MIT License | MIT License |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
egg
-
An Introduction to Graph Theory
Maybe program optimization?
https://egraphs-good.github.io/
- The E-graph extraction problem is NP-complete
-
What is the state of the art for creating domain-specific languages (DSLs) with Rust?
For semantic analyzers, check out egg and egglog. They're custom data structures for representing compiler rewrite rules in a non-destructive way.
-
Ask HN: What is new in Algorithms / Data Structures these days?
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".)
-
What are the current hot topics in type theory and static analysis?
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.
-
Compiler Optimizations Are Hard Because They Forget
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!).
-
Modularity in IR representation and modification
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.
-
Any recommendations for good resources that show how algorithms and data structures are converted into fpga circuits
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.
-
Strategies for doing symbolic integration algorithmically
For rewriting, you may also find interesing equality saturation: https://egraphs-good.github.io/
Agda
-
Types versus sets (and what about categories?)
This was recently deemed inappropriate:
"Bye bye Set"
"Set and Prop are removed as keywords"
https://github.com/agda/agda/pull/4629
-
If given a list of properties/definitions and relationship between them, could a machine come up with (mostly senseless, but) true implications?
Still, there are many useful tools based on these ideas, used by programmers and mathematicians alike. What you describe sounds rather like Datalog (e.g. Soufflé Datalog), where you supply some rules and an initial fact, and the system repeatedly expands out the set of facts until nothing new can be derived. (This has to be finite, if you want to get anywhere.) In Prolog (e.g. SWI Prolog) you also supply a set of rules and facts, but instead of a fact as your starting point, you give a query containing some unknown variables, and the system tries to find an assignment of the variables that proves the query. And finally there is a rich array of theorem provers and proof assistants such as Agda, Coq, Lean, and Twelf, which can all be used to help check your reasoning or explore new ideas.
-
What can Category Theory do?
Haskell and Agda are probably the most obvious examples. Ocaml too, but it is much older, so its type system is not as categorical. There is also Idris, which is not as well-known but is very cool.
-
What are the current hot topics in type theory and static analysis?
Most of the proof assistants out there: Lean, Coq, Dafny, Isabelle, F*, Idris 2, and Agda. And the main concepts are dependent types, Homotopy Type Theory AKA HoTT, and Category Theory. Warning: HoTT and Category Theory are really dense, you're going to really need to research them.
-
Amendmend proposal: Changed syntax for Or patterns
Does this come with plans to separately unify the body with each of the contexts induced by matching on each of the respective patterns (similar to what’s discussed here), or will it behave like the _ pattern and use only the most general context?
-
Functional Programming and Maths <|> How can a code monkey learn Agda?
That's absolutely untrue. From the horse's mouth:
- Doom emacs and agda-mode
-
FP language idea - would this is possible to infer and type check?
Agda has the so-called mixfix operators (which are powerful enough to cover pre/in/postfix cases with an arbitrary number of arguments), check that out: - https://agda.readthedocs.io/en/v2.6.1/language/mixfix-operators.html - https://github.com/agda/agda/blob/master/examples/Introduction/Operators.agda - https://github.com/agda/agda-stdlib/blob/master/src/Data/Product/Base.agda
-
Best Programming Language for Computational Proof
Coq, Agda, Lean, Isabelle, and probably some others which are not coming to my mind at the moment, but those would be considered the major ones.
-
Do you use Idris or Coq, and why?
Funny that you say this, because there are some obvious long standing open feature requests with looking up the type of the term under cursor — № 4295 and № 516. I am not blaming anyone in particular — this is the way it is. I wish I could find time to rewrite the proof search engine (how hard can it be), but I am already buried under a pile of other commitments and a good chunk of overwhelming sadness.
What are some alternatives?
prose - Microsoft Program Synthesis using Examples SDK is a framework of technologies for the automatic generation of programs from input-output examples. This repo includes samples and sample data for the Microsoft Program Synthesis using Example SDK.
lean - Lean Theorem Prover
Symbolics.jl - Symbolic programming for the next generation of numerical software
coq - Coq is a formal proof management system. It provides a formal language to write mathematical definitions, executable algorithms and theorems together with an environment for semi-interactive development of machine-checked proofs.
Catlab.jl - A framework for applied category theory in the Julia language
open-typerep - Open type representations and dynamic types
Dagger.jl - A framework for out-of-core and parallel execution
HoleyMonoid - Automatically exported from code.google.com/p/monoid-cont
glow - Compiler for Neural Network hardware accelerators
distributive - Dual Traversable
StaticArrays.jl - Statically sized arrays for Julia
lean4 - Lean 4 programming language and theorem prover