[cdr-discuss] Issues with DEFTYPE

[Pascal Costanza]

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 at common-lisp.net
> http://common-lisp.net/cgi-bin/mailman/listinfo/cdr-discuss

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