Digging Deeper into Sufficiently Smartness
Programming in the 21st Century - James Hague - June 14, 2009(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 collect_digits(“1234.0”) returns “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:
reverse(collect_digits(List))
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.
With 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?
Categories: Blogs Programming in the 21st Century
Erlang on Twitter
» jajusuf (ja'jusuf): dewa erlang kali dilangit RT @rezaovlozz: Lo juga donk cup deket ama agama,biar nanti dlangit kita besama2”@jajusuf: @edy_sant: @yuuuuda:”
» felhobacsi (Gergely Hodicska): RT @oker1: Efficient Web Applications with Erlang and Cowboy http://t.co/A6alQ27nSz
» renotz (reni pravita): At sevel wif @rei_erlang, @the_backBones, roni koplak.. Wkwkwkkk http://t.co/xYcnheAfdR
» raditya_erlang (raditya_erlangga): @0rdinary_boys allhamdulilah bay sehat km sendiri
» 0rdinary_boys (loedin): @raditya_erlang bozzz gmn kbarnya nh. #
» CindyEKC (Cindy Puspita A ): Hehe”@doni_erlang: Hus dak blh gt lah haha “@CindyEKC: Iy kak lumayan oleh* buat mak yg lg d rumh hhhehe””
» geeksays (A Geek): Erlang - A concurrent Programming Language [Overview] http://t.co/5xbhPXGKmn
» TrainByTweet_VO (TrainByTweet_VO): VOIP: #Engineering #Network #VOIP #Erlang #Ethernet #Codec #Voice #Bandwidth #Signaling #Protocol #Firewall #Security #Encryption
» newitfarmer (newitfarmer): [repost ]BigData Using Erlang, C And Lisp To Fight The Tsunami Of Mobile Data http://t.co/GACAb67apP
» newitfarmer (newitfarmer): Photo: [repost ]BigData Using Erlang, C And Lisp To Fight The Tsunami Of Mobile Data… http://t.co/HC8WstgdvJ
Statistics
Number of aggregated posts: 10648
Most recent article: May 14, 2013
Latest comments
» Moraru on This is Why You Spent All that Time Learning to Program: It is true that computer science was a pain in the back at time that i’ve had to learn it…
» Commercial hand dryers on Couchbase Meetup at new HQ: Buy online from here where you will get so much of variety in Commercial hand dryers for people. If you…
» Fort McMurray Homes on Motivated Reasoning and Erlang vs Python vs Node: I don’t really understand why this post is motivational? I don’t even see a post, just a title. Fort McMurray…