[Python-Dev] Is core dump always a bug? Advice requested

Michel Pelletier michel at dialnetwork.com
Wed May 12 16:31:43 EDT 2004


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




More information about the Python-Dev mailing list