4.3.1 Coding style

Scheme is a rich language, in which there are usually several ways to say the same thing. A coding style is a set of rules that a programmer uses for choosing an expressive form to use in a given situation. Usually these rules are aesthetic, but sometimes there are efficiency issues involved; this section describes a few choices that have non-obvious efficiency consequences.

Better predicates

Consider the following implementation of map as might be found in any introductory book on Scheme:

(define (map f lst)
  (if (null? lst)
      '()
      (cons (f (car lst)) (map f (cdr lst)))))

The problem with this definition is that at the points where car and cdr are called we still do not know that lst is a pair. The compiler must insert a type check, or if type checks are disabled, the program might give wrong results. Since one of the fundamental properties of map is that it transforms lists, we should make the relationship between the input pairs and the result pairs more apparent in the code:

(define (map f lst)
  (cond ((pair? lst)
         (cons (f (car lst)) (map f (cdr lst))))
        ((null? lst)
         '())
        (else
         (error "Not a proper list:"  lst))))

Note also that the pair? case comes first because we expect that map will be called on lists which have, on average, length greater that one.

Internal procedures

Calls to internal procedures are faster than calls to global procedures. There are two things that make internal procedures faster: First, the procedure call is compiled to a direct jump to a known location, which is more efficient that jumping ‘via’ a global binding. Second, there is a knock-on effect: since the compiler can see the internal procedure, the compiler can analyze it and possibly produce better code for other expressions in the body of the loop too:

(define (map f original-lst)
  (let walk ((lst original-lst))
    (cond ((pair? lst)
           (cons (f (car lst)) (walk (cdr lst))))
          ((null? lst)
           '())
          (else
           (error "Not a proper list:"  original-lst)))))

Internal defines

Internal definitions are a useful tool for structuring larger procedures. However, certain internal definitions can thwart compiler optimizations. Consider the following two procedures, where compute-100 is some unknown procedure that we just know returns ‘100’.

(define (f1)
  (define v 100)
  (lambda () v))

(define (f2)
  (define v (compute-100))
  (lambda () v))

The procedure returned by f1 will always give the same result and the compiler can prove this. The procedure returned by f2 may return different results, even if f2 is only called once. Because of this, the compiler has to allocate a memory cell to v. How can the procedure return different results?

The fundamental reason is that the continuation may escape during the evaluation of (compute-100), allowing the rest of the body of f2 to be executed again:

(define keep)

(define (compute-100)
  (call-with-current-continuation
   (lambda (k)
     (set! keep k)
     100)))

(define p (f2))

(p)                ⇒ 100
(keep -999)        ⇒ p     re-define v and p
(p)                ⇒ -999

To avoid the inefficiency introduced to handle the general case, the compiler must prove that the continuation cannot possibly escape. The compiler knows that lambda expressions and constants do not let their continuations escape, so order the internal definitions so that definitions of the following forms come first:

(define x 'something)
(define x (lambda (…) …))
(define (f u v) …)