Issue SYNTACTIC-ENVIRONMENT-ACCESS Writeup

Forum:          Compiler

Issue:          SYNTACTIC-ENVIRONMENT-ACCESS

References:     CLtL Chapter 8: Macros,

                CLtL Chapter 9: Declarations,

                Issue COMPILE-FILE-ENVIRONMENT,

                Issue DEFINING-MACROS-NON-TOP-LEVEL,

                Issue DESTRUCTURING-BIND,

                Issue EVAL-WHEN-NON-TOP-LEVEL,

                Issue GET-SETF-METHOD-ENVIRONMENT,

                Issue FUNCTION-NAME,

                Issue FUNCTION-TYPE,

                Issue MACRO-ENVIRONMENT-EXTENT,

                Issue MACRO-FUNCTION-ENVIRONMENT,

                Issue PROCLAIM-LEXICAL,

		Issue PACKAGE-CLUTTER

Category:       ADDITION

Edit history:   Version 1, 2-Oct-88, Eric Benson

                Version 2, 17-Feb-89, Kim A. Barrett

                Version 3, 9-Mar-89, Kim A. Barrett (respond to comments)

                Version 4, 12-Mar-89, Sandra Loosemore (more revisions)

                Version 5, 20-Mar-89, Sandra Loosemore (only proposal SMALL)

                Version 6, 23-Mar-89, Sandra Loosemore (more revisions)

                Version 7,  7-Apr-89, Moon & Barrett (more revisions)

                Version 8,  9-Jun-89, Kim A. Barrett (add DEFDECLARE)

                Version 9, 13-Jun-89, Moon (small corrections)

		Version 10, 22-Jun-89, Loosemore (more clarifications,

			primarily relating to DEFDECLARE)

		Version 11, 04-Jul-89, Loosemore (amendments from June mtg)


Status:         Proposal SMALL passed June 89



Problem description:


 When macro forms are expanded, the expansion function is called with two

 arguments: the form to be expanded, and the environment in which the form was

 found.  The environment argument is of limited utility.  The only use

 sanctioned currently is as an argument to MACROEXPAND or MACROEXPAND-1 or

 passed directly as an argument to another macro expansion function.  Recently

 passed cleanup issues allow it as an argument to MACRO-FUNCTION and to

 GET-SETF-METHOD.


 It is very difficult to write a code walker that can correctly handle local

 macro and function definitions, due to insufficient access to the information

 contained in environments and the inability to augment environments with local

 definitions.



Proposal (SYNTACTIC-ENVIRONMENT-ACCESS:SMALL):


 The following functions provide information about syntactic environment

 objects.  In all of these functions the argument named ENV is an environment

 of the sort received by the &ENVIRONMENT argument to a macro or as the

 environment argument for EVALHOOK.  (It is not required that implementations

 provide a distinguished representation for such objects.)  Optional "env"

 arguments default to NIL, which represents the local null lexical environment

 (containing only global definitions and proclamations that are present in the

 runtime environment).  All of these functions should signal an error of type

 TYPE-ERROR if the value of an environment argument is not a syntactic

 environment.


 The accessors VARIABLE-INFORMATION, FUNCTION-INFORMATION, and

 DECLARATION-INFORMATION retrieve information about declarations that are in

 effect in the environment.  Since implementations are permitted to ignore

 declarations (except for SPECIAL declarations and OPTIMIZE SAFETY

 declarations if they ever compile unsafe code), these accessors are required

 only to return information about declarations that were explicitly added to

 the environment using AUGMENT-ENVIRONMENT.  They might also return

 information about declarations recognized and added to the environment by the

 interpreter or the compiler, but that is optional at the discretion of the

 implementer.  Implementations are also permitted to canonicalize

 declarations, so the information returned by the accessors might not be

 identical to the information that was passed to AUGMENT-ENVIRONMENT.


 VARIABLE-INFORMATION variable &optional env            [Function]


  This function returns information about the interpretation of the symbol

  VARIABLE when it appears as a variable within the lexical environment ENV.

  The following three values are returned.


  The first value indicates the type of definition or binding which is apparent

  in ENV:


    NIL            There is no apparent definition or binding for variable.


    :SPECIAL       VARIABLE refers to a special variable, either declared 

                   or proclaimed. 


    :LEXICAL       VARIABLE refers to a lexical variable.


    :SYMBOL-MACRO  VARIABLE refers to a SYMBOL-MACROLET binding.


    :CONSTANT      VARIABLE refers to a named constant, defined by

                   DEFCONSTANT, or VARIABLE is a keyword symbol.


 [Note: If issue PROCLAIM-LEXICAL passes, then the :LEXICAL result will also

  refer to variables proclaimed lexical.]


  The second value indicates whether there is a local binding of the name.  If

  the name is locally bound, the second value is true.  Otherwise, NIL is

  returned.


  The third value is an a-list containing information about declarations

  that apply to the apparent binding of the variable.  The keys in the a-list

  are symbols which name declaration-specifiers, and the format of the

  corresponding value in the CDR of each pair depends on the particular 

  declaration name involved.  The standard declaration names

  that might appear as keys in this a-list are:


    DYNAMIC-EXTENT a non-NIL value indicates that the variable has been

                declared DYNAMIC-EXTENT. If the value is NIL, the pair

                might be omitted.


    IGNORE      a non-NIL value indicates that the variable has been declared

                IGNORE. If the value is NIL, the pair might be omitted.


    TYPE        a type specifier associated with the variable by a TYPE

                declaration or an abbreviated declaration such as (FIXNUM VAR).

                If no explicit association exists, either by PROCLAIM or

                DECLARE, then the type specifier is T.  It is permissible for

                implementations to use a type specifier that is equivalent

                to or a supertype of the one appearing in the original

                declaration.  If the value is T, the pair might be

                omitted.


  If an implementation supports additional declaration-specifiers that

  apply to variable bindings, those declaration names might also

  appear in the a-list.  However, the corresponding key must not

  be a symbol that is external in any package defined in the standard

  or that is otherwise accessible in the USER package.


  The a-list might contain multiple entries for a given key.

  The consequences of destructively modifying the list

  structure of this a-list or its elements (except for values that 

  appear in the a-list as a result of DEFINE-DECLARATION) are undefined.


  Programmers are reminded that the global binding might differ from the

  local one, and can be retrieved by calling VARIABLE-INFORMATION

  again with a null lexical environment.



 FUNCTION-INFORMATION function &optional env            [Function]


  This function returns information about the interpretation of the function

  name FUNCTION when it appears in a functional position within lexical 

  environment ENV.  The following three values are returned.


  The first value indicates the type of definition or binding of the function

  name which is apparent in ENV:


    NIL            There is no apparent definition for FUNCTION.


    :FUNCTION      FUNCTION refers to a function.


    :MACRO         FUNCTION refers to a macro.


    :SPECIAL-FORM  FUNCTION refers to a special form.


  Some function names can refer to both a global macro and a global special

  form.  In such a case, the macro takes precedence, and :MACRO is returned as

  the first value.


  The second value specifies whether the definition is local or global.  If

  local, the second value is true, and it is false when the definition is

  global.


  The third value is an a-list containing information about declarations

  that apply to the apparent binding of the function.  The keys in the a-list

  are symbols which name declaration-specifiers, and the format of the

  corresponding values in the CDR of each pair depends on the particular 

  declaration name involved.  The standard declaration names

  that might appear as keys in this a-list are:


    INLINE      one of the symbols INLINE, NOTINLINE, or NIL to indicate

                whether the function name has been declared INLINE, has been

                declared NOTINLINE, or neither.  If the value is NIL, the

                pair might be omitted.


    FTYPE       the type specifier associated with the function name in the

                environment, or the symbol FUNCTION if there is no functional

                type declaration or proclamation associated with the function

                name.  This value might not include all the apparent FTYPE

                declarations for the function name.  It is permissible for

                implementations to use a type specifier that is equivalent

                to or a supertype of the one that appeared in the original

                declaration.  If the value is FUNCTION, the pair might be

                omitted. 


    DYNAMIC-EXTENT  a non-NIL value indicates that the function has been

                declared DYNAMIC-EXTENT.  If the value is NIL, thie pair

                might be omitted.


  If an implementation supports additional declaration-specifiers that

  apply to function bindings, those declaration names might also

  appear in the a-list.  However, the corresponding key must not be

  a symbol that is external in any package defined in the standard or

  that is otherwise accessible in the USER package.


  The a-list might contain multiple entries for a given key.

  In this case the value associated with the first entry has

  precedence.  The consequences of destructively modifying the list

  structure of this a-list or its elements (except for values

  that appear in the a-list as a result of DEFINE-DECLARATION) are 

  undefined.


  Programmers are reminded that the global binding might differ from the local

  one, and can be retrieved by calling FUNCTION-INFORMATION again with a null

  lexical environment.



 DECLARATION-INFORMATION decl-name &optional env        [Function]


  This function returns information about declarations named by the

  symbol DECL-NAME that are in force in the environment ENV.

  Only declarations that do not apply to function or variable bindings

  can be accessed with this function.  The format of the information

  that is returned depends on the DECL-NAME involved.


  It is required that this function recognize OPTIMIZE and DECLARATION as

  DECL-NAMEs.  The values returned for these two cases are as follows:


    OPTIMIZE    a list whose entries are of the form (quality value), where

                "quality" is one of the optimization qualities defined by the

                standard (SPEED, SAFETY, COMPILATION-SPEED, SPACE, and DEBUG)

                or some implementation-specific optimization quality, and

                "value" is an integer in the range 0 to 3.  The returned list

                always contains an entry for each of the standard qualities and

                for each of the implementation-specific qualities.  In the

                absence of any previous declarations, the associated values are

                implementation-dependent.  The list might contain multiple

                entries for a quality, in which case the first such entry

                specifies the current value.

                The consequences of destructively modifying this list or

		its elements are undefined.

                


    DECLARATION a list of the declaration names which have been proclaimed as

                valid through the use of the DECLARATION proclamation.

                The consequences of destructively modifying this list or

		its elements are undefined.


  If an implementation has been extended to recognize additional

  declaration specifiers in DECLARE or PROCLAIM, it is required that

  either the DECLARATION-INFORMATION function should also recognize those

  declarations, or that the implementation provide an accessor that is

  specialized for that declaration specifier.  If DECLARATION-INFORMATION

  is used to return the information, the corresponding DECL-NAME must not

  be a symbol that is external in any package defined in the standard or

  that is otherwise accessible in the USER package.



 AUGMENT-ENVIRONMENT env &KEY variable

                              symbol-macro

                              function

                              macro

                              declare                           [Function]


  This function returns a new environment containing the information present in

  ENV, augmented with the information provided by the keyword arguments.  It is

  intended to be used by program analyzers that perform a code walk.


  The arguments are supplied as follows:


  :VARIABLE     A list of symbols which shall be visible as bound variables in

                the new environment.  Whether each binding is to be interpreted

                as special or lexical depends on SPECIAL declarations recorded

                in the environment or provided in the :DECLARE argument list.


  :SYMBOL-MACRO A list of symbol macro definitions, specified as a list of

                (name definition) lists (that is, in the same format as the

                CADR of a SYMBOL-MACROLET special form).  The new environment

                will have local symbol-macro bindings of each symbol to the

                corresponding expansion, so that MACROEXPAND will be able to

                expand them properly.  A type declaration in the :DECLARE

                argument which refers to a name in this list implicitly

                modifies the definition associated with the name.  The effect

                is to wrap a THE form mentioning the type around the

                definition.


  :FUNCTION     A list of function names which shall be visible as local

                function bindings in the new environment.


  :MACRO        A list of local macro definitions, specified as a list of (name

                definition) lists.  Each definition must be a function of two

                arguments (a form and an environment).  The new environment

                will have local macro bindings of each name to the

                corresponding expander function, which will be returned by

                MACRO-FUNCTION and used by MACROEXPAND.


  :DECLARE      A list of decl-specs.  Information about these declarations can

                be retrieved from the resulting environment using the

                VARIABLE-INFORMATION, FUNCTION-INFORMATION, and

                DECLARATION-INFORMATION accessors.


  An error is signalled if any of the symbols naming macros in the

  :SYMBOL-MACRO alist are also included in the :VARIABLE list.  An error is

  signaled if any of the symbols naming macros in the :SYMBOL-MACRO alist are

  also included in a SPECIAL decl-spec in the :DECLARE argument.  An error is

  signalled if any of the names of macros in the :MACRO alist are also included

  in the :FUNCTION list.  The consequences of destructively modifying the list

  structure of any of the arguments to this function are undefined.


  The condition type of each of these errors is PROGRAM-ERROR.


  The extent of the returned environment is the same as the extent of the

  argument environment.  The result might share structure with the argument

  environment, but the argument environment is not modified.


  While an environment argument from EVALHOOK is permitted to be used as the

  environment argument for this function, the reverse is not true.  If an

  attempt is made to use the result of AUGMENT-ENVIRONMENT as the environment

  argument for EVALHOOK, the consequences are undefined.  The environment

  returned by AUGMENT-ENVIRONMENT can only be used for syntactic analysis, ie.

  the functions specified by this proposal and functions such as MACROEXPAND.



 DEFINE-DECLARATION decl-name lambda-list &body body               [Macro]


  Define a handler for the named declaration.  This is the mechanism by which

  AUGMENT-ENVIRONMENT is extended to support additional declaration

  specifiers.  The function defined by this macro will be called with two

  arguments, a decl-spec whose CAR is decl-name, and the ENV argument to

  AUGMENT-ENVIRONMENT.  Two values must be returned by the function.  The

  first value must be one of the following keywords:


  :VARIABLE     the declaration applies to variable bindings.

  :FUNCTION     the declaration applies to function bindings.

  :DECLARE      the declaration does not apply to bindings.


  For the case where the first value indicates the declaration applies to

  bindings, the second value is a list, the elements of which are lists of the

  form (binding-name key value).  If the corresponding information

  function (either VARIABLE-INFORMATION or FUNCTION-INFORMATION) is applied to

  the binding name and the augmented environment, the a-list which is

  the third value returned by the information function will contain the value

  under the specified key.


  When the first value is :DECLARE, the second value is a cons whose CAR is a

  key and whose CDR is the associated value.  The function

  DECLARATION-INFORMATION, when applied to the key and the augmented

  environment, will return the associated value.


  DEFINE-DECLARATION causes DECL-NAME to be proclaimed to be a

  declaration (it is as if its expansion included a call (PROCLAIM

  '(DECLARATION decl-name))).  As is the case with standard

  declaration specifiers, the evaluator and compiler are permitted,

  but not required, to add information about declaration specifiers

  defined with DEFINE-DECLARATION to the macroexpansion and evalhook

  environments.


  The consequences are undefined if DECL-NAME is a symbol which can

  appear as the CAR of any declaration specifier defined in the standard.


  The consequences are also undefined if the return value from a 

  declaration handler defined with DEFINE-DECLARATION includes a key name

  that is used by the corresponding accessor to return information about

  any declaration specifier defined in the standard.  (For example, if

  the first return value from the handler is :VARIABLE, the second return

  value may not use the symbols DYNAMIC-EXTENT, IGNORE, or TYPE as key

  names.)


  The DEFINE-DECLARATION macro does not have any special compile-time

  side-effects.



 PARSE-MACRO name lambda-list body &optional env        [Function]


  This function is used to process a macro definition in the same way

  as DEFMACRO and MACROLET.  It returns a lambda-expression that accepts

  two arguments (a form and an environment).  The "name", "lambda-list",

  and "body" arguments correspond to the parts of a DEFMACRO or MACROLET

  definition.


  The "lambda-list" argument can include &ENVIRONMENT and &WHOLE.  The "name"

  argument is used to enclose the "body" in an implicit BLOCK, and might also

  be used for implementation-dependent purposes (such as including the name of

  the macro in error messages if the form does not match the lambda-list).



 ENCLOSE lambda-expression &optional env                [Function]


  This function returns an object of type FUNCTION that is equivalent to what

  would be obtained by evaluating `(FUNCTION ,LAMBDA-EXPRESSION) in syntactic

  environment ENV.  The LAMBDA-EXPRESSION is permitted to reference only the

  parts of the environment argument ENV that are relevant only to syntactic

  processing, specifically declarations and the definitions of macros and

  symbol-macros.  The consequences are undefined if the LAMBDA-EXPRESSION

  contains any references to variable or function bindings that are 

  lexically visible in ENV; any GO to a tag that is lexicaly visible in 

  the environment ENV; or any RETURN-FROM a block name that is lexically 

  visible in the environment ENV.



Rationale:


  This proposal defines a minimal set of accessors (VARIABLE-INFORMATION,

  FUNCTION-INFORMATION, and DECLARATION-INFORMATION) and a constructor

  (AUGMENT-ENVIRONMENT) for environments.


  All of the standard declaration specifiers, with the exception of SPECIAL,

  can be defined fairly easily using DEFINE-DECLARATION.  It also

  seems to be able to handle most extended declarations.


  The PARSE-MACRO function is provided so that users don't have to write their

  own code to destructure macro arguments.  With the addition of

  DESTRUCTURING-BIND to the language, this function is not entirely necessary.

  However, it is probably worth including anyway, since any program-analyzing

  program is going to need to define it, and the definition isn't completely

  trivial.


  ENCLOSE is needed to allow expander functions to be defined in a non-NULL

  lexical environment, as required by DEFINING-MACROS-NON-TOP-LEVEL:ALLOW.  It

  also provides a mechanism by which the forms in an (EVAL-WHEN (COMPILE) ...)

  can be executed in the enclosing environment (see Issue

  EVAL-WHEN-NON-TOP-LEVEL).


  Making declarations from an &ENVIRONMENT or EVALHOOK environment optional

  continues to allow implementations the freedom simply to ignore all such

  declarations in the compiler or interpreter.



Examples:


#1:  This example illustrates the first two values returned by the function

     VARIABLE-INFORMATION.


  (DEFMACRO KIND-OF-VARIABLE (VAR &ENVIRONMENT ENV)

    (MULTIPLE-VALUE-BIND (KIND BINDINGP)

                         (VARIABLE-INFORMATION VAR ENV)

      `(LIST ',VAR ',KIND ',BINDINGP)))


  (DEFVAR A)


  (DEFCONSTANT B 43)


  (DEFUN TEST ()

    (LET (C)

      (LET (D)

        (DECLARE (SPECIAL D))

        (SYMBOL-MACROLET ((E ANYTHING))

          (LIST (KIND-OF-VARIABLE A)

                (KIND-OF-VARIABLE B)

                (KIND-OF-VARIABLE C)

                (KIND-OF-VARIABLE D)

                (KIND-OF-VARIABLE E)

                (KIND-OF-VARIABLE F))))))


  (TEST) -> ((A :SPECIAL NIL)

             (B :CONSTANT NIL)

             (C :LEXICAL T)

             (D :SPECIAL T)

             (E :SYMBOL-MACRO T)

             (F NIL NIL))


      

#2:  This example illustrates the first two values returned by the function

     FUNCTION-INFORMATION.


  (DEFMACRO KIND-OF-FUNCTION (FUNCTION-NAME &ENVIRONMENT ENV)

    (MULTIPLE-VALUE-BIND (KIND BINDINGP)

                         (FUNCTION-INFORMATION FUNCTION-NAME ENV)

      `(LIST ',FUNCTION-NAME ',KIND ',BINDING)))


  (DEFUN A ())


  (DEFUN (SETF A) (V))


  (DEFMACRO B ())


  (DEFUN TEST ()

    (FLET ((C ()))

      (MACROLET ((D ()))

        (LIST (KIND-OF-FUNCTION A)

              (KIND-OF-FUNCTION B)

              (KIND-OF-FUNCTION QUOTE)

              (KIND-OF-FUNCTION (SETF A))

              (KIND-OF-FUNCTION C)

              (KIND-OF-FUNCTION D)

              (KIND-OF-FUNCTION E)))))


  (TEST) -> ((A :FUNCTION NIL)

             (B :MACRO NIL)

             (QUOTE :SPECIAL-FORM NIL)

             ((SETF A) :FUNCTION NIL)

             (C :FUNCTION T)

             (D :MACRO T)

             (E NIL NIL))



#3: This example shows how a code-walker might walk a MACROLET special form.

    It assumes that the revised MACROLET semantics described in proposal

    DEFINING-MACROS-NON-TOP-LEVEL:ALLOW are in effect. 


  (DEFUN WALK-MACROLET (FORM ENV)

    (LET ((MACROS  (MAKE-MACRO-DEFINITIONS (CADR FORM) ENV)))

      (MULTIPLE-VALUE-BIND (BODY DECLS) (PARSE-BODY (CDDR FORM))

        (WALK-IMPLICIT-PROGN

          BODY

          (AUGMENT-ENVIRONMENT ENV :MACRO MACROS :DECLARE DECLS)))))


  (DEFUN MAKE-MACRO-DEFINITIONS (DEFS ENV)

    (MAPCAR #'(LAMBDA (DEF)

                (LET ((NAME (CAR DEF)))

                  (LIST NAME

                        (ENCLOSE (PARSE-MACRO NAME (CADR DEF) (CDDR DEF) ENV)

                                 ENV))))

            DEFS))



Cost to Implementors:


 Most implementations already record some of this information in some form.

 Providing these functions should not be too difficult, but it is a more than

 trivial amount of work.


Cost to Users:


 This change is upward compatible with user code.


Current practice:


 No implementation provides all of this interface currently.  Portable Common

 Loops defines a subset of this functionality for its code walker and

 implements it on a number of diffent versions of Common Lisp.


Discussion:


 The first version of this proposal expressly did not deal with the objects

 which are used as environments by EVALHOOK.  This version is extended to

 support them in the belief that such environments share a lot of functionality

 with the syntactic environments needed by a compiler.  While the two types of

 environments might have very different implementations, there are many

 operations which are reasonable to perform on either type, including all of

 the accessor functions described by this proposal.


 There has been discussion about a macro called WITH-AUGMENTED-ENVIRONMENT,

 either in addition to or instead of AUGMENT-ENVIRONMENT.  The point of this

 would be to say that the extent of the augmented environment is the dynamic

 extent of the WITH-AUGMENTED-ENVIRONMENT form.  There was some concern that

 there might be cases where the macro was awkward to use.  Such a macro is not

 included in this proposal.  If AUGMENT-ENVIRONMENT is provided, then such a

 macro is trivially written in terms of the function.  There are places in the

 processing of sequential binding forms where using such a macro might be more

 difficult than using the specified function.


 Some people have indicated they think that the :MACRO argument (and the

 :SYMBOL-MACRO argument too?) to AUGMENT-ENVIRONMENT should be an a-list of the

 form ((name . definition)...) rather than the form ((name definition)...).


 Some people have indicated they think that implementations must never discard

 any declarations, even if they are not otherwise used by the interpreter or

 compiler.  Proposal SMALL is consistent with what CLtL says (implementations

 are free to ignore all declarations except SPECIAL declarations), but the

 DECLARATION-INFORMATION function might not be particularly useful unless it is

 guaranteed to do something.  Requiring implementations to keep track of

 declarations they'd otherwise ignore would involve some implementation cost

 and also might incur a performance penalty.


 ENCLOSE happens to subsume the extension to COERCE for converting a lambda

 expression into a function (see Issue FUNCTION-TYPE, passed in June 1988).

 Perhaps the extension to COERCE should be backed out?


There have been some suggestions for related functionality that have not

been included in this proposal because we haven't had the time to give

them adequate consideration, and some of them might be controversial.

These suggestions include:


- Adding a function to canonicalize type specifiers.


- Extending VARIABLE-INFORMATION to return a value indicating whether there

  is a special binding of the variable in the environment, regardless of

  whether or not it has been shadowed by a lexical or symbol-macro binding

  of the same name.


- A function to map over all names that are defined in the lexical 

  environment:


    MAP-ENVIRONMENT fn key &optional env

 

    KEY must be one of the symbols :FUNCTION, :VARIABLE, or :DECLARATION.


    when key is :FUNCTION,

      for every symbol S for which (FUNCTION-INFORMATION s ENV)

      would return the values X, true, Y, for any X and Y,

      FN is applied to the arguments S, X, and Y.


    when key is :VARIABLE,

      for every symbol S for which (VARIABLE-INFORMATION s ENV)

      would return the values X, true, Y, for any X and Y,

      FN is applied to the arguments S, X, and Y.


    when key is :DECLARATION,

      for every symbol S for which (VARIABLE-INFORMATION s ENV)

      would return a non-nil value L

      FN is applied to the arguments S and L. 


- Adding additional accessors and keyword arguments to AUGMENT-ENVIRONMENT

  for BLOCK and TAGBODY labels.