Limited Collections 
Author Message
 Limited Collections

I have a question about limited collections. Say I create a limited
collection over a particular class like the following:

  define class <person> (<object>)
  end class <person>;

  define constant <people> = limited(<vector>, of: <person>);

  define method test()
    let people = make(<people>, size: 2);
    people[0] := make(<person>);
  end method test;

When I've called 'make' on <people> without using the 'fill' keyword,
is this an error? By doing that, 'fill' will default to #f resulting
in an element of the collection not being a subclass of the element
type.

So if I create a limited collection of a specific type like the above,
I must either fill it with existing values of that type or use a
stretchy collection and add the elements.

I ask because HD 2 beta 2 behaves as I would expect. It signals an
exception when creating the limited vector saying #f is not of type
<person>. This broke existing code which worked under HD 1.2
presumably because limited collections of such types didn't enforce
the limits in that version.

Chris.



Mon, 24 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:

> When I've called 'make' on <people> without using the 'fill' keyword,
> is this an error? By doing that, 'fill' will default to #f resulting
> in an element of the collection not being a subclass of the element
> type.

> So if I create a limited collection of a specific type like the above,
> I must either fill it with existing values of that type or use a
> stretchy collection and add the elements.

I think that's right.

I don't see much advantage in using limited collections of user defined
classes like this.  There are some -- you can get a little bit of error
checking, and you know what type of element you're pulling off, which can
avoid dynamic dispatch afterwards, though no little more than just doing
an explicit type check would get you:

   let him :: <person> = people[0];

That's useful, but it's a pretty minor advantage of limited collections.
The big gains come, I think, from being able to store the data for all the
<person>s in one chunk in the vector instead of storing pointers to
zillions of individually-allocated objects.  I've been trying to think
about exactly this problem, and I think the compiler can only make this
optomisation if:

1) <person> has and can have no subclasses

2) <person> is "functional", so that it makes no difference if it is
sometimes passed around by value instead of by reference.

If you've got 1) but not 2) then the compiler can at least save space by
storing only a pointer and not a (type, valuePtr) pair in the array, which
is something at least...

If this seems wrong to someone, please tell me quick, because I'm probably
going to try to implement something along these lines in Gwydion
soonish...  And the *other* thing I need to check on is whether it makes
any sense to use limited collection types to specialise method arguments.
I don't think it does (unlike limited integers), but if it does then that
may make implementation rather harder and need rather more compiler
support.

-- Bruce



Mon, 24 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:

> I don't see much advantage in using limited collections of user defined
> classes like this.  There are some -- you can get a little bit of error
> checking, and you know what type of element you're pulling off, which can
> avoid dynamic dispatch afterwards, though no little more than just doing
> an explicit type check would get you:

Thanks Bruce. That's pretty much what I thought. I was using it in a
similar manner to using a C++ template collection class - a means of
ensuring only elements of that type could be stored and retrieved.

Quote:
> And the *other* thing I need to check on is whether it makes any
> sense to use limited collection types to specialise method
> arguments.  I don't think it does (unlike limited integers), but if
> it does then that may make implementation rather harder and need
> rather more compiler support.

In the DRM, under 'Uninstantiable Limited Collection Types' it
mentions (page 129 in my version):

  "Although limited types created from these classes cannot be
  instantiated, they are still useful as specializers."

On a quick scan, specialisation using limited collections exists in
some of the source shipped with HD as well.

Chris.



Mon, 24 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:
> -----Original Message-----


> Sent: Thursday, July 08, 1999 3:19 AM

> Subject: Limited Collections

> I have a question about limited collections. Say I create a limited
> collection over a particular class like the following:

>   define class <person> (<object>)
>   end class <person>;

>   define constant <people> = limited(<vector>, of: <person>);

>   define method test()
>     let people = make(<people>, size: 2);
>     people[0] := make(<person>);
>   end method test;

> When I've called 'make' on <people> without using the 'fill' keyword,
> is this an error? By doing that, 'fill' will default to #f resulting
> in an element of the collection not being a subclass of the element
> type.

Yes, that is an error.

Quote:
> So if I create a limited collection of a specific type like the above,
> I must either fill it with existing values of that type or use a
> stretchy collection and add the elements.

> I ask because HD 2 beta 2 behaves as I would expect. It signals an
> exception when creating the limited vector saying #f is not of type
> <person>. This broke existing code which worked under HD 1.2
> presumably because limited collections of such types didn't enforce
> the limits in that version.

The 1.2 implementation was a bug.  The elements of a limited collection are required to be of the element type.

The primary benefit of a limited collection is that the type of the elements is known.  This allows many optimizations in a compiler that does type inferencing (as HD does).  For some element types a more compact representation is also possible.  There's some additional information on this subject in the Optimization chapter of Dylan Programming.



Mon, 24 Dec 2001 03:00:00 GMT  
 Limited Collections
...

Quote:
> If the resulting object is then passed to a method, should it match a
> specialiser of "limited(<collection>, of: <boolean>)"?  Perhaps the user
> expects to get something that matches, but it clearly can't!  That makes
> sense in many ways, since the user didn't really get a limited collection.

> But what about if "make(limited(<vector>, of: <boolean>, size: 10))"
> returns an object or some implementation-private class: <boolean-vector>.
> This will be a subclass of <vector> and so will match method a specialiser
> of <vector>.  But will it match a specialiser of "limited(<collection>,
> of: <boolean>)"?  That seems tricky.

   Huh?  How can it not.

   "limited(<collection>, of: <boolean>)"  is an expression.  Just like any
   other type specifier.  That expression has to return some "value".  Encoded
   in that "type" should be something that matches the type of the instance returned by
   make.  It shouldn't matter what the context is;  an argument to make OR the specialier
   of a method.  The expression should return the same value in BOTH contexts.
   So how can the types be different?

   It shouldn't matter who defines the limited method.  This may mean there is
   some overhead at startup.  You have to evaluate those type expressions to determine
   all the types involved. But that's why they put the "Dy" in Dylan. ;-)

   The only cooperation needed seems to be for this limited expression to return an
   instantiable class.  In that case  make will create something of the
   exactly same type as the argument (i.e., make does something "sane".   Now if user
   "redefines" make to do  something insane then I suppose this won't work).

   it probably wouldn't be a good idea for limited to return an instantiable "abstract" class.
   That doesn't particularly make sense in conjunction with limited ( you're trying for
   to be as specific as possible).   However, the instanation of an "abstract" class
   should a subclass.  So the method should still applicable, just more broadly than
   neccessary.

---

Lyman



Mon, 24 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:
> [...]

> But limited() returns a type, not a class.  make() returns a member of a
> class.  Therefore the type of the instance returned by make(limited()) can
> not be the same as the type of limited().  In particular,
> make(limited(foo)) is allowed to return the same thing as make(foo) would.

> Furthermore, make() is likely to return objects of exactly the *same*
> class for a lot of different values of limited() passed to it.  For
> example, all limited vectors or objects that still need to live on the
> heap will use the exact same class, differing only in a slot holding the
> element type and a slot holding the size -- neither of which affects the
> type of the object.  

Not the result of object-class, certainly, but instance-specific properties
can change the non-class types for which instance? returns true for a given
object.

Quote:
> How can these be told apart by type descriminators?

By referring to that stored element type in instance? tests. The limited
integer type perhaps more intuitively suggests the idea that a type
inclusion test need not refer exclusively to the class hierarchy of the
instance being tested, but the same goes for limited collections.

-- Keith



Mon, 24 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:

> > And the *other* thing I need to check on is whether it makes any
> > sense to use limited collection types to specialise method
> > arguments.  I don't think it does (unlike limited integers), but if
> > it does then that may make implementation rather harder and need
> > rather more compiler support.

> In the DRM, under 'Uninstantiable Limited Collection Types' it
> mentions (page 129 in my version):

>   "Although limited types created from these classes cannot be
>   instantiated, they are still useful as specializers."

Ah, but I'm talking about the *Instantiable* Limited Collection types, not
the Uninstantiable ones...

Quote:
> On a quick scan, specialisation using limited collections exists in
> some of the source shipped with HD as well.

Really?  I'm curious as to how this can work.  I mean, if
"limited(<collection>, of: <boolean>)" is not instantiable (as it is not)
then there can exist no objects of that type.  What actual argument, then,
could match a specialiser of "limited(<collection>, of: <boolean>)"?  Only
an argument that is of a type that is an instantiable limited collection,
such as <vector>.  So let's move on to instantiable limited collections...

According to the DRM in...

<http://www.harlequin.com/products/ads/dylan/doc/drm/drm_69.htm>

"Some limited collection types are instantiable. make(limited(C, ...),
...) returns a direct instance of some subclass of C. Typically this class
is not standardized and its name is not exported, but it is valid for this
class to be C itself. There is nothing special about this class; it is
simply a class known to the applicable limited method [...]"

OK, so "make(limited(<vector>, of: <boolean>, size: 10))" is free to
simply punt and call "make(<vector>, size: 10)" (which will return a
<simple-object-vector>).

If the resulting object is then passed to a method, should it match a
specialiser of "limited(<collection>, of: <boolean>)"?  Perhaps the user
expects to get something that matches, but it clearly can't!  That makes
sense in many ways, since the user didn't really get a limited collection.

But what about if "make(limited(<vector>, of: <boolean>, size: 10))"
returns an object or some implementation-private class: <boolean-vector>.
This will be a subclass of <vector> and so will match method a specialiser
of <vector>.  But will it match a specialiser of "limited(<collection>,
of: <boolean>)"?  That seems tricky.  One can't name
"limited(<collection>, of: <boolean>)" (or even "limited(<vector>, of:
<boolean>, size: 10)") as a superclass.  If it is not required to match
such a specialiser then make on a singleton of "limited(<vector>, of:
<boolean>)" can in theory be provided by any ordinary library, or indeed
by the end user himself.  But if it is required to match a specialiser
then it seems to me that some special cooperation will be required from
the compiler.

And yet this would contradict the statement that "it is valid for this
class to be C itself".

Andrew Shalit, where are you when we need you? ;-)

-- Bruce



Tue, 25 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:


> ...
> > If the resulting object is then passed to a method, should it match a
> > specialiser of "limited(<collection>, of: <boolean>)"?  Perhaps the user
> > expects to get something that matches, but it clearly can't!  That makes
> > sense in many ways, since the user didn't really get a limited collection.

> > But what about if "make(limited(<vector>, of: <boolean>, size: 10))"
> > returns an object or some implementation-private class: <boolean-vector>.
> > This will be a subclass of <vector> and so will match method a specialiser
> > of <vector>.  But will it match a specialiser of "limited(<collection>,
> > of: <boolean>)"?  That seems tricky.

>    Huh?  How can it not.

>    "limited(<collection>, of: <boolean>)"  is an expression.  Just like any
>    other type specifier.  That expression has to return some "value".  Encoded
>    in that "type" should be something that matches the type of the

instance returned by

Quote:
>    make.  It shouldn't matter what the context is;  an argument to make
OR the specialier
>    of a method.  The expression should return the same value in BOTH
contexts.
>    So how can the types be different?

Yes, "limited()" will return the same type in both cases.

But limited() returns a type, not a class.  make() returns a member of a
class.  Therefore the type of the instance returned by make(limited()) can
not be the same as the type of limited().  In particular,
make(limited(foo)) is allowed to return the same thing as make(foo) would.

Furthermore, make() is likely to return objects of exactly the *same*
class for a lot of different values of limited() passed to it.  For
example, all limited vectors or objects that still need to live on the
heap will use the exact same class, differing only in a slot holding the
element type and a slot holding the size -- neither of which affects the
type of the object.  How can these be told apart by type descriminators?

-- Bruce



Tue, 25 Dec 2001 03:00:00 GMT  
 Limited Collections

Quote:
> [...]

> > On a quick scan, specialisation using limited collections exists in
> > some of the source shipped with HD as well.

> Really?  I'm curious as to how this can work.  I mean, if
> "limited(<collection>, of: <boolean>)" is not instantiable (as it is not)
> then there can exist no objects of that type.  

If there are instantiable subtypes of the type in question, then instances
can indeed exist. Which is good news, because <object> is not instantiable,
remember. 8)

Quote:
> What actual argument, then, could match a specialiser of "limited
> (<collection>, of: <boolean>)"?  Only an argument that is of a type that
> is an instantiable limited collection, such as <vector>.  

Exactly, limited(<vector>, of: <boolean>) is both instantiable and a subtype
of limited(<collection>, of: <boolean>), so instances of the former are
also instances of the latter.

Quote:
> [...]

> According to the DRM in...

> <http://www.harlequin.com/products/ads/dylan/doc/drm/drm_69.htm>

> "Some limited collection types are instantiable. make(limited(C, ...),
> ...) returns a direct instance of some subclass of C. Typically this class
> is not standardized and its name is not exported, but it is valid for this
> class to be C itself. There is nothing special about this class; it is
> simply a class known to the applicable limited method [...]"

> OK, so "make(limited(<vector>, of: <boolean>, size: 10))" is free to
> simply punt and call "make(<vector>, size: 10)" (which will return a
> <simple-object-vector>).

I think the statement you quote is unfortunately rather misleading - the above
punt is not valid. For example, later in the same section the DRM says:

  "Each element of an instance of a limited collection type must be an
   instance of the element type. Fetching an element of the collection is
   guaranteed to return an instance of the element type. Setting or
   initializing an element will check that the new element is an instance of
   the element type and signal an error of type <type-error> if it is not."

Because <simple-object-vector> won't do the appropriate checks, it isn't
a valid implementation class for limited(<vector>, of: <boolean>). Also,
<simple-object-vector> isn't a subtype of limited(<vector>, of: <boolean>)
according to the rules specified because the element type of the former is
<object>, not <boolean>.

Charitably, I'd say "it is valid for this class to be C itself" was
intended to be taken as "in certain situations, it is valid for this class to
be C itself" - i.e. only where this doesn't violate the rules.

I hope this clarifies things a little.

-- Keith



Tue, 25 Dec 2001 03:00:00 GMT  
 
 [ 9 post ] 

 Relevant Pages 

1. do limited collections work in d2c?

2. help understanding instances of limited collections

3. Limited Collection Type Disjointness

4. limited collections and subtype?

5. limited collections and subtype?

6. Collection of collections, how to collect?

7. collection inside a collection: how to selectively collect?

8. Extension of non-limited type needs limited component

9. Subtype of limited type non-limited?

10. limited/non-limited in Ada95

11. VAST: BIG collection

12. extracting sql query result from ordered collection

 

 
Powered by phpBB® Forum Software