Issue: EVAL-DEFEATS-LINKER

[Masinter.pa@Xerox.COM]

Date: 12 Jun 87 15:36:10 PDT (Fri)


Issue:        EVAL-DEFEATS-LINKER
References:   Functions (p32); FUNCTIONP (p76); APPLY (pp107-108);
              FUNCALL (p108); #. (pp355-356); #, (p356)
Category:     CHANGE
Edit history: 12-Jun-87, Version 1 by Clinger

Problem description:

It appears to be impossible to write a selective linker for Common Lisp
that is both reliable and effective.  The reason is that most programs
must call APPLY, FUNCALL, or READ, which potentially call SYMBOL-FUNCTION
or EVAL, which must be regarded as potential references to any standard
or user-defined Common Lisp procedure.  At a minimum, therefore, the
entire Common Lisp library gets linked into the deliverable application.

Proposal (EVAL-DEFEATS-LINKER:FLUSH-GRATUITOUS-EVALS):

Change the definition of the function type to exclude symbols and lists.
Change the definition of FUNCTIONP to be false of symbols and lists.
Change the definitions of APPLY and FUNCALL so it is an error to pass
them a symbol or a list as their first argument.

Functions such as MAPCAR that are defined by reference to the concept of
function or by reference to APPLY and FUNCALL would be affected by these
changes as well, but it would not be necessary to change their
written specification.

Remove the #. and #, dispatching macro characters from the standard reader
syntax.  Require the interpreter, compiler, and interactive loader to use
a reader syntax that has been extended by adding the #. and #, dispatching
macro characters.

Test Case:

The executable file for the following program is comparable in size to
a complete Common Lisp system.

    (DEFUN MAIN ()
      (PRINT (EVAL (READ))))

A selective linker should, however, be able to link the following program
into a relatively small executable file.

    (DEFUN MAIN ()
      (PRINT (APPLY (FOO) (READ))))

    (DEFUN FOO ()
      (LET ((BIAS (RANDOM 1000)))
        #'(LAMBDA (&REST ARGS) (+ BIAS (APPLY #'+ ARGS)))))

Currently selective linkers have difficulty with the preceding program
because they must also make programs like the following work, where FOO
"computes" an arbitrary function.  Under the proposal, the only ways
to compute an arbitrary function would be through explicit use of EVAL
or SYMBOL-FUNCTION et cetera.

    (DEFUN MAIN ()
      (PRINT (APPLY (FOO) (READ))))

    (DEFUN FOO () (READ))

Rationale:

Selective linking is essential for most industrial applications.  Symbols
and lambda expressions are regarded as functions for historical reasons
only.  The description of the #, dispatching macro character on p356
suggests that both #. and #, are intended for use in code, not in data
to be read by an application program.

Current practice:

Hardly any implementations of Common Lisp attempt to remove unnecessary
code from a deliverable application.  Those that do appear to ignore the
problems posed by the third test case, and are therefore unreliable.
That is, they are incorrect because they behave as though this proposal
has been adopted when it has not.

Adoption Cost:

Implementations do not actually have to change APPLY and FUNCALL, since
they would not have to signal an error when passed a symbol or list.
Implementations that rely on #. and #, in non-code data would suffer
a conversion cost, but it seems unlikely that any implementations do this.

Cost of non-adoption:

Selective linking will continue to be unavailable or unreliable.

Benefits:

The availability of reliable selective linkers will make Common Lisp suitable
for a much braoder range of applications.

Conversion Cost:

Programs for which reliable selective linking is unimportant (that is,
essentially all current Common Lisp programs) can be converted by
redefining APPLY and FUNCALL and by defining the #. and #, dispatching
character macros.  This will be referred to below as the trivial conversion.

Programs for which reliable selective linking is important, if any exist,
are presumably written in a style that needs no conversion.

To convert an existing program into a style that can be linked selectively,
it is necessary to examine all calls to APPLY, FUNCALL, MAPCAR, and other
functions that take functions as arguments.  Where the argument expression
is of the form (FUNCTION f), no conversion is necessary.  Where the first
argument is of the form (QUOTE f), it should be changed to (FUNCTION f).
Where the first argument is of neither of these two forms, human intervention
will be necessary.  It seems likely that most calls will have first arguments
of the form (FUNCTION f) or (QUOTE f), so this conversion can be automated
substantially but not completely.

As with all conversions, arguments to EVAL must be analyzed specially.
Since uses of EVAL generally defeat selective linking, however, it is
clear that programs that make extensive use of EVAL were not intended
to be passed through a selective linker.  Hence the trivial conversion
should suffice for such programs.

If the program reads data from files, then it may be necessary to scan the
files for occurrences of #. and #,.  If any occurrences are found, they
will have to be removed.  It seems clear, however, that no program intended
for selective linking will rely on #. and #, in data files.

Esthetics:

This proposal simplifies Common Lisp by removing weird special cases that
contribute to the language's reputation for inefficiency.

Discussion:

This is a good example of the practical importance of aesthetics in language
design.  The difficulties implementors face in writing a selective linker
for Common Lisp are inherent in the current language definition.  It is
better to fix the language than to postulate sufficiently clever linkers.

While this proposal will make it possible to construct selective linkers,
it will not make it trivial.  In many implementations, for example, the
data structure for each symbol contains among other things a pointer to
the symbol's home package, a value cell, and a function cell.  In such an
implementation each symbol may represent a potential reference to the value
cell of any symbol accessible from its home package.  Implementations that
care about selective linking may have to break such links.

Scheme proves that it is possible to design a Lisp that can be linked
selectively.  Reliable selective linkers have been written for T and for
MacScheme, and possibly for other implementations as well.