RE: Promises and Decidability in Asynchronous Error Handling

A well-known problem with loops, as implemented in various programming languages, is that infinite loops are silenced by default. Consider the following program, which simply adds some numbers in a loop:

```js
var sum = 0;
while (Math.random() < config.loopLimt) { // Note the misspelling!
  sum += Math.random();
}
```

On line two, the property "loopLimit" is misspelled, which should cause the program to report an infinite loop as the condition will never be true. Under the current programming language paradigm, however, the error will be silenced and the program will loop happily forever.

Various solutions have been proposed for dealing with this problem, such as:

- Extending debugging tools to allow some visibility into the code currently running in your program, through a specialized tab or view.

- Using CPU consumption to determine when a loop has locked up the program, and thus probably consistutes a program error.

- Adding a `safeWhile` construct to the language which ensures you cannot loop more than 64K times.

While each of these approaches provides a partial solution to the problem, they are ultimately inadequate because they do not address the underlying cause.

The root cause of this issue is that, as currently specified, **the problem of deciding whether a particular `while` loop terminates is Turing undecidable**.

This is *not* a desirable property for a looping mechanism to have, and it is not a design choice that can be reversed at a later date.

In order to make loop termination decidable, it is sufficient to require that the loop condition must be become true *within a well-defined window*. One such window would be the current second.

The designers of regular expressions have made a similar decision with their string matching API. A quick search on StackOverflow relating to loops and "infinite" loops in regular expressions yielded no results. This cursory evidence suggests that requiring looping constructs to be finite is not a significant problem for regular expression users.

In my view, it would be a mistake to standardize the undecidable looping model of the current `while` loop design.

---

Which is all to say, being unable to Turing-decide how a programming construct will work is not a particularly noteworthy disqualifier, and indeed opens up extremely powerful features in most cases. I believe the same is true of the current promise design.

Received on Monday, 21 October 2013 19:59:25 UTC