#

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

Copyright 1996-2005, LispWorks Ltd. All rights reserved.