The big advantage is that procedural abstraction allows you to separate use from implementation. We don't need to know how a procedure accomplishes what it does, we just need to know what the result should be. On the other side of the barrier, we don't need to know how where the arguments came from, or what the result is used for, we just need to compute it. Presumably, the more efficiently the better. Now let's return to Louis Reasoner. He's just written a sorting routine:
(define (lib-sort list <) (cond ((pair? list) (let ((first (car list))) (do ((before '() (cons (car after) before)) (after (lib-sort (cdr list) <) (cdr after))) ((or (null? after) (< first (car after))) (append (reverse before) (cons first after)))))) ((null? list) '()) (else (error "foo"))))It occurs to him that maybe that call to
reversecould be a bottleneck, so he instruments it with the code from the last post:
(define lib-sort (let ((reverse-counter 0)) (register-counter! reverse-counter) (lambda (list <) (cond ((pair? list) (let ((first (car list))) (do ((before '() (cons (car after) before)) (after (lib-sort (cdr list) <) (cdr after))) ((or (null? after) (< first (car after))) (set! reverse-counter (+ reverse-counter 1)) (append (reverse before) (cons first after)))))) ((null? list) '()) (else (error "foo")))))) ;Value: lib-sort (lib-sort '(3 1 4 1 5 9 2 6 5 3 5) <) ;Value 20: (1 1 2 3 3 4 5 5 5 6 9) ((cadr (assq 'reverse-counter *counters*))) ;Value: 11But Louis is called away before he can go much further down this path. He gives the rest of his tasks to his intern.
The intern has to write a program that, given a list, sorts it and returns a pair where the
caris the sorted list, and the
cdris the length of the sorted list. That's trivial:
(define (sort-and-length list <) (let ((s (lib-sort list <))) (cons s (length s))))But it occurs to him that this is less efficient than it could be. The call to
lengthhas to traverse the entire list, and presumably the call to
lib-sortmust as well. In order to cut down on the number of list traversals, the intern takes a look at the code for
lib-sort. It is rather baffling to him (he is an intern), but he figures out that since
reverseis called on every recursive call, the number of calls to reverse has to equal the length of the list. So he codes up this monstrosity:
(define (sort-and-length list <) (let* ((c (assq 'reverse-counter *counters*)) (start ((cadr c))) (s (lib-sort list <))) (cons s (- ((cadr c)) start))))Time passes...
It turns out a customer is complaining that the code is too slow. A quick test shows that he is trying to sort a list of ten thousand elements and it is spending all its time in
“What idiot wrote this?!” asks Cy D. Fect. “There is an FFI to
qsort.” Cy replaces the sort routine:
(define (lib-sort list predicate) (vector->list (ffi-qsort (list->vector list) predicate)))Of course he removed the code that tracks calls to
reversebecause qsort doesn't use it. When he checks in the code, lib-sort is much, much faster, but for some reason all the menus in the GUI now only contain a single entry. Cy calls in Ben Bitdiddle for help. Ben notices that the GUI calls
sort-and-lengthfor each menu, and
sort-and-lengthis reporting that each menu has zero entries. He fixes
sort-and-lengthto do the obvious thing and everything is off and running again. Ben shakes his head and sighs.
One of the most important points of procedural abstraction is that it allows you to change the implementation of the procedure at will without having to analyze the entire code base. We saw before that if we allow the internal variable names to escape (by using them as keys), then we can no longer change the names. In this case, we're going further. We want to eliminate the name altogether because we're changing the entire algorithm. The variable `reverse-counter' won't even exist anymore in this code. By exposing it in this way, we made it possible for an unplanned dependency to be added.
In this example, the unplanned dependency was rather idiotic. That's not the point. I have run into this sort of bug many, many times where an abstraction is not fully documented (or not well documented) and a programmer misunderstands the API and uses some internal function for the wrong purpose. Things work fine until the implementation changes, then very weird unrelated things start to break. Sometimes the code is so tangled that you have to emulate the effect of the old implementation just to keep from having to rewrite huge swaths of the unrelated code.