peridot VS elaboration-zoo

I've mostly finished up a preprint of a research paper on Peridot, my programming language! It still needs some work, but I'm happy enough with it to post it. If you have any questions or suggestions don't hesitate to tell me here. I would love feedback :-)

I'm finishing up with Peridot! The research goals of the project are close to being accomplished, so I'll be wrapping up soon. I'm really satisfied with it as a proof-of-concept for the ideas it implements. The last main bit of the project is a research paper I'm writing which details the language and its applications in detail.

Hey all! I've been working on my programming language Peridot for about six months, and it's finally at the point where I can call it an MVP! Peridot is a language in which the compiler backend is implemented in userspace via metaprogramming.

The Peridot MVP is feature-complete! All that's left to do are bugfixes, after which it will be a real, usable language. Here's the major features, in no particular order:

I'm not aware of any current implementations, but I'll be implementing it in my language, Peridot. Unfortunately that won't be for a few months though.

The second was called Konna. AFAIK it’s Finnish for “frog”, but sources seem to disagree? I don’t speak Finnish, I got the word from a Finnish video game. My third and current language is called Peridot. I’m pretty proud of this name, although it’s less searchable than the previous ones. The origin is pretty simple, I was just looking around at gemstones and thought peridot looked neat.

Hey! I'm Peridot's author. Peridot is a language based on two-level type theory which allows for the compiler backend to be written in userspace. The language is really two languages tied together: a logic language, and a dependently typed functional language. The former is built for metaprogramming - high-level optimizers and compilers can be written that translate the latter language into a target language of choice. An in-depth explanation of the language's rationale can be found here.

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.

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.

If you're interested in dependent types, you might like András Kovács' elaboration zoo, which uses Haskell as the implementation language.

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/

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.

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!

Highly recommend checking the first part of elaboration-zoo to see how all this might be implemented, it clears a lot of things up.

Pattern unification