[closer-devel] Recursive types

[Marco Antoniotti]

On Jul 13, 2008, at 17:54 , Pascal Costanza wrote:

>
> On 13 Jul 2008, at 12:22, Marco Antoniotti wrote:
>
>> Hi
>>
>> I am writing here because this may be the place closest to some of  
>> the issue I would like to raise (slowly!) with some of the typing  
>> issues in CL.
>>
>> Consider the following (contrived) example
>>
>> (defstruct node
>>   content
>>   (left nil :type (or null arc))
>>   (right nil :type (or null arc)))
>>
>>
>> (defstruct arc
>>   (source nil :type (or null node))
>>   (sink nil :type (or null node)))
>>
>> At least on LW, compiling the snippet the first time raises the  
>> following warning
>>
>> ; (SUBFUNCTION MAKE-NODE (DEFSTRUCT NODE))
>> ;;;*** Warning in (SUBFUNCTION MAKE-NODE (STRUCTURE NODE)):  
>> Ignoring type declaration with illegal type (OR NULL ARC)
>> ;;;*** Warning in (SUBFUNCTION MAKE-NODE (STRUCTURE NODE)):  
>> Ignoring type declaration with illegal type (OR NULL ARC)
>>
>> There seem to be no way in CL to make a "forward" type declaration.
>
> I see some possibilities for workarounds, all with different  
> advantages and disadvantages:
>
> 1)
>
> (defun %arcp (object)
>   (typep object 'arc))
>
> (deftype %arc ()
>   '(satisfies %arcp))
>
> (defstruct node
>   content
>   (left nil :type (or null %arc))
>   (right nil :type (or null %arc)))
>
> (defstruct arc
>   (source nil :type (or null node))
>   (sink nil :type (or null node)))
>
> 2)
>
> (defstruct root)
>
> (defstruct (node (:include root))
>   content
>   (left nil :type (or null root))
>   (right nil :type (or null root)))
>
> (defstruct (arc (:include root))
>   (source nil :type (or null root))
>   (sink nil :type (or null root)))
>
> 3)
>
> (defclass node ()
>   (content left right))
>
> (defclass arc ()
>   ((source :initform nil :type (or null node))
>    (sink :initform nil :type (or null node))))
>
> (defclass node ()
>   (content
>    (left :initform nil :type (or null arc))
>    (right :initform nil :type (or null arc))))

(2) and (3) are better for different reasons.  In any case, the  
problem exhibits itself especially with DEFSTRUCTs.  E.g., (3) could  
look like

(defstruct node)

(defstruct arc (source nil :type (or null node) ...)
(defstruct node (left nil :type (or null arc))

but then you hit the "DEFSTRUCT cannot really be redefined" problem.


>> 2 - where would you look in the ANSI spec for places where various  
>> clauses needs to be changed or removed to make recursive types "CDR- 
>> able"?
>
> As far as I can tell, a modification of deftype should be  
> sufficient, such that (deftype name) "announces" a type without  
> saying yet what it will be.
>
> Maybe write a first draft of such a CDR, and then ask the vendors  
> what they think, they should know best whether and where this hurts...

That is my intention.  However, just modifying DEFTYPE already raises  
issues.  See the following...

(deftype foo)

(deftype bar)

(deftype foo-or-bar () '(or foo bar))


Now, all these types are actually "empty" from a set-theoretic point  
of view.

Also, note the following interesting behavior on LWM and ACL 8.1 (I  
have not tested other implementations).

CL-USER 13 > (deftype gnao ())
GNAO

CL-USER 14 > (typep nil 'gnao)
NIL

CL-USER 15 > (defstruct gnao a s d)
GNAO

CL-USER 16 > (make-gnao)
#S(GNAO :A NIL :S NIL :D NIL)

CL-USER 17 > (typep (make-gnao) 'gnao)
NIL

CL-USER 18 > (type-of (make-gnao))
GNAO

AFAIAC this is not good.   And the culprit is the DEFTYPE that does  
introduce an extra namespace in CL without really defining what is in  
there and how I can manipulate it.

Cheers


--
Marco Antoniotti


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/closer-devel/attachments/20080721/9333f697/attachment.html>