Hacker News Reader

My most recent Orwellian moment was reading about an old heuristic algorithm with high complexity that has been abandoned as the middle ground between a simpler heuristic and much more complex ones because of its computational complexity.

The problem as I see it is in how they represent the data in a way that makes one think of linear algebra. Refinements brought the naive original implementation down to cubic time, and the literature, as far as I can tell, stops there.

But here’s the thing, when I tried to unpack the logic to figure out what is actually going on under the hood, I realized that a quadratic subproblem could be restated as a sorting problem. Sorting is very much nlogn these days, if not lower due to radix sort being an option.

Which means that this heuristic has the same computational complexity as the naive solution. I’m not saying I’ve discovered anything new, except perhaps that this algorithm is homomorphic to another one. It’s just that it’s so stuck in one representation that you can’t see it for what it is unless you stare pretty hard at it.

Another strategy: Instead of creating new abstractions willy-nilly (which will probably be "wrong" in some sense you won't discover until much later, when it's too late to drop it), you base your abstractions off something that selects for "correct" low-entropy abstractions, e.g. by stealing ideas from math.

By all means, steal ideas from math. (Great artists, etc.) Math has had a couple thousand years practice in learning how (and how not to) express abstract ideas as formal written text.

But don’t abuse math. Like redefining summation to mean any old thing under the sun. Least of all when it’s a fricking union, for which the math symbol is ‘∪’, not ‘＋’.

Union symbol is not on the keyboard.

Sure, make it easy to type then we can use it instead of +

However, anyone who has been programming for a while should be able to puzzle out what + is doing.

Emojis aren’t on the keyboard either but folks don’t seem to have a problem typing them, even on desktop.

Funny that software engineers can figure out complex parallelism and algorithms, but typing ∪ as a function name is next to blasphemy.

Both set union and number addition are examples of monoids, a maths concept from the field of abstract algebra. So there is a maths abstraction that unites these ideas.

Uhh quick limiting thing here (although I agree that the addition symbol is fine): the existence of a unifying math concept alone does not justify using the "+" symbol. By that argument, notating permutation conjugation with a "+" is fine, but that would be a notational sin as the "+" operator is reserved for commutative operations.

However, with that disclaimer, noting that both operations form monoids and both are commutative justifies the "+".

Haskell doesn't use the + symbol for monoids, it uses <>.

"Computer Science could be called the post-Turing decline in the study of formal systems."

Bad example is bad example. Programmers are awful for using algebraic symbols to describe non-algebraic semantics. Algebra is already its own language; a lingua franca of math. If you’re abusing it for a different purpose then you’re doing both of them wrong.

Otherwise, article is basically arguing we should drag everyone down to the lowest-common denominator “to be safe”, rather than allowing individuals and groups to raise themselves up as appropriate in order to tackle their given problems more effectively.

That’s group-think, authoritarianism, and reducing expert knowledge workers to anonymous plug-n-play “human resources”. What’s the software equivalent to “Churnalism”? Because that’s how you get the software equivalent to “Churnalism”.

Now, if you want to talk about the criticality of Human Communications, and how utterly atrocious many programmers are at it, even amongst their own (never mind with “outsider” stakeholders like users and management), then I’m all on board with that discussion. Good and bad use of abstraction (trade jargon), effective knowledge “transfer” (really reconstruction), and successful team collaboration (especially heterogeneous teams, which are vital to solving the actual problem at hand). This is epically important stuff, and this profession has so much yet to learn.

But rationalizing away “this is how we’ve always done it so this is how we will always do it”? Don’t be surprised when the rest of the world treats you as cheap, easy, disposable code-monkeys, paying you peanuts and zero respect. That’s the deal you bought into yourselves, and you have no-one to blame but yourselves.

> What’s the software equivalent to “Churnalism”?

Basically anything consumer-facing from the past 15 years, especially if it's "mobile"

>you should be able to inspect the meaning of the more abstract syntax by expanding its definition in place and see how it works in context. [...] But why that approach is not integrated into the language itself, I have no idea.

Are you asking why _all_ programming languages don't make their own Abstract Syntax Tree a 1st-class concept for self-reflection and manipulation of its own syntax like Lisp?

Because there are tradeoffs to that approach. If one thinks there are zero tradeoffs to Lisp's philosophy of "code is data", I contend one doesn't fully understand Lisp. Yes, self-inspection is a powerful device but even Lisp programmers[1] keep inventing new languages for others to use that do not have Lisp-like ASTs as 1st-class concepts. I ask people to really think deeply on why that's been happening for decades and comment with any insights.

[1] e.g. Guy Steele a Lisp expert, works on creating the new Java language at Sun in 1994.

The main reason is that designers are not even aware of the techniques. You can get CS degree that includes compiler work, and have a head full of LALR(1), without knowing anything about the Lisp approach.

In my Alma Mater, at the time, there was a third year course in programming languages that had Scheme exposure. The follow-up fourth year course in compiler construction was all C hacking with Lex and Yacc, and that was that.

I was able to wriggle out of taking the prerequisite, too.

> Are you asking why _all_ programming languages don't make their own Abstract Syntax Tree

No, I'm asking why there isn't _any_ programming language (that I'm aware of) with an integrated IDE where you can make static code rewrite expansions (replace an function call instance with its definition) at writing time, and instead depend on waiting until runtime to have an in-memory stack and navigate between functions to see how a function call will run.

Curious what happens when V1 and V2 cannot be "plused"

In a statically-typed language you’d just get a compile error. The compiler knows the types of the values in the map and whether or not the (+) operation is valid for them. You’d likely need a little more code than what’s in the GP post, something restricting the values in your map to types that implement “addable” or whatever the terminology is for your language.

In a dynamically-typed language you’d get some kind of runtime error.

Just think of (+) like any other function and what would happen in your language if you call a function with types that the function doesn’t support.

Well, in Scala with default predef it would depend on the order or the arguments. If first one is a string it would just append string representation of the second one. One could use a random generator to guess what would happen in JavaScript. I do not know what Python does in these cases

Sorry for being cryptic, the point was that I prefer appenders being explicitly documented in types or method signatures instead of some built-in magic

Two more possibilities to add onto the pile: Transpilers (like Typescript to Javascript) and custom Domain Specific Languages.

Swift extensions are a perfect way to achieve this.