I was under the impression that it was fairly common to use 'deftype' thus:
(deftype symlist ()
'(or null
(cons symbol symlist)))
But the Hyperspec says (Section 4.4, macro DEFTYPE):
> Recursive expansion of the type specifier returned as the expansion
> must terminate, including the expansion of type specifiers which are
> nested within the expansion.
> The consequences are undefined if the result of fully expanding a type
> specifier contains any circular structure, except within the objects
> referred to by member and eql type specifiers.
Does this language rule out my definition of 'symlist'? It seems to
work okay in Allegro and CLISP.
> (typep '(a b) 'symlist)
t
> (typep '(a 5 b) 'symlist)
nil
--
-- Drew McDermott
Yale Computer Science Department
Drew McDermott <··················@at.yale.dot.edu> writes:
> Does this language rule out my definition of 'symlist'?
Yes, it does.
> It seems to work okay in Allegro and CLISP.
In CLISP 2.32:
[1]> (deftype symlist () '(or null (cons symbol symlist)))
SYMLIST
[2]> (defun symlistp (x) (typep x 'symlist))
SYMLISTP
[3]> (compile 'symlistp)
*** - Lisp stack overflow. RESET
Drew McDermott wrote:
> I was under the impression that it was fairly common to use 'deftype' thus:
>
> (deftype symlist ()
> '(or null
> (cons symbol symlist)))
What about...
(defun symlistp (list)
(every #'symbolp list))
(deftype symlist () '(satisfies symlistp))
Pascal
--
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
Pascal Costanza <········@web.de> writes:
> (defun symlistp (list)
> (every #'symbolp list))
>
> (deftype symlist () '(satisfies symlistp))
I suppose it could be better to define that as
(deftype symlist () '(and list (satisfies symlistp)))
so that the compiler can treat (declare (type symlist foo))
as (declare (type list foo)) if it cannot optimize based on
the SATISFIES type specifier.
Kalle Olavi Niemitalo wrote:
> I suppose it could be better to define that as
>
> (deftype symlist () '(and list (satisfies symlistp)))
>
> so that the compiler can treat (declare (type symlist foo))
> as (declare (type list foo)) if it cannot optimize based on
> the SATISFIES type specifier.
This definition is not precisely the same as my recursive definition,
because it says nothing about whether the list ends with nil. Of
course, that would be easy to fix by redefining 'symlistp'.
Still, it is odd that recursive type specifiers are disallowed, given
that recursion is such an integral part of the language. I really can't
think of a rationale for the restriction. One might observe that the
'or' type specifier has to be interpreted in an ordered way, so that
(or null (cons symbol symlist))
halts under 'typep', whereas
(or (cons symbol symlist) null)
might not. But exactly the same argument applies to recursive functions
using 'or', and no one objects to those.
The main reason to prefer the recursive definition is that it allows you
to infer the type of (car x) if x is of the type in question, whereas
the "black box" definitions (using 'satisfies') do not.
--
-- Drew McDermott
Yale Computer Science Department
Drew McDermott <··················@at.yale.dot.edu> writes:
> Still, it is odd that recursive type specifiers are disallowed, given
> that recursion is such an integral part of the language. I really
> can't think of a rationale for the restriction.
Subtypep
--
~jrm
Joe Marshall wrote:
> Drew McDermott <··················@at.yale.dot.edu> writes:
>
>
>>Still, it is odd that recursive type specifiers are disallowed, given
>>that recursion is such an integral part of the language. I really
>>can't think of a rationale for the restriction.
>
>
> Subtypep
>
Actually, it's well understood how to do subtyping using recursive
types. See Benjamin Pierce's book on "Types and Programming Languages"
for the details.
Once you throw 'satisfies' into the mix, you can't get anywhere. So I
don't exactly see why the need for 'subtypep' justifies forbidding
recursive types. It seems to me it ought to be the other way around.
--
-- Drew McDermott
Yale Computer Science Department
Drew McDermott wrote:
> Actually, it's well understood how to do subtyping using recursive
> types. See Benjamin Pierce's book on "Types and Programming Languages"
> for the details.
The question is actually whether at the time of the standard there was
any relevant practice within the `industrial programming' CL community
to warrant such far reaching
> Once you throw 'satisfies' into the mix, you can't get anywhere. So I
> don't exactly see why the need for 'subtypep' justifies forbidding
> recursive types. It seems to me it ought to be the other way around.
I find the subtypep argument compelling, but even more, it is useful for
both implementation and application programmers to assume that typep
always completes (in the absence of satisfies). Recursive deftypes
won't necessarily terminate when given circular structure.
I would be happy to consider some systematic extension to the CL type
system. Types such as your symlist would allow compilers to make useful
inferences with less tedious code annotation by the programmer. Also,
many years ago there were requests for real parametric types e.g.
(array single-float (n n) for a square array, but no one was willing
to do the slog work to figure out how to integrate such things
usefully into the language in a way that wouldn't break existing
practices or performance assumptions.
Steven M. Haflich <·················@alum.mit.edu> wrote:
> I would be happy to consider some systematic extension to the CL type
> system.
I'd not be the least surprised if most people were... But the question of
how remains. Will the have to be a period of diversification before
extensions (whether ANSI or community ones) to the standard, or are there
"obvious" things that could be hotwired?
Obvious here could mean any of several things, of course:
* Specified extensions that most implementations already support, like
MOP.
* Extensions like the "specialized lists" mentioned that have obvious
uses but are neither specified not implemented but would (hopefully) be
relatively simple to.
* Extensions that have that have competing (but not mutually
exclusive) de-facto standards like user extensible streams.
Me, I believe in a period of diversification, but definitely not mind
being proven wrong. ;-)
Cheers,
-- Nikodemus
In article <············@news.wss.yale.edu>,
Drew McDermott <··················@at.yale.dot.edu> wrote:
> Still, it is odd that recursive type specifiers are disallowed, given
> that recursion is such an integral part of the language.
Recursion requires that you be able to test for the base case and stop
recursing, which requires a sequential language. DEFTYPE is a
declarative specification, not a procedural one, so recursion is not
applicable.
There can be similar problems with recursive macros.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin <······@alum.mit.edu> writes:
> Recursion requires that you be able to test for the base case and stop
> recursing, which requires a sequential language. DEFTYPE is a
> declarative specification, not a procedural one, so recursion is not
> applicable.
I don't mean to comment on DEFTYPE specifically, but I'm not sure of your
claim in the general case. Recursion isn't limited to procedural languages.
Declarative languages can use recursion just fine.
As an example, predicate calculus (aka first-order logic) is the canonical
declarative language, and it's pretty important to be able to define recursive
concepts in the language.
Separately, many interesting declarative languages have inference engines
built to process them, and you certainly have to understand what to do about
recursive definitions when writing the inference engines.
But it seem extreme to say that the _reason_ DEFTYPE doesn't allow recursion
is that it is declarative instead of procedural. I think that's an orthogonal
issue, not an explanation.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
At a book burning, don't leave too soon, or you might miss the dictionaries.
-- Deep Thoughts, by Jack Handey [1999]
Barry Margolin wrote:
> Recursion requires that you be able to test for the base case and stop
> recursing, which requires a sequential language. DEFTYPE is a
> declarative specification, not a procedural one, so recursion is not
> applicable.
>
> There can be similar problems with recursive macros.
What do you mean? Can you give an example?
Pascal
--
ECOOP 2004 Workshops - Oslo, Norway
*1st European Lisp and Scheme Workshop, June 13*
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
*2nd Post-Java Workshop, June 14*
http://prog.vub.ac.be/~wdmeuter/PostJava04/
In article <············@f1node01.rhrz.uni-bonn.de>,
Pascal Costanza <········@web.de> wrote:
> Barry Margolin wrote:
>
> > Recursion requires that you be able to test for the base case and stop
> > recursing, which requires a sequential language. DEFTYPE is a
> > declarative specification, not a procedural one, so recursion is not
> > applicable.
> >
> > There can be similar problems with recursive macros.
>
> What do you mean? Can you give an example?
(defmacro my-or (&rest expressions)
`(let ((first ,(car expressions))
(rest ,(cdr expressions)))
(cond (first first)
((not (null ',rest))
(my-or ,@rest)))))
The bug in this is that the not-null test is within the backquoted
expansion, not in the code that will be run at macro-expansion time, so
it won't prevent future expansion attempts.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Pascal Costanza wrote:
>
>
> Drew McDermott wrote:
>
>> I was under the impression that it was fairly common to use 'deftype'
>> thus:
>>
>> (deftype symlist ()
>> '(or null
>> (cons symbol symlist)))
>
>
> What about...
>
> (defun symlistp (list)
> (every #'symbolp list))
>
> (deftype symlist () '(satisfies symlistp))
>
>
SATISFIES seems to imply a run-time check. Recursive data types should
be allowed, although the language of the CLHS (and, if memory does not
fail me, some implementations) make this very iffy.
In the simple case above, at a minimum, the CLHS should have had
provisions for a number of LIST/CONS based type specifiers. E.g.
(declare (type (simple-list symbol) sl)
(type (simple-list integer *) il)
(type (simple-list float 42) fl)
(type (complex-list float float &rest integer) cl))
Where COMPLEX-LIST is a type specifier that takes a variation of a
lambda list for specifying its elements. SIMPLE-LIST and COMPLEX-LIST
should be subtypes of of LIST.
Cheers
--
Marco