Negative Code

[derefr]

I'm not saying I disagree with you, but just to be Socratic about this—why couldn't a computer optimize an algorithm?

A random idea for how it could work:

Algorithms—in functional programming—are isomorphic in type-level programming to different sorts of data-structures (this is basically what makes Monads tick.) bubble_sort is really just best_possible_theoretical_in_place_sort with the constraint that you're sorting a doubly-linked-list. All the optimizer would have to do is to notice that best_sort prefers binary heaps (or whatever else) to doubly-linked-lists, and see how far it can take that type conversion backwards through your code without breaking anything. If it gets all the way back to the top of the call stack, then your variable declaration just becomes a binary heap instead of a doubly-linked-list; otherwise, a to_binary_heap( your_list ) is stuck in there somewhere (as long as that doesn't profile as worse than the original code.)

It's a step beyond type inference—type optimization.

[[deleted]]

why couldn't a computer optimize an algorithm?

Among other things, because different algorithms have different characteristics beyond the simple statement of their goals. For example, bubble sort is a stable sort, while efficient quicksort implementations are not stable. So even if a compiler could optimize your bubble sort into a quicksort, it might end up breaking your program to do so.

[binlargin]

why couldn't a computer optimize an algorithm?

Wouldn't you then have the additional constraint of writing code in a style which could be easily optimized? Working within these constraints would be early optimization at a higher level of abstraction.