{"id":6772,"date":"2015-05-18T22:19:48","date_gmt":"2015-05-19T02:19:48","guid":{"rendered":"http:\/\/esr.ibiblio.org\/?p=6772"},"modified":"2015-05-22T05:32:06","modified_gmt":"2015-05-22T09:32:06","slug":"zeno-tarpits","status":"publish","type":"post","link":"http:\/\/esr.ibiblio.org\/?p=6772","title":{"rendered":"Zeno tarpits"},"content":{"rendered":"<p>There&#8217;s a deeply annoying class of phenomena which, if you write code for any length of time, you will inevitably encounter.  I have found it to be  particularly prevalent in transformations to clean up or canonicalize large, complex data sets; repository export tools hit variants of it all the time, and so does my doclifter program for lifting [nt]roff markup to XML-DocBook. <\/p>\n<p>It goes like this.  You write code that handles a large fraction (say, 80%) of the problem space in a week.  Then you notice that it&#8217;s barfing on the 20% remaining edge cases.  These will be ugly to handle and greatly increase the complexity of your program, but it can be done, and you do it.<\/p>\n<p>Once again, you have solved 80% of the remaining cases, and it took about a week &#8211; because your code is more complex than it used to be; testing it and making sure you don&#8217;t have regressions is about twice as difficult.  But it can be done, at the cost of doubling your code complexity again, and you do it. Congratulations! You now handle 80% of the remaining cases.  Then you notice that it&#8217;s barfing on 20% of remaining tricky edge cases&#8230;.<\/p>\n<p>&#8230;lather, rinse, repeat.  If the problem space is seriously gnarly you can find yourself in a seemingly neverending cycle in which you&#8217;re expending multiplicatively more effort on each greater effort for multiplicatively decreasing returns.  This is especially likely if your test range is expanding to include weirder data sets &#8211; in my case, older and gnarlier repositories or newer and gnarlier manual pages.<\/p>\n<p>I think this is a common enough hazard of programming to deserve a name.<\/p>\n<p><!--more--><\/p>\n<p>If this narrative sounds a bit familiar, you may be thinking of the paradox of motion usually attributed to the philosopher Zeno of Elea.  From the <a href=\"http:\/\/www.iep.utm.edu\/zeno-par\/\">Internet Encyclopedia of Philosophy<\/a>:<\/p>\n<blockquote><p>\nIn his Achilles Paradox, Achilles races to catch a slower runner\u2013for example, a tortoise that is crawling away from him. The tortoise has a head start, so if Achilles hopes to overtake it, he must run at least to the place where the tortoise presently is, but by the time he arrives there, it will have crawled to a new place, so then Achilles must run to this new place, but the tortoise meanwhile will have crawled on, and so forth. Achilles will never catch the tortoise, says Zeno. Therefore, good reasoning shows that fast runners never can catch slow ones.<\/p><\/blockquote>\n<p>In honor of Zeno of Elea, and with some reference to the concept of a Turing tarpit, I propose that we label this programming hazard a &#8220;Zeno tarpit&#8221;.<\/p>\n<p>Once you know this a thing you can be watching for it and perhaps avoid overinvesting in improvement cycles that pile up code complexity you will regret later.  Also &#8211; if somebody asks you why your project has run so long over its expected ship date, &#8220;It turned into a Zeno tarpit&#8221; is often both true and extremely expressive. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>There&#8217;s a deeply annoying class of phenomena which, if you write code for any length of time, you will inevitably encounter. I have found it to be particularly prevalent in transformations to clean up or canonicalize large, complex data sets; repository export tools hit variants of it all the time, and so does my doclifter&hellip; <a class=\"more-link\" href=\"http:\/\/esr.ibiblio.org\/?p=6772\">Continue reading <span class=\"screen-reader-text\">Zeno tarpits<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13],"tags":[],"class_list":["post-6772","post","type-post","status-publish","format-standard","hentry","category-software","entry"],"_links":{"self":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/6772","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6772"}],"version-history":[{"count":4,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/6772\/revisions"}],"predecessor-version":[{"id":6776,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/6772\/revisions\/6776"}],"wp:attachment":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6772"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6772"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6772"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}