walkability.txt 7.64 KB
Newer Older
1
2
3
4
Motivation

The Common Lisp standard describes a lot of facilities for treating code as
data. Unfortunately, it stops short of specifying enough functionality to
Philipp Marek's avatar
Typos    
Philipp Marek committed
5
allow writing a portable code walker. In addition, some requirements that
6
7
8
9
10
might have been assumed to be implications of the standard are not spelled out
explicitly. As a result, implementations have different behaviour, which
creates more corner cases than necessary for partial code walking
implementations.

11
12
13
Some of the functionality useful for code walkers has been described in the
second edition of «Common Lisp: the Language» as included in the standard, but
later removed.
14

Philipp Marek's avatar
Philipp Marek committed
15
16
17
18
19
20
// Comment PM: Which features would we actually want? Is that about
   providing better LOOP and ITERATE, for better macro debugging, ...?
   What do implementations already provide here? Could we get by with some
   TRIVIAL-WALKABILITY library and very small patches to the implementations?


21
22
23
24
25
26
27
28
29
30
31
This document defines three sets of requirements, CDR-NN-a, CDR-NN-b, and 
CDR-NN-b. The first set of requirements is intended to be easy to implement and
maintain. The goal is to provide easy and uniform detection and use of the
functionality implementations already provide under implementation-specific
names. The second set of requirements requires some additional work from
implementations, but provides a way to move some advanced functionality from «a
smart enough  macro» stories to reality. The third set of requirements permits
more efficient implementation of code walkers, while only using the 
functionality many implementations are expected to have internally.

«Requirements of CDR-NN» is synonymous with «requirements of CDR-NN-a».
32
33
34

The uniform naming requirements (CDR-NN-a).

35
A compliant implementation SHALL provide :CDR-NN keyword in *features* and
36
37
CDR-NN package (this package MAY have a different name and CDR-NN nickname).
The CDR-NN package SHALL contain a subset of the symbols described in the
38
39
current section. Each provided symbol SHALL name a function, a macro, a type,
or a constant satisfying the description in the current section.
40

41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
VARIABLE-INFORMATION — this symbol names a function for obtaining information
about a variable in an environment, as described in CLtL2.

FUNCTION-INFORMATION — this symbol names a function for obtaining information
about a function in an environment, as described in CLtL2.

DECLARATION-INFORMATION — this symbol names a function for obtaining
information about a declaration in an environment, as described in CLtL2.

AUGMENT-ENVIRONMENT — this symbol names a function for creating a new
environment with an extra entry, as described in CLtL2.

DEFINE-DECLARATION — this symbol names a macro for defining handlers for named
declarations as described in CLtL2.

PARSE-MACRO — this symbol names a function for processing macro definitions 
like defmacro does as described in CLtL2.

Philipp Marek's avatar
Typos    
Philipp Marek committed
59
ENCLOSE — this symbol names a function for processing an anonymous function
60
61
definition in a (compile-time) lexical environment as described in CLtL2.

Philipp Marek's avatar
Philipp Marek committed
62
63
BLOCK-INFORMATION — this symbol names a function that accepts a block name and        // Comment PM: what about (BLOCK NIL ...)?
an optional environment, and returns :BLOCK if blocks are tracked in the              //  We need two return values.
64
65
66
67
68
69
70
71
72
73
74
75
76
77
environment object and a block with the provided name is listed, and NIL
otherwise.

TAG-INFORMATION — this symbol names a function that accepts a tag name and an
optional environment, and returns :TAG if tags are tracked in the environment
object and a block with the provided name exists, and NIL otherwise.

COPY-ENVIRONMENT — this symbol names a function that accepts a single
lexical environment argument and returns a new environment with the same
entries.

PARENT-ENVIRONMENT — this symbol names a function that accepts a single
lexical environment and returns the parent environment, if parent environment
is tracked and exists, and NIL otherwise.
78

79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
WITH-AUGMENTED-ENVIRONMENT — this symbol names a macro.
WITH-AUGMENTED-ENVIRONMENT ((old-env new-env &key variable symbol-macro
function macro declare) &body body) executes BODY with variable named by 
NEW-ENV bound to a possibly dynamically scoped environment modified by
starting from OLD-ENV and applying the &key arguments as if by
AUGMENT-ENVIRONMENT. It is unspecified what happens on access to OLD-ENV
inside BODY. After the WITH-AUGMENTED-ENVIRONMENT the OLD-ENV environment
should be the same and with the same contents as before.

WITH-PARENT-ENVIRONMENT — this symbol names a macro.
WITH-PARENT-ENVIRONMENT ((env parent) &body body) executes BODY with variable
named by PARENT bound to the parent environment of ENV if parent environment
is tracked and exists.

ENVIRONMENT-ENTRY-NAMES — this symbol names a function of a single environment
argument that returns the list that includes the symbols naming all the 
entries (macros, symbol-macros, functions, variables and declarations) in the
environment. The list MAY also contain other entries. If blocks and tags are
tracked in the lexical environment object, their names SHOULD be included in
the result.

MACROEXPAND-ALL — this symbol names a function that accepts a form and an
optional environment, and returns the expansion of the form in that
environment. The function SHALL take the environment argument into account if
it is passed to it.

LEXICAL-ENVIRONMENT — this symbol names a type that includes all possible
non-NIL values of &environment parameter to macros defined via DEFMACRO or
MACROLET. The type SHOULD be as narrow as feasible.

Philipp Marek's avatar
Typos    
Philipp Marek committed
109
Additionally, implementations MAY provide :CDR-NN-EXPANSIONS in *features*. In
110
this case, the following constraints SHALL hold.
111
112
113

A compliant implementation SHALL provide macro definitions for all operators
defined as macros in the standard. Expansion of conforming (portable) code
114
115
116
117
SHALL be conforming code that MAY use some implementation-specific functions
and SHALL be portable except for the choice of functions. The expansion SHALL
NOT pass non-portable (non-standard) arguments to standard operators. For every
form in the original code, this form or the result of expanding some
118
119
120
121
122
123
124
125
126
127
128
macros inside the form SHALL be a form of the expansion.

Examples of discouraged behaviours permitted by the Common Lisp standard.

   (defun f (x) (1+ x))

is currently allowed to expand to any of the following:
   
   (define-function 'f '(lambda f (x) (block f (1+ x))))
   (define-function 'f (impl::named-lambda f (x) (block f (1+ x))))
   (define-function 'f "x -> (1+ x)")
129

130
131
132
133
134
135
136
137
138
139
140
Note that the standard permits to provide a macro expansion for a special
operator. The requirements of both the standard and of this specification can
be satisfied if impl::named-lambda is a special operator implemented via
expansion to

   (function '(impl::named-lambda f (x) (block f (1+ x))))

but with an additional macro expansion provided that returns

   (labels ((f (x) (1+ x))) (function f))

141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
Full code walking support requirements (CDR-NN-b).

A compliant implementation SHALL implement CDR-NN-a, SHALL satisfy the
:CDR-NN-EXPANSIONS requirements and SHALL provide at least the following
functionality as defined in CDR-NN-a requirements.

Either WITH-AUGMENTED-ENVIRONMENT, or AUGMENT-ENVIRONMENT, or
ENVIRONMENT-ENTRY-NAMES, or MACROEXPAND-ALL.

Efficient code walking support (CDR-NN-c)

A compliant implementation SHALL implement CDR-NN-b and SHALL provide at least 
the following functionality as defined in CDR-NN-a requirements.

Either WITH-AUGMENTED-ENVIRONMENT or AUGMENT-ENVIRONMENT.
ENVIRONMENT-ENTRY-NAMES.
PARSE-MACRO.
LEXICAL-ENVIRONMENT.
Philipp Marek's avatar
Philipp Marek committed
159
160
161
162

// Comment PM: Why do we define various levels (-a, -b, -c) if the things
	in them are declared as "SHALL"? IMO that means that every implementation
    conforming to -a already conforms to -c as well.