wffl

vaguely burnt

  • it/its

I do stuff; pfp by spicymochi



prophet
@prophet

I personally believe that the most important property of a type system is that it has a really simple, consistent1 core. If you don't have this, you will accrue accidental complexity over time.

You can see this pretty well in Rust and TypeScript where, as an outsider, a lot of type system discussions are a bit strange to follow because it seems like they're designing themselves into a corner much more than they're arguing about anything fundamental to the problem they're trying to solve.
This isn't a dig at either language, they both have pretty strong constraints that make them rely on very specific features so this is more or less inevitable. But they're also both not exactly known for being simple, are they?

This is actually one of the main reason why I love full spectrum dependent types! Some people think dependent types are complex or difficult but that's just because the ways to approximate them in languages like Haskell or OCaml are quite complex.

Dependent types on their own are actually much simpler than either of those languages!
For example, OCaml's module language sits on top of the regular term language and reinvents a lot of the term level concepts (functors, first class modules, (mutually) recursive modules, etc) with a lot of subtle but significant limitations.
Similarly, Haskell's type language reinvents a lot of what already exists in the term language (open/closed type families, type-level pattern matching, data kinds, etc.) with β€” you guessed it β€” a lot of subtle but significant limitations.

Dependent types make things much simpler because they collapse all of those languages β€” terms, types, kinds and modules β€” into a single one that behaves consistently.

With full spectrum dependent types, "can I do this with a functor/type family" isn't even a question you need to ask because functors and type families are just functions and you should hopefully know what you can do with functions.
If modules are just record-like values that happen to be usually known at compile time, then first-class-modules are just... modules that aren't known at compile time. This isn't even something you would think of as a feature, it's just what naturally falls out of your type system if you remove all the arbitrary restrictions that a separate module language creates!

Even polymorphism itself goes from something relatively opaque (at least to beginners) about how a function "can work for every possible instantiation of a" to a dependent function with an implicit parameter that happens to have type Type. This even largely gives you higher-rank polymorphism for free because a higher-rank function is just a higher order function where the argument happens to take an argument of type Type.

If you want the simplest possible type system, it should probably have dependent types.


  1. consistent in the informal sense that it works nicely without a lot of exceptions, not in the formal sense of "only allows you to construct terms of types that correspond to true propositions"


wffl
@wffl

this reply is a dig at Rust's type system. it sucks.


You must log in to comment.

in reply to @prophet's post:

a couple questions because i must be confused:

  1. I had thought typescript was sort of dependently typed, in that checks + control flow analysis could narrow the type of a variable to specific values. And I thought it had "full" row polymorphism. So what's missing? The ability to create functions that act at a type level?
  2. How do you model Rust lifetimes in a dependently typed language?

This is a little confusing because "dependently typed" is a little broad of a term ^^ Yes, TypeScript has some dependently typed features (in the same way that Haskell does) but neither of them have full-spectrum dependent types (or first-class types if you want) so there is still a pretty strong phase distinction between types and terms and you can't just use terms in types (if you have a literal type like 5 in TS, that's not the value 5, it's a type that is only inhabited by the value 5).

I don't think lifetimes fall out of dependent types in the same way as e.g. modules. You could probably get close if you have some Lifetime type (with static : Liftetime) and use, like, polymorphic continuations (as in borrow : forall a. Something -> ((l : Lifetime) -> a) -> a) like Haskell's runST. But I don't think you could get non-lexical life times that way so you would probably still want a proper second-class lifetime system in practice.

ah makes sense, ty!

the only full-spectrum dependently typed language I know of is Lean 4, which comes with a lot of other interesting features that make the language traditionally hard to get into. Besides (presumably) Polaris, are there any other languages you know of that have a core like this?

idris is really nice at this! mostly because it doesn't try too hard to be a theorem prover and puts more emphasis on practical programming.
there are also coq and agda but those usually aren't exactly meant to be... run ^^

a lot of type system discussions are a bit strange to follow because it seems like they're designing themselves into a corner much more than they're arguing about anything fundamental to the problem they're trying to solve

I can definitely understand this point but I'm becoming more convinced that this is an inevitability when attempting to support all of the features & domains the users of these languages are wanting. Problems could probably be solved with 'let's blow up fundamental assumptions about the type system and make large breaking changes', but many users would find this untenable and it wouldn't get the (economic) support necessary.

An example of this is Niko's dyn* proposal1, which to an outsider looks insane (I am apparently Rust-brained enough to think these ideas are awesome). I think the proposal has been modified in further posts/discussions of his, but iiuc this is exactly what you're getting at: adding archaic syntax to solve a problem that's really 5 problems down the road. Something notable here is that to the insiders this syntax and similar proposals also look insane, it's just that new features and syntax need to mesh well into the millions of existing lines of code and maintainers understand they need to take what they can get in terms of lang design. This leads to a scary conclusion: get your programming language semantics correct/'consistent' the first time or face dire consequences N years later because you didn't account for 'that one feature' (which is quite different from a lot of other kinds of software).

A cool attempt I've seen at building a nice core language for systems dev is Pikelet2 but that has sadly gone dormant. Hopefully the future contains many more dependently typed languages. I think Zig's design space is interesting here - essentially ignoring any type theory and focusing on partial evaluation. A lot of these ideas could be combined into something more cohesive - e.g. a language with partial eval like Zig but with more options for compilation / safety modes like adding linear types, liquid types, etc. Starting from 'the type system is just a turning machine users can use to build whatever' while encoding special behavior in could be a viable path for future-proofing the lang. (On the infinite TODO list is finishing my prototype for something like this... we'll see how far I get I suppose.)

I agree in spirit but in practice I am somewhat traumatised by Agda and https://plfa.github.io. Perhaps that's more because it's more about writing type systems than using Agda's type system to implement something practical? I'm not sure. This comment is basically me saying "yes, but" and maybe I just want someone to give me a dependently typed language that has as good tooling as Go or Rust, great documentation and a vibrant community that uses the language for more than just type system research.