#dependent types

[rictic]

I haven’t been paying attention to the functional programming world for the past few years, but it turns out there’s fun new stuff! Dependent typing seems like it’s actually becoming (become?) useful and not just for type theorists! I’ve been spending this weekend checking out Idris, going through the Idris book. I recommend both.

It’s the first time since I first checked out Rust that I’ve been this excited about a programming language. Idris doesn’t strike me as super practical at this point, but the pieces seem to hang together very well, and there’s lots of good work for other languages to build on.

If you feel pretty comfortable with Haskell and are looking for something like it but that fixes its main mistakes (e.g. strict by default) and with a type system with a bunch of fun new stuff on top, Idris is for you!

My head is very fuzzy from hacking on this all weekend, may write up more later. This book is actually making me feel a little dizzy.

[traversal]

Edwin Brady: Type-driven Development in Idris

[csquotes-blog]

I have emphasised that a meta system allowing non-canonical objects to be treated as indirect proof notations for a represented object system [aka tactics] must have total functions, and be expressive enough to specify which judgement a `thm` object proves.

Robert Pollack, On extensibility of proof checkers

[traversal]

[traversal]

[traversal]

[ezyang]

Compiling dependently typed languages to System FC

One of the most annoying things about creating a new programming language is generating code for it. Optimizations take a long time to develop, so it takes a long time before a compiler which does code generation from scratch to catch up to a highly optimizing compiler like GHC's.

When your language is sufficiently similar to that of an existing one, you can often compile into their intermediate representation, and let their optimization passes take care of things from there. A number of language do this with GHC Core, compiling their code into Core and then letting the optimizer take care of things from there.

However, how do you go about implementing this transformation when your language has a more expressive type system than System F with coercions? The trouble arises when you have types which you know are equal, but cannot express the evidence of equality in the coercion language.

Traditional extraction to Haskell/ML from dependently typed languages often makes use of unsafeCoerce/Object.magic to manage these cases, but too much use of these impedes optimization. Another possibility is to generate additional axioms to represent coercions that would otherwise not be safe.

Anecdotally, integrating with the type system of the target language can be quite important. Edwin tried targeting Idris to GHC core a while ago (five years?) and he either had segfaults (because the optimizer was assuming invariants about his code which didn't hold) or he completely defeated the optimizer (because he made all of his objects opaque and thus with no type information.)