4 ms·

> It seems there is a fundamental difference: zero-ness is a value property while number-ness is a type property The distinction is up to the programming langu

> It seems there is a fundamental difference: zero-ness is a value property while number-ness is a type property The distinction is up to the programming language designer to define. You absolutely could define types such that divide-by-zero is caught as a type error. You'd need a Zero type and a NonZeroNumber type, and have Number be the superset of them. Then define division over Number / NonZeroNumber.

librasteve 3y ago
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.
obastani 3y ago
This breaks down because it's not easy to statically reason about when a variable is a NonZeroNumber. For example, what is the type signature for subtraction of two NonZeroNumbers? You can't guarantee that it isn't zero, so it has to be a Number. Thus, you can't divide by the difference. You could use a more powerful type system to reason about these kinds of constraints, but then type checking quickly becomes undecidable (or at least very, very expensive).
- naasking 3y ago
  > For example, what is the type signature for subtraction of two NonZeroNumbers? You can't guarantee that it isn't zero, so it has to be a Number. You can encode this failure as well, so at least the possibility becomes explicit: NonZero -> NonZero -> Either NonZero Number Oleg also showed you can make an even safer statically checked version with pretty standard type theory and modules: https://okmij.org/ftp/Computation/lightweight-guarantees/lightweight-static-capabilities.pdf https://okmij.org/ftp/Computation/lightweight-guarantees/lig...
- vidarh 3y ago
  a = b - c if a != 0 then x = y / a Here you can infer that the type of 'a' inside the 'then' is a NonZeroNumber. "All" you need is for the type checker to be able to recognize when a conditional acts as a guard against a subset of the possible types.
  - tromp 3y ago
    But if we're dividing by (a-1) then recognizing that it's safe may require a type NonOneNumber. And in other cases perhaps NonFortyTwoNumber. Where does that end?
    - vidarh 3y ago
      Only in as much as it would require the type checker to be able to express and operate on expressions constraining or combining types, not name every one. E.g. being able to recognise that in this: if a < 2 then exit .. afterward, "a" has a named numeric type fully covered by its previous type combined with the extra constraints of the check if that allows picking a more constrained type, and its real type is further constrained to the subset a>=2, and be able to reconcile that this means 'a' can't be 1. In practice, yes, you can absolutely get into situations where this will mean you end up writing extra checks to prove to the compiler that a value can only be within the required subset if the type checker couldn't figure it out. How often will depend on how advanced your type checker is.
pona-a 3y ago
But what if we use predicate-based typing? Then your "type" will be something like `(x) ↦ (0 < x < ∞)`, holding true only if the value matches it. Then, given the type function is pure, the hypothetical compiler may somehow optimize them out most of the production code that can be statically analyzed...

librasteve 3y ago

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.

obastani 3y ago

This breaks down because it's not easy to statically reason about when a variable is a NonZeroNumber. For example, what is the type signature for subtraction of two NonZeroNumbers? You can't guarantee that it isn't zero, so it has to be a Number. Thus, you can't divide by the difference. You could use a more powerful type system to reason about these kinds of constraints, but then type checking quickly becomes undecidable (or at least very, very expensive).

naasking 3y ago
> For example, what is the type signature for subtraction of two NonZeroNumbers? You can't guarantee that it isn't zero, so it has to be a Number. You can encode this failure as well, so at least the possibility becomes explicit: NonZero -> NonZero -> Either NonZero Number Oleg also showed you can make an even safer statically checked version with pretty standard type theory and modules: https://okmij.org/ftp/Computation/lightweight-guarantees/lightweight-static-capabilities.pdf https://okmij.org/ftp/Computation/lightweight-guarantees/lig...
vidarh 3y ago
a = b - c if a != 0 then x = y / a Here you can infer that the type of 'a' inside the 'then' is a NonZeroNumber. "All" you need is for the type checker to be able to recognize when a conditional acts as a guard against a subset of the possible types.
- tromp 3y ago
  But if we're dividing by (a-1) then recognizing that it's safe may require a type NonOneNumber. And in other cases perhaps NonFortyTwoNumber. Where does that end?
  - vidarh 3y ago
    Only in as much as it would require the type checker to be able to express and operate on expressions constraining or combining types, not name every one. E.g. being able to recognise that in this: if a < 2 then exit .. afterward, "a" has a named numeric type fully covered by its previous type combined with the extra constraints of the check if that allows picking a more constrained type, and its real type is further constrained to the subset a>=2, and be able to reconcile that this means 'a' can't be 1. In practice, yes, you can absolutely get into situations where this will mean you end up writing extra checks to prove to the compiler that a value can only be within the required subset if the type checker couldn't figure it out. How often will depend on how advanced your type checker is.

pona-a 3y ago

But what if we use predicate-based typing? Then your "type" will be something like `(x) ↦ (0 < x < ∞)`, holding true only if the value matches it. Then, given the type function is pure, the hypothetical compiler may somehow optimize them out most of the production code that can be statically analyzed...