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.
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
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
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.
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 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
(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
return different results, even if
f2 is only called once.
Because of this, the compiler has to allocate a memory cell to
How can the procedure return different results?
The fundamental reason is that the continuation may escape during the
(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) …)
Note: The IEEE Scheme standard permits only lambda expressions and constants as the value of internal defines. Furthermore, all internal definitions must appear before any other expressions in the body. Following the standard simultaneously assures portability and avoids the implementation inefficiencies described in this section.