View mode: basic / threaded / horizontal-split · Log in · Help
March 05, 2003
Re: built in support for lists
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++/
March 05, 2003
Re: built in support for lists
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
March 05, 2003
Re: built in support for lists
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
March 06, 2003
Re: built in support for lists
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.
Next ›   Last »
1 2
Top | Discussion index | About this forum | D home