[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

declaring the elements of a list

Jim Newton

12/23/2015 2:56:00 PM

Common lisp has a type specifier operator CONS which can declare the car and cdr of a cons cell.
e.g.,

(defun F (x)
(declare (type (cons number null)) x)
; x is a singleton list of a number
...)

However, it is pretty common to have a list of homogeneous elements. E.g., a list of strings
or a list of symbols. But there's no easy way to declare this except excessive use of (cons...)
E.g., (cons number (cons number (cons number (cons number null)))) ; a list of 4 numbers.

My guess is that even if there were a way to make such a declaration, it would be of
dubious utility to the compiler or runtime environment.

Is it perhaps conceivable that the compiler or runtime environment could take advantage of
such a declaration given that cons cells are mutable.

Any function who receives a reference to a list may modify any cons cell in it.
It seems to me that there would be no way for the compiler to gain an advantage in such
a declaration.

Am I mistaken? Might there be some optimization a compiler could if the user could
declare the :element-type of a list? Would it be possible for the system to prevent
running code from breaking the declared promise via destructive functions?

Of course there might be advantages of readability for humans to understand the intent
of variables, but my question is about the compiler, or runtime environment.
17 Answers

Operations

12/23/2015 3:25:00 PM

0

Not sure about the compiler or runtime, but you can certainly do the
following.

CL-USER(1): (deftype list-of-ints () '(or null (cons integer list-of-ints)))
LIST-OF-INTS
CL-USER(2): (typep (list 1 2 3) 'list-of-ints)
T
CL-USER(3): (typep (list 1 2.3 3) 'list-of-ints)
NIL

Jim Newton

12/23/2015 5:49:00 PM

0

And I can probably extend that to have the type parameterized

(deftype list-of (type)
`(or null (cons ,type (list-of ,type))))

or maybe that's an infinite loop. Haven't tried it yet.




On Wednesday, December 23, 2015 at 4:24:59 PM UTC+1, Operations wrote:
> Not sure about the compiler or runtime, but you can certainly do the
> following.
>
> CL-USER(1): (deftype list-of-ints () '(or null (cons integer list-of-ints)))
> LIST-OF-INTS
> CL-USER(2): (typep (list 1 2 3) 'list-of-ints)
> T
> CL-USER(3): (typep (list 1 2.3 3) 'list-of-ints)
> NIL

Barry Margolin

12/23/2015 6:47:00 PM

0

In article <3df174fe-a326-46ee-815d-b87302b86048@googlegroups.com>,
Jim Newton <jimka.issy@gmail.com> wrote:

> And I can probably extend that to have the type parameterized
>
> (deftype list-of (type)
> `(or null (cons ,type (list-of ,type))))
>
> or maybe that's an infinite loop. Haven't tried it yet.

CLHS http://clhs.lisp.se/Body/m... says: "Recursive expansion of
the type specifier returned as the expansion must terminate, including
the expansion of type specifiers which are nested within the expansion."

So a self-referential type like this is not valid.

>
> On Wednesday, December 23, 2015 at 4:24:59 PM UTC+1, Operations wrote:
> > Not sure about the compiler or runtime, but you can certainly do the
> > following.
> >
> > CL-USER(1): (deftype list-of-ints () '(or null (cons integer list-of-ints)))
> > LIST-OF-INTS
> > CL-USER(2): (typep (list 1 2 3) 'list-of-ints)
> > T
> > CL-USER(3): (typep (list 1 2.3 3) 'list-of-ints)
> > NIL

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Teemu Likonen

12/23/2015 7:00:00 PM

0

operations@ravenpack.com [2015-12-23 16:24:50+01] wrote:

> Not sure about the compiler or runtime, but you can certainly do the
> following.
>
> CL-USER(1): (deftype list-of-ints () '(or null (cons integer list-of-ints)))
> LIST-OF-INTS
> CL-USER(2): (typep (list 1 2 3) 'list-of-ints)
> T

With the following debugger output from SBCL:

Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.

PROCEED WITH CAUTION.
[Condition of type SB-KERNEL::CONTROL-STACK-EXHAUSTED]

--
/// Teemu Likonen - .-.. <https://github.com/tl... //
// PGP: 4E10 55DC 84E9 DFF6 13D7 8557 719D 69D3 2453 9450 ///

Siebe de Vos

12/23/2015 8:51:00 PM

0

On 2015-12-23 15:55, Jim Newton wrote:
> Common lisp has a type specifier operator CONS which can declare the car and cdr of a cons cell.
> e.g.,
>
> (defun F (x)
> (declare (type (cons number null)) x)
> ; x is a singleton list of a number
> ...)
>
> However, it is pretty common to have a list of homogeneous elements. E.g., a list of strings
> or a list of symbols. But there's no easy way to declare this except excessive use of (cons...)
> E.g., (cons number (cons number (cons number (cons number null)))) ; a list of 4 numbers.

What you are asking could be described by:

(defstruct (four-numbers (:type list))
(number1 0 :type number)
(number2 0 :type number)
(number3 0 :type number)
(number4 0 :type number))

Then check http://clhs.lisp.se/Body/m_..., :named and :type (the
defstruct option, not the slot option): the spec goes some way to
prevent list based structures to be considered as a type.

If you turn that around you realize that the language suggests to
represent structured data by structure objects instead of lists. And, of
course, lists of homogeneous elements by vectors.

S.

Alan Bawden

12/23/2015 9:38:00 PM

0

Jim Newton <jimka.issy@gmail.com> writes:

> And I can probably extend that to have the type parameterized
>
> (deftype list-of (type)
> `(or null (cons ,type (list-of ,type))))
>
> or maybe that's an infinite loop. Haven't tried it yet.

As you expected, that doesn't work. But don't despair! I always define
the following:

(deftype list-of (elt-type)
(declare (ignore elt-type))
`list)

And then my code is full of things like `(list-of (integer 1 *))'.

In really dumb compilers this does nothing.

Smarter compilers at least know that the value is a list.

People reading my code know what I was intending.

And someday some Common Lisp compiler will actually support the notion
of homogeneous lists, and then I'll just change my definition of
`list-of' and without changing another line of code I'll be covered!
(And then I'll have to fix all the bugs that it exposes...)

--
Alan Bawden

TwirlwT

12/23/2015 9:59:00 PM

0

El miércoles, 23 de diciembre de 2015, 22:38:26 (UTC+1), Alan Bawden escribió:
> Jim Newton writes:
>
> > And I can probably extend that to have the type parameterized
> >
> > (deftype list-of (type)
> > `(or null (cons ,type (list-of ,type))))
> >
> > or maybe that's an infinite loop. Haven't tried it yet.
>
> As you expected, that doesn't work. But don't despair! I always define
> the following:
>
> (deftype list-of (elt-type)
> (declare (ignore elt-type))
> `list)
>
> And then my code is full of things like `(list-of (integer 1 *))'.
>
> In really dumb compilers this does nothing.
>
> Smarter compilers at least know that the value is a list.
>
> People reading my code know what I was intending.
>
> And someday some Common Lisp compiler will actually support the notion
> of homogeneous lists, and then I'll just change my definition of
> `list-of' and without changing another line of code I'll be covered!
> (And then I'll have to fix all the bugs that it exposes...)
>
> --
> Alan Bawden

This is how to define a type that denotes a list of numbers:

(defun is-list-of-numbers(l)
(every (lambda(x) (typep x 'number)) l))

(deftype list-of-numbers()
`(and list (satisfies is-list-of-numbers)))

CL-USER> (typep (list 10 20 30) 'list-of-numbers)
T
CL-USER> (typep (list 10 :a 30) 'list-of-numbers)
NIL

Pascal J. Bourguignon

12/23/2015 11:43:00 PM

0

Jim Newton <jimka.issy@gmail.com> writes:

> Common lisp has a type specifier operator CONS which can declare the car and cdr of a cons cell.
> e.g.,
>
> (defun F (x)
> (declare (type (cons number null)) x)
> ; x is a singleton list of a number
> ...)
>
> However, it is pretty common to have a list of homogeneous elements. E.g., a list of strings
> or a list of symbols. But there's no easy way to declare this except excessive use of (cons...)
> E.g., (cons number (cons number (cons number (cons number null)))) ; a list of 4 numbers.
>
> My guess is that even if there were a way to make such a declaration, it would be of
> dubious utility to the compiler or runtime environment.

No, it would be quite useful, given that a number of CL functions are
specified to take _proper_ lists, while some other can take dotted lists
(and rarely, circular lists).

Therefore having a proper-list or list for short type would be useful,
if the compiler could track values (ie. perform the needed global data
flow analysis).


> Is it perhaps conceivable that the compiler or runtime environment
> could take advantage of such a declaration given that cons cells are
> mutable.

The difficulty here is the presence of both mutation and multiple
threads. If the type of a value can be changed in another thread, the
compiler can infer few thingsâ?¦


> Any function who receives a reference to a list may modify any cons cell in it.
> It seems to me that there would be no way for the compiler to gain an advantage in such
> a declaration.

Yes, performing a global data flow analysis, the compiler could know
whether calling that function maintains the type of the value or not.
But only if it can prove that no other threads can modify the value, or
that it knows all the threads that can modify the value and how.

Clearly, that's beyond what compiler writers are willing to implement
(and customers willing to pay).


> Am I mistaken? Might there be some optimization a compiler could if the user could
> declare the :element-type of a list? Would it be possible for the system to prevent
> running code from breaking the declared promise via destructive functions?
>
> Of course there might be advantages of readability for humans to understand the intent
> of variables,

Definitely.

For human readability, and minimum checking, you can use the type
specifier:

`(or null (cons type list))


For example, to specify the type of slots implementing a relation, I
use:

(deftype list-of (type) `(or null (cons ,type list)))
(deftype relation-to (type multiplicity)
(if (multiple-multiplicity-p multiplicity)
`(list-of ,type)
`(or null ,type)))

ccl does check the values bound to instance slots, so this works nicely.

(defclass employee (person)
((employers :initform '() :type '(relation-to employer *))))


Of course, it breaks if the second element of the list is not of the
specified type.


> but my question is about the compiler, or runtime environment.

With CL, you can specify a proper-list type with a satisfies type specifier.

(defvar *proper-list-predicates* (make-hash-table))

(deftype proper-list (&optional (element-type t element-type-p))
(if element-type-p
(let ((predicate (gethash element-type *proper-list-predicates*)))
(unless predicate
(setf predicate
(setf (gethash element-type *proper-list-predicates*)
(compile (intern (concatenate 'string "PROPER-LIST-OF-"
(prin1-to-string element-type)
"-P"))
`(lambda (list)
(and (proper-list-p list)
(every (lambda (item)
(typep item ',element-type))
list)))))))
`(satisfies ,predicate))
`(satisfies proper-list-p)))

(typep '(1 2 3) '(proper-list integer))
;; --> t
(typep '(1 2.3 3) '(proper-list integer))
;; --> nil
(typep '(1 2.3 3) '(proper-list number))
;; --> t
(typep '(1 2 . 3) '(proper-list integer))
;; --> nil
(typep '(1 2 . #1=(4 5 . #1#)) '(proper-list integer))
;; --> nil


However, as you may note, SATISFIES types can be arbitrarily complex to
check, since they're involving arbitrary lisp code. In our case,
proper-list-p and every are O(n) with n being the number of cons cells
in the list.

Also, most CL implementations cannot compare SATISFIES types to other
types with SUBTYPEP. You can help some implementations to derive a
negative result by using:

`(or null cons (satisfies proper-list-p))

instead of:

`(satisfies proper-list-p)

Notice however that while most CL compilers only implement a minimum
effort for type deriving and type checking of complex types, in general
they can use them without restriction in TYPEP and CHECK-TYPE. So
it's not useless at all to define and use them.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Pascal J. Bourguignon

12/23/2015 11:44:00 PM

0

Operations <operations@ravenpack.com> writes:

> Not sure about the compiler or runtime, but you can certainly do the
> following.
>
> CL-USER(1): (deftype list-of-ints () '(or null (cons integer list-of-ints)))
> LIST-OF-INTS
> CL-USER(2): (typep (list 1 2 3) 'list-of-ints)
> T
> CL-USER(3): (typep (list 1 2.3 3) 'list-of-ints)
> NIL

Nope, not conforming. You're lucky that this works with this
implementation, but in general it will break. And even with your
implementation, it will probably break with other type operations than
typep.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Pascal J. Bourguignon

12/23/2015 11:46:00 PM

0

TwirlwT <danieltorridoverde@gmail.com> writes:

> El miércoles, 23 de diciembre de 2015, 22:38:26 (UTC+1), Alan Bawden escribió:
> This is how to define a type that denotes a list of numbers:
>
> (defun is-list-of-numbers(l)
> (every (lambda(x) (typep x 'number)) l))
>
> (deftype list-of-numbers()
> `(and list (satisfies is-list-of-numbers)))

Nope. This doesn't work because LIST is defined as (OR NULL CONS), and
EVERY expects a SEQUENCE, which is either a VECTOR or a PROPER-LIST.

Therefore (typep '(a b) 'list-of-numbers) will break.

See my other answer for a proper solution.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk