Hacker News Reader

Comment by lisper | Hacker News Reader

Sounds like a cool idea, but how do you fix bugs in functions with lots of callers?

That's basically what the twitter thread I linked explains. It sounds like there is an automatic propagation mechanism for updating downstream callers if the type hasn't changed, otherwise it sounds like a manual update process.

Sounds like trading one set of problems for another.

Welcome to software engineering where there is no golden bullets, only different tradeoffs :)

There are also circles of hell. (opposite of silver bullet)

Law of conservation of complexity

Tangent: here's what I find fascinating: when we evaluate which algorithm or data structure is best to handle a given situation, we know how to reason about algorithmic complexity and pick a best option for our situation.

But then when it comes to ideas like this we just tend to say "we're trading one set of problems or another", as if we can't evaluate the problems in a similar manner. And I'm not picking on you here, I tend to do the same!

Yes, we're trading one set of problems for another, but what if the old set of problems was "O(n²)" and the new set of problems is "O(nlog(n))"? Or maybe it's the other way around. Why isn't it obviour how to apply those earlier skills here?

I would like to note that even with algorithms/datastructures "best" is USUALLY not the word (even assuming that all algorithms/structures are discovered/known). "Good enough" / "fits in my multi dimensional budget" is reality:

(0) It is easy to order two real numbers. 1 is greater than 0. But can we order points on the cartesian plane (1,2) or (2,1) or (0,100000000000)? Already at 2nd dimension not all points are easily ordered. There is solution "just give priority to 1st coordinate", but can you really completely disregard memory usage and focus solely on cpu?

(1) Theoretically, to get "best", one needs to evaluate not only O(n) of avg cpu usage, and avg memory usage, but also worst and best cases, while using knowledge of input data distribution (e.g. maybe input is almost sorted). Memory access patterns, cache locality, battery life, suitability for your hardware also must come into play. (many dimensions)

(2) Practially one has to do profiling on real hardware with real configurations / inputs / workloads. Different workloads may favor different algorithms/structures. (again results with many dimensions)

(3) Due to constrained time people will not even go over all algorithms. Real people will immediatly rule out really bad ones, then pick 1 or 2 algorithms that theoretically are good enough match, and see if their profiling results fit in cpu/memory budgets. (even if budget is not on paper, but just part of intuition)

The same way we do now: release a new version and tell people to migrate.

No, now I can just redefine the buggy function and all the callers will get the new version automatically. Having to update all callers seems like a high price to pay. Seems like the Right Answer is something like a hash of the api or the contract rather than the implementation.

The (public) name of the implementation is the unique identifier of the contract in most systems, so I think your "Right Answer" is roughly the status quo?

No. The name of a function in current languages has no connection at all to what the function does. (What would be the contract for a function named ‘foo’?)

That's kind of the thing that makes APIs possible, right? It sounds to me like "what if programming were done in a completely flat global namespace in which abstractions, encapsulation, and structure were impossible."

No. An API specifies more than the name of the function. It will specify the arguments, their types, the type of the return value, and at least informally, what the function does. You can change the underlying implementation without changing the API. That's the whole point of an API. The problem with current API technology is that the informality of the spec of what the function does. That allows some aspects of the behavior of the function to change without triggering any warnings.

By having the linker work on hashes of implementations you eliminate that problem but create a new problem. You can no longer change the behavior of the function because you can't change the function. That means you can't suddenly change behavior that some caller is counting on, but it also means you can't fix bugs without changes in the caller.

Reading this now, I'm imagining all the horrors of static linking but applied to every function instead of whole modules.

Maybe the simplest solution is to allow the function to change to the new version, but make it easy to revert in the event that something breaks. This of course means that you can't make the names of the functions their hash (without lying, preventing the runtime from checking that hashes ways match, or modifying emitted bytecode or native code to do what you want), it has to be an orthogonal layer on top of them like types (as I mentioned elsewhere in the thread).

Nope, according to https://twitter.com/unisonweb/status/1173942969726054401

when you change a function implementation the system has to walk the callers graph backwards starting from all the places where the function was called updating all the implementations with the new hash, then callers of these with the new implementation and so on up to main (or whatever it's called).

I had a chance to implement something like this in a system that used jbpm 3 graph language (basically process X version 1 called process Y version 1 and I updated process Y to version 2). It's nontrivial especially with recursion, I'm wondering how they are dealing with that.

A git-like datastore for your AST+callgraph.

Let's say you have definitions like that:

    f: Nat -> Nat
    g: Nat -> Nat
    h: Nat -> Nat
    h x = g (x * 2)
    g x = f (x * 3)
    f x = x < 0 ? 1 : h (x / 4)

And now you change f to be

    f x = x < 1 ? 1 : h (x / 4)

How do you do that? There's a cycle in the callgraph. In fact - how do you calculate a hash of a function that calls itself if you need its hash to calculate its hash :)

EDIT: nevermind, recursion is a special case handled differently.

Reply on news.ycombinator.com