www.digitalmars.com         C & C++   DMDScript  

D - Ode to the set

reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Hi,

One of the features I miss the most in C is the set. Being a member of the 
Free Pascal development team, I program a lot in Pascal. Now I don't want 
to say that Pascal rules and C sucks, but there are some things that Pascal 
is superior in.

Why do you need a set?

I think it can best be illustrated with an example. The following code code 
from the AOLserver http server and is used to encode a parameter to place 
in in a URL. For example the text "This is a sentence" is changed into 
"This%20is%20a%20sentence".

char *
Ns_EncodeUrl(Ns_DString *pds, char *string)
{
    static char safechars[] =
        "abcdefghijklmnopqrstuvwxyz"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "0123456789";

    while (*string != '\0') {

        if (strchr(safechars, *string) != NULL) {
            Ns_DStringNAppend(pds, string, 1);
        } else {
            char buf[4];
            sprintf(buf, "%%%02x", (unsigned char) *string);
            Ns_DStringNAppend(pds, buf, 3);
        }
        ++string;
    }
    return pds->string;
}

That's really horrible inefficient isn't it? But it's easy to maintain, if 
the safechars are not correct, you can correct it by changing it. Now how 
would you do this into Pascal?

function ns_encodeurl(s:string):string;

const   safechars=['a'..'z','A'..'Z','0'..'9'];

var     i:longint;

begin
    ns_encodeurl:='';
    for i:=1 to length(s) do
        if s[i] in safechars then
            ns_encodeurl:=ns_encodeurl+s[i]
        else
            ns_encodeurl:=ns_encodeurl+'%'+hexstr(byte(s[i]));
end;

That looks much cleaner! And it's much more efficient; instead of a strchr 
call for each character the compiler now only needs a set lookup. And 
because this is a constant set, the compiler can optimize this into a few 
compare operations.

Set's make also good flags. In C you usually see code like this:

#define borders_enabled         1
#define shadow_enabled          2
#define lights_enabled          4

And then:

void do_nice_things(int flags) {
    if (flags & borders_enabled) {
    };
};

Now how would you do it with a set? A simple enumeration does the trick:

type    effects=(borders_enabled,shadow_enabled,lights_enabled);

And then:

procedure do_nice_things(flags:set of effects);

begin
    if borders_enabled in effects then
        begin
        end;
end;

... so no terrible long header files. Just simple enumerations, while the 
compiler will propably generate the same code.

So, how about a set in D??

Greetings,

Daniel Mantione
Aug 21 2001
next sibling parent reply "Angus Graham" <agraham_d agraham.ca> writes:
"Daniel Mantione" <daniel deadlock.et.tudelft.nl> wrote
 That looks much cleaner! And it's much more efficient; instead of a strchr
 call for each character the compiler now only needs a set lookup. And
 because this is a constant set, the compiler can optimize this into a few
 compare operations.

Well, to be fair, the C version doesn't have to use strchr. You could just change if (strchr(safechars, *string) != NULL) { to char c = *string; if( (c>='a' && 'z'>=c) || (c>='A' && 'Z'>=c) || (c>='0' && '9'>=c) ) or even char set[][] = { {'a','z'}, {'A','Z'}, {'0','9'}; char c = *string; if( (c>=set[0][0] && set[0][1]>=c) || (c>=set[1][0] && set[1][1]>=c) || (c>=set[2][0] && set[2][1]>=c) ) or finally char set[][] = { {'a','z'}, {'A','Z'}, {'0','9'}; char c = *string; for( int i=0; i<sizeof(set); ++i ) { found = (c>=set[i][0] && set[i][1]>=c); } if(found) { which is a little hectic, bit is what I presume the Pascal version does internally. Angus Graham
Aug 21 2001
next sibling parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Angus Graham wrote:
 
 "Daniel Mantione" <daniel deadlock.et.tudelft.nl> wrote
 That looks much cleaner! And it's much more efficient; instead of a strchr
 call for each character the compiler now only needs a set lookup. And
 because this is a constant set, the compiler can optimize this into a few
 compare operations.

Well, to be fair, the C version doesn't have to use strchr. You could just change... [options snipped]

Those alternatives aren't very pretty, IMO. strchr()'s actually pretty efficient -- only one function call involved, and I presume the typical Pascal system is going to make a function call to do a set lookup. However, strchr() isn't a general object-in-set function. For the general case, are D's associative arrays good enough, Daniel? -RB
Aug 21 2001
parent reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Russell Bornschlegel wrote:

 Those alternatives aren't very pretty, IMO.

That's indeed the point. Code like this is hard to maintain.
 strchr()'s actually pretty efficient -- only one function call involved,
 and I presume the typical Pascal system is going to make a function call
 to do a set lookup. However, strchr() isn't a general object-in-set
 function.

Our own Free Pascal compiler uses compares if the amount of compares that are needed is smaller than 9. If the amount of compares is greater than 9, it creates a bit map, and checks if bit number x is set. So: if s[i] in ['0'..'9'] .. will generate the same code as .. if i>='0' and i<='9' .. while .. if s[i] in ['a','d','#','A..X','!','-','+','0..9'] .. will generate code similar to .. const bitmap:packed array[#0..#255] of boolean=(0,0,0, .... ); if bitmap[s[i]] then -- Both are much more efficient than a strchr call. Furthermore, strchr is often optmized for very long strings, look at the implementation in the GNU libc for an example how much code it is.
 For the general case, are D's associative arrays good enough, Daniel?

They are a cool feature, but how would you use them as a set replacement? Daniel
Aug 21 2001
next sibling parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Daniel Mantione wrote:
 
 Russell Bornschlegel wrote:
 For the general case, are D's associative arrays good enough, Daniel?

They are a cool feature, but how would you use them as a set replacement?

Associative array of bit; 1 = exists, 0 = unexists. bit[ char ] myset; // set of char // do we need to explicitly zero things here? myset[ 'x' ] = 1; // 'x' exists in set myset[ 'y' ] = 1; // 'y' exists in set myset[ 'j' ] = 1; // 'j' exists in set if (myset['j'] == 1) { ... } myset['y'] = 0; // take y out of the set if (myset['y'] == 1) { ... } Alternately, ignore the contents of each element, and use the existence of an element in the associative array as set membership. int[ char ] myset; // set of char myset[ 'x' ] = 1; // 'x' exists in set myset[ 'y' ] = 42; // 'y' exists in set myset[ 'j' ] = 3721; // 'j' exists in set if ('j' in myset) { ... } delete myset['y']; // take y out of the set if ('y' in myset) { ... } The D spec is silent on the implementation details for associative arrays, but they'd likely be binary trees (ordered keys, lookup time normally O(log2(n))) or hashes (disordered keys, lookup time normally O(1)). The D compiler could conceivably do weird optimizations on bit-type associative arrays. -RB
Aug 22 2001
next sibling parent reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Hi,

No, this won't do as replacement; it is much to cumbersome to use. You are 
right that a set allways needs to be a bitmap in unoptimized form. The 
compiler can then decide if it optimizes the bitmap away.

Try to code my first example with such an array. It's no replacement.

Furthermore, sets also have union, difference and subset operations, which 
you don't want to hard code.

Daniel

Russell Bornschlegel wrote:

 They are a cool feature, but how would you use them as a set replacement?

Associative array of bit; 1 = exists, 0 = unexists. bit[ char ] myset; // set of char // do we need to explicitly zero things here? myset[ 'x' ] = 1; // 'x' exists in set myset[ 'y' ] = 1; // 'y' exists in set myset[ 'j' ] = 1; // 'j' exists in set if (myset['j'] == 1) { ... } myset['y'] = 0; // take y out of the set if (myset['y'] == 1) { ... } Alternately, ignore the contents of each element, and use the existence of an element in the associative array as set membership. int[ char ] myset; // set of char myset[ 'x' ] = 1; // 'x' exists in set myset[ 'y' ] = 42; // 'y' exists in set myset[ 'j' ] = 3721; // 'j' exists in set if ('j' in myset) { ... } delete myset['y']; // take y out of the set if ('y' in myset) { ... } The D spec is silent on the implementation details for associative arrays, but they'd likely be binary trees (ordered keys, lookup time normally O(log2(n))) or hashes (disordered keys, lookup time normally O(1)). The D compiler could conceivably do weird optimizations on bit-type associative arrays. -RB

Aug 22 2001
parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Daniel Mantione wrote:

 No, this won't do as replacement; it is much to cumbersome to use. You are
 right that a set allways needs to be a bitmap in unoptimized form. The
 compiler can then decide if it optimizes the bitmap away.
 
 Try to code my first example with such an array. It's no replacement.

Your Ns_EncodeUrl() example? In C, that's a mess for a number of reasons, not the least of which is C's inadequate string handling. In terms of performance efficiency, in C, the set lookup is going to get swamped by the sprintf. In Pascal, the set lookup may be faster but it'll be drowned out over the long haul by array bounds checking. :) In terms of implementation cleanliness, Pascal wins out here. In D, I think the _usage_ of the set is just as clean; if assoc-array-of-bits is optimized specially, then performance should be basically equal, and that just leaves the instantiation of the set. So, I concede the desirability of static range-initialization in associative arrays in D: char[] hexlate = "0123456789ABCDEF"; bit[char] safechars; // we want a way of saying this in a static initializer safechars[ 'a'..'z' ] = 1; safechars[ 'A'..'Z' ] = 1; safechars[ '0'..'9' ] = 1; // all others left undefined/null/nonexistent char[] source, destination; for (i = 0; i < source.length(); i++) { char c = source[i]; if (c in safechars) { // append character destination.append( c ); // Walter: does destination += c do the Right Thing? } else { // append %## code destination.append( '%%' ); destination.append( hexlate[ ( (c >> 4) & 0x0F ) ] ); // upper 4 bits of c as hex digit destination.append( hexlate[ (c & 0x0F) ] ); // lower 4 bits of c as hex digit } } Which seems reasonably clean to me. It's not clear to me from my reading of the D spec whether Walter intended range initialization to work on associative arrays. -RB
Aug 22 2001
parent reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Hi,

Yes, this looks like a very promising implementation to use sets. What you 
are essentially saying is that an array of bits has set semantics, like the 
"in" operator.

This fits very well in the philosophy of the language. In C you can use an 
int as boolean, in Pascal not. This can apply to arrays/sets as set as well.

Still, I would propose to also have some kind of set constructor, to be 
able to code:

if (i in ['a'..'z']) {};

So the set constructor ['a'..'z'] constructs an associative array of bits. 
Now the compiler can analize this and see that the same result can be 
achieved by doing compares. In fact, Free Pascal does this when it 
encounters a constant set.

Note that a set constructor is not something to write down a constant set, 
but an expression that results in a set. The following code is completely 
legal:

var a,b:longint;
    c:set;

begin
    a:=1;
    b:=3;
    c:=[a,b,2*b+7,4,5,6];
end;

How about using [...] as set constructor in D? I don't think it makes the 
syntax ambiguous. Or do we need a different constructor?

Your example would then be written as:

   char[] hexlate = "0123456789ABCDEF";
   bit[char] safechars = ['a'..'z','A'..'Z','0'..'9'];
 
   // all others left undefined/null/nonexistent
 
   char[] source, destination;
 
   for (i = 0; i < source.length(); i++)
   {
     char c = source[i];
     if (c in safechars)
     {
         // append character
         destination.append( c );
         // Walter: does destination += c do the Right Thing?
     }
     else
     {
         // append %## code
         destination.append( '%%' );
         destination.append( hexlate[ ( (c >> 4) & 0x0F ) ] );
         destination.append( hexlate[ (c & 0x0F) ] );
     }
   }

Russell Bornschlegel wrote:

 Daniel Mantione wrote:
 
 No, this won't do as replacement; it is much to cumbersome to use. You
 are right that a set allways needs to be a bitmap in unoptimized form.
 The compiler can then decide if it optimizes the bitmap away.
 
 Try to code my first example with such an array. It's no replacement.

Your Ns_EncodeUrl() example? In C, that's a mess for a number of reasons, not the least of which is C's inadequate string handling. In terms of performance efficiency, in C, the set lookup is going to get swamped by the sprintf. In Pascal, the set lookup may be faster but it'll be drowned out over the long haul by array bounds checking. :)

What do you mean? There are no arrays involved.
 In terms of implementation cleanliness, Pascal wins out here. In D, I
 think the _usage_ of the set is just as clean; if assoc-array-of-bits is
 optimized specially, then performance should be basically equal, and that
 just leaves the instantiation of the set.
 
 So, I concede the desirability of static range-initialization in
 associative arrays in D:
 
   char[] hexlate = "0123456789ABCDEF";
   bit[char] safechars;
 
   // we want a way of saying this in a static initializer
   safechars[ 'a'..'z' ] = 1;
   safechars[ 'A'..'Z' ] = 1;
   safechars[ '0'..'9' ] = 1;
 
   // all others left undefined/null/nonexistent
 
   char[] source, destination;
 
   for (i = 0; i < source.length(); i++)
   {
     char c = source[i];
     if (c in safechars)
     {
         // append character
         destination.append( c );
 // Walter: does destination += c do the Right Thing?
     }
     else
     {
         // append %## code
         destination.append( '%%' );
         destination.append( hexlate[ ( (c >> 4) & 0x0F ) ] );   // upper 4
         bits of c as hex digit
         destination.append( hexlate[ (c & 0x0F) ] );            // lower 4
         bits of c as hex digit
     }
   }
 
 Which seems reasonably clean to me. It's not clear to me from my reading
 of the D spec whether Walter intended range initialization to work on
 associative arrays.
 
 -RB

Greetings, Daniel Mantione
Aug 22 2001
parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Daniel Mantione wrote:
 Yes, this looks like a very promising implementation to use sets. What you
 are essentially saying is that an array of bits has set semantics, like the
 "in" operator.

As currently specified, though, associative-array-of-bit actually has three states per key: 1, 0, or not-in-set. That's not a great fit to an underlying array-of-bit implementation.
 Still, I would propose to also have some kind of set constructor, to be
 able to code:
 
 if (i in ['a'..'z']) {};
 
 So the set constructor ['a'..'z'] constructs an associative array of bits.
 Now the compiler can analize this and see that the same result can be
 achieved by doing compares. In fact, Free Pascal does this when it
 encounters a constant set.

OK.
 In terms of performance efficiency, in C, the set lookup is going to get
 swamped by the sprintf. In Pascal, the set lookup may be faster but it'll
 be drowned out over the long haul by array bounds checking. :)

What do you mean? There are no arrays involved.

Not in that code snippet, but in the rest of the program, whatever that program might be. That's what I meant by "the long haul". I really tried to resist suggesting: static char* translate[] = { "%00", "%01", "%02" ... "0", "1", "2" ... "A", "B", "C" ... "a", "b", "c" ... "%FE", "%FF" }; // about 2K bytes while (*string) { char* x = translate[*string++]; while (*x) { *dest++ = *x++; } } -RB
Aug 22 2001
next sibling parent reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Russell Bornschlegel wrote:

 What do you mean? There are no arrays involved.

Not in that code snippet, but in the rest of the program, whatever that program might be. That's what I meant by "the long haul".

Luckily you can turn off range checking, which you usually do when your program is bug-free. Daniel
Aug 22 2001
parent "Walter" <walter digitalmars.com> writes:
Daniel Mantione wrote in message <9m19an$1a1b$1 digitaldaemon.com>...
Luckily you can turn off range checking, which you usually do when your
program is bug-free.

Range checking is a wonderful feature that goes too far when you can't turn it off for the production release.
Oct 15 2001
prev sibling parent "Sean L. Palmer" <spalmer iname.com> writes:
"Russell Bornschlegel" <kaleja estarcion.com> wrote in message
news:3B8422B8.80B09E1C estarcion.com...
 Daniel Mantione wrote:
 Yes, this looks like a very promising implementation to use sets. What


 are essentially saying is that an array of bits has set semantics, like


 "in" operator.

As currently specified, though, associative-array-of-bit actually has three states per key: 1, 0, or not-in-set. That's not a great fit to an underlying array-of-bit implementation.

Seems like a set is more of an associative array of a type that has no value and takes no storage. So I don't think associative array of any value type would be an optimal way to implement a set. Sean
Oct 28 2001
prev sibling next sibling parent reply "Walter" <walter digitalmars.com> writes:
"Russell Bornschlegel" <kaleja estarcion.com> wrote in message
news:3B83EF19.D755A19 estarcion.com...
 The D spec is silent on the implementation details for
 associative arrays, but they'd likely be binary trees (ordered
 keys, lookup time normally O(log2(n))) or hashes (disordered keys,
 lookup time normally O(1)).

They're a mix of hash tables and binary trees. The implementation would be free to pick its own way of implementing them.
Aug 23 2001
next sibling parent Russell Bornschlegel <kaleja estarcion.com> writes:
Walter wrote:
 
 "Russell Bornschlegel" <kaleja estarcion.com> wrote in message
 news:3B83EF19.D755A19 estarcion.com...
 The D spec is silent on the implementation details for
 associative arrays, but they'd likely be binary trees (ordered
 keys, lookup time normally O(log2(n))) or hashes (disordered keys,
 lookup time normally O(1)).

They're a mix of hash tables and binary trees. The implementation would be free to pick its own way of implementing them.

So the spec won't offer promises about key ordering? -R
Aug 23 2001
prev sibling parent "Rajiv Bhagwat" <dataflow vsnl.com> writes:
Walter <walter digitalmars.com> wrote in message
news:9m4329$2vv4$1 digitaldaemon.com...
 "Russell Bornschlegel" <kaleja estarcion.com> wrote in message
 news:3B83EF19.D755A19 estarcion.com...
 The D spec is silent on the implementation details for
 associative arrays, but they'd likely be binary trees (ordered
 keys, lookup time normally O(log2(n))) or hashes (disordered keys,
 lookup time normally O(1)).

They're a mix of hash tables and binary trees. The implementation would be free to pick its own way of implementing them.

Have you checked up 'Suneido' language, where the common 'object' data type is accesible *both* as asso. arrays and vectors? Taking their own example, this is how you can specify the object literals: #(1, 2, "abc", "def") #(name: "Joe", age: 23) #(1, "abc", name: "Joe") In the last example, the value of element 2 is "Joe", also accesible thru [2]. More on www.suneido.com -- Rajiv
Aug 24 2001
prev sibling parent "Walter" <walter digitalmars.com> writes:
Russell Bornschlegel wrote in message <3B83EF19.D755A19 estarcion.com>...
The D spec is silent on the implementation details for
associative arrays, but they'd likely be binary trees (ordered
keys, lookup time normally O(log2(n))) or hashes (disordered keys,
lookup time normally O(1)).

It's supposed to be an implementation detail <g>, but they are implemented as a hashed array of binary trees. My experience with them is that they are very efficient.
Oct 14 2001
prev sibling parent "Walter" <walter digitalmars.com> writes:
"Daniel Mantione" <daniel deadlock.et.tudelft.nl> wrote in message
news:9lvkln$a05$1 digitaldaemon.com...
 For the general case, are D's associative arrays good enough, Daniel?


int[char] set; char c; if (c in set) { }
Aug 23 2001
prev sibling parent reply "Sheldon Simms" <sheldon semanticedge.com> writes:
Im Artikel <9luk4s$2oqi$1 digitaldaemon.com> schrieb "Angus Graham"
<agraham_d agraham.ca>:

 "Daniel Mantione" <daniel deadlock.et.tudelft.nl> wrote
 That looks much cleaner! And it's much more efficient; instead of a
 strchr call for each character the compiler now only needs a set
 lookup. And because this is a constant set, the compiler can optimize
 this into a few compare operations.

Well, to be fair, the C version doesn't have to use strchr. You could just change if (strchr(safechars, *string) != NULL) { to char c = *string; if( (c>='a' && 'z'>=c) || (c>='A' && 'Z'>=c) || (c>='0' && '9'>=c) ) or even char set[][] = { {'a','z'}, {'A','Z'}, {'0','9'}; char c = *string; if( (c>=set[0][0] && set[0][1]>=c) || (c>=set[1][0] && set[1][1]>=c) || (c>=set[2][0] && set[2][1]>=c) ) or finally char set[][] = { {'a','z'}, {'A','Z'}, {'0','9'}; char c = *string; for( int i=0; i<sizeof(set); ++i ) { found = (c>=set[i][0] && set[i][1]>=c); } if(found) { which is a little hectic, bit is what I presume the Pascal version does internally.

Which basically proves Daniel's point. Why should the programmer have to code this explicitly? -- Sheldon Simms / sheldon semanticedge.com
Aug 21 2001
next sibling parent "D Man" <clockwork austin.rr.com> writes:
I second that.  I am not a fan of Pascal, but if there are features that are
this handy...

"Sheldon Simms" <sheldon semanticedge.com> wrote in message
news:9lul5d$2p87$1 digitaldaemon.com...
 Im Artikel <9luk4s$2oqi$1 digitaldaemon.com> schrieb "Angus Graham"
 <agraham_d agraham.ca>:

 "Daniel Mantione" <daniel deadlock.et.tudelft.nl> wrote
 That looks much cleaner! And it's much more efficient; instead of a
 strchr call for each character the compiler now only needs a set
 lookup. And because this is a constant set, the compiler can optimize
 this into a few compare operations.

Well, to be fair, the C version doesn't have to use strchr. You could just change if (strchr(safechars, *string) != NULL) { to char c = *string; if( (c>='a' && 'z'>=c) || (c>='A' && 'Z'>=c) || (c>='0' && '9'>=c) ) or even char set[][] = { {'a','z'}, {'A','Z'}, {'0','9'}; char c = *string; if( (c>=set[0][0] && set[0][1]>=c) || (c>=set[1][0] && set[1][1]>=c) || (c>=set[2][0] && set[2][1]>=c) ) or finally char set[][] = { {'a','z'}, {'A','Z'}, {'0','9'}; char c = *string; for( int i=0; i<sizeof(set); ++i ) { found = (c>=set[i][0] && set[i][1]>=c); } if(found) { which is a little hectic, bit is what I presume the Pascal version does internally.

Which basically proves Daniel's point. Why should the programmer have to code this explicitly? -- Sheldon Simms / sheldon semanticedge.com

Aug 21 2001
prev sibling parent reply "Angus Graham" <agraham_d agraham.ca> writes:
 Which basically proves Daniel's point. Why should the programmer have to
 code this explicitly?

Becuase if you have a large list of things to test membership in you can use a real container. If you have a tiny list you can use one line of code. How often would a built in set be useful? To me, seldom to never, so why cut down a tree and put it in every D manual? I'm not even too happy about having associative arrays built in. Much as I love them in Perl, it's just gonna make the runtime bigger and slower, my manual longer and heavier. A nice standard library is the place for containers. Angus Graham
Aug 21 2001
next sibling parent Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Angus Graham wrote:

 Which basically proves Daniel's point. Why should the programmer have to
 code this explicitly?

Becuase if you have a large list of things to test membership in you can use a real container.

This is true for complex types. Sets of records would be example be a very bad idea, the question comes wether they need to be stored in a tree, btree, or whatever. In a practical language the programmers needs to be in control of this. In these cases, a tree object or a btree object is more apropiate. But in the case of ordinal types, a set isn't easily replaced by a library.
  If you have a tiny list you can use one line of code.

Only in the case of a constant set! And even then, people are going to do things like strchr yo make things easy to maintain. With a set, you have both: clean looking code and very efficient code.
 How often would a built in set be useful?  To me, seldom to never, so why
 cut down a tree and put it in every D manual?

You have never programmed in Pasacal or Delphi? If I program in C I *really* miss the set.
 I'm not even too happy about having associative arrays built in.  Much as
 I love them in Perl, it's just gonna make the runtime bigger and slower,
 my
 manual longer and heavier.  A nice standard library is the place for
 containers.

There is some truth in this. Associative arrays also need to be stored in internal datastructures over which the programmer has no control. An object might be a good idea too here. If you do it with properties, it will feel like an array too. Greetings, Daniel Mantione
Aug 22 2001
prev sibling parent "Anthony Steele" <asteele nospam.iafrica.com> writes:
"Angus Graham" <agraham_d agraham.ca> wrote in message
news:9lump1$2qal$1 digitaldaemon.com...
 Which basically proves Daniel's point. Why should the programmer have to
 code this explicitly?

Becuase if you have a large list of things to test membership in you can

 a real container.

True, for instance, In Delphi (*The* pascal-derived language these days), a set may have up to 256 elements, no more. All it really is whole lot of bits side by side, 32 byets at most. Membership testing is implemented as bit testing, union as or-ing the bits, etc.
 If you have a tiny list you can use one line of code.
 How often would a built in set be useful?  To me, seldom to never, so why
 cut down a tree and put it in every D manual?

Speaking as someone who has used Delphi for several years, sets over an enum are very usefull, used often, and would be missed. The most common usage is for options to a class or proc. For instance, look at this code fragment: type TFontStyle = (fsBold, fsItalic, fsUnderline, fsStrikeOut); TFontStyles = set of TFontStyle; class TFont procedure setStyle(style: TFontStyles); // actually this would be a property, but one thing at a time ... end; MyFont.setStyle( [fsBold, fsUnderline]); .. MyFont.Style := myFont.Style + fsItalic; The implementation is effiicient, and so is the usage syntax. And it's type-safe. Object-Pascal is not perfect, but this feature is really nice
Sep 14 2001
prev sibling next sibling parent reply Charles Hixson <charleshixsn earthlink.net> writes:
Daniel Mantione wrote:
 Hi,
 
 One of the features I miss the most in C is the set. Being a member of the 
 Free Pascal development team, I program a lot in Pascal. Now I don't want 
 to say that Pascal rules and C sucks, but there are some things that Pascal 
 is superior in.
 
...

AVL-trees, and B+Trees. And other classical data structures. Perhaps a better approach would be to emphasize ways that make the language easy to extend with these features. If not, then if it came to a choice my vote would be for the inclusion of B+Trees as a standard language feature. I would want to use them far more frequently, and they are much more work to implement. So, perhaps the question should be, what possible language (as opposed to library) features would make it easier to integrate sets into the language? And how could these be generalized to support data strudtures in general? (Presumably including associative arrays, strings, and the other built in features.) One thing that most of these seem to do is to allow one to store data by means of some non-numeric keying function (usually a string, but lets try to keep this general). Another is to test the structure for the existence of that key. Another is to retrieve data associated with that key. Another is to remove a key, and its associated data. Anything else primitive-common? Then the operations are, essentially a[key]=x, x=a[key], x in a, and a[key]=null. Can these operations be defined for arbitrary user defined data structures? The one remaining operation is initialization. If a data structure were a class, then this could be handled with a constructor. So the problem would be in specifying how the argument list of the constructor could cope with the kinds of argument that you want to use to initialize a set. Is this a fair analysis? If so, then I feel it a better basis to proceed than on a data structure by data structure basis. And what is required here is that in be made an overloadable operator. (Well, and the argument list problem. I don't know how that should be handled. I usually start with an empty data structure and add things to it.)
Aug 22 2001
next sibling parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Charles Hixson wrote:
 If not, then if it came to a choice my
 vote would be for the inclusion of B+Trees as a standard language
 feature.  I would want to use them far more frequently, and they are
 much more work to implement.

Are you interested in the primitive functionality of B+Trees, or of some particular implementation-dependent characteristic of them? In a garbage-collected language like D, where you have few or no performance guarantees to begin with, it doesn't seem necessary to make a big deal over the latter.
 One thing that most of these seem to do is to allow one to store data by
 means of some non-numeric keying function (usually a string, but lets
 try to keep this general).  Another is to test the structure for the
 existence of that key.  Another is to retrieve data associated with that
 key.  Another is to remove a key, and its associated data.  Anything
 else primitive-common?

Yes: iterate over the whole collection, performing an arbitrary operation on each element. This is the only operation I see in your list that isn't supported by associative arrays in the D spec. A set can be represented by an associative array where the contents of an existing element are unused -- all you care about is the existence or absence of an element. Consider that the STL set and map containers are normally implemented as some flavor of binary tree, while Perl's associative array, which does essentially the same thing, is normally referred to and implemented as a hash. They're used the same way, but have slightly different performance characteristics -- that most people aren't worried about, because they're lazy and would otherwise be doing linear searches on arrays or linked lists, so the near-constant lookup time of a hash or the log2 lookup time of a tree is a huge win for them. Trees can also maintain the collection in order, while hashes can't.
 Then the operations are, essentially a[key]=x, x=a[key], x in a, and
 a[key]=null.

The D-spec associative array specifies "delete a[key]" instead of "a[key] = null", and I think you meant "key in a" instead of "x in a", but yeah. Note -- I do agree that the language should support adding new data structures for your particular needs; to do them reasonably requires: - operator overloading to make them pretty, including overloading operator delete, operator in, and operator []. - templates or the equivalent to make them reusable and type-safe. It looks like you aren't going to get both these features in early releases of D, unfortunately... -Russell B
Aug 22 2001
next sibling parent reply Charles Hixson <charleshixsn earthlink.net> writes:
Russell Bornschlegel wrote:
 Charles Hixson wrote:
 
If not, then if it came to a choice my
vote would be for the inclusion of B+Trees as a standard language
feature.  I would want to use them far more frequently, and they are
much more work to implement.

Are you interested in the primitive functionality of B+Trees, or of some particular implementation-dependent characteristic of them? In a garbage-collected language like D, where you have few or no performance guarantees to begin with, it doesn't seem necessary to make a big deal over the latter.

remember it from session to session. An external database can do this, but installing it remotely can be a large hassle, and it's often overkill for what I need.
 
One thing that most of these seem to do is to allow one to store data by
means of some non-numeric keying function (usually a string, but lets
try to keep this general).  Another is to test the structure for the
existence of that key.  Another is to retrieve data associated with that
key.  Another is to remove a key, and its associated data.  Anything
else primitive-common?

Yes: iterate over the whole collection, performing an arbitrary operation on each element. This is the only operation I see in your list that isn't supported by associative arrays in the D spec. A set can be represented by an associative array where the contents of an existing element are unused -- all you care about is the existence or absence of an element. Consider that the STL set and map containers are normally implemented as some flavor of binary tree, while Perl's associative array, which does essentially the same thing, is normally referred to and implemented as a hash. They're used the same way, but have slightly different performance characteristics -- that most people aren't worried about, because they're lazy and would otherwise be doing linear searches on arrays or linked lists, so the near-constant lookup time of a hash or the log2 lookup time of a tree is a huge win for them. Trees can also maintain the collection in order, while hashes can't.

"for_each" operator. But that could be implemented as a function, though an operator would be nicer. Remember, that if these structures are implemented as classes, then additional functions can be added as needed, by sub-classing. (E.g., is an each operator sensible on a set? Only the common sensible ones are primitive-common.) Part of the question here is what are the inheritance characteristics. How does one specify a generic class parameter? A set of integers and a set of strings have slightly different characteristics. Does the inheritance mechanism allow for this specialization? If I define a set of wheels, what is it's relationship to a set of bicycle wheels? (Assuming that BicycleWheel is a descendant from Wheel.) Can I compare membership between the two sets? etc. Another question is what kind of languate is D? Clearly STL/C++ and Python would have much different answers if I asked them "What kind of object can I put into a set?" and "What kind of object can I get back out of a set?" Python can look at the thing you get back and tell what it is. C++ depends on the definition of the set to tell it what kind of object it got back. C++ is faster. Python is more flexible. Now my personal needs are for a language that produces stand-alone code. Python has problems with this (though that's being worked on). To me, speed is a secondary consideration. I'm currently working on a dataset of about 1500 cases with a basically N^2 complexity. It takes about 10-15 minutes to run using Eiffel code with all of the checks on. I'd like a faster execution, but it's not a killer. (Most of that time comes from hash table processing. I'm searching for a better alternative.) But it MUST be stand alone code. People need to be able to run it from out on the server, and I may never have seen their computer. Scratch Python. Scratch all interpretive languages. Scratch all languages that require massive dll's. etc. So that's how I notice what features are optimum. Garbage collection is a real winner. A B+Tree would really help, as would any method for maintaining persistent variables... help, but not be decisive. Stand-alone code is decisive.
 
Then the operations are, essentially a[key]=x, x=a[key], x in a, and
a[key]=null.

The D-spec associative array specifies "delete a[key]" instead of "a[key] = null", and I think you meant "key in a" instead of "x in a", but yeah. Note -- I do agree that the language should support adding new data structures for your particular needs; to do them reasonably requires: - operator overloading to make them pretty, including overloading operator delete, operator in, and operator []. - templates or the equivalent to make them reusable and type-safe. It looks like you aren't going to get both these features in early releases of D, unfortunately... -Russell B

change. So now's the time to speak up. If I don't at least mention what I feel is important, then it's only my fault if it doesn't happen. If it doesn't happen anyway ... all languages are design tradeoffs. You examine what's around, and you see what you can make do what you need done. (And I'm more interested in the Linux version than in the Windows version, so what's in the early releases isn't THAT significant. But if I don't get people thinking about it, then it probably won't be in the later one's either.)
Aug 22 2001
parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Charles Hixson wrote:
 
 Russell Bornschlegel wrote:
 Charles Hixson wrote:
One thing that most of these seem to do is to allow one to store data by
means of some non-numeric keying function (usually a string, but lets
try to keep this general).  Another is to test the structure for the
existence of that key.  Another is to retrieve data associated with that
key.  Another is to remove a key, and its associated data.  Anything
else primitive-common?

Yes: iterate over the whole collection, performing an arbitrary operation on each element. This is the only operation I see in your list that isn't supported by associative arrays in the D spec.

You're right. Ok, in addition to the "in" operator we need an "each" or "for_each" operator. But that could be implemented as a function, though an operator would be nicer.

Turns out we have it in the D spec: for (int i = 0; i < assoc_array.keys.length; i++) { operate_on( assoc_array[ assoc_array.keys[i] ] ); }
 Another question is what kind of languate is D?  Clearly STL/C++ and
 Python would have much different answers if I asked them "What kind of
 object can I put into a set?" and "What kind of object can I get back
 out of a set?"  Python can look at the thing you get back and tell what
 it is.  C++ depends on the definition of the set to tell it what kind of
 object it got back.  C++ is faster.  Python is more flexible.

I know you're concerned with the builtin functionality, but it's worth mentioning that you can get the Pythonish functionality (if I understand what you're talking about -- I don't know Python) from C++ in a number of ways if you're willing to do some work. An STL container can store references to polymorphic types. C++ can do just about anything, wrap that functionality in a class, and tuck it away -- the only problem is that someone has to write that class in the first place. The code to do it, apparently, is much smaller than the Ada equivalent, but that's not saying a lot. ;)
 Now my personal needs are for a language that produces stand-alone code.
   Python has problems with this (though that's being worked on).  To me,
 speed is a secondary consideration.  I'm currently working on a dataset
 of about 1500 cases with a basically N^2 complexity. [problem description
 snipped]

All I can say is "C++ and STL maps." There's a reason C++ is widely used, and its syntactic elegance sure ain't it...
 It looks like you aren't going to get both these features in early
 releases of D, unfortunately...

Well, Walter said that it was alpha, and the features were subject to change. So now's the time to speak up. If I don't at least mention what I feel is important, then it's only my fault if it doesn't happen.

All granted. My concern right now is that a one-man, no-budget effort to develop a new language can get derailed very easily by people screaming "don't even bother unless you're going to put Feature X in!" I want Walter to get a usable compiler out, _then_ we can beat on it and complain in a more informed manner :) -Russell B
Aug 22 2001
next sibling parent reply Charles Hixson <charleshixsn earthlink.net> writes:
Russell Bornschlegel wrote:
 Charles Hixson wrote:
 
Russell Bornschlegel wrote:

Charles Hixson wrote:

One thing that most of these seem to do is to allow one to store data by
means of some non-numeric keying function (usually a string, but lets
try to keep this general).  Another is to test the structure for the
existence of that key.  Another is to retrieve data associated with that
key.  Another is to remove a key, and its associated data.  Anything
else primitive-common?

operation on each element. This is the only operation I see in your list that isn't supported by associative arrays in the D spec.

"for_each" operator. But that could be implemented as a function, though an operator would be nicer.

Turns out we have it in the D spec: for (int i = 0; i < assoc_array.keys.length; i++) { operate_on( assoc_array[ assoc_array.keys[i] ] ); }

doesn't make it clean to use. Contrast that with: assoc_array.for_each.key(k) operate_on (k); The syntax of that example is a bit wierd, as I am mangling several different languages, but I trust the meaning is clear. The question here is how the key should be passed to the operate_on method.
 
...
 
 C++ can do just about anything, wrap that functionality in a 
 class, and tuck it away -- the only problem is that someone has
 to write that class in the first place. The code to do it, 
 apparently, is much smaller than
 the Ada equivalent, but that's not saying a lot. ;)

Actually, except in the sense of algorithmic completeness, there are a lot of things that neither C++ nor any other statically bound language can do. But there's been a big speed and portability tradeoff, so languages have tended to divide into two camps, the dynamic linkers and the static linkers. C++, Ada, Eiffel, that kind are static linkers. Smalltalk, Lisp, Python, Ruby, that kind are the dynamic linkers. There are reasons for the split, and neither side is able to really capture the features of the other (though there are a lot of wild claims made). Java is a rather interesting mix, sort of standing half way between them. It attempts to get the advantages of both sides, and ends up getting a lot of the disadvantages of each, also. As well as some unique strengths. (Which it tends to ignore in favor of being familiar to C programmers, but look at Kiev to see some of the possibilities.)
 
 
...

All I can say is "C++ and STL maps." There's a reason C++ is widely used, and its syntactic elegance sure ain't it...

Doing it by hand in Eiffel is, for me, easier and more portable than using C++ with the STL. Possibly if I had to throw a Mac into the equation, my answer would be different, but so far I haven't needed that. I guess that if someone tells me it has to run on a Mac, I may tell them "Yellow Dog Linux". It's not a good answer, but I haven't really studied that question. Or maybe by that time Python will be able to do stand-alone compiles. Or Ruby. But it won't be C++ until after they fix their inheritance rules mess.
 
 
...
 
 All granted. My concern right now is that a one-man, no-budget effort 
 to develop a new language can get derailed very easily by people screaming
 "don't even bother unless you're going to put Feature X in!" I want Walter
 to get a usable compiler out, _then_ we can beat on it and complain in 
 a more informed manner :)
 
 -Russell B
 

syntactic sugar. Maybe I'm wrong. Maybe I get overenthusiastic. But I try. E.g., most of this discussion was about what minimal changes could make lots of standard data structures easy and clean to use. Most of these would be library features. Inheritance is already scheduled to be a lot more dynamic than in C++, garbage collection is already built in (eliminating a lot of work for destructors). Etc. So what is being discussed is whether or not a couple of prepositions could be added, and whether or not they would be useful enough to bother with. But with decently flexible inheritance and overloadable user defined operators, then, say, :in: and :each: could be defined within a class tree, and all data structures could just implement their own flavor of it. So it would all reduce to libraries. But if it had to be written "in( xxx )" and "each ( xxx )" then it would be much uglier and less friendly.
Aug 22 2001
parent reply Russell Bornschlegel <kaleja estarcion.com> writes:
Charles Hixson wrote:
 
 Russell Bornschlegel wrote:
 Turns out we have it in the D spec:

   for (int i = 0; i < assoc_array.keys.length; i++)
   {
       operate_on( assoc_array[ assoc_array.keys[i] ] );
   }

doesn't make it clean to use. Contrast that with: assoc_array.for_each.key(k) operate_on (k); The syntax of that example is a bit wierd, as I am mangling several different languages, but I trust the meaning is clear. The question here is how the key should be passed to the operate_on method.

Hmm. How about: foreach (keytype k in assoc_array.keys) { operate_on( k ); } This overloads "in" somewhat, but the foreach should be a sufficient hint to the parser; the keytype (int, string, whatever) makes the k look like a declaration like any other.
 C++ can do just about anything, wrap that functionality in a
 class, and tuck it away...

Actually, except in the sense of algorithmic completeness, there are a lot of things that neither C++ nor any other statically bound language can do.

Frankly, I've never used a dynamically linked language, I don't think. Can you give me a short example of a cool thing you can do with dynamic linking?
    So what is being discussed is whether or not a couple of prepositions
 could be added, and whether or not they would be useful enough to bother
 with.  But with decently flexible inheritance and overloadable user
 defined operators, then, say, :in: and :each: could be defined within a
 class tree, and all data structures could just implement their own
 flavor of it.  So it would all reduce to libraries.  But if it had to be
 written "in( xxx )" and "each ( xxx )" then it would be much uglier and
 less friendly.

Okay. I freely admit to being unafraid of ugly constructs, and to having been thoroughly warped by using C++. I firmly believe that no matter how elegant the language can be, some damn fool is going to use two-space indents, asinine bracketing styles, uncommented state machines implemented via numeric literal cases in huge nested switches, or other constructs of equal value, and that I'll be forced to maintain their code. C++ is the least of my problems this week. :) -RB
Aug 22 2001
parent reply Charles Hixson <charleshixsn earthlink.net> writes:
Russell Bornschlegel wrote:
 Charles Hixson wrote:
 
...

Hmm. How about: foreach (keytype k in assoc_array.keys) { operate_on( k ); } This overloads "in" somewhat, but the foreach should be a sufficient hint to the parser; the keytype (int, string, whatever) makes the k look like a declaration like any other.

 
C++ can do just about anything, wrap that functionality in a
class, and tuck it away...

lot of things that neither C++ nor any other statically bound language can do.

Frankly, I've never used a dynamically linked language, I don't think. Can you give me a short example of a cool thing you can do with dynamic linking?

var = eval(include(filename.suf).something(include(otherfile.suf))) + "qwert"; The reason that most AI work is done in the dynamic languages isn't only because Lisp is easier to parse (or Forth would be more popular) and it sure isn't speed. It's because code can copy itself, modify the copy, and then transfer execution to the copy. Even where parsing is a bit difficult (can you say Python) this ability is maintained. This normally means that you need to cart around an interpreter to do the job, but not always. Some Smalltalk dialects can export their meaning as C code, and some dialects of Lisp are directly compileable. Now truthfully, this could also be done with C (assuming decent cooperation from the OS), but it's so difficult that nobody does it. So C, etc., don't get used in the areas that need that kind of flexibility. And Lisp, Python, Ruby, etc. don't get used where speed is needed, though there's a study that "proves" that Lisp code can execute as fast as C code. (I think that what they actually end up comparing is code optimizers, but that's not what they claim to show... and what's wrong with saying "My code can be more highly optimized with automatic tools, so that for a sufficiently complex task it is faster than your code!", but that's not what they said.)
 
...
 
 Okay. I freely admit to being unafraid of ugly constructs, and to having
 been thoroughly warped by using C++. I firmly believe that no matter how
 elegant the language can be, some damn fool is going to use two-space 
 indents, asinine bracketing styles, uncommented state machines implemented
 via numeric literal cases in huge nested switches, or other constructs of
 equal value, and that I'll be forced to maintain their code. C++ is the
 least of my problems this week. :)
 
 -RB
 

problem for me (except when stupid editors convert my tabs into spaces, and won't let me say what columns the tabs are supposed to represent).
Aug 22 2001
parent Russell Bornschlegel <kaleja estarcion.com> writes:
Charles Hixson wrote:
 
 Russell Bornschlegel wrote:
 Frankly, I've never used a dynamically linked language, I don't
 think. Can you give me a short example of a cool thing you can
 do with dynamic linking?

var = eval(include(filename.suf).something(include(otherfile.suf))) + "qwert"; The reason that most AI work is done in the dynamic languages isn't only because Lisp is easier to parse (or Forth would be more popular) and it sure isn't speed. It's because code can copy itself, modify the copy, and then transfer execution to the copy. Even where parsing is a bit difficult (can you say Python) this ability is maintained. This normally means that you need to cart around an interpreter to do the job, but not always. Some Smalltalk dialects can export their meaning as C code, and some dialects of Lisp are directly compileable. Now truthfully, this could also be done with C (assuming decent cooperation from the OS), but it's so difficult that nobody does it. So C, etc., don't get used in the areas that need that kind of flexibility.

Ah, okay, Perl has this also -- I've seen it, seen that it could be cool, but outside of one cookbook use (a Perl program eval'ing a startup/rc file written in Perl) I haven't tried it. Really it's dynamic code- evaluation/dynamic compilation, as much as dynamic linking. I suppose I could invoke a C compiler to build a DLL and then bind the DLL, in C/Win32, but that's probably not really very time-efficient... :) And not really supported by standard C, but with the proper OS support you can build a sequence of native machine code in a buffer and then execute that buffer. High performance 3D applications have been known to do this, for highly critical polygon-pushing paths. Also, blah blah blah security blah blah blah executing arbitrary code from an external file blah blah blah. :) -RB
Aug 22 2001
prev sibling parent Dan Hursh <hursh infonet.isl.net> writes:
Russell Bornschlegel wrote:
 
 Charles Hixson wrote:
 Yes: iterate over the whole collection, performing an arbitrary
 operation on each element. This is the only operation I see in your
 list that isn't supported by associative arrays in the D spec.

You're right. Ok, in addition to the "in" operator we need an "each" or "for_each" operator. But that could be implemented as a function, though an operator would be nicer.

Turns out we have it in the D spec: for (int i = 0; i < assoc_array.keys.length; i++) { operate_on( assoc_array[ assoc_array.keys[i] ] ); }

Yes, but can this break if you are adding or deleting certain elements for the array as you go? In that case you would have to do this: string[] keys = assoc_array.keys; for (int i = 0; i < keys.length; i++){ if( bad_element(assoc_array[keys[i]]) ) delete assoc_array[keys[i]]; } A foreach that worked on arrays with a known size and associative arrays would be nicer and less error prone. Dan
Aug 26 2001
prev sibling parent Russell Bornschlegel <kaleja estarcion.com> writes:
Please excuse reply-to-self.

Russell Bornschlegel wrote:
 Yes: iterate over the whole collection, performing an arbitrary
 operation on each element. This is the only operation I see in your
 list that isn't supported by associative arrays in the D spec.

My mistake: myarray.keys returns the keys of an associative array, over which you can iterate to your hearts content. -Russell B
Aug 22 2001
prev sibling next sibling parent reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Charles Hixson wrote:

 It's hard to argue that sets wouldn't be nice to have.  So would
 AVL-trees, and B+Trees.  And other classical data structures.  Perhaps a
 better approach would be to emphasize ways that make the language easy
 to extend with these features.  If not, then if it came to a choice my
 vote would be for the inclusion of B+Trees as a standard language
 feature.  I would want to use them far more frequently, and they are
 much more work to implement.

Nonsense. The set is an elementary type, just like the integer or pointer and no library can easily replace it, just like you cannot easily implement a float in a library. In fact, with any example you would be able to give, a the rewrite of that example with a set if almost allways superior in efficiency and/or maintainability and never has worse efficiency. It is true that mathematically, a set can consist of everything, but this is not done so in programming languages. It is true that a mathematically behaving set (that can store everything) can better be implemented as a set. With operator overloading you can make it behave as a set. Now the elementary datatype. A set is a bitmap in all programming languages that support it. In Pascal a set consits of a maximum of 256 different items, because the compiler uses a byte to enumerate them. This is a stupid limitation of Pascal, but the designers definitely got the idea. The built-in set should support types that can be enumerated. For example: enum colours {red, green, blue}; .. would do as the basetype of a set. char[]; .. would not do. You cannot enumerate all possible strings. char[2]; .. perhaps would do. That would be a bitmap of 65536 entries. Greetings, Daniel Mantione
Aug 22 2001
parent reply Charles Hixson <charleshixsn earthlink.net> writes:
Daniel Mantione wrote:
 Charles Hixson wrote:
 
 
It's hard to argue that sets wouldn't be nice to have.  So would
AVL-trees, and B+Trees.  And other classical data structures. ...

Nonsense. The set is an elementary type, just like the integer or pointer and no library can easily replace it, just like you cannot easily implement a float in a library. In fact, ... .. perhaps would do. That would be a bitmap of 65536 entries. Greetings, Daniel Mantione

Considering that bit arrays are an included part of the language, I fail to understand why a set could not be implemented as a library. Given that the compiler would have all the necessary information, it should (this might be optomistic) be able to optimize references to your "SmallSet" class as inline calls. So the problem is just syntax, which is what I was discussing. If that was answered, then I didn't understand the answer. Also, neither strings, associative arrays, nor sets are elementary types. They are composits. A reasonable way to model a string is as an array of characters. A reasonable way to model an associative array is as a hash table. And a reasonable way to model a small set is as a bit vector. But even these aren't the elementary types. If you wish evidence, consider C++ without the STL, or other complex libraries. You can build each of those types out of the elements present, yet none of them are present. And the things that you build them out of are simpler constructs that have been inherited from C. Now, perhaps what you meant was that it seems to you vastly preferable that a set type be built-in to the language. If so, then you have the right of it. I can't argue about what your opinion is. But others may legitimately have different opinions. What I am proposing is that the language support the operations needed to facilitate an easy use of sets, among other data structures. And that the implementation be parcelled out to the constructors of the libraries. This seems to me a much more efficient approach, as well as a more reasonable one. But then I don't often feel the need for sets. I even want to use bags more often than I want to use sets, and usually I prefer that my data be in some sorted form with attatched data structures. So I am also biased.
Aug 22 2001
parent reply Daniel Mantione <daniel deadlock.et.tudelft.nl> writes:
Charles Hixson wrote:

 Considering that bit arrays are an included part of the language, I fail
 to understand why a set could not be implemented as a library.  Given
 that the compiler would have all the necessary information, it should
 (this might be optomistic) be able to optimize references to your
 "SmallSet" class as inline calls.  So the problem is just syntax, which
 is what I was discussing.  If that was answered, then I didn't
 understand the answer.

To optimize things well, you need compiler magic. A simple ... if i in [0..9,18..20] ... would never get optimized if the set was implemented in a library. So compiler would be able to see that it can optimize the bitmap away in this case. About syntax, you would like that a set that is implemented with a btree in a library for example, programs same as the built in set. To be able to do that you need operator overloading, which is being heavily dicussed. Daniel
Aug 22 2001
parent Charles Hixson <charleshixsn earthlink.net> writes:
Daniel Mantione wrote:
 Charles Hixson wrote:
 
 
Considering that bit arrays are an included part of the language, I fail
to understand why a set could not be implemented as a library.  Given
that the compiler would have all the necessary information, it should
(this might be optomistic) be able to optimize references to your
"SmallSet" class as inline calls.  So the problem is just syntax, which
is what I was discussing.  If that was answered, then I didn't
understand the answer.

To optimize things well, you need compiler magic. A simple ... if i in [0..9,18..20] ... would never get optimized if the set was implemented in a library. So compiler would be able to see that it can optimize the bitmap away in this case. About syntax, you would like that a set that is implemented with a btree in a library for example, programs same as the built in set. To be able to do that you need operator overloading, which is being heavily dicussed. Daniel

A library should provide many different varieties of data structure. Not just one. You chose the flavor that fits your problem. As to compound ranges (not to my mind the same thing as a set, but rather one thing that is sometimes handled by sets), I don't know what the best choice would be. If there were a range primitive, then one might want to say: if i in [0..9] or i in [18..20] a bit clumsier, I admit. Or one could define a class that implemented range handling in the way that one chose, as defined by the problem under consideration. OTOH, I will admit that it would be nice if complex range constants were a recognized data type (which would imply complex range variables). And that one of the more reasonable ways to implement that would be as a set. But not the only reasonable way. It's perfectly reasonable to have a complex range that can handle things like: Range r = "Alpha" .. "Blueberry" union "Peanuts" ... "Zebras" All you need for this is two vectors of string, call them lower and upper. (The rest is a lot of work, but basically obvious.) I've needed to do this a couple of times, and once I needed to deal with complex ranges of floating point numbers, and even needed to perform arithmetic on the ranges. Consider what: r -= "Spinach"; would mean. (Defining what arithmetic and comparison ops mean when applied to ranges of floating point values is a bit interesting. That is probably very domain specific. But I needed to do it the time I needed ranges of floating point numbers [well, rationals was all I really needed, but it was easier to use floats].) Here union, intersect, remove, etc. are the basic ops. But these map in a relatively straightforward way onto the general data structure operations that I was proposing. (Relatively. It's certainly a less good fit than most.) But I rarely end up dealing with simple numbers except as numbers, so *I* don't see much need for the Pascal kind of set. Except occasionally.
Aug 22 2001
prev sibling parent reply "Anthony Steele" <asteele nospam.iafrica.com> writes:
"Charles Hixson" <charleshixsn earthlink.net> wrote in message
news:3B83D667.40505 earthlink.net...

...

AVL-trees, and B+Trees. And other classical data structures. Perhaps a better approach would be to emphasize ways that make the language easy to extend with these features.

Most things can be added to an OO language simply by writing the appropriate classes, or finding them in the standard library. But I have not seen sets done well this way in an efficient manner - To take an example, Java, where classes are by design the *only* mechanism for making new types, there is a set class, and no language support for enums. However using sets and option-objects is so ugly and cumbersome that everyone, sun included, just uses named integer constants. This is a giant leap backwards. Built-in enums and sets in Delphi are a great enabler.
Sep 14 2001
parent Charles Hixson <charleshixsn earthlink.net> writes:
Anthony Steele wrote:

 "Charles Hixson" <charleshixsn earthlink.net> wrote in
 message news:3B83D667.40505 earthlink.net...


 ...

would AVL-trees, and B+Trees. And other classical data structures. Perhaps a better approach would be to emphasize ways that make the language easy to extend with these features.

Most things can be added to an OO language simply by writing the appropriate classes, or finding them in the standard library. But I have not seen sets done well this way in an efficient manner - To take an example, Java, where classes are by design the *only* mechanism for making new types, there is a set class, and no language support for enums. However using sets and option-objects is so ugly and cumbersome that

is a giant
 leap backwards. Built-in enums and sets in Delphi are a great 


ability to overload the indexing operators.
 everyone, sun included, just uses named integer

and sets in Delphi are a great enabler.

ability to overload the indexing operators. In Python, e.g., the same opeartors used to set and access the hash table directories, can also be used to access B+Tree style databases. It's true that one needs ancillary operations to access the additional features (e.g., in-order traversal), but the features of set by key and retrieve by key can be accessed via a simple: a{"peanut"} = "butter"; print a{"peanut"} --> butter In python the key step is that when on initializes the variable ("a" in this case), instead of initializing it as a hash table: a = {} or a = {"Able" : "was", "I" : "ere"} one initializes it as a database: a = db("C:\file\location.dbm") The type of database is determined by the module "anydbm" which looks at the file to figure out which of three or four kinds of database it is. The B+Tree version that I'm speaking of is the SleepyCat database. But most of this doesn't require run-time configuration. Clearly one might prefer to declare at compile time that it was a B+Tree rather than a flat-file lookup table, but as long as the ancestral class (abstract class or interface?), say, DBM, had the requisite methods defined, that would be all that was required. Then the methods could be activated at run time. But if the standard operations can't be overloaded, then this falls through. As an alternative, I have proposed using demarkations, e.g. :+:, but this doesn't work well when used as indexing syntax, consider: a:[:"peanut":}: = "butter"; I'd almost prefer: a.set("peanut").to("butter"); or: a("peanut").set_to("butter");
Sep 17 2001
prev sibling parent "Walter" <walter digitalmars.com> writes:
An array of bits in D probably comes closest to what you're looking
for. -Walter
Oct 14 2001