Recursive types

[Marco Antoniotti]

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

Cheers
--
Marco

[Pascal Costanza]

Post by Marco Antoniotti
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))))

Post by Marco Antoniotti
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.

Post by Marco Antoniotti
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

[Marco Antoniotti]

Post by Pascal Costanza

Post by Marco Antoniotti
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))
Ignoring type declaration with illegal type (OR NULL ARC)
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
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.

Post by Pascal Costanza

Post by Marco Antoniotti
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

[Pascal Costanza]

Post by Marco Antoniotti

Post by Pascal Costanza
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.

Hm, well, my idea was that (deftype foo) only "announces" the type foo
but doesn't define it yet, so that you can do things like this:

(deftype arc) ;; not yet defined, but tells the compiler that it will
be defined later

(defstruct node
content
(left nil :type (or null arc))
(right nil :type (or null arc))

(defstruct arc ;; now it is defined as a struct
(source nil :type (or null node))
(sink nil :type (or null node)))

The tricky part is in (a) specifying where an announced but not yet
defined type is allowed to be used and (b) specifying what is the
latest point in time when an announced type must effectively be
defined (like, for example, performing the first type test with the
given type - it's unclear to me what the most adequate criterion
should be here).

Post by Marco Antoniotti
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.

Why? You got what you asked for. (deftype gnoa ()) has an empty body,
so by default it returns nil, which happens to be the type that
doesn't have any instances.

Furthermore, ANSI CL doesn't say anything about type redefinition, so
we are in unspecified realm here. ANSI CL only says something about
class redefinition, but that doesn't change the corresponding types.
The CLOS MOP says that changing the metaclass of a class is forbidden,
so you can't change (the kind of) types using the CLOS MOP either.


Pascal

[Marco Antoniotti]

Post by Pascal Costanza

Post by Marco Antoniotti

Post by Pascal Costanza
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.

Hm, well, my idea was that (deftype foo) only "announces" the type
(deftype arc) ;; not yet defined, but tells the compiler that it
will be defined later
(defstruct node
content
(left nil :type (or null arc))
(right nil :type (or null arc))
(defstruct arc ;; now it is defined as a struct
(source nil :type (or null node))
(sink nil :type (or null node)))
The tricky part is in (a) specifying where an announced but not yet
defined type is allowed to be used and (b) specifying what is the
latest point in time when an announced type must effectively be
defined (like, for example, performing the first type test with the
given type - it's unclear to me what the most adequate criterion
should be here).

Yes. All of these issues should be cleared.

Post by Pascal Costanza

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

.....

Post by Pascal Costanza

Post by Marco Antoniotti
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.

Why? You got what you asked for. (deftype gnoa ()) has an empty
body, so by default it returns nil, which happens to be the type
that doesn't have any instances.
Furthermore, ANSI CL doesn't say anything about type redefinition,
so we are in unspecified realm here. ANSI CL only says something
about class redefinition, but that doesn't change the corresponding
types.

Yes. We are in "evil country" (i.e. unspecified behavior or
implementation dependent). So you see that the issue is not all that
easy to fix. I'll submit this to LW and Franz and hear what they say.


--
Marco Antoniotti

[Gary King]

Hi Marco,

I can't offer any trenchant comments but I am very much in favor of
Common Lisp being able to use type declarations more "dynamically".

Post by Marco Antoniotti
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.
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?
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"?
Cheers
--
Marco
_______________________________________________
closer-devel mailing list
http://common-lisp.net/cgi-bin/mailman/listinfo/closer-devel

--
Gary Warren King, metabang.com
Cell: [phone]
Fax: [phone]
gwkkwg on Skype * garethsan on AIM