Previous | Table of Contents | Next |
The Scheme report acknowledges Lisp and Algol as Schemes intellectual parents. The main ideas that Scheme took from Algol, which are among the main ideas that distinguish Scheme from other dialects of Lisp, are block structure and lexical scope.
The following is an iterative Lisp program to compute a power of a number by repeated multiplication:
(define (power base expt) (power-helper base expt 1)) (define (power-helper base expt result) (if (= expt 0) result (power-helper base (- expt 1) (* result base))))
This program is written in Scheme but could work essentially unchanged in any dialect of Lisp. Although the notation may be unfamiliar, this program mirrors the structure that would be used in a C-like language:
int power(int base, int expt) { int result; result = 1; while (expt > 0) { result = result * base; expt = expt - 1; } return result; }
The procedure named power-helper in the Scheme version implements the while loop in the C version.
Its inelegant to clutter a program with helper procedures that are used only from one calling procedure. Scheme allows the programmer to make the helper procedure internal to the procedure that uses it:
(define (power base expt) (define (helper base expt result) (if (= expt 0) result (helper base (- expt 1) (* result base)))) (helper base expt 1))
So far, this is merely a cosmetic advance; it makes the program more self-documenting and reduces the possibility of accidentally writing two conflicting procedures with the same name. Internal definitions become more useful when combined with the other feature that Scheme took from Algol, lexical scope.
In the sample exponentiation program, the variable base has the same value in every call to the helper procedure. Scheme allows the helper to inherit that variable from the outer procedure:
(define (power base expt) (define (helper expt result) (if (= expt 0) result (helper (- expt 1) (* result base)))) (helper expt 1))
Because the name base is not reused as a parameter to the helper procedure, references to base within that procedure use the value of base in the outer power procedure.
The earliest Lisp interpreters used dynamic scope, which means that each procedure has access to the variables of the procedure that called it, rather than to the variables of the procedure inside which it is defined. Lexical scope is easier for a compiler because in a lexically scoped language, the compiler knows which variable any particular use of some name means, whereas in a dynamically scoped language, the same name in the same procedure may mean two different variables depending on which procedure calls it.
In addition to the efficiency advantage of lexical scope, another reason to prefer it over dynamic scope is that it avoids potential name capture bugs. If the same name is used in two different contexts, the one that a procedure sees may not be the one that the programmer intended, depending on where the procedure is called. With lexical scope, it is clear from the text of the program which variable is used.
Most Lisp users currently accept lexical scope as the best choice; Common Lisp, the other widely used dialect, has followed Schemes lead and adopted lexical scope. Two dialects of Lisp that continue to use dynamic scope are Elisp, the Emacs extension language, and Logo, a dialect used in education. Dynamic scope is arguably easier for a novice to understand. In some ways, it makes debugging easier, and there are situations in which a name capture is what the programmer wants. However, lexical scope is preferred for most applications, not only for the efficiency and correctness reasons mentioned, but for a third reason that applies only to a language such as Scheme in which procedures are first-class data. Ill come back to that point shortly.
Other innovations, based on recent research in programming languages, are original in Scheme itself. Two of these, first-class procedures and tail call elimination, are simplifying removals of restrictions that clearly demonstrate the power of Schemes approach to language design. The other two, first-class continuations and hygienic macros, are somewhat more arcane.
Previous | Table of Contents | Next |