Container library progress
jacob navia
linux and the few tests already in place give the same results.
This finished I will start implementing the first of the associative containers (hashtable)
for implementing later AVL trees and probably fibonacci heaps...
There are MANY papers bout associative containers, and many algorithms to choose
from.
What bothers me is that many algorithms look much better in paper, but in practice they
do not perform very well because of cache interactions:
The more overhead a container has, the less data that will be stored in the cache.
The less data stored in the cache, the more that the algorithm will "swap", i.e.
will wait for main memory to be ready. Since at 3GHZ the processor can do up to 40-50
clocks just waiting for main memory, all the cleverness of the algorithms is totally
wasted unless you are handling HUGE data sets in the order of several million
members.
The idea would be to implement simple algorithms first, then to implement more sophisticated ones
but maintaining the same interface.
The interface will be similar to the C++ STL to easy the conversions between
this library and C++.
At the same time I have developed a primitive template mechanism in standard
C, and tested it with the "vector" container. It is a very simple program that
expand a suitable written file containing keywords introduced by $@ ... @$
and produces a standard C file for a vector container specialized to containers of
the given type.
All this obviates the need for more complicated language constructs.
jacob
Noob
> The bitstring module is finished (modulo tests). It now compiles cleanly on
> linux and the few tests already in place give the same results.
>
> This finished I will start implementing the first of the associative
> containers (hashtable)
> for implementing later AVL trees and probably fibonacci heaps...
clc is now your personal blogging space?
> There are MANY papers bout associative containers, and many algorithms
> to choose from.
Should you ever wish to discuss them, comp.programming is there for you.
> What bothers me is that many algorithms look much better in paper, but
> in practice they
> do not perform very well because of cache interactions:
>
> The more overhead a container has, the less data that will be stored in
> the cache.
> The less data stored in the cache, the more that the algorithm will
> "swap", i.e.
> will wait for main memory to be ready. Since at 3GHZ the processor can
> do up to 40-50
> clocks just waiting for main memory, all the cleverness of the
> algorithms is totally
> wasted unless you are handling HUGE data sets in the order of several
> million
> members.
No. You're misusing the terminology. Again.
Getting data from RAM is not considered swapping.
Swapping involves copying data between secondary storage and RAM.
http://en.wikipedia.org/wiki/Paging
Sheesh.
Ben Pfaff
> What bothers me is that many algorithms look much better in
> paper, but in practice they do not perform very well because of
> cache interactions:
>
> The more overhead a container has, the less data that will be
> stored in the cache.
It seems that you've decided that you want at least one balanced
binary tree implementation. Have you considered a scapegoat
tree? They have no per-node overhead at all, and only a small
overhead per-tree.
More information:
http://en.wikipedia.org/wiki/Scapegoat_tree
My implementation:
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.h
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.c
http://git.savannah.gnu.org/cgit/pspp.git/tree/tests/libpspp/bt-test.c
--
"I've been on the wagon now for more than a decade. Not a single goto
in all that time. I just don't need them any more. I don't even use
break or continue now, except on social occasions of course. And I
don't get carried away." --Richard Heathfield
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> What bothers me is that many algorithms look much better in
>> paper, but in practice they do not perform very well because of
>> cache interactions:
>>
>> The more overhead a container has, the less data that will be
>> stored in the cache.
>
> It seems that you've decided that you want at least one balanced
> binary tree implementation. Have you considered a scapegoat
> tree? They have no per-node overhead at all, and only a small
> overhead per-tree.
>
> More information:
> http://en.wikipedia.org/wiki/Scapegoat_tree
>
> My implementation:
> http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.h
> http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.c
> http://git.savannah.gnu.org/cgit/pspp.git/tree/tests/libpspp/bt-test.c
Hi
That looks extremely interesting, and your implementation is quite OK. The only problem I see
is that I do not want to have any copyright problems so that people can do ANYTHING with the code.
In that way it will be widely used. Is there a way to avoid the GNU license?
The problem with GNU source code is that if you use it, you have to put your software
under GNU also. I want that the library is available for commercial uses ALSO, i.e.
absolutely no copyright.
Could that be possible?
Thanks
Ben Pfaff
> That looks extremely interesting, and your implementation is quite
> OK. The only problem I see is that I do not want to have any copyright
> problems so that people can do ANYTHING with the code. In that way it
> will be widely used. Is there a way to avoid the GNU license?
>
> The problem with GNU source code is that if you use it, you have to
> put your software under GNU also. I want that the library is available
> for commercial uses ALSO, i.e. absolutely no copyright.
The copyright in that code is assigned to FSF, so I don't really
have control over it.
It's simple code; I was just pointing to it to show that it was
simple. I guess that you are able to implement whatever tree
structure you like.
--
"In My Egotistical Opinion, most people's C programs should be indented six
feet downward and covered with dirt." -- Blair P. Houghton
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> That looks extremely interesting, and your implementation is quite
>> OK. The only problem I see is that I do not want to have any copyright
>> problems so that people can do ANYTHING with the code. In that way it
>> will be widely used. Is there a way to avoid the GNU license?
>>
>> The problem with GNU source code is that if you use it, you have to
>> put your software under GNU also. I want that the library is available
>> for commercial uses ALSO, i.e. absolutely no copyright.
>
> The copyright in that code is assigned to FSF, so I don't really
> have control over it.
>
> It's simple code; I was just pointing to it to show that it was
> simple. I guess that you are able to implement whatever tree
> structure you like.
OK. Thanks for your help, I did not know at all about scapegoat trees!
According to the wiki they should be much better than the AVL or
the others...
Specially this part seems interesting:
Unlike most other self-balancing search trees, scapegoat trees are entirely flexible as to their
balancing. They support any α such that 0.5 <= α < 1. A high α value results in fewer balances,
making insertion quicker but lookups and deletions slower, and vice versa for a low α. Therefore in
practical applications, an α can be chosen depending on how frequently these actions should be
performed.
This means that the user could change the parameter when creating the tree according
to the usage he will do of it, quite nice!
Thanks again.
jacob
jacob navia
> jacob navia wrote:
>
>> The bitstring module is finished (modulo tests). It now compiles cleanly on
>> linux and the few tests already in place give the same results.
>>
>> This finished I will start implementing the first of the associative
>> containers (hashtable)
>> for implementing later AVL trees and probably fibonacci heaps...
>
> clc is now your personal blogging space?
>
>> There are MANY papers bout associative containers, and many algorithms
>> to choose from.
>
> Should you ever wish to discuss them, comp.programming is there for you.
>
The thread "C the complete Meta-Nonsense" contains (until now) 81 messages,
all of them completely off topic. You did not complain about it.
The thread "How to convert Infix notation to postfix notation" has degenerated into
a flame war about everything but C. It has 451 messages. You did not complain.
When I report about the progress done in a project to make a public library
of containers in C, a project that I have repeatedly written about in this group
THEN
you complain.
>> What bothers me is that many algorithms look much better in paper, but
>> in practice they
>> do not perform very well because of cache interactions:
>>
>> The more overhead a container has, the less data that will be stored in
>> the cache.
>> The less data stored in the cache, the more that the algorithm will
>> "swap", i.e.
>> will wait for main memory to be ready. Since at 3GHZ the processor can
>> do up to 40-50
>> clocks just waiting for main memory, all the cleverness of the
>> algorithms is totally
>> wasted unless you are handling HUGE data sets in the order of several
>> million
>> members.
>
> No. You're misusing the terminology. Again.
>
> Getting data from RAM is not considered swapping.
> Swapping involves copying data between secondary storage and RAM.
>
> http://en.wikipedia.org/wiki/Paging
>
You did notice the QUOTES that I put around the "swap" verb?
I was applying one concept to a slightly different environment and
warning the reader with the quotes that the word can't be understood
literally. You choose to make an issue of that.
Why?
Because you have nothing to say, nothing substantive anyway.
> Sheesh.
Yes.
Moi
> More information:
> http://en.wikipedia.org/wiki/Scapegoat_tree
>
Thanks for the links, Ben.
It is a pity that the ACM site is still restricted to paying users only.
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/bt.c
But luckily I can have a look at your source code, too.
AvK
Ben Pfaff
> On Mon, 09 Nov 2009 09:41:01 -0800, Ben Pfaff wrote:
>
>
>> More information:
>> http://en.wikipedia.org/wiki/Scapegoat_tree
>
> It is a pity that the ACM site is still restricted to paying users only.
I agree.
The original scapegoat tree paper is available here (linked from
Wikipedia):
http://cg.scs.carleton.ca/~morin/teaching/5408/refs/gr93.pdf
--
"Given that computing power increases exponentially with time,
algorithms with exponential or better O-notations
are actually linear with a large constant."
--Mike Lee
Moi
> Moi <ro...@invalid.address.org> writes:
>> It is a pity that the ACM site is still restricted to paying users
>> only.
>
> I agree.
>
> The original scapegoat tree paper is available here (linked from
> Wikipedia):
> http://cg.scs.carleton.ca/~morin/teaching/5408/refs/gr93.pdf
Thanks again.
I'll check it out.
AvK
Seebs
> The thread "C the complete Meta-Nonsense" contains (until now) 81 messages,
> all of them completely off topic. You did not complain about it.
They're not *completely* off-topic, though. Discussion of C books is topical,
so's discussion of reviews of C books.
There's certainly a fair amount of discussion of C going on.
-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
Dann Corbit
ro...@invalid.address.org says...
Boost has a Scapegoat tree container also:
http://www.boost.org/doc/libs/1_36_
0/doc/html/intrusive/sg_set_multiset.html
Ian Collins
>
> The idea would be to implement simple algorithms first, then to
> implement more sophisticated ones
> but maintaining the same interface.
>
> The interface will be similar to the C++ STL to easy the conversions
> between
> this library and C++.
>
> At the same time I have developed a primitive template mechanism in
> standard
> C, and tested it with the "vector" container. It is a very simple
> program that
> expand a suitable written file containing keywords introduced by $@ ... @$
> and produces a standard C file for a vector container specialized to
> containers of
> the given type.
>
> All this obviates the need for more complicated language constructs.
Isn't this a bit of a quixotic exercise? Why not just use C++?
If you have to use a platform without a C++ compiler, give the nice
people at www.comeaucomputing.com a call.
--
Ian Collins
Richard Heathfield
<snip>
> Isn't this a bit of a quixotic exercise?
Perhaps, but windmills are *important*. (I'm quite serious about
that.)
Although Jacob Navia's approach is rather different to mine, I think
the objective is a reasonable one.
> Why not just use C++?
C++ is certainly a viable option, but there are at least two reasons
why you might not choose it:
1) you can't;
2) you don't want to.
"You can't" covers "no implementation for target platform and
insufficient budget to pay for one to be developed or target platform
incapable of supporting C++ implementation", "boss says no to C++",
and so on. "You don't want to" probably covers most of the other
reasons.
> If you have to use a platform without a C++ compiler, give the nice
> people at www.comeaucomputing.com a call.
Unless you can't, or don't want to.
(Pace, Greg! I *know* there's nobody on the planet that doesn't want
to give you a call! I'm just trying to stop them melting your
router...)
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
"Usenet is a strange place" - dmr 29 July 1999
Sig line vacant - apply within
jacob navia
>
> Isn't this a bit of a quixotic exercise? Why not just use C++?
>
> If you have to use a platform without a C++ compiler, give the nice
> people at www.comeaucomputing.com a call.
>
As always, the messages from Mr Collins promote C++. His only objective
in posting in this group is to preach how great C++ is.
Granted, here anybody can say anything, Mr Collins included. But it would
be better if he stopped bothering to write in a C group if he thinks C++
is so great. There are C++ groups where he can write.
Nick Keighley
> On 2009-11-09, jacob navia <ja...@nospam.org> wrote:
> > The thread "C the complete Meta-Nonsense" contains (until now) 81 messages,
> > all of them completely off topic. You did not complain about it.
>
> They're not *completely* off-topic, though. Discussion of C books is topical,
> so's discussion of reviews of C books.
>
> There's certainly a fair amount of discussion of C going on.
as someone who's participated, I think you're fooling yourself
Nick Keighley
> Ian Collins a écrit :
>
>
>
> > Isn't this a bit of a quixotic exercise? Why not just use C++?
>
> > If you have to use a platform without a C++ compiler, give the nice
>
> As always, the messages from Mr Collins promote C++. His only objective
> in posting in this group is to preach how great C++ is.
>
> Granted, here anybody can say anything, Mr Collins included. But it would
> be better if he stopped bothering to write in a C group if he thinks C++
> is so great. There are C++ groups where he can write.
if someone wants container classes I don't see the problem in pointing
them in the direction of C++.
Richard Heathfield
You're specifically right, in that that C++ is better discussed in C++
groups. And you're generally right, in that the right place to
discuss a topic is in a group set up to discuss that topic.
I am glad to be able to agree with you so definitely - it makes a
pleasant change.
I trust that you do not only consider your advice applicable to
others, but also consider it applicable to your own articles, so no
doubt in future you will confine discussion of lcc-win32 to
comp.compilers.lcc.
Note that this is not a complaint about the current thread! As far as
I can see, there's nothing off-topic about your OP whatsoever. (I
don't happen to like your approach, but that's not your problem. If I
cared, it would be my problem, not yours.)
jacob navia
>>
>>
>>
>>> Isn't this a bit of a quixotic exercise? Why not just use C++?
>>> If you have to use a platform without a C++ compiler, give the nice
>>> people atwww.comeaucomputing.coma call.
>> As always, the messages from Mr Collins promote C++. His only objective
>> in posting in this group is to preach how great C++ is.
>>
>> Granted, here anybody can say anything, Mr Collins included. But it would
>> be better if he stopped bothering to write in a C group if he thinks C++
>> is so great. There are C++ groups where he can write.
>
> if someone wants container classes I don't see the problem in pointing
> them in the direction of C++.
>
>
>
Nobody wanted "container classes"... In the code I posted there are no classes
at all.
Joe Wright
> On 2009-11-09, jacob navia <ja...@nospam.org> wrote:
>> The thread "C the complete Meta-Nonsense" contains (until now) 81 messages,
>> all of them completely off topic. You did not complain about it.
>
> They're not *completely* off-topic, though. Discussion of C books is topical,
> so's discussion of reviews of C books.
>
> There's certainly a fair amount of discussion of C going on.
>
> -s
Especially all that stuff about re-learning C.
--
Joe Wright
"If you rob Peter to pay Paul you can depend on the support of Paul."
gwowen
> Nobody wanted "container classes"... In the code I posted there are no classes
> at all.
You have structures that encapsulate both data and methods to
manipulate that data. Regardless of whether you wish to call them
classes, they're definitely objects.
jacob navia
If "objects" means object oriented programming the answer is surely NO.
There is no class hierarchy, no inheritance, just objects in the C sense.
Obviously C has objects too. But no object oriented programming.
Nick Keighley
> Nick Keighley a écrit :> >> Ian Collins a écrit :
> >>> Isn't this a bit of a quixotic exercise? Why not just use C++?
> >>> If you have to use a platform without a C++ compiler, give the nice
> >>> people atwww.comeaucomputing.comacall.
>
> >> As always, the messages from Mr Collins promote C++. His only objective
> >> in posting in this group is to preach how great C++ is.
I'd not noticed this
> >> Granted, here anybody can say anything, Mr Collins included. But it would
> >> be better if he stopped bothering to write in a C group if he thinks C++
> >> is so great. There are C++ groups where he can write.
>
> > if someone wants container classes I don't see the problem in pointing
> > them in the direction of C++.
>
> Nobody wanted "container classes"... In the code I posted there are no classes
> at all.
fair point. C++ containers aren't classes either.
What I /meant/ to say was if someone wants container libraries I don't
see the problem in pointing
them in the direction of C++. You can write nearly-C in C++ and have
containers.
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
wrote:
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? ;-)
Richard Heathfield
<b684ea5f-6682-4aa7...@k17g2000yqh.googlegroups.com>,
gwowen wrote:
So are ints and chars and floats.
gwowen
> So are ints and chars and floats.
Only in standardese, not in common computer science usage.
Richard Heathfield
<6b5a3681-fe77-486c...@j24g2000yqa.googlegroups.com>,
gwowen wrote:
Compiler writers were calling them objects long before OOP was a mere
twinkle in Alan Kay's eye.
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
> On Nov 10, 2:10 pm, jacob navia <ja...@nospam.org> wrote:
>
>> 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.
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
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?
Gareth Owen
> 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)
> Your answer skips that discussion entirely and you take examples
> to prove...
>
> well WHAT?
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.
You're grouping by commonality and presenting common interface (not a
single common interface, two distinct common interfaces
"SequentialContainer" and "AssociativeContainer"). That's subtyping.
You don't call it subtyping, because the interface definition does not
exist in code (no language support), but that's what it is.
You've separated interface and implementation.
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.
Richard Heathfield
<snip>
> You're encapsulating methods and data together. That's pretty much
> the definition of object orientation.
"Actually I made up the term "object-oriented", and I can tell you I
did not have C++ in mind." - Alan Kay.
<snip>
> To deny that what you're doing is object orientated (as you have
> repeatedly done) is simply incorrect.
"OOP to me means only messaging, local retention and protection and
hiding of state-process, and extreme late-binding of all things. It
can be done in Smalltalk and in LISP." - Alan Kay.
jacob navia
> jacob navia <ja...@nospam.org> writes:
>
>> 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.
>> Your answer skips that discussion entirely and you take examples
>> to prove...
>>
>> well WHAT?
>
> 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
> On Nov 10, 5:22 pm, jacob navia <ja...@nospam.org> wrote:
>
> > 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.
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?
> > (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.
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
wrote:
> 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
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
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.
:-)
Richard Heathfield
<b1e5f09b-f40b-447f...@h34g2000yqm.googlegroups.com>,
gwowen wrote:
> On Nov 11, 9:36 am, Nick Keighley <nick_keighley_nos...@hotmail.com>
> wrote:
>
>> 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.
"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.
> "Overloaded" certainly.
> Would you consider overloading to be the same as polymorphic?
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. The distinction between
<snip>
Richard Heathfield
wrote:
operators and functions is merely syntactic. (Sorry!)
gwowen
> > Erm... Good question. I don't really have a firm handle on what
> > polymorphic means applied to operators.
>
> "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
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.
--
Keith Thompson (The_Other_Keith) ks...@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
Richard Harter
<gwo...@gmail.com> wrote:
>> 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 access them by index in the
>> sequence, in an associative container you access them by key.
>
>The index in the sequence IS (conceptually) the key.
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.
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.
And that is how I conceptualize i. :-)
Richard Harter, c...@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Infinity is one of those things that keep philosophers busy when they
could be more profitably spending their time weeding their garden.
jacob navia
> On Wed, 11 Nov 2009 02:13:04 -0800 (PST), gwowen
> <gwo...@gmail.com> wrote:
>
>>> 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 access them by index in the
>>> sequence, in an associative container you access them by key.
>> The index in the sequence IS (conceptually) the key.
>
> 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.
Gareth Owen
> 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.
Using that definition, then I'd say "+" is not polymorphic, merely
overloaded.
Quite often, though, you'll hear C++ programmers refer to templates as
"static polymorphism" or "compile time polymorphism", and
Liskov-substitution-principle public inheritance as "dynamic
polymorphism". It appears that the word "polymorphism" is itself
polymorphic, although possibly not as polymorphic as word "static"...
Me, I agree with Dodgson:
"When I use a word, it means just what I choose it to mean;
neither more, nor less"
Gareth Owen
> 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!
That's certainly a big difference. But consider a hashtable and a
multimap. If I try and add an element with a pre-existing key, what
happens? In one, we (usually) replace the existing datum, in the other
we allow duplicate keys.
Is that a fundamental difference, or is that merely a big difference?
If its fundamental, would you consider both to be Associative
Containers?
> 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.
Indeed, such an "apply" function shows up a "fundamental ;)" similarity
between Associative Containers and Sequential Containers.
Given a list of things, we can apply a function that transforms the
things. Given a hashtable of {keys,things}, we can apply a function
that transforms the things.
jacob navia
>> "Apply" generic function that calls a user defined function for
>> each element in the list array, hash table or whatever.
>
> 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.)
Richard Heathfield
> jacob navia <ja...@nospam.org> writes:
> [...]
>> 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? Saucepans and jerry-cans look completely different
to me, but they are both containers. (I nearly said pots and kettles,
but I realised just in time that that might be misinterpreted!)
> (Yes, I'm quoting you out of context and ignoring the rest of the
> article.)
I'm not. :-)
Keith Thompson
> In <lnhbt0l...@nuthaus.mib.org>, Keith Thompson wrote:
>> jacob navia <ja...@nospam.org> writes:
>> [...]
>>> 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
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".
--
Online waterways route planner: http://canalplan.org.uk
development version: http://canalplan.eu
Gareth Owen
> 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.
Bjarne Stroustrup (sp?) has written a few times on why you can't add
operators to C++, and the reasons given do eventually boil down to
"precedence issues will kill you."
You can overload ||, but when you do, it ceases to become short-cutting,
so everyone is advised never to do that...
Gareth Owen
> Gareth Owen a écrit :
>> jacob navia <ja...@nospam.org> writes:
>> 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...
I'm sorry, but I don't understand this.
jacob navia
What can be a method that is common to ALL containers, serial, associative or
whatever?
Spilling.
ANY container can spill its contents into a sink, i.e. in data processing
terms, write a serialized representation of its contents into a character
string buffer or into a file stream.
This can be done with the "Apply" function, that would call a user defined
"Print" function or "WriteToDisk" function to write the contents of the
container into the disk.
Chris M. Thomasson
news:hdgcn5$8r7$1...@aioe.org...
> Gareth Owen a écrit :
>> jacob navia <ja...@nospam.org> writes:
>>
>>> Gareth Owen a écrit :
>>>> jacob navia <ja...@nospam.org> writes:
>>>> 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...
>>
>> I'm sorry, but I don't understand this.
>
> What can be a method that is common to ALL containers, serial, associative
> or
> whatever?
Getting the number of objects within the container?
Nick Keighley
> Gareth Owen a écrit :
> > jacob navia <ja...@nospam.org> writes:
> >> Gareth Owen a écrit :
> >>> jacob navia <ja...@nospam.org> writes:
> >>> 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...
>
> > I'm sorry, but I don't understand this.
I understand but I don't agree!
> What can be a method that is common to ALL containers, serial, associative or
> whatever?
>
> Spilling.
function application
> ANY container can spill its contents into a sink, i.e. in data processing
> terms, write a serialized representation of its contents into a character
> string buffer or into a file stream.
>
> This can be done with the "Apply" function, that would call a user defined
> "Print" function or "WriteToDisk" function to write the contents of the
> container into the disk.
yes, but the apply functions doesn't have to be a serializer. You
could increment all the elements for instance. This isn't just nik-
pikery. The point about serialization is that implies an ordering
whilst function application doesn't neceessarily.
The functional programming people sometimes have both a map() (apply a
function to all elements- no ordering) and for_each() apply a function
to each element in order.
Nick Keighley
> <b1e5f09b-f40b-447f-96a0-88447402a...@h34g2000yqm.googlegroups.com>
> >> 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.
>
> "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!).
be careful you might reinvent Lisp...
[my examples are from the Lisp-like language scheme]
There there are no operators just some functions a spelt funny
(average 1 2 3)
(+ 1 2 3)
the "function call operator" is called apply
(apply + (1 2 3))
[I know I missed a quote out]
> 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?
there has to be a set of built in primitives. This set can be
surprisingly small.
jacob navia
>>> jacob navia <ja...@nospam.org> writes:
>>>> Gareth Owen a �crit :
>>>>> jacob navia <ja...@nospam.org> writes:
>
>
>>>>> 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...
>>> I'm sorry, but I don't understand this.
>
> I understand but I don't agree!
>
>
>> What can be a method that is common to ALL containers, serial, associative or
>> whatever?
>>
>> Spilling.
>
> function application
>
Yes, since spilling needs function application. But function application
is done with a purpose, and the common purpose for all containers that
I proposed was spilling the contents into a sink.
>
>> ANY container can spill its contents into a sink, i.e. in data processing
>> terms, write a serialized representation of its contents into a character
>> string buffer or into a file stream.
>>
>> This can be done with the "Apply" function, that would call a user defined
>> "Print" function or "WriteToDisk" function to write the contents of the
>> container into the disk.
>
> yes, but the apply functions doesn't have to be a serializer. You
> could increment all the elements for instance. This isn't just nik-
> pikery. The point about serialization is that implies an ordering
> whilst function application doesn't neceessarily.
>
Serialization doesn't imply an order. When the container is an
associative container there is no fixed order.
> The functional programming people sometimes have both a map() (apply a
> function to all elements- no ordering) and for_each() apply a function
> to each element in order.
>
>
In the case of associative containers, Apply is equivalent to map (no order)
but in the case of sequential containers Apply will follow the sequence order.
Nick Keighley
> 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.
if you want Algol-68 you know where to find it (Algol-68 allowed you
to define new operators and even specify their precedence)
Nick Keighley
> 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 make the lack of support sound like a virtue...
> 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.
C is Turing Complete. We can do anything in C.
> What Nick Keighley understood :
was i mistaken?
> > 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.
well obviously I think my (I stole it actually) jokes are funny!
I don't think C makes OO very easy. I think your lack of inheritance
is telling. Though you could argue that don't need it in this
application.
We can do anything in C, but it isn't necessarily easy.
> 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.
and C is no different in this regard
> 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.
and why is C any different? If I want a Lisp style CLOS (it allows
dispatch on more than one argument- hence avoiding the dreaded Vistor
Pattern [*]) then I can write one in C++. Or Cobol. But is it worth
the trouble?
[*] it doesn't really matter what this all means, it just means CLOS
can do things easily that are hard to do even in C++'s object model
jacob navia
> On 11 Nov, 10:36, jacob navia <ja...@nospam.org> wrote:
>
>> 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 make the lack of support sound like a virtue...
>
Well, that *is* a virtue from my point of view, and that is what you don't understand.
Exactly the LACK of any paradigm that is the accepted paradigm for the language allows
you to design ANY paradigm yourself!
The advantage of C is precisely that it does NOT impose a pre-determined way of doing
things.
>
> I don't think C makes OO very easy. I think your lack of inheritance
> is telling. Though you could argue that don't need it in this
> application.
>
Precisely. Anyway I could do some kind of inheritance. Just put common
methods and data in the same position in all containers and there,
you have inheritance.
> We can do anything in C, but it isn't necessarily easy.
>
If you want easy OO programming do C# or C++ or...
[long list snipped for brevity]
If you want to program exactly the paradigm you think it is best for
your application use C.
>
>> 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.
>
> and C is no different in this regard
>
What framework is imposed on you? None! That is precisely its advantage.
Nick Keighley
> Nick Keighley a écrit :
> > On 11 Nov, 10:36, jacob navia <ja...@nospam.org> wrote:
> >> 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 make the lack of support sound like a virtue...
>
> Well, that *is* a virtue from my point of view, and that is what you don't understand.
I do understand. I don't agree. We are beginning to repeat ourselves
so I'll make this brief.
> Exactly the LACK of any paradigm that is the accepted paradigm for the language allows
> you to design ANY paradigm yourself!
great. So I'll rewrite all my applications in FORTRAN IV
*ALL* real-world programming languages are Turing Complete and hence
are in a theoretical sense equivalent to any other TC language. If I
want OO (or CLOS or functional programming) I can write a translator
in FORTRAN IV. Hence FORTRAN IV can be used to program in any
paradigm.
This is known as the Turing Tarpit, where anything is possible but
nothing is easy.
<snip>
> The advantage of C is precisely that it does NOT impose a pre-determined way of doing
> things.
The advantage of <any language> is precisely that it does NOT impose a
pre-determined way of doing <certain> things.
<snip>
gwowen
> your application use C.
In what way does the availability of C++ STL containers *impose* a
framework on C++ programmers?
Do the same criticisms not apply to C-augmented-with-your-container-
library?
bartc
> On 11 Nov, 19:05, Nick <3-nos...@temporary-address.org.uk> wrote:
>
>> 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.
>
> if you want Algol-68 you know where to find it (Algol-68 allowed you
> to define new operators and even specify their precedence)
And then you might end up with APL or some equally succinct language.
Sometimes giving too much freedom to a mere programmer (rather than a
language designer or some other responsible person) is not a good idea...
--
Bartc
Nick Keighley
> Nick Keighley wrote:
> > On 11 Nov, 19:05, Nick <3-nos...@temporary-address.org.uk> wrote:
> >> 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.
>
> > if you want Algol-68 you know where to find it (Algol-68 allowed you
> > to define new operators and even specify their precedence)
>
> And then you might end up with APL or some equally succinct language.
I think APL avoided precedence by always applying the operators in the
same order (right to left if I recall correctly)
> Sometimes giving too much freedom to a mere programmer (rather than a
> language designer or some other responsible person) is not a good idea...
I think that's why no one has followed Algol-68's example. But for
ages it allowed me to say "oh, <language X> is just a subset of
Algol-68"
Ben Bacarisse
> On 12 Nov, 13:04, "bartc" <ba...@freeuk.com> wrote:
>> Nick Keighley wrote:
<snip>
>> > if you want Algol-68 you know where to find it (Algol-68 allowed you
>> > to define new operators and even specify their precedence)
<snip>
> I think that's why no one has followed Algol-68's example.
Except Pop-11, Haskell, ML (and derivatives like F# and OCaml),
Scala and, no doubt, others :-)
<snip>
--
Ben.
Seebs
> What can be a method that is common to ALL containers, serial, associative or
> whatever?
Count of stored members. Retrieval by key (where key may be an index or
some other kind of value). Addition of a new member with a given key.
Iteration over all members.
You might find it instructive to compare arrays and hashes in something like
Ruby, which treats them a fair bit like each other in some ways.
-s
--
Copyright 2009, all wrongs reversed. Peter Seebach / usenet...@seebs.net
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
dragan
> The bitstring module is finished (modulo tests).
Who are you talking to?? Does this guy have an audience and marketing avenue
here?
Malcolm McLean
sourcecode or compilers. To an extent this is legitimate use of the group.
Richard Heathfield
Presenting C code for comment is a perfectly legitimate use of the
group. Although Jacob Navia didn't do that on this occasion, he has
done so in the recent past and is giving an update on progress. That
is a 100% legitimate use of this group.
David Thompson
<nick_keigh...@hotmail.com> wrote:
> On 11 Nov, 10:56, Richard Heathfield <r...@see.sig.invalid> wrote
> > <b1e5f09b-f40b-447f-96a0-88447402a...@h34g2000yqm.googlegroups.com>
> > "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!).
>
> be careful you might reinvent Lisp...
>
LISP et seq also make control structures (routine, if/selection,
loop/iteration, etc.) look like function calls (or vice versa).
An example of only operator=function is FORTH and PostScript. They do
all computation against an implicitly shared data stack (or perhaps
two), so you don't need 'apply', just 'execute'. PostScript has very
limited special syntax for control structures, plus more built on this
somewhat like LISP (~compile-time) macros; and normally uses names for
what are normally operators but you can define symbols. FORTH has
explicit and manipulable compilation into the dictionary, with a small
builtin set of control primitives to which you can add more; and
normally symbols for most operators but you can define names.
Phil Carmody
> On Thu, 12 Nov 2009 00:24:08 -0800 (PST), Nick Keighley
> <nick_keigh...@hotmail.com> wrote:
>
> > On 11 Nov, 10:56, Richard Heathfield <r...@see.sig.invalid> wrote
> > > <b1e5f09b-f40b-447f-96a0-88447402a...@h34g2000yqm.googlegroups.com>
>
> > > "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!).
> >
> > be careful you might reinvent Lisp...
>
> LISP et seq also make control structures (routine, if/selection,
> loop/iteration, etc.) look like function calls (or vice versa).
I'dn't've said so. They make control structures look like
structured data, and they make function calls look like
structured data. There's no attempt to make either look
like the other, simply both to a common sexp structure.
Phil
--
Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
Richard Bos
> Nick <3-no...@temporary-address.org.uk> writes:
>
> > 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.
>
> Bjarne Stroustrup (sp?) has written a few times on why you can't add
> operators to C++, and the reasons given do eventually boil down to
> "precedence issues will kill you."
He hasn't studied Prolog very well, then. It has no problems with
letting you define your own operators with your own desired precedence
(and binding).
Mind you, that doesn't mean that it's a good idea. All it means is that
precedence issues are not the reason why it's a bad idea.
Richard
Ben Pfaff
> Gareth Owen <gwo...@gmail.com> wrote:
>
>> Nick <3-no...@temporary-address.org.uk> writes:
>>
>> > 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.
>>
>> Bjarne Stroustrup (sp?) has written a few times on why you can't add
>> operators to C++, and the reasons given do eventually boil down to
>> "precedence issues will kill you."
>
> He hasn't studied Prolog very well, then. It has no problems with
> letting you define your own operators with your own desired precedence
> (and binding).
Smalltalk gets away with it, too, by having a very simple
precedence chart. Prefix unary operators have the highest
precedence, followed by binary operators, which always associate
left to right.
--
Ben Pfaff
http://benpfaff.org
robert...@yahoo.com
While I've never done more than dabble in Prolog, and that probably 15
years ago, how does it handle that? You could either have a very
simple scheme (like Smalltalk's or other languages that essentially
have no precedence - Forth, Lisp, APL, etc.), or you have a problem,
as far as I can see.
Do you define precedence of the new operator globally or locally?
While defining it globally is fairly straight forward, it seems like
it would easily lead to conflicts as soon as more than one attempt was
made to define that operator. IOW, package A does "#defineop "-:-"
binary,precedence=3.5,bind=rtl" and package B does "#defineop "-:-"
unary,precedence=2,bind=ltr", and you've got a mess. Of course you
could simply define two incompatible definitions as being an error,
but then someone’s going to try to reinvent namespaces again.
OTOH, if you define them locally, you get parsing problems, in that
you can't determine the precedence or binding of an operator without
knowing the types it's operating on, and you can't determine that
before you know what operands are binding with the operator.
Dik T. Winter
> ral...@xs4all.nl (Richard Bos) writes:
> > Gareth Owen <gwo...@gmail.com> wrote:
> >> Bjarne Stroustrup (sp?) has written a few times on why you can't add
> >> operators to C++, and the reasons given do eventually boil down to
> >> "precedence issues will kill you."
> >
> > He hasn't studied Prolog very well, then. It has no problems with
> > letting you define your own operators with your own desired precedence
> > (and binding).
>
> Smalltalk gets away with it, too, by having a very simple
> precedence chart.
Algol 68 had it too. Unary operators had highest priority, others got a
priority ranging from 9 to 1 (programmer defined). However, I think
Stroustrup alludes to the possible problem in Algol 68 where you could
*redefine* the priority of operators within a block. E.g. with the
predefined operators '+' and '*' the following block would print 65:
'begin' 'prio' '*' = 6, '+' = 7;
print(5 * 6 + 7)
'end'
and all operators that looked the same would have the same priority at each
particular place.
--
dik t. winter, cwi, science park 123, 1098 xg amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Dik T. Winter
...
> OTOH, if you define them locally, you get parsing problems, in that
> you can't determine the precedence or binding of an operator without
> knowing the types it's operating on, and you can't determine that
> before you know what operands are binding with the operator.
In Algol 68 this wsa done by giving all operators that looked the same
have the same priority, so no parsing problems.
David Thompson
<thefatphi...@yahoo.co.uk> wrote:
They both look like data, yes, and as an important result can be
manipulated as data. But that means they look like each other.
I think it's the same elephant.