walkability.txt 7.07 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

15
16
17
18
19
20
21
22
23
24
25
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».
26
27
28

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

29
A compliant implementation SHALL provide :CDR-NN keyword in *features* and
30
31
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
32
33
current section. Each provided symbol SHALL name a function, a macro, a type,
or a constant satisfying the description in the current section.
34

35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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
53
ENCLOSE — this symbol names a function for processing an anonymous function
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
definition in a (compile-time) lexical environment as described in CLtL2.

BLOCK-INFORMATION — this symbol names a function that accepts a block name and
an optional environment, and returns :BLOCK if blocks are tracked in the
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.
72

73
74
75
76
77
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
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
103
Additionally, implementations MAY provide :CDR-NN-EXPANSIONS in *features*. In
104
this case, the following constraints SHALL hold.
105
106
107

A compliant implementation SHALL provide macro definitions for all operators
defined as macros in the standard. Expansion of conforming (portable) code
108
109
110
111
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
112
113
114
115
116
117
118
119
120
121
122
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)")
123

124
125
126
127
128
129
130
131
132
133
134
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))

135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
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.