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

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
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
>
>

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.

"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...
> >
> NO - put this stuff in the "standard library", shouldn't generics
(templates) be
> 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

Have a look at Functional C++ for ideas.  -M.

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

>> 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.

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

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

"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...
>> >
>> NO - put this stuff in the "standard library", shouldn't generics
> (templates) be
>> 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
> 
I fully agree with Mark's letter.


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.

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