Object IDs are bad (was: Ousterhout and Tcl lost the plot with latest paper)
Andrew Koenig
In article <336222...@nospam.acm.org> Thant Tessman <th...@nospam.acm.org> writes:
> What I disagreed with (object to!) is Koenig's implication that C++'s use
> of addresses as a "built-in" concept of object identity is in anyway
> superior to SML's use of references.
I would object to that argument too, and I did not make it.
--
--Andrew Koenig
a...@research.att.com
http://www.research.att.com/info/ark
Thant Tessman
Andrew Koenig wrote:
>
> In article <336222...@nospam.acm.org> Thant Tessman <th...@nospam.acm.org> writes:
>
> > What I disagreed with (object to!) is Koenig's implication that C++'s use
> > of addresses as a "built-in" concept of object identity is in anyway
> > superior to SML's use of references.
>
> I would object to that argument too, and I did not make it.
Okay, whatever. However, you did say:
> [...] I can say with confidence that from where I sit, C++ is not
> wretched by comparison [to SML] -- just different. Each language has
> its strengths and weaknesses.
You yourself provided an example of how much easier it is to manipulate
trees in SML compared to C++. What problems can C++ address more naturally
than SML? (since problems involving object identity aren't an example)
(Of course SML does have its weaknesses, but by comparison, a discussion
of C++'s strengths and flaws always sounds like an argument about whether
one should face north or east when one is sacrificing one's goat to the
rain god.)
-thant
Andrew Koenig
> You yourself provided an example of how much easier it is to manipulate
> trees in SML compared to C++. What problems can C++ address more naturally
> than SML? (since problems involving object identity aren't an example)
As one example, several years ago I tried doing an exact implementation
in ML of the "hoc" desk calculator program that appears in the book
``The Unix Programming Environment'' by Kernighan and Pike. I found
two things:
1. The ML version was about half the size of the original C version,
but ran about twice as slowly.
2. I was not able to complete the ML version because the compiler
available to me at the time lacked any facility for converting
an ASCII string to the floating-point equivalent. Although I had
accurate routines in C to convert ASCII to floating point,
there was no easy way to call those routines from ML.
Since then, I have periodically asked the ML compiler people I know when
there will be a version of their system that will let me interface to tools
written in other languages. The answer is always that it's almost ready.
Perhaps when it is finally ready, I will be able to consider ML for serious
programming. Meanwhile, though, the support is just not there.
Francois-Rene Rideau
[comp.lang.{scheme,lisp} removed from the thread]
a...@research.att.com (Andrew Koenig) writes:
> [Problems with SML being slow and lacking good floating point support
> and foreign function interface]
I don't know enough about SML to comment your experience,
but maybe you are using the wrong ML!
Caml (and now OCaml) always has had full FP support,
with (now safely) statically typed printf, and more,
and it generated portable bytecode long before the Java hype began.
OCaml now also has an optimizing native-code compiler,
so it might compete with a C version,
while still giving you compact source (there's also ocamllex and ocamlyacc).
And there's a well-documented way to interface OCaml with C code,
which has been done for such things as Unix systems programming,
X programming, regular expressions, etc. (you just need write stubs).
OCaml has lots of other goodies (statically-typed OO stuff,
modules and *applicative* functors, Tk interface, Windows port, etc),
so the language can favorably compare to SML.
Morale:
1) don't blame the language because of one implementation
2) when an implementation ain't good enough to you, just get another one.
[Ok, one can argue that CAML and SML are not the exact "same" language.
Why must you use SML (or worse, C/C++) and not CAML, already?]
== Fare' -- rid...@ens.fr -- Franc,ois-Rene' Rideau -- DDa(.ng-Vu~ Ba^n ==
Join the TUNES project for a computing system based on computing freedom !
TUNES is a Useful, Not Expedient System
URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"
Andrew Koenig
> 1) don't blame the language because of one implementation
> 2) when an implementation ain't good enough to you, just get another one.
Again, this misses the point. It is like saying `If you don't like
where you live, then move.'
Maybe you like some things about where you live and not others.
Maybe if you moved, there would be other disadvantages.
Maybe you don't want to lose all your friends and have to make
new ones.
Maybe the place you'd like to move won't let you in.
Not being perfectly satisfied with something is not, by itself,
reason to chuck it.
b...@teco.net
> In Thant Tessman <th...@nospam.acm.org> writes:
> > What problems can C++ address more naturally
> > than SML? (since problems involving object identity aren't an example)
a...@research.att.com (Andrew Koenig) responds:
> 1. The ML version was about half the size of the original C version,
> but ran about twice as slowly.
>
> 2. I was not able to complete the ML version because the compiler
> available to me at the time lacked any facility for converting
> an ASCII string to the floating-point equivalent. Although I had
> accurate routines in C to convert ASCII to floating point,
> there was no easy way to call those routines from ML.
Well I guess you win Andrew. C++ really is more natural than SML
E. Young
a...@research.att.com (Andrew Koenig) writes:
> Since then, I have periodically asked the ML compiler people I know when
> there will be a version of their system that will let me interface to tools
> written in other languages. The answer is always that it's almost ready.
> Perhaps when it is finally ready, I will be able to consider ML for serious
> programming. Meanwhile, though, the support is just not there.
I believe Objective Caml (http://pauillac.inria.fr/ocaml) allows
programs to interface with C code. It's in the manual, but I've never
used this facility so I don't know how well it works in practice.
-Edwin
Jeffrey Mark Siskind
> As one example, several years ago I tried doing an exact implementation
> in ML of the "hoc" desk calculator program that appears in the book
> ``The Unix Programming Environment'' by Kernighan and Pike. I found
> two things:
>
> 1. The ML version was about half the size of the original C version,
> but ran about twice as slowly.
>
> 2. I was not able to complete the ML version because the compiler
> available to me at the time lacked any facility for converting
> an ASCII string to the floating-point equivalent. Although I had
> accurate routines in C to convert ASCII to floating point,
> there was no easy way to call those routines from ML.
>
> Since then, I have periodically asked the ML compiler people I know when
> there will be a version of their system that will let me interface to tools
> written in other languages. The answer is always that it's almost ready.
> Perhaps when it is finally ready, I will be able to consider ML for serious
> programming. Meanwhile, though, the support is just not there.
Might I suggest that you try this exercise in Scheme/Stalin. I bet that the
Scheme version will be the same size as the ML version (or smaller) and Stalin
will generate code that will be as fast as C. And Stalin will let you
interface to C code that converts ASCII to floating point. (It also has a
builtin STRING->NUMBER procedure.)
Jeff (home page http://www.emba.uvm.edu/~qobi)
Thant Tessman
I asked:
> What problems can C++ address more naturally than SML?
Andrew Koenig wrote:
> As one example, several years ago I tried doing an exact implementation
> in ML of the "hoc" desk calculator program that appears in the book
> ``The Unix Programming Environment'' by Kernighan and Pike. I found
> two things:
>
> 1. The ML version was about half the size of the original C
> version, but ran about twice as slowly.
I suspect that if you tried your experiment again that you would find that
the SML version's performance was much more in line with the C version,
unless the algorithm required much dynamic memory management in which case
the SML version would be faster.
> 2. I was not able to complete the ML version because the compiler
> available to me at the time lacked any facility for converting
> an ASCII string to the floating-point equivalent. Although I
> had accurate routines in C to convert ASCII to floating point,
> there was no easy way to call those routines from ML.
This hasn't been true for a while. And in fact, there is now an SML
Standard Basis Library which includes utilities such as this.
http://www.research.att.com/~jhr/sml/basis/index.html
(Check out, for example, SBL's support for wide characters for another
good example of why C++ sucks.)
> Since then, I have periodically asked the ML compiler people I know when
> there will be a version of their system that will let me interface to tools
> written in other languages. The answer is always that it's almost ready.
> Perhaps when it is finally ready, I will be able to consider ML for serious
> programming. Meanwhile, though, the support is just not there.
MLWorks and SML/NJ both have C foreign interfaces. Admittedly, they are
currently a little awkward to use compared to the overall elegance of SML,
but they do work and they are improving. (SML developers felt that it
was more important to first reduce the need to resort to C at all, hence
the SBL. Also, there are of course implementations of other languages
that support higher-order functions that interface extremely well with C.)
***
The above is really a distraction from the original question. Yes, much
more energy has gone into developing C++'s tools than has gone into
developing tools for any of the far superior languages that exist. But
this is exactly why I hate C++ so much, and the point I keep trying to
make. So much work (including my own) has been wasted trying to make C++
merely not suck so much when we should have been building truly powerful
applications.
-thant
Andrew Koenig
> more energy has gone into developing C++'s tools than has gone into
> developing tools for any of the far superior languages that exist.
Which suggests that perhaps your opinion of what is superior is not universal.
Erik Naggum
* Thant Tessman
| more energy has gone into developing C++'s tools than has gone into
| developing tools for any of the far superior languages that exist.
* Andrew Koenig
| Which suggests that perhaps your opinion of what is superior is not
| universal.
the odd thing about energy and superiority is that more work is always
_necessary_ on the inferior product than on the superior. we also observe
that much more is published on inferior products than on superior products,
such as on virus detection and protection for Microsoft "operating
systems", such as undocumented features in MS-DOS to make the machine
perform reasonably fast in the display subsystem of games, etc. we find
that the more someone is dissatisfied with his working environment, the
more fuss they make, too. the whole of USENET can be seen as evidence that
people do not write articles to express their agreement with each other.
it is rather curious that someone who _must_ know better argues that the
superiority of something and the energy poured into it are not inversely
related. or are you saying that C++ is a superior language for the same
reason that MS-DOS is a superior operating system, Andrew?
that said, the draft subject to the second ISO CD registration vote for C++
contains remarkably good work in the standard template library. it's a
pity all that energy is wasted on C++. "what a magnificent waste!"
#\Erik
--
if we work harder, will obsolescence be farther ahead or closer?
Andrew Koenig
> * Andrew Koenig
> | Which suggests that perhaps your opinion of what is superior is not
> | universal.
> it is rather curious that someone who _must_ know better argues that the
> superiority of something and the energy poured into it are not inversely
> related. or are you saying that C++ is a superior language for the same
> reason that MS-DOS is a superior operating system, Andrew?
I am saying just what I said before, which is that not everyone has the
same opinion about what is superior to what. Such divergence of opinion
is usually called `personal taste,' and the more I see of the world,
the more I realize just how divergent people's tastes really are.
Darin Johnson
>> more energy has gone into developing C++'s tools than has gone into
>> developing tools for any of the far superior languages that exist.
>
There are three conflicting trains of thought on this.
1) Things that are superior become popular.
2) Things that are popular are claimed to be superior.
3) Superiority and popularity are unrelated.
--
Darin Johnson
da...@usa.net.delete_me
Alexander Stepanov
Erik Naggum wrote:
>
> * Thant Tessman
> | more energy has gone into developing C++'s tools than has gone into
> | developing tools for any of the far superior languages that exist.
>
> * Andrew Koenig
> | Which suggests that perhaps your opinion of what is superior is not
> | universal.
>
> the odd thing about energy and superiority is that more work is always
> _necessary_ on the inferior product than on the superior. we also observe
> that much more is published on inferior products than on superior products,
> such as on virus detection and protection for Microsoft "operating
> systems", such as undocumented features in MS-DOS to make the machine
> perform reasonably fast in the display subsystem of games, etc. we find
> that the more someone is dissatisfied with his working environment, the
> more fuss they make, too. the whole of USENET can be seen as evidence that
> people do not write articles to express their agreement with each other.
>
> it is rather curious that someone who _must_ know better argues that the
> superiority of something and the energy poured into it are not inversely
> related. or are you saying that C++ is a superior language for the same
> reason that MS-DOS is a superior operating system, Andrew?
>
> that said, the draft subject to the second ISO CD registration vote for C++
> contains remarkably good work in the standard template library. it's a
> pity all that energy is wasted on C++. "what a magnificent waste!"
Being responsible for the standard template library, I could assure you that
C++ does have merits. I tried to implement STL in a variety of languages
and failed. I had a very modest goal - to be able to express linear search
in a such way that it would work for any data structure for which it makes
sense. C++ was the only language in which I could do it. There are many
things I do not like about it - OOP is the main example. There are
some things that I really miss - an ability to describe conforming families
of types (iterators, for example). But I still do not know any other language
in which I could express what I wanted to express. I teach a course on Generic
Programming at my place of work, and while I curse C++ constantly during my
lectures, I still use it.
Do I mean to say that C++ is the ultimate programming language? Perish the
thought! We do need a better programming language. But I do not believe that
anything better already exists. And, yes, I tried Scheme, ML, Ada, Java...
And I tried them quite seriously, spending years on every fad that comes out
of POPL.
So there is at least one person who believes that C++ with all its flaws is
the most remarkable piece of work in programming languages since C, and that
any future progress in programming languages must be based on lessons of C++.
>
> #\Erik
> --
> if we work harder, will obsolescence be farther ahead or closer?
--
Alexander Stepanov
step...@sgi.com
Silicon Graphics
2011 N. Shorline Boulevard
Mountain View, CA 94043-1389
tel.: (415)933-6121
David Chase
Alexander Stepanov wrote:
> So there is at least one person who believes that C++ with all its flaws is
> the most remarkable piece of work in programming languages since C, and that
> any future progress in programming languages must be based on lessons of C++.
Yes, I can see myself saying exactly the same words, but I'd probably
intend
them to mean something else.
David Chase
ozan s. yigit
Erik Naggum:
> the odd thing about energy and superiority is that more work is always
> _necessary_ on the inferior product than on the superior.
taking something like lisp and building hardware, user interfaces, complex
environments etc. around it seems like lot more work than what was typically
expected for an average language; you have either just proven lisp machines
were somehow inferior, or the relationship between energy and superiority
is nowhere near as simple as you would prefer...
oz
Chris Cole
Being responsible for the standard template library, I could assure you that
C++ does have merits. I tried to implement STL in a variety of languages
and failed. I had a very modest goal - to be able to express linear search
in a such way that it would work for any data structure for which it makes
sense. C++ was the only language in which I could do it.
Your comparative language experiences would make a great article
(or book). Any chance you've published an account of your various
attempts anywhere?
-Chris
Darin Johnson
In article <336A4D...@mti.sgi.com>, Alexander Stepanov wrote:
>Being responsible for the standard template library, I could assure you that
>C++ does have merits. I tried to implement STL in a variety of languages
>and failed. I had a very modest goal - to be able to express linear search
>in a such way that it would work for any data structure for which it makes
>sense. C++ was the only language in which I could do it.
Really? How odd. Why couldn't this be done in Smalltalk, Eiffel, or Java?
My biggest gripes with STL is that it's inefficient and bloated (ie,
you store objects directly meaning that full copies must be made often
when manipulating things; and you get the *entire* class in a
template, not just a template that provides a type safe wrapper to a
library). I could live with such problems if the C++ experts would
actually admit they're problems rather than cite these as benefits
(which implies they're not going to bother fixing them).
--
Darin Johnson
da...@usa.net.delete_me
Cyber Surfer
With a mighty <E9J3F...@research.att.com>,
a...@research.att.com uttered these wise words...
> Which suggests that perhaps your opinion of what is superior is not universal.
No opinions are universal.
Followups set to comp.lang.misc.
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
Martin Rodgers | Programmer and Information Broker | London, UK
Please note: my email address is gubbish.
Andrew Koenig
In article <slrn5mkihg...@connectnet1.connectnet.com> da...@usa.net.delete_me (Darin Johnson) writes:
> There are three conflicting trains of thought on this.
> 1) Things that are superior become popular.
> 2) Things that are popular are claimed to be superior.
> 3) Superiority and popularity are unrelated.
I believe
4) Saying that one thing is superior to another is meaningful only
in context, which usuallly includes a purpose.
Anyone who claims, for example, that a Ferrari is superior to a Ford
without considering context is cordially invited to try to get a Ferrari
up my driveway with two inches of snow on it. In that context, a
Ferrari is probably useless and a Ford is so-so, unless it happens
to have four-wheel drive, in which case it might be OK.
If you don't agree on a context before comparing tools, the result of
the comparison is unlikely to have any useful meaning.
Thant Tessman
Alexander Stepanov wrote:
> Being responsible for the standard template library, I could assure you
> that C++ does have merits. I tried to implement STL in a variety of
> languages and failed. I had a very modest goal - to be able to express
> linear search in a such way that it would work for any data structure for
> which it makes sense. C++ was the only language in which I could do it.
> [...] And, yes, I tried Scheme, ML, Ada, Java... And I tried them quite
> seriously, spending years on every fad that comes out of POPL.
I will admit that templates and the STL are utterly amazing creations
given the fact that it's C++, but I find the above VERY hard to believe.
Here's why: I've implemented function overloading in Scheme using
macros. This, plus Scheme's dynamic type system gives the programmer
just as much genericity (if not more genericity) in Scheme as in C++.
My implementation was of course slower than C++'s templates (because
dispatching on overloaded functions was done dynamically), but believe
me it was far easier to implement than the STL (let alone templates).
And the programming language Dylan provides this expressiveness at the
language level giving the compiler the chance to statically dispatch
when possible in order to provide good performance.
As for SML, C++'s template functions are a pale imitation of SML's
support for generic polymorphism, and C++'s template classes are
a pale imitation of SML's functors. There are differences, some
possibly in C++'s favor. For example, SML doesn't allow overloaded
functions. But to the degree that overloaded functions are resolved
statically, overloading is merely syntactic sugar. And to the degree
that they are resolved dynamically (via virtual member functions in
the case of C++), we're talking OO, which you said you don't like.
Another difference between SML's functors and C++' templates is that
templates are generiated automatically in pieces as needed. Although
some people hate this, I happen to think this is cool, and I suspect
that this is at the heart of any advantage you may think C++ has over
SML. This latter property of templates has allowed me to do some truly
scary things with templates that I don't think I could do using functors.
But the template tricks I've come up with are UNIVERSALLY used to get
around the other problems of C++.
As for the STL itself, as cool as it is, it really comes off as being
an attempt to make it easier to do the kind of things in C++ that have
always been easy in other languages. I welcome examples to the contrary
if they exist.
***
Alexander Stepanov's dissillusionment with OO reminds me of something
I've been thinking about for a while. Object-oriented methodology
is a collection of techniques for managing program complexity. A
very large "a-ha" for me was that higher-order functions could be
used to build OO systems. Therefore, higher-order functions are
a more fundamental/powerful concept than OO.
(The only reason to build OO into the language (as opposed to
providing it in a library) is to give the compiler the chance to
optimize on those techniques, which is why Dylan, for example,
provides both higher-order functions and OO.)
The strange thing is that I've never seen a defender of C++
acknowledge the power of higher-order functions. Higher-order
functions are simply functions that build other functions. But
I can't help but get the impression that the defenders of C++ just
don't get it. This would explain why they feel it is necessary to
build all this other complex machinery.
-thant
scha...@wat.hookup.net
From my understanding, the Lisp machines were built on an already existing
environment (that had been used at MIT for quite some time already).
Hartmann Schaffer
Andrew Koenig
> I will admit that templates and the STL are utterly amazing creations
> given the fact that it's C++, but I find the above VERY hard to believe.
It's easy to toss gratuitous insults into what you say,
but that doesn't make your statements any more or less valid.
> Here's why: I've implemented function overloading in Scheme using
> macros. This, plus Scheme's dynamic type system gives the programmer
> just as much genericity (if not more genericity) in Scheme as in C++.
> My implementation was of course slower than C++'s templates (because
> dispatching on overloaded functions was done dynamically), but believe
> me it was far easier to implement than the STL (let alone templates).
> And the programming language Dylan provides this expressiveness at the
> language level giving the compiler the chance to statically dispatch
> when possible in order to provide good performance.
Perhaps Alex will confirm the following: He said that C++ was the only
language in which he could implement linear search so that it would work
on any reasonable data structure, but I suspect he may have omitted to
add ``without substantial run-time overhead compared to a straightforward
hand-coded solution.''
I do not think it's particularly difficult to write a generic linear
search in any of a number of languages, but it invariably runs much more
slowly than the same algorithm recoded for the particular data structure
being searched.
> As for SML, C++'s template functions are a pale imitation of SML's
> support for generic polymorphism, and C++'s template classes are
> a pale imitation of SML's functors. There are differences, some
> possibly in C++'s favor. For example, SML doesn't allow overloaded
> functions. But to the degree that overloaded functions are resolved
> statically, overloading is merely syntactic sugar. And to the degree
> that they are resolved dynamically (via virtual member functions in
> the case of C++), we're talking OO, which you said you don't like.
C++ template functions aren't an imitation of SML, because Bjarne was
unfamiliar with SML when he designed templates. Moreover, there are
significant differences between the two notions. See, for example,
my article ``An Example of Language-Sensitive Design'', in the Journal
of Object-Oriented Programming, Vol. 8, no. 4. The gist of that article
is to show a C++ program that, translated directly into SML, yields a
lousy SML program. If we redesign the program to fit well with SML,
and then try to translate it to C++, we get a lousy C++ program. The
point is that the two languages have different enough views of the world
that the same techniques just don't apply.
> Another difference between SML's functors and C++' templates is that
> templates are generiated automatically in pieces as needed. Although
> some people hate this, I happen to think this is cool, and I suspect
> that this is at the heart of any advantage you may think C++ has over
> SML. This latter property of templates has allowed me to do some truly
> scary things with templates that I don't think I could do using functors.
> But the template tricks I've come up with are UNIVERSALLY used to get
> around the other problems of C++.
Well, if you start with the attitude that the language is full of problems
to be overcome, you'll certainly find them. That's true of any language.
> As for the STL itself, as cool as it is, it really comes off as being
> an attempt to make it easier to do the kind of things in C++ that have
> always been easy in other languages. I welcome examples to the contrary
> if they exist.
The thing I find particularly interesting about STL is not that it makes
it easier to do things in C++ that I could already do in other languages.
Rather, STL makes it easier to do things EFFICIENTLY in C++ that I could
not do efficiently in ANY other language readily available to me.
It is very easy to write a library in any of a number of languages that
will sort a generic data structure, but that library will probably do a
dynamic type dispatch for every comparison. What's nice about C++ templates
is that that dynamic type dispatch is done at compile time, and is used as
a way of getting the compiler to lay down appropriate code at run time.
Other languages I have seen either don't do that at all, or make it substantially
harder. Of course a counterexample may exist, but if it does, it doesn't
seem to be a widespread part of current practice.
> Alexander Stepanov's dissillusionment with OO reminds me of something
> I've been thinking about for a while. Object-oriented methodology
> is a collection of techniques for managing program complexity. A
> very large "a-ha" for me was that higher-order functions could be
> used to build OO systems. Therefore, higher-order functions are
> a more fundamental/powerful concept than OO.
I suspect that they are a dual, in the logical sense.
OO: `Everything is data, even programs'
FP: `Everything is program, even data'
> (The only reason to build OO into the language (as opposed to
> providing it in a library) is to give the compiler the chance to
> optimize on those techniques, which is why Dylan, for example,
> provides both higher-order functions and OO.)
I think there are other reasons as well. OOP is particularly useful
for simulations, and lots of commercial applications involve
simulation in one way or another.
> The strange thing is that I've never seen a defender of C++
> acknowledge the power of higher-order functions. Higher-order
> functions are simply functions that build other functions. But
> I can't help but get the impression that the defenders of C++ just
> don't get it. This would explain why they feel it is necessary to
> build all this other complex machinery.
Perhaps you haven't looked hard enough. You might start with STL
function adaptors, which are nothing more or less than higher-order
functios, or come to my Usenix tutorial at the COOTS conference this
June, which will talk a good bit about how to use templates to simulate
higher-order functions in C++. I will completely agree with you that
it would be nice if C++ had a more direct way of supporting higher-order
functions, but that desire is mostly abstract -- in practice I don't see
it getting in the way of using C++ to solve problems that arise for real.
Barry Margolin
In article <5kg5d1$apm$1...@nic.wat.hookup.net>,
<scha...@wat.hookup.net.this.should.stop.spam> wrote:
>From my understanding, the Lisp machines were built on an already existing
>environment (that had been used at MIT for quite some time already).
Nope, they were essentially built from scratch from the ground up. The
people who wrote the LispM OS had previously implemented ITS, a timesharing
OS for PDP-6 and PDP-10 systems, and implemented ITS MacLisp. So they had
experience in OS and Lisp design and implementation, but the LispM
environment is at all like ITS (in fact, it has more high-level conceptual
similarities with Multics than ITS).
--
Barry Margolin
BBN Corporation, Cambridge, MA
bar...@bbnplanet.com
(BBN customers, call (800) 632-7638 option 1 for support)
Alexander Stepanov
Andrew Koenig wrote:
>
> In article <336B72...@nospam.acm.org> Thant Tessman <th...@nospam.acm.org> writes:
>
> > I will admit that templates and the STL are utterly amazing creations
> > given the fact that it's C++, but I find the above VERY hard to believe.
>
> It's easy to toss gratuitous insults into what you say,
> but that doesn't make your statements any more or less valid.
>
> > Here's why: I've implemented function overloading in Scheme using
> > macros. This, plus Scheme's dynamic type system gives the programmer
> > just as much genericity (if not more genericity) in Scheme as in C++.
> > My implementation was of course slower than C++'s templates (because
> > dispatching on overloaded functions was done dynamically), but believe
> > me it was far easier to implement than the STL (let alone templates).
> > And the programming language Dylan provides this expressiveness at the
> > language level giving the compiler the chance to statically dispatch
> > when possible in order to provide good performance.
>
> Perhaps Alex will confirm the following: He said that C++ was the only
> language in which he could implement linear search so that it would work
> on any reasonable data structure, but I suspect he may have omitted to
> add ``without substantial run-time overhead compared to a straightforward
> hand-coded solution.''
While what you are saying is true, the amazing fact is that I could not even
do a slow generic linear search in Scheme. I taught a graduate course in
algorithm design based on Scheme for 10 consequitive semesters. (There are
almost 500 students who had been exposed to my ridiculous attempts to express
complex algorithms in a language that hides memory, - I have been fortunate,
however, since none of them had taken me to court.) Time after time, I tried
to generalize over vectors and lists, and failed. Common Lisp is an example of
the similar attempt: the position function returns an integer index for both list
and vector if an element is found and nil otherwise. It is a not very useful
result for lists - using integers as iterator for all the sequence types is
plainly not what one needs. It is equaly important to see how subranges are
dealt with: keyword arguments :start and :end are integers - not a very useful
choice for lists.
>
> I do not think it's particularly difficult to write a generic linear
> search in any of a number of languages, but it invariably runs much more
> slowly than the same algorithm recoded for the particular data structure
> being searched.
>
> > As for SML, C++'s template functions are a pale imitation of SML's
> > support for generic polymorphism, and C++'s template classes are
> > a pale imitation of SML's functors. There are differences, some
> > possibly in C++'s favor. For example, SML doesn't allow overloaded
> > functions. But to the degree that overloaded functions are resolved
> > statically, overloading is merely syntactic sugar. And to the degree
> > that they are resolved dynamically (via virtual member functions in
> > the case of C++), we're talking OO, which you said you don't like.
>
> C++ template functions aren't an imitation of SML, because Bjarne was
> unfamiliar with SML when he designed templates. Moreover, there are
> significant differences between the two notions. See, for example,
> my article ``An Example of Language-Sensitive Design'', in the Journal
> of Object-Oriented Programming, Vol. 8, no. 4. The gist of that article
> is to show a C++ program that, translated directly into SML, yields a
> lousy SML program. If we redesign the program to fit well with SML,
> and then try to translate it to C++, we get a lousy C++ program. The
> point is that the two languages have different enough views of the world
> that the same techniques just don't apply.
Well, a world recognized ML authority spent some time working with me
on - guess what - expressing linear search. I still have a long message from
him explaining why it could not be done. I would gladly switch to ML if
somebody can show me how I can express what I want to express in it. I have
no personal stake in C++. I use it as a tool. And both Bjarne and Andy could
attest to my long standing criticism of some of its main features.
>
> > Another difference between SML's functors and C++' templates is that
> > templates are generiated automatically in pieces as needed. Although
> > some people hate this, I happen to think this is cool, and I suspect
> > that this is at the heart of any advantage you may think C++ has over
> > SML. This latter property of templates has allowed me to do some truly
> > scary things with templates that I don't think I could do using functors.
> > But the template tricks I've come up with are UNIVERSALLY used to get
> > around the other problems of C++.
>
> Well, if you start with the attitude that the language is full of problems
> to be overcome, you'll certainly find them. That's true of any language.
>
> > As for the STL itself, as cool as it is, it really comes off as being
> > an attempt to make it easier to do the kind of things in C++ that have
> > always been easy in other languages. I welcome examples to the contrary
> > if they exist.
I guess you are a much better programmer than I am, since you find that it
is easy to do what I find totally impossible. If you ever come to the Bay
Area, please stop by and give a talk on library design to our group.
(The remark is addressed to Thant Tessman, and not to Andy Koenig. Andy,
however, is always welcome too, and I hope that he knows it.)
>
> The thing I find particularly interesting about STL is not that it makes
> it easier to do things in C++ that I could already do in other languages.
> Rather, STL makes it easier to do things EFFICIENTLY in C++ that I could
> not do efficiently in ANY other language readily available to me.
>
> It is very easy to write a library in any of a number of languages that
> will sort a generic data structure, but that library will probably do a
> dynamic type dispatch for every comparison. What's nice about C++ templates
> is that that dynamic type dispatch is done at compile time, and is used as
> a way of getting the compiler to lay down appropriate code at run time.
> Other languages I have seen either don't do that at all, or make it substantially
> harder. Of course a counterexample may exist, but if it does, it doesn't
> seem to be a widespread part of current practice.
>
> > Alexander Stepanov's dissillusionment with OO reminds me of something
> > I've been thinking about for a while. Object-oriented methodology
> > is a collection of techniques for managing program complexity. A
> > very large "a-ha" for me was that higher-order functions could be
> > used to build OO systems. Therefore, higher-order functions are
> > a more fundamental/powerful concept than OO.
>
> I suspect that they are a dual, in the logical sense.
> OO: `Everything is data, even programs'
> FP: `Everything is program, even data'
Hear, hear. One of them tells us that binary search is an object, while the
other insists that stack is a function.
>
> > (The only reason to build OO into the language (as opposed to
> > providing it in a library) is to give the compiler the chance to
> > optimize on those techniques, which is why Dylan, for example,
> > provides both higher-order functions and OO.)
>
> I think there are other reasons as well. OOP is particularly useful
> for simulations, and lots of commercial applications involve
> simulation in one way or another.
>
> > The strange thing is that I've never seen a defender of C++
> > acknowledge the power of higher-order functions. Higher-order
> > functions are simply functions that build other functions. But
> > I can't help but get the impression that the defenders of C++ just
> > don't get it. This would explain why they feel it is necessary to
> > build all this other complex machinery.
>
> Perhaps you haven't looked hard enough. You might start with STL
> function adaptors, which are nothing more or less than higher-order
> functios, or come to my Usenix tutorial at the COOTS conference this
> June, which will talk a good bit about how to use templates to simulate
> higher-order functions in C++. I will completely agree with you that
> it would be nice if C++ had a more direct way of supporting higher-order
> functions, but that desire is mostly abstract -- in practice I don't see
> it getting in the way of using C++ to solve problems that arise for real.
I should add that I had been a proponent of functional programming for
more than a decade - one of my first papers was presented at the First
Functional Programming Conference. I have acknowledged the power of higher
order functions. My problem was that I was not interested in doing tail
recursive factorials or memoizing Fibonacci numbers - I wanted to implement
algorithms that people could use when they build their systems. And that
forced me to use C++.
And, believe me, my life would have been much easier if I stayed with
one of the officially approved religions. In the circles where I circulate,
it is not politically acceptable to defend C++, especially if you like
C and not ++. I wish I could love Java...
> --
> --Andrew Koenig
> a...@research.att.com
> http://www.research.att.com/info/ark
--
Alexander Stepanov
step...@mti.sgi.com
Matt Kennel (Remove 'nospam' to reply)
On Fri, 2 May 1997 12:59:52 GMT, Andrew Koenig <a...@research.att.com> wrote:
::> | Which suggests that perhaps your opinion of what is superior is not
:> | universal.
:
:> it is rather curious that someone who _must_ know better argues that the
:> superiority of something and the energy poured into it are not inversely
:> related. or are you saying that C++ is a superior language for the same
:> reason that MS-DOS is a superior operating system, Andrew?
:I am saying just what I said before, which is that not everyone has the
:same opinion about what is superior to what. Such divergence of opinion
:is usually called `personal taste,' and the more I see of the world,
:the more I realize just how divergent people's tastes really are.
My opinion is that a properly designed langauge is the best and most effective
tool, and that alternate extra-language tools are often feeble makeups for
that tool's insufficiency.
--
Matthew B. Kennel/Institute for Nonlinear Science, UCSD/
Don't blame me, I voted for Emperor Mollari.
Jon S Anthony
In article <336A4D...@mti.sgi.com> Alexander Stepanov <step...@mti.sgi.com> writes:
> of types (iterators, for example). But I still do not know any other
> language in which I could express what I wanted to express. I teach
...
> Do I mean to say that C++ is the ultimate programming language? Perish the
> thought! We do need a better programming language. But I do not believe that
> anything better already exists. And, yes, I tried Scheme, ML, Ada, Java...
> And I tried them quite seriously, spending years on every fad that comes out
> of POPL.
How do you square this with the fact that STL has been implemented in
Ada95??? As the saying goes, "if it happens, it must be possible".
/Jon
--
Jon Anthony
Organon Motives, Inc.
Belmont, MA 02178
617.484.3383
j...@organon.com
Thant Tessman
Darin Johnson wrote:
>
> In article <336A4D...@mti.sgi.com>, Alexander Stepanov wrote:
> > Being responsible for the standard template library, I could
> > assure you that C++ does have merits. I tried to implement STL
> > in a variety of languages and failed. I had a very modest goal
> > - to be able to express linear search in a such way that it
> > would work for any data structure for which it makes sense.
>
> Really? How odd. Why couldn't this be done in Smalltalk, Eiffel,
Imagine trying to write a sort routine that worked not on just
arrays, but any data structure that supported a specific set of
operations, like get_next_item. The beauty of the STL is that you
can mix and match algorithms and data structures. This is hard
to do in a purely traditional message-based object-oriented
framework.
However, it's easy to do in any language that supports CLOS-style
generic functions, like Dylan, Scheme (with the appropriate library),
and, oh yeah, Common Lisp.
And if your language doesn't support generic functions, but it
does support higher-order functions, then you're only slightly
inconvenienced by the need to build and pass in the functions
that the sort routine (or whatever) needs to manipulate the data
structures.
A preference for C++ is not a matter of taste but of ignorance.
-thant
--
Philosophy is the search for the set of principles
that will finally free us from the need to think.
james anderson
greetings,
i have been following discussions for some time now regarding "patterns"
and program design. and am wondering if anyone has written on patterns
(especially the direction pree is taking them) from a dynamic-language
perspective.
i've seen references to gabriel's book, but oxford press claims i won't
be able to get one until june. (if it's even relevant)
any other pointers?
thanks,
Andrew Koenig
> A preference for C++ is not a matter of taste but of ignorance.
A preference for mindless insults is not cleverness but immaturity.
Matt Austern
jsa@alexandria (Jon S Anthony) writes:
> In article <336A4D...@mti.sgi.com> Alexander Stepanov <step...@mti.sgi.com> writes:
> >
> > Do I mean to say that C++ is the ultimate programming language? Perish the
> > thought! We do need a better programming language. But I do not believe that
> > anything better already exists. And, yes, I tried Scheme, ML, Ada, Java...
> > And I tried them quite seriously, spending years on every fad that comes out
> > of POPL.
>
> How do you square this with the fact that STL has been implemented in
> Ada95??? As the saying goes, "if it happens, it must be possible".
Are you referring to the original Musser-Stepanov "Ada Generic
Library", or to a more recent port of the STL to Ada?
If the former, then I think it's quite clear to anyone who has
compared the two libraries that the STL is a vast improvement over the
AGL.
If the latter---if, that is, someone has recently ported the entire
STL to Ada 95---then I would be quite interested in seeing a detailed
description of the work. Seeing the same concepts expressed in two
different ways can be very informative.
Mike Rubenstein
a...@research.att.com (Andrew Koenig) wrote:
> In article <336CB3...@nospam.acm.org> Thant Tessman <th...@nospam.acm.org> writes:
>
> > A preference for C++ is not a matter of taste but of ignorance.
>
> A preference for mindless insults is not cleverness but immaturity.
It's almost as if you are suggesting that someone could agree with
Thant Tessman for some reason other than ignorance.
Michael M Rubenstein
Mike Rubenstein
a...@research.att.com (Andrew Koenig) wrote:
> In article <336CB3...@nospam.acm.org> Thant Tessman <th...@nospam.acm.org> writes:
>
> > A preference for C++ is not a matter of taste but of ignorance.
>
> A preference for mindless insults is not cleverness but immaturity.
It's almost as if you are suggesting that someone could disagree with
Erik Naggum
* Thant Tessman
| A preference for C++ is not a matter of taste but of ignorance.
* Andrew Koenig
| A preference for mindless insults is not cleverness but immaturity.
one may judge the maturity of a person by what he finds insulting and why.
Chris Bitmead uid(x22068)
a...@research.att.com (Andrew Koenig) writes:
> Perhaps Alex will confirm the following: He said that C++ was the only
> language in which he could implement linear search so that it would work
> on any reasonable data structure, but I suspect he may have omitted to
> add ``without substantial run-time overhead compared to a straightforward
> hand-coded solution.''
I still think this is wrong. A CLOS coded generic search algorithm
should be just as fast as a hand-coded Lisp search.
Of course C++ tends to be a little faster than Lisp anyway, but this
isn't an "ultimate performance" thread.
David Chase
Matt Kennel (Remove 'nospam' to reply) wrote:
> My opinion is that a properly designed langauge is the best and most effective
> tool, and that alternate extra-language tools are often feeble makeups for
> that tool's insufficiency.
But not all tools are equal for that test. Adding checking to
C++ (and retaining binary compatibility) is onerous and slow (I've
done it). On the other hand, back in the early days before
Modula-3 had official generics, a tool was written to do "poor man's
generics" that worked quite well, and it was not onerous, and it
was not slow. Right now, working in Java, we needed something like
generics, and one of the people in the company wrote some a perl (ick!)
script to crank out the generics for us. The Modula-3 generics
were easier, and less disgusting, because Modula-3 is easy to parse,
and because one of the people working on the language felt that such
tools were often useful, and thus wrote a "toolkit" to make it easy.
I believe we also used this same toolkit to write a makefile generator
and the first pickler-generator (pickling is simply serialization
directed to a file) was probably written using this toolkit.
You can always quibble about whether or not these add-ons are officially
part of the language or not; in practice, I used them, they worked.
David Chase
Marnix Klooster
Alexander Stepanov wrote, among other things:
> I should add that I had been a proponent of functional programming for
> more than a decade - one of my first papers was presented at the First
> Functional Programming Conference. I have acknowledged the power of higher
> order functions. My problem was that I was not interested in doing tail
> recursive factorials or memoizing Fibonacci numbers - I wanted to implement
> algorithms that people could use when they build their systems. And that
> forced me to use C++.
>
> And, believe me, my life would have been much easier if I stayed with
> one of the officially approved religions. In the circles where I circulate,
> it is not politically acceptable to defend C++, especially if you like
> C and not ++. I wish I could love Java...
You might want to look at Pizza (http://www.cis.unisa.edu.au/~pizza).
That's Java plus higher-order functions, parametric polymorphism (nice
for sorting!) and algebraic datatypes. If it doesn't make Java lovable,
it certainly makes it usable.
[Followups adapted.]
> Alexander Stepanov
> step...@mti.sgi.com
Groetjes,
<><
Marnix
--
Marnix Klooster | If you post a reply to a
mklo...@research.baan.nl | News article of mine, please
mar...@worldonline.nl | send me a copy by e-mail.
Lyman S. Taylor
In article <336BE0...@mti.sgi.com>,
Alexander Stepanov <step...@mti.sgi.com> wrote:
>Andrew Koenig wrote:
>>
...
>> on any reasonable data structure, but I suspect he may have omitted to
>> add ``without substantial run-time overhead compared to a straightforward
>> hand-coded solution.''
>
>While what you are saying is true, the amazing fact is that I could not even
>do a slow generic linear search in Scheme
>algorithm design based on Scheme for 10 consequitive semesters. (There are
Hmmm, I suppose by generic linear search you mean something analogous
to Common Lisp's FIND. If so, then the following seems to generically
do the job. It is a tad crude, but I only spent but an little over
an hour and a half developing it. :-) [ And a less times coming
up with the examples and doing some testing... ] It tried not to
use anything that didn't have simple Scheme translation. Or most
other functional languages.... ( e.g. there no dependence on
CLOS and multiple values can be mimiced by returning a list/structure ).
[ More comments after the code... ]
------------------------8< generic_find.lisp >8-------------------------
(defun make-list-iterator ( some-list &optional start end )
"Return a list iterator. This iterator can be queried about it's
value, forward, end?, and interface functions. The optional start
and end should be a sublist of the argument. WARNING the current
implementation doesn't confirm this."
(unless start
(setq start some-list))
(labels ((forward () (if (eql end start )
(error "At end of sequence")
(setq start (rest start))))
(backward () (error "No backward protocol on this type"))
(value () (if (eql end start )
(error "At end of sequence")
(first start)))
(end? () (eql end start))
(interface () (values #'forward #'value #'end? #'backward )))
#'(lambda (action )
(case action
(interface (interface) )
(value (value))
(forward (forward))
(end? (end?))
(otherwise (error "unknown action"))))))
#|
Usage Examples:
Prints all of the elements of the list and returns ALL-DONE.
(multiple-value-bind ( forward value end? )
(funcall (make-list-iterator '( a b c )) 'interface)
(labels ((demo-loop ()
(cond ((funcall end?) 'all-done)
(t (print (funcall value))
(funcall forward)
(demo-loop)))))
(demo-loop)))
Same as above with slightly different approach.
(let ((iter (make-list-iterator '(a b c))))
(labels ((demo-loop ()
(cond ((funcall iter 'end?) 'all-done)
(t (print (funcall iter 'value))
(funcall iter 'forward)
(demo-loop)))))
(demo-loop)))
Prints B through D then returns ALL-DONE.
(let* ((demo-list '(a b c d e f ))
(iter (make-list-iterator demo-list
(nthcdr 1 demo-list)
(nthcdr 4 demo-list )) ) )
(labels ((demo-loop ()
(cond ((funcall iter 'end?) 'all-done)
(t (print (funcall iter 'value))
(funcall iter 'forward)
(demo-loop)))))
(demo-loop)))
|#
(defun make-vector-iterator ( some-vector &optional (start 0) end )
"Return a vector iterator. This iterator can be queried about it's
value, forward, end?, and interface functions. The optional start and
end must be numbers and start < end. WARNING the current implementation
doesn't confirm this."
(unless end
(setq end (length some-vector)))
(labels ((forward () (if (eql end start )
(error "At end of sequence")
(setq start (1+ start))))
(backward () (if (eql end start )
(error "At start of sequence")
(setq end (1- end ))))
(value () (if (eql end start )
(error "At end of sequence")
(svref some-vector start)))
(end? () (eql end start))
(interface () (values #'forward #'value #'end? #'backward )))
#'(lambda (action )
(case action
(interface (interface) )
(value (value))
(forward (forward))
(end? (end?))
(backward (backward))
(otherwise (error "unknown action"))))))
#|
Usage Examples:
Prints all of the elements and returns the symbol ALL-DONE
(multiple-value-bind ( forward value end? )
(funcall (make-vector-iterator '#( a b c )) 'interface)
(labels ((demo-loop ()
(cond ((funcall end?) 'all-done)
(t (print (funcall value))
(funcall forward)
(demo-loop)))))
(demo-loop)))
Same thing as above slightly different interface
(let ((iter (make-vector-iterator '#(a b c))))
(labels ((demo-loop ()
(cond ((funcall iter 'end?) 'all-done)
(t (print (funcall iter 'value))
(funcall iter 'forward)
(demo-loop)))))
(demo-loop)))
Prints only B through D then returns ALL-DONE
(let* ((demo-vector '#(a b c d e f ))
(iter (make-vector-iterator demo-vector 1 4 )))
(labels ((demo-loop ()
(cond ((funcall iter 'end?) 'all-done)
(t (print (funcall iter 'value))
(funcall iter 'forward)
(demo-loop)))))
(demo-loop)))
|#
(defun make-iterator ( object )
"Return the appropriate iterator based upon the type of the given object.
At present this should either be a list or a vector."
(cond ((typep object 'list) (make-list-iterator object ))
((typep object 'vector ) (make-vector-iterator object))
(t (error "No iterator for this type: ~A" (type-of object)))))
;;; The following version takes advantage of the multivalued INTERFACE
;;; function. It binds the specific iterator state changing functions
;;; to their "generic" names.
(defun generic-find1 ( item sequence )
"Return an iterator at the first occurance of item in the sequence.
Otherwise invokes an error [ Admittedly a bit drastic, could be rewritten
to return NIL. FUNCTIONP would distinguish the results.]."
(let ( (iter (make-iterator sequence )) )
(multiple-value-bind ( forward value end? ) (funcall iter 'interface)
(labels ((find-loop ()
(cond ((funcall end?) (error "not found"))
((eql item (funcall value)) iter)
(t (funcall forward)
(find-loop)))))
(find-loop)))))
;;; The following version requires a dispatch through the iterator's
;;; case statement. Doesn't require a call to interface. And allows
;;; multiple iterators to be used together without confusion over
;;; the interace functions. ( a tad slower due to the indirection though).
(defun generic-find2 ( item sequence )
"Return an iterator at the first occurance of item in the sequence.
Otherwise invokes an error [ Admittedly a bit drastic, could be rewritten
to return NIL. FUNCTIONP would distinguish the results.]."
(let ( (iter (make-iterator sequence )) )
(labels ((find-loop ()
(cond ((funcall iter 'end?) (error "not found"))
((eql item (funcall iter 'value)) iter )
(t (funcall iter 'forward)
(find-loop)))))
(find-loop))))
(defmacro with-iterator ( iter-sequence &rest body )
"Any of the iterator's interface functions may be call/funcalled within
the body. Additionally the iterator is bound the named specified by the
iterartor sequence list."
`( let (( ,(first iter-sequence) (make-iterator ,(second iter-sequence))))
(multiple-value-bind (forward value end? backward )
(funcall ,(first iter-sequence) 'interface)
,@body )))
;;; The following is a rehash of find1, but using a macro to "hide" some
;;; of the overhead of extracting the iterator's interface functions.
;;;
(defun generic-find3 ( item sequence )
"Return an iterator at the first occurance of item in the sequence.
Otherwise invokes an error [ Admittedly a bit drastic, could be rewritten
to return NIL. FUNCTIONP would distinguish the results.]."
(with-iterator (iter sequence )
(labels ((find-loop ()
(cond ((funcall end?) (error "not found"))
((eql item (funcall value)) iter)
(t (funcall forward)
(find-loop)))))
(find-loop))))
#|
Usage Examples..
(funcall (generic-find1 'b '(a b c)) 'value)
(funcall (generic-find2 'b '(a b c)) 'value)
(funcall (generic-find3 'b '(a b c)) 'value)
(funcall (generic-find1 'b '#(a b c)) 'value)
(funcall (generic-find2 'b '#(a b c)) 'value)
(funcall (generic-find3 'b '#(a b c)) 'value)
|#
---------------------------8< end of generic_find.lisp >8-----------------
Collections in Dylan have an iteration protocol that allows one to
"generically iterate" with collections, but allowing collection subtype
specific iteration functions to be defined for efficiency.
http://www.harlequin.com/books/DRM/drm-102.html#MARKER-9-268
The other thing I find curious is that, in admittedly simplified viewpoint,
templates simply are a "code writing" mechanism. But so are Common Lisp
macros. It seems like most of the functionality of C++'s templates
could be implemented as CL macro(s). Maybe seriously non trival macros
but none the less, where's the "show stopper"?? This discounts the
the functionality of causing a compile time error if interface isn't
completely implemented ( since CL is dynamic that doesn't "matter"
so much in it's context. ). And also any of the "value semantics"
cruft that doesn't matter either in "reference semantics" languages.
Along the lines of with-iterator macro above, create generic functions
bodies and fill in the details later. The calls to the template functions
are customized at compile time by placing bodies with calls to them
inside of a macro.
i. define the generic template functions with a macro.
(define-template-fcn generic-find ( T ) ( item ( sequence T ))
.... body of the function using the generic iterator
names ... )
Puts the body of the function and substutuion information into
a repository for later retrieval, copying, customization.
ii. add the type as part of specification.
(using-generics ( sequence sequence-type )
....
(generic-find item sequence )
... )
which writes a context specific version of the generic-find, given
sequence specfic functions ( with possibly name-mangled identifiers).
[ With more booking overhead could keep track if the had been
instantiated before and just reuse that version. ]
--
Lyman S. Taylor "Because no matter where you go,
(ly...@cc.gatech.edu) there you are."
Buckaroo Banzai
Zooko
Erik Naggum <er...@naggum.no> wrote:
>* Thant Tessman
>| A preference for C++ is not a matter of taste but of ignorance.
>
>* Andrew Koenig
>| A preference for mindless insults is not cleverness but immaturity.
>
>one may judge the maturity of a person by what he finds insulting and why.
Spare change can often be found under car seats.
Zooko Journeyman
signatures follow
+ island Life in a chaos sea
Not speaking for DigiCash or /.
the University of Colorado / br...@colorado.edu or
---* br...@digicash.com
Thant Tessman
Alexander Stepanov wrote:
> [...] the amazing fact is that I could not even do a slow
> generic linear search in Scheme. [...] Time after time, I
> tried to generalize over vectors and lists, and failed.
> Common Lisp is an example of the similar attempt: the position
> function returns an integer index for both list and vector if an
> element is found and nil otherwise. It is a not very useful
> result for lists - using integers as iterator for all the
> sequence types is plainly not what one needs. It is equaly
> important to see how subranges are dealt with: keyword
> arguments :start and :end are integers - not a very useful
> choice for lists.
Yeah, integers make crummy iterators. So what? I still don't
understand why you couldn't use CLOS generic functions to do
*exactly* the same kind of thing you did in the STL. Now that
I think about it, the biggest trick behind the STL is getting the iterator
behavior worked out.
Help me
out here with an example if you could.
Andrew Koenig wrote:
> I suspect that they are a dual, in the logical sense.
> OO: `Everything is data, even programs'
> FP: `Everything is program, even data'
I've considered this view myself. It might be true if OO made
it easy to treat programs as data, but this typically isn't the
case. Besides, higher-order functions are useful even in OO
languages.
> Perhaps you haven't looked hard enough. [...to find a defender
> of C++ acknowledge higher-order functions...] You might start with
> STL function adaptors, which are nothing more or less than higher-
> order functios, or come to my Usenix tutorial at the COOTS conference
> this June, which will talk a good bit about how to use templates
> to simulate higher-order functions in C++.
I've done it myself even before knowing anything about the STL. I was
really proud of myself for figuring out that this could be done in C++
until I thought about how much effort it took to get what really
was a cheesy technique to work at all.
Besides, this doesn't sound so much like an acknowledgement of the
power of higher-order functions as much as it sounds like yet another
in a long history of desparate attempts to defend C++ from
clearly superior alternatives. (Yes C++ supports higher-order
functions. Well, actually it doesn't, but you can build these
things that you can use sort of like you would use higher-order
functions in certain situations. Yeah they're a pain-in-the-ass
to build, and yeah, your compiler may not handle it yet, but at
least you can keep using C++, which after all, is a very successful
language.)
Alexander Stepanov wrote:
> I should add that I had been a proponent of functional programming
> for more than a decade - one of my first papers was presented at the
> First Functional Programming Conference. I have acknowledged the power
> of higher order functions. My problem was that I was not interested
> in doing tail recursive factorials or memoizing Fibonacci numbers -
> I wanted to implement algorithms that people could use when they
> build their systems. And that forced me to use C++.
Gee, my hatred for C++ was fostered by doing real-time 3D graphics on
SGI machines. The only help I want building systems on this machine
is an alternative to C++. And as soon as I have time to get the
OpenGL working under something else (most likely SML), I'm going to
drop C++ as fast as I can. In the mean-time I'm going to bitch and
moan about C++ because it makes me feel a little better.
Greg Morrisett
Alexander Stepanov <step...@mti.sgi.com> wrote in article
<336BE0...@mti.sgi.com>...
>
> Well, a world recognized ML authority spent some time working with me
> on - guess what - expressing linear search. I still have a long message
from
> him explaining why it could not be done. I would gladly switch to ML if
> somebody can show me how I can express what I want to express in it. I
have
> no personal stake in C++. I use it as a tool. And both Bjarne and Andy
could
> attest to my long standing criticism of some of its main features.
Erm, how's this?
exception NotFound
fun search {predicate : 'elt -> bool,
next : 'collection -> ('elt,'collection) option} =
let fun loop c = case next c of
NONE => raise NotFound
| SOME(elt,rest) => if pred elt then elt else
loop rest
in
loop
end
For the ML-impaired: search is a polymorphic function that abstracts
the collection type and element type, takes two arguments, each
higher-order
functions, the first of which determines if the element is the one you're
looking for, the second just returns the first component of a collection
together with the "rest" of the collection. The search function returns
a loop (as a higher-order function) which when given a collection,
walks through the collection and returns the first element matching
the predicate (if any), and raises the NotFound exception otherwise.
Let's see, to find the first element of a list of (int*string) pairs where
the
integer component is 5:
search {predicate = fn (x,_) => x = 5, next = fn [] => NONE | hd::tl =>
SOME(hd,tl)}
To search an array A of bools for the last true element:
search {predicate = fn b => b, next = fn (A,i) => if i >= 0 then
SOME(Array.sub(A,i),i-1) else NONE} (A,Array.size(A)-1)
Other things you're looking for that this can't do? I'm truly curious...
-Greg
Matt Austern
da...@usa.net.delete_me (Darin Johnson) writes:
> In article <336A4D...@mti.sgi.com>, Alexander Stepanov wrote:
> >Being responsible for the standard template library, I could assure you that
> >C++ does have merits. I tried to implement STL in a variety of languages
> >and failed. I had a very modest goal - to be able to express linear search
> >in a such way that it would work for any data structure for which it makes
> >sense. C++ was the only language in which I could do it.
>
> Really? How odd. Why couldn't this be done in Smalltalk, Eiffel, or Java?
Alex and I tried to implement the STL in Java; you can see our attempt
at http://reality.sgi.com/austern/java/index.html. For a number of
reasons, though, the attempt wasn't all that successful. The most
obvious problem is that Java doesn't have any sort of genericity at
all (polymorphism is not a substitute), but there were actually some
other issues as well.
The main reason that Alex never tried to implement the STL in Eiffel
is that he doesn't know Eiffel. I do, though, so I'll take the
liberty of responding for him.
(Caveat: my Eiffel experience is a year or two old. It's possible
that the language has changed since then, and that my comments are no
longer applicable.)
The general problem is that the whole goal of writing a library of
generic algorithms is to separate algorithms from data structures: you
want to write a partition algorithm, for example, that can work for
arrays, doubly-linked lists, and any other data structure that users
might create. This separation is difficult in Eiffel, though, because
Eiffel was designed with precisely the opposite goal in mind: it
encourages a very close association between algorithms and data
structures. This shows up in a number of small details, which turn
out to be more important than they initially appear.
It might be possible to write something like the STL in Eiffel; I
don't really see how, though. The main problems that I see are
(1) The lack of genericity at the level of functions, as opposed to
the level of classes; (2) The lack of nested type declarations;
(3) The lack of typedef---it's surprisingly important; and (4) A
constrained genericity mechanism that relies on inheritance.
The constrained genericity problem is probably the worst of them. The
STL does impose requirements on generic parameters, but the
requirements involve rather complicated relationships between types; I
don't see how to capture those relationships in terms of inheritance.
Alexander Stepanov
Matt Austern wrote:
>
> The main reason that Alex never tried to implement the STL in Eiffel
> is that he doesn't know Eiffel. I do, though, so I'll take the
> liberty of responding for him.
>
This statement is only partially correct. I do not know Eiffel. I never
tried to implement STL in Eiffel. I do not believe, however, that these
statements are causally connected.
I considered several langages which I did not know as possible
instruments for building a library of generic software components: CLU,
Modula 3, Oberon, SML, Eiffel. I always sought the best advice from the
experts available to me to assertain if such a task would be possible.
For all of these languages I came to the conclusion that I would not be
able to accomplish my task.
To put it simply: I was trying to develop a systematic organization of
algorithms, data structures and other software components. I was not
trying to produce a C++ library. I discovered that C++ was the best
available tool for the job. It is clearly possible to argue that I
failed and the organization of software components in STL is
fundamentally flawed. But if I was succesful, it was only because
Bjarne Stroustrup provided me with the right tool.
--
Alexander Stepanov
step...@sgi.com
T. K. Lakshman
A followup
Alex sent me an appropriate
response which i'm including (with Alex's permission)
--------------------------------------------------------------
From stepanov@wotan Mon May 5 14:59:29 1997
Received: from wotan.mti.sgi.com by sanganak.mti.sgi.com via ESMTP (950413.SGI.8.6.12/940406.SGI.AUTO)
for <laks...@sanganak.mti.sgi.com> id OAA00118; Mon, 5 May 1997 14:59:28 -0700
Received: by wotan.mti.sgi.com (950413.SGI.8.6.12/930416.SGI.AUTO-MTI)
for lakshman id OAA08799; Mon, 5 May 1997 14:59:27 -0700
Date: Mon, 5 May 1997 14:59:27 -0700
From: stepanov@wotan (Alexander Stepanov)
Message-Id: <1997050521...@wotan.mti.sgi.com>
Apparently-To: lakshman@wotan
Status: OR
Thant Tessman wrote:
> A preference for C++ is not a matter of taste but of ignorance.
It is worse than that. Many leading C++ people have strong communist
background. Bjarne Stroustrup's grandfather was a notorious union
organizer and Alex Stepanov was a member of several youth communist
organizations for over a decade.
It is a duty of every honest American to denounce them to the proper
authorities.
Alex
---------------------------------------------------------------------
Jon S Anthony
> > How do you square this with the fact that STL has been implemented in
> > Ada95??? As the saying goes, "if it happens, it must be possible".
>
> Are you referring to the original Musser-Stepanov "Ada Generic
> Library", or to a more recent port of the STL to Ada?
The latter. It has been developed at RPI. The former used Ada83.
> If the latter---if, that is, someone has recently ported the entire
> STL to Ada 95---then I would be quite interested in seeing a detailed
> description of the work. Seeing the same concepts expressed in two
> different ways can be very informative.
I will see if I still have the pointers to this stuff (I suppose if
you just went over to their web site and started rooting around [how
else can you find anything on the web?] you will find it.)
Fergus Henderson
Matt Austern <aus...@isolde.mti.sgi.com> writes:
>Alex and I tried to implement the STL in Java; you can see our attempt
>at http://reality.sgi.com/austern/java/index.html. For a number of
>reasons, though, the attempt wasn't all that successful. The most
>obvious problem is that Java doesn't have any sort of genericity at
>all (polymorphism is not a substitute), but there were actually some
>other issues as well.
Why isn't polymorphism an adequate substitute?
Clearly polymorphism isn't an _ideal_ substitute, because of the
need for lots of downcasts. That's unfortunate, but doing type checking
at run time rather than at compile time isn't going to make the sky fall
in.
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh> | of excellence is a lethal habit"
PGP: finger f...@128.250.37.3 | -- the last words of T. S. Garp.
Anthony Shipman
In <336BE0...@mti.sgi.com> Alexander Stepanov <step...@mti.sgi.com> writes:
>Well, a world recognized ML authority spent some time working with me
>on - guess what - expressing linear search. I still have a long message from
>him explaining why it could not be done. I would gladly switch to ML if
>somebody can show me how I can express what I want to express in it. I have
>no personal stake in C++. I use it as a tool. And both Bjarne and Andy could
>attest to my long standing criticism of some of its main features.
Can we have a specification of what you want to express please?
--
Anthony Shipman "You've got to be taught before it's too late,
TUSC Computer Systems Pty Ltd Before you are six or seven or eight,
To hate all the people your relatives hate,
E-mail: a...@tusc.com.au You've got to be carefully taught." R&H
Rob Warnock
james anderson <jan...@ibm.net> wrote:
+---------------
| i've seen references to gabriel's book, but oxford press claims i won't
| be able to get one until june.
How odd! A local technical store had them in stock a couple of months
ago when I bought my copy...
+---------------
| (if it's even relevant)
+---------------
Well, Gabriel's book provides (IMHO) a nice overview of the meta-issues.
And some musings about the probable limitations of "patterns".
-Rob
-----
Rob Warnock, 7L-551 rp...@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 415-933-1673 FAX: 415-933-4392
2011 N. Shoreline Blvd. [after 8/2/1997 ==> 650-933-xxxx]
Mountain View, CA 94043 PP-ASEL-IA
-Rob
-----
Rob Warnock, 7L-551 rp...@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 415-933-1673 FAX: 415-933-4392
2011 N. Shoreline Blvd. [after 8/2/1997 ==> 650-933-xxxx]
Mountain View, CA 94043 PP-ASEL-IA
Andrew Koenig
> Andrew Koenig wrote:
> > I suspect that they are a dual, in the logical sense.
> > OO: `Everything is data, even programs'
> > FP: `Everything is program, even data'
> I've considered this view myself. It might be true if OO made
> it easy to treat programs as data, but this typically isn't the
> case. Besides, higher-order functions are useful even in OO
> languages.
Sure, but function objects are just objects and can be manipulated
like other objects.
> Besides, this doesn't sound so much like an acknowledgement of the
> power of higher-order functions as much as it sounds like yet another
> in a long history of desparate attempts to defend C++ from
> clearly superior alternatives.
Desparate? Hardly. It's an expression of the pragmatic observation
that an awful lot of programs -- and programmers -- don't make a great
deal of use of higher-order functions. If they're important to you,
then by all means choose a language that supports them the way you like.
But don't assume that your taste is universal.
Anthony Shipman
In <336CB3...@nospam.acm.org> Thant Tessman <th...@nospam.acm.org> writes:
>Imagine trying to write a sort routine that worked not on just
>arrays, but any data structure that supported a specific set of
>operations, like get_next_item. The beauty of the STL is that you
>can mix and match algorithms and data structures. This is hard
>to do in a purely traditional message-based object-oriented
>framework.
My viewpoint is that a design based on adding operations like
get_next_item() to a data structure is at too low a level.
First boost your technology to the level of a lazy functional language like
Haskell.
Then view a list as not just a data type but an abstract interface for
linear operations.
To add linear operations to a data structure add a function that maps
the data structure to a list of the members of the structure. For
example to a tree data structure add a function that builds a list of
the members in depth first order. Another function could be written to
build a list in breadth first order. These adaptor functions can be
quite small, being little more than a mathematical specification of
depth-first or breadth-first or whatever traversal.
Then any function that operates on a list can operate on the data
structure. Careful use of type classes will let the syntax be quite
neat.
It is important that lazy evaluation be used. This lets a search
function terminate the search early which will terminate the traversal
of the data structure early as you would expect. The low-level
implementation will be equivalent to what you would write with a
get_next_item() function but it's all generated automatically.
The only minuses that I can think of are that
* there may be dynamic dispatching on each member operation. Recent
developments in optimising dynamic dispatching to be static will help
here.
* memory allocation issues will give higher peak memory usage but also
quite possibly greater speed since there is no overhead due to the
reference counting a C++ iterator would use as it passes over the
data structure. Deforestation optimisations could eliminate the
memory allocation issues completely.
The big plus of this functional approach is that the linear operations
and the data structures are completely decoupled. You can compose any
data structure and linear operation using an appropriate adaptor
function that describes the traversal order.
Other pluses are that improvements in optimisations in compilers will
result in all existing code being improved. Whereas hand-written code
for the interaction of operations and data structures in lower-level
languages tend to become frozen. For example a parallelising compiler
will let you run multiple concurrent iterations on parallel hardware
with no extra effort.
Fergus Henderson
a...@tusc.com.au (Anthony Shipman) writes:
>My viewpoint is that a design based on adding operations like
>get_next_item() to a data structure is at too low a level.
>
>First boost your technology to the level of a lazy functional language like
>Haskell.
[...]
>The low-level
>implementation will be equivalent to what you would write with a
>get_next_item() function but it's all generated automatically.
Well, hopefully. But you are assuming quite a bit. My guess is that
in practice for most current Haskell and C++ implementations, C++ and
STL will beat this style of Haskell code by a significant constant factor.
Thant Tessman
Alexander Stepanov wrote:
> [...] It is clearly possible to argue that I
> failed and the organization of software components in STL is
> fundamentally flawed.
I haven't seen anybody argue this. Given the context, the
STL is a thing of beauty.
(Of course, as with everything related to C++, practice falls
far short of what little even theory promises, and as expected,
my implementation of the STL from SGI sucks. For one thing,
some very peculiar errors in my code turned out to be caused
by a "PAUSE" macro defined in "alloc.h".)
> But if I was succesful, it was only because
> Bjarne Stroustrup provided me with the right tool.
This is the claim I reject. It doesn't surprise me at all
that the STL couldn't be done in Eifel or Java. But SML or
CLOS or...you're gonna have to substantiate that one.
-thant
Matt Austern
f...@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
> >Alex and I tried to implement the STL in Java; you can see our attempt
> >at http://reality.sgi.com/austern/java/index.html. For a number of
> >reasons, though, the attempt wasn't all that successful. The most
> >obvious problem is that Java doesn't have any sort of genericity at
> >all (polymorphism is not a substitute), but there were actually some
> >other issues as well.
>
> Why isn't polymorphism an adequate substitute?
>
> Clearly polymorphism isn't an _ideal_ substitute, because of the
> need for lots of downcasts. That's unfortunate, but doing type checking
> at run time rather than at compile time isn't going to make the sky fall
> in.
Polymorphism isn't an adequate substitute for genericity because it
doesn't do the same thing; it's not primarily an issue of efficiency
(although that matters too), but of semantics.
Note that it's generic algorithms I'm concerned with, not just
container classes. If the only tool I have at hand is polymorphism,
then I don't see a way of writing a single algorithm that can be used
for vectors, singly linked lists, double linked lists, and binary
search trees.
Ramesh Bharadwaj
Greg Morrisett <j...@cs.cornell.edu> writes....
<ML code deleted>
> For the ML-impaired: search is a polymorphic function that abstracts
> the collection type and element type, takes two arguments, each
> higher-order
> functions, the first of which determines if the element is the one you're
> looking for, the second just returns the first component of a collection
> together with the "rest" of the collection. The search function returns
> a loop (as a higher-order function) which when given a collection,
> walks through the collection and returns the first element matching
> the predicate (if any), and raises the NotFound exception otherwise.
Phew! Now *I'm* convinced that I've not been missing much by not using ML.
Do you seriously expect professional programmers to flock to ML just because
it is possible to code linear search in ML, moreover in such an elegant way :-)
--ramesh
M. Prasad
Francois-Rene Rideau wrote:
>
> Matt Austern <aus...@isolde.mti.sgi.com> writes:
>
> > Polymorphism isn't an adequate substitute for genericity because it
> > doesn't do the same thing; it's not primarily an issue of efficiency
> > (although that matters too), but of semantics.
> >
> > Note that it's generic algorithms I'm concerned with, not just
> > container classes. If the only tool I have at hand is polymorphism,
> > then I don't see a way of writing a single algorithm that can be used
> > for vectors, singly linked lists, double linked lists, and binary
> > search trees.
> >
> The functor would take as argument a module with the types and primitives
> needed by your generic algorithm, and return a module that returns
> your generic functions.
>
> Alternatively, you could use the object system from OCAML.
> [Note that OCAML also has functors, and that its standard library
> never needed do anything that required objects, only functors]
Cute stuff, though hard to debug (presumably in this
programming style you would want to write functors
of your own ...) hence the lack of catching-on, IMO.
Francois-Rene Rideau
Matt Austern <aus...@isolde.mti.sgi.com> writes:
> Polymorphism isn't an adequate substitute for genericity because it
> doesn't do the same thing; it's not primarily an issue of efficiency
> (although that matters too), but of semantics.
>
> Note that it's generic algorithms I'm concerned with, not just
> container classes. If the only tool I have at hand is polymorphism,
> then I don't see a way of writing a single algorithm that can be used
> for vectors, singly linked lists, double linked lists, and binary
> search trees.
>
Use functors!
The functor would take as argument a module with the types and primitives
needed by your generic algorithm, and return a module that returns
your generic functions.
Alternatively, you could use the object system from OCAML.
[Note that OCAML also has functors, and that its standard library
never needed do anything that required objects, only functors]
== Fare' -- rid...@ens.fr -- Franc,ois-Rene' Rideau -- DDa(.ng-Vu~ Ba^n ==
Join the TUNES project for a computing system based on computing freedom !
TUNES is a Useful, Not Expedient System
URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"
Thant Tessman
> >
> >| A preference for mindless insults is not cleverness but immaturity.
> >
> > one may judge the maturity of a person by what he finds insulting
> > and why.
>
> Spare change can often be found under car seats.
My hovercraft is full of eels.
-thant
Alexander Stepanov
Anthony Shipman wrote:
>
> Can we have a specification of what you want to express please?
You can take a look at:
http://www.sgi.com/Technology/STL/
to find what linear search in STL does (it is called find).
If you like a less formal set of requiremts it is:
1. Semantics:
1. I would like to mutate what I find if the data structure
is mutable;
2. I would like to restart the search from the position I found.
3. I would like multiple search paths through a data structure:
reverse order, stride, etc;
4. I would like it to work for subranges of a data structure;
5. I would like to compare two positions for equality.
2. Complexity:
1. I would like the generic code to be as fast as hand
optimized code in the same language. (As a matter of fact,
I would even like it to be as fast as hand optimized code
written in assembly);
2. I would like to be able to choose an algorithm that is
optimized for a certain subtheory: e.g. I can find a maximum trip
count fast, I would like to do hand unrolling.
> --
> Anthony Shipman "You've got to be taught before it's too late,
> TUSC Computer Systems Pty Ltd Before you are six or seven or eight,
> To hate all the people your relatives hate,
> E-mail: a...@tusc.com.au You've got to be carefully taught." R&H
--
Alexander Stepanov
step...@mti.sgi.com
Matthew Fuchs
Thant Tessman wrote:
>
...
>
> Alexander Stepanov's dissillusionment with OO reminds me of something
> I've been thinking about for a while. Object-oriented methodology
> is a collection of techniques for managing program complexity. A
> very large "a-ha" for me was that higher-order functions could be
> used to build OO systems. Therefore, higher-order functions are
> a more fundamental/powerful concept than OO.
>
Not just objects, but clients and servers are also trivially implemented
through higher-order functions, or closures. This works really nice for
distributed systems with mobile objects (you can either look at my work
or at Luca Cardelli's Obliq). Closures and objects are both implemented
the same way - an environment pointer and a function pointer (the latter
being somewhat optimized away by some compilers).
Closures are much more flexible than objects and classes (esp. in the
C++ sense) because there is much more flexibility on binding times.
And closures are first class, which classes traditionally are not.
The "hard" part of implementing objects, from the point of view of
higher order functions, are instance variables, but they can be handled
with macros.
>
> The strange thing is that I've never seen a defender of C++
> acknowledge the power of higher-order functions. Higher-order
> functions are simply functions that build other functions. But
> I can't help but get the impression that the defenders of C++ just
> don't get it. This would explain why they feel it is necessary to
> build all this other complex machinery.
>
But C++ is great -- for implementing Scheme ;-)
Matthew Fuchs
ma...@wdi.disney.com
http://cs.nyu.edu/phd_students/fuchs
Fergus Henderson
Matt Austern <aus...@isolde.mti.sgi.com> writes:
>f...@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
>
>> Why isn't polymorphism an adequate substitute?
>>
>> Clearly polymorphism isn't an _ideal_ substitute, because of the
>> need for lots of downcasts. That's unfortunate, but doing type checking
>> at run time rather than at compile time isn't going to make the sky fall
>> in.
>
>Polymorphism isn't an adequate substitute for genericity because it
>doesn't do the same thing; it's not primarily an issue of efficiency
>(although that matters too), but of semantics.
Well, I'm still missing the difference. I don't see why polymorphism
plus downcasting doesn't give you the same semantics as genericity.
Note that genericity can be implemented with shared code, just like
polymorphism is -- for example, some Ada compilers implement Ada
generics that way, and so do all Haskell compilers. The only semantis
differences that I can see are that (a) with genericity, you get
homogenous collections, whereas with polymorphism you get heterogenous
collections -- but fortunately it is easy to use the latter to
implement the former; and (b) you're going to need some explicit
downcasts.
>Note that it's generic algorithms I'm concerned with, not just
>container classes. If the only tool I have at hand is polymorphism,
>then I don't see a way of writing a single algorithm that can be used
>for vectors, singly linked lists, double linked lists, and binary
>search trees.
You could just use the same design embodied in the STL: your single
algorithm works on Iterators (or more specifically InputIterators,
ForwardIterators, etc.), and each Container provides begin() and end()
methods that return Iterators.
Why is that so hard??
Graham C. Hughes
-----BEGIN PGP SIGNED MESSAGE-----
f...@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
> Well, I'm still missing the difference. I don't see why polymorphism
> plus downcasting doesn't give you the same semantics as genericity.
The C rule regarding casts bears repeating, and in fact is relevant to
every statically typed language; a cast tells the compiler you know
much more about the happenings then it does. Don't do it if you can
possibly help it. Casts are a sledgehammer, designed to subvert the
type system.
In the days predating templates in C++, collection classes had to be
done using polymorphism & downcasting. This was error prone and type
unsafe, and the primary reason I didn't do much C++ programming at the
time. Element extraction was tedious, and ensuring that the element
had the type you thought it did was worse. Java is in this situation
now, and (modulo Pizza) it doesn't look to be getting any better.
Using polymorphism plus downcasting as a substitute for genericity is
the clearest indicator I can possibly find that the author is used to
a dynamically typed language. This works fine for CLOS, Python,
Smalltalk, what have you, but is inappropriate for statically typed
languages such as C++, Ada, Eiffel, and others.
Note that (with some care) an STL vector can be made into a
pseudo-heterogeneous container by storing pointers. The care is
necessary due to memory allocation issues.
- --
Graham Hughes http://A-abe.resnet.ucsb.edu/~graham/ MIME & PGP mail OK.
const int PGP_fingerprint = "E9 B7 5F A0 F8 88 9E 1E 7C 62 D9 88 E1 03 29 5B";
#include <stddisclaim.h>
-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv
Comment: Processed by Mailcrypt 3.4, an Emacs/PGP interface
iQCVAwUBM2/D+yqNPSINiVE5AQH8+wP9F+p2M6T1+wEuq02LRm9YphEtUmFqS1XH
iO70tZoovXhIyq0eehpYYdc9fnoonOcZPyKvTfqp+KqnIPk1Di1Lv+1+Mvg9zD69
Se5g5UZ9d54vJXyXoLp+4ArKUsmcmiVE8Y1yiRbZ0q38smKixGbr5y7+wVMSCGhZ
ew+KluYLvTQ=
=h9jn
-----END PGP SIGNATURE-----
Alexander Stepanov
Thant Tessman wrote:
>
> Alexander Stepanov wrote:
>
> > [...] It is clearly possible to argue that I
> > failed and the organization of software components in STL is
> > fundamentally flawed.
>
> I haven't seen anybody argue this. Given the context, the
> STL is a thing of beauty.
>
> (Of course, as with everything related to C++, practice falls
> far short of what little even theory promises, and as expected,
> my implementation of the STL from SGI sucks. For one thing,
> some very peculiar errors in my code turned out to be caused
> by a "PAUSE" macro defined in "alloc.h".)
Please sent us (s...@sgi.com) a detailed report. We will try to fix it
as fast as possible. This bug has never been reported.
Interestingly, you are the first disgrunted customer we had. Most people
are very happy with our implementation.
>
> > But if I was succesful, it was only because
> > Bjarne Stroustrup provided me with the right tool.
>
> This is the claim I reject. It doesn't surprise me at all
> that the STL couldn't be done in Eifel or Java. But SML or
> CLOS or...you're gonna have to substantiate that one.
1. Addresses.
STL is based on the fundamental assumption that addresses are
good. The memory model of the C machine is the right base for the
abstraction. Neither Lisp nor ML allow a natural address/location
abstraction. You can implement address like thingies in them, but
the built-in data strucutres do not based on the needed abstraction.
Note that in Lisp one tends to stick to the built-in data-structures.
I never seen a serious impementation of a doubly-linked lists in Lisp.
(Yes, yes, I had done one myself too, but it was not serious.) As far
as I know, the same holds true for SML. Arrays and lists can not
be easily unified. Or at least, they are not usually unified.
Take a look at list->vector, vector->list pair in Scheme and compare it
with generic constructor in STL containers. They have to provide
2N new conversion functions for every new data structure in the library.
Clearly, they do not bother to extend the number of data structures.
One of the things I am trying to do now is to extend the iterator
classification to handle non-uniform memory references. (One of
my collegues, Fred Chow, proposes to call them NUMA-iterators.) It is
quite remarkable how the existing STL framework could be extended to
deal with MP, cache behaviour, parallelism. But it all relies on
addresses. Abstract addresses, but addresses nevertheless.
2. Container vs. iterator
Lisp also brought a conceptual confusion of list as an iterator and list
as a data structure. There is no way to distiguish between the two uses.
It is a subtle point, but I am sure you can see it. It also makes it
impossible to have an ownership or whole-part semantics for data
structures and makes it impossible to survive without
garbage collection. (I like garbage collection as an option, but
Lisp and ML make a virtue out of necessity.)
3. Type system
It is possible to define swap in C++. And you can use partial
specialization to choose the right swap.
template <class T>
inline void swap(T& x, T& y) {
T tmp = x;
x = y;
y = tmp;
}
and
template <class T>
inline void swap(vector<T>& x, vector<T>& y) {
x.swap(y);
}
And you should see amazing things you can do with types using
partial specialization. (Look at the description of iterator_traits
in the standard.) It is very easy to specify very complicated
relations among type categories.
It is so easy to use the type system to carry semantic information
and to use types for selecting correct algorithms. Somebody once
remarked that STL shows how much can be accomplished by passing empty
structures around.
I do not know any other language where I can easily say:
1. Normally, reduce returns an identity element of its operation.
template <class InputIterator, class BinaryOperation>
iterator_traits<InputIterator>::value_type
reduce(InputIterator first, InputIterator last, BinaryOperation op) {
if (first == last) return identity_element(op);
iterator_traits<InputIterator>::value_type result = *first;
while (++first != last) result = op(result, *first);
return result;
}
2. The default operation of reduce is plus.
template <class InputIterator>
iterator_traits<InputIterator>::value_type
inline reduce(InputIterator first, InputIterator last) {
return reduce(first, last,
plus<iterator_traits<InputIterator>::value_type());
}
3. The default identity element of plus is 0
template <class T>
inline T identity_element(const plus<T>&) {
return T(0);
}
4. The default identity element of multiply is 1
template <class T>
inline T identity_element(const multiply<T>&) {
return T(1);
}
Note, that if I want to add a bunch of doubles I just say:
vector<double> v;
// fill v with doubles
cout << reduce(v.begin(), v.end());
// now print the product:
cout << reduce(v.begin(), v.end(), multiply<double>());
I do not need to pass ++, *, ==, = for iterators as our ML experts
suggest that we do. Types are good. Compiler will find the right
operations.
And if tomorrow I put my doubles into a set (does SML have sets?),
I can just say:
set<double> v;
// fill v with doubles
cout << reduce(v.begin(), v.end());
// now print the product:
cout << reduce(v.begin(), v.end(), multiply<double>());
And if, tomorrow, you define sets that use skip lists you just do:
skip_set<double> v;
// fill v with doubles
cout << reduce(v.begin(), v.end());
// now print the product:
cout << reduce(v.begin(), v.end(), multiply<double>());
Now, take Common Lisp reduce. It is not generic. (If you define your own
doubly linked list, their reduce is not going to do anything reasonable
for it.) It is hard making it generic, or they would have done it.
Using these techniques, is quite easy to define algorithms affiliated
with different algebraic structures, say, Euclidian domains. It is quite
easy to state that, say, all polynomial rings over a field are
Euclidian domains. It is also possible to state when to use Euclid's
algorithm and when to use binary gcd algorithm. That is, it is possible
to describe algorithms over theories - and that's what generic
programming is all about. Yes, there are languages other than C++, that
allow one to do this, Axiom and A# by Richard Jenks et al. is one which
needs to get far greater recognition. (I would use them as a proof that
it is much more important for a language designer to know their van der
Waerden, than to read lambda calculus books. As a matter of fact, many
would benifit greatly if they worked carefully through George Chrystal's
great textbook.) Ada 95 is much, much better for generic programming
than Ada 83. SML and CLOS? I do not think so.
>
> -thant
Alex
--
Alexander Stepanov
step...@sgi.com
Richard A. O'Keefe
Alexander Stepanov <step...@mti.sgi.com> writes:
>While what you are saying is true, the amazing fact is that I could not even
>do a slow generic linear search in Scheme.
A generic linear search has the following form:
- there is an abstract data type that represents
(a position in) a sequence.
- there is an operation ended? which tests whether
such a position has reached its end.
- there is an operation current which returns the element at a
position which is not ended
- there is an operation next which returns the next position
after a position which is not ended
(define generic-linear-search
(lambda (Ended? Current Next)
(lambda (Position Test? Success-Continuation Failure-Continuation)
(let loop ((P Position))
(if (Ended? P)
(Failure-Continuation)
(let ((C (Current P)))
(if (Test? (Current P))
(Success-Continuation C)
(loop (Next P)) )) )) )) )
(define list-linear-search
(generic-linear-search null? car cdr))
(define (vector-linear-search Vector)
(let ((N (vector-length Vector)))
(generic-linear-search
(lambda (I) (>= I N))
(lambda (I) (vector-ref V I))
(lambda (I) (+ I 1)) )))
Now the operations used here are essentially the SAME (strictly, a subset)
of the operations the STL relies on. If you have a Scheme system where
generic-linear-search can be declared integrable, what you get is precisely
what you need, and quite as efficient as directly hand-written code.
>Time after time, I tried
>to generalize over vectors and lists, and failed.
But
(1) As the STL itself so forcibly reminds us, lists and vectors are not
the only kinds of sequences. generic-linear-search as written above
will work just fine for a sequence defined by reading lines from a
file (although you really need a rewind operation; Scheme doesn't
make transput as easy as one might wish).
(2) As the STL itself so forcibly reminds us, with those extremely
useful cost tables in the draft C++ standard, the cost of an operation
depends on the costs of the primitive operations provided by the
underlying data structures. The whole *reason* for having different
list and vector data structures is to support different cost models
for the sequence operations, to support different tradeoffs.
I've done a great deal of "sequence" stuff in Pascal (augmented by
Ada-style packages implemented using M4, gah!) and it just didn't seem
that hard. The main thing that got in my way was the fact that Pascal
*DIDN'T* manage memory for me, so every single type had to have "make"
and "free" operations.
>Well, a world recognized ML authority spent some time working with me
>on - guess what - expressing linear search. I still have a long message from
>him explaining why it could not be done.
This would be an *EXTREMELY* useful thing to know. I beg you to get that
person to publish the message or permit the publication of that message by
you. Perhaps the two of you could jointly publish the result? PLEASE do
it soon!
It would of course be even better if you and he could explain whether/why
not it can be done in Haskell, which has a form of inheritance/overloading
that may (or may not, I don't know what your problem was) be useful.
If you could do this, maybe we could get some real technical content into
this discussion.
One interesting thing about C++ templates is that the template language
is in itself a complete programming language. I have seen some amazing
computations expressed that way. (It's almost like a first order functional
language, in some ways.) This fact alone makes the C++ template mechanism
more powerful than the Ada generic mechanism, which is not computation-
universal, or Scheme function inlining (ditto), or ML structures and
functors (again, ditto). Myself, speaking as a programmer, I feel a lot
safer using a language where I know that compilation can always be done in
a finite time, but I have to admit the power of the C++ approach. If the
reason for the STL needing C++ is due to that fact alone, I don't find it
terribly interesting, but if there is some much more fundamental problem,
I would VERY much like to understand it.
>I should add that I had been a proponent of functional programming for
>more than a decade - one of my first papers was presented at the First
>Functional Programming Conference. I have acknowledged the power of higher
>order functions. My problem was that I was not interested in doing tail
>recursive factorials or memoizing Fibonacci numbers - I wanted to implement
>algorithms that people could use when they build their systems. And that
>forced me to use C++.
The trouble is, it's all very well saying "C++ can do this, C++ can do that",
but the STL has been out for a while, and there are still very few C++
compilers that can actually *compile* the model STL implementation. As
soon as I heard about the STL, I grabbed the documentation and the model
implementation, and then had to face the fact that I *COULDN'T* use it.
In fact, on the machine where I do most of my work, which does have a
couple of C++ compilers, I *STILL* can't use the STL.
>And, believe me, my life would have been much easier if I stayed with
>one of the officially approved religions.
C++ *is* an officially approved religion. It has *far* more clout than
any functional language. Because of that fact alone, providing a C++
version of the STL was an exceptionally good thing to do. I just wish
I could use it.
>I wish I could love Java...
Could Java-as-we-know it support the STL? Does it have the same
mysterious problem that Scheme and ML are said to have?
--
Will maintain COBOL for money.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.
Chris Bitmead uid(x22068)
a...@research.att.com (Andrew Koenig) writes:
> > Besides, this doesn't sound so much like an acknowledgement of the
> > power of higher-order functions as much as it sounds like yet another
> > in a long history of desparate attempts to defend C++ from
> > clearly superior alternatives.
>
> Desparate? Hardly. It's an expression of the pragmatic observation
> that an awful lot of programs -- and programmers -- don't make a great
> deal of use of higher-order functions.
Huh? I'm sure hardly any programmers use higher-order
functions. Perhaps that's because hardly any main stream languages
support it? It's a bit hard to write functional COBOL you know.
When did you observe a group of programmers using a higher-order
functional language that did not use them?
b...@teco.net
laks...@sanganak.mti.sgi.com (T. K. Lakshman) writes:
> > A preference for C++ is not a matter of taste but of ignorance.
>
> It is worse than that. Many leading C++ people have strong communist
> background. Bjarne Stroustrup's grandfather was a notorious union
> organizer and Alex Stepanov was a member of several youth communist
> organizations for over a decade.
This makes sense. C++ reduces both coding gurus and ignorant morons to
the same pathetic level of productivity, and therefore salary. It also
supports full employment. Very communist!
Seriously though, STL is very clever and I respect the design a
lot. It's not enough to turn a sow's ear into a silk purse however.
Matt Kennel (Remove 'nospam' to reply)
On Mon, 05 May 1997 10:12:59 -0700, Thant Tessman <th...@nospam.acm.org> wrote:
:
:Alexander Stepanov wrote:
:
:> generic linear search in Scheme.
:Yeah, integers make crummy iterators. So what?
Why do people want an 'iterator', a noun, instead of 'iteration', a verb?
--
Matthew B. Kennel/Institute for Nonlinear Science, UCSD/
Don't blame me, I voted for Emperor Mollari.
Fergus Henderson
"Graham C. Hughes" <graham...@resnet.ucsb.edu> writes:
>f...@mundook.cs.mu.OZ.AU (Fergus Henderson) writes:
>
>> Well, I'm still missing the difference. I don't see why polymorphism
>> plus downcasting doesn't give you the same semantics as genericity.
>
>[... lots of stuff about why casts are evil ...]
>Using polymorphism plus downcasting as a substitute for genericity is
>the clearest indicator I can possibly find that the author is used to
>a dynamically typed language.
Sure. I was thinking of implementing something like STL in Java,
and when it comes to genericity, Java is a dynamically typed language.
In C, casts are certainly something you want to avoid whenever
possible. In Java, casts are not nearly as unsafe as they are in C,
because they are checked at runtime. Sure, something like Pizza would
be better, but I don't think the need to downcast in Java is a
show-stopper. I think you could write a version of STL in Java
without resorting to preprocessing hacks, and apart from issues of
efficiency that could be solved by a sufficiently smart compiler,
and apart from the need to downcast, I think it could be just as
powerful as the C++ STL. In fact, it would have some advantages over
the C++ STL: the interfaces would be explicit in the code, and the
compiler would check them, whereas in C++ the interfaces for
things like ForwardIterator or Assignable are present only in the
documentation, not in the code, and are not checked by the compiler.
Daniel F. Higgins
> Polymorphism isn't an adequate substitute for genericity because it
> doesn't do the same thing; it's not primarily an issue of efficiency
> (although that matters too), but of semantics.
>
> container classes. If the only tool I have at hand is polymorphism,
> then I don't see a way of writing a single algorithm that can be used
> for vectors, singly linked lists, double linked lists, and binary
> search trees.
I've been tossing around the idea of making wrapper classes for all the
types, and modeling some of the polymorphic design of these classes
after java.. I did it to write a database engine, constructing a record
from a bunch of base fields (of certain types).
What is the down side of polymorphism? Is run-time typing is going to be
included in the next C++, and when is it coming out!
--
Daniel F. Higgins
//////////////////////////
http://www.fsu.umd.edu/students/dhiggins/index.html
dhig...@netbiz.net
Fergus Henderson
I wrote:
>I think you could write a version of STL in Java
>without resorting to preprocessing hacks, and apart from issues of
>efficiency that could be solved by a sufficiently smart compiler,
>and apart from the need to downcast, I think it could be just as
>powerful as the C++ STL.
Actually on further reflection I see that the Java version would have
another disadvantage compared to the C++ version. As Alexander Stepanov
has pointed, in C++ you can do nifty things with template specialization.
In Java you could still special-case the algorithms, e.g.
foo(InputIterator i) {
if ((RandomAccessIterator) i) {
// use random access algorithm
random_access_foo((RandomAccessIterator) i);
} else if ((SomeOtherSpecialIterator) i) {
// use some other special case
some_other_foo_algorithm((SomeOtherSpecialIterator) i);
} else {
// if none of the special cases apply, just
// use a single-pass algorithm
single_pass_foo(i);
}
}
and a smart compiler could inline foo() and optimize away the if-then-else
and the type tests. (Of course, relying on compiler optimization is not
always a good thing. It might be a good idea to add pragmas or something
to give the compiler a hints that it should always specialize foo();
it could then issue a warning if for some reason it wasn't able to do so.)
However, the disadvantage of this Java solution is that all the special
cases must be listed in a single function; adding a new specialization
requires modifying that function.
Andrew Koenig
In article <s6yenbk...@aalh02.alcatel.com.au> Chris....@alcatel.com.au (Chris Bitmead uid(x22068)) writes:
> Huh? I'm sure hardly any programmers use higher-order
> functions. Perhaps that's because hardly any main stream languages
> support it? It's a bit hard to write functional COBOL you know.
Agreed.
> When did you observe a group of programmers using a higher-order
> functional language that did not use them?
Never -- but it doesn't matter, because the higher-order functional
languages do not support -- and their communities consider irrelevant --
other key aspects of programming languages that most commercial
programmers consider indispensible.
For example, a good chunk of commercial programming practice today
is related in some way to object-oriented design. A key notion in
object-oriented design is the use of objects to represent concepts
in the program being designed. An important characteristic of objects
is their ability to store mutable state information.
The higher-order functional languages generally do not support mutable
state, because doing so would compromise referential transparency. In
particular, higher-order functions seem to be the most useful when
combined with lazy evaluation, which in turn does not seem to combine
well with the idea of mutable state. So these well known and widely
used design techniques simply do not apply in such languages.
That means, in turn, that if you wish to program in functional style,
you really have to change almost everything about how you think
about programming. It's not just a matter of using higher-order
functions or not using them.
M. Prasad
Matt Kennel (Remove 'nospam' to reply) wrote:
>
> On Mon, 05 May 1997 10:12:59 -0700, Thant Tessman <th...@nospam.acm.org> wrote:
> :
> :Alexander Stepanov wrote:
> :
> :> [...] the amazing fact is that I could not even do a slow
> :> generic linear search in Scheme.
>
> :Yeah, integers make crummy iterators. So what?
>
> Why do people want an 'iterator', a noun, instead of 'iteration', a verb?
I believe the term "iterator" was introduced by some
experimental languages around early 80s or late 70s.
An "iterator" is a thing you can use to iterate. For instance,
one iterator might allow you to iterate over numbers from
1 to 100 (the most common variety of iterator -- in many
programming languages, known as a "FOR" statement.) Another
iterator might allow you to iterate over elements of
a list. A third might allow you to iterate over all
the triangular decompositions of a polygon.
These experimental programming languages also allowed
users to write their own iterators. "C"s for statement
uses a syntax so you can embed a "list iterator" right
in the for statement (though it is a bit cumbersome to
extend the concept to more complex iterations.)
The idea came from attempts to "abstract" the elements
of programming -- procedures and data. (Of course,
OOP has become the popular modern way of abstracting
these.)
Nathan Davis
> > > A preference for C++ is not a matter of taste but of ignorance.
> >
> > It is worse than that. Many leading C++ people have strong communist
> > background. Bjarne Stroustrup's grandfather was a notorious union
> > organizer and Alex Stepanov was a member of several youth communist
> > organizations for over a decade.
>
> This makes sense. C++ reduces both coding gurus and ignorant morons to
> the same pathetic level of productivity, and therefore salary. It also
> supports full employment. Very communist!
How can you say that that C++ reduces everyone to the same "pathetic"
level of productivity. I learned C++ in my early teens, with hardly any
trouble at all. I am very productive with it. I have yet to see a
language that is so easy to use that gives you the power you need (I
haven't actually used JAVA yet, but I'm guessing it's probably similar
since its based on C++, except the
class.names.are.so.long.they.take.up.five.hundred.lines). The only
other impression I have of JAVA is that it isn't as well organized as
C++ (although, it was probably just the coder).
There is one thing we all have to keep in mind: it takes a while to get
used to a new language. I think that probably a lot of these JAVA
hypers probably didn't have the patience to actually learn C++. Sure,
JAVA can probably get morons to turn out simple applications in a couple
of hours. However, will they get much farther than that? If they are
truly morons, we C++ programmers don't have anything to worry about
because they won't have the technical skills to do anything significant
(i.e. optimized code).
One more thing: I use C++, and I am *not* a communist (I am a
conservative, thank you very much!).
--Nathan Davis
David Monniaux
Andrew Koenig (a...@research.att.com) wrote:
: In article <s6yenbk...@aalh02.alcatel.com.au> Chris....@alcatel.com.au (Chris Bitmead uid(x22068)) writes:
: Never -- but it doesn't matter, because the higher-order functional
: languages do not support -- and their communities consider irrelevant --
: other key aspects of programming languages that most commercial
: programmers consider indispensible.
This argument, which is basically that academic people design pretty languages
that are unuseable in "real" environments is somewhat flawed (see below).
: For example, a good chunk of commercial programming practice today
: is related in some way to object-oriented design. A key notion in
: object-oriented design is the use of objects to represent concepts
: in the program being designed. An important characteristic of objects
: is their ability to store mutable state information.
You should perhaps try "semi functional" languages like ML, especially
Objective CAML. It seems to have what most people here want:
- functional features
- imperative features
- objects (not very used, since the functors seem more powerful for
most purposes)
- functors and modules
When it comes to implementing structures and having generic algorithms,
I think modules and functors are very powerful. You can, for instance,
write a whole module using, say, a priority queue. You test it with,
say, a heap for that queue. Then you feel that more appropriate
structures may be better (say, you want to have a disk-cached queue).
You then abstract the queue, making it a parameter. You can use your
module, by simply instanciating it with your heap or your nifty
disk-cached system.
The standard library features Map's, Set's etc..., and more structures
are easily coded. I've myself added Heap's etc...
http://pauillac.inria.fr/ocaml
When it comes to efficiency, O'Caml features both a bytecode compiler,
for quick compiles during development, and a native code compiler.
It is the implementation language for production-stage projects such
as Coq (a theorem prover which is used to prototype critical systems,
such as embedded airplane systems) and Ensemble. The O'Caml compiler
is itself written in O'Caml.
--
"If computers worked, it'd be known."
Computer science student at ENS, Lyon, France
http://www.ens-lyon.fr/~dmonniau
PS: As for the general tone of the discussion, I'm somehow disgusted.
Many people here seem to argue that their way is the only way, and
that people who don't agree have obviously never done "serious"
programming. The quality of the talk would certainly improve if
we spent less time accusing each other of, basically, incompetency,
and more time actually working on design.
Michael Greenwald
"M. Prasad" <pra...@nospam.polaroid.com> writes:
>Matt Kennel (Remove 'nospam' to reply) wrote:
>> Why do people want an 'iterator', a noun, instead of 'iteration', a verb?
Because there are languages where iterators *are* (first class)
objects that you can pass around and store. You can apply an iterator
to a body (a.k.a a function or closure) providing a useful way of
abstracting control structure. A noun makes much more sense than a
verb in this case. You can think of an iterator as a (possibly)
optimized form of co-routine.
>I believe the term "iterator" was introduced by some
>experimental languages around early 80s or late 70s.
CLU certainly used "iterator" in the 70s. I don't know if it was the
first language to use it as a keyword.
>An "iterator" is a thing you can use to iterate. For instance,
>one iterator might allow you to iterate over numbers from
>1 to 100 (the most common variety of iterator -- in many
>programming languages, known as a "FOR" statement.) ...
Daniel Wang
>>>>> "Andrew" == Andrew Koenig <a...@research.att.com> writes:
Andrew> Never -- but it doesn't matter, because the higher-order
Andrew> functional languages do not support -- and their communities
Andrew> consider irrelevant -- other key aspects of programming
Andrew> languages that most commercial programmers consider
Andrew> indispensible.
{stuff deleted}
Andrew> For example, a good chunk of commercial programming practice
Andrew> today is related in some way to object-oriented design.
{stuff deleted}
Objective CAML
Andrew> The higher-order functional languages generally do not support
Andrew> mutable state, because doing so would compromise referential
Andrew> transparency.
{stuff deleted}
Andrew> In particular, higher-order functions seem to be
Andrew> the most useful when combined with lazy evaluation, which in
Andrew> turn does not seem to combine well with the idea of mutable
Andrew> state. So these well known and widely used design techniques
Andrew> simply do not apply in such languages.
Not all of the functional language community is tied to the idea of
referential transperency. The ML family of langauges have always had eager
evaluation, exceptions, references, and higher-order functions. Not to
mention the Scheme/Lisp community.
Andrew> That means, in turn, that if you wish to program in functional
Andrew> style, you really have to change almost everything about how you
Andrew> think about programming. It's not just a matter of using
Andrew> higher-order functions or not using them.
Assuming you toss the ML family of languages into the functional style, the
above statements are just wrong. Though, I have to agree programing in ML
has changed my way of thinking about programming. It's encouraged me to
write clear and correct code.
There's functional and *purely* functional. Just like there's OO and
*purely* OO. (C++ as opposed to Smalltalk). I'd wager that any programing
style taken to an extreme is bad because it assumes there is one true way to
do something and tries to shoe horn everything into that style. Taking
things to extreme's is worth the research effort though, since you get to
learn what fits and what doesn't. Giving langauge designers a better feel
for the design space by pushing the envelop of the explored design space.
Functional languages haven't caught on commercially because they have been
primiarly used as vehicles for doing research. The parties doing the
langauge work don't have any motive to force their ideas sell their ideas to
the commerical world. Most of the functional languages are pretty new in
comparison to langues like Simula which begot C++. I'd wager that in 20 or
so years everyone will be hacking languages that look like some of the
research languages today. It's taken about the long for simple ideas like
garbage collection to get pushed into the comercial world by languages like
Java, which builds on a lot of old research.
Seth LaForge
On Wed, 7 May 1997 11:53:15 GMT, Andrew Koenig <a...@research.att.com> wrote:
>In article <s6yenbk...@aalh02.alcatel.com.au> Chris....@alcatel.com.au (Chris Bitmead uid(x22068)) writes:
>> functions. Perhaps that's because hardly any main stream languages
>> support it? It's a bit hard to write functional COBOL you know.
>
>Agreed.
>
>> When did you observe a group of programmers using a higher-order
>> functional language that did not use them?
>
>languages do not support -- and their communities consider irrelevant --
>other key aspects of programming languages that most commercial
>programmers consider indispensible.
I think that in context what Chris meant by "higher-order functional
language" is any language which supports higher-order functions, i.e.
supports functions and continuations as first-class objects.
Languages which support higher-order functions need not be side-effect
free, or lazy. I've always thought that using the term "functional"
to refer to side-effect free, possibly lazy languages was a rather bad
choice of terms...
>For example, a good chunk of commercial programming practice today
>is related in some way to object-oriented design. A key notion in
>object-oriented design is the use of objects to represent concepts
>in the program being designed. An important characteristic of objects
>is their ability to store mutable state information.
>
>The higher-order functional languages generally do not support mutable
>state, because doing so would compromise referential transparency. In
>particular, higher-order functions seem to be the most useful when
>combined with lazy evaluation, which in turn does not seem to combine
>well with the idea of mutable state. So these well known and widely
>used design techniques simply do not apply in such languages.
This is simply not true. There is nothing which ties closures to lazy
nonmutating languages. I have found closures to be very useful in
lazy languages (Haskell), strict nonmutating languages (ML), and
side-effecting languages. In particular, Pizza (a superset of Java;
see http://www.cis.unisa.edu.au/~pizza/) supports closures and
anonymous functions quite nicely, and Sather
(http://www.icsi.berkeley.edu/~sather/) likewise supports closures in
a rather unique way. Note that both of these are OO langauges which
rely on side effects all the time.
I have found the closures in these languages to be really useful. In
writing a ray tracer in Sather, I used closures in the parser to
represent partially-evaluated portions of the parse tree for later
evaluation (the reason this was necessary has to do with grotty
details of OpenInventor syntax which I won't go into here). I used
closures and anonymous functions extensively in implementing a fractal
image compression algorithm in Pizza.
>That means, in turn, that if you wish to program in functional style,
>you really have to change almost everything about how you think
>about programming. It's not just a matter of using higher-order
>functions or not using them.
It's true that using higher-order functions effectively requires a
slight change in thinking, but it certainly doesn't require you change
everything, and it doesn't require that you use lazy side-effect free
languages. In my experience, closures simplify many programming
tasks, no matter what language you're working in. They are by no
means necessary, but they're really nice.
Seth
Marco Antoniotti
This is a very interesting and informative posting. I learned a lot
from it. However, being the hard-line Commonist Lisper I cannot help
to comment on the following. :)
In article <336FDF...@mti.sgi.com> Alexander Stepanov <step...@mti.sgi.com> writes:
From: Alexander Stepanov <step...@mti.sgi.com>
Newsgroups: comp.lang.scheme,comp.lang.lisp,comp.lang.misc,comp.lang.functional,comp.lang.c++
Date: Tue, 06 May 1997 18:47:29 -0700
Organization: SGI/MIPS
... much cut.
Now, take Common Lisp reduce. It is not generic. (If you define your own
doubly linked list, their reduce is not going to do anything reasonable
for it.) It is hard making it generic, or they would have done it.
Doubly linked lists in Common Lisp are easily implemented (the fact
that they are not in the language and that maybe lisp programmers do
not use them as much may be the reason for the lack of
implementations)
However, about REDUCE...
------------------------------------------------------------------------------
(defpackage "STL" ; just a name
(:use "COMMON-LISP")
(:shadow "REDUCE"))
(in-package "STL")
(defmethod reduce ((s sequence) f &key from-end start end initial-value)
(common-lisp:reduce f s
:from-end from-end
:start start
:end end
:initial-value initial-value))
(defmethod reduce ((s dll:dll) f &key from-end start end initial-value)
(dll:reduce f s
:from-end from-end
:start start
:end end
:initial-value initial-value))
(defmethod reduce ((s hash-table) f &key from-end start end initial-value)
;; You got the hang of it.
)
------------------------------------------------------------------------------
Where I will pardoned the swap of arguments (nobody said that CL is
perfect) and the assumption of existence of a DLL package with a DLL
class defined in it as well as a specialized dll:reduce.
Happy Lisping
--
Marco Antoniotti
==============================================================================
California Path Program - UCB
Richmond Field Station
tel. +1 - 510 - 231 9472
Darin Johnson
>In the days predating templates in C++, collection classes had to be
>done using polymorphism & downcasting. This was error prone and type
>unsafe, and the primary reason I didn't do much C++ programming at the
>time.
Yes, but now we have templates, and we can do polymorphism+downcasting
inside the template! Thus, type safety, few errors, ease of use, and
elegance, without all that ugly inefficiency of actually *duplicating*
code, which is what the vast majority of templated collection classes
do.
Why don't people do this?? I'm honestly baffled. Why not an array,
list, bag, set, etc, that operate on pointers to void, with templates
to create concrete type-safe classes? And this easily lets you have
precompiled collection classes, whereas even the best C++ compiler
today still has problems with precompiling templates, especially
monstrosities like STL.
>Using polymorphism plus downcasting as a substitute for genericity is
>the clearest indicator I can possibly find that the author is used to
>a dynamically typed language. This works fine for CLOS, Python,
>Smalltalk, what have you, but is inappropriate for statically typed
>languages such as C++, Ada, Eiffel, and others.
Yes, but static typing is also opposed to object orientedness (IMHO,
and depending upon how you were raised). That is, object oriented
fundamentals treats data as an amorphous object - you can perform
operations on the data *without* knowing the type.
Yes, I know static typing is a good thing, but that doesn't mean it's
not in opposition to OO at the same time. Languages achieve different
tradeoffs as they have different goals. Smalltalk wants to be a pure
OO language, to enable pure OO programs to be written, so static
typing has to go or take a severely diminished role. C++ has the goal
of being efficient for low level programming at the same time it has
OO concepts, so static typing has to stay while being loosened, and OO
has to be added while being restricted.
Also, by saying "substitute for genericity", I think the logic is a
bit backwards. Genericity implies typing, and thus is not necessarily
needed in languages with no typing or weak typing. (even downcasting
is undefinable, you can't downcast in Smalltalk...)
>Note that (with some care) an STL vector can be made into a
>pseudo-heterogeneous container by storing pointers. The care is
>necessary due to memory allocation issues.
If C++ had garbage collection, all these odd little rules and things
to remember about memory/constructors/destructors would have been
designed much differently.
But I consider this "care" to be obvious. STL advocates love to warn
about never storing pointers, as you might accidentally lose memory.
Gack, what a horrible argument. I might as well never call "new" as I
might lose memory. Obviously if someone is storing pointers in an STL
collection, they will need to take care that memory isn't lost,
*exactly* as if they were using the pointers anywhere else. Yes, I
know destructors won't get called on the objects that are pointed to
when the collection is destructed, that's obvious. Good programming
would imply that I destruct the objects before destructing the
collection anyway, regardless of if I store the objects themselves or
the pointers. It's *sloppy* programming to rely upon having
everything cleaned up just because you go out of scope.
Yes, memory leaks are a major headache; but I think the proposed
solution of having bloated slow code isn't perfect either (ie, bloated
because of immense duplication from templates, and slow because
objects are copied instead of pointers). Sadly, a large chunk of the
C++ community doesn't want to admit there was a tradeoff involved.
--
Darin Johnson
da...@usa.net.delete_me
Matt Austern
da...@usa.net.delete_me (Darin Johnson) writes:
> >Note that (with some care) an STL vector can be made into a
> >pseudo-heterogeneous container by storing pointers. The care is
> >necessary due to memory allocation issues.
>
> If C++ had garbage collection, all these odd little rules and things
> to remember about memory/constructors/destructors would have been
> designed much differently.
>
> But I consider this "care" to be obvious. STL advocates love to warn
> about never storing pointers, as you might accidentally lose memory.
Which STL developers say that you should never store pointers in
containers? Not Alex Stepanov, certainly, and not Bjarne Stroustrup.
Not the C++ standardization committee either, for that matter: the
standard C++ library contains an adaptor, mem_fun, which is
specifically intended for the case when an STL container contains
pointers.
It is absolutely not true that there's anything wrong with storing
pointers in STL containers. STL containers contain objects, and
pointers, in C++, are perfectly good objects. My automated tests
specifically test storing pointers in STL containers.
Alexander Stepanov
I got several dosen private messages containing code in Scheme that
purports to demonstrate the error of my ways. And now we do get CL
code that puts me into my proper place.
I tried to explain something. I might have failed. I might be wrong. But
I have spent 10 years writing code in these languages, and it is a
matter of common courtesy to assume that I do know something before
sending me angry personal messages accusing me of all kinds of
monstrous things.
To demonstrate that I heard of higher order functions I include a
hand-out I wrote in 1985 (note, that I do define a "generic" reduce)
plus few relevant manpages from a large algorithmic library that I wrote
in 84-85. I apologize for sending such a large post, but it might calm
some people.
(I even have two papers that deal with reduce in functional languages
setting, but I do not have them handy to post on the net, nor are they
are really worth reading, but for the fact that I been there done that.)
;;; Iterators
;;; one of the central ideas of higher order programming
;;; is the idea of using higher order functional forms
;;; (functions that produce functions) instead of using
;;; recursion (tail or otherwise)
;;; we can implement a function that adds square roots of all even
;;; numbers in an interval (a, b); but if we want to add square roots
;;; of all numbers in a list we shall need another program; and
;;; another one for vectors; and another one for heaps ...
;;; we can simplify our life by introducing iterators, that are
;;; somewhat like universal quantifiers on data structures
;;; simpliest class of functional forms are iterators
;;; iterator is a function that takes a structure and
;;; returns a function that takes a function f of one
;;; argument as its argument and applies f to every
;;; element of the structure
;;; most primitive kind of iterators can be produced with
(define (primitive-iterator initial-value transform)
(lambda (function)
(define (loop x)
(function x)
(loop (transform x)))
(loop initial-value)))
;;; sometimes the function we pass to the iterator is destructive
;;; and can affect x; to handle cases like that we define
(define (primitive-iterator! initial-value transform)
(lambda (function)
(define (loop x)
((lambda (next) (function x) (loop next))
(transform x)))
(loop initial-value)))
;;; For example, we can iterate through natural numbers with
(define for-each-natural-number
(primitive-iterator 1 1+))
;;; Problem:
;;; what will happen if you say
;;; (for-each-natural-number print)
;; ? (before you try it find out Ctrl-Break on your keyboard)
;;; here you can ask what good does it do to have a non-terminating
;;; iterators.
;;; but we can make functions that
;;; starting with any iterator can produce other iterators
;;; out of it
;;; for example, restrict-iterator takes a predicate and
;;; an iterator and returns a new iterator which applies
;;; function only to those elements that satisfy the predicate
(define (restrict-iterator predicate iterator)
(lambda (function)
(iterator (when-combinator predicate function))))
;;; and we can compose an iterator with a function
(define ((compose-iterator f iterator) g)
(iterator (compose g f)))
;;; and we can terminate the iteration with the following two
;;; iterator-manipulating functions:
(define (iterator-until predicate iterator marker)
(lambda (function)
(call-with-current-continuation
(lambda (exit)
(iterator (if-combinator predicate exit function))
marker))))
(define (iterator-while predicate iterator marker)
(lambda (function)
(call-with-current-continuation
(lambda (exit)
(iterator (if-combinator predicate function exit))
marker))))
;;; where call-with-current-continuation (or call/cc) is a
;;; function that ...
;;; there is an "extra" feature in iterators created with
;;; iterator-until and iterator-while: in case
;;; of "unnatural" termination they return a value that caused it
;;; otherwise they return a marker
;;; we can define a product of iterators
(define (product-of-iterators operation iterator1 iterator2)
(lambda (function)
(iterator1
(lambda (x)
(iterator2
(lambda (y)
(function (operation x y))))))))
;;; first class continuations allow us to step through an iterator
(define (make-step-iterator function iterator)
(lambda (return)
(iterator
(lambda (x)
(set! return
(call-with-current-continuation
(lambda (rest) (function x) (return rest))))))
#!false))
(define (step-iterator iterator)
(call-with-current-continuation
(lambda (here)
(iterator here))))
(define (sum-of-iterators operation iterator1 iterator2)
(lambda (function)
(let ((value1 '())
(value2 '()))
(let loop ((step1 (step-iterator
(make-step-iterator
(lambda (x) (set! value1 x))
iterator1)))
(step2 (step-iterator
(make-step-iterator
(lambda (x) (set! value2 x))
iterator2))))
(cond ((and step1 step2)
(function (operation value1 value2))
(loop (step-iterator step1)
(step-iterator step2)))
(step1 step1)
(step2 step2)
(else #!false))))))
(define (for-each-in-interval first last)
(iterator-until
(bind-1-of-2 < last)
(primitive-iterator first 1+)
'will-never-use-this-marker))
;;; it would also be nice
;;; to implement reduction (reduction operator was introduced by
;;; Kenneth Iverson in APL)
(define (reduce iterator)
(lambda (function . initial-value)
(define (add-to x)
(set! initial-value (function initial-value x)))
(cond (initial-value
(set! initial-value (car initial-value))
(iterator add-to)
initial-value)
(else
(let ((marker #!false))
(define (first-time x)
(set! initial-value x)
(set! marker #!true)
(set! first-time add-to))
(iterator (lambda (x) (first-time x)))
(if marker initial-value (function)))))))
;;; where set! is a special form that changes a value of a binding
;;; with all that we can give a new definition of factorial
(define (factorial n)
((reduce (for-each-in-interval 1 n)) *))
;;; Problem
;;; what does this function do:
(define (foo n)
((reduce
(compose-iterator (compose / factorial) (for-each-in-interval 0
n)))
+))
;;; ?
;;; Problem
;;; implement a function that takes an iterator and computes a mean of
;;; elements through which iteration is done
;;; functional forms on lists
;;; <cons, car and stuff>
(define (for-each-cdr list)
(iterator-while pair? (primitive-iterator list cdr) '()))
;;; (define for-each-cdr
;;; (compose (bind-1-of-2 iterator-while pair?)
;;; (bind-2-of-2 primitive-iterator cdr)))
(define (for-each-cdr! list)
(iterator-while pair? (primitive-iterator! list cdr) '()))
(define (for-each list)
(compose-iterator car (for-each-cdr list)))
(define (map! list)
(lambda (function)
((for-each-cdr list) (lambda (x) (set-car! x (function (car x)))))))
(define (reverse-append a b)
((reduce (for-each a)) (T-combinator cons) b))
(define (reverse-append! a b)
((reduce (for-each-cdr! a))
(lambda (x y) (set-cdr! y x) y)
b))
(define (vector-for-each-index v)
(for-each-in-interval 0 (-1+ (vector-length v))))
(define (vector-for-each v)
(compose-iterator (lambda (x) (vector-ref v x))
(vector-for-each-index v)))
(define (vector-map! v)
(lambda (function)
((vector-for-each-index v)
(lambda (i) (vector-set! v i (function (vector-ref v i)))))))
(define (rcons pair value)
(let ((temp (cons value '())))
(set-cdr! pair temp)
temp))
(define ((collect-cons iterator) function)
(let ((header (cons 9 9))) ;9 is as good as anithing
((reduce iterator)
rcons
header)
(cdr header)))
(define (map list)
(collect-cons (for-each list)))
(define (list-copy list) ((map list) identity))
(define ((collect-append! iterator) function)
(reverse!
((reduce iterator)
(lambda (x y) (reverse-append! (function y) x))
'())))
(define (map-append! list) (collect-append! (for-each list)))
(define (member-if predicate? list)
((iterate-until
(compose predicate? car)
(for-each-cdr list)
'())
identity))
(define (filter predicate list)
((collect-cons (restrict-iterator predicate (for-each list)))
identity))
(define (filter! predicate list)
((collect-append! (restrict-iterator (compose predicate car)
(for-each-cdr! list)))
identity))
The library that I created (a Scheme precurser to STL) did contain:
MAKE-ACCUMULATE
Format: ((MAKE-ACCUMULATE iterator)
function
initial-value
structure)
Parameters:
iterator - An iterator
function - A function of two variables.
initial-value - A value suitable as the first argument to the
function.
structure - A structure containing values suitable as the second
argument to the function.
Explanation: Make-accumulate creates an accumulating function;
i.e., a function which accumulates the results of another
function applied to a structure. An accumulating function takes
three arguments. The first is an initial value to start the
accumulation process. This initial value is used both as a
starting value for the result to be returned and as an initial
argument to function. The second argument to an accumulating
function is a function to be applied. The third argument is a
structure to which the function is to be applied. Make-accumulate
itself takes an iterator as an argument. This describes how the
function is to be applied to the structure. Thus, the function
returned by make-accumulate is specific to the iterator and can
be called with various functions and structures. It is, of
course, necessary that the iterator be compatible with the
structure and that the function be compatible both with the
structure and initial value. Accumulate-for-each is an
accumulating function created by calling make-accumulate with the
iterator for-each.
Implementation:
(define ((make-accumulate iterator)
function
initial-value
structure)
(iterator
(lambda (x)
(set! initial-value (function initial-value x)))
structure)
initial-value)
and
AKE-REDUCE
Format: (MAKE-REDUCE predicate reduction)
Parameters:
predicate - A predicate which returns true iff the structure
passed to it is non-empty; e.g., if a list is not null.
reduction - A reduction operator.
function - A function of two variables.
structure - A structure.
identity - (optional argument) Result to return if the structure
is empty.
Explanation: Make-reduce creates a reduction operator which works
on empty data structures as well as non-empty ones given a
predicate which works on non-empty structures. A reduction
operator is one which applies a function to all the elements of a
structure and returns the result. It may or may not be
destructive of the structure. Make-reduce returns a function of
two arguments with an optional third argument. If the structure
is non-empty, the reduction returned by make-reduce is the same
as the reduction passed to it. If the structure is empty, the
reduction returned will return the identity argument passed to
make-reduce (if such an argument is present) or the empty list
(if no identity argument is present.) For more information, see
the description of REDUCE below.
Usage: (see the definition of REDUCE, below)
Implementation:
(define ((make-reduce non-empty-predicate? non-empty-reduction)
operation structure . identity)
(cond ((non-empty-predicate? structure)
(non-empty-reduction operation structure))
((pair? identity) (car identity))
(else (operation))))
and
REDUCE
Format: (REDUCE operation list)
Parameters:
operation - A function of two variables. The function should
return a value suitable as an argument to it.
list - A list containing elements suitable as arguments to the
operation.
Explanation: Reduce applies the operation to all elements of the
list and returns the result. The operation should be associative.
Reduce returns the empty list if called with an empty list,
regardless of what the operation itself would return if it were
called with an empty list.
Usage: (define (mag+ x y) (+ (abs x) (abs y))) ==> mag+
(reduce mag+ '(1 -5 -4 7)) ==> 17
(reduce mag+ '()) ==>
'()
(+) ==> 0
Implementation:
(define reduce
(make-reduce
pair?
(lambda (operation list)
(accumulate-for-each
operation
(car list)
(cdr list))))
and
PARALLEL-REDUCE!
PAIRWISE-REDUCE!
Format: (PAIRWISE-REDUCE-NON-EMPTY-LIST! operation list)
(PAIRWISE-REDUCE operation list)
(PARALLEL-REDUCE operation list)
Parameters:
operation - A function of two variables. The list should contain
elements suitable as arguments to this function and the function
should itself return a value suitable as an argument to itself.
The function should be associative.
list - A list, possibly empty.
Explanation: Parallel-reduce! is a reduction operation. It
applies an operation on the elements of a list in parallel in a
pairwise fashion; i.e., it applies the operation to the first two
elements in the list, then to the next two elements in the list,
etc. This leaves a list with half as many elements. Parallel-
reduce! then works on the halved list, halving its size again.
This is continued until a single element remains containing the
value to be returned. Parallel-reduce! modifies the list it is
passed and returns the result of the operation. After its
invocation, the list passed as input contains a single element
whose value is the result of applying the operation to all the
elements of the original list (or is an empty list if the
original list was empty.) On a single processor and for
operations without side-effects, parallel reduction is similar to
ordinary (sequential) reduction. However, for operations with
side effects, in particular when intermediate results are saved,
parallel reduction can give rise to much more efficient
algorithms. Pairwise-reduce! carries out one round of parallel-
reduce!, halving the list.
Usage: (define a '(2 5 8 11 13)) ==> a
(pairwise-reduce! - a) ==> (-3 -3 13)
a ==> (-3
-3 13)
(define b '("ex" "c" "elle" "nt")) ==> b
(parallel-reduce! string-append b) ==> "excellent"
(car b)
Implementation:
(define (pairwise-reduce-non-empty-list! operation list)
(for-each-cdr
(lambda (x)
(when (pair? (cdr x))
(set-car! x (operation (car x) (cadr x)))
(set-cdr! x (cddr x))))
list)
list)
(define pairwise-reduce!
(make-reduce pair? pairwise-reduce-non-empty-list!))
(define parallel-reduce!
(make-reduce
pair?
(lambda (operation list)
(apply-until
(lambda (x) (null? (cdr x)))
(lambda (x)
(pairwise-reduce-non-empty-list! operation x))
list)
(car list))))
Lyman S. Taylor wrote:
>
> In article <336FDF...@mti.sgi.com>,
> Alexander Stepanov <step...@mti.sgi.com> wrote:
> >> that the STL couldn't be done in Eifel or Java. But SML or
> >> CLOS or...you're gonna have to substantiate that one.
>
> I, for one, am still waiting...... "impossible" "cannot"
> deserve some justification.
>
> >1. Addresses.
> >
> >STL is based on the fundamental assumption that addresses are
> >good. The memory model of the C machine is the right base for the
> >abstraction. Neither Lisp nor ML allow a natural address/location
> >abstraction.
>
> Eh?? Admittedly Lisp nor ML allow one to point to internal structure
> of "entities" ( i.e. you can't do arbitrary pointer manipulation).
> However, constrained to the boundaries of "entities" what exaclty is
> inexpressible?
>
>
> > You can implement address like thingies in them, but
>
> Oh. let's see. It acts like a adress, hence "address like".
> So here were have an address/location abstraction.
>
> >the built-in data strucutres do not based on the needed abstraction.
>
> And what praytell stops you from layering/adding this abstraction onto the
> built-in data structures?
>
> [ Remeber the postulation stipulated several messages back was that it was
> "impossible" to do. In my book "impossible" is a relatively strong
> stipulation. ]
>
> >Note that in Lisp one tends to stick to the built-in data-structures.
> >I never seen a serious impementation of a doubly-linked lists in Lisp.
>
> I haven't seen one... therefore it doesn't exist and therefore impossible.
> Yeah right. Or could it possibly be that most folks, if they need one,
> just independently "reinvent the wheel"? How likely is that if it isn't
> in the "standard library"? If the folks a Harlequin/Lucid, Franz, Symbolics,
> etc. ( i.e. a large group of lisp programmers with some legacy of code
> behind them.. ) chime in and say there is NO doubly-linked lists in any
> of their code... then I might fell inclined revisit this argument.
>
>
> >as I know, the same holds true for SML. Arrays and lists can not
> >be easily unified. Or at least, they are not usually unified.
> >Take a look at list->vector, vector->list pair in Scheme and compare it
> >with generic constructor in STL containers.
>
> And if you added a generic constructor abstraction in Common Lisp utilizing
> macros you couldn't get the STL functionality??
>
> I asked this before and didn't really get a response. So I'll rephrase it.
> C++ templates are essentailly "syntactic sugar". There's little templates
> do that a programmer couldn't do by just typing approximately the same
> code over and over again. Fortunately the C++ compiler does some
> bookkeeping for him/her and does alot of code writing and substitution
> "automagically".
>
> Likewise the macro system of Common Lisp can be used to add "syntactic
> sugar" to Common Lisp code. It can be used to do bookeeping (i.e. execute
> arbitrary pieces of code at compile time) in conjunction with writing
> code.
>
> So what stops a STL-like implementor from
> i. adding a template-like mechanism to "raw" CL.
> ii. implementing the STL using this mechanism.
>
> [ Again discounting compile time checks on "correctness" of the code
> given that Common Lisp is a dynamic language and isn't overly pressed
> about static type checking. ] While not a CL macro "guru", offhand
> I do not see what the "show stopper" is in implementing this.
>
> Code refering to these generic may have to be incased in macro body but
> that seems about as "different"/"onerous" as suffixing "<data_type>" after
> STL type/function references.
>
> [ throw in the use of CLOS for overloading function names and I definately
> do not.]
>
> Something along the lines of....
>
> (with-generics ( (generic-type1 param )
> (generic-type2 param param )
> ( (generic-fcn1 (generic-arg param )
> (generic-arg param ) param param ) )
> ( (generic-fcn2 (generic-arg param param) param ) ))
>
> ;; if pressed about speed.. some declarations..
> (declare (..... (var10 generic-type1 ) (var11 generic-type2) ... ))
>
>
> ... (generic-fcn1 var10 (generic-fcn2 var11 ) .... ) ... )
>
> the macroexpansion of the above could be just as name-mangled as anything
> a C++ compilier might generate... ;-)
>
> [ I'm not too familiar with Scheme macros to affirm/discount there
> ability to do this task. I wouldn't dismiss it though. ]
>
> In Essence, in the case of lisp I think that if it is syntactic sugar
> you are in seach of, then you criticism should appeal to the deficiencies
> of the syntactic sugar making capabilities of the language. Otherwise
> this debate is "stuck on 'stupid' and not getting off".
>
> >One of the things I am trying to do now is to extend the iterator
> >classification to handle non-uniform memory references. (One of
> >my collegues, Fred Chow, proposes to call them NUMA-iterators.) It is
> >quite remarkable how the existing STL framework could be extended to
> >deal with MP, cache behaviour, parallelism. But it all relies on
> >addresses. Abstract addresses, but addresses nevertheless.
> >
> >2. Container vs. iterator
> >
> >Lisp also brought a conceptual confusion of list as an iterator and list
> >as a data structure. There is no way to distiguish between the two uses.
> >It is a subtle point, but I am sure you can see it.
>
> Errr, you seemed to have lost me on this one...
>
> C/C++ Lisp
>
> int a[4] = { 1, 2, 3, 4};
> int *p = a; (setf p '( 1 2 3 4 ))
>
> printf("%d \n", *p); (format t "%d ~%" (first p ))
> p = p + 1 ; (setf p (rest p))
> printf("%d \n", *p): (format t "%d ~%" (first p ))
>
> Exactly what is the subtle difference in the way C/C++ treats "p"
> and how Lisp treats "p"?
>
> >3. Type system
> >
> >It is possible to define swap in C++. And you can use partial
> >specialization to choose the right swap.
>
> The unstated implication that in Scheme/Common Lisp you cannot
> define swap????? Surely you jest....
>
> for CL see ( slightly more than the same functionality..)
>
> http://www.harlequin.com/books/HyperSpec/Body/mac_rotatef.html#rotatef
>
> >I do not know any other language where I can easily say:
>
> [ template reduce code deleted... ]
>
> >3. The default identity element of plus is 0
>
> Oh like
> (+) ==> 0
>
> >4. The default identity element of multiply is 1
>
> Oh like
> (*) ==> 1
>
> >
> >Now, take Common Lisp reduce. It is not generic. (If you define your own
> >doubly linked list, their reduce is not going to do anything reasonable
> >for it.) It is hard making it generic, or they would have done it.
>
>
> This is akin to saying C++ isn't good because printf isn't generic
> enough...
>
> 1. In Common Lisp reduce is a function. So yeah it is a tad difficult to
> expand to other datastructures. You can't overload the name ( actually
> not quite true but could involve implementation dependent gyrations)
> It has also been around "forever" too.
>
> http://www.harlequin.com/books/HyperSpec/Body/fun_reduce.html#reduce
>
> However, I'm going to use a simplified argument list that matches
> the reduce that is there..
>
> (defgeneric my-reduce ( fcn seq ) )
>
> ;; if just any prefdefined sequence and a function...
> (defmethod my-reduce ( (fcn function) (seq sequence ) )
> (reduce fcn seq ))
>
> (defmethod my-reduce ( (fcn function) (seq T ) )
> ... here define insanely great generic algorithm to
> do reduce.... )
>
> (defmethod my-reduce ( (fcn function) (seq whiz-bang) )
> ... here define even more insanely great generic alogirtm
> to do reduce specialized for the whiz-bang data structure)
>
> [ NOTE: I could if I made explicit the full lambda list...
> i. assign the current REDUCE to a new symbol.
> OLD-REDUCE ( so I could use the predefined code).
>
> ii. define my defgeneric on the name REDUCE.
> and say yes the warning message "do you really want
> do this, I'm about to redefine reduce as a generic
> function and potentiall blow away the previous
> definition".
> iii. define my new reduce with the same name, but old
> argument set-up. Albeit for slightly slower
> overall performance... since now a generic function
> instead of a function. ]
>
> 2. The default reduction function for reduce is + ... Gee that's gotta
> be hard to do in Lisp, huh??? :-)
>
> If the lambda list for reduce looked list STL's would this be
> "impossible".
>
> (defgeneric stl-reduce ( begin-iter end-iter
> &optional (fcn function stl-plus)) )
>
> [ again + is a function in CL. If you want to overload with abandon
> you'll need your own name. ]
>
> (defmethod stl-reduce ( (being-iter iterator) (end-iter iterator)
> &optional (fcn function stl-plus ))
> .... insanely great generic stl-reduce code goes here... )
>
> .....
>
> --
> Lyman S. Taylor Comment by a professor observing two students
> (ly...@cc.gatech.edu) unconscious at their keyboards:
> "That's the trouble with graduate students.
> Every couple of days, they fall asleep."
--
Alexander Stepanov
step...@mti.sgi.com
Thant Tessman
Alexander Stepanov wrote:
> But if I was succesful, it was only because
> Bjarne Stroustrup provided me with the right tool.
I wrote:
> This is the claim I reject. It doesn't surprise me at all
> that the STL couldn't be done in Eifel or Java. But SML or
> CLOS or...you're gonna have to substantiate that one.
[...stuff...]
At the end of this post is an implementation of doubly-linked lists
implemented in SML but in the style of the STL. There's also
a "replace" function like the one in the STL just to show
how it would work.
I think it satisfies all your criteria for a genericity.
1) You can mutate what you find in the data structure
Iterators are separate from containers so that:
2) You can restart searches
3) You can have multiple search paths
4) You can consider subranges
5) You can compare two positions for equality
Also, this is fully generic, with no run-time type dispatching.
This implementation took me about two hours and I am not an SML
expert by any stretch of the imagination. But it's still more
succinct than the equivalent C++ code. And doing things in the
spirit of SML using higher-order functions to build your data
accessor functions would produce still more succinct code than
what I have here (as Greg Morrisett has already demonstrated).
The only advantage to programming this way in C++ is that templates
support partial specialization. I mentioned earlier that I thought
this was pretty neat. But the STL only uses it as a replacement
for what using higher-order functions buys you anyway. And believe
me, I use partial specialization all the time. I'd still rather
be programming in SML.
> [...reduce...]
>
> I do not need to pass ++, *, ==, = for iterators as our ML experts
> suggest that we do. Types are good. Compiler will find the right
> operations.
First, not wanting to pass in these functions is a long way from
"can't do a generic linear search". Second, CLOS generic functions
allow you to specialize functions in exactly the same way that templates
allow partial specialization (except that the dispatch is done
dynamically). So I don't buy for a moment that it's hard making a
generic "reduce" in Common Lisp simply because no one's done it.
I think it's more likely that no one has seen the need since it's
so easy just to create and pass around functions directly.
(BTW, things like "reduce" is what I was talking about when I said
that the STL came off as merely an attempt to make it easier to
do things in C++ that were already easy in other languages.)
The whole trick to the STL is separating containers from iterators and
getting all the properties of both consistent enough to make it easy
to write generic algorithms. This is a very cool thing. Your
implementation of the STL plays C++'s strengths well (were it that
we all had so much influence with the language creator), but there
is NOTHING inherent about this problem that makes C++ particularly
suited to solving it.
Please, please, please just let C++ die.
-thant
(**************)
signature DATASTRUCTURE =
sig
exception MemoryFault
eqtype ''a iterator
eqtype ''a container
val null : ''a iterator
val new : unit -> ''a container
val push_back : ''a container * ''a -> unit
val push_front : ''a container * ''a -> unit
val first : ''a container -> ''a iterator
val last : ''a container -> ''a iterator
val prev : ''a iterator -> ''a iterator
val next : ''a iterator -> ''a iterator
val set : ''a iterator * ''a -> unit
val get : ''a iterator -> ''a
end
structure Chain : DATASTRUCTURE =
struct
exception MemoryFault
datatype ''a iterator =
LNull
| Link of ''a ref * {prev: ''a iterator ref, next: ''a iterator ref}
datatype ''a container = Chain of {head: ''a iterator ref,
tail: ''a iterator ref}
fun new () = Chain {head = ref LNull, tail = ref LNull}
fun push_back (Chain {head, tail}, item) =
case tail of
ref LNull => let
val link = Link (ref item, {prev=ref LNull,
next=ref LNull})
in
tail := link;
head := link
end
| ref (Link (_, {next, ...})) => let
val link = Link(ref item,
{prev = ref (!tail),
next = ref LNull})
in
next := link;
tail := link
end
fun push_front (Chain {head, tail}, item) =
case head of
ref LNull => let
val link = Link (ref item, {prev=ref LNull,
next=ref LNull})
in
tail := link;
head := link
end
| ref (Link (_, {prev, ...})) => let
val link = Link(ref item,
{prev = ref LNull,
next = ref (!head)})
in
prev := link;
head := link
end
fun first (Chain {head as ref link, ...}) = link
fun last (Chain {tail as ref link, ...}) = link
fun next LNull = raise MemoryFault
| next (Link (_, {next as ref n, ...})) = n
fun prev LNull = raise MemoryFault
| prev (Link (_, {prev as ref p, ...})) = p
fun set (LNull, _) = raise MemoryFault
| set (Link (item, _), newValue) = (item := newValue)
fun get LNull = raise MemoryFault
| get (Link (item, _)) = !item
val null = LNull
end
functor SomeAlgos(DataStructure:DATASTRUCTURE) =
struct
(* for now all we have is replace, but you get the point *)
fun replace(first, last, oldValue, newValue) =
let
fun f i =
if (i=DataStructure.null) then ()
else
(if ((DataStructure.get i) = oldValue)
then (DataStructure.set (i, newValue))
else ();
if (i<>last) then f(DataStructure.next i) else ())
in
f(first)
end
end
(* an example of their use *)
open Chain;
val chain : int container = new ();
push_back(chain, 1);
push_back(chain, 2);
push_front(chain, ~1);
val i = first chain;
(* specialize the algorithm to chains, like instantiating a template *)
structure SomeChainAlgos = SomeAlgos(Chain);
SomeChainAlgos.replace(first chain, last chain, 1, 99);
(* here's polymorphic swap in SML *)
fun swap (a, b) =
let
val tmp = !a
in
a := !b;
b := tmp
end
Peter Ludemann
Matt Austern <aus...@isolde.mti.sgi.com> writes:
> Alex and I tried to implement the STL in Java; you can see our attempt
> at http://reality.sgi.com/austern/java/index.html. For a number of
> reasons, though, the attempt wasn't all that successful. The most
> obvious problem is that Java doesn't have any sort of genericity at
> all (polymorphism is not a substitute), but there were actually some
> other issues as well.
What's wrong with using "interfaces" to describe the interesting usage
properties of the data structures? That would avoid the need for
polymorphistic downcasting. Of course, people would need to wrap
their data-structures in interface declarations, e.g.:
class SimpleList implements LeftToRightTraversal, PositionIndexing {
// LeftToRightTraversal interface methods are First(), Next()
// PositionIndexing interface method is Get(int i)
// (note that list.First() == list.Get(0))
}
but that could be done with a downcast in the library.
It's hard to get such interface designs right. Back in the old days,
when we didn't call these things "objects" (one project I worked on
had "agents" and "aspects"), we mis-designed a RDBMS interface to have
only the methods "First", "Last", "Next", "Previous", with horrible
performance for positioning to the i'th result).
--
Peter Ludemann +1.415.813.6806 (fax: +1.415.813.7499)
Software Architect lude...@inxight.com
InXight Software, Inc. http://www.inxight.com
PAHV 105, 3400 Hillview Ave., Palo Alto, CA 94304
Lyman S. Taylor
>> CLOS or...you're gonna have to substantiate that one.
I, for one, am still waiting...... "impossible" "cannot"
deserve some justification.
>1. Addresses.
>
>STL is based on the fundamental assumption that addresses are
>good. The memory model of the C machine is the right base for the
>abstraction. Neither Lisp nor ML allow a natural address/location
>abstraction.
Eh?? Admittedly Lisp nor ML allow one to point to internal structure
of "entities" ( i.e. you can't do arbitrary pointer manipulation).
However, constrained to the boundaries of "entities" what exaclty is
inexpressible?
> You can implement address like thingies in them, but
Oh. let's see. It acts like a adress, hence "address like".
So here were have an address/location abstraction.
>the built-in data strucutres do not based on the needed abstraction.
And what praytell stops you from layering/adding this abstraction onto the
built-in data structures?
[ Remeber the postulation stipulated several messages back was that it was
"impossible" to do. In my book "impossible" is a relatively strong
stipulation. ]
>Note that in Lisp one tends to stick to the built-in data-structures.
>I never seen a serious impementation of a doubly-linked lists in Lisp.
I haven't seen one... therefore it doesn't exist and therefore impossible.
Yeah right. Or could it possibly be that most folks, if they need one,
just independently "reinvent the wheel"? How likely is that if it isn't
in the "standard library"? If the folks a Harlequin/Lucid, Franz, Symbolics,
etc. ( i.e. a large group of lisp programmers with some legacy of code
behind them.. ) chime in and say there is NO doubly-linked lists in any
of their code... then I might fell inclined revisit this argument.
>as I know, the same holds true for SML. Arrays and lists can not
>be easily unified. Or at least, they are not usually unified.
>Take a look at list->vector, vector->list pair in Scheme and compare it
>with generic constructor in STL containers.
And if you added a generic constructor abstraction in Common Lisp utilizing
>One of the things I am trying to do now is to extend the iterator
>classification to handle non-uniform memory references. (One of
>my collegues, Fred Chow, proposes to call them NUMA-iterators.) It is
>quite remarkable how the existing STL framework could be extended to
>deal with MP, cache behaviour, parallelism. But it all relies on
>addresses. Abstract addresses, but addresses nevertheless.
>
>2. Container vs. iterator
>
>Lisp also brought a conceptual confusion of list as an iterator and list
>as a data structure. There is no way to distiguish between the two uses.
>It is a subtle point, but I am sure you can see it.
Errr, you seemed to have lost me on this one...
C/C++ Lisp
int a[4] = { 1, 2, 3, 4};
int *p = a; (setf p '( 1 2 3 4 ))
printf("%d \n", *p); (format t "%d ~%" (first p ))
p = p + 1 ; (setf p (rest p))
printf("%d \n", *p): (format t "%d ~%" (first p ))
Exactly what is the subtle difference in the way C/C++ treats "p"
and how Lisp treats "p"?
>3. Type system
>
>It is possible to define swap in C++. And you can use partial
>specialization to choose the right swap.
The unstated implication that in Scheme/Common Lisp you cannot
define swap????? Surely you jest....
for CL see ( slightly more than the same functionality..)
http://www.harlequin.com/books/HyperSpec/Body/mac_rotatef.html#rotatef
>I do not know any other language where I can easily say:
[ template reduce code deleted... ]
>3. The default identity element of plus is 0
Oh like
(+) ==> 0
>4. The default identity element of multiply is 1
Oh like
(*) ==> 1
>
>Now, take Common Lisp reduce. It is not generic. (If you define your own
>doubly linked list, their reduce is not going to do anything reasonable
>for it.) It is hard making it generic, or they would have done it.
Richard A. O'Keefe
a...@research.att.com (Andrew Koenig) writes:
>Desparate? Hardly. It's an expression of the pragmatic observation
>that an awful lot of programs -- and programmers -- don't make a great
>then by all means choose a language that supports them the way you like.
>But don't assume that your taste is universal.
Very few tastes are universal.
A taste for programs that can visibly be seen to be correct is certainly
not one of them. A great deal of programmers are very bad at what they
do. We *cannot* measure the usefulness of a technique by counting noses.
(We *can* measure the profitability of a product that way, but that's a
quite different thing.) We should measure the effectiveness of a tool
like higher order functions by lines _not_ written, lives _not_ lost.
And is Andrew Koenig actually right in his claim? There seem to be a lot
of people who say they are using C++, and C++ templates surely have to
count as meta-functions. (The C++ template language is computation-
universal; when you instantiate an innocent-looking library template,
an _amazing_ amount of compile-time computation may go on behind the
scenes, and I'm not talking about the innards of the compiler either,
I'm talking about computations _in_ the template language.) If the
structuring of the library in the draft C++ standard doesn't prove the
usefulness of (compile-time) higher-order functions, what _does_ it prove?
Olivier Lefevre
Alexander Stepanov wrote:
> [...] I always sought the best advice from the
> experts available to me to assertain if such a task would be possible.
> For all of these languages I came to the conclusion that I would not
> be able to accomplish my task.
You posted a little earlier a list of your requirements for the
linear search. Can we look at it the other round and have the list
of questions these experts were asked, the crib sheet, in other
words?
Regards,
Olivier Lefevre
New York, NY
Chris Bitmead uid(x22068)
Alexander Stepanov <step...@mti.sgi.com> writes:
> > This is the claim I reject. It doesn't surprise me at all
> > that the STL couldn't be done in Eifel or Java. But SML or
> > CLOS or...you're gonna have to substantiate that one.
>
> 1. Addresses.
>
> STL is based on the fundamental assumption that addresses are
> good. The memory model of the C machine is the right base for the
> abstraction. Neither Lisp nor ML allow a natural address/location
> abstraction.
I'm really confused about this statement. How does a reference to a
Lisp object differ to a pointer to a C++ object. I just can't see what
the distinction is.
> You can implement address like thingies in them, but
> the built-in data strucutres do not based on the needed abstraction.
Huh? STL was not built using the "built-in data structures" of
C++. STL *IS* a collection of data structures.
The question is, could you write some CLOS sets, vectors, lists, and a
set of algorithms that work over all of them.
> Note that in Lisp one tends to stick to the built-in data-structures.
> I never seen a serious impementation of a doubly-linked lists in Lisp.
I had never seen an implementation of doubly linked lists in C++
either until I actually went to the trouble of writing my own.
> (Yes, yes, I had done one myself too, but it was not serious.) As far
> as I know, the same holds true for SML. Arrays and lists can not
> be easily unified. Or at least, they are not usually unified.
Surely we are discussing what can be done, rather than what is usually
done? Arrays and lists in C++ were never unified until STL came along
right?
> 2. Container vs. iterator
>
> Lisp also brought a conceptual confusion of list as an iterator and list
> as a data structure. There is no way to distiguish between the two uses.
Well, that is only one way of using lisp. You can do the same in C++
if you want.
> It is a subtle point, but I am sure you can see it. It also makes it
> impossible to have an ownership or whole-part semantics for data
> structures and makes it impossible to survive without
> garbage collection. (I like garbage collection as an option, but
> Lisp and ML make a virtue out of necessity.)
Well certainly no functional language could survive without GC.
Hey, if you admit it's a necessity, it might as well be a virtue eh?
> 3. Type system
>
> It is possible to define swap in C++. And you can use partial
> specialization to choose the right swap.
<snip>
Well I didn't think this was a debate about static vs dynamic
typing. Of course, implementing swap in lisp is even more trivial than
C++, although most lispers consider assignment (which swap is a form
of), unnecessary and bad style.
> And you should see amazing things you can do with types using
> partial specialization. (Look at the description of iterator_traits
> in the standard.) It is very easy to specify very complicated
> relations among type categories.
A static typing argument, which I don't want to get into.
(Of course it's easy to use the type system in CLOS to do
specialisation as well, and IMHO much more powerful as well.)
> It is so easy to use the type system to carry semantic information
> and to use types for selecting correct algorithms.
Same goes for CLOS.
> Note, that if I want to add a bunch of doubles I just say:
>
> vector<double> v;
>
> // fill v with doubles
>
> cout << reduce(v.begin(), v.end());
>
> // now print the product:
>
> cout << reduce(v.begin(), v.end(), multiply<double>());
Yes, nice but easier in CLOS. Following is an implementation of reduce
in Scheme. To make it do what you want in CLOS to work on generic
types, all one has to do is to substitute "car" "cdr" and "null?" for
some suitable iterator generic functions, with suitable data structure
iterators which define these generic features. You would probably pass
an iterator rather than the data structure itself.
BTW, you'll also notice that the Lisp version is something that your
average programmer would actually write in real life. All that STL
code you wrote, while terribly clever, is probably too complex for
your average programmer to go to the effort of writing in real life.
First up, the list only version...
(define (reduce op list)
(if (null? (cdr list))
(car list)
(op (car list) (reduce op (cdr list)))))
(define v (make-vector))
;; fill with doubles
(reduce + v)
;; now print the product:
(reduce * v)
Now to make it work with different data structures... you would
probably have data structures have a method called "get-iterator" or
something and the code would look something like:
(define (reduce op iter)
(if (at-end? iter)
(obj iter)
(op (next iter) (reduce op (next iter)))))
(define v (make-vector))
;; fill with doubles
(reduce + (get-iterator v))
Still very easy to write. Much easier than C++.
> I do not need to pass ++, *, ==, = for iterators as our ML experts
> suggest that we do. Types are good. Compiler will find the right
> operations.
Not passing iter methods is easy to achieve in all OO languages I
think, including eiffel.
> And if tomorrow I put my doubles into a set (does SML have sets?),
> I can just say:
>
> set<double> v;
>
> // fill v with doubles
>
> cout << reduce(v.begin(), v.end());
Just a result of having nice consistent data structures and iterators.
> Now, take Common Lisp reduce. It is not generic. (If you define your own
> doubly linked list, their reduce is not going to do anything reasonable
> for it.) It is hard making it generic, or they would have done it.
I'm not expert in CL, so I havn't really used it's version of
reduce. I suppose it only works for lists, but there is nothing
stopping you writing a set of consistent data structures with a reduce
function that works over all of them.
>SML and CLOS? I do not think so.
While it is common in lisp to do most of your work with lists, I can't
see why that is a problem with the language. Perhaps it is just time
you implemented STL in Lisp.
Eli Barzilay
Whow, man - now you got me - please don't insult Lisp if you havn't used
it
(and reading your mail I see that you DON'T know it too good).
So we have C and we have C++, this is the same as Lisp and CLOS - saying
that
the Lisp reduce function is not generic is very true - it works only for
Lisp
lists - but try doing something similar with C - where you don't even
have any
container primitive data structure except for arrays.
So the rules should be that if you use C++ to show how beautiful it is -
then
you must let me use CLOS for the same thing! And here is a possible
translation of what you've shown in Lisp using CLOS (not that I think
that
this is the best way of doing this -- you do have some questionable
points in
your code). This is based on some definitions for the "iter" class, and
the
operation class with plus as an instance.
;;; 1. Normally, reduce returns an identity element of its operation.
;;; 2. The default operation of reduce is plus.
(defmethod GREDUCE ((first iter) (last iter) &optional (op plus))
(if (iter-equal first last)
(identity-element op)
(let ((result (iter-value first)))
(loop while (not (iter-equal (advance first) last))
do (setf result (apply-op op result (iter-value first))))
result)))
;;; 3. The default identity element of plus is 0
(defmethod IDENTITY-ELEMENT ((op plus-op))
0)
;;; 4. The default identity element of multiply is 1
(defmethod IDENTITY-ELEMENT ((op multiply-op))
1)
;;; add a bunch of doubles - based on implementation for a vect class
(let ((v (make-instance 'vect)))
;; fill v with doubles
(print-object (greduce (get-first v) (get-last v)) t)
;; now print the product:
(print-object (greduce (get-first v) (get-last v) multiply) t)
)
;; And if tomorrow I put my doubles into a set
(let ((v (make-instance 'set)))
;; fill v with doubles
(print-object (greduce (get-first v) (get-last v)) t)
;; now print the product:
(print-object (greduce (get-first v) (get-last v) multiply) t)
)
;; And if, tomorrow, you define sets that use skip lists you just do
(let ((v (make-instance 'skip-set)))
;; fill v with doubles
(print-object (greduce (get-first v) (get-last v)) t)
;; now print the product:
(print-object (greduce (get-first v) (get-last v) multiply) t)
)
Now I'm sure that you will see something up there and say that this is
not
what you need, or I didnt make something, etc. Just remember that
modifying
the above for any kind of behavior you want is VERY easy. So will be an
implementation for the container classes and iterator - and guess what -
I can
even do that with DOUBLY-LINKED list implementation (I guess that using
two
pointers and really using them will mean that this will be a `serious'
implementation?)
--
Eli
Barzilay:
Maze
is Life!
Andrew Koenig
In article <5kq8jp$3...@cri.ens-lyon.fr> dmon...@ens-lyon.fr (David Monniaux) writes:
> Andrew Koenig (a...@research.att.com) wrote:
> : Never -- but it doesn't matter, because the higher-order functional
> : languages do not support -- and their communities consider irrelevant --
> : other key aspects of programming languages that most commercial
> : programmers consider indispensible.
> This argument, which is basically that academic people design pretty languages
> that are unuseable in "real" environments is somewhat flawed (see below).
That's not my argument. Rather, it is that there several schools of
language design, each of whose adherents considers irrelevant some things
that other schools' adherents consider essential. Each school believes
its favorite environments and problems to be the only `real' ones.
> You should perhaps try "semi functional" languages like ML, especially
> Objective CAML. It seems to have what most people here want:
> - functional features
> - imperative features
> - objects (not very used, since the functors seem more powerful for
> most purposes)
> - functors and modules
I have used ML a good bit, but I would have a very hard time convincing
my colleagues on the business side of the house to use it, if only
because the first prerequisite is the widespread availability of a
commercially supported compiler on each of several platforms and
corresponding commercial training courses. Plus a significant commercial
user community -- no one wants to be the first to bet part of their
business on something.
Incidentally, the ML that I've used has neither inheritance nor
overloading, nor is it likely to acquire them any time soon.
> When it comes to implementing structures and having generic algorithms,
> I think modules and functors are very powerful. You can, for instance,
> write a whole module using, say, a priority queue. You test it with,
> say, a heap for that queue. Then you feel that more appropriate
> structures may be better (say, you want to have a disk-cached queue).
> You then abstract the queue, making it a parameter. You can use your
> module, by simply instanciating it with your heap or your nifty
> disk-cached system.
> The standard library features Map's, Set's etc..., and more structures
> are easily coded. I've myself added Heap's etc...
Modules and functors are very powerful indeed, for similar reasons to
the ones that make C++ templates powerful.
> PS: As for the general tone of the discussion, I'm somehow disgusted.
> Many people here seem to argue that their way is the only way, and
> that people who don't agree have obviously never done "serious"
> programming. The quality of the talk would certainly improve if
> we spent less time accusing each other of, basically, incompetency,
> and more time actually working on design.
I think we're in violent agreement.
David Chase
Alexander Stepanov wrote:
> I tried to explain something. I might have failed. I might be wrong. But
> I have spent 10 years writing code in these languages, and it is a
> matter of common courtesy to assume that I do know something before
> sending me angry personal messages accusing me of all kinds of
> monstrous things.
But you are not the only person for whom this is true. It
is pretty interesting that someone (not you) might assume that
when I criticize C++, it is because either
(1) it is only because C++ is popular.
or
(2) I have a vested interest in a C++ not being popular.
Especially when the person making that suggestion happens to
have a vested interest in C++ being popular and staying popular.
In fact, I do have an interest in Java, but only since the beginning
of this year; before that I worked in C++, C, C*, and various
assembly languages. I haven't had a financial interest in Modula-3's
success since early 1990. I've being criticizing C++ in some form or
another for a long time now, though I have tried to keep it in
the form of constructive criticism (for example, in 1990, I commented
on how C++ was choosing the "wrong" model for its exceptions, and
pointed out how at least one other language had started out that
way, and changed, after actually studying a body of code, and modifying
the compiler to change the default. Very recently, I pointed out that
I thought the standard really ought to decide what division and
remainder
mean in the presence of negative integers, especially since it looks
like, in fact, the whole world agrees already). I've griped about
STL, but I've at least tried to explain why (I think that the use of
pointers into the middle of arrays is a bad idea, because of the way it
complicates analysis, garbage collection, serialization, runtime
checking,
and parallelization. Promoting the syntax promotes the practice.)
But, you can see, I have reasons, and some of them ought to find
some sympathy within the C++ community (Fortran programs are often
vectorized, loop-interchanged, or parallelized, all by the compiler,
sometimes with integer factor speedups -- some C++ compilers may be
doing that now, but I first heard of a workstation Fortran compiler
doing this in late 1993).
I've also tried to say good things about the languages that contain
features that seem to make people (those people who have tried
two languages, so that they could actually make a comparison) more
productive. Garbage collection is a very good thing. Static checking,
where possible, is a very good thing. Having a proper array type,
that gets its bounds checked at each reference, is a very good thing.
Having a type system about which people can reason and write theorems
is another good thing; it allows you to write things like Modula-3's
network objects, which, I am told, is the "killer app" for anyone
who needs to write a distributed application, and actually gets around
to
giving them a serious try (typically after having tried to get the
job first with CORBA, and failing). Having something as mundane
as an easily parsed language, so that you can write tools for it
without spending dozens of thousands of dollars just for the parser,
is a good thing. Having a proper separation between interface files
and implementation files, is another good thing.
These are all things (except for static checking) that C++ lacks. C++
is incredibly complex; I have over 15 years of experience (24, if you
count the first tic-tac-toe game), writing everything from vectorizers,
to mostly-lock-free runtime systems, to garbage collectors, to pattern
matchers, to optimizing code generators. I've got my CS PhD, and I've
got my cum laude before that (from a school not known for grade
inflation,
thank you very much), and my team made it into the local school-benefit
spelling bee finals as well. I've got a really good memory for details,
and I can usually handle complexity pretty well, but I find C++ to be
beyond my grasp, despite writing tens of thousands of lines of it, and
reading and debugging hundreds of thousands of lines of it. I've
written incomprehensible code in C++ (usually discovered six months
after the fact) and other people I've worked with have also written
incomprehensible code in C++. Compared to other languages, there
is more of it (it = incomprehensible code), and it is more twisted,
because C++ provides so many exciting ways to write weird code
(templates, default conversions, default parameters, overloading,
copy constructors, and inheritance), plus all the tricks that we
already know and love from C. These features have their uses,
but they have their costs, and after seeing them used in many ways,
I think that the costs outweigh the benefits. In some cases, it is not
so much the feature, as the way the feature is implemented; templates
seem to have grown from a useful idea, into something that is
difficult to implement (at least, it is difficult for the current
crop of C++ compiler writers to implement, given all the bugs
and incompatibilities and weird compiler-specific instantiation
handshakes that I have seen) and sometimes quite difficult to read.
And, even though I have a much larger financial interest in the success
of Java, I wish I were working in Modula-3, and working on Modula-3,
because it is a better language (i.e., experienced programmers are more
productive in it), but Java pays better, and is better (my estimate of
the same metric) than C++, and I have to pay the mortgage. That is why,
before this, I worked on C++. I'm still waiting to hear from someone
who has written more than 10,000 lines of Java, or Eiffel, or Modula-3,
who has also tried C++, and who prefers C++ for any purpose other than
paying the rent or mortgage.
David Chase
M. Prasad
Chris Bitmead uid(x22068) wrote:
[snip]
> C++, although most lispers consider assignment (which swap is a form
> of), unnecessary and bad style.
This is theory (promulgated by advocates of "Functional
Programming",) but in practice, I doubt any large
scale production quality Lisp code exists which does
not use assignment. For large and complicated
multiple-module tasks, it is simply not practical to live
with this rule, though it is good for small textbook
examples. (Of course, I would be very interested in
counter-examples if they exist and comments on how it
was done, what was the experience like...)
David Monniaux
Andrew Koenig (a...@research.att.com) wrote:
: In article <5kq8jp$3...@cri.ens-lyon.fr> dmon...@ens-lyon.fr (David Monniaux) writes:
: I have used ML a good bit, but I would have a very hard time convincing
: my colleagues on the business side of the house to use it, if only
: because the first prerequisite is the widespread availability of a
: commercially supported compiler on each of several platforms and
: corresponding commercial training courses. Plus a significant commercial
: user community -- no one wants to be the first to bet part of their
: business on something.
In a nutshell: ML won't be used commercially because there's no commercial
compiler for it, and surely people won't start making a commercial compiler
for it if nobody uses it in the commercial world.
:-)
The situation may be different here, as Caml has become one of the commonly
taught languages at college level. However, the main problem is that the
industry, as you said, is very conservative, and it takes tons of resources
(think of all the hype Sun had to build around Java, which is not even
"new" technology, since it's basically a scaled-down C++ with a GC) to
have it accept things it is not used to.
However, I can tell you that O'Caml has begun to catch on. It is, for
instance, used to prototype airplane embedded systems (if it is not a
"serious" application, I don't see what is "serious" :-) ).
The question is whether it will remain a teaching language, used only
in niche applications such as prototyping and proofs on safety-critical
systems, or whether it'll come mainstream.
: Incidentally, the ML that I've used has neither inheritance nor
: overloading, nor is it likely to acquire them any time soon.
O'Caml has those but, as I said, few people actually use its OO features.
--
Thant Tessman
David Monniaux wrote:
> In a nutshell: ML won't be used commercially because there's no
> commercial compiler for it, and surely people won't start making
> a commercial compiler for it if nobody uses it in the commercial
> world.
>
> :-)
>
> [...]
Andrew Koenig
> In a nutshell: ML won't be used commercially because there's no commercial
> compiler for it, and surely people won't start making a commercial compiler
> for it if nobody uses it in the commercial world.
> :-)
Absolutely correct, unfortunately.
There is a superb compiler available -- for free -- but its authors
don't seem to be interested in turning it into something that
would be useful for real work. Among the things missing is accurate
documentation of the run-time libraries, a stable way of interfacing
with the underlying operating system, and a way of creating
stand-alone executables without undue space overhead.
The compiler folks could easily solve these problems if they wanted to.
But it doesn't seem to be important to them.
Jeffrey Mark Siskind
To: pra...@polaroid.com
Subject: Re: C++ briar patch (Was: Object IDs are bad)
References: <3364CA...@nospam.acm.org> <E9DAD...@research.att.com>
<3368C7...@nospam.acm.org> <E9J3F...@research.att.com>
<30715635...@naggum.no> <336A4D...@mti.sgi.com>
<slrn5ml08o...@connectnet1.connectnet.com>
<fxtwwpd...@isolde.mti.sgi.com> <336E82...@mti.sgi.com>
<336F59...@nospam.acm.org> <336FDF...@mti.sgi.com>
<s6y7mha...@aalh02.alcatel.com.au> <3371D6...@polaroid.com>
--text follows this line--
"M. Prasad" <pra...@polaroid.com> writes:
> Chris Bitmead uid(x22068) wrote:
>
> [snip]
> > C++, although most lispers consider assignment (which swap is a form
> > of), unnecessary and bad style.
>
> This is theory (promulgated by advocates of "Functional
> Programming",) but in practice, I doubt any large
> scale production quality Lisp code exists which does
> not use assignment. For large and complicated
> multiple-module tasks, it is simply not practical to live
> with this rule, though it is good for small textbook
> examples. (Of course, I would be very interested in
> counter-examples if they exist and comments on how it
> was done, what was the experience like...)
Back in 1981, my colleagues Ken Crouch and Jay Southard and I wrote MacPitts,
a silicon compiler that took behavioural system descriptions as input and
produced full-custom VLSI layouts as output. MacPitts was about 50,000 lines
of Franz-Lisp code. It was written in a purely functional style. On a VAX
11/750, with 8M of memory, running 4.1 BSD, it could compile a four-page
description of a 32-bit microprocessor to a layout with 10,000 transistors, in
about 4 hours.
Jeff (home page http://www.emba.uvm.edu/~qobi)
Lyman S. Taylor
In article <s6y7mha...@aalh02.alcatel.com.au>,
Chris Bitmead uid(x22068) <Chris....@alcatel.com.au> wrote:
>
>I'm not expert in CL, so I havn't really used it's version of
>reduce. I suppose it only works for lists, but there is nothing
Actually it works on any of the "built-in" sequences. But isn't
exactly the epitome generic design either. It's largely crafted to
work well with the math ops and correct input. :-)
The "identity" value must be embedded in the function applied ...
( the STL does decouple these... ) And admittedly some of the
hackery in the string-accum function wouldn't be needed if the
initial accumulation value was the identity value... i.e. application
to a list of 1 is special cased to just return the original single
element, kind of "penny wise and pound foolish". [ only in the
default behaviour though. go figure.. ]
(defun integer-accum (&rest args )
"add up the value of the numeric values of the arguments."
(print args )
(if args
(+ (first args ) (second args ))
0))
(defun string-accum (&rest args )
"add up the value of the integer values of the arguments.
NOTE: The first pair will be two characters. After that it will be
the sum so far and character."
(print args )
(if args
(+ (if (typep (first args ) 'number)
(first args)
(char-int (first args)))
(char-int (second args)))
0))
(reduce #'integer-accum '( 1 2 3 4)) ==> 10 ;; list of ints
(reduce #'integer-accum '() ==> 0
(reduce #'integer-accum '#(1 2 3 4)) ==> 10 ;; vector of ints
(reduce #'string-accum "defh") ==> 510 ;; a string
(reduce #'string-accum "") ==> 0 ;; the empty string
;; dubious examples
(reduce #'+ '( "hello world" )) ==> "hello world"
(reduce #'string-accum "a" ) ==> #\a
(reduce #'string-acum "a" :intial-value 0 ) ==> 97
http://www.harlequin.com/books/HyperSpec/Body/fun_reduce.html#reduce
[although, all the examples in the above use lists... ditto on Steele's CLtL2]
Alexander Stepanov
Eli Barzilay wrote:
>
> Whow, man - now you got me - please don't insult Lisp if you havn't
> used it (and reading your mail I see that you DON'T know it too good).
>
This seems to be a common sentiment. I keep getting little Lisp, Scheme,
and SML programs showing my amazing ignorance.
It is, however, unlikely to effect me. You see, I tried. I used
Symbolics, I used Common Lisp, I taught a course on implementing Common
Lisp. I implemented THE LOOP macro. (As a matter of fact, I probably
impemented every single macro in Common Lisp - I am looking for my
lecture notes from my CL class, but cannot find them yet.) I know what
locatives were. I do know about SETF. I read the lambda papers in the
seventies. I read a very large portion of MIT Scheme code - and forced
many innocent students to do the same. (As a matter of fact, my last
large project in Scheme - a VLIW simulator - was done in 1994.) While I
never seriously programmed in ML, I did seriously read one ML book and
many ML papers. One possible explanation is that I am just stupid and
cannot appreciate the thing of beauty.
If you are satisfied with this explanation, STOP READING NOW, and,
please, please, do not send me mail expressing you opinion about my
mental abilities and moral qualities of my ancestors.
There some of you, who express genuine interest and I would try to
explain some of my points. What follows is a sort of an Apologia pro
vita sua. It is rumbling and unclear, but it is difficult to explain the
motivations of a lifetime of research, especially when one is lead to
conclusions contrary to the accepted academic wisdom.
I started working on what I now call generic programming in the mid
seventies. I was thinking about parallelizing transformations of simple
loops, summation for example. a + (b + (c + d)) = (a + b) + (c + d). I
noticed that this transformation depended on the associativity of +. I
concluded that this transformation is affiliated with an algebraic
theory of semigroups. The natural conclusion was that it is important to
be able to express in the programming language tha fact that certain
operations are associative. While it is true that any reasonable
compiler knows about associativity of + for built-in types, it is
impossible to inform it that other operations, say max, are associative,
and it is impossible to express properties of even + for non-built in
types, quaternions for example. At the same time I noticed that
transforming sequential reduction to parallel reduction makes sense even
for sequential computations. For example, it is always better to merge
four lists of the same size with the parallel reduction than with the
left-most reduction. And then, to my great surprise, I realized that
while it is true for merge, it is not true in general. For example,
parallel reduction does not help at all if you multiply many polynomials
After a while, I discovered that the same operations benefit from
parallel reduction as benefit from Russian peasant algorithm for power
and the other way around. Both reduction and power are associated with
the same theory of monoids and the algorithmic selection for both
depends on complexity properties of the monoid operation. It took me a
while to realize that the property in question is a simple bilinear
inequality for the cost function.
So by 1980, I realized that there is a natural way to describe
algorithms in terms of multisorted algebras with complexity requirements
associated with them. One of the difficulties of explaining what I
wanted to do to other people was the fact that algorithms people did not
want to hear about multisorted algebras, multisorted algebras people did
not want to hear about adding non-algebraic complexity axioms and
clearly wanted to leave Russian peasant algorithms to Russian peasants.
(As one of my good friends, who is a very multisorted person, says, -
Knuth is just hacking.)
When John Backus made his famous Turing award speech, I saw the light. I
decided that I had to combine my ideas about associating operations with
semantical and complexity properties with FFP. I realized that Backus
was somewhat mistaken when he tried to restrict the number of functional
forms, but I tried to express a large body of algorithms in FFP-like
form. I spent several years trying to represent heaps, or to do Prim's
algorithm in a functional way. At some point it became clear to me that
I was doing something quite silly. I saw that addresses were good. There
are different theories of address operations that allow me to group
algorithms together and express them in the most abstract form. I saw
that data structures are models of different address algebras. I saw
that I can use morphisms of these address operations as a way to provide
an encapsulation of different traversal methods. I would say that by
1984 I had a fairly good idea of the taxonomy of different software
components. The only thing that I needed was a programming language to
express my ideas.
Let us see what I wanted to say. I wanted a language that would allow me
to write programs in terms of what I call a concept. There are two ways
of describing what a concept is. First, model theoretic, namely, a
concept is a set of types with similar interfaces. (The notion of
"similar" is actually quite lax. It is a free combination of structural
and named equivalence for signature groups.) Second, proof theoretic
(or, more exactly, code theoretic), a concept is a collection of all the
valid and efficient programs written in terms of it.
I needed types to hang semantical and complexity information onto. I
needed overloading, to be able to use different algorithms on different
subtheories. I became more and more convinced that an address is a
fundamental component kind. I found Lisp more and more inadequate from a
very metaphysical point of view. It equates an object and its address. I
wanted to be able to talk about address as quite different than the
object it names. ( I knew that: "A name means an object. The object is
its meaning." Wittgenstein, Tractatus 3.203, but I wanted "meaning",
"denotation" to be an explicit function since I wanted to define it
differently for different models of the same address concept.) I also
came to the realization that I wanted a language with copy and equality
defined quite differently from Lisp. That is, I realized that I could
build a very useful theory of containers (data strucutres with
ownership) based on a philosophically sound notion of whole and part;
something along the lines of:
1.If two objects share a part, then one object is a part of the other
(no sharing, objects are disjoint).
2. No circularity among objects - an object cannot be a part of itself
and, therefore, cannot be part of any of its parts.
3. When an object is destroyed all its parts are destroyed.
4. Two objects are equal iff their essential parts are equal.
And then in 1987 I discovered C. That is, I discovered C++, but the part
that I was really impressed was C. C treatment of pointers and the
semantics of built-in types were much closer to my theory than anything
I have seen before. There were some big disappointments - the language
did not provide == operator for structs and my theory demanded that
T x = y; assert(x == y);
Unfortunately, at that point C++ was not at all usable. It took me
several years to discover the reasons why I could not use inheritance.
But I got really impressed with the underlying C machine and with the
way Bjarne added function and operator overloading, and with the notions
of copy constructor and desctructor. (I do not, of course, like the fact
that they are member functions. I could do really better things if they
could be globally defined and templatized.)
And then Bjarne added templates. I was quite astonsihed with what I
could do with them. I could express very complex relations between
concepts, I could carry a lot of information with types. Aren't C++
templates just glorified macros? I do not thing so. I think that they
are very powerful type generating mechanisms. The ability to nest
templates together with partial specialization allowed me to express a
complex relations between types.
Is C++ pefect for generic programming? No. After all, the central things
for this style of programming is a notion of concept. Things like input
iterator. You cannot express them in C++. STL relies very havily on
extra-linguistic specifications. While I do like C model of memory very
much, it is too specific. I do believe that parameterization by memory
models, different pointer types if you like, is very important. There
are hundreds of little glitches. But it is much better than anything
else I know of for expressing what I have been trying to express.
Erik Naggum
* David Monniaux
| In a nutshell: ML won't be used commercially because there's no
| commercial compiler for it, and surely people won't start making a
| commercial compiler for it if nobody uses it in the commercial world.
| :-)
* Andrew Koenig
| Absolutely correct, unfortunately.
The Harlequin Group made MLWorks available for beta testing last fall. the
beta license expired 1997-01-01, after which I received a questionnaire and
some notes on how to get the commercial product. I elected not to buy it.
well over 100 people got a copy of this product (and some of the mailings,
hence I know the numbers).
take a look at <URL:http://www.harlequin.com/full/products/sp/mlworks.html>
you can even download an evaluation version. yes, this products exists is
available on a large number of platforms.
I hope you're better informed in other cases where you use "absolutely
correct" about something, Andrew.
#\Erik
--
if we work harder, will obsolescence be farther ahead or closer?
Daniel Wang
>>>>> "David" == David Monniaux <dmon...@ens-lyon.fr> writes:
David> In a nutshell: ML won't be used commercially because there's no
David> commercial compiler for it, and surely people won't start making
David> a commercial compiler for it if nobody uses it in the commercial
David> world. :-)
Alexander Stepanov
M. Prasad wrote:
>
> Alexander Stepanov wrote:
> >
> > Eli Barzilay wrote:
> > >
> > > Whow, man - now you got me - please don't insult Lisp if you havn't
> > > used it (and reading your mail I see that you DON'T know it too good).
> > >
> >
> > This seems to be a common sentiment. I keep getting little Lisp, Scheme,
> > and SML programs showing my amazing ignorance.
> >
>
>
> I see from one of your earlier messages that
> you were also disappointed with CLU. Did you
> find the template features in CLU inadquate,
> or was it the treatment of object equality/similarity?
You got it just right. CLU has Ada like genericity. You have to
do explicit instantiation. But the second one is much more
important. CLU has a Lisp-like machine model. (See my recent
post in comp.lang.scheme where I tried to explain the machine
model aspects of why I stopped using Lisp.)
> One would think the built-in iterator concepts would
> make generic programming for data structures easier?
No. You see, iterators in STL are a much more elaborate
things than iterators in CLU or series in Common Lisp.
It did take me a long time to figure out a semantic
difference between input iterators and forward iterators,
and to see the algorithmic classes that require one or the
other. (One-pass, one-direcitonal vs. Multi-pass,
one-direcitonal.) But I did learn a from CLU. It helped me to
realize the importance of types. I am also indebted to Barbara
for the initial explanation why inheritance is weaker than
genericity. My understanding did develop since that time (1987,
if I remember correctly), but she did a remarkable job,
explaining it to me while riding in a car from Newark airport to
Bell Labs. Her explanation did save me years.
I did learn from OBJ work of Goguen and Meseguer. But I
couldn't do STL in OBJ 3 or FOOPS or MOD.
The only language from which I did not learn anything is Java. I
spent 6 months writing code in it and came back empty handed.
Again, I am not saying that there is nothing marvelous in Java,
but only that I personally did not get any insights. I clearly
failed in my task to do STL in Java, but you should realize that
there are at least 3 different implementations of STL in Java,
and one of them (JGL) is, I was told, shipped with Microsoft
Java product. So, when I say that it is not possible, I clearly
have different criteria than Microsoft. The same is true in
Scheme. There are pieces of code in STL which are just
translations of my very old Scheme code. And I could clearly
translate the entire STL into Scheme - after all, I did build
an architecture simulator in Scheme and if I can simulate a
modern VLIW computer, I clearly can simulate an abstract C
machine.
So, restating my point again, I was looking for a certain
abstract machine model. The model for which I had been looking
happened to be an abstraction of an existing C/C++ machine model
and quite different from Lisp/CLU machine model. When I found
it, I was exceedingly happy. That is, I was not starting from
C++, but from some rather philosophical set of requirements.
(As an amusing aside: my project on generic programming at
General Electric Research was terminated after a new lab manager
attended my talk on logic of whole/parts; he put it quite
nicely: General Electric does not need philosophers.)
> Did this turn out not to be the case in your
> experimentation?
Richard A. O'Keefe
>* David Monniaux
>| In a nutshell: ML won't be used commercially because there's no
>* Andrew Koenig
>| Absolutely correct, unfortunately.
Erik Naggum <er...@naggum.no> writes:
>The Harlequin Group made MLWorks available for beta testing last fall.
It's also worth noting that the Poplog system (Common Lisp, Prolog, Pop-11,
powerful editor VED, more documentation than a strong man can lift ...)
has included ML for several years. I had a student who was using it
several years back. It worked pretty well. All the Poplog languages
interoperate quite smoothly, and you have been able to mix in dynamically
loaded C, Fortran, &c since the earliest days.