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
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
On Mon, Aug 11, 2008 at 9:56 PM, Pascal Costanza pc@p-cos.net wrote:
Maybe I'm missing something...
The ability to derive the type of both CAR and CDR of an INT-LIST (or whatever).
That said,
(let ((list (get-list))) (declare (type (cons integer list) list)) ...)
gives compiler as much information as a recursive type, assuming that the CDR is always assigned back to LIST.
Likewise,
(defstruct listoid (int 0 :type integer) (tail nil :type (or null listoid)))
gives the compiler just as much information (though the representation is almost certain to be 4 words on the heap as opposed to 2 for a CONS. DEFSTRUCT also gives you the ability to define what amount to mutually recursive types:
(defstruct one (two nil :type (or null two))) (defstruct two (one nil :type (or null one)))
All in all, I would be perhaps more interested in a SIMPLE-LIST type, (where CAR is always of the same type), then recursive DEFTYPE in general:
(deftype int-list () '(simple-list integer))
In terms of what implmenentations do, what does Allegro do for
(compile nil '(lambda (x) (typep x 'int-list)))
and
(deftype fixnum-list () '(or null (cons fixnum fixnum-list)))
(compile nil '(lambda (x) (declare (fixnum-list x) (optimize speed)) (let ((a (first x)) (b (second x))) (when (and a b) (+ a b))))
? (That is, does it implement recursive types for the compiler as well, or do they just work in full calls to TYPEP?)
Cheers,
-- Nikodemus
On Aug 12, 2008, at 03:48 , Nikodemus Siivola wrote:
...
DEFSTRUCT also gives you the ability to define what amount to mutually recursive types:
(defstruct one (two nil :type (or null two))) (defstruct two (one nil :type (or null one)))
This mostly works. However, LW warns you that TWO is not a valid type specifier (while compiling a file containing the two definitions. AFAIU, this behavior is "conforming".
All in all, I would be perhaps more interested in a SIMPLE-LIST type, (where CAR is always of the same type), then recursive DEFTYPE in general:
(deftype int-list () '(simple-list integer))
In terms of what implmenentations do, what does Allegro do for
(compile nil '(lambda (x) (typep x 'int-list)))
CL-USER> (deftype int-list () '(or null (cons integer int-list)))
INT-LIST CL-USER> (compile nil (lambda (x) (typep x 'int-list))) #<Function (:ANONYMOUS-LAMBDA 3) @ #x105e6862> NIL NIL CL-USER> (funcall * '(a s d)) NIL CL-USER> (funcall * '(1 2)) T
and
(deftype fixnum-list () '(or null (cons fixnum fixnum-list)))
(compile nil '(lambda (x) (declare (fixnum-list x) (optimize speed)) (let ((a (first x)) (b (second x))) (when (and a b) (+ a b))))
? (That is, does it implement recursive types for the compiler as well, or do they just work in full calls to TYPEP?)
CL-USER> (deftype fixnum-list () '(or null (cons fixnum fixnum-list))) FIXNUM-LIST CL-USER> (compile nil '(lambda (x) (declare (fixnum-list x) (optimize speed)) (let ((a (first x)) (b (second x))) (when (and a b) (+ a b))))) #<Function (:ANONYMOUS-LAMBDA 5) @ #x106d2e7a> NIL NIL CL-USER> (funcall * '( 1 2 )) 3 CL-USER> (funcall * '( 1 a ))
;;; This is the SLIME backtrace
`A' is not of the expected type `NUMBER' [Condition of type TYPE-ERROR]
Restarts: 0: [ABORT-REQUEST] Abort handling SLIME request. 1: [ABORT] Abort entirely from this (lisp) process.
Backtrace: 0: (SWANK::DEBUG-IN-EMACS #<TYPE-ERROR @ #x1070970a>) 1: (SWANK:SWANK-DEBUGGER-HOOK #<TYPE-ERROR @ #x1070970a> #<Function SWANK-DEBUGGER-HOOK>) 2: (ERROR TYPE-ERROR :DATUM A :EXPECTED-TYPE NUMBER :FORMAT-CONTROL "~@<`~s' is not of the expected type `~s'~:@>" :FORMAT-ARGUMENTS (A NUMBER)) 3: ((:ANONYMOUS-LAMBDA 7) (1 A)) 4: (FUNCALL #<Function (:ANONYMOUS-LAMBDA 7) @ #x1070769a> (1 A))
So it looks like you get a TYPE-ERROR as expected, but I think this is coming from the call to +.
Cheers -- Marco Antoniotti
On 12 Aug 2008, at 09:48, Nikodemus Siivola wrote:
On Mon, Aug 11, 2008 at 9:56 PM, Pascal Costanza pc@p-cos.net wrote:
Maybe I'm missing something...
The ability to derive the type of both CAR and CDR of an INT-LIST (or whatever).
...when you add recursion to type specifiers, you won't be able to do that in the general case anymore as well.
Pascal