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

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

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

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.