5 ms·
> that's the only example in the article that seems to imply any kind of compile-time safety The type-checked example is this: var lst : List[Integer] :=
by chriswarbo 8y ago
> that's the only example in the article that seems to imply any kind of compile-time safety
The type-checked example is this:
var lst : List[Integer] := List(Integer).new();
var i : Integer := lst.add(3) + 4;
To me, this isn't so different from something like Java:
List<Integer> lst = new List();
Integer i = lst.add(3) + 4;
The major difference is the extra argument in `List(Integer)` (compared to `List()`). That's kind of unfortunate, but note that it's a value, not an annotation. It's still generic, since we could just as easily pass in some variable (e.g. `T2`) that we've received as an argument, or pulled out of some other method, etc.
This extra argument (a run-time representation of the type) is actually to be expected. Values (including functions) which are generic (in the Java sense), also called "parametrically polymorphic", or as you say "type-dependent types", can be understood as taking those parameters as extra arguments (which is precisely what this article is talking about); although the value itself cannot change its behaviour depending on that argument. For example, `List<T> reverse(List<T> input)` cannot work different for, say, `List<Boolean>` compared to `List<Integer>`.
This is really clear in Haskell. The Glasgow Haskell Compiler uses an intermediate language called "GHC Core", where generic values are literally represented in the same way as functions. There's a nice overview at https://alpmestan.com/posts/2013-06-27-ghc-core-by-example-episode-1.html https://alpmestan.com/posts/2013-06-27-ghc-core-by-example-e... (the "id'" example is the first generic one).
> it does seem like normal generics could be a type-dependent type in a case like this
Generics are definitely type-dependent types. However, when I said "dependent types" I was referring specifically to value-dependent types, e.g. https://en.wikipedia.org/wiki/Dependent_type https://en.wikipedia.org/wiki/Dependent_type
Note in that Wikipedia article's introduction "dependent types are used to encode logic's quantifiers like 'for all'". Compare that to the generic example in that GHC Core link above, where the keyword "forall" gets inserted by the compiler ;)
The Wikipedia article also states "Deciding the equality of dependent types in a program may require computations". That's what I was getting at with the system described in this article: it doesn't seem to allow for type-level computations, without which we may end up getting errors that "expected type X, given type Y" when those types are 'obviously' the same (to us, but not the the checker, since it's not able to compute).
I know Bracha is a fan of 'pluggable type systems', where we can use a variety of type systems to check things about the same program (perhaps requiring different annotations). However, I'm not sure if these 2 rules are enough to perform meaningful reductions on types (e.g. to spot that `Pair(T1, T2).secondType()` is equal to `T2`). I'd imagine we'd have to "lift" more and more expressions into the type level (e.g. `return`, then `if/then/else`, and so on) until we have a full-blown theorem prover like Agda!
- chriswarbo 8y agoReading this back, I'd also suggest a comparison with Hindley-Milner type systems ( https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_sy... ) These type systems are used by ML and its descendents (OCaml, Haskell, Rust, Reason, etc.) and are generally seen as a "sweet spot". They feature: - Types depending on types (AKA type constructors) - Values depending on types (e.g. type classes) - Type-generic values (AKA parametric polymorphism) - Higher-kinded types (AKA higher-order types, or generics at the type-level) - Inference of all types - Erasure of all types Things which Hindley-Milner can't do include: - Inference of values (AKA implicit arguments, as found in Scala and Idris) - Erasure of values - Types which depend on values (AKA dependent types) These things are important for this article, since it represents types as values (which the two given rules let us access from our type annotations). In particular, if we could infer (some) values, we could avoid having to specify arguments like in `List(Integer)`. Going "beyond" Hindley-Milner is a very active area of research. There's a nice talk about this at https://www.reddit.com/r/haskell/comments/390dyx/conor_mcbride_type_inference_needs_revolution/ https://www.reddit.com/r/haskell/comments/390dyx/conor_mcbri... (which i admit is a bit symbol-heavy); full disclosure, I was in the audience for that talk ;)
- Groxx 8y agoThanks for all the info! I definitely do want to learn more about this kind of thing, it's always interesting and I'm always glad for more links :) To circle all the way back around tho, from the intro to the article: >A while back, I discussed the problem of shadow language constructs. I gave examples of shadow constructs such as Standard ML modules, traditional imports etc. Here is another: reified generics. The article seems to be about trying to eliminate shadow types, e.g. meta-type info carried by the compiler but not otherwise visible. By turning generics into type-generator funcs. My question / confusion is around "it seems like you can't type-check that at compile-time without being either so explicit it's no longer generic, or with shadow types, so I don't see how this helps". Or indeed changes anything. Generics as type-generating funcs makes sense, it lets you choose erasure-or-not however you like. Perfectly on board[1]. But how do you type-check it at compile-time without "shadow types"? (if the answer is "read my comments", I'm happy to! I haven't gone through them super carefully yet.) [1]: well... in concept. I'm not sure how libraries would be able to use this in a standard way, seems like it'd lead to multiple competing "generics systems". But that's also useful sometimes. I like languages that let you do that kind of thing, though the ecosystem does not always benefit from it.