[HARLEQUIN][Common Lisp HyperSpec (TM)] [Previous][Up][Next]


Issue RECURSIVE-DEFTYPE Writeup

Issue:        RECURSIVE-DEFTYPE

Forum: Editorial

References: DEFTYPE (p50)

Category: CLARIFICATION

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

Problem Description:

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)

'null

`(cons t (list-of-length ,(- length 1)))))

Proposal (RECURSIVE-DEFTYPE:EXPLICITLY-VAGUE):

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

specifiers.

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

DEFMACRO.

Clarify that the consequences are undefined if the result of fully

macroexpanding a form contains any non-constant circular list

structure.

Rationale:

This probably protects the status quo in most implementations,

while giving users a clear sense of what's reasonable and what's not.

Test Cases:

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))

(IF FAST

`(SATISFIES FOO-FAST)

`(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.

Current Practice:

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:

Probably none.

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.

Benefits:

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.

Aesthetics:

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.

Discussion:

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.''


[Starting Points][Contents][Index][Symbols][Glossary][Issues]
Copyright 1996, The Harlequin Group Limited. All Rights Reserved.