Ask HN: Are there any languages/compilers that optimize at this level? | Hacker News Reader

Ask HN: Are there any languages/compilers that optimize at this level?

2 pointsgoldenkey3 comments

As you might know, if you wanted to grab the lowest entry from a list, lst.sort().first() is extremely inefficient compared to lst.select(1). Grabbing the first sorted entry is the selection algorithm for k=1 [1]

My hunch is that due to the halting problem, incompleteness, and Entscheidungsproblem, it would be extremely difficult, if not impossible, to do such high level optimization. But I would like to hear what HN has to say. Thanks!

[1] https://en.wikipedia.org/wiki/Selection_algorithm

[2] https://en.wikipedia.org/wiki/Entscheidungsproblem

View on HN

Well, the problem to optimise it is that sort will often not be the trivial bubble sort, but something like quicksort, that starts by sorting parts of the sequence. The fact that the first element of the result is the smallest element is therefore hidden to usual compilers. You would need a theorem prover, and even with them, it's not entirely trivial to prove.

So even for lazy programming language such as Haskell it may be impossible to transform the first sort into a selection of the extremum.

ON THE OTHER HAND!

If you used Common Lisp, and take the pain of shadowing the functions from the CL package, you could write a compiler macro on FIRST to perform this optimisation yourself.

However, this would be delicate, since in CL, the SORT function mutates the sequence, and both the predicate and the optional key function argument may have side effects. Not performing the SORT in those conditions would be a wrong optimisation.

But if your compiler-macro can determine that no side effect occurs, then you will be able to substitute the (first (sort ...)) call to a call to select the wanted extremum element.

OP asked "this level", by the way. It is hard to write macros for every such case.

However, OP may read about superoptimization, which is yet in research stage.

You’re “hiding” an important aspect: you know that the two programs are equivalent, i.e. for all inputs they return the same output.

This is something an algorithm can’t do.

If you have a given set of equivalent algorithms and you know their complexity, optimizing is somehow easier (though you can still get into complexity issues).

Reply on news.ycombinator.com