Forum:		Compiler
Issue:		COMPILE-ENVIRONMENT-CONSISTENCY
References:	CLtL p. 68-69, 143, 321
		RAM's "Compiler Cleanup Proposal #3"
Category:	CLARIFICATION
Edit History:   V1, 2 Sep 1988, Sandra Loosemore (initial draft)
		V2, 9 Sep 1988, Sandra Loosemore (incorporate suggestions)
		V3, 26 Oct 1988, Sandra Loosemore (add suggestion from Benson)
		V4, 08 Mar 1989, Sandra Loosemore (wording changes)
		V5, 22 Mar 1989, Sandra Loosemore (fix error language)
		V6, 15 Jun 1989, Sandra Loosemore (Bob Kerns's amendment)
Status		Proposal CLARIFY passed, June 89
		Recommendation to drafting committee:  under item 1, clarify
		that the information *does* need to be present at runtime if
		there are runtime calls to EVAL or COMPILE.


Problem Description:

CLtL does not clearly specify what aspects of the compiletime
environment the compiler (or other preprocessor) may "wire in" to code
being compiled.  At what time (compiletime or runtime) are certain
kinds of definitions "captured"?  What happens if these definitions
are not consistent at both compile and run times?


Proposal COMPILE-ENVIRONMENT-CONSISTENCY:CLARIFY:

The process of compilation causes certain kinds of information present
in the compiletime environment to be captured and incorporated into
the resulting compiled code.  Other kinds of information may not be
captured until the compiled code is actually run.  

Specifically:

(1) The following information *must* be present in the compiletime
environment for the program to be compiled correctly.  This
information need not also be present in the runtime environment.

    (a) In conforming code, macros referenced in the code being compiled
        must have been previously defined in the compiletime environment.
	The compiler must treat any form that is a list beginning with
	a symbol that does not name a macro or special form as a function
	call.  (This implies that SETF methods must also be available at
	compiletime.)

    (b) In conforming code, proclamations for SPECIAL variables must
        be made in the compiletime environment before any bindings of
        those variables are processed by the compiler.  The compiler
        must treat any binding of an undeclared variable as a lexical
        binding.

(2) The compiler *may* incorporate the following kinds of information
into the code it produces, if the information is present in the
compiletime environment and is referenced within the code being
compiled.  Except where some other behavior is explicitly stated, when
the compiletime and runtime definitions are different, it is
unspecified which will prevail within the compiled code.  It is also
permissible for implementations to signal an error at runtime to
complain about the discrepancy.  In all cases, the absence of the
information at compiletime is not an error, but its presence may
enable the compiler to generate more efficient code.

    (a) The compiler may assume that functions that are defined and
	declared INLINE in the compiletime environment will retain the
        same definitions at runtime.

    (b) The compiler may assume that, within a named function, a
	recursive call to a function of the same name refers to the
	same function, unless that function has been declared NOTINLINE.

    (c) COMPILE-FILE may assume that, in the absence of NOTINLINE
	declarations, a call within the file being compiled to a named
	function which is defined in that file refers to that function.
	(This permits "block compilation" of files.)  The behavior of
	the program is unspecified if functions are redefined individually 
	at runtime.

    (d) The compiler may assume that the signature (or "contract") of
	all built-in Common Lisp functions will not change.  In addition,
	the compiler may treat all built-in Common Lisp functions as if
	they had been proclaimed INLINE.

    (e) The compiler may assume that the signature (or "contract") of
	functions with FTYPE information available will not change.  (See
	issue FUNCTION-TYPE-ARGUMENT-TYPE-SEMANTICS.)

    (f) The compiler may "wire in" the values of symbolic constants
	that have been defined with DEFCONSTANT in the compiletime
	environment.

    (g) The compiler can assume that type definitions made with DEFTYPE 
        or DEFSTRUCT in the compiletime environment will retain the same 
        definition in the runtime environment.  It may also assume that
        a class defined by DEFCLASS in the compiletime environment will
        be defined in the runtime environment in such a way as to have
        the same superclasses and metaclass.  This implies that
        subtype/supertype relationships of type specifiers will not 
        change between compiletime and runtime.  (Note that it is not 
        an error for an	unknown type to appear in a declaration at
        compiletime, although it is reasonable for the compiler to 
        emit a warning in such a case.)

    (h) The compiler may assume that if type declarations are present
	in the compiletime environment, the corresponding variables and 
	functions present in the runtime environment will actually be of
	those types; otherwise, the runtime behavior of the program is 
	undefined.

(3) The compiler *must not* make any additional assumptions about
consistency between the compiletime and runtime environments.  In 
particular:

    (a) The compiler may not assume that functions that are defined
	in the compiletime environment will retain the either the
	same definition or the same signature at runtime, except
	in situations (2a) through (2e) above.

    (b) The compiler may not signal an error if it sees a call to a
	function that is not defined at compiletime, since that function
	may be provided at runtime.

Rationale:

  This proposal generally reflects current practice.


Proposal COMPILE-ENVIRONMENT-CONSISTENCY:BOBS-AMENDMENT:

This is the same as proposal CLARIFY, except all of item (2g) is replaced
with:

    (g) The compiler can assume that type definitions made with
        DEFTYPE or DEFSTRUCT in the compiletime environment will
        retain the same definition in the runtime environment.  This
        implies that subtype/supertype relationships of type specifiers
        defined by DEFTYPE or DEFSTRUCT will not change between
        compiletime and runtime.  (Note that it is not an error for an
        unknown type to appear in a declaration at compiletime,
        although it is reasonable for the compiler to emit a warning
        in such a case.)

Rationale:

  Users should be free to redefine classes between compile and 
  run time.


Current Practice:

There don't seem to be any compilers around that do not implement the
provisions of item (1).

For item (2), most compilers (including Lucid) optimize self-recursive
calls by default.  Most compilers also opencode data structure
accessors (such as CAR) at some level of optimization, and some code
much more complicated built-in functions inline as well.  VaxLisp, for
example, normally compiles MEMBER inline.  The Lucid compiler makes
use of type declarations to perform generic-to-specific
transformations on many arithmetic and sequence functions, which is
also a form of inlining.  KCL performs block compilation by default,
and Lucid does so under certain conditions.


Cost to implementors:

Unknown, but probably minor.


Cost to users:

Since most implementations appear to be largely in conformance with the
proposal, users should notice little difference.


Benefits:

The presence of a definite specification of what may happen when will
help users structure their programs so they will compile correctly in
all Common Lisp implementations.


Discussion:

Most of the discussion on this issue has been centered on the
terminology describing error situations for item (2).  In most cases
where there is an inconsistency between compile-time and run-time, the
results will be unpredictable but harmless.  The major exception is
violation of type declarations, which is a "crash-and-burn" error in
many implementations.

There has also been some concern raised that item (3) would prohibit
such things as a cross-compiler that produces standalone programs in
an environment that disallows redefinition of functions.  The intent
of this proposal is not to prohibit a compiler from having a magic
switch that imposes additional restrictions on the programs it
compiles, but such a compiler would not be a compiler for Common Lisp.

Several people have expressed reservations about items 2b and 2c, saying
that self-tail-recursion optimization and block compilation should not
be the default behavior of the compiler.  Gail Zacharias responds:

  This item [2c] has nothing to do with whether anybody does it by
  default.  The question is whether an end user can take a Common Lisp
  program whose internals he's not familiar with, block-compile it, and
  be guaranteed that it will continue to function correctly.  This item
  says that yes, a correct CL program must explicitly indicate what
  functions in the source it will redefine at runtime.  I don't think
  this places such a great burden on the programmer.  Without this
  provision, only somebody intimately familiar with a program could know
  whether it can be safely block-compiled, making block-compilation
  useless in the context of portable CL programs.
  
  This thing about "block compilation shouldn't be the default" seems to
  come up every time this item is discussed.  That's an environment
  question and is not addressed by the proposal.  The proposal simply
  says that block compilation should be legal.

Sandra Loosemore says:

  Proposal BOBS-AMENDMENT may lead to trouble because it implies
  restrictions on user programs as well as implementations, and there is
  no way for users to determine whether a type specifier involves a
  class name or class object.  An example of a user program that would
  be affected is a macro that calls SUBTYPEP in the process of computing
  its expansion.  While the results returned by SUBTYPEP will give the
  correct relationship between the type specifiers at the time the macro
  is expanded, this may well be wrong for the runtime environment if
  classes are allowed to move around in the type hierarchy in the
  meantime.

  It isn't even possible for users to definitely identify type specifiers
  that involve class names or class objects, because there is no user
  visible function in the language to expand DEFTYPE type specifiers.

  If we adopt proposal BOBS-AMENDMENT, I see three possible solutions:

     - we could simply document the problem in the standard, warning 
       users not to make assumptions about the permanence of SUBTYPEP 
       relationships without further analysis of the type specifiers
       involved.

     - we could add a TYPE-EXPAND function to expand type specifiers
       that have been defined with DEFTYPE, to aid users in performing
       their own analysis of type specifiers.

     - we could add a function similar to SUBTYPEP (or perhaps an optional
       argument to SUBTYPEP that would cause it to have this behavior),
       that would always return NIL NIL if any of the type specifiers
       involved are permitted to be redefined in a way that would change
       their position in the type hierarchy.

  There seems to be some general agreement that redefinability of classes
  is really a property of the metaclass, but that we can't say anything 
  more definite until the metaobject protocol is in a more finished state.

  I don't necessarily oppose BOBS-AMENDMENT, I just want to make sure that
  everyone knows exactly what they're voting for.