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


 

Forums >

comp.lang.lisp

subtype of cons

Taoufik Dachraoui

1/9/2016 7:31:00 PM

Hi

I wish I can tag a cons object to be of foo type as shown below:

(let ((a (cons 1 2)) (b (cons 2 3)))
(tag a 'foo)
(values (car a) (cdr a) (type-of a) (type-of b))
->
1
2
FOO
CONS

Any thoughts?

Kind regards
Taoufik
12 Answers

Taoufik Dachraoui

1/9/2016 8:07:00 PM

0

On Saturday, January 9, 2016 at 8:31:06 PM UTC+1, Taoufik Dachraoui wrote:
> Hi
>
> I wish I can tag a cons object to be of foo type as shown below:
>
> (let ((a (cons 1 2)) (b (cons 2 3)))
> (tag a 'foo)
> (values (car a) (cdr a) (type-of a) (type-of b))
> ->
> 1
> 2
> FOO
> CONS
>
> Any thoughts?
>
> Kind regards
> Taoufik

Currently I am using one extra cons to tag the sparse-a structure as follows:

(defun make-sparse-a () (cons *tag-sparse-a* (cons nil nil)))
(defun sparse-a-p (a) (and (consp a) (eq (car a) *tag-sparse-a*)))

But this incurs an extra cons

Kind regards
Taoufik

Taoufik Dachraoui

1/9/2016 8:33:00 PM

0

On Saturday, January 9, 2016 at 8:31:06 PM UTC+1, Taoufik Dachraoui wrote:
> Hi
>
> I wish I can tag a cons object to be of foo type as shown below:
>
> (let ((a (cons 1 2)) (b (cons 2 3)))
> (tag a 'foo)
> (values (car a) (cdr a) (type-of a) (type-of b))
> ->
> 1
> 2
> FOO
> CONS
>
> Any thoughts?
>
> Kind regards
> Taoufik

Again here is the code I am using currently, but would like to find a better solution that is more
efficient (better performance without incurring the extra cons):

(setf *print-pretty* t)

(defun make-sparse-a ()
(cons :SPARSE-A
(cons nil nil)))
(defun sparse-a-p (a) (and (consp a) (eq :SPARSE-A (car a))))
(deftype sparse-a () '(satisfies sparse-a-p))

(set-pprint-dispatch
'sparse-a
(lambda (stream a)
(declare (ignore a))
(format stream "#<SPARSE-A>")))

Kind regards
Taoufik

Alberto Riva

1/9/2016 9:32:00 PM

0

On 01/09/2016 03:07 PM, Taoufik Dachraoui wrote:
> On Saturday, January 9, 2016 at 8:31:06 PM UTC+1, Taoufik Dachraoui wrote:
>> Hi
>>
>> I wish I can tag a cons object to be of foo type as shown below:
>>
>> (let ((a (cons 1 2)) (b (cons 2 3)))
>> (tag a 'foo)
>> (values (car a) (cdr a) (type-of a) (type-of b))
>> ->
>> 1
>> 2
>> FOO
>> CONS
>>
>> Any thoughts?
>>
>> Kind regards
>> Taoufik
>
> Currently I am using one extra cons to tag the sparse-a structure as follows:
>
> (defun make-sparse-a () (cons *tag-sparse-a* (cons nil nil)))
> (defun sparse-a-p (a) (and (consp a) (eq (car a) *tag-sparse-a*)))
>
> But this incurs an extra cons

Do you *really* need to use a cons? Couldn't you use a structure? I
expect the overhead would be pretty small...

Alberto

Marco Antoniotti

1/10/2016 9:52:00 AM

0

On Saturday, January 9, 2016 at 10:31:36 PM UTC+1, Alberto Riva wrote:
> On 01/09/2016 03:07 PM, Taoufik Dachraoui wrote:
> > On Saturday, January 9, 2016 at 8:31:06 PM UTC+1, Taoufik Dachraoui wrote:
> >> Hi
> >>
> >> I wish I can tag a cons object to be of foo type as shown below:
> >>
> >> (let ((a (cons 1 2)) (b (cons 2 3)))
> >> (tag a 'foo)
> >> (values (car a) (cdr a) (type-of a) (type-of b))
> >> ->
> >> 1
> >> 2
> >> FOO
> >> CONS
> >>
> >> Any thoughts?
> >>
> >> Kind regards
> >> Taoufik
> >
> > Currently I am using one extra cons to tag the sparse-a structure as follows:
> >
> > (defun make-sparse-a () (cons *tag-sparse-a* (cons nil nil)))
> > (defun sparse-a-p (a) (and (consp a) (eq (car a) *tag-sparse-a*)))
> >
> > But this incurs an extra cons
>
> Do you *really* need to use a cons? Couldn't you use a structure? I
> expect the overhead would be pretty small...
>
> Alberto

The overhead is probably *less* in most implementations.

--
MA

rpw3

1/10/2016 10:57:00 AM

0

Alberto Riva <alb@nospam.chip.org> wrote:
+---------------
| > Taoufik Dachraoui wrote:
| > Currently I am using one extra cons to tag the sparse-a structure
| > as follows:
| > (defun make-sparse-a () (cons *tag-sparse-a* (cons nil nil)))
| > (defun sparse-a-p (a) (and (consp a) (eq (car a) *tag-sparse-a*)))
| > But this incurs an extra cons
|
| Do you *really* need to use a cons? Couldn't you use a structure?
| I expect the overhead would be pretty small...
+---------------

Indeed. But even if he insists on using conses he could
still benefit from using DEFSTRUCT to provide the constructor,
predicate, & accessor functions automatically, e.g.:

> (defstruct (sparse-a (:type list) :named)
first
second)

SPARSE-A
> (defparameter *x* (make-sparse-a :first 123 :second 456))

*X*
> *x*

(SPARSE-A 123 456)
> (sparse-a-p *x*)

T
> (sparse-a-second *x*)

456
>

Of course, the result is *still* just a list of conses:

> (type-of *x*)

CONS
>

But he could later remove the options and get a real structure
[which is internally a vector-like object] without having to
change the code for the constructor/predicate/accessors, but
now you have a distinct type:

> (defstruct sparse-a
first
second)

SPARSE-A
> (defparameter *x* (make-sparse-a :first 123 :second 456))

*X*
> *x*

#S(SPARSE-A :FIRST 123 :SECOND 456)
> (sparse-a-p *x*)

T
> (sparse-a-second *x*)

456
> (type-of *x*)

SPARSE-A
>


-Rob

-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <http://rpw...
San Mateo, CA 94403

Pascal J. Bourguignon

1/10/2016 1:40:00 PM

0

Taoufik Dachraoui <dachraoui.taoufik@gmail.com> writes:

> Hi
>
> I wish I can tag a cons object to be of foo type as shown below:
>
> (let ((a (cons 1 2)) (b (cons 2 3)))
> (tag a 'foo)
> (values (car a) (cdr a) (type-of a) (type-of b))
> ->
> 1
> 2
> FOO
> CONS
>
> Any thoughts?

To do exactly that, you will need either:

- to patch an implementation,

- to re-implement cons conformingly (and therefore, the lisp printer,
the lisp reader, all the sequence, list and cons functions, etc).


Use a structure:

(defstruct (kons
(:type list)
:named
(:conc-name nil)
(:constructor kons (kar kdr)))
kar kdr)

(defstruct (foo
(:include kons)
(:constructor foo (kar kdr))))

(defstruct (bar
(:include kons)
(:constructor bar (kar kdr))))

(make-foo) --> (foo nil nil)
(foo 1 2) --> (foo 1 2)
(first (foo 1 2)) --> foo
(foo-p (foo 1 2)) --> t
(first (bar 3 4)) --> bar
(bar-p (bar 3 4)) --> t


(foo-p (foo 1 2)) --> t
but:
(type-of (foo 1 2)) --> cons


Or:

(defstruct (kons
(:conc-name nil)
(:constructor kons (kar kdr)))
kar kdr)

(defstruct (foo
(:include kons)
(:constructor foo (kar kdr))))

(defstruct (bar
(:include kons)
(:constructor bar (kar kdr))))


(values (foo 1 2)
(type-of (foo 1 2))
(foo-p (foo 1 2))
(type-of (bar 3 4))
(bar-p (bar 3 4)))
--> #S(foo :kar 1 :kdr 2)
foo
t
bar
t

--
__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

1/10/2016 1:43:00 PM

0

Marco Antoniotti <marcoxa@gmail.com> writes:

> On Saturday, January 9, 2016 at 10:31:36 PM UTC+1, Alberto Riva wrote:
>> On 01/09/2016 03:07 PM, Taoufik Dachraoui wrote:
>> > On Saturday, January 9, 2016 at 8:31:06 PM UTC+1, Taoufik Dachraoui wrote:
>> >> Hi
>> >>
>> >> I wish I can tag a cons object to be of foo type as shown below:
>> >>
>> >> (let ((a (cons 1 2)) (b (cons 2 3)))
>> >> (tag a 'foo)
>> >> (values (car a) (cdr a) (type-of a) (type-of b))
>> >> ->
>> >> 1
>> >> 2
>> >> FOO
>> >> CONS
>> >>
>> >> Any thoughts?
>> >>
>> >> Kind regards
>> >> Taoufik
>> >
>> > Currently I am using one extra cons to tag the sparse-a structure as follows:
>> >
>> > (defun make-sparse-a () (cons *tag-sparse-a* (cons nil nil)))
>> > (defun sparse-a-p (a) (and (consp a) (eq (car a) *tag-sparse-a*)))
>> >
>> > But this incurs an extra cons
>>
>> Do you *really* need to use a cons? Couldn't you use a structure? I
>> expect the overhead would be pretty small...
>>
>> Alberto
>
> The overhead is probably *less* in most implementations.

Nope.

A structure will have to have a pointer to the structure class.
So:
(defstruct tagged-cons
tag
cons)

will take at least as much space than a mere cons.
If you consider that defstruct also defines new accessors, predicate,
copiers, and constructors, and must book-keep the structure type and
class, you will see that is orders of magnitudes more costly than using
a mere cons.

You can have defstruct use a mere cons with the option (:type list), and
adding other options to disable the predicate, the copiers, etc. But
this will always be a little more costly than the pre-existing cons
cells, for a single new field.


--
__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

smh

1/10/2016 3:14:00 PM

0

You may not yet have grasped everything about the CL type system.

On Saturday, January 9, 2016 at 11:31:06 AM UTC-8, Taoufik Dachraoui wrote:
> I wish I can tag a cons object to be of foo type as shown below:
>
> (let ((a (cons 1 2)) (b (cons 2 3)))
> (tag a 'foo)
> (values (car a) (cdr a) (type-of a) (type-of b))
> ->
> 1
> 2
> FOO
> CONS

(type-of (cons 1 2)) can return FOO iff foo has been defined appropriately using deftype. See the "recognizable subtype" requirement on the dictionary page for type-of.

Now, if the deftype were in effect, then the above type-of form _could_ return any of these:

FOO ; iff an appropriate deftype is in force
CONS
(CONS FIXNUM)
(CONS (MOD 37) (INTEGER 2 2))
(CONS (EQL 1) (MEMBER 2 4 6 8))

But most implementations will return simple CONS. There are good reasons. type-of might be used in speed-critical dispatch. Usually all user code wants is CONS, so consing up a more verbose type specifier is wasteful. Finally, there is a semantic problem returning a deftype type.

Suppose we have these _two_ deftypes:

(deftype foo () '(cons (mod 256) (mod 256)))
(deftype bar () '(cons (member 1 3 5 7 9 1027) (member 2 4 6 8 10)))

then which should (type-of (cons 1 2)) return? The cons is an element of both types, and neither is a subset of the other.

While X3J13 did tighten the restrictions on TYPE-OF, history and usual practice come into consideration. For non-complex numbers and for most other built-in types, implementations have customarily returned an atomic type symbol. For arrays (simple or non-simple) they have included the upgraded element-type and dimensions. That is what user code has come to expect. I don't remember anything in the ANS that spells this out.

Pascal Costanza

1/10/2016 3:21:00 PM

0

On 09/01/2016 21:32, Taoufik Dachraoui wrote:
> On Saturday, January 9, 2016 at 8:31:06 PM UTC+1, Taoufik Dachraoui wrote:
>> Hi
>>
>> I wish I can tag a cons object to be of foo type as shown below:
>>
>> (let ((a (cons 1 2)) (b (cons 2 3)))
>> (tag a 'foo)
>> (values (car a) (cdr a) (type-of a) (type-of b))
>> ->
>> 1
>> 2
>> FOO
>> CONS
>>
>> Any thoughts?
>>
>> Kind regards
>> Taoufik
>
> Again here is the code I am using currently, but would like to find a better solution that is more
> efficient (better performance without incurring the extra cons):
>
> (setf *print-pretty* t)
>
> (defun make-sparse-a ()
> (cons :SPARSE-A
> (cons nil nil)))
> (defun sparse-a-p (a) (and (consp a) (eq :SPARSE-A (car a))))
> (deftype sparse-a () '(satisfies sparse-a-p))
>
> (set-pprint-dispatch
> 'sparse-a
> (lambda (stream a)
> (declare (ignore a))
> (format stream "#<SPARSE-A>")))

If almost all your conses are of a particular type, and only some
exceptions deviate from that, you could use an external hash table to
record the exceptions, and otherwise assume a default type. This depends
a lot on your application, of course.

Pascal

--
My website: http:/...
Common Lisp Document Repository: http://cdr.eu...
Closer to MOP & ContextL: http://common-lisp.net/proje...
The views expressed are my own, and not those of my employer.

Taoufik Dachraoui

1/10/2016 9:50:00 PM

0

On Sunday, January 10, 2016 at 4:14:05 PM UTC+1, smh wrote:
> You may not yet have grasped everything about the CL type system.
>
> On Saturday, January 9, 2016 at 11:31:06 AM UTC-8, Taoufik Dachraoui wrote:
> > I wish I can tag a cons object to be of foo type as shown below:
> >
> > (let ((a (cons 1 2)) (b (cons 2 3)))
> > (tag a 'foo)
> > (values (car a) (cdr a) (type-of a) (type-of b))
> > ->
> > 1
> > 2
> > FOO
> > CONS
>
> (type-of (cons 1 2)) can return FOO iff foo has been defined appropriately using deftype. See the "recognizable subtype" requirement on the dictionary page for type-of.
>
> Now, if the deftype were in effect, then the above type-of form _could_ return any of these:
>
> FOO ; iff an appropriate deftype is in force
> CONS
> (CONS FIXNUM)
> (CONS (MOD 37) (INTEGER 2 2))
> (CONS (EQL 1) (MEMBER 2 4 6 8))
>
> But most implementations will return simple CONS. There are good reasons.. type-of might be used in speed-critical dispatch. Usually all user code wants is CONS, so consing up a more verbose type specifier is wasteful. Finally, there is a semantic problem returning a deftype type.
>
> Suppose we have these _two_ deftypes:
>
> (deftype foo () '(cons (mod 256) (mod 256)))
> (deftype bar () '(cons (member 1 3 5 7 9 1027) (member 2 4 6 8 10)))
>
> then which should (type-of (cons 1 2)) return? The cons is an element of both types, and neither is a subset of the other.
>
> While X3J13 did tighten the restrictions on TYPE-OF, history and usual practice come into consideration. For non-complex numbers and for most other built-in types, implementations have customarily returned an atomic type symbol. For arrays (simple or non-simple) they have included the upgraded element-type and dimensions. That is what user code has come to expect. I don't remember anything in the ANS that spells this out.

I already defined a type for sparse-a as follows:

(defun sparse-a-p (a) (and (consp a) (eq :SPARSE-A (car a))))
(deftype sparse-a () '(satisfies sparse-a-p))

I use (typep obj 'sparse-a) or (sparse-a-p obj) ; (type-of (make-sparse-a)) -> CONS
so I do not use type-of; I was initially surprise to see CONS in response to (type-of (make-sparse-a)
but now I understand, thanks.

I thought of using a hash table to store all sparse-a objects but this has an unacceptable overhead
for my application.

Kind regards
Taoufik