5 ms·

So if I understand correctly, the real point is instead of programming defensively at runtime, you can do it in the type system. My main question is the extent

So if I understand correctly, the real point is instead of programming defensively at runtime, you can do it in the type system. My main question is the extent to which this is possible in more conventional languages.

yummyfajitas 12y ago
Yep - that's probably a fair way to describe it. It's of course possible in other statically typed languages, it's just not as easy. There are also some things that I'm not sure are reasonable at all in something like Java/C++ without writing a lot of code. For example: https://www.chrisstucchio.com/blog/2014/type_safe_vector_addition_with_dependent_types.html https://www.chrisstucchio.com/blog/2014/type_safe_vector_add...
- marmaduke 12y ago
  Thanks for the link. I've been wondering how to lift N-D operations into the type system. If I write with NumPy x = r_[:n].reshape((3, -1, n/15))[:, :2].sum(axis=-1) a compiler could figure out that the shape of x is (3, 2) and allow y = x + randn(m, 1, 2) while forbidding z = y - r_[:7] With NumPy you have to wait for a runtime error, and only if the shapes can't be broadcast. We're not even talking correct use of dimensions, etc. I suppose this may have been tackled in Haskell in the Repa library, but I'd need to read papers like http://benl.ouroborus.net/papers/repa/repa-icfp2010.pdf http://benl.ouroborus.net/papers/repa/repa-icfp2010.pdf to know. Hence my question if we could lift this into the type system in a conventional language, but I don't think it's possible in a general way.
  - thinkpad20 12y ago
    I'm not sure what the notation you're using represents, but it looks like you're talking about matrices of a known size. What that's an example of is dependent types, where types can be parameterized by values, and not just types. For example, a (2D) matrix is parameterized by what it contains, and its dimensions. The former is a type but the latter are values. Without dependent types (or some subset of their capability) you can't represent this matrix type; you'd just have to check at runtime that no out-of-bounds access was occurring, so no; I don't think you could put this in a conventional language (without some crazy gymnastics, perhaps involving macros or similar). However, with dependent types, this is absolutely possible to statically guarantee that no out-of-bounds access will occur at runtime.
- tel 12y ago
  I would say that it's not always possible. It's probably "possible" if you put about half the invariant in the type and half the invariant in documentation, of course, but that's a much weaker claim! Java is in an interesting place in that its type system is rudimentary but not unpowerful. C is a more useful didactic target---there really do exist invariants which can be encoded in Haskell types but could never be encoded in C types! Another huge target is parametricity. You can write Java code which is "maybe sort of parametric" but it really isn't and subsequently you can never trust it because of the existence of things like global reference equality and hash codes (in the least). Finally, there are expressivity concerns. Java cannot encode as many things in its type language as something like Agda (to make a clear comparison). You can simply note that Java's type equality is nowhere nearly as developed as Agda's! As an example of using Java to indicate a fairly non-trivial invariant and comparing that implementation to Scala, Haskell, and C# consider Tony Morris' challenge http://tonymorris.github.io/blog/posts/understanding-practical-api-design-static-typing-and-functional-programming/ http://tonymorris.github.io/blog/posts/understanding-practic...
tel 12y ago
Just imagine that every static constraint you want to encode has to be written in the language of the types, a subset of your chosen language. C's language of types is incredibly primitive. Haskell's is quite nice. Agda/Idris/Coq's type language is technically equivalent to its value language so you can encode incredible things. It turns out that due to people's general desire for compilation to always terminate that the type language behaves quite different from the value language. It also turns out that the type language operates differently because we're more interested in logical constraints than actual evaluation. The major thing that the above change is that you no longer have the "it's always a Turing complete language" excuse. Type languages can actually significantly and meaningfully differ in power. So it's meaningful to say that there are constraints that can be encoded statically in Haskell but cannot in C (no matter how you try). And it's also true that Coq can encode constraints that cannot be encoded in Haskell (though Haskell keeps making its type language stronger!).
- marmaduke 12y ago
  Would you then accept a worthless value language if the type language was perfect? Anyway, this was quite an enlightening comment for me: Agda/Idris/Coq's type language is technically equivalent to its value language. Given a sufficiently interesting type language, could we statically type the problem I posed in another comment here https://news.ycombinator.com/item?id=8966065 https://news.ycombinator.com/item?id=8966065 ?
  - tel 12y ago
    I'm not sure anyone has developed a language with a great type level language and a worthless value level one. But that said, theorem provers (like Coq) essentially consider value-level computation as vestigial: nobody cares about running Coq programs, just checking them. To encode what you're looking for requires type-level natural numbers and a reasonable notion of type-level equality. These are fairly non-trivial. You can encode this in Haskell, but type leve" equality is a bit hard to work with so you may suffer some pains (I know, I've done it several times!). Agfa and Idris would be where I would look to see this sort of thing materialize.
  - 12y ago
jfoutz 12y ago
Another way to think about it is kinda related to pg's stratified design. At the lowest level, you have things like system services, files, sockets, perhaps other processes. Regular old code may use those abstractions - or not - and build new stuff. for example parsers, matrixes, http responses, database connections. Just like regular old code helps you manage the relationships between an input file and an output file, the type system helps you manage the relationship between libraries, or sets of functionality in your code. I don't care what type of data you pull from the database, but that type must agree with the type of matrix you're constructing. The parser may return a syntactically correct tree, or an error. One use of the type system is to ensure that all possible error conditions are handled in a meaningful way. You can do this in java, but haskell's type system is a bit more expressive, so it's easier to enforce higher level constraints. Another way to look at it, the type system is like the algebra axioms you want your system to follow. if equality is reflexive, a == b, then also b == a. At that level we don't care if a is 5 or "hello" or @TcpConnection(0x1342341a).
jerf 12y ago
"My main question is the extent to which this is possible in more conventional languages." It is substantially possible in more conventional languages, however the conventional languages have holes in them which can not be filled in by libraries. For instance, a bog-standard approach in any OO language is to hide the raw constructor and give only mediated access via some other class method (or local equivalent construct). This can allow you to easily enforce constraints like "A CreditCardNumber either had its parity validated OR does not exist". If you then put methods on an object that allow you to only manipulate the object in certain ways that maintain the constraints, there will exist no (direct) way to violate the basic constraints of the object. This is reasonably powerful, and mastery of this technique is something that I would consider to be core to considering yourself at least a mid-tier professional developer. However, there are many constraints you can not enforce in conventional languages. You can not enforce via type whether or not a given call will do IO or access global variables in unexpected manners. You can not enforce via type that a given method will only be called in a certain context (key in things like transactional memory, where you'd better be doing your STM things inside an actual transaction or the whole thing breaks down). You can not enforce whether an object will or will not be shared across thread boundaries. And so on, for a wide variety of additional guarantees that can be provided by a stronger type system. In the exciting-but-experimental world of dependent typing, you can enforce at the type system that a number is even or odd and stuff like that. There are many different additional constraints being explored right now across a wide variety of languages, and while functional languages are leading the way, and there are some solid reasons for that, it isn't just functional languages that can use this... for instance, see Rust, which isn't functional at all in the modern sense but can still guarantee some of the things I said above. (Rust, for instance, bring a question to the fore that I've been interested in for a while, but haven't had a major language to check it with: Is the important thing about functional programming immutability, or is it controlling mutation carefully? If in practice the latter is really what's important, than it is possible to see a set of "immutable" languages and see them successfully control mutation but accidentally attribute that to the "immutability", because that's the mechanism we happened to be using to accomplish the mutation control. I've already previously explained why I believe Erlang definitely had this problem: https://news.ycombinator.com/item?id=7744109 https://news.ycombinator.com/item?id=7744109 but with Rust we can explore whether Haskell has the right of the argument, or if Rust-style mutation control will turn out in practice to be sufficient. But it will be years before we can even start forming a decent answer... Rust needs some large scale programs and a body of people with experience writing large-scale Rust programs before we can even start forming a solid answer.)

yummyfajitas 12y ago

Yep - that's probably a fair way to describe it. It's of course possible in other statically typed languages, it's just not as easy. There are also some things that I'm not sure are reasonable at all in something like Java/C++ without writing a lot of code. For example: https://www.chrisstucchio.com/blog/2014/type_safe_vector_addition_with_dependent_types.html https://www.chrisstucchio.com/blog/2014/type_safe_vector_add...

marmaduke 12y ago
Thanks for the link. I've been wondering how to lift N-D operations into the type system. If I write with NumPy x = r_[:n].reshape((3, -1, n/15))[:, :2].sum(axis=-1) a compiler could figure out that the shape of x is (3, 2) and allow y = x + randn(m, 1, 2) while forbidding z = y - r_[:7] With NumPy you have to wait for a runtime error, and only if the shapes can't be broadcast. We're not even talking correct use of dimensions, etc. I suppose this may have been tackled in Haskell in the Repa library, but I'd need to read papers like http://benl.ouroborus.net/papers/repa/repa-icfp2010.pdf http://benl.ouroborus.net/papers/repa/repa-icfp2010.pdf to know. Hence my question if we could lift this into the type system in a conventional language, but I don't think it's possible in a general way.
- thinkpad20 12y ago
  I'm not sure what the notation you're using represents, but it looks like you're talking about matrices of a known size. What that's an example of is dependent types, where types can be parameterized by values, and not just types. For example, a (2D) matrix is parameterized by what it contains, and its dimensions. The former is a type but the latter are values. Without dependent types (or some subset of their capability) you can't represent this matrix type; you'd just have to check at runtime that no out-of-bounds access was occurring, so no; I don't think you could put this in a conventional language (without some crazy gymnastics, perhaps involving macros or similar). However, with dependent types, this is absolutely possible to statically guarantee that no out-of-bounds access will occur at runtime.
tel 12y ago
I would say that it's not always possible. It's probably "possible" if you put about half the invariant in the type and half the invariant in documentation, of course, but that's a much weaker claim! Java is in an interesting place in that its type system is rudimentary but not unpowerful. C is a more useful didactic target---there really do exist invariants which can be encoded in Haskell types but could never be encoded in C types! Another huge target is parametricity. You can write Java code which is "maybe sort of parametric" but it really isn't and subsequently you can never trust it because of the existence of things like global reference equality and hash codes (in the least). Finally, there are expressivity concerns. Java cannot encode as many things in its type language as something like Agda (to make a clear comparison). You can simply note that Java's type equality is nowhere nearly as developed as Agda's! As an example of using Java to indicate a fairly non-trivial invariant and comparing that implementation to Scala, Haskell, and C# consider Tony Morris' challenge http://tonymorris.github.io/blog/posts/understanding-practical-api-design-static-typing-and-functional-programming/ http://tonymorris.github.io/blog/posts/understanding-practic...

tel 12y ago

Just imagine that every static constraint you want to encode has to be written in the language of the types, a subset of your chosen language. C's language of types is incredibly primitive. Haskell's is quite nice. Agda/Idris/Coq's type language is technically equivalent to its value language so you can encode incredible things. It turns out that due to people's general desire for compilation to always terminate that the type language behaves quite different from the value language. It also turns out that the type language operates differently because we're more interested in logical constraints than actual evaluation. The major thing that the above change is that you no longer have the "it's always a Turing complete language" excuse. Type languages can actually significantly and meaningfully differ in power. So it's meaningful to say that there are constraints that can be encoded statically in Haskell but cannot in C (no matter how you try). And it's also true that Coq can encode constraints that cannot be encoded in Haskell (though Haskell keeps making its type language stronger!).

marmaduke 12y ago
Would you then accept a worthless value language if the type language was perfect? Anyway, this was quite an enlightening comment for me: Agda/Idris/Coq's type language is technically equivalent to its value language. Given a sufficiently interesting type language, could we statically type the problem I posed in another comment here https://news.ycombinator.com/item?id=8966065 https://news.ycombinator.com/item?id=8966065 ?
- tel 12y ago
  I'm not sure anyone has developed a language with a great type level language and a worthless value level one. But that said, theorem provers (like Coq) essentially consider value-level computation as vestigial: nobody cares about running Coq programs, just checking them. To encode what you're looking for requires type-level natural numbers and a reasonable notion of type-level equality. These are fairly non-trivial. You can encode this in Haskell, but type leve" equality is a bit hard to work with so you may suffer some pains (I know, I've done it several times!). Agfa and Idris would be where I would look to see this sort of thing materialize.
- 12y ago

jfoutz 12y ago

Another way to think about it is kinda related to pg's stratified design. At the lowest level, you have things like system services, files, sockets, perhaps other processes. Regular old code may use those abstractions - or not - and build new stuff. for example parsers, matrixes, http responses, database connections. Just like regular old code helps you manage the relationships between an input file and an output file, the type system helps you manage the relationship between libraries, or sets of functionality in your code. I don't care what type of data you pull from the database, but that type must agree with the type of matrix you're constructing. The parser may return a syntactically correct tree, or an error. One use of the type system is to ensure that all possible error conditions are handled in a meaningful way. You can do this in java, but haskell's type system is a bit more expressive, so it's easier to enforce higher level constraints. Another way to look at it, the type system is like the algebra axioms you want your system to follow. if equality is reflexive, a == b, then also b == a. At that level we don't care if a is 5 or "hello" or @TcpConnection(0x1342341a).

jerf 12y ago

"My main question is the extent to which this is possible in more conventional languages." It is substantially possible in more conventional languages, however the conventional languages have holes in them which can not be filled in by libraries. For instance, a bog-standard approach in any OO language is to hide the raw constructor and give only mediated access via some other class method (or local equivalent construct). This can allow you to easily enforce constraints like "A CreditCardNumber either had its parity validated OR does not exist". If you then put methods on an object that allow you to only manipulate the object in certain ways that maintain the constraints, there will exist no (direct) way to violate the basic constraints of the object. This is reasonably powerful, and mastery of this technique is something that I would consider to be core to considering yourself at least a mid-tier professional developer. However, there are many constraints you can not enforce in conventional languages. You can not enforce via type whether or not a given call will do IO or access global variables in unexpected manners. You can not enforce via type that a given method will only be called in a certain context (key in things like transactional memory, where you'd better be doing your STM things inside an actual transaction or the whole thing breaks down). You can not enforce whether an object will or will not be shared across thread boundaries. And so on, for a wide variety of additional guarantees that can be provided by a stronger type system. In the exciting-but-experimental world of dependent typing, you can enforce at the type system that a number is even or odd and stuff like that. There are many different additional constraints being explored right now across a wide variety of languages, and while functional languages are leading the way, and there are some solid reasons for that, it isn't just functional languages that can use this... for instance, see Rust, which isn't functional at all in the modern sense but can still guarantee some of the things I said above. (Rust, for instance, bring a question to the fore that I've been interested in for a while, but haven't had a major language to check it with: Is the important thing about functional programming immutability, or is it controlling mutation carefully? If in practice the latter is really what's important, than it is possible to see a set of "immutable" languages and see them successfully control mutation but accidentally attribute that to the "immutability", because that's the mechanism we happened to be using to accomplish the mutation control. I've already previously explained why I believe Erlang definitely had this problem: https://news.ycombinator.com/item?id=7744109 https://news.ycombinator.com/item?id=7744109 but with Rust we can explore whether Haskell has the right of the argument, or if Rust-style mutation control will turn out in practice to be sufficient. But it will be years before we can even start forming a decent answer... Rust needs some large scale programs and a body of people with experience writing large-scale Rust programs before we can even start forming a solid answer.)