2.6. Top-Level Definitions

The variables bound by let and lambda expressions are not visible outside the bodies of these expressions. Suppose you have created an object, perhaps a procedure, that must be accessible anywhere, like + or cons. What you need is a top-level definition, which may be established with define. Top-level definitions are visible in every expression you enter, except where shadowed by another binding.

Let's establish a top-level definition of the double-any procedure of the last section.

 (define double-any   (lambda (f x)     (f x x)))

The variable double-any now has the same status as cons or the name of any other primitive procedure. We can use double-any as if it were a primitive procedure.

 (double-any + 10) ⇒ 20 (double-any cons 'a) ⇒ (a . a)

A top-level definition may be established for any object, not just for procedures.

 (define sandwich "peanut-butter-and-jelly") sandwich ⇒ "peanut-butter-and-jelly"

Most often, though, top-level definitions are used for procedures.

As suggested above, top-level definitions may be shadowed by let or lambda bindings.

 (define xyz '(x y z)) (let ((xyz '(z y x)))   xyz) ⇒ (z y x)

Variables with top-level definitions act almost as if they were bound by a let expression enclosing all of the expressions you type.

Given only the simple tools you have read about up to this point, it is already possible to define some of the primitive procedures provided by Scheme and described later in this book. If you completed the exercises from the last section, you should already know how to define list.

 (define list (lambda x x))

Also, Scheme provides the abbreviations cadr and cddr for the compositions of car with cdr and cdr with cdr. That is, (cadr list) is equivalent to (car (cdr list)), and, similarly, (cddr list) is equivalent to (cdr (cdr list)). They are easily defined as follows.

 (define cadr   (lambda (x)     (car (cdr x)))) (define cddr   (lambda (x)     (cdr (cdr x)))) (cadr '(a b c)) ⇒ b (cddr '(a b c)) ⇒ (c)

Any definition (define var exp) where exp is a lambda expression can be written in a shorter form that suppresses the lambda. The exact syntax depends upon the format of the lambda expression's formal parameter specifier, i.e., whether it is a proper list of variables, a single variable, or an improper list of variables. A definition of the form

 (define var₀   (lambda (var₁ ... var_n)     e₁ e₂ ...))

may be abbreviated

 (define (var₀ var₁ ... var_n)   e₁ e₂ ...)

while

 (define var₀   (lambda var_r     e₁ e₂ ...))

may be abbreviated

 (define (var₀ . var_r)   e₁ e₂ ...)

and

 (define var₀   (lambda (var₁ ... var_n . var_r)     e₁ e₂ ...))

may be abbreviated

 (define (var₀ var₁ ... var_n . var_r)   e₁ e₂ ...)

For example, the definitions of cadr and list may be written as follows.

 (define (cadr x)   (car (cdr x))) (define (list . x) x)

This book does not often employ this alternative syntax. Although it is shorter, it tends to mask the reality that procedures are not intimately tied to variables, or names, as they are in many other languages. This syntax is often referred to, somewhat pejoratively, as the "defun" syntax for define, after the defun form provided by Lisp languages in which procedures are more closely tied to their names.

Top-level definitions make it easier for us to experiment with a procedure interactively because we need not retype the procedure each time it is used. Let's try defining a somewhat more complicated variation of double-any, one that turns an "ordinary" two-argument procedure into a "doubling" one-argument procedure.

 (define doubler   (lambda (f)     (lambda (x) (f x x))))

doubler accepts one argument, f, which must be a procedure that accepts two arguments. The procedure returned by doubler accepts one argument, which it uses for both arguments in an application of f. We can define, with doubler, the simple double and double-cons procedures of the last section.

 (define double (doubler +)) (double 13/2) ⇒ 13 (define double-cons (doubler cons)) (double-cons 'a) ⇒ (a . a)

We can also define double-any with doubler.

 (define double-any   (lambda (f x)     ((doubler f) x)))

Within double and double-cons, f has the appropriate value, i.e., + or cons, even though the procedures are clearly applied outside the scope of f.

What happens if you attempt to use a variable that is not bound by a let or lambda expression and that does not have a top-level definition? Try using the variable i-am-not-defined to see what happens.

 (i-am-not-defined 3)

Most Scheme systems print an error message to inform you that the variable is unbound or undefined.

The system will not complain about the appearance of an undefined variable within a lambda expression, until and unless the resulting procedure is applied. The following should not cause an error, even though we have not yet established a top-level definition of proc2.

 (define proc1   (lambda (x y)     (proc2 y x)))

If you try to apply proc1 before defining proc2, you should get an error message. Let's give proc2 a top-level definition and try proc1.

 (define proc2 cons) (proc1 'a 'b) ⇒ (b . a)

When you define proc1, the system accepts your promise to define proc2, and does not complain unless you use proc1 before defining proc2. This allows you to define procedures in any order you please. This is especially useful when you are trying to organize a file full of procedure definitions in a way that makes your program more readable. It is necessary when two procedures defined at top level depend upon each other; we will see some examples of this later.

Exercise 2.6.1.

What would happen if you were to type

 (double-any double-any double-any)

given the definition of double-any from the beginning of this section?

Exercise 2.6.2.

A more elegant (though possibly less efficient) way to define cadr and cddr than given in this section is to define a procedure that composes two procedures to create a third. Write the procedure compose, such that (compose p₁ p₂) is the composition of p₁ and p₂ (assuming both take one argument). That is, (compose p₁ p₂) should return a new procedure of one argument that applies p₁ to the result of applying p₂ to the argument. Use compose to define cadr and cddr.

Exercise 2.6.3.

Scheme also provides caar, cdar, caaar, caadr, and so on, with any combination of up to four a's (representing car) and d's (representing cdr) between the c and the r (see Section 6.3). Define each of these with the compose procedure of the preceding exercise.