Container library progress

[gwowen]

If "objects" means object oriented programming the answer is surely NO.

Data and methods encapsulated together. That's an object, by every
definition I've ever heard. There's no data hiding, and no
polymorphism, but they're still objects. Objects with ugly syntax and
no language support are still objects.

 

[Julienne Walker]

if someone wants container classes I don't see the problem in pointing
them in the direction of C++.

Jacob's project is specific to C (as stated in the goals, IIRC)
because it fills a hole that C's standard library leaves open. If I
ask for a container library *in C*, or want to write a library *for
C*, directing me to another language because that other language
happens to have a similar feature is nonsensical. Java has container
classes too, should we direct people there as well? ;-)

 

[gwowen]

So are ints and chars and floats.

Only in standardese, not in common computer science usage.

 

[gwowen]

Compiler writers were calling them objects long before OOP was a mere
twinkle in Alan Kay's eye.

And data analysts were referring to their number-crunching secretaries
as "computers" before Alan Turing had heard of the Enigma machine.
Language is funny like that.

 

[jacob navia]

gwowen a écrit :

Data and methods encapsulated together. That's an object, by every
definition I've ever heard.

Yes, that is one part of object oriented programming.

But inheritance and classes are as essential to it as are methods.

I do not want to denigrate OO programming. There are some useful usages, for instance
in GUI programming, and where a hierarchical view of the data is appropiate.

Here in the container library I do not see any big hierarchy.

If you look at the way they are traversed there are just groups
of similar containers:

(1) Sequential containers. Here we have a meaning for "Next", "Previous", and they
can be seen as a sequence of some kind of object
(2) Associative containers like hashtables or trees where you associate a key with some
data. There are no meanings to "next" oder "previous"

If you look at the contents you can have

(1) Abstract containers that work with void pointers
(2) Concrete containers where the members are fixed: int lists, double vectors, etc.

If you look at whether you can have duplicates or not you have sets or multisets,
etc.

I am sure we could go on classifying things, and in some situations some classifications
could be useful in another situations they could be a hindrance.

That is why I do not try to over-classify containers in some way. Obviously bitstrings
are a specialization of a vector, it would not be very useful to store each bit in a
doubly linked list for instance ... even if it could be done.

As you can see, object oriented programming doesn't apply here specially well.
But it could be a way of describing things. If you have a classification in mind
be free to propose it

There's no data hiding, and no
polymorphism, but they're still objects.

There is a limited polymorphism since I will group all common methods to sequential
containers at the same place for the different container vtables so that you will
access the same position when using them. This makes the client code independent
of the specific sequential container used and allow easy migration from one container
to a different one.

Objects with ugly syntax and
no language support are still objects.

"Ugly" is in th eyes of the person making that judgement... What is ugly for you is
beautiful for me. No longer we have some language abstraction that interposes
between you and what you are doing. YOU are the one doing everything, there is
PRECISELY no language support what gives you an absolute freedom of expression.

YOU CAN DO WHAT YOU WANT. No limits.

This is the C language

 

[gwowen]

gwowen a écrit :

Yes, that is one part of object oriented programming.
But inheritance and classes are as essential to it as are methods.

Not really. Polymorphism pretty much requires object orientation, but
the converse is simply not true.

(1) Sequential containers. Here we have a meaning for "Next", "Previous", and they can be seen as a sequence of some kind of object

So you have a bunch of similar-but-different things that present the
same interface to the outside world, based on their commonalities.
Congratulations, you're doing object oriented programming. The notion
of "Sequential container" here functions as an abstract base class/
interface (call it what you will).

(2) Associative containers like hashtables or trees where you associate a key with some data. There are no meanings to "next" oder "previous"

So you have a bunch of similar-but-different things that present the
same interface to the outside world, based on their commonalities.
Congratulations, you're doing object oriented programming. The notion
of "Associative container" here functions as an abstract base class/
interface (call it what you will).

 

[jacob navia]

gwowen a écrit :

Not really. Polymorphism pretty much requires object orientation, but
the converse is simply not true.


So you have a bunch of similar-but-different things that present the
same interface to the outside world, based on their commonalities.
Congratulations, you're doing object oriented programming. The notion
of "Sequential container" here functions as an abstract base class/
interface (call it what you will).


So you have a bunch of similar-but-different things that present the
same interface to the outside world, based on their commonalities.
Congratulations, you're doing object oriented programming. The notion
of "Associative container" here functions as an abstract base class/
interface (call it what you will).

My argument was that according to what FEATURE of the container you
treat as important you arrive at several *different* classifications.

If you classify by access to elements you have sequential/associative
for instance

If you classify by what object is stored you have abstract containers
with void * or concrete ones like bit strings

The purpose of my post was that there is no single evident classification.

Your answer skips that discussion entirely and you take examples
to prove...

well WHAT?

 

[jacob navia]

Gareth Owen a écrit :

The purpose of my post was that there is no single evident classification.

The commonality between associative containers and sequential containers
is that they're containers. The single classification is "container".
The common interface is "Given a key (of some type) extract the element
(of some type) indexed by that key". Wheteher you call it getElement(),
operator[] or something else is not important.

Container
/ \
Associative Sequential
Container Container
/ \ / \
Hashtable RBTree Vector List (examples only)

Now, what would an associative and sequential containers have in common?

The access methods are completely different. In a sequential container you access
them by index in the sequence, in an associative container you access them by
key. I do not see what the "Container" abstraction buy us in common behavior.

And with another criteria (classifying by stored data) I could draw:

Container
/ \
Abstract Concrete
/ \
/ \
Any object Numeric: integers, doubles
boolean: bitstrings
Composite structures, containers, etc

And there are probably OTHER ways to classify containers, using another feature
as the basis for the clasification.

Container
/ | \
/ | \
Read Only | Read/Write
|
Write only

A container is write only when created (it doesn't contain anything), it becomes
read/write when filling it, and can become read-only when no more data
should be stored in it.

That what you're doing is, in essence, object-oriented (and even a
little bit polymorphous).

You're encapsulating methods and data together. That's pretty much the
definition of object orientation.

OK. If you want, I do not really care since I am NOT against OO programming.
Well, as long as it is done in C!

You're grouping by commonality and presenting common interface (not a
single common interface, two distinct common interfaces
"SequentialContainer" and "AssociativeContainer"). That's subtyping.

If you want, OK.

You don't call it subtyping, because the interface definition does not
exist in code (no language support), but that's what it is.

Fine with me.

You've separated interface and implementation.

Well, I am doing that since I learned programming. I mean separating interface
and implementation, abstraction, grouping common functions is the basis of
software engineering. Yes, OO programming does that, but C programming does that
too, and I figure that even assembly language programming can do that too.

Those are general concepts.

In Java (for example) you'd write

public class Vector implements SequentialContainer ...
public class HashTable implements AssociativeContainer ...
public class RedBlackTree implements AssociativeContainer ...

To deny that what you're doing is object orientated (as you have
repeatedly done) is simply incorrect.

OK. If you want, I agree with that.

You can do OO programming in C. There is no language support, and you
are not constrained to do OO programming within a fixed language framework.

You can do as you want, classify as you want, you are completely free to do as you
think it is best for your application.

 

[Nick Keighley]

Not really.  Polymorphism pretty much requires object orientation, but
the converse is simply not true.

I think there are more forms of polymorphism than you think.

double x, y, z;
int i, j, k;

k = i + j;
z = x + y;

isn't + being polymorphic?

So you have a bunch of similar-but-different things that present the
same interface to the outside world, based on their commonalities.
Congratulations, you're doing object oriented programming.  

without inheritance I think it's usually called Object Based
Programming

The notion
of "Sequential container" here functions as an abstract base class/
interface (call it what you will).

what Jacob is doing is what I do when i want to emulate OO in C (which
is a bit like trying to shove half a a pound of melted butter up a
hedgehog's bottom with a red hot needle). You've got a constructor
that builds objects which contain data and the function pointers
provide virtual methods.

 

[gwowen]

double x, y, z;
int i, j, k;

k = i + j;
z = x + y;

isn't + being polymorphic?

Erm... Good question. I don't really have a firm handle on what
polymorphic means applied to operators. "Overloaded" certainly.
Would you consider overloading to be the same as polymorphic?

without inheritance I think it's usually called Object Based
Programming

I completely accept that distinction.

 

[gwowen]

The access methods are completely different.

No, they're not. Or rather, the implementations might be wildly
differnt, but conceptually, they're the same.

In a sequential container you accessthem by index in the sequence, in an associative container you access them by key.

The index in the sequence IS (conceptually) the key.

 

[jacob navia]

What I said:

You can do OO programming in C. There is no language support, and you
are not constrained to do OO programming within a fixed language framework.

You can do as you want, classify as you want, you are completely free to do as you
think it is best for your application.

What Nick Keighley understood :

what Jacob is doing is what I do when i want to emulate OO in C (which
is a bit like trying to shove half a a pound of melted butter up a
hedgehog's bottom with a red hot needle).

Mr Keighley thinks using this kind of language is funny, and probably is very
proud of it.

But what is important to understand is that all OO frameworks and most other
languages give you that: a FRAMEWORK where you should fit your ideas. This is
very good if your needs fit tightly in the framework.

In most cases, they don't and then... well then you find yourself

> trying to shove half a a pound of melted butter up a
> hedgehog's bottom with a red hot needle.

and it is your fault since you could have done it in C.

 

[gwowen]

"Operator" is a posh word for "function".

Sure. What I meant was "I don't really have a firm handle on what
polymorphic means applied to operators and functions, at least if its
a different concept to overloading."

 

[Keith Thompson]

Sure. What I meant was "I don't really have a firm handle on what
polymorphic means applied to operators and functions, at least if its
a different concept to overloading."

I think the term polymorphism usually refers to something that's
resolved at run time. For example, if you have a pointer to a foo and
you pass it to func(), you might invoke a different implementation of
func() depending on what kind of foo you're pointing to.

Overloading is resolved at compile time.

 

[jacob navia]

Richard Harter a écrit :

That depends upon how one conceptualizes.

In the elemental interface to a simple sequence there is no index
as such. There is only current, next, and previous. It is quite
true that you can create an index but to do that you need a base
point. That is, you can pick any item in the list mark and call
it item n. Then the previous item has index n-1, the next has
index n+1, and so on.

Adding a base point to a simple sequence makes it a virtual array
for which an index can serve as a key. Without the inclusion of
a base point the properties of sequential containers and
associative containers are significantly different. Even if we
do add a base point insertions and deletions have fundamentally
different properties. For example, in an associative container
insertion and deletion does not alter the key-value relationship.
In a sequential container insertion and deletion does alter the
index-value relationship.

That is a fundamental difference. When I eliminate one element
from the array, all the indexes for the elements after the one deleted
are changed. In an associative array nothing happens!

Associative containers and sequential ones look completely different to me.
What could be the procedures that could be attached to a container
"as such"?

There is only one that appears obvious. Containers hold some
data, and they can "spill" that data into some other container
or sink.

Serializing an object can be done with the existing interface using the
"Apply" generic function that calls a user defined function for
each element in the list array, hash table or whatever.

Since "Apply" takes one extra argument, we could shovel there a sink
value (string buffer, or a file pointer) where the data in the element
should be stored in serialized form.

This "spill" operation (and its base function "Apply") could be
common to all containers, and could be a reason why an abstract
concept like "container as such" could be worthwhile.

I haven't looked at Jacob's code so I won't comment on it or on
his approach. That said, it seems to me that the critical issue
in any such enterprise is to get the taxonomy of data structure
interfaces well thought out in advance.

This is one of the reasons I post regularly in this forum. Contrary
to many people, I do not think that the best things go out of the
mind of geniuses. Obviously because I am not a genius of data
processing, but also because I think a team is better than any
individual. The sum is better than its parts... or worse, it depends.

In any case I thank you for your contribution.

 

[jacob navia]

Gareth Owen a écrit :

Indeed, such an "apply" function shows up a "fundamental " similarity
between Associative Containers and Sequential Containers.

Exactly. I agree with you. If you read the rest of my message that is what
I was proposing. The only function that could work with an abstract
container is the serializing of its contents...

 

[Keith Thompson]

Associative containers and sequential ones look completely different to me.

[...]

Then why do you use the word "container" for both of them?

(Yes, I'm quoting you out of context and ignoring the rest of the
article.)

 

[Keith Thompson]

Associative containers and sequential ones look completely
different to me.

[...]

Then why do you use the word "container" for both of them?

Why shouldn't he?

[...]

No reason at all. My point is merely that they aren't "completely
different".

[...]

 

[Nick]

"Operator" is a posh word for "function". The syntax may be different,
but the idea is the same. It is not difficult to envisage a C-like
language where all the operators are replaced by functions (with the
possible exception of the function call operator!). Obviously,
functions like add() would have to be implemented (at least
initially) in a language-external way. Er, actually that's not quite
true, is it?

unsigned int add(unsigned int x, unsigned int y)
{
declare(result, xor(x, y));
declare(carry, and(x, y));
if(ge(carry, 0))
{
leftshift(carry, 1);
assign(result, add(result, carry));
}

result;
}

(Did I get that right? What a ghastly language!)

The above makes it easy to see that you could also have add(unsigned
int x, double y), add(float x, long y), and so on. Polymorphism. The
next step is to leave the polymorphism where it is but replace the
functions with operators. Syntactic sugar, basically.


It is clear that they are related concepts. Polymorphic functions can
be thought of as a number of different functions with the same name,
where the decision as to which to call depends on the context in
which they are called. Overloaded operators can be thought of as a
number of different operators with the same symbol, where the
decision as to which to use depends on the context in which they are
used.

It's never been clear to me why many languages let you extend the
existing operators in completely random directions, but don't let you
add to them. It's a bit as though C allowed you to create your own
functions, but required them to be called "sin" or "printf" but take
different parameters to the standard library to distinguish them

I suppose they start by allowing you to extend the natural meaning of
operators to cope with user defined data types, but can't stop being
doing things like << for streams in C++.

Mind you, having played with a language with multiple infix operators,
it's pretty clear that operator precedence is a bigger problem than for
arithmetical ones. I can never remember whether "print 'hello LOU'
after 'L' into 'lcase'" should output "lo lou" or "OU".

 

[Chris M. Thomasson]

Gareth Owen a écrit :

What can be a method that is common to ALL containers, serial, associative
or
whatever?

[...]

Getting the number of objects within the container?