Those of you who enjoyed my post on palindrome predicates may also like Joe Marshall’s follow-up to his original post that inspired mine. In it, he considers the two implementations—recursive and iterative—and what it would take for a sufficiently smart compiler to generate code for the recursive algorithm that’s as efficient as that for the interative algorithm.
He does that by imagining a series of steps that such a compiler might take to transform the recursive solution into the iterative one. The lowest hanging fruit is, of course, to get rid of the string copying that the substring function does in most implementations of Scheme (and all conforming implementations of Common Lisp). The Guile Scheme implementation almost does this—see the discussion by Chris Wellons in my original post. That single optimization produces a dramatic improvement in performance. When I ran the same test with Chez Scheme, which does not implement copy-on-modify semantics for stringcopy the execution went from a little over 9 seconds to over an hour and a half.
Marshall doesn’t stop there. He continues with a set of more or less reasonable steps that a smart compiler might make until the two implementations are the same. (One of those steps is unlikely to be made by a compiler, regardless of how smart it is, but is nevertheless possible.) Marshall doesn’t mean for his post to be taken as a serious suggestion: it’s more of a thought experiment. It’s an interesting exercise in understanding how some simple steps can make code significantly better.