Issue COMPILED-FUNCTION-REQUIREMENTS Writeup

Forum:		Compiler

Issue:		COMPILED-FUNCTION-REQUIREMENTS

References:	CLtL p. 32, 76, 112, 143, 438-439

		Issue FUNCTION-TYPE (passed)

		Issue COMPILER-LET-CONFUSION (passed)

		Issue EVAL-WHEN-NON-TOP-LEVEL (passed)

		Issue LOAD-TIME-EVAL (passed)

		Issue COMPILE-ENVIRONMENT-CONSISTENCY

		Issue COMPILE-ARGUMENT-PROBLEMS (passed)

Category:	CLARIFICATION, CHANGE

Edit History:   V1, 3 Jan 1989 Sandra Loosemore

		V2, 10 Jan 1989, Sandra Loosemore (additional proposal)

		V3, 10 Feb 1989, Sandra Loosemore (new proposal)

		V4, 11 Mar 1989, Sandra Loosemore (fix wording to agree

			with other pending proposals)

		V5, 23 Mar 1989, Sandra Loosemore (restore proposal FLUSH)

		V6, 30 May 1989, Sandra Loosemore (fix proposal TIGHTEN to

			apply only to COMPILE-FILE)

		V7, 22 Jun 1989, Sandra Loosemore (restore FLUSH again)

		V8, 04 Jul 1989, Sandra Loosemore (amendments from meeting)

Status:		Proposal TIGHTEN passed, as amended, June 89



Problem Description:


There is confusion about what functions might be or must be of type

COMPILED-FUNCTION, and what attributes must be true of

COMPILED-FUNCTIONs.  Is the distinction between COMPILED-FUNCTIONs and

other functions only one of representation, or can user programs infer

anything about COMPILED-FUNCTIONs?  Are implementations required to

distinguish between compiled and non-compiled functions?


CLtL defines a COMPILED-FUNCTION as "a compiled code object".  (Issue

FUNCTION-TYPE says only that COMPILED-FUNCTION must be a subtype of

FUNCTION.)  Although it is not explicitly stated, CLtL implies that

compiled code must conform to certain rules; in particular, it states

that all macros are expanded at compile time, and specifies different

behavior for the COMPILER-LET and the EVAL-WHEN special forms

depending on whether they are interpreted or compiled.


The description of COMPILE in CLtL says that "a compiled-function object

[is] produced".  It is not clear to everyone whether this implies that

COMPILED-FUNCTION-P must be true of such functions.  CLtL says nothing

about whether functions defined in files compiled with COMPILE-FILE and

subsequently loaded must be of type COMPILED-FUNCTION.


There are two proposals, FLUSH and TIGHTEN.


Proposal TIGHTEN presents a simple model of the compilation process.  A

minimal compiler could be implemented to perform a code walk to apply

the indicated transformations to the function source code.  Of course,

most compilers will perform other transformations as well, such as

translating the Lisp source code into a representation that is more

compact or which can be executed more efficiently.


Proposal COMPILED-FUNCTION-REQUIREMENTS:FLUSH:


  (1) Remove the type specifier COMPILED-FUNCTION and the predicate

      COMPILED-FUNCTION-P from the language.

  

  (2) Remove the language from proposal COMPILE-ARGUMENT-PROBLEMS:CLARIFY

      that says "it is an error" to try to COMPILE a function that

      was defined interpretively in a non-null lexical environment.

      Instead, state that if COMPILE cannot compile the function,

      it should simply behave as an identity operation.


  Rationale:


    Some people think the wording of proposal TIGHTEN is too vague and

    does not provide an adequate definition of what COMPILED-FUNCTIONs

    are.  Some people think that since proposal TIGHTEN does not require

    COMPILE to produce a COMPILED-FUNCTION, its specification is too 

    weak to be of much use to users.


    Since we are unable to reach concensus on what a COMPILED-FUNCTION

    really is, or how to construct one, it seems better to remove it

    from the language entirely.

  


Proposal COMPILED-FUNCTION-REQUIREMENTS:TIGHTEN:


  (1) Clarify that if a function is of type COMPILED-FUNCTION, the

      following are guaranteed about the function:

  

      - All macro calls appearing lexically within the function have 

        already been expanded and will not be expanded again when the

        function is called.  (See CLtL p. 143.)  The process of

        compilation effectively turns MACROLET and SYMBOL-MACROLET

        constructs into PROGNs with all instances of the local macros

        in the body fully expanded.

  

      - If the function contains lexically nested LOAD-TIME-VALUE forms,

        these have already been pre-evaluated and will not be evaluated

        again when the function is called.

  

  (2) Implementations are free to classify all functions as 

      COMPILED-FUNCTIONs, provided that all functions satisfy the criteria

      listed in item (1).  It is also permissible for functions that are

      not COMPILED-FUNCTIONs to satisfy the above criteria.

  

  (3) Clarify when functions are defined in a file which is compiled

      with COMPILE-FILE, and the compiled file is subsequently LOADed,

      objects of type COMPILED-FUNCTION result.

  

  (4) Clarify that COMPILE must produce an object of type

      COMPILED-FUNCTION.

  

  

  Rationale:

  

  This proposal allows users to count on both COMPILE and COMPILE-FILE 

  always producing objects that are COMPILED-FUNCTION-P.

  

  Some specific properties are assigned to compiled functions.  Users

  would be able to rely on any function which is of type

  COMPILED-FUNCTION having really been (at least partially) compiled.

  

  It also states what many people believe to be the minimum functionality 

  required of a compiler.

  

   

Current Practice:

 

It appears that most implementations currently distinguish compiled

versus non-compiled functions on the basis of representation.  It seems

unlikely that any implementation would have problems satisfying the

stated minimum requirements for compilation.

  

Lucid uses the same representation for both compiled and non-compiled

functions, except there is a bit in the header used to distinguish them.


A-Lisp uses the same representation for both compiled and interpreted

functions and currently labels them both as COMPILED-FUNCTION, but the

implementation of COMPILED-FUNCTION-P could be easily fixed to

distinguish "real" compiled functions.


On the TI Explorer, the COMPILE function can return an object of

either type COMPILED-FUNCTION or LEXICAL-CLOSURE, where the latter

consists of two components -- an environment and a COMPILED-FUNCTION.

There is confusion about whether microcoded functions should be

considered compiled or not.


In Utah Common Lisp, COMPILED-FUNCTION-P currently returns true of all

function objects, but there is an internal tag field in the object

which allows real compiled functions to be distinguished from

interpreted functions.



Cost to implementors:


Unknown, but probably not too great.  Many implementations will

probably have to make some minor changes to representation of

functions and/or to the definition of COMPILED-FUNCTION-P, but

probably most of those changes are necessary to support the

FUNCTION-TYPE proposal anyway.



Cost to users:


Probably minimal.  Since the COMPILED-FUNCTION type specifier is

currently ill-defined, it is hard to imagine that existing programs

can portably rely on any interpretation of what it means that is

inconsistent with what is presented here.



Benefits:


The specification of what the compiler must do is made more explicit.



Discussion:


This writeup originally contained an additional proposal,

TIGHTEN-COMPILE.  A straw vote at the March 1989 meeting indicated

that an earlier version of proposal TIGHTEN had the most support.

However, a number of people still have a strong preference for

proposal FLUSH.  


Recent mail on the cl-compiler list has indicated that Moon, Loosemore

and MacLachlan favor flushing COMPILED-FUNCTION; White and Burke have

no objection to doing so; and that Pitman would like to see the type

retained with both COMPILE and COMPILE-FILE required to produce

compiled functions.  Nobody has explicitly stated a preference for

proposal TIGHTEN in this round of discussion.


Loosemore would also prefer to see the type retained, but thinks that

since we have been unable to reach a consensus on what the

compiled-function type means or how to construct an object of this

type, we are much better off not saying anything about it at all in

the standard, than standardizing a definition that is too vague to

be of any use to users, or that some people believe is wrong.


The FIXNUM and BIGNUM types were also defined in CLtL solely on the

basis of distinguished representations, and that this definition has

proved inadequate for just about all portable usages of these type

specifiers.  Defining COMPILED-FUNCTION solely on the basis of

distinguished representation seems like a bad idea.


David Gray notes:

  We make good use of the type COMPILED-FUNCTION in our implementation,

  but all of the accessor functions for objects of that type are

  non-standard, which makes me wonder if it might be best to just remove

  this type from the standard along with BIGNUM.


One use of the COMPILED-FUNCTION type is in declarations.  A-Lisp and

Lucid, for example, can compile FUNCALL more efficiently if it can be

determined that the function is of type COMPILED-FUNCTION.  However,

in order for such declarations to be really useful, there should be a

way to construct an object which is guaranteed to be of type

COMPILED-FUNCTION.


Moon says:

  I much prefer the option FLUSH...

  This type has no portable meaning and never should have existed.


Pierson says:

  What I (and believe Kent) want is a guarantee that [COMPILE] won't

  signal an error; if nothing else works COMPILE will simply apply

  #'IDENTITY to the symbol's function.  Specifically, it should be

  legal and safe to attempt to speed up my current program(s) by

  doing:


    (DO-SYMBOLS (SYM <my-package>)

    	(WHEN (FBOUNDP SYM) (COMPILE SYM)))