3 ms·

Why only go that far? You can have types for One, Two, Three … Inf and then define division of type Four by type Two as type Two and so on. This would eliminate

Why only go that far? You can have types for One, Two, Three … Inf and then define division of type Four by type Two as type Two and so on. This would eliminate the need to actually run your program since your type checker would be Turing complete and all code would run in Zero time.

timhh 3y ago
That's completely feasible and there are languages that do this. It doesn't really eliminate the need to run your program unless the inputs to your program are also completely restricted types like One, Two, Three. In which case yeah, you don't need to run it and the type system can just tell you the answer. I believe you can do that sort of thing in loads of type systems, e.g. Typescript, but there are languages that intentionally support it. I use a niche DSL that has fancy types like this called Sail. https://github.com/rems-project/sail https://github.com/rems-project/sail In my experience the downsides of these fancy "first class type systems" are 1. More incomprehensible error messages. 2. The type checker moves from a deterministic process that either succeeds or fails in an understandable way, to SMT solvers which can just say "yep it's ok" or "nope, couldn't prove it", semi-randomly, and there's little you can do about it. Still my experience of Sail is that it's very comfortable to go a little bit further into SMT land, and my experience of Dafny is that it's very unpleasant to go full formal-verification at the moment. I've done a fair bit of hardware formal verification too and that's a different story - very easy and very powerful. I'm hoping one day that software formal verification is like that.
zokier 3y ago
> You can have types for One, Two, Three … Inf and then define division of type Four by type Two as type Two and so on That's not far from TypeScripts type system
dunham 3y ago
That's essentially what dependent typed languages do. But the stuff that happens at type checking level has to be known to terminate, so it isn't Turing complete. Without this restriction, it is possible to prove false things to the compiler by writing code that never returns.

timhh 3y ago

That's completely feasible and there are languages that do this. It doesn't really eliminate the need to run your program unless the inputs to your program are also completely restricted types like One, Two, Three. In which case yeah, you don't need to run it and the type system can just tell you the answer. I believe you can do that sort of thing in loads of type systems, e.g. Typescript, but there are languages that intentionally support it. I use a niche DSL that has fancy types like this called Sail. https://github.com/rems-project/sail https://github.com/rems-project/sail In my experience the downsides of these fancy "first class type systems" are 1. More incomprehensible error messages. 2. The type checker moves from a deterministic process that either succeeds or fails in an understandable way, to SMT solvers which can just say "yep it's ok" or "nope, couldn't prove it", semi-randomly, and there's little you can do about it. Still my experience of Sail is that it's very comfortable to go a little bit further into SMT land, and my experience of Dafny is that it's very unpleasant to go full formal-verification at the moment. I've done a fair bit of hardware formal verification too and that's a different story - very easy and very powerful. I'm hoping one day that software formal verification is like that.

zokier 3y ago

> You can have types for One, Two, Three … Inf and then define division of type Four by type Two as type Two and so on That's not far from TypeScripts type system

dunham 3y ago

That's essentially what dependent typed languages do. But the stuff that happens at type checking level has to be known to terminate, so it isn't Turing complete. Without this restriction, it is possible to prove false things to the compiler by writing code that never returns.