[closer-devel] Recursive types

[Pascal Costanza]

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

> So, the questions I raise are two.
> 1 - which would be the best forum (:if-exists :use-it :if-does-not- 
> exist :do-not-use-c.l.l.-yet) where to have this discussion?

Maybe lisp forum: http://www.lispforum.com/ - but it's quite new,  
don't know yet how good it is.

Maybe #lisp.

At c.l.l, you would probably get responses telling that X solves this,  
where X is one or more of {Cells, OCaml, F#}, so that's probably not a  
good option.

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


Pascal

-- 
Pascal Costanza, mailto:pc at p-cos.net, http://p-cos.net
Vrije Universiteit Brussel, Programming Technology Lab
Pleinlaan 2, B-1050 Brussel, Belgium






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