Hi,
I think the only place where you could meaningfully specify this is with TYPEP (and maybe SUBTYPEP). You could probably specify something like: "The type declaration should only be expanded as far as is necessary to make the type test terminate." (Very badly worded, but I hope you get the idea.)
However, I think it's good that ANSI CL leaves this undefined, because this means that a compiler can focus on static optimizations to avoid any runtime expansions of type information. If recursive types were allowed in general here, it would become undecidable whether a type definition is statically checkable or not.
The situation is not as bad as it looks, because there is already a hook for performing runtime type tests. For example, what's wrong with the following?
(defun int-list-p (object) (or (null object) (and (consp object) (integerp (car object)) (int-list-p (cdr object)))))
(deftype int-list () '(satisfies int-list-p))
You could probably come up with a macro that does this automatically for you and looks similar to CL-style type specifications. If you worry about efficiency for such dynamic tests, it's probably better to come up with partial evaluation techniques for functions in general, which would benefit the overall language more, than doing this just for type specifications.
Maybe I'm missing something...
Pascal
On 11 Aug 2008, at 18:52, Marco Antoniotti wrote:
Hi
I have the following DEFTYPE
(deftype int-list () '(or null (cons integer int-list)))
Then in LW this happens
CL-USER 6 > (typep '(1 2 3) 'int-list)
Stack overflow (stack size 15997).
In Franz ACL the following happens instead
CL-USER> (typep '(1 2 3) 'int-list) T CL-USER> (typep '(1 a 3) 'int-list) NIL
(Sorry these are the only implementations I have at hand right now).
Now: recursive types are not well understood by the CLHS, and it would seem that both implementations are somewhat "conforming". However, since we are in 2008, ACL behavior is the "correct" one, although it would seem that the people at Franz are stretching the CLHS.
The question I have is the following: how do we go ahead and write a CDR that described ACL apparent behavior (i.e. how do we introduce "correct" recursive types in CL)?
Note that I just want to start a discussion on this issue and collect comments and ideas. I am interested in a medium term discussion on the issue; I am not interested in responses like "use Qi" or "use F#/Ocaml/Haskell etc" (as an aside, Haskell is my favorite of the bunch).
Thanks
-- Marco Antoniotti
PS. There are also issues of "compilation" vs "run-time" environments to be taken into account. -- Marco Antoniotti
cdr-discuss mailing list cdr-discuss@common-lisp.net http://common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss