Armin said: > > Even without these, checking if a bytecode could possibly over/underflowthe > > stack is indeed equivalent to the halting problem; a silly example: > > > > <some algorithm which may stop or not> > > POP_TOP > > > > This underflows the stack if and only if the algorithm stops. Guido said: > The same arguments could > prove that Java's bytecode verification is "impossible", but > nevertheless it's done. But I belive Armin's argument that it equals the halting problem is incorrect. The net stack effect of bytecode can be verified regardless of the algorithm. If it is seen that two bytecodes produce an element on the stack and one bytecode consumes two, then the net effect is zero. As Jeremy pointed out, iterations (of well formed code) have no net effect. Although Armin's example could certainly fail due to exhausting the stack of return frames (which is a runtime issue), or memory, or anything else, no well formed bytecode can exhaust the bytecode stack. The way to know if it's well formed is to verify it using something like a control flow analysis similar to the way the Java ASM bytecode generation API does it. The secondary benefit of this is that you are assured at runtime that the stack size the compiler computes for the bytecode is genuine. -Michel
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4