3 ms·
In general, what you want to be able to mix types and values are dependent types (see languages such as Coq, Agda, Idris). However, dependent types are way too
by tomp 12y ago
In general, what you want to be able to mix types and values are dependent types (see languages such as Coq, Agda, Idris). However, dependent types are way too powerful, and as such extremely difficult to use.
A light-weight form of dependent types are refined types, which are essentially dependent function types that have contracts on their parameters and return types. As refined types are way more limited than full dependent types (essentially, linear arithmetics, logic, and simple stuff like this), you don't always need to write the proofs manually but can use an automated theorem prover such as Z3.
This is a hot research topic. There are attempts to do type inference for refined types - see [1] and [2]. The Liquid Haskell team is also exploring the issue of dependent types and laziness [3]. Below you mentioned that you want "soft casts" as well - check out [4], which attempts to do just that (implemented in language Sage [5]).
I'm very interested in this topic as well, and have experimented a bit [6]; as it turns out, it's not that hard to implement a basic type-checker for simple refined types. It's also quite powerful - using Z3, even non-linear problems such as rectangular array access (mentioned by a poster below) are solvable, since you can trivially prove its safety using real arithmetics (which is decidable).
The only big disadvantage that I see is the difficulty with dealing with state, but then again, even programmers can't reason about it properly; I mean, if `x` is a mutable object, can you really say `if x.a != 0 then 1 / 0` and be sure that no-one will modify `x.a` in the meantime from another thread? I hope that linear types could help.
[1] http://goto.ucsd.edu/~rjhala/papers/liquid_types.pdf http://goto.ucsd.edu/~rjhala/papers/liquid_types.pdf
[2] https://www.cs.purdue.edu/homes/suresh/papers/vmcai13.pdf https://www.cs.purdue.edu/homes/suresh/papers/vmcai13.pdf
[3] http://goto.ucsd.edu/~nvazou/refinement_types_for_haskell.pdf http://goto.ucsd.edu/~nvazou/refinement_types_for_haskell.pd...
[4] http://www.kennknowles.com/research/knowles-flanagan.toplas.2010.pdf http://www.kennknowles.com/research/knowles-flanagan.toplas....
[5] http://sage.soe.ucsc.edu/sage-tr.pdf http://sage.soe.ucsc.edu/sage-tr.pdf
[6] https://github.com/tomprimozic/type-systems/tree/master/refined_types https://github.com/tomprimozic/type-systems/tree/master/refi...
- ufo 12y ago> A light-weight form of dependent types are refined types, which are essentially dependent function types that have contracts on their parameters and return types I had never seen it written that way. What can full dependent types do that you can't do with refinement types?
- tomp 12y agoI'm not sure, as I'm not really knowledgeable in programming with full dependent types (as in Agda, Idris, or Coq). However, I can point you to this discussion on Reddit [1]; essentially, one user (kamatsu) is saying that refinement types are not dependent types: > More or less, if you have sigma and/or pi types, then you have dependent types. If you don't, you don't. Also, he claims that a crucial difference is that dependent types are proofs, while type-checking refined types requires proof search. Then, another user (neelk) points out an article [2] which claims (I haven't read it) that dependent types can be encoded using singleton types, which can be written using refined types. [1] http://www.reddit.com/r/programming/comments/26se9k/refined_types_a_better_type_system_for_more/chu013j http://www.reddit.com/r/programming/comments/26se9k/refined_... [2] http://www.iro.umontreal.ca/~monnier/comp-deptypes.pdf http://www.iro.umontreal.ca/~monnier/comp-deptypes.pdf