www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.dtl - initial cut at "minimal template lib"

reply Ben Hinkle <bhinkle4 juno.com> writes:
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8Bit

Well yesterday I was poking around with Java's Collections Framework and
that didn't go so well since it ran into various dmd bugs and it also
wasn't meshing well with existing D concepts like dynamic and assoc arrays.
So this morning I switched tactics and have started a "minimal template
library". The only thing I have so far is list.d (attached). I've pasted
below the unittest for list.d to give a flavor of usage (hint: List is a
parametrized struct). Basically List behaves alot like dynamic arrays
except the obvious O(n)/O(1) differences. Feedback welcome.

  List!(int) x;
  x.add(3);
  x.add(4);
  assert( x[0] == 3 );
  assert( x[1] == 4 );
  assert( x.length == 2 );

  // test addFront
  List!(int) y;
  y.addFront(4);
  y.addFront(3);

  // test ==
  assert( x == y );
  List!(int) w = x.dup;
  w.add(5);
  assert( x != w);

  // test remove
  assert( w.remove == 5 );
  w.trim();
  w.add(5);

  // test reverse lists
  List!(int) z = y.reverse.apply;
  assert( z[0] == 4 );
  assert( z[1] == 3 );

  // test foreach iteration
  foreach(int n, inout int val; z) {
    val = n*10;
  }
  assert( z[0] == 0 );
  assert( z[1] == 10 );
  foreach(int n, int val; y.reverse()) {
    assert(x[1-n] == val);
  }

  // test slicing
  List!(int) v = w[1..3];
  assert( v.length == 2 );
  assert( v[0] == 4 );
  assert( v[1] == 5 );

  // test another node type
  List!(char[]) str;
  str.add("hello");
  str.add("world");
  assert( str[str.length-1] == "world" );
Jul 18 2004
next sibling parent reply "Matthew" <admin stlsoft.dot.dot.dot.dot.org> writes:
Ben

Pending some compiler fixes, I'm only days away from releasing 0.1 of DTL. Do
you
want to perhaps dovetail our efforts? I've currently got List, Vector, Queue and
Map, so maybe if you're feeling creative you could look at some different types,
so as to avoid wasting effort?

Of course, if you're pioneering a solo course, that's fine. I'll meet you at the
colosseum. ;)

Matthew


"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:cdeeab$2haf$1 digitaldaemon.com...
 Well yesterday I was poking around with Java's Collections Framework and
 that didn't go so well since it ran into various dmd bugs and it also
 wasn't meshing well with existing D concepts like dynamic and assoc arrays.
 So this morning I switched tactics and have started a "minimal template
 library". The only thing I have so far is list.d (attached). I've pasted
 below the unittest for list.d to give a flavor of usage (hint: List is a
 parametrized struct). Basically List behaves alot like dynamic arrays
 except the obvious O(n)/O(1) differences. Feedback welcome.

   List!(int) x;
   x.add(3);
   x.add(4);
   assert( x[0] == 3 );
   assert( x[1] == 4 );
   assert( x.length == 2 );

   // test addFront
   List!(int) y;
   y.addFront(4);
   y.addFront(3);

   // test ==
   assert( x == y );
   List!(int) w = x.dup;
   w.add(5);
   assert( x != w);

   // test remove
   assert( w.remove == 5 );
   w.trim();
   w.add(5);

   // test reverse lists
   List!(int) z = y.reverse.apply;
   assert( z[0] == 4 );
   assert( z[1] == 3 );

   // test foreach iteration
   foreach(int n, inout int val; z) {
     val = n*10;
   }
   assert( z[0] == 0 );
   assert( z[1] == 10 );
   foreach(int n, int val; y.reverse()) {
     assert(x[1-n] == val);
   }

   // test slicing
   List!(int) v = w[1..3];
   assert( v.length == 2 );
   assert( v[0] == 4 );
   assert( v[1] == 5 );

   // test another node type
   List!(char[]) str;
   str.add("hello");
   str.add("world");
   assert( str[str.length-1] == "world" );

Jul 18 2004
parent reply Ben Hinkle <bhinkle4 juno.com> writes:
My next target is a red-black tree for sorted maps. I've also written a
little set of array helpers: 
- reserve space for a dynamic array
- reserve space for an assoc array
- clear out an assoc array without losing capacity
- foreach backwards over a dyn array without reversing the elements in place

So in total mintl will have 3 files (maybe plus a doc file if I'm feeling
ambitious). If the red-black tree can be reused in DTL that would be cool
but I'd like to let these things evolve independently for a while. I don't
mean to be a pain in the tush by putting out a "competing" List/Map/etc but
I just wanted to test out some ideas. For instance, do we need iterators?
maybe not. Can the types be structs? I think so. Stuff like that. All of
your recent DTL posting got me thinking about these things. It would be
nice to keep the concepts as simple as the ones for dynamic arrays and
assoc arrays. Anyhow, I'm gonna finish up the rbtree in the next few days
or so.

-Ben

Matthew wrote:

 Ben
 
 Pending some compiler fixes, I'm only days away from releasing 0.1 of DTL.
 Do you want to perhaps dovetail our efforts? I've currently got List,
 Vector, Queue and Map, so maybe if you're feeling creative you could look
 at some different types, so as to avoid wasting effort?
 
 Of course, if you're pioneering a solo course, that's fine. I'll meet you
 at the colosseum. ;)
 
 Matthew
 
 
 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:cdeeab$2haf$1 digitaldaemon.com...
 Well yesterday I was poking around with Java's Collections Framework and
 that didn't go so well since it ran into various dmd bugs and it also
 wasn't meshing well with existing D concepts like dynamic and assoc
 arrays. So this morning I switched tactics and have started a "minimal
 template library". The only thing I have so far is list.d (attached).
 I've pasted below the unittest for list.d to give a flavor of usage
 (hint: List is a parametrized struct). Basically List behaves alot like
 dynamic arrays except the obvious O(n)/O(1) differences. Feedback
 welcome.

   List!(int) x;
   x.add(3);
   x.add(4);
   assert( x[0] == 3 );
   assert( x[1] == 4 );
   assert( x.length == 2 );

   // test addFront
   List!(int) y;
   y.addFront(4);
   y.addFront(3);

   // test ==
   assert( x == y );
   List!(int) w = x.dup;
   w.add(5);
   assert( x != w);

   // test remove
   assert( w.remove == 5 );
   w.trim();
   w.add(5);

   // test reverse lists
   List!(int) z = y.reverse.apply;
   assert( z[0] == 4 );
   assert( z[1] == 3 );

   // test foreach iteration
   foreach(int n, inout int val; z) {
     val = n*10;
   }
   assert( z[0] == 0 );
   assert( z[1] == 10 );
   foreach(int n, int val; y.reverse()) {
     assert(x[1-n] == val);
   }

   // test slicing
   List!(int) v = w[1..3];
   assert( v.length == 2 );
   assert( v[0] == 4 );
   assert( v[1] == 5 );

   // test another node type
   List!(char[]) str;
   str.add("hello");
   str.add("world");
   assert( str[str.length-1] == "world" );


Jul 19 2004
parent reply "Matthew" <admin.hat stlsoft.dot.org> writes:
"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:cdgfi3$c61$1 digitaldaemon.com...
 My next target is a red-black tree for sorted maps. I've also written a
 little set of array helpers:
 - reserve space for a dynamic array
 - reserve space for an assoc array
 - clear out an assoc array without losing capacity
 - foreach backwards over a dyn array without reversing the elements in

 So in total mintl will have 3 files (maybe plus a doc file if I'm feeling
 ambitious). If the red-black tree can be reused in DTL that would be cool
 but I'd like to let these things evolve independently for a while. I don't
 mean to be a pain in the tush by putting out a "competing" List/Map/etc

 I just wanted to test out some ideas. For instance, do we need iterators?
 maybe not. Can the types be structs? I think so. Stuff like that. All of
 your recent DTL posting got me thinking about these things. It would be
 nice to keep the concepts as simple as the ones for dynamic arrays and
 assoc arrays. Anyhow, I'm gonna finish up the rbtree in the next few days
 or so.

You're not being a pain in the slightest. The approach you've described sounds perfectly attuned with my own. I'm not really focusing on particular containers at the moment, I'm trying to get the overall "paradigm" sorted, if you'll pardon my grandiloquence. My current focus is trying to get Walter to change some parts of the language, so we can compose filters. I'm going to do a workaround, but the real thing'd be much easier. In the long run, I hope my vision of DTL is accepted/acceptable, and that all contributions of specific container classes all fall into a consistent library. Regarding iterators, I'm currently doubtful about them. I'm quite certain that they'll have far less important in D than they do in C++. I've been thinking about the struct/class issue, and I'm pleased that you're also thinking about it. I look forward to hearing more of your thoughts.
 -Ben

 Matthew wrote:

 Ben

 Pending some compiler fixes, I'm only days away from releasing 0.1 of


 Do you want to perhaps dovetail our efforts? I've currently got List,
 Vector, Queue and Map, so maybe if you're feeling creative you could


 at some different types, so as to avoid wasting effort?

 Of course, if you're pioneering a solo course, that's fine. I'll meet


 at the colosseum. ;)

 Matthew


 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:cdeeab$2haf$1 digitaldaemon.com...
 Well yesterday I was poking around with Java's Collections Framework



 that didn't go so well since it ran into various dmd bugs and it also
 wasn't meshing well with existing D concepts like dynamic and assoc
 arrays. So this morning I switched tactics and have started a "minimal
 template library". The only thing I have so far is list.d (attached).
 I've pasted below the unittest for list.d to give a flavor of usage
 (hint: List is a parametrized struct). Basically List behaves alot like
 dynamic arrays except the obvious O(n)/O(1) differences. Feedback
 welcome.

   List!(int) x;
   x.add(3);
   x.add(4);
   assert( x[0] == 3 );
   assert( x[1] == 4 );
   assert( x.length == 2 );

   // test addFront
   List!(int) y;
   y.addFront(4);
   y.addFront(3);

   // test ==
   assert( x == y );
   List!(int) w = x.dup;
   w.add(5);
   assert( x != w);

   // test remove
   assert( w.remove == 5 );
   w.trim();
   w.add(5);

   // test reverse lists
   List!(int) z = y.reverse.apply;
   assert( z[0] == 4 );
   assert( z[1] == 3 );

   // test foreach iteration
   foreach(int n, inout int val; z) {
     val = n*10;
   }
   assert( z[0] == 0 );
   assert( z[1] == 10 );
   foreach(int n, int val; y.reverse()) {
     assert(x[1-n] == val);
   }

   // test slicing
   List!(int) v = w[1..3];
   assert( v.length == 2 );
   assert( v[0] == 4 );
   assert( v[1] == 5 );

   // test another node type
   List!(char[]) str;
   str.add("hello");
   str.add("world");
   assert( str[str.length-1] == "world" );



Jul 19 2004
next sibling parent "Ben Hinkle" <bhinkle mathworks.com> writes:
 Regarding iterators, I'm currently doubtful about them. I'm quite certain
 that they'll have far less important in D than they do in C++.

Cool. I agree. I've been playing around with using a one-item sub-list (or sub-map or whatever) as a replacement for an iterator. From what I understand of ranges you might be thinking something similar. For example, I've added an opApply that instead of passing the integer index like foreach( int n, T val; x) {} // x[n] is val passes a one-item sub-list holding the current item: foreach( List!(T) n, T val; x){} // n[0] is val Also I've added more functions to handle sub-lists - things like removing them, growing them, inserting before and after them, spanning them... etc. Maps can be treated similarly (a slice of a map is a sub-map) but it has a downside of increasing the size of the struct to have pointers to the first and last nodes in addition to the tree root.
Jul 19 2004
prev sibling parent reply "Bent Rasmussen" <exo bent-rasmussen.info> writes:
 I've been thinking about the struct/class issue, and I'm pleased that

 also thinking about it. I look forward to hearing more of your thoughts.

I'd guess that you need both struct based and class based variants of collections like list, e.g. I've made Sequence and SequenceRef, the first is a struct template while the second is a class template. Both mix-in their implementation and both are quite useful. I guess for types like arrayed lists there's even four variants: struct/class dynamic/static; not to speak of higher-dimensional structures. It'll be interesting to see how much "D-think" there'll be in the first version of DTL...
Jul 19 2004
next sibling parent reply Daniel Horn <hellcatv hotmail.com> writes:
definitely do both struct and class of everything

you never know when one might come in handy...

on the other hand it definitely muddles pass-by-ref and pass-by-val

you get cases where you pass a vector<> into a function and it gets 
copied sometimes:
i.e. the inner function does a push_back on a value...
that may or may not increase memory allocation
then that inner function sets the value--that may or may not set the 
caller's copy of the struct
but one thing is certain: the caller's vector struct will be precisely 
the size it was when it was passed it, because it's a local struct var...
how do we deal with difficult to identify bugs like this (they only 
occur on power of two borders)


Bent Rasmussen wrote:
I've been thinking about the struct/class issue, and I'm pleased that

you're
also thinking about it. I look forward to hearing more of your thoughts.

I'd guess that you need both struct based and class based variants of collections like list, e.g. I've made Sequence and SequenceRef, the first is a struct template while the second is a class template. Both mix-in their implementation and both are quite useful. I guess for types like arrayed lists there's even four variants: struct/class dynamic/static; not to speak of higher-dimensional structures. It'll be interesting to see how much "D-think" there'll be in the first version of DTL...

Jul 19 2004
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Daniel Horn" <hellcatv hotmail.com> wrote in message
news:cdhkqj$s1a$1 digitaldaemon.com...
 definitely do both struct and class of everything

I disagree. It might seem like a convenience to have many versions of nearly the same thing but it actually winds up making the library impossible to use. Long discussions about this kind of thing were had about the dll-loader module. I picked structs for my containers since dynamic arrays and assoc arrays have struct-like semantics and so it seems natural to have other containers follow the same style as them. For instance slicing a dynamic array returns another dynamic array. In the same way slicing a List returns a List and slicing a Map returns a Map.
 you never know when one might come in handy...

 on the other hand it definitely muddles pass-by-ref and pass-by-val

 you get cases where you pass a vector<> into a function and it gets
 copied sometimes:
 i.e. the inner function does a push_back on a value...
 that may or may not increase memory allocation
 then that inner function sets the value--that may or may not set the
 caller's copy of the struct
 but one thing is certain: the caller's vector struct will be precisely
 the size it was when it was passed it, because it's a local struct var...
 how do we deal with difficult to identify bugs like this (they only
 occur on power of two borders)


 Bent Rasmussen wrote:
I've been thinking about the struct/class issue, and I'm pleased that

you're
also thinking about it. I look forward to hearing more of your thoughts.

I'd guess that you need both struct based and class based variants of collections like list, e.g. I've made Sequence and SequenceRef, the


 a struct template while the second is a class template. Both mix-in


 implementation and both are quite useful. I guess for types like arrayed
 lists there's even four variants: struct/class dynamic/static; not to


 of higher-dimensional structures.

 It'll be interesting to see how much "D-think" there'll be in the first
 version of DTL...


Jul 20 2004
parent reply "Bent Rasmussen" <exo bent-rasmussen.info> writes:
I can't believe it to be a bad idea to support both inheritance and
composition.
Jul 20 2004
parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
It's the old design question of complexity vs features. Some use-cases are
not worth the added complexity. Keep in mind complexity makes a library
harder to learn, use and maintain and many times the use-case is so seldomly
used that it just adds baggage. Do I want a concept of "dynamic array" that
I can subclass? personally, no, I don't. I've never subclassed vector<>,
Vector or ArrayList (to use the C++/Java classes).

"Bent Rasmussen" <exo bent-rasmussen.info> wrote in message
news:cdjuu4$1s66$1 digitaldaemon.com...
 I can't believe it to be a bad idea to support both inheritance and
 composition.

Jul 21 2004
next sibling parent reply Ilya Minkov <minkov cs.tum.edu> writes:
Ben Hinkle schrieb:
 It's the old design question of complexity vs features. Some use-cases are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so seldomly
 used that it just adds baggage. Do I want a concept of "dynamic array" that
 I can subclass? personally, no, I don't. I've never subclassed vector<>,
 Vector or ArrayList (to use the C++/Java classes).

On the one hand, i agree that for D, a less complex library is quite appropriate. On the other hand, i recall a nice use of subclassing an array (or any other container) in Sather, where language supports all of that so nicely that it adds no complexity to the library... However, D is not the same, and potential productivity gains would probably be minimal. -eye
Jul 21 2004
parent reply Berin Loritsch <bloritsch d-haven.org> writes:
Ilya Minkov wrote:

 Ben Hinkle schrieb:
 
 It's the old design question of complexity vs features. Some use-cases 
 are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so 
 seldomly
 used that it just adds baggage. Do I want a concept of "dynamic array" 
 that
 I can subclass? personally, no, I don't. I've never subclassed vector<>,
 Vector or ArrayList (to use the C++/Java classes).

On the one hand, i agree that for D, a less complex library is quite appropriate. On the other hand, i recall a nice use of subclassing an array (or any other container) in Sather, where language supports all of that so nicely that it adds no complexity to the library... However, D is not the same, and potential productivity gains would probably be minimal.

There is an advantage to having a standard interface to interact with, allowing the implementation of that interface to change. For example, I may know I need to interact with a list of items, so I declare my variable as a list<>. I don't know what implementation of the list will yield the better results yet, but at least I know I am working on a subset of methods that are available in all implementations. I might start with a vector<> and then realize that the backing array is inneficient for large amounts of data so I switch to a linked_list<>. It's not subclassing that empowers the user, but interfaces. list<Coord> m_coordinates = vector<Coord>; list<Coord> m_coordinates = linked_list<Coord>; The List interface in Java has the standard "Collection" interface as well as list specific functions. The actual implementations of the List have additional functions that pertain to that type of list (like a getHead() or getTail() for LinkedList). I have specified in Java libraries I wrote that I am returning a collection, but did not identify what kind it was. I needed the luxury of choosing whether I returned a list or a set--but I wasn't sure of the details at that time. So interfaces provide alot of help when you need to deal with a wider variety of things. In D we have templates, so I don't know how much that changes the picture. I can still see times where it would be very convenient to have an interface for the collections as opposed to working directly against an implementation. Just to handle temporary unknowns.
Jul 21 2004
next sibling parent reply "Ben Hinkle" <bhinkle mathworks.com> writes:
"Berin Loritsch" <bloritsch d-haven.org> wrote in message
news:cdm2qk$2qgl$1 digitaldaemon.com...
 Ilya Minkov wrote:

 Ben Hinkle schrieb:

 It's the old design question of complexity vs features. Some use-cases
 are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so
 seldomly
 used that it just adds baggage. Do I want a concept of "dynamic array"
 that
 I can subclass? personally, no, I don't. I've never subclassed



 Vector or ArrayList (to use the C++/Java classes).

On the one hand, i agree that for D, a less complex library is quite appropriate. On the other hand, i recall a nice use of subclassing an array (or any other container) in Sather, where language supports all of that so nicely that it adds no complexity to the library... However, D is not the same, and potential productivity gains would probably be minimal.

There is an advantage to having a standard interface to interact with, allowing the implementation of that interface to change. For example, I may know I need to interact with a list of items, so I declare my variable as a list<>. I don't know what implementation of the list will yield the better results yet, but at least I know I am working on a subset of methods that are available in all implementations. I might start with a vector<> and then realize that the backing array is inneficient for large amounts of data so I switch to a linked_list<>. It's not subclassing that empowers the user, but interfaces. list<Coord> m_coordinates = vector<Coord>; list<Coord> m_coordinates = linked_list<Coord>; The List interface in Java has the standard "Collection" interface as well as list specific functions. The actual implementations of the List have additional functions that pertain to that type of list (like a getHead() or getTail() for LinkedList). I have specified in Java libraries I wrote that I am returning a collection, but did not identify what kind it was. I needed the luxury of choosing whether I returned a list or a set--but I wasn't sure of the details at that time. So interfaces provide alot of help when you need to deal with a wider variety of things. In D we have templates, so I don't know how much that changes the picture. I can still see times where it would be very convenient to have an interface for the collections as opposed to working directly against an implementation. Just to handle temporary unknowns.

True. The runtime dispatching of Java's library is nice - though it does mean the performance might not be as good as compile-time binding. The use case you are talking about (protecting oneself from choosing a collection type too early in the development process) can be avoided by making up an alias. For example define alias vector MyCollectionAlias; Then instead of using vector<Coord> everywhere you can use MyCollectionAlias<Coord>. If the time comes when you want to use a linked list instead of a vector you only have to change the alias definition and recompile. Writing libraries might be more scary, though, unless one can modify and recompile the library. Anyhow, there are trade-offs in either direction. -Ben
Jul 21 2004
next sibling parent Berin Loritsch <bloritsch d-haven.org> writes:
Ben Hinkle wrote:

 True. The runtime dispatching of Java's library is nice - though it does
 mean the performance might not be as good as compile-time binding. The use
 case you are talking about (protecting oneself from choosing a collection
 type too early in the development process) can be avoided by making up an
 alias.

I would argue that the performance hit is negligible--but without anything to authoritatively prove that its just your word against mine. My personal observation is that most projects I have seen that make design decisions based solely on performance/micro-benchmark claims ends up causing more issues than they solve. (I'm not saying that its happening in your work at all). The example I gave is just one of the times it comes in handy.
 For example define
  alias vector MyCollectionAlias;
 Then instead of using vector<Coord> everywhere you can use
 MyCollectionAlias<Coord>. If the time comes when you want to use a linked
 list instead of a vector you only have to change the alias definition and
 recompile. Writing libraries might be more scary, though, unless one can
 modify and recompile the library. Anyhow, there are trade-offs in either
 direction.

The alias thing is pretty cool. Now that Java has "generics" of some fashion, I think it can really use an alias command. Personally, from a design perspective, I usually opt for the least amount of lock-in possible to start with. It's kind of the Agile Programming motto of "you ain't gonna need it until you need it". As a result, by the time I am done with the library (I've written many Java libraries), it works well and is flexible enough for just about everyone's need. I think of the required contract, and do everything I can to leave the implementation for as late in the game as possible. Which is why I am a fan of interfaces. Getting to the compile vs. runtime argument, I must say that as a primarily Java developer I am shielded from that due to the runtime. Modern JVMs will recompile the code natively and based on the actual implementation, you will have your compile time binding. I just expressed my own personal opinions, take them as you will. I agree that subclassing the the collection implementation (I think that is what sparked this little side-tangent) doesn't buy much.
Jul 21 2004
prev sibling next sibling parent reply Berin Loritsch <bloritsch d-haven.org> writes:
Ben Hinkle wrote:
 
 True. The runtime dispatching of Java's library is nice - though it does
 mean the performance might not be as good as compile-time binding. The use
 case you are talking about (protecting oneself from choosing a collection
 type too early in the development process) can be avoided by making up an
 alias. For example define
  alias vector MyCollectionAlias;
 Then instead of using vector<Coord> everywhere you can use
 MyCollectionAlias<Coord>. If the time comes when you want to use a linked
 list instead of a vector you only have to change the alias definition and
 recompile. Writing libraries might be more scary, though, unless one can
 modify and recompile the library. Anyhow, there are trade-offs in either
 direction.

I'm playing devil's advocate here for a moment. Please bear with me, while I have extensive programming experience, I am new to D. Since I write a lot of code that is designed to be used as a library, and backwards compatibility is very important to me, what would be the impact of using an interface? The reason I say that is because the following two methods are functionally equivalent, but not syntactically equivalent: vector<Coord> getPolygon() linked_list<Coord> getPolygon() If I found that the linked_list worked better for me after I already released the library I would have to choose between breaking backwards compatibility or living with the deficiencies the other collection had. Array backed lists and linked lists are best suited to different types of interaction, so you can't just say there should be only one type of list. Now, if I were able to use an interface, I would be free to make the change without breaking binary compatibility with any software already installed on the system. I would also be able to enjoy the boost in performance that would arguably be orders of magnitude better than runtime dispatching vs. compiletime dispatching. I think this is about as best an argument as I can muster supporting interfaces for the collections. Within an application, one can always use the implementations directly (in many cases that's what happens), so they still have the advantage of compiletime binding where they need it. With a library the goals are interoperability so the interfaces make more sense to manage potential change. Does that make sense, or am I just blowing wind here? If I'm blowing wind, I'll stop now.
Jul 21 2004
next sibling parent Sean Kelly <sean f4.ca> writes:
In article <cdmmvk$1mf$1 digitaldaemon.com>, Berin Loritsch says...
I'm playing devil's advocate here for a moment.  Please bear with me,
while I have extensive programming experience, I am new to D.

Since I write a lot of code that is designed to be used as a library,
and backwards compatibility is very important to me, what would be the
impact of using an interface?

Potentially, a bit more flexibility.
The reason I say that is because the following two methods are
functionally equivalent, but not syntactically equivalent:

vector<Coord>      getPolygon()
linked_list<Coord> getPolygon()

If I found that the linked_list worked better for me after I already
released the library I would have to choose between breaking backwards
compatibility or living with the deficiencies the other collection had.
Array backed lists and linked lists are best suited to different types
of interaction, so you can't just say there should be only one type of
list.

Now, if I were able to use an interface, I would be free to make the
change without breaking binary compatibility with any software already
installed on the system.  I would also be able to enjoy the boost in
performance that would arguably be orders of magnitude better than
runtime dispatching vs. compiletime dispatching.

I think this is about as best an argument as I can muster supporting
interfaces for the collections.

Within an application, one can always use the implementations directly
(in many cases that's what happens), so they still have the advantage
of compiletime binding where they need it.  With a library the goals
are interoperability so the interfaces make more sense to manage
potential change.

Does that make sense, or am I just blowing wind here?  If I'm blowing
wind, I'll stop now.

Makes perfect sense, and I agree with you. The C++ containers are actually a bit annoying in this regard as there is little support for polymorphism. Adding an interface layer allows for at least a bit of wiggle room, while the user is still free to use the container directly if there are specialized methods he would like to call. Iterators answer some of the polymorphic need in C++ but really not enough in most cases. I really wouldn't mind seeing a set of interfaces for each general container type as it would give the most flexibility. Sean
Jul 21 2004
prev sibling parent reply "Kris" <someidiot earthlink.dot.dot.dot.net> writes:
I agree with you Berin :-)

If Ben can wrap an interface on top of the concrete implementation (where it
makes sense), then that's what I would personally use from a client
perspective (it feels more 'solid' than an alias to me). It's what I try to
expose from within my libraries too; for the reason you state, but also so
that others might plug in a concurrent alternative.

Regarding performance: runtime overhead for Interface dispatching is minimal
in Walters implementation, but the casting to and from a concrete
implementation is not. I imagine (hope) this is just a question of compiler
maturity rather than a language design issue.

- Kris

"Berin Loritsch" <bloritsch d-haven.org> wrote in message
news:cdmmvk$1mf$1 digitaldaemon.com...
 Ben Hinkle wrote:
 True. The runtime dispatching of Java's library is nice - though it does
 mean the performance might not be as good as compile-time binding. The


 case you are talking about (protecting oneself from choosing a


 type too early in the development process) can be avoided by making up


 alias. For example define
  alias vector MyCollectionAlias;
 Then instead of using vector<Coord> everywhere you can use
 MyCollectionAlias<Coord>. If the time comes when you want to use a


 list instead of a vector you only have to change the alias definition


 recompile. Writing libraries might be more scary, though, unless one can
 modify and recompile the library. Anyhow, there are trade-offs in either
 direction.

I'm playing devil's advocate here for a moment. Please bear with me, while I have extensive programming experience, I am new to D. Since I write a lot of code that is designed to be used as a library, and backwards compatibility is very important to me, what would be the impact of using an interface? The reason I say that is because the following two methods are functionally equivalent, but not syntactically equivalent: vector<Coord> getPolygon() linked_list<Coord> getPolygon() If I found that the linked_list worked better for me after I already released the library I would have to choose between breaking backwards compatibility or living with the deficiencies the other collection had. Array backed lists and linked lists are best suited to different types of interaction, so you can't just say there should be only one type of list. Now, if I were able to use an interface, I would be free to make the change without breaking binary compatibility with any software already installed on the system. I would also be able to enjoy the boost in performance that would arguably be orders of magnitude better than runtime dispatching vs. compiletime dispatching. I think this is about as best an argument as I can muster supporting interfaces for the collections. Within an application, one can always use the implementations directly (in many cases that's what happens), so they still have the advantage of compiletime binding where they need it. With a library the goals are interoperability so the interfaces make more sense to manage potential change. Does that make sense, or am I just blowing wind here? If I'm blowing wind, I'll stop now.

Jul 21 2004
parent reply Ben Hinkle <bhinkle4 juno.com> writes:
Kris wrote:

 I agree with you Berin :-)
 
 If Ben can wrap an interface on top of the concrete implementation (where
 it makes sense), then that's what I would personally use from a client
 perspective (it feels more 'solid' than an alias to me). It's what I try
 to expose from within my libraries too; for the reason you state, but also
 so that others might plug in a concurrent alternative.

The concurrent versions of a queue, for example, has been in the back of my mind and is an argument for interfaces. I have a feeling, though, the differences in threading behavior between a concurrent container and a non-concurrent container wouldn't make any switch as simple as changing a "new Queue" to "new ConcurrenQueue" - there are subtle assumptions in interfaces and implementations that make 100% "plug and play" hard. Personally I wouldn't use the alias thing - it was just an idea if one really has no idea how a given data structure will be used and the flexibility of switching mid-development is needed. I generally like Java's collection framework - which was why I took a stab at porting it. It's reassuring to write code that just takes an Iterator, for example, and not care what one is iterating over.
 Regarding performance: runtime overhead for Interface dispatching is
 minimal in Walters implementation, but the casting to and from a concrete
 implementation is not. I imagine (hope) this is just a question of
 compiler maturity rather than a language design issue.

I had more in mind the inlining that the compiler can do if everything is known at compile time. Runtime dispatching prevents inlining. I agree the actual function call is not a performance problem.
Jul 21 2004
parent "Kris" <someidiot earthlink.dot.dot.dot.net> writes:
"Ben Hinkle"  wrote ..
 The concurrent versions of a queue, for example, has been in the back of

 mind and is an argument for interfaces. I have a feeling, though, the
 differences in threading behavior between a concurrent container and a
 non-concurrent container wouldn't make any switch as simple as changing a
 "new Queue" to "new ConcurrenQueue" - there are subtle assumptions in
 interfaces and implementations that make 100% "plug and play" hard.

Very true; was actually referring to something else (my poor choice of words), but I'm glad you made this point. I'm running into that "100%" barrier myself right now.
 I generally like Java's collection framework - which was why I took a stab
 at porting it. It's reassuring to write code that just takes an Iterator,
 for example, and not care what one is iterating over.

I have the same "hangup", so can sympathize <g> BTW, how much trouble is it to port the Java code? Would a mechanical translator help you significantly?
 Regarding performance: runtime overhead for Interface dispatching is
 minimal in Walters implementation, but the casting to and from a


 implementation is not. I imagine (hope) this is just a question of
 compiler maturity rather than a language design issue.

I had more in mind the inlining that the compiler can do if everything is known at compile time. Runtime dispatching prevents inlining. I agree the actual function call is not a performance problem.

Right. I hadn't considered that.
Jul 21 2004
prev sibling parent "Matthew" <admin.hat stlsoft.dot.org> writes:
"Ben Hinkle" <bhinkle mathworks.com> wrote in message
news:cdme7s$2usd$1 digitaldaemon.com...
 "Berin Loritsch" <bloritsch d-haven.org> wrote in message
 news:cdm2qk$2qgl$1 digitaldaemon.com...
 Ilya Minkov wrote:

 Ben Hinkle schrieb:

 It's the old design question of complexity vs features. Some use-cases
 are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so
 seldomly
 used that it just adds baggage. Do I want a concept of "dynamic array"
 that
 I can subclass? personally, no, I don't. I've never subclassed



 Vector or ArrayList (to use the C++/Java classes).

On the one hand, i agree that for D, a less complex library is quite appropriate. On the other hand, i recall a nice use of subclassing an array (or any other container) in Sather, where language supports all of that so nicely that it adds no complexity to the library... However, D is not the same, and potential productivity gains would probably be minimal.

There is an advantage to having a standard interface to interact with, allowing the implementation of that interface to change. For example, I may know I need to interact with a list of items, so I declare my variable as a list<>. I don't know what implementation of the list will yield the better results yet, but at least I know I am working on a subset of methods that are available in all implementations. I might start with a vector<> and then realize that the backing array is inneficient for large amounts of data so I switch to a linked_list<>. It's not subclassing that empowers the user, but interfaces. list<Coord> m_coordinates = vector<Coord>; list<Coord> m_coordinates = linked_list<Coord>; The List interface in Java has the standard "Collection" interface as well as list specific functions. The actual implementations of the List have additional functions that pertain to that type of list (like a getHead() or getTail() for LinkedList). I have specified in Java libraries I wrote that I am returning a collection, but did not identify what kind it was. I needed the luxury of choosing whether I returned a list or a set--but I wasn't sure of the details at that time. So interfaces provide alot of help when you need to deal with a wider variety of things. In D we have templates, so I don't know how much that changes the picture. I can still see times where it would be very convenient to have an interface for the collections as opposed to working directly against an implementation. Just to handle temporary unknowns.

True. The runtime dispatching of Java's library is nice - though it does mean the performance might not be as good as compile-time binding.

With DTL it won't matter. You'll be able to instantiate with or without a common, runtime polymorphic, interface
 The use
 case you are talking about (protecting oneself from choosing a collection
 type too early in the development process) can be avoided by making up an
 alias. For example define
  alias vector MyCollectionAlias;
 Then instead of using vector<Coord> everywhere you can use
 MyCollectionAlias<Coord>. If the time comes when you want to use a linked
 list instead of a vector you only have to change the alias definition and
 recompile. Writing libraries might be more scary, though, unless one can
 modify and recompile the library. Anyhow, there are trade-offs in either
 direction.

Jul 23 2004
prev sibling parent "Matthew" <admin.hat stlsoft.dot.org> writes:
"Berin Loritsch" <bloritsch d-haven.org> wrote in message
news:cdm2qk$2qgl$1 digitaldaemon.com...
 Ilya Minkov wrote:

 Ben Hinkle schrieb:

 It's the old design question of complexity vs features. Some use-cases
 are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so
 seldomly
 used that it just adds baggage. Do I want a concept of "dynamic array"
 that
 I can subclass? personally, no, I don't. I've never subclassed vector<>,
 Vector or ArrayList (to use the C++/Java classes).

On the one hand, i agree that for D, a less complex library is quite appropriate. On the other hand, i recall a nice use of subclassing an array (or any other container) in Sather, where language supports all of that so nicely that it adds no complexity to the library... However, D is not the same, and potential productivity gains would probably be minimal.

There is an advantage to having a standard interface to interact with, allowing the implementation of that interface to change. For example, I may know I need to interact with a list of items, so I declare my variable as a list<>. I don't know what implementation of the list will yield the better results yet, but at least I know I am working on a subset of methods that are available in all implementations. I might start with a vector<> and then realize that the backing array is inneficient for large amounts of data so I switch to a linked_list<>. It's not subclassing that empowers the user, but interfaces. list<Coord> m_coordinates = vector<Coord>; list<Coord> m_coordinates = linked_list<Coord>; The List interface in Java has the standard "Collection" interface as well as list specific functions. The actual implementations of the List have additional functions that pertain to that type of list (like a getHead() or getTail() for LinkedList). I have specified in Java libraries I wrote that I am returning a collection, but did not identify what kind it was. I needed the luxury of choosing whether I returned a list or a set--but I wasn't sure of the details at that time. So interfaces provide alot of help when you need to deal with a wider variety of things. In D we have templates, so I don't know how much that changes the picture. I can still see times where it would be very convenient to have an interface for the collections as opposed to working directly against an implementation. Just to handle temporary unknowns.

One of the aspects of DTL is that all containers may optionally be instantiated to implement one or more standard interfaces. I've already got this stuff working nicely, with a List, a Stack and a Vector being manipulated by the same, compiled, function via a common interface. The instantiations with, and without, the generic interface look like the following: alias Vector!(Int) vector_t; alias Vector!(Int, IContainer) polymorphic_vector_t; [btw, I'm really going to try and get DTL 0.1 done this weekend, as I am sure everyone's well past the point of patience by now. Just a minor inconvenience that I've started a rather high-pressure contract for a new client this week ... ;)]
Jul 23 2004
prev sibling parent reply "Kris" <someidiot earthlink.dot.dot.dot.net> writes:
I'm a big fan of simplicity, so more power to you Ben.


"Ben Hinkle" <bhinkle mathworks.com> wrote in message
news:cdlvdj$2ot0$1 digitaldaemon.com...
 It's the old design question of complexity vs features. Some use-cases are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so

 used that it just adds baggage. Do I want a concept of "dynamic array"

 I can subclass? personally, no, I don't. I've never subclassed vector<>,
 Vector or ArrayList (to use the C++/Java classes).

 "Bent Rasmussen" <exo bent-rasmussen.info> wrote in message
 news:cdjuu4$1s66$1 digitaldaemon.com...
 I can't believe it to be a bad idea to support both inheritance and
 composition.


Jul 21 2004
parent reply Ilya Minkov <minkov cs.tum.edu> writes:
How about the old library by Daniel Yokomiso?

http://www.minddrome.com/produtos/d/

The license is unwieldy, but i don't think this was intentional and he 
might agree to change it.

-eye

Kris schrieb:
 I'm a big fan of simplicity, so more power to you Ben.
 
 
 "Ben Hinkle" <bhinkle mathworks.com> wrote in message
 news:cdlvdj$2ot0$1 digitaldaemon.com...
 
It's the old design question of complexity vs features. Some use-cases are
not worth the added complexity. Keep in mind complexity makes a library
harder to learn, use and maintain and many times the use-case is so

seldomly
used that it just adds baggage. Do I want a concept of "dynamic array"

that
I can subclass? personally, no, I don't. I've never subclassed vector<>,
Vector or ArrayList (to use the C++/Java classes).

"Bent Rasmussen" <exo bent-rasmussen.info> wrote in message
news:cdjuu4$1s66$1 digitaldaemon.com...

I can't believe it to be a bad idea to support both inheritance and
composition.



Jul 22 2004
parent reply J C Calvarese <jcc7 cox.net> writes:
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

Ilya Minkov wrote:
 How about the old library by Daniel Yokomiso?
 
 http://www.minddrome.com/produtos/d/
 
 The license is unwieldy, but i don't think this was intentional and he 
 might agree to change it.
 
 -eye

It is licensed LGPL. That could create serious problems for close-source development, but open source projects may still be able to work with it. Though I'm sure it was revolutionary when first released, it has gathered some cobwebs over the years. A while back, I tried to brush off some of the dust, but I tired of trying to get the unittests to pass. (I'd say that Mr. Yokomiso is a strong believer in DbC.) I've attached my work in case someone could benefit from it. After only a few months, even my efforts to update it to newer compiler versions has gotten stale, so this might be a losing proposition. :(
 
 Kris schrieb:
 
 I'm a big fan of simplicity, so more power to you Ben.


 "Ben Hinkle" <bhinkle mathworks.com> wrote in message
 news:cdlvdj$2ot0$1 digitaldaemon.com...

 It's the old design question of complexity vs features. Some 
 use-cases are
 not worth the added complexity. Keep in mind complexity makes a library
 harder to learn, use and maintain and many times the use-case is so

seldomly
 used that it just adds baggage. Do I want a concept of "dynamic array"

that
 I can subclass? personally, no, I don't. I've never subclassed vector<>,
 Vector or ArrayList (to use the C++/Java classes).

 "Bent Rasmussen" <exo bent-rasmussen.info> wrote in message
 news:cdjuu4$1s66$1 digitaldaemon.com...

 I can't believe it to be a bad idea to support both inheritance and
 composition.




-- Justin (a/k/a jcc7) http://jcc_7.tripod.com/d/
Jul 22 2004
next sibling parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
J C Calvarese wrote:
 Ilya Minkov wrote:
 
 How about the old library by Daniel Yokomiso?

 http://www.minddrome.com/produtos/d/

 The license is unwieldy, but i don't think this was intentional and he 
 might agree to change it.

 -eye

It is licensed LGPL. That could create serious problems for close-source development, but open source projects may still be able to work with it.

AFAIK, LGPL is the least troublesome of the GNU licenses, even when it comes to closed-source projects using the library. Lars Ivar Igesund
Jul 23 2004
parent Ilya Minkov <minkov cs.tum.edu> writes:
Lars Ivar Igesund schrieb:
 AFAIK, LGPL is the least troublesome of the GNU licenses, even when it 
 comes to closed-source projects using the library.

GPL has the requierement that when library functions more than 10 lines in length are linked into the executable, this executable must be completely open-source. Thus, for a header-only library it's not a solution, as well as for non-stripped D libraries or template libraries. What you are referring to is 2 things: * libraries which are shared and belong somehow to an open-source operating system don't impose a problem at all, since they have no restrictions on the target executable. * some libraries (like wxWidgets or FLTK) have a modified LGPL which allows linking without forcing to open-source. But Daniel's Deimos hasn't. Daniel has been a friendly and helpful guy. I think he just didn't give enough thought or thorough reading to LGPL. The copy he distributes with the library even contains the "insert your name here" placeholders. :) I don't think the restriction on making the whole executable was intended, even if the intention that derivations from the library should be was. -eye
Jul 25 2004
prev sibling parent Berin Loritsch <bloritsch d-haven.org> writes:
J C Calvarese wrote:

 Ilya Minkov wrote:
 
 How about the old library by Daniel Yokomiso?

 http://www.minddrome.com/produtos/d/

 The license is unwieldy, but i don't think this was intentional and he 
 might agree to change it.

 -eye

It is licensed LGPL. That could create serious problems for close-source development, but open source projects may still be able to work with it.

:( There are a bunch of open source licenses that are not compatible with the LGPL, such as the venerable Apache Software License. I prefer something more pragmatic to the *GPL dogma. For most of my stuff, I wouldn't be able to use it.
Jul 23 2004
prev sibling parent reply "Matthew" <admin stlsoft.dot.dot.dot.dot.org> writes:
"Bent Rasmussen" <exo bent-rasmussen.info> wrote in message
news:cdhjsb$roi$1 digitaldaemon.com...
 I've been thinking about the struct/class issue, and I'm pleased that

 also thinking about it. I look forward to hearing more of your thoughts.

I'd guess that you need both struct based and class based variants of collections like list, e.g. I've made Sequence and SequenceRef, the first is a struct template while the second is a class template. Both mix-in their implementation and both are quite useful. I guess for types like arrayed lists there's even four variants: struct/class dynamic/static; not to speak of higher-dimensional structures. It'll be interesting to see how much "D-think" there'll be in the first version of DTL...

What's "D-think"? Is that a bit like "double-speak"? :-)
Jul 19 2004
parent "Bent Rasmussen" <exo bent-rasmussen.info> writes:
 What's "D-think"? Is that a bit like "double-speak"? :-)

I mean using the language constructs that make D special.I've heard the term "D style" before, its probably the same thing. :-)
Jul 19 2004
prev sibling parent Ant <Ant_member pathlink.com> writes:
In article <cdeeab$2haf$1 digitaldaemon.com>, Ben Hinkle says...
 Feedback welcome.

for yourself and everybody that you want to use the lib add proper documentation into the source. Use doxygen to generate (or just test) the documentation. Use the javadoc sintax and tags. Ant
Jul 19 2004