halting-problem

    1.1.0 • Public • Published

    halting-problem

    Solves the halting problem :)

    Not really, sadly that's impossible. What this program does aim to do is pick up on some really simple examples of while loops and for loops that never terminate. It's extremely limited and written with the aim of only ever picking up programs that definitely never halt.

    Build Status Dependency Status NPM version

    Installation

    npm install halting-problem
    

    Usage

    var halts = require('halting-problem');
    try {
      halts('while (true);');
      console.log('It halts!');
    } catch (ex) {
      console.log('oops, this program never halts');
    }

    You can also catch any addtional errors by using halts.loopProtect.

    var halts = require('halting-problem');
    try {
      var src = halts.loopProtect('function foo() { return true; } while (foo());');
      Function('haltingProblem', src)(halts);
      console.log('It halts!');
    } catch (ex) {
      console.log('oops, this program never halts');
    }

    API

    halts(src)

    Assert that some code might halt. This will catch some really obvious errors where a while loop never exits. It throws an error if src is some JavaScript with an obvious infinite loop.

    halts.loopProtect(src, protectFn)

    Adds calls to protectFn (which defaults to haltingProblem.protect) inside any places where an infinite loop might occur.

    halts.protect(lineNumber)

    Throws an error if more than 1 second (or the specified timeout) has elapsed since the last time halts.reset was called.

    halts.reset(timeout)

    Resets the timeout (which defaults to 1 second).

    Examples

    This example halts:

    var n = 10;
    while (> 0) {
      n--;
    }

    In this example, the user accidentally typed m instead of n, so this does not halt:

    var n = 10;
     
    while (> 0) {
      m--;
    }

    Assumptions

    Erring on the side of safety, this assumes that any function call results in any loops exiting. For example, they could throw an error.

    Erring on the side of pragmatism, this assumes that there is no dead-code. e.g. it incorrectly states that the following code does not terminate:

    if (false) {
      while (true) {}
    }

    Erring on the side of pragmatism, this assumes that no exceptions are thrown other than explicit throw statements.

    Throwing an error is treated as an acceptable way out of an infinite loop, even if there is no catch block to handle it.

    Contributing

    If you find any program that does eventually halt, but that this library throws an error for (but that doesn't break any of the assumptions) submit a pull request to add the script to /test/halting and I will do my best to fix it.

    There are crazy numbers of programs that don't halt, but that this program won't catch. Please do not submit an issue for such programs. Also do not submit pull requests that just add a test case for such a program. Please do add code to detect such cases though. I'd love this to catch a more significant number of non-trivial cases where JavaScript will go into an infinite loop.

    License

    MIT

    Keywords

    none

    Install

    npm i halting-problem

    DownloadsWeekly Downloads

    11

    Version

    1.1.0

    License

    MIT

    Unpacked Size

    16.9 kB

    Total Files

    29

    Last publish

    Collaborators

    • forbeslindesay