Safe dead code removal in a pure functional language
jfmengels.net
jfmengels.net
One place I have found that static analysis fails is with API contexts. Either they get it wrong and offer to remove API elements or they get it less-wrong and just don't touch anything that can be exported. Granted getting it right would require all usages of the API or a blessed list of things we know we want to keep ... in which case we are potentially back at our source code as a source of truth anyway.
Another interesting hole is "do we keep code that is only referenced by tests?" In some cases, it makes sense but it's definitely a knob that the user needs to adjust manually so far as I have seen.
To be slightly fair to Java, annotations don't themselves do anything to the annotated method. Calling a method directly is the same regardless of whatever annotations are on it -- of course, unless it or one of its upstreams looks at the annotations, but that's isomorphic to just passing the data along.
Java annotations induce different behaviors in specific callers that are designed to take advantage of those annotations, which is arguably even worse -- like a meta analogue of the COMEFROM keyword.
Also, coming across transient runtime errors because you use multi-catch (a basic Java language feature) and some java library that injects bytecode is pretty lame. All the benefits of a typed+compiled language with all the benefits of monkey patching!
There is a talk by Kent Dybvig called "the macro writer's bill of rights" on YouTube that goes into optimizations that help macro writers.
But in some cases, this is needed for efficiency.
To me, the answer is 'extremely often', so I don't see the value of what GP is proposing. It's nice to have pure functions and some kind of separation, but it's not worth it to give up returning values from effectful procedures.
You MAY be able to get away with making this a pure function by returning a shallow copy, but I believe that depends on how central the sharing aspect is.
> The return value is either going to pertain to the state before the side-effect, the state after the side-effect, or the side-effect itself. The first two could easily be broken out into pure functions. The third, again, mostly comes down to error reporting.
So this definitely falls into category three, which makes the coupling legitimate. It's possible I was wrong in my statement that that category "mostly comes down to error reporting"; it was just based on my own past experience.
I guess things get more complicated when you consider I/O. A function that gets a file handle or makes a GET request is technically impure and mutates the state of the macro-system, and yet is primarily concerned with what it returns. I tend to lump these into the "plain functions" bucket, but it's a gray area.
A function takes some declaration id, generates one or several records based on the declaration data, commits them to the database and returns the record id's so they can be used in the UI or similar.
Either the record id's are displayed to the user directly, they're used for filtering in a grid, used for generating response files to external system, or something else.
Often this would get called several times for the same declaration id, usually generating new records, so it's easier to have the function return the id's rather than trying to reconstruct what it did.
Could be there's an easy way to map this to pure functions, I haven't thought about it. Would be interested to know though.
> Often this would get called several times for the same declaration id, usually generating new records, so it's easier to have the function return the id's rather than trying to reconstruct what it did.
Are the "new" records meaningfully different in some way, or are they just new instances in memory of what is fundamentally the same value? In the former case, there's state somewhere that's causing each one to be different (there is not a pure relationship from id -> record set). In the latter case, you don't actually need multiple instances (unless you expect them to be mutated by other code down the line and are guarding against side-effects, in which case you could defensively clone the pure function's result as needed instead of calling it multiple times).
Edit: it's possible I misunderstood, and that what's happening is you're inserting data into a database which has its own auto-incrementing IDs that it then returns to you. If so, the coupling between value creation and state/mutation exists in the database's API itself, and so is outside of your control. There's not much you can do in that case because you don't own that code.
> Are the "new" records meaningfully different in some way
Yeah usually. A typical example is something external added data to the declaration, and new records are generated to reflect this.
And yeah, auto-incs is the norm.
But this generally only works if all of the information going into Z is under your code's purview. If the auto-increment were happening in your code instead of in the database then you could make the records a pure function of the domain data + the next auto-incremented ID, and the procedural code which calls the pure function would retrieve the ID and increment it, call the pure function with it to generate the records, and then call another impure function to persist them. But of course moving the auto-increment logic and state from the DB to your application code is a huge undertaking involving many other trade-offs, and is not necessarily recommended just for the sake of something like this.
It is reasonably easy to do a caching function that takes arbitrary functions and data and caches their result as a map of tuples (data, function, timestamp for example). Definitely not always the right thing to do, but could eek out some performance in where you get the same data multiple times.
Edit: I found that it is called memoization: Looks to me to very easily be extensible to allow timestamps too, to check if the record is older than X.
https://stackoverflow.com/questions/833180/handy-f-snippets/...
> unless you expect them to be mutated by other code down the line and are guarding against side-effects
Sometimes you hand off a mutable object to some other code and that code mutates it for its own purposes. If you hand the same object to multiple functions in this case, they'll all see each other's changes and if this wasn't intentional then voila, you've got a bug. This is one motivation for immutable data structures: you don't have to worry about whether an object might get mutated so you don't have to eagerly clone it. But in an existing codebase it may not be a trivial thing to simply introduce immutability. This is why, instead, I suggested making that defensive cloning explicit and decoupled from the rest of the logic.
The crux is that you can't deterministically know how the operation will go until you try it, and you therefore have to return some information about the operation itself which can't just be derived in a pure way from the state of things before or after the operation.
is talk called "Effects as Data" describing that idea: https://www.youtube.com/watch?v=6EdXaWfoslc
I developed an open source game in Elm, and I've been very impressed with the benefits of the pure functional approach. It takes some getting used to, for sure, but it makes things really simple to reason about once you get used to it.
There are definitely rough edges still: Elm in particular is just missing a lot of stuff, but I was surprised how much value the pure functional approach gave me.
Separate the thing you want done from the doing it, because when you intermingle the doing-the-thing it greatly complications the scheduling logic. Think of it as a working programmers io monad.
Otherwise the best you can do is lint and rely on a human to use their best judgement about whether to remove it or not.
The C++ language allows temporary objects to be generated and/or optimized away.
Those objects can have constructors and destructors with side effects, and those side effects appear or go away together with the object to which they are attached.
If your program depends on whether a temporary object does something or not, you are officially screwed.
Recently, I discovered an like-new pair of shoes at the bottom of a closet. I bought them some four or five years ago, I guess, and somehow forgot about them. They got buried under other items. This was a day or two before Christmas; it was like an unexpected present.
Now, someone could have surreptitiously entered my home at any time before that and removed these "dead shoes". I would never have known.
So therefore, it wouldn't be stealing, right? It's a "semantics-preserving transformation of someone's belongings".
That does not preclude notifying the user, or getting confirmation
But even if you do blindly accept each fix, the behavior of the program won't change.
then he (I) happily switched to Elm, because even with a lot of static analysis rules, it's really hard to avoid impure functions when a lot of the libraries and existing code use that, and sometimes even require that.
If you don't want to use the GC it is customary to use a pure wrapper around malloc (even though you theoretically shouldn't, it works fine in practice).
https://dlang.org/library/core/memory/pure_malloc.html
https://run.dlang.io/is/xB0Qeu this RPN calculator (the one I wrote for the dlang.org page but ungolfed) is pure and checked as such by the compiler. It's also referentially transparent because "in" means the input parameter is constant and can't escape (and thread local fyi).
What if the removed function call would have produced an important error?
It's no different from a function entering into an infinite loop and never returning. It has a return type; it simply doesn't ever return.
Some type systems go further and have the type system differentiate between total and partial functions, where total functions are guarantee to always return a value of their type eventually.
In Haskell one must use the assertion's result to trip the assertion, which can be awkward. But Elm is strict; I wonder how assertions are treated in this sort of DCE.
assert(list.len() > 0);
//code that assumes that the list not be empty
if list.len() > 0 then
// code assumes that the list not be empty
else
assertion_fail("list is not empty")
One does not as such first makes an assertion as the first element of a sequence, and then proceeds under the assumption that the assertion did not fail, but rather calls the `assertion_fail` function on some code paths, which then never returns if ever it be reached.
The type system will call the function all the same, as as far as the type system and language runtime is concerned, it is an ordinary function that will return a value of the expected type, but under the hood it aborts the entire program, and prints proper diagnostics.
so instead of
function a(b) { assert(b > 0); return b + 1; }
you'd do
a b = if b > 0 then Ok (b + 1) else Err "b was not > 0"
To then use the result of the function call, you'll need to unwrap the result, by handling the case where the function returned Ok, but also the case where you return Err
case a -2 of Ok b -> -- display the value b Err errorMessage -> -- display the error message
THis is the kind of technique Elm uses to ensure that you'll have no runtime errors in your code: by forcing you to handle the error cases. The nice thing is that the types can indicate whether something can fail or can't.
Making it so you can't have asserts will just mean that you won't have those kind of tests.
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.
I would say it is undecidable, to be honest. For example
if(undecidable_function())
return lots_of_code();
else
return 0;
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.
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.
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.
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.
Things like dead-code removal are a pretty standard for modern optimizing compilers!
You'd be surprised how much code this doesn't apply to.
But the true question is: can an algorithm figure that out?
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.
Awesome! My colleagues won't come to Haskell. But I can stop asking them if Java can tell pure from impure.