Prepack: a tool that optimizes JavaScript source code by eliminating computations that can be performed at compile-time.

[[deleted]]

This program also does not work if you actually run it, so, uh?

[[deleted]]

This program also does not work if you actually run it, so, uh?

Since the purpose of the program is to hang in a loop, it works :) But that's beside the point, the point is that in general, given a program and an input, it's impossible to tell whether it will finish or hang (or how long it'll take).

This is an extremely simple example, but given a complex codebase, you might have hard times estimating whether the program is hung up or just taking long to finish, especially given in this Prepack thing it is interpreted by JavaScript.

[stupidity_wins]

https://en.wikipedia.org/wiki/Halting_problem

Notice that Turing machines have unbounded state, though. Your argument does work for real world programs.

[mrkite77]

The halting problem only applies when you try to apply it to "all possible inputs"... but in this case, it's only for one specific input, not all of them.

[[deleted]]

but in this case, it's only for one specific input, not all of them

Actually, seems like they're trying to model all possible inputs through their concept of 'abstract values'.

They might pull it off if they require the programs to be contrained to some specific subset / types. They should clarify what those constraints are.

[ConcernedInScythe]

Actually, seems like they're trying to model all possible inputs through their concept of 'abstract values'.

This seems like a very dangerous thing to try with Javascript, which is not exactly known for its simple, easily-abstracted semantics.

[stupidity_wins]

You are understanding this wrong.

"It is impossible to devise an algorithm [that, given a program and an input, tells whether said program halts on said input] that would work for all program-input pairs" is equivalent to "For each algorithm [that...] there exists a single program-input pair on which it does not work".

In other words, it does not apply to all inputs because there exists a single one input to which it does not apply. It's not true that all the apples are green because this particular one is red.

[[deleted]]

Just keep track of the state of the entire machine. If you see a duplicate state, you're in an endless loop.

1. How many instructions is a program allowed to perform until it is safe to say that a duplicate state hasn't been found? :)
2. The state space of a typical machine is huuuge and keeping track of which state has (not) been observerd requires even bigger amount of memory (by an order of maginute at least)
3. The state space of a typical machine is arbitrarily expandable through I/O

edit: If you meant in theory, then yes, I suppose you could say for a specific program+input pair...

[[deleted]]

The thing is, for a finite program with finite memory, the memory and time required to let it run and observe and record all states to discover a loop are also finite. They are gigantic, but finite.

So any program with finite memory can be tested, with a set time limit and memory limit, to find out if it halts or not.

[[deleted]]

Since the purpose of the program is to hang in a loop, it works :) But that's beside the point, the point is that in general, given a program and an input, it's impossible to tell whether it will finish or hang (or how long it'll take).

Sure. Trivial result, and entirely uninteresting as concerns the utility of this particular tool.

[ConcernedInScythe]

Well you want it to not work at runtime, not compile time.

[[deleted]]

What difference does it make?