ericelliott / ericelliott/rtype
predicate literals lead to undecidable problem in static analysis
- Dominant language
- JavaScript
- Stars
- 1.1k
- Forks
- 38
- PR merge metrics
- No merged PRs in 30d
Description
[predicates](https://github.com/ericelliott/rtype#the-predicate-type) may be used in an interface
``` TS
interface Integer (number) => number === parseInt(number, 10);
```
They introduce [dependent types](https://en.wikipedia.org/wiki/Dependent_type):
> a dependent type is a type whose definition depends on a value
> [...]
> Dependent types add complexity to a type system. Deciding the equality of dependent types in a program may require computations. If arbitrary values are allowed in dependent types, then deciding type equality may involve deciding whether two arbitrary programs produce the same result; hence [type checking](https://en.wikipedia.org/wiki/Type_checking) may become [undecidable](https://en.wikipedia.org/wiki/Undecidable_problem).
Furthermore, `Integer` is rather a type than a characteristic of a value. What is the type of the result `c` in
```
var c = a + b; // a: Integer, b: Integer
```
Catchy question! You get an error. `+` is not defined for `Integer` and we do not know that `Integer` is a `Number`. We need to add the type `Number` to the parameter of the predicate to provide this information:
``` TS
interface Integer (number: Number) => number === parseInt(number, 10);
```
What is the type of `c` now? Since `+` is not defined for `Integer` but for `Number`, `c` is of type `Number`. If we like to pass `c` to a function that takes an `Integer` we have to do a manually type check before. Otherwise, we cann't do static type analysis in a safe way.
Contributor guide
No contributing guide indexed for this repository
Research direction
The issue names no files, tests, or entry points. First locate the implementation of predicate types and static analysis, then determine how predicate literals and inherited Number information should be handled; completion requires an agreed design that makes the resulting type behavior and safety rules explicit.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- javascript
- Domain
- compilers
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 18/100