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