www.digitalmars.com         C & C++   DMDScript  

D - built in support for lists

reply "Dan Liebgold" <dliebgold yahoo.com> writes:
Since D has builtin support for dynamic arrays, it seems like putting
language support in for lists might be a natural design extension. I'm
trying to brainstorm up a workable approach.

In C++ I implemented a list system using templates and macros which was
rather complicated internally, but a real breeze to use.  The template
system in D and lack of macros pretty much preclude the use of the system as
it was implemented in C++. Perhaps, however, its basic idea could be used to
form a design approach:

class ENTRY {
    int data;
    char [] name;
    this (char [] inname) { name[] = inname[]; }
}

Note that ENTRY type has no concept of it being part of a list. How do you
form a list of ENTRYs?  You must first declare a "listable" version of it:

typedef listable ENTRY ENTRYNODE;

The "listable <type>" construct will create a new type which has two
properties: "next" and "prev", that are automatically declared to by of type
<type>. The new types inherits everthing about <type>, include its
constructors.  So now we have a type ENTRYNODE with next and prev properties
each of type ENTRYNODE also. You can use these properties to make lists out
of ENTRYNODE:

ENTRYNODE g_entrylist;  // g_ indicates global

// add a new entry at the head of the list
void CreateEntry () {
  ENTRYNODE newentry = new ENTRYNODE;
  newentry.next = g_entrylist;
  // newentry.prev = null;  <-- this would be the default setting after
construction
  newentry.next.prev = newentry;
  g_entrylist = newentry;
}

void Iterate_Forward (ENTRYNODE head,  void delegate (ENTRYNODE e) proc)
{
  for (ENTRYNODE node = head; node != null; node = node.next) {
    proc(node);
  }
}

void Iterate_Backward (ENTRYNODE tail,  void delegate (ENTRYNODE e) proc)
{
  for (ENTRYNODE node = tail; node != null; node = node.prev) {
    proc(node);
  }
}

Pretty mundane, huh?  The real value comes in being able to do this multiple
times to one type, and then have that type reside on multiple lists,
distinguished only by type:

typedef listable ENTRYNODE ENTRYNODE2;

ENTRYNODE2 g_entry2list;

Now I can create ENTRYNODE2's and put them on both g_entry2list and
g_entrylist.  Iterating each list will be done as if the other did not
exist, for example:

void Iterate_Forward (ENTRYNODE2 head,  void delegate (ENTRYNODE2 e) proc)
{
  for (ENTRYNODE2 node = head; node != null; node = node.next) {
    proc(node);
  }
}

void print (ENTRYNODE n) {
    printf("%s\n",n.name);
}

void print (ENTRYNODE2 n) {
    printf("2: %s\n",n.name);
}

// g_entrylist and g_entry2list both contain the same nodes, but these
functions will distinguish them automatically
Iterate_Forward (g_entrylist,print);
Iterate_Forward (g_entry2list,print);


Some notes:

 - All this is done without the original ENTRY type being modified in any
way.

 - The functions about for list iteration can be probably moved into a
template along with other list utility functions like insert, delete, and
sort.

 - This is a great example of something that could be implemented through a
compiler extension interface.

 - For an example of objects being store on multiple lists, consider OS
kernels with file descriptors... a single file's descriptor could be queued
to a process, a port and a kernel master list.

 - An issue: requires a new keyword, declaration syntax, and a pair of new
properties.

 - Another issue is with allocation of the objects. You cannot allocate an
ENTRY and use it on either of these lists, and you cannot even allocate an
ENTRYNODE and use it on an ENTRYNODE2 list. The furthest descendant type is
the only one you can create to use with a stack of list types.

Thoughts?

Dan
Mar 02 2003
next sibling parent reply "Achillefs Margaritis" <axilmar b-online.gr> writes:
Not only arrays and lists, but trees also need to be part of the language.
And N-ary trees share most functionality with a linked list: a tree node is
a double linked list, and also a node of the same type.

In C++, I always use my own templates for lists/nodes because the available
ones (for example MFC's CList or STL's list) are not suitable. Their main
disadvantage is that the nodes must be allocated separately from the
objects. In my implementation, the objects that want to be part of a
double-linked list must inherit from Node. For example (not every member is
shown):

template <class T> class Node {
public:
private:
    T *_prev;
    T *_next;
    friend List<T>;
};

template <class T> class List {
public:
    T *first();
    T *last();
    void prepend(T *node);
    void append(T *node);
    void insertBefore(T *node, T *next);
    void insertAfter(T *node, T *prev);
    void remove(T *node);

private:
    T *_first;
    T *_last;
    int _count;
};

Here is an example of using the list:

class Foo  : public Node<Foo> {
};
List<Foo> list1;
Foo foo1;
list1.append(&foo1);
list1.remove(&foo1);

This approach has the following advantages:

1) nodes are allocated as part of the object; less cache misses
2) node traversal becomes very very simple:

for(Foo *foo = list1.first(); foo; foo = foo->next()) {
    //TODO process FOO
}

3) N-ary trees can be easily constructed; the list's code is reused:

template <class T> class Tree : public Node<T>, public List<T> {
};

class FooTree : public Tree<FooTree> {
};

This approach also has a disadvantage: an object can belong to maximum one
list at a time. But this hasn't bother me, because I have never met such a
case.

If D has built-in lists and trees, it will be a great advantage, especially
to novice programmers that get lost in such concepts.

"Dan Liebgold" <dliebgold yahoo.com> wrote in message
news:b3sidu$1g7$1 digitaldaemon.com...
 Since D has builtin support for dynamic arrays, it seems like putting
 language support in for lists might be a natural design extension. I'm
 trying to brainstorm up a workable approach.

 In C++ I implemented a list system using templates and macros which was
 rather complicated internally, but a real breeze to use.  The template
 system in D and lack of macros pretty much preclude the use of the system

 it was implemented in C++. Perhaps, however, its basic idea could be used

 form a design approach:

 class ENTRY {
     int data;
     char [] name;
     this (char [] inname) { name[] = inname[]; }
 }

 Note that ENTRY type has no concept of it being part of a list. How do you
 form a list of ENTRYs?  You must first declare a "listable" version of it:

 typedef listable ENTRY ENTRYNODE;

 The "listable <type>" construct will create a new type which has two
 properties: "next" and "prev", that are automatically declared to by of

 <type>. The new types inherits everthing about <type>, include its
 constructors.  So now we have a type ENTRYNODE with next and prev

 each of type ENTRYNODE also. You can use these properties to make lists

 of ENTRYNODE:

 ENTRYNODE g_entrylist;  // g_ indicates global

 // add a new entry at the head of the list
 void CreateEntry () {
   ENTRYNODE newentry = new ENTRYNODE;
   newentry.next = g_entrylist;
   // newentry.prev = null;  <-- this would be the default setting after
 construction
   newentry.next.prev = newentry;
   g_entrylist = newentry;
 }

 void Iterate_Forward (ENTRYNODE head,  void delegate (ENTRYNODE e) proc)
 {
   for (ENTRYNODE node = head; node != null; node = node.next) {
     proc(node);
   }
 }

 void Iterate_Backward (ENTRYNODE tail,  void delegate (ENTRYNODE e) proc)
 {
   for (ENTRYNODE node = tail; node != null; node = node.prev) {
     proc(node);
   }
 }

 Pretty mundane, huh?  The real value comes in being able to do this

 times to one type, and then have that type reside on multiple lists,
 distinguished only by type:

 typedef listable ENTRYNODE ENTRYNODE2;

 ENTRYNODE2 g_entry2list;

 Now I can create ENTRYNODE2's and put them on both g_entry2list and
 g_entrylist.  Iterating each list will be done as if the other did not
 exist, for example:

 void Iterate_Forward (ENTRYNODE2 head,  void delegate (ENTRYNODE2 e) proc)
 {
   for (ENTRYNODE2 node = head; node != null; node = node.next) {
     proc(node);
   }
 }

 void print (ENTRYNODE n) {
     printf("%s\n",n.name);
 }

 void print (ENTRYNODE2 n) {
     printf("2: %s\n",n.name);
 }

 // g_entrylist and g_entry2list both contain the same nodes, but these
 functions will distinguish them automatically
 Iterate_Forward (g_entrylist,print);
 Iterate_Forward (g_entry2list,print);


 Some notes:

  - All this is done without the original ENTRY type being modified in any
 way.

  - The functions about for list iteration can be probably moved into a
 template along with other list utility functions like insert, delete, and
 sort.

  - This is a great example of something that could be implemented through

 compiler extension interface.

  - For an example of objects being store on multiple lists, consider OS
 kernels with file descriptors... a single file's descriptor could be

 to a process, a port and a kernel master list.

  - An issue: requires a new keyword, declaration syntax, and a pair of new
 properties.

  - Another issue is with allocation of the objects. You cannot allocate an
 ENTRY and use it on either of these lists, and you cannot even allocate an
 ENTRYNODE and use it on an ENTRYNODE2 list. The furthest descendant type

 the only one you can create to use with a stack of list types.

 Thoughts?

 Dan

Mar 02 2003
parent reply Mark T <Mark_member pathlink.com> writes:
In article <b3t6ru$aqf$1 digitaldaemon.com>, Achillefs Margaritis says...
... lists, but trees also need to be part of the language.
And N-ary trees share most functionality with a linked list: a tree node is
a double linked list, and also a node of the same type.

NO - put this stuff in the "standard library", shouldn't generics (templates) be used for these type of constructs? Maybe someone or group could start fleshing out what the API for the "standard library" should look like. Of course, this will take a few iterations to get it right. It is one way to "prove" that the language is complete enough. from comp.object: ============================================== Library design is language design--- Andrew Koenig, Barbara Moo: Ruminations on C++ Chap 25: "Library design is language design" Chap 26: "Language design is library design" ============================================== Please don't kitchen-sink the language.
Mar 02 2003
parent reply "Dan Liebgold" <dliebgold yahoo.com> writes:
"Mark T" <Mark_member pathlink.com> wrote in message
news:b3t8s4$bs5$1 digitaldaemon.com...
 In article <b3t6ru$aqf$1 digitaldaemon.com>, Achillefs Margaritis says...


 used for these type of constructs?

Well, D's design approach really doesn't support this. After all, don't dynamic (and associative) arrays belong in the standard library? Truly if you can build in dynamic arrays, you should be able to build in lists. The trick is getting the notation right. I believe, however, that D really isn't ready for list syntax design until it can build dynamic arrays with dynamic initializers, as the concepts are quite closely related. Dan
Mar 02 2003
next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
 put this stuff in the "standard library"


Built-in language support for data structures makes standard libraries easier to write and more powerful. In fact this is one of Neel Krishnaswami's motivations for the Needle language (see below). -M. -------------------------------------- Obviously, Needle will get the features that I, personally, like a lot: macros, multimethods, static typing, continuations, higher-order functions. But getting all that implemented isn't really what I'm primarily interested in (though I am interested in that, and have learned a lot). What really interests me is the standard library. In practice, the ease of programming is in the libraries. Example: Python is an okay language (it's like Smalltalk's dumber cousin) and it kind of sucks in terms of design, with a lot of ad-hoc'd up protocols, but they're all *actually there*. So it has a rich library set and I can turn to it immediately when I need to hack. This is a *big* win, and a reason I use it as much as I use Ocaml, despite liking ML a lot more than Python. My goal with Needle is to see what kind of maximum-leverage libraries I can write when I have everything I want in a language. I mean to put things like parser combinators, constraint sublanguages, concurrency, and other really extremely powerful ideas right into the core libraries. One of the things that surprised me was that a lot of Todd Proebsting's potential "disruptive technlogies" were things I was already contemplating for Needle's standard library. It felt like he was reading my mind, though I guess if you are looking for things to seriously raise the abstraction level of programs you don't have a big list. The big difference is that I think of these as things you build from macros, HOFs and call/cc, and he thinks that they should be basic language features.
Mar 04 2003
parent reply Bill Cox <bill viasic.com> writes:
Mark Evans wrote:
put this stuff in the "standard library"


Built-in language support for data structures makes standard libraries easier to write and more powerful. In fact this is one of Neel Krishnaswami's motivations for the Needle language (see below). -M. -------------------------------------- Obviously, Needle will get the features that I, personally, like a lot: macros, multimethods, static typing, continuations, higher-order functions. But getting all that implemented isn't really what I'm primarily interested in (though I am interested in that, and have learned a lot). What really interests me is the standard library. In practice, the ease of programming is in the libraries. Example: Python is an okay language (it's like Smalltalk's dumber cousin) and it kind of sucks in terms of design, with a lot of ad-hoc'd up protocols, but they're all *actually there*. So it has a rich library set and I can turn to it immediately when I need to hack. This is a *big* win, and a reason I use it as much as I use Ocaml, despite liking ML a lot more than Python. My goal with Needle is to see what kind of maximum-leverage libraries I can write when I have everything I want in a language. I mean to put things like parser combinators, constraint sublanguages, concurrency, and other really extremely powerful ideas right into the core libraries. One of the things that surprised me was that a lot of Todd Proebsting's potential "disruptive technlogies" were things I was already contemplating for Needle's standard library. It felt like he was reading my mind, though I guess if you are looking for things to seriously raise the abstraction level of programs you don't have a big list. The big difference is that I think of these as things you build from macros, HOFs and call/cc, and he thinks that they should be basic language features.

Hi, Mark. Just reading your e-mail, it seems to me that he is arguing the other way. Put more in the library, less in the language, including built-in support for data structures like lists. I think it would be cool if D could implement associative arrays in the libraries, without speed penalties or lack of synax support. If it could do that, surely it could also support efficient lists. That could allow D to be significantly simplified. Bill
Mar 04 2003
parent reply Mark Evans <Mark_member pathlink.com> writes:
Bill Cox says...
it seems to me that he is arguing the other 
way.  Put more in the library, less in the language

No, he said that he wants cool features in the language so he can write awesome standard libraries using those features. That concept is a driving motivation for the whole language -- which is written in O'Caml by the way! What would be cool is if D could implement common data structures natively, so our standard library code is clean, easy to maintain, powerful, easy to leverage, and easy to modify in applications. After all isn't this exactly what STL tried to do for C++? STL in fact almost made it into the C++ language, there just wasn't enough committee time to handle it. (Read the FC++ papers touching on STL as well.) Mark
Mar 04 2003
parent reply Ilya Minkov <midiclub 8ung.at> writes:
Mark, i think lists and other certain constructs needn't be in the 
language core. Instead, constructs must be in the language core which 
allow to write them easily.

This especially applies to trees. There's such a great variety of 
them... that however many you implement the hard way, there are still 
few which are not implemented. So, there must be a simple way to 
implement them. And make the library terse and legible, so that anyone 
can implement his variety. This doesn't necessarily apply to other 
types, like associative arrays which all behave the same and so it's not 
likely someone would really want to write his own.

Mark, have you ever programmed in OCaml? It seems to me that not. Which 
functional (or mixed) language experience do you have? From the 
impression i get, you don't know OCaml except from hearsay and examples 
of what has been done in it. Let me show an easy but powerful example of 
defining a tree.

---8<---
(* Here we define a usual binary tree with unknown underlying type 'a. 
(Actually, it's a pointer type.) *)

type 'a tree = Empty | Tree of ('a * 'a tree * 'a tree);;
(*             11111 3 1111    222222222222222222222222

Here i've marked the following:
  - 1: constructor name, you use it to create a btree initialised to a 
certain subtype;
  - 2: tuple type declaration, which is like a C struct;
  - 3: "OR", which means that a type is a compound type, like "smart union".
Try to translate it into C and you fail. Well, it is not impossible, but 
gets fairly clumnsy. Another interesting thing: OCaml looks like and 
behaves pretty much like BNF, e.g.:
type BinaryOperator = Plus | Minus | Mult | Divide;; If you ever write a 
recursive-descend parser, further similarity within a patternmatcher 
would strike you. *)

let rec insert item tree = match tree with
	|Empty -> Node (item, Empty, Empty);
	|Node (y, left, right) when (item < y)
		-> Node (y, insert item left, right);
	|Node (y, left, right)
		-> Node (y, left, insert item right);;

(* All types are deduced. "|" is the same "OR", just for pattern 
matching. All data requered for pattern-matching is usually compiled 
into an integer, further it works like "case". Earlier matches have 
higher priority, so that a third one doesn't get executed in tree is not 
empty (which is the first), or if tree is a node, a key of which is 
larger than the item (which is the second). This apperently places 
smaller items to the left part of the tree, and the larger in the right 
Arrow "->" is equivalent to the C's return statement, just that it 
instead of exiting the function exits the patternmatcher. In this sample 
it's the same though, since this function only consists of a 
petternmatcher. *)
--->8---

I think that these features (safe/smart unions and case over union 
types) are the most basic ones and need to be implemented. I have even 
posted an article once about implementing a *complete* OCaml-like 
patternmatcher and other functional features as a code pre-processor for 
C++. Please take a look at it. I have even been so kind to dig it up again.

http://citeseer.nj.nec.com/leung96cbased.html

I think D is also quite suited to write compilers. I think i can make a 
kind of library with a similar behaviour and look as BNF, without 
requiering for such things, through global variables representing 
"types" and operator overloading on them. However, adding a support for 
the features in the language would make writing all kinds of 
applications easier.


Mark Evans wrote:
 Bill Cox says...
 
it seems to me that he is arguing the other 
way.  Put more in the library, less in the language

No, he said that he wants cool features in the language so he can write awesome standard libraries using those features. That concept is a driving motivation for the whole language -- which is written in O'Caml by the way! What would be cool is if D could implement common data structures natively, so our standard library code is clean, easy to maintain, powerful, easy to leverage, and easy to modify in applications. After all isn't this exactly what STL tried to do for C++? STL in fact almost made it into the C++ language, there just wasn't enough committee time to handle it. (Read the FC++ papers touching on STL as well.) Mark

Mar 05 2003
parent reply Mark Evans <Mark_member pathlink.com> writes:
Ilya Minkov says...
Mark, i think lists and other certain constructs needn't be in the 
language core. Instead, constructs must be in the language core which 
allow to write them easily.
This especially applies to trees. The

Er, Ilya, the topic is lists! I don't recall advocating trees as a fundamental primitive. Since you ask, I think a hash table primitive is a no-brainer, but would be happy without trees (though XML comes to mind, see http://www.cduce.org/ for an example of built-in XML primitives). D is low-level enough that one can write anything. Taking your argument to an extreme, we could eliminate while / for / until from the core and tell people to use GOTO statements instead. That is how programmers used to write loops. Since then, languages have advanced to the benefit of all. No one today writes loops with GOTO statements. The more power we put in the language, the faster and better and more maintainable our libraries will be. There will be less mutual dependency between them; they will be smaller and easier to modify. We'll also get faster compilation, since we won't have to include extra headers and link libraries. The language itself will supply what is needed. This thinking is exactly what Neel has in mind for Needle, and what I tried to clarify about his comments. I'll let pass your remarks about my skills. Try to stay away from ad hominem like that. Suffice it to say your impression is wrong. I don't know what you're trying to show with the code. That it's easy to write trees and compilers in O'Caml? OK, O'Caml is a terrific language. Now show us examples in D and see what the code looks like. http://flint.cs.yale.edu/cs421/case-for-ml.html Mark
Mar 05 2003
parent Ilya Minkov <midiclub 8ung.at> writes:
Mark Evans wrote:
 Ilya Minkov says...
 
 Er, Ilya, the topic is lists!  I don't recall advocating trees as a fundamental
 primitive.  Since you ask, I think a hash table primitive is a no-brainer, but
 would be happy without trees (though XML comes to mind, see
 http://www.cduce.org/ for an example of built-in XML primitives).

They are relatives... Yes, including lists into the language is not bad but doesn't buy very much. But i'm sorry for going off the topic again.
 D is low-level enough that one can write anything.  Taking your argument to an
 extreme, we could eliminate while / for / until from the core and tell people
to
 use GOTO statements instead.  That is how programmers used to write loops.
 Since then, languages have advanced to the benefit of all.  No one today writes
 loops with GOTO statements.

You probably misunderstood me. I like libraries being short, and thus languages powerful.
 The more power we put in the language, the faster and better and more
 maintainable our libraries will be.  There will be less mutual dependency
 between them; they will be smaller and easier to modify.  We'll also get faster
 compilation, since we won't have to include extra headers and link libraries.
 The language itself will supply what is needed.  This thinking is exactly what
 Neel has in mind for Needle, and what I tried to clarify about his comments.

Exactly. It is also the power to create powerful libraries with a few lines of code.
 I'll let pass your remarks about my skills.  Try to stay away from ad hominem
 like that.  Suffice it to say your impression is wrong.  I don't know what
 you're trying to show with the code.  That it's easy to write trees and
 compilers in O'Caml?  OK, O'Caml is a terrific language.  Now show us examples
 in D and see what the code looks like.

I don't know you personally. I'm sorry - i apologise in public. I spend you a Pizza or something. :) I'll make a D example next days. First off, it'd be a template. Second, emulation of tagged union usually requieres an enum. Not necessary in this case, though a code can get cluttered a bit.
 http://flint.cs.yale.edu/cs421/case-for-ml.html

Here come my comments on it. 1. Garbage collection. - D has it. 2. Tail recursion is optimized. - this is implementation detail. Future compilers will support it. Besides, i think i know how to circumvent eating up stack without any panalty in code size. I'll have to make some experiments though. 3. The data types in ML match the compiling process. - Strings are in D, bignums are easy to implement through operator overloading (see 8). 4. The type constructors in ML are just plain wonderful for describing things like ASTs - one thing that D doesn't have, and i wish it would. This is the IMO *only* key feature on the list we don't have. 5. Safety - D is only a little less safe than ML. 6. ML was designed for theorem proving... - D was designed to be a suitable all-purpose language. 7. Exceptions - D exceptions are not worse. 8. Type inference. - We don't have it. But what's particularly good about it? It can be emulated, though with a significant performance loss. I consider operator overloading better (more important) than type inference, and they simply don't work together well. 9. Compiler construction kits - are to come. 10. Ocaml is fast - yes, but D is also fast. 11. Support - can there be better support than Walter and this newsgroup? 12. Library - is to come. Who says it can't be better? 13. The module system - D has it as well, and the templates. All in all, D might look pretty well in this domain, even though it has not been specifically developed for these problems.
Mar 05 2003
prev sibling parent Farmer <itsFarmer. freenet.de> writes:
"Dan Liebgold" <dliebgold yahoo.com> wrote in
news:b3ujqm$10kt$1 digitaldaemon.com: 

 "Mark T" <Mark_member pathlink.com> wrote in message
 news:b3t8s4$bs5$1 digitaldaemon.com...
 In article <b3t6ru$aqf$1 digitaldaemon.com>, Achillefs Margaritis
 says... 


 used for these type of constructs?

Well, D's design approach really doesn't support this. After all, don't dynamic (and associative) arrays belong in the standard library? Truly if you can build in dynamic arrays, you should be able to build in lists. The trick is getting the notation right. I believe, however, that D really isn't ready for list syntax design until it can build dynamic arrays with dynamic initializers, as the concepts are quite closely related. Dan

When we would have arrays, associative arrays, lists and trees right in the language, what's next? What about graphs? What about hyper-graphs? What about ... I would favour: "Since D has support for templates, it seems like removing direct language support for associative arrays is a natural design choice." When D templates have matured, using templates for associative arrays will be as simple as using D's associative arrays are now. Then D's associative arrays can be removed/deprecated without pain. Of course, D templates are not yet ready to accomplish this.
Mar 04 2003
prev sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
Have a look at Functional C++ for ideas.  -M.

http://www.cc.gatech.edu/~yannis/fc++/
Mar 04 2003
next sibling parent Dan Liebgold <Dan_member pathlink.com> writes:
In article <b42vv9$iri$1 digitaldaemon.com>, Mark Evans says...
Have a look at Functional C++ for ideas.  -M.

http://www.cc.gatech.edu/~yannis/fc++/

Just taking a quick look.... that's some cool stuff! The problem, of course, is the immense amount of templatization required to get that behavior. It just won't be that useable unless its builtin to the language. Dan
Mar 04 2003
prev sibling parent "Sean L. Palmer" <seanpalmer directvinternet.com> writes:
The hallmark of C++ is that it does support such a wide variety of
programming techniques.  I am constantly amazed at the things people figure
out how to make C++ do.

Sean

"Mark Evans" <Mark_member pathlink.com> wrote in message
news:b42vv9$iri$1 digitaldaemon.com...
 Have a look at Functional C++ for ideas.  -M.

 http://www.cc.gatech.edu/~yannis/fc++/

Mar 04 2003