References: DEFTYPE (p50)
Edit history: 05-Mar-91, Version 1 by Pitman
15-Mar-91, Version 2 by Pitman, Loosemore
(expand scope of proposal to treat both program and
structural circularities, and to treat both macros
and type specifiers equivalently)
Status: For X3J13 consideration
In discussion of issue CONS-TYPE-SPECIFIER, it became apparent that some
users thought it might be ok to have non-terminating recursive DEFTYPE
definitions. Some vendors balked at this. The case in question, which
is not [yet] valid Common Lisp at the time the proposal is written, but
which nevertheless illustrates the point, is Barry Margolin's:
(deftype proper-list (&optional (element-type t))
`(or null (cons ,element-type proper-list)))
Another case, which is also not valid Common Lisp but which illustrates
a case that might be more tolerable is Allan Wechsler's:
(deftype list-of-length (length)
(if (= 0 length)
`(cons t (list-of-length ,(- length 1)))))
Clarify that recursive expansion of the type specifier returned as
the expansion of a DEFTYPE must terminate, including the expansion
of type specifiers which are nested within the expansion.
Clarify that the consequences are undefined if the result of
fully expanding a type specifier contains any circular structure,
except within the objects referred to by MEMBER and EQL type
Clarify that recursive expansion of the form returned as the
expansion of a DEFMACRO must terminate, including the expansion
of other macros which are subforms of other forms returned by
Clarify that the consequences are undefined if the result of fully
macroexpanding a form contains any non-constant circular list
This probably protects the status quo in most implementations,
while giving users a clear sense of what's reasonable and what's not.
These test cases are more contrived in nature, but are chosen to be
actually plausible to test in existing implementations (something not
true of the cases mentioned in the problem description):
#1: (DEFUN RETURNS-T (X) X)
(DEFTYPE FOO () '(OR (SATISFIES RETURNS-T) FOO))
This is an error because in (TYPEP X 'FOO), FOO cannot, in general,
be fully expanded because the expansion does not terminate.
#2: (DEFTYPE FOO (&KEY (FAST NIL))
`(AND SYMBOL (FOO :FAST T))))
This is well-defined because in (TYPEP X 'FOO), FOO can, in general,
be fully expanded without error because the recursion always terminates.
#3: Macro definitions like:
(DEFMACRO MAPCAR1 (FN LIST)
`(IF (NULL ,LIST) '()
(CONS (FUNCALL ,FN (CAR ,LIST))
(MAPCAR1 ,FN (CDR ,LIST)))))
would be explicitly undefined.
#4: Forms involving explicit circularities, such as
(PROGN . #1=((PRINT 'FOO) . #1#))
would be explicitly undefined.
#5: Type specifiers involving explicit circularities, such as
a. (TYPEP 3 '(AND #1=(T . #1#)))
would be explicitly undefined, except for cases like
b. (TYPEP 3 '(EQL #1=(T . #1#)))
which would still be well-defined.
Genera implements this proposal.
#1: The proposal makes this an error.
Genera uses a TYPE-EXPAND function internally at compile time and
so cannot handle this case.
#2: The proposal requires this to work.
Genera handles this case.
#3: The proposal makes this an error.
Genera can manage to do (MAPCAR #'1+ '(1 2 3)) as a standalone form,
but blows out during lexical analysis both in the interpreter and
compiler if you put it in a definition.
#4: The proposal makes this case an error.
Genera can't handle this case at all.
#5: The proposal makes #5a an error but requires #5b to work.
Genera doesn't handle #5a but does handle #5b.
Cost to Implementors:
Cost to Users:
Little or none. Code which exploited the erroneous cases were already
not portable in practice, so probably no users relied on them.
Cost of Non-Adoption:
Portability pitfalls waiting for unsuspecting users.
Compiler writers who didn't want to handle this won't go to sleep every
night in fear that they really should have and that some day someone will
be knocking on their door asking why not.
This is intended to be equivalent to the status quo for macros, although
it doesn't have to be spelled out there because the presence of MACROEXPAND
pretty much forces it. In any case, it clarifies that DEFTYPE and DEFMACRO
must be essentially consistent on this issue.
Pitman supports this proposal.
If Sandra Loosemore's TYPE-EXPAND proposal (part of issue TYPE-SPECIFIER-P)
passed, this view of the world would pretty much be forced anyway.
Of Margolin's example, Rob MacLachlan (at CMU) wrote:
``I am fairly sure that nobody has addressed this issue.
Although I have been aware of it, I kept quiet about it,
because my compiler gags on recursive deftypes, and I was
afraid someone would decide that was a bug.''