elaboration-zoo
creusot
elaboration-zoo | creusot | |
---|---|---|
23 | 15 | |
562 | 868 | |
- | - | |
5.3 | 9.6 | |
4 months ago | 2 months ago | |
Haskell | Rust | |
BSD 3-clause "New" or "Revised" License | GNU Lesser General Public License v3.0 only |
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.
elaboration-zoo
- Dependent types do’s and don’ts
-
How to implement dependent type theory I (2012)
I've noticed amongst many peers that when going down the type theory/pl theory journey there is a ton of hidden knowledge and context we all find ourselves collecting.
All of this knowledge and context spread amongst a common set of books, papers, blog posts, and git repos floating around the internet.
At the risk of creating yet another partial silo, I decided earlier this year to create a project similar to the [Elaboration Zoo](https://github.com/AndrasKovacs/elaboration-zoo) but focused on a blessed path to MLTT with a number of the desirable language features via bidirectional typechecking.
https://github.com/solomon-b/lambda-calculus-hs
The project is incomplete and my end goal is a website like the [1 Lab](https://1lab.dev) but focused on Type Theory and PL Theory, but I ran low on steam and could use some collaborators.
-
How to implement dependent types in 80 lines of code
Thanks, yeah, I haven't benchmarked the implementation yet, and I see the repeated substitution happening. Would the NbE approach where we have indices for terms and levels for values fix the issue (I believe you wrote the implementation here)?
I find the NbE approach that combines both indices and levels quite appealing. You remain first-order (easier for debugging and etc.), but no need to define substitution now.
-
Online courses that use, but don't teach, Haskell?
If you're interested in dependent types, you might like András Kovács' elaboration zoo, which uses Haskell as the implementation language.
-
A personal list of Rust grievances
I think it's more a reflection of how Rust evolved, and the techniques and approaches known and understood at the time and the strangeness budget they were (understandably) willing to take on at the time as opposed to something inherent. And also sometimes having separate, complicated features for similar things (as opposed to simple features that compose powerfully) can be useful pedagogically as well.
At any rate, this is something I'm interested in, and so that's why it appears so high up on my list. Often you really do want sub-languages for different purposes, but managing how they interact and work together, what is the same and what is different, and how that impacts usability is interesting (and difficult) part. I feel like it should be possible to do this, but it's going to take some work and there's still lots of unknowns.
In technical terms, I'm interested in dependently typed module systems, multistage programming[1], graded modal type theory[2], elaborator reflection, and two level type theory[3]. These all sound pretty intimidating, but you can actually see glimmers of some of this stuff in how Zig handles type parameters and modules, for example, something that most programmers really like the first time they see it!
I do feel like there is the core of a simple, flexible, powerful systems language out there... but finding it, and making it approachable while maintaining a solid footing in the theory and being sensitive to the practical demands of systems programming is a nontrivial task, and many people will be understandably skeptical that this is even a good direction to pursue. Thankfully the barrier to entry for programming language designers to implementing languages in this style has reduced significantly in just the last number of years[4], so I have hope that we might see some interesting stuff in the coming decade or so. In the meantime we have Rust as well, which is still an excellent language. I'm just one of those people who's never content with the status quo, always wishing we can push the state of the art further. This is why I got excited by Rust in the first place! :)
[1]: https://github.com/metaocaml/metaocaml-bibliography
[2]: https://granule-project.github.io/
[3]: https://github.com/AndrasKovacs/staged
[4]: https://github.com/AndrasKovacs/elaboration-zoo/
-
Reference Implementation for MLF
Another option is this algorithm by Andras Kovacs dubbed "Dynamic order elaboration": https://github.com/AndrasKovacs/elaboration-zoo/tree/master/06-first-class-poly . Basically if you are checking a term against a bare meta variable, then postpone the checking until the meta variable has a solution.
-
purescript-backend-optimizer - A new optimization pipeline and modern-ES backend for PureScript.
Special shout out to /u/AndrasKovacs and elaboration-zoo (as well as their various NbE notes) which served as a primary inspiration for the architecture. Can't thank you enough for those resources!
-
Barebones lambda cube in OCaml
Highly recommend checking the first part of elaboration-zoo to see how all this might be implemented, it clears a lot of things up.
-
Peridot MVP
Pattern unification
creusot
-
Conditioonal Compilation across Crates?
However, it seems that C is not "notified" whether --cfg thing is set, only the main crate being built is. Regardless of this flag, the dummy macro is always chosen. Am I doing something wrong? It should work; the Creusot project is doing something similar.
-
Kani 0.29.0 has been released!
I believe https://github.com/xldenis/creusot is more similar in that it also uses proofs to prove rust code correct.
-
Prop v0.42 released! Don't panic! The answer is... support for dependent types :)
Wow that sounds really cool! I'm not an expert but does that mean that one day you could implement dependend types or refinement types in Rust as a crate ? I currently only know of tools like: Flux Creusot Kani Prusti
-
Linus Torvalds: Rust will go into Linux 6.1
Easy reasoning does not end on memory safety. For example, deductive verification of Rust code is possible exactly because there's no reference aliasing in safe Rust
-
A personal list of Rust grievances
> No support for using something like separation logic within Rust itself to verify that unsafe code upholds the invariants that the safe language expects.
I think this is something we might see in the future. There are a lot of formal methods people who are interested in rust. Creusot in particular is pretty close to doing this - at least for simpler invariants
https://github.com/xldenis/creusot
-
Whiley, a language with statically checked pre and post conditions, releases its 0.6.1 version and portions implemented in Rust
Seems similar in principle to cruesot except as another language instead of as a layer on-top of rust.
-
What it feels like when Rust saves your bacon
You often encounter this entire thread of rhetoric when someone wants to put a diversion into the central argument, yeah but it doesn't ____.
But Rust does do that, match exhaustiveness, forcing the handling of errors and the type system enables things like CreuSAT [1] using creusot [2]
[1] https://news.ycombinator.com/item?id=31780128
[2] https://github.com/xldenis/creusot
> Creusot works by translating Rust code to WhyML, the verification and specification language of Why3. Users can then leverage the full power of Why3 to (semi)-automatically discharge the verification conditions!
Units of Measure, https://github.com/iliekturtles/uom
The base properties of the language enable things that can never be done in C++.
- Creusot: Deductive Verification of Rust
-
What Is Rust's Unsafe?
> I’ve been working on a tool: https://github.com/xldenis/creusot to put this into practice
Note that there are other tools trying to deal with formal statements about Rust code. AIUI, Rust developers are working on forming a proper working group for pursuing these issues. We might get a RFC-standardized way of expressing formal/logical conditions about Rust code, which would be a meaningful first step towards supporting proof-carrying code within Rust.
-
AdaCore and Ferrous Systems Joining Forces to Support Rust
This is exciting! I've met with people from AdaCore and Ferrous systems (individually) several times and they're all serious, competent and motivated.
I'm curious what kinds of software they want to (eventually) verify, my PhD thesis is developing a verification tool for Rust (https://github.com/xldenis/creusot) and I'm always on the look out for case studies to push me forward.
The road to formally verified Rust is still long but in my unbiased opinion looking quite bright, especially compared to other languages like C.
What are some alternatives?
StepULC - Efficient and single-steppable ULC evaluation algorithm
misra-rust - An investigation into what adhering to each MISRA-C rule looks like in Rust. The intention is to decipher how much we "get for free" from the Rust compiler.
pi-forall - A demo implementation of a simple dependently-typed language
l4v - seL4 specification and proofs
tinka
Daikon - Dynamic detection of likely invariants
peridot - A fast functional language based on two level type theory
agda-stdlib - The Agda standard library
higher-order-unification - A small implementation of higher-order unification
hacspec - Please see https://github.com/hacspec/hax
iterator_item - A syntax exploration of eventually stable Rust Iterator items
CreuSAT - CreuSAT - A formally verified SAT solver written in Rust and verified with Creusot.