Sketchy LISP

An Introduction to Functional Programming in Scheme

2 Less Basic Scheme Programming

2.1 Variable Argument Procedures

Many languages provide a means of defining procedures that take a variable number of arguments, and Scheme is among them. Normally each variable is bound to one argument during a procedure call. For example, the following max procedure takes two arguments and returns the greater one of them:

(define (max a b)
  (if (> a b) a b))

When max is called, its argument a is bound to the first argument and b is bound to its second argument:

(max 34 43)
-> (if (> 34 43) 34 43)

However, the real max procedure of Scheme is a variadic procedure, which means that it accepts any positive number of arguments:

(max 5 1 3 8 9 7 2 6 4) => 9

In the previous section, the max-list procedure was defined. This procedure extracted the greatest member from a list of values. It had to be called with a single argument which was a list of the numbers to process:

(max-list '(5 1 3 8 9 7 2 6 4)) => 9

So the algorithm is already there. The only problem left is to stop Scheme from decomposing the list of arguments when calling a procedure. This is where improper lists come into play. A procedure with an improper argument list takes any number of arguments, but at least as many as it has variables before the dot. Here is an example:

(define (fv2 a b . c) c)

This procedure accepts at least two arguments. Its first argument will be bound to a and the second one to b. The list of remaining arguments will be bound to c:

(fv2 'foo 'bar 'baz)    => (baz)
(fv2 'a 'b 'c 'd 'e 'f) => (c d e f)

If the procedure has exactly two members, the empty list is bound to c:

(fv2 'a 'b) => ()

Passing any smaller number of arguments to fv2 results in an error:

(fv2 'a) => bottom
(fv2) => bottom

The max procedure should expect at least one member, because applying max to zero members would not make any sense. Here is a procedure that can be wrapped around max-list in order to create a max procedure taking a variable number of arguments but at least one:

(define (max x . a)
  (max-list (cons x a)))

The x before the dot makes Scheme report an error when less than one argument is passed to max. However, the x has to be consed to the list holding the rest of arguments before passing the list to max-list. This could be avoided by making max accept zero or more arguments. In this case, though, the max procedure itself would have to make sure that at least one argument was passed to it:

(define (max . a)
  (if (null? a)
      (bottom "max requires at least one argument")
      (max-list a)))

This definition has no symbols between the procedure name and the dot of the argument list, so it binds the entire list of arguments to a without doing any decomposition. When zero arguments are passed to this version of max, the bottom procedure is used to abort the computation and report an error.

Note that the bottom procedure does not really exist in Scheme. Because it does not exist, Scheme will print an error message and abort the current computation when it encounters an application of bottom, which is exactly what bottom is intended to do. If your Scheme system offers a (non-standard) procedure like error or wrong, you may prefer to use it in the place of bottom.

Because (non-primitive) procedures are created using lambda, there must be a way to create variadic lambda functions, too. Indeed this is possible:

((lambda (a . b) b) 'foo 'bar) => (bar)
((lambda (a . b) b) 'a 'b 'c)  => (b c)
((lambda (a . b) b) 'foo)      => ()

Using lambda, procedures that are local to a letrec can be made variadic, too. It is even possible to create procedures accepting zero or more arguments using lambda. A pair obviously cannot be used to achieve this, because a pair with no car part would not be a pair. So how does it work? Decomposing the signatures of some procedures gives the answer. The signature of a procedure is a list containing the name and the variables of a procedure, as in

(define (f2 a b . c) c)

The cdr part of a signature is the argument list of a procedure, e.g.:

; Definition           Signature    Arguments
(define (f x) y)       (f x)        (x)
(define (f x . y) y)   (f x . y)    (x . y)
(define (f . x) x)     (f . x)      x

So the argument list of a variadic procedure with zero or more arguments is not a list at all, but a single variable. This variable will be associated with the entire list of arguments when the procedure is called:

((lambda x x) 'a 'b 'c) => (a b c)
((lambda x x) 'foo)     => (foo)
((lambda x x))          => ()

BTW: (Lambda x x) happens to be the code of a very useful Scheme procedure named list. All it does is to evaluate to the list of arguments passed to it. Because Scheme evaluates arguments before passing them to procedures, the resulting list will be a list of normal forms, which is different from specifying a literal list:

    '((+ 5 7) (* 3 4)) => ((+ 5 7) (* 3 4))
(list (+ 5 7) (* 3 4)) => (12 12)

Because variadic arguments are passed as lists, they cannot simply be passed to other variadic procedures. For example, the following attempt ro write a procedure that extracts the limits of a list (its least and its greatest member) fails:

((lambda a (list (min a) (max a))) x) => bottom

This expression reduces to bottom for any value of x, because a list is passed to min and to max while both of these procedures expect numbers as their arguments. If min and max were two-argument procedures, this would be simple:

(lambda a
  (list (min (car a) (cadr a))
        (max (car a) (cadr a))))

This approach decomposes the variable argument list using car and cadr and then passes the extracted arguments to min and max. This method works only if the number of arguments is known in advance, though.

The program would be much nicer and simpler, if the variable argument list itself could just be passed to min and max. This is the point where the apply procedure comes into play:

(define (limits . a)
  (list (apply min a)
        (apply max a)))

(Apply f a) applies a procedure f to a list of arguments a:

(apply f '(1 2 3)) -> (f 1 2 3)

Of course the number of members of the list must match the number of arguments that the procedure expects:

(apply cons '(a)) -> (cons 'a) => bottom

Apply is an ordinary procedure. Its arguments are passed to it using call by value. A procedure is called by value, if all arguments of that procedure are evaluated before they are passed to the procedure. In Scheme all procedures are called by value. Pseudo functions, on the other hand, are applied by name. Passing arguments to a function using call by name means that the arguments are not evaluated before they are passed to the function. For example, quote is called by name:

(quote (+ 2 3)) => (+ 2 3)

while the list procedure is called by value:

(list (+ 2 3)) => (5)

(Apply f a) receives its arguments by value, but applies f to the members of a using call by name:

(apply cons '(a b))
-> (cons a b)
=> (a . b)

If (apply f a) would pass the members of a using call by value, they would be evaluated twice: once when calling apply and another time when applying f. In the above example this would mean that the values of a and b would be passed to cond, resulting in bottom if a or b was unbound. If you actually wanted to pass the values of some variables a, b, and c to a procedure using apply, you would use list:

(apply + (list a b c))

but then again, this would be equivalent to using the procedure being applied directly:

(apply + (list a b c))  =  (+ a b c)

BTW: The compose procedure introduced earlier in this book can be improved by using apply, too. The version introduced earlier can only compose unary procedures (procedures of one argument). The improved version accepts a procedure of any arity (any number of arguments) in the last position:

(define (compose f g)
  (lambda x (f (apply g x))))