IMO one of the most valuable things I've learned about static analysis is that the halting problem is overly pessimistic. It's easy to prove very interesting things about real-world code.

Things like dead-code removal are a pretty standard for modern optimizing compilers!

They didn't say dead code analysis was decidable, but purity analysis.

Purity analysis is indeed trivially decidable, if you limit yourself to "probably always pure", not "pure when executed on a Tuesday". It boils down to "is this function calling only pure functions and not using any of the impure operators?". The trouble comes with dynamic languages where you usually don't know shit about a function's arguments, though. In that case you need a control flow Analysis of the whole program.

I think this was meant to have read as "provably always pure", not "probably always pure."

effing spell checkers ...

Almost everything is undecidable. Yet static analysis still works well. It turns out that real programs often don't trigger the nasty behavior that makes things behave badly.

No, obviously.

You'd be surprised how much code this doesn't apply to.

> No, obviously.

But the true question is: can an algorithm figure that out?

Turing proved the answer is no.

Computer programs can have remarkably simple semantics.

All compilers do is analyse dependencies (or a lack of) and do things to exploit them or their absence. The algorithms that do that are inherently not able to solve the halting problem, but that clearly doesn't hurt or we wouldn't have processors at all.

You can all kinds of useful stuff without Turing completeness - eBPF code for example is guaranteed to terminate.

You can get 99% of the way there without solving the halting problem, though. :)

Sure, but under some assumptions. Assumptions like that some piece of code won't be transformed by a macro, that reasonably looking code like `a.b` doesn't have side effects, etc.

It's not that it's impossible, but that 1% (or 5%, 10%, ???% depending on how the project is structured and whether it uses a lot of side-effects or dynamic properties) can be enough make your program crash if the assumption turns out to be wrong.

Another example that you could go for, is can you determine whether a property of an object is used or not. If you have a language like JavaScript where you can do `object[propertyName]`, that turns out to be very hard. In a pure functional language, that is comparatively pretty straightforward to detect.

Of course. Thus, "the soundiness manifesto". If you want to eval() your entire program to be something completely different just to spike your analysis tool, go ahead. But in the real world these cases are minimal and asking developers to make some annotations to help out in these cases isn't arduous.

Notably this is largely a problem with JavaScript and Ruby. There are plenty of non-functional languages where we don't need to havoc wildly to handle ordinary program behavior.

The javascript example gets further compounded by doing something like `object["prefix" + variable]`.

I've seen some very large companies abuse JS object proxies so that code is nearly impossible to follow even with the best IDEs and someone who's excellent at grepping.