It's not about technology for its own sake. It's about being able to implement your ideas.
(If you haven't read On Being Sufficiently Smart, go ahead and do so, otherwise this short note won't have any context.)
I frequently write Erlang code that builds a list which ends up backward, so I call
lists:reverse at the very end to flip it around. This is a common idiom in functional languages.
lists:reverse is a built-in function in Erlang, meaning it's implemented in C, but for the sake of argument let's say that it's written in Erlang instead. This is super easy, so why not?
reverse(L) -> reverse(L, ). reverse([H|T], Acc) -> reverse(T, [H|Acc]); reverse(, Acc) -> Acc.
Now suppose there's another function that uses
reverse at the very end, just before returning:
collect_digits(L) -> collect_digits(L, ). collect_digits([H|T], Acc) when H >= $0, H =< $9 -> collect_digits(T, [H|Acc]); collect_digits(_, Acc) -> reverse(Acc).
This function returns a list of ASCII digits that prefix a list, so
"1234". And now one more "suppose": suppose that one time we decide that we really need to process the result of
collect_digits backward, so we do this:
The question is, can the compiler detect that there's a double reverse? In theory, the last
reverse could be dropped from
collect_digits in the generated code, and each call to
collect_digits could be automatically wrapped in a call to
reverse. If there ends up being two calls to
reverse, then get rid of both of them, because it's just wasted effort to double-reverse a list.
lists:reverse as a built-in, this is easy enough. But can it be deduced simply from the raw source code that
reverse(reverse(List)) can be replaced with
List? Is that effort easier than simply special-casing the list reversal function?
permalink June 14, 2009
I'm James Hague, a recovering programmer who has been designing video games since the 1980s. Programming Without Being Obsessed With Programming and Organizational Skills Beat Algorithmic Wizardry are good starting points. For the older stuff, try the 2012 Retrospective.
Where are the comments?