Re:MIT develops new tool that can interrupt infinite loops
by carbonica on Tuesday August 02, 2011 @09:49PM
(#2839503)
My undergraduate thesis tackled static analysis in Ruby. One of the problems I attacked was "does a given method yield to its block?" I broke methods into a few classes, two of which are "Block-Required" and "Block-Optional."
I had to write software which proved a method optionally yielded, which isn't just undecidable, but unrecognizable. For non-CS folks, that means it's actually harder than the halting problem. Yet my software works on nearly all Ruby code I throw at it - it only really has difficulty on complex delegation patterns. Unsurprisingly, the code people write to create Block-Optional methods is highly structured.
I had to write software which proved a method optionally yielded, which isn't just undecidable, but unrecognizable. For non-CS folks, that means it's actually harder than the halting problem. Yet my software works on nearly all Ruby code I throw at it - it only really has difficulty on complex delegation patterns. Unsurprisingly, the code people write to create Block-Optional methods is highly structured.