ericelliott / ericelliott/rtype

predicate literals lead to undecidable problem in static analysis

Open
#66 17 comments 0 reactions 0 assignees View on GitHub
ready
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.