Re: associative array, container, mapping, terminology

phil-news-nospam@xxxxxxxx writes:

On 11 Feb 2009 09:56:26 -0800 Tim Rentsch <txr@xxxxxxxxxxxxxxxxxxx> wrote:

| Just to clarify - the question is phrased in terms of whether values
| all have the same /type/ or may have different /types/, but what
| you're meaning to ask about is whether the values are all instances of
| the same /class/ or may be instances of different /classes/, right?

That distinction may be specific to languages.

The specific words used vary from language to language, but the
conceptual difference is language independent.


| To put this in C terms, I think the situation you're asking about (for
| the first case) is something along these lines:
|
| struct value_prefix {
| unsigned what_kind;
| };
|
| struct key_and_value {
| char *key; /* keys are strings here */
| struct value_prefix *value;
| };
|
| struct value_0 {
| struct value_prefix tag;
| /* other value_0 structure members here */
| };
|
| struct value_1 {
| struct value_prefix tag;
| /* other value_1 structure members here */
| };
|
| ...
|
| struct value_prefix *p = some_key_and_value.value_prefix;
| switch( p->what_kind ){
| case 0: struct value_0 *v0 = (struct value_0*)p;
| ...
| break;
| case 1: struct value_1 *v1 = (struct value_1*)p;
| ...
| break;
| ...
| }

I don't follow what you are doing here, so I can't say either yes or now.


| Note that, in the dictionary (or association, or mapping, whatever),
| all values have the same /type/, namely (struct value_prefix*). But
| the pointers point at different kinds of /objects/. This situation
| resembles what you're meaning to ask about, yes?

I don't know what you mean by values (of the same type) and pointers.
If what I get when doing a lookup in a association/containter/dictionary
is a pointer, I see that as a kind of type, but also specific to what it
points to. E.g. a pointer to one kind of struct and a pointer to a
different kind of struct I consider to really be two different types.
In C, such pointers would be defined as such (struct a *x; struct b *y;).

The struct used to hold the pointer to the "value" portion of the
association has a fixed type (in the C sense of the word type).
At run-time, a value pointer would point to different kinds of objects,
but which kind isn't known at compile time, only at run-time.
The "kind" of an object is referred to its /class/, or sometimes
as its /run-time type/, but which term is used isn't so important
as the property that, whatever we call this aspect, it's known
only at run-time, not at compile time.


| The distinction is important, because if one notion is a compile-time
| notion, and the other notion is a run-time notion. What you're
| asking about is values of different run-time kinds, not about values
| of different compile-time kinds -- right?

I wrote a mapping (association/containter/dictionary) library in C. The way
it is presently designed, the creation of a new mapping requires a commitment
to use a specific type as the key. Only that key type can be used with that
mapping. It is thus "key homogenous" to construct a term. They way this
library is designed, the act of creating a new entry is separate from the act
of storing a value into an entry. There is an insert operation, given a key.
It succeeds of the insertion was possible (one variation of the insert allows
multiple entries with the same key). Once the insert is done, that entry is
now the active entry. Thus the mapping has a cursor. I can then use any of
the functions to store data into the mapping. Each of these functions is
specific to the types being stored. There's one for storing an int. There's
another for storing a float. There are many others. What type is being stored
is also stored, so that it can be determined later. When a lookup is done and
is found, that found entry becomes active. A store could be done to replace
its value. Or a fetch could be done to extract its value. The actual lookup
returned the type (or a status existing but never stored into, or failure).

Using just slightly different terminology, your storage function will
store different kinds of object values, and it remembers what kind of
object value it stored. What kind of value is stored for a particular
key (or entry?) is known only at run-time, not at compile-time. The
differentation that occurs is a run-time differentiation, not a
compile-time one.


This is a run time distinction of type in the sense that any entry could have
any type decided at run time. There is a compile time aspect to it because
there are different functions to deal with different types. It's not a case
of all types being stored or fetched as data are using the same function across
all these possible types. The functions are thus declared with specific types
in the argument list, or as return values, or as pointers in the argument list
where the values are to be stored or fetched.

So there are compile-time type-specific functions to store different
kinds of objects (so the functions have static typing), but the
data structure itself allows storing different kinds of objects,
with what kind of object will be stored being a run-time parameter,
not a compile-time constraint -- right?


But the point here is one instance of a mapping can have only the same type of
key, but can have different types of data. One ENTRY in a mapping can only
have one type of value.

I take this to mean an individual entry can remember only one kind of object
value at any one time. At some later point in time, that entry might
remember an object value of a different kind, yes?


I'm studing expanding this library so that it will not only support a wider
range of types, focusing on programmer defined structs, but also have the
basic variations of allowing mappings to either have a homogenous key type
or have a heterogenous key type (allowing more than one key type in the same
mapping). I also want to add homogenous data types (the implementation can
be slightly optimized for this case). This means I can have 4 different basic
varations of mappings, and within thise that have homogenous key and/or data,
there would be sub-variations based on what specific key and/or data type is
chosen.

Suppose we decided to represent keys thusly:

struct abstract_key_s;
typedef struct abstract_key_s *Key;
struct abstract_key_s {
unsigned long key_kind; /* for key object's internal use */
unsigned long (*hash)( Key ); /* hash value function for this key */
int (*compare( Key, Key )); /* determine ordering of two keys */
};

This representation allows the association data structure code
to use a single type for keys, but accommodates keys of many
different kinds ("heterogeneous" keys). However, at this level,
these abstract keys accommodate all the flexibility we need,
and the abstract keys have just one type (in the sense that
the calling code for the association code never needs to do
any type conversion, just call functions). What's important
about this is that, although it is heterogeneous at a lower
level, at the level of the association data structure itself,
keys are homogeneous. If you're intending to talk about
the data structure code, the higher level perspective (that
is, homogeneous) is important; whereas, if you're intending
to talk about what sorts of things are held, the lower level
perspective (that is, heterogeneous) is important. And if
it's important to talk about both levels, then keys will be
homogeneous in one part of the discussion and heterogeneous
in another. So an essential question is, at what level
will the presentation occur, because different levels
result in different descriptions.


What I am basically looking for HERE in this newsgroup is terminology.
Are there different terms I can use for a mapping or association or
container or dictionary that has:

1. Homogenous keys and homogenous data
2. Homogenous keys and heterogenous data (what I have now)
3. Heterogenous keys and homogenous data
4. Heterogenous keys and heterogenous data

... without having to spell out these specific combinations.

Yes, I understood that the question you were asking is a question
about terminology. Before trying to give an answer I wanted to make
sure it was understood what question is being asked. Values that
are homogeneous at one level can be heterogeneous at another level
(or the other way around); so in asking the question, it's important
not only to describe the situation, but also to say at what level(s)
you want to talk about the values (and/or keys) involved.
.

Relevant Pages

  • [PATCH 13/24] CRED: Separate per-task-group keyrings from signal_struct [ver #7]
    ... from the cred struct rather than the signal_struct. ... #ifdef CONFIG_SECURITY ... * copy the keys in a thread group for fork without CLONE_THREAD ...
    (Linux-Kernel)
  • VC6 -> VC2005 conversion problem
    ... struct SHomog ... static void CrossProduct(const SPoint& p, const SPoint& q, SHomog& r) ... returns number of keys ... enabled, disable normalization ...
    (microsoft.public.vc.mfc)
  • Re: associative array, container, mapping, terminology
    ... |> different kind of struct I consider to really be two different types. ... | but which kind isn't known at compile time, ... With homogenous keys and heterogenous data, my structs have the key appended ... I'm looking at having a mapping that is homogenous keys and homogenous data, ...
    (comp.programming)
  • Re: USB keyboard problem
    ... The keyboard_t struct kbd is passed to the ukbd_interrupt ... ukbd driver but within the mechanism that fills in ks_ndata. ... Once this has been done, a majority of the keys (a-z, 1-0 ... have found that when you hit any of the modifier keys, ...
    (freebsd-hackers)
  • Re: associative array, container, mapping, terminology
    ... | struct key_and_value { ... I wrote a mapping library in C. ... of storing a value into an entry. ... varations of mappings, and within thise that have homogenous key and/or data, ...
    (comp.programming)