View mode: basic / threaded / horizontal-split · Log in · Help
March 02, 2003
built in support for lists
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
March 02, 2003
Re: built in support for lists
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
>
>
March 02, 2003
Re: built in support for lists
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.
March 03, 2003
Re: built in support for lists
"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
March 04, 2003
Re: built in support for lists
Have a look at Functional C++ for ideas.  -M.

http://www.cc.gatech.edu/~yannis/fc++/
March 04, 2003
Re: built in support for lists
>> 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.
March 04, 2003
Re: built in support for lists
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
March 04, 2003
Re: built in support for lists
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
March 05, 2003
Re: built in support for lists
"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.
March 05, 2003
Re: built in support for lists
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
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home