5 ms·
Pure-function analysis is not that hard. If you want the easy one, it is a pretty straightforward local analysis. If you want the hard stuff you need a sound ca
by UncleMeat 6y ago
Pure-function analysis is not that hard. If you want the easy one, it is a pretty straightforward local analysis. If you want the hard stuff you need a sound call graph and some fix-point computation over the whole program, but it is still achievable.
The thing that is valuable here is the existence of pure functions, not necessarily the requirement. For a huge number of real programs written in java or whatever the exact same technique applies.
- amelius 6y ago> but it is still achievable I would say it is undecidable, to be honest. For example if(undecidable_function()) return lots_of_code(); else return 0; Can you remove lots_of_code() or not?
- AlexCoventry 6y agoYou can get 99% of the way there without solving the halting problem, though. :)
- jfmengels1 6y agoSure, 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.
- wolfadex 6y agoThe 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.
- UncleMeat 6y agoOf 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.
- choeger 6y agoThey 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.
- shwestrick 6y agoIMO 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!
- mhh__ 6y agoNo, obviously. You'd be surprised how much code this doesn't apply to.
- amelius 6y ago> No, obviously. But the true question is: can an algorithm figure that out?
- mhh__ 6y agoTuring 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.
- UncleMeat 6y agoAlmost 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.
- mrkeen 6y ago> Pure-function analysis is not that hard. Awesome! My colleagues won't come to Haskell. But I can stop asking them if Java can tell pure from impure.