« A tool that reflects how I write code!
Inferring the types of the Combinator Birds »

Naive Programming Follow-Up

I was happy to see some pretty engaged discussion at Reddit about my recent blog post about Naive Programming. What was most clearly lacking in my original post were some examples, so I’ve included a concrete example from the Structure and Intrepretations of Computer Programs book (the famous SICP book) at http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html. 

Here is the naive code for factorial:

(define (factorial n)
  (if (= n 1)
  1
  (* n (factorial (- n 1)))))

Now here is the more idiomatic usage of Scheme:

(define (factorial n)
  (fact-iter 1 1 n))(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                  max-count)))

In the SICP, which is an introductory text, programmers are being taught from the beginning to write code that is unclear, and works around problems in the language implementation or specification. This sets up bad habits for life. I’ve had to work for years to ween myself off the habit of premature/unneccessary optimization. To be honest, I don’t know whether the problem lies in Scheme implementation or specifications, but I do know it harms the quality of Scheme code.

While intended as tounge in cheek, the examples at Evolution of a Haskell Programmer (http://www.willamette.edu/~fruehr/haskell/evolution.html) are another great set of examples because they do reflect reality. The code that is the easiest to understand is considered naive by advanced Haskell programmer. That is upside-down, the naive code is the best code from the point of view of an engineer. A professional software engineer strives to write code that is easy to understand, easy to modify, easy to verify, and that clearly communicates a programmer’s intent. To achieve this code should reflect the problem domain as much as possible rather than the vagaries of the language (e.g. an inability to transform simple recursive calls into iteration

I hope these examples help clarify my view point. 

This entry was posted on Monday, July 2nd, 2007 at 6:09 pm and is filed under Everything. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

7 Responses to “Naive Programming Follow-Up”

  1. cdiggins.com » My Goal: Naive Programming Says:
    July 2nd, 2007 at 6:14 pm

    [...] make sure your language implementation can deal with it. PS: I’ve followed this up with a new post about naive programming containing some code [...]

  2. soegaard Says:
    July 2nd, 2007 at 9:49 pm

    Since factorial and fibonacci is always used in benchmarks the idiomatic names are “fact” and “fib” due to the puns.

    Be that as it may, it strikes me as odd, that your original example counts down where as the last one counts up. A more natural translation into SICP-style would be:

    
(define (fact n)
  (define (fact-iter product n)
    (if (= n 1)
        product
        (fact-iter (* n product) (- n 1))))
  (fact-iter 1 n))

    However, I don’t think SICP-style is idiomatic Scheme anymore. A much more common approach to these kinds of loops are named lets:

    
(define (fact n)
  (let loop ([product 1] [n n])
    (if (= n 1)
        product
        (loop (* n product) (- n 1)))))

    A srfi-42 addict as me would write:

    
(define (fact n)
  (product-ec (: i (+ n 1))
              i))
  3. cdiggins Says:
    July 2nd, 2007 at 10:06 pm

    Thanks for your feedback Jens, and sharing a more idiomatic Scheme approach. Clearly I am not much of a Scheme expert. :-)

    I actually lifted both samples directly from the SICP page I linked to.

  4. Kirit Says:
    July 3rd, 2007 at 5:42 am

    The point at issue has to do with tail-call optimisation. The Scheme standard states that it must perform this in order to get O(1) memory overhead (I have an explanation of the memory overhead issues in recursive forms no my web site).

    In order to get the recursive functions into a form that the compiler can optimise they have to be given in tail recursive form which for a function like factorial involves the use of a separate accumulator argument.

    Re-writing recursive algorithms into a tail recursive form can be an extremely hard challenge. I thought the power function I used as an example impossible after trying without success for a few days. Luckily somebody else knew the solution.

    The compiler is basically looking for a way to remove the function call overhead by re-using the same stack frame for each step. In effect it converts the recursion into a for loop.

  5. will Says:
    July 3rd, 2007 at 10:42 am

    Chris, have you read Iverson’s Turing Award lecture?

    I’ve also been struggling with this issue. Haven’t connected all the dots, though.

  6. will Says:
    July 3rd, 2007 at 11:24 am

    From Iverson’s “The Description of Finite Sequential Processes”:

    A programming language is commonly characterized as problem-oriented or machine-oriented, according as it is intended mainly for the description and analysis of algorithms or for their execution.

    Where are the problem-oriented languages today? None of the languages we learn and use–even those considered “academic”–are effective tools of thought. C++, Java, Lisp, Haskell, even Cat all fall terribly short of the mark.

  7. soegaard Says:
    July 3rd, 2007 at 1:37 pm

    Thanks for indenting the code in my comment.

    After checking with SICP I notice they have a footnote 29) which is what they would have
    written in “real” code.

    Btw, I forgot a 1 in the srfi-42 version.

Leave a Reply

You must be logged in to post a comment.