Generic Programming
alex...@gmail.com
Before implementing STL, Alex Stepanov was a Schemer. In his
interviews, he stated that he found only one language in which he could
express his ideas.
Most people, especially those with less than expert knowledge of C++,
don't realize it, but the main idea of STL is *not* to provide a bunch
of container classes with useful methods.
While this is certainly how STL is most often used, its big idea is to
separate data structures and algorithms. Imagine 10 algorithms that
work on 10 data structures. Using the right abstractions over the data
structures (iterators), we only have to describe each of the algorithms
once instead of 10 times.
Stepanov stated that he looked at a lot of languages, including ML and,
of course Scheme, studying each for at least a year, but found them
lacking until he learned C++.
Stepanov is probably smarter than 99.9% of "guys on USENET", so his
words should not be taken lightly. Can "STL" be done in ML or Lisp? Has
it?
O'Caml standard library and ExtLib are certainly not the right
examples. They just provide a collection of data structures with
specific algorithms, not a framework for writing structure-independent
algorithms.
O'Caml graph library, on the other hand, attempts to separate data
structures and algorithms, but it looks like they run into the
limitations of the O'Caml type system, and sometimes have to settle for
suboptimal solutions (Search their documentation for 'limitation' and
read the FAQ, if interested)
It is my understanding that even if it hadn't been for the type system
limitations in ML, users would be stuck with doing "module arithmetic"
to achieve STL-like functionality, whereas C++ programmers can
basically state what they mean.
As to Lisp, personally, I don't see why a very slow (run-time
genericity) STL-like library can not be written using CLOS for example.
But the fact is that it hasn't.
Here are the interviews, by the way. Don't design yet another
programming language, until you've read them! Not only he bashes
"lesser" languages, takes shots at garbage collection, but also he
decries OOP in general.
http://www.stlport.org/resources/StepanovUSA.html
http://www.sgi.com/tech/stl/drdobbs-interview.html
netytan
languages and promote C++ ;).
I have no doubt that such a system could be made in Lisp/Scheme (likely
with Macros?) however there's no good reason too IMO due to the
flexibility of Lisp/Scheme's type system.
Common Lisp already includes a large number of generic functions for
interacting with the various collections etc.
Templates are a response to the rigidness of C++ and a really horrible
tool to work with, and I have.
The idea of having templates itself isn't too bad but the way in which
they are done in C++ is ugly to say the least.
It reads like yet another language layer added onto C along with the
preprocessor and appears as one of a collection of hacks over C.
You can do things in Lisp/Scheme that you cant in C++, or as easily.
Arguing that C++ is thus a more powerful language seems insane to me
and likely to others.
Maybe I've misunderstood, but the answer to your question: yes :)
Mark.
netytan
the best or anything like that but because of the paradigms they
introduce.
Thanks,
Mark.
Dave Benjamin
> O'Caml standard library and ExtLib are certainly not the right
> examples. They just provide a collection of data structures with
> specific algorithms, not a framework for writing structure-independent
> algorithms.
Why so quick to discount Extlib? It seems to me that its "Enum" type
provides exactly what you describe:
http://ocaml-lib.sourceforge.net/doc/Enum.html
Granted, it's only a specific type of iterator, and the STL goes quite a
bit further in the specific kinds of iteration, data structures, and
algorithms it can generalize. Still, as long as every module supports a
common interface (and this is as much a social problem as a technical
one), data structures and algorithms can certainly be made interchangeable
and pluggable in ML.
--
.:[ dave benjamin: ramen/[spoomusic.com] ]:.
Bruce Hoult
alex...@gmail.com wrote:
> While this is certainly how STL is most often used, its big idea is to
> separate data structures and algorithms. Imagine 10 algorithms that
> work on 10 data structures. Using the right abstractions over the data
> structures (iterators), we only have to describe each of the algorithms
> once instead of 10 times.
Dylan does that. Data structures define an appropriate "protocol", and
algorithms use the protocol.
For example, collections define "forward-iteration-protocol", which is a
generic function that returns a number of values and functions, which
are then used by algorithms such as empty?, map, choose, and the "for"
loop.
As another example, hash tables define "table-protocol", which returns a
method for calculating a hash code and a method for testing values for
equivilence.
This could be slow, but in practice when a Dylan compiler (e.g. Gwydion
d2c) knows the type of a collection, the call to
"forward-iteration-protocol" has the exact method selected at compile
time, and it is inlined, and the functions that are returned are also
inlined. So you can just write "for (e in myCollection) ... end" and
you automatically get optimal code no matter whether myCollection is a
list or a string or a vector or whatever.
--
Bruce | 41.1670S | \ spoken | -+-
Hoult | 174.8263E | /\ here. | ----------O----------
alex...@gmail.com
There are several issues that will get in its (ML's and ExtLib's in
particular) way, even if it works around the "social" problem you
mention (I'm not stating that Enum's notion of iterators is sound, btw)
In the order of importance:
* Type system. Same as with graphs [1]. C++ doesn't have this problem.
I can create my own 5-parameter container template, and just apply
std::sort to it. There are probably other type system gotchas besides
this one in ML.
* Speed. O'Caml simply won't optimize STL'ish polymorphic code the way
C++ compilers are expected to optimize proxy objects (iterators). If
only MLton hackers wasted their time on OCaml instead of SML! :-)
* Syntax. Functor syntax is required. The user can't just say:
sort i1 i2 (* sort all elements between these two iterators *)
He has to say
module V = ....
module S = SortSequence(V)
S.sort i1 i2
[1] Copied from OCamlGraph FAQ:
Q: I have a graph implementation with polymorphic types for vertices or
edges and thus I can't apply the algorithms functors
A: Here we bump into ocaml's type system limitations: the number of
type parameters must be know when the functor is written and the
simplest choice for us was to assume no type parameter at all. (This is
exactly the same for functors Set.Make or Map.Make from ocaml standard
library.) As a (bad) workaround, you can copy the functor body and
substitute your own functions for the functor arguments.
bunn...@gmail.com
> Stepanov is probably smarter than 99.9% of "guys on USENET", so his
> words should not be taken lightly. Can "STL" be done in ML or Lisp? Has
> it?
>
I don't know if this is what you think of, but something that comes
"close" to an STL like paradigm is
http://www.malgil.com/esl/ftl.html
Very interesting, and somewhat weird, but worth looking at, even if
it's
just for the approach taken...
cheers,
felix
Greg Buchholz
> Is "STL" possible in ML and Lisp?
It is possible in Haskell, but it seems like the idea really hasn't
caught on. I think the main thing holding it back in languages like
Haskell and ML are their use of pattern matching for destructuring
collections. Views ( http://www.haskell.org/development/views.html )
are supposed to cure the problem, but they apparently never caught on.
See also the following for related topics...
An Overview of Edison...
http://citeseer.ist.psu.edu/okasaki00overview.html
Edison's main page...
http://www.haskell.org/ghc/docs/edison/
Algebraic Abstract Data Structures...
http://66.102.7.104/search?q=cache:TJvTnpY2PuoJ:www.stud.tu-ilmenau.de/~robertw/dessy/fun/
Greg Buchholz
Algebraic Collections: A Standard for Functional Data Structures
http://www.google.com/search?q=cache:7Jr20jK3_zYJ:www.stud.tu-ilmenau.de/~robertw/dessy/fun/+dessy+haskell&hl=en
Philippa Cowderoy
> alex...@gmail.com wrote:
> > Is "STL" possible in ML and Lisp?
>
> It is possible in Haskell, but it seems like the idea really hasn't
> caught on. I think the main thing holding it back in languages like
> Haskell and ML are their use of pattern matching for destructuring
> collections. Views ( http://www.haskell.org/development/views.html )
> are supposed to cure the problem, but they apparently never caught on.
I suspect the reason for this is the results in this paper:
http://research.microsoft.com/Users/simonpj/Papers/pat.htm
In short, it turns out to seem more sensible to just provide sugar for
shoving values through a function before matching. I'm not sure why
transformational patterns were never implemented in GHC though.
A problem that's all in your head is still a problem.
Brain damage is but one form of mind damage.
Thant Tessman
> Is "STL" possible in ML and Lisp?
http://makeashorterlink.com/?W1FC2397C
[...]
-thant
--
Socialism, like the ancient ideas from which it springs, confuses the
distinction between government and society. As a result of this, every
time we object to a thing being done by government, the socialists
conclude that we object to its being done at all. -- Frédéric Bastiat
alex...@gmail.com
> alex...@gmail.com wrote:
> > Is "STL" possible in ML and Lisp?
>
> http://makeashorterlink.com/?W1FC2397C
>
> Alexander Stepanov was making about C++ being the only
> language that supported the kind of generic programming he
> wanted to do.
I'm afraid your example there does not refute Stepanov's claims.
> [...]
If you read [...], or this follow-up by Andreas Rossberg in the thread
you are linking
http://groups.google.com/group/comp.lang.ml/msg/64ac56f5985fb52a, or my
other message in this thread, I think you'll see why.
But I'll try to explain it again anyway. In your example, you provide
algorithms that work on polymorphic data structures with a single
parameter. I can't use your algorithm on my data structures that either
aren't polymorphic or take two parameters (like map, multimap, etc.)
Thant Tessman
> Thant Tessman wrote:
>
>>alex...@gmail.com wrote:
>>
>>>Is "STL" possible in ML and Lisp?
>>
>>http://makeashorterlink.com/?W1FC2397C
>>
>>QUOTE: I wrote it many years ago only to refute some claims
>>Alexander Stepanov was making about C++ being the only
>>language that supported the kind of generic programming he
>>wanted to do.
>
>
> I'm afraid your example there does not refute Stepanov's claims. [...]
Can you be more specific? C++ templates *are* more expressive than SML's
modules, but SML's modules are definitely capable of doing what Stepanov
claimed only C++ allowed him to do (at least in the original thread that
goaded me into implementing the example I provided).
And it should be pointed out that all this is only a big deal in the
context of strong typing.
-thant
--
Gold: monetary unit of the peaceable kingdom. Dollah: toilet paper of
the war whores. -- machinehead
alex...@gmail.com
> alex...@gmail.com wrote:
> > Thant Tessman wrote:
> >
> >>alex...@gmail.com wrote:
> >>
> >>>Is "STL" possible in ML and Lisp?
> >>
> >>http://makeashorterlink.com/?W1FC2397C
> >>
> >>QUOTE: I wrote it many years ago only to refute some claims
> >>Alexander Stepanov was making about C++ being the only
> >>language that supported the kind of generic programming he
> >>wanted to do.
> >
> >
> > I'm afraid your example there does not refute Stepanov's claims. [...]
>
> Can you be more specific? C++ templates *are* more expressive than SML's
> modules, but SML's modules are definitely capable of doing what Stepanov
> claimed only C++ allowed him to do (at least in the original thread that
> goaded me into implementing the example I provided).
Never mind, I see you won that argument against the great Stepanov back
in 1997 anyways :-)
http://groups.google.com/group/comp.lang.functional/msg/11af16e20b3b9424
I'm not saying that language X is better than Y, just that you have not
refuted his claim that ML wasn't suitable for implementing STL, because
your example fell short.
Using the C++ lingo, your generic functions will not work on containers
of "genericity arity" different from 1. For example, they will not work
on non-template containers, or container classes whose definitions
begin with
template<class T, class R, class S> // "genericity arity" = 3
It's been discussed many times. Pick one:
http://groups.google.com/group/comp.lang.ml/msg/64ac56f5985fb52a
(Andreas)
http://groups.google.com/group/comp.lang.functional/msg/d22bb77058438df0
(me)
http://www.lri.fr/~filliatr/ocamlgraph/FAQ (last FAQ in OcamlGraph)
I see no point in copy-pasting the same arguments
> And it should be pointed out that all this is only a big deal in the
> context of strong typing.
Right, one could probably create an STL-like library using CLOS (slow
run-time genericity), as I mentioned in the very first message of this
thread, but as far as it's been established, only C++ satisfies all
three of the desired properties
1. Compile-time genericity
2. Mutable data structures
3. Sufficient genericity
* Comon Lisp CLOS satisfies 2 and 3 (slow runtime dispatch, *very* slow
in practice)
* AFAIK Haskell satisfies 1 and 3 (slow, incorrect asymptotic
complexity when working with graphs, actually - Stepanov talked about
it in his interviews, which I referenced)
* ML satisfies 1 and 2 (not generic enough for STL - the claim you
claimed to have refuted)
P.S. Jeremy Siek, to whom you tried to pitch your flawed proof, went on
to create Boost Graph Library (with co-authors), where many algorithms
work on many graph representations. It's interesting to compare BGL to
OCamlGraph.
Paul Rubin
> * Comon Lisp CLOS satisfies 2 and 3 (slow runtime dispatch, *very* slow
> in practice)
>
> * AFAIK Haskell satisfies 1 and 3 (slow, incorrect asymptotic
> complexity when working with graphs, actually - Stepanov talked about
> it in his interviews, which I referenced)
>
> * ML satisfies 1 and 2 (not generic enough for STL - the claim you
> claimed to have refuted)
Does STL do this stuff at the expense of exponential code bloat?
ajk...@gmail.com
various languages (Jeremy Siek is one of the authors). See
http://www.osl.iu.edu/publications/prints/2003/comparing_generic_programming03.pdf
That paper ignores the issue of performance. At the time that STL was
designed, the performance of ML compilers didn't match C++ templates,
as polymorphism of all kinds (core, module, functor) was typically
compiled using uniform representations (no specialization), in order to
achieve "separate compilation". But I think MLton has since proved that
ML (at least, SML) can match C++.
- Andrew.
Thant Tessman
[...]
> Using the C++ lingo, your generic functions will not work on containers
> of "genericity arity" different from 1. For example, they will not work
> on non-template containers, or container classes whose definitions
> begin with
>
> template<class T, class R, class S> // "genericity arity" = 3
>
> It's been discussed many times. Pick one:
>
> http://groups.google.com/group/comp.lang.ml/msg/64ac56f5985fb52a
> (Andreas)
>
> http://groups.google.com/group/comp.lang.functional/msg/d22bb77058438df0
> (me)
>
> http://www.lri.fr/~filliatr/ocamlgraph/FAQ (last FAQ in OcamlGraph)
>
> I see no point in copy-pasting the same arguments [...]
I know nothing about Ocaml, but I read the first two the first time you
referenced them. I don't understand the point you're trying to make with
them. That's why I asked you to be more specific. It's been a while
since I played around with SML, but my memory is that you're certainly
free to describe a datastructure with more than one free type variable
(i.e. a "genericity arity" of greater than one).
C++'s templates allow for specialization on type and even integers. But
beside that, as far as I can tell, C++'s templates and SML's modules are
equivalent in expressive power. The main difference is that SML requires
that the interface be explicitly spelled out, whereas C++'s templates
sort of infer the interface as they are instantiated. (Note that even
some C++ advocates argue that this is a *flaw* with C++'s templates. I'm
agnostic on the issue.)
As for instantiation itself, in the case of SML, whether a module is
optimized on a per-type basis is entirely implementation-dependent. (But
it is my understanding that an SML compiler must see the whole program
to make those kinds of optimizations. MLton is just such a compiler.)
> P.S. Jeremy Siek, to whom you tried to pitch your flawed proof, went on
> to create Boost Graph Library (with co-authors), where many algorithms
> work on many graph representations. It's interesting to compare BGL to
> OCamlGraph.
I'm sure the BGL is an impressive piece of work, but as I tried to point
out in the thread I referenced, in SML (or indeed any language with
genuine support for higher-order functions), it's just not as herculean
a task as it is in C++ to get many algorithms to play nice with many
data structures. Consequently, that's usually not the main focus of a
library.
As for "The Great Stepanov," I was probably not as polite as I should
have been. And I will eagerly repeat that the STL is a thing of beauty
in its context. Heck, I use it every day. But I still defend my claim
that C++ has been a *huge* misallocation of resources. (I'm no expert,
but first evidence is that XML might be even worse in that department.)
-thant
--
"That's not a good way to determine how good or bad things are, by
how many things are exploding." -- Lawrence DiRita, chief spokesman
for the United States Defense Department
Thant Tessman
>> P.S. Jeremy Siek, to whom you tried to pitch your flawed proof, went on
>> to create Boost Graph Library (with co-authors), where many algorithms
>> work on many graph representations. It's interesting to compare BGL to
>> OCamlGraph.
>
>
> I'm sure the BGL is an impressive piece of work, but as I tried to point
> out in the thread I referenced, in SML (or indeed any language with
> genuine support for higher-order functions), it's just not as herculean
> a task as it is in C++ to get many algorithms to play nice with many
> data structures. Consequently, that's usually not the main focus of a
> library.
Wow, that's a coincidence. If you haven't already, check out a paper
referenced earlier in the thread by ajkenn:
http://www.osl.iu.edu/publications/prints/2003/comparing_generic_programming03.pdf
In it, Jeremy Siek among others implement the Boost Graph Library in
several languages to identify the features they consider important to
the support of generic programming as defined by Stepanov et al.
-thant
--
The nationalist not only does not disapprove of atrocities
committed by his own side, but he has a remarkable capacity
for not even hearing about them. -- George Orwell
Tomasz Zielonka
> Right, one could probably create an STL-like library using CLOS (slow
> run-time genericity), as I mentioned in the very first message of this
> thread, but as far as it's been established, only C++ satisfies all
> three of the desired properties
>
> 1. Compile-time genericity
> 2. Mutable data structures
> 3. Sufficient genericity
> * AFAIK Haskell satisfies 1 and 3 (slow, incorrect asymptotic
> complexity when working with graphs, actually - Stepanov talked about
> it in his interviews, which I referenced)
Modern Haskell (beyond H98) has mutable data structures (arrays,
references (mutable cells)). Can we agree now that it satisfies all the
desired properties?
BTW, could you point me to a place where Stepanov talked about Haskell?
I couldn't find it.
Best regards
Tomasz
--
I am searching for programmers who are good at least in
(Haskell || ML) && (Linux || FreeBSD || math)
for work in Warsaw, Poland
alex...@gmail.com
> alex...@gmail.com wrote:
> > Right, one could probably create an STL-like library using CLOS (slow
> > run-time genericity), as I mentioned in the very first message of this
> > thread, but as far as it's been established, only C++ satisfies all
> > three of the desired properties
> >
> > 1. Compile-time genericity
> > 2. Mutable data structures
> > 3. Sufficient genericity
>
> > * AFAIK Haskell satisfies 1 and 3 (slow, incorrect asymptotic
> > complexity when working with graphs, actually - Stepanov talked about
> > it in his interviews, which I referenced)
>
> Modern Haskell (beyond H98) has mutable data structures (arrays,
> references (mutable cells)). Can we agree now that it satisfies all the
> desired properties?
>
> BTW, could you point me to a place where Stepanov talked about Haskell?
> I couldn't find it.
>
He talked about pure functional programming in general
"There were some interesting ideas, but the research didn't lead to
practical results because Tecton was functional. We believed Backus's
idea that we should liberate programming from the von Neumann style,
and we didn't want to have side effects. That limited our ability to
handle very many algorithms that require the notion of state and side
effects.
[snip]
Network algorithms were the primary target. Later Dave Musser, who was
still at GE Research, joined us, and we developed even more components,
a fairly large library. The library was used at the university by
graduate students, but was never used commercially. I realized during
this activity that side effects are important, because you cannot
really do graph operations without side effects. You cannot replicate a
graph every time you want to modify a vertex. Therefore, the insight at
that time was that you can combine high order techniques when building
generic algorithms with disciplined use of side effects. Side effects
are not necessarily bad; they are bad only when they are misused."
Jon Harrop
> * Type system. Same as with graphs [1]. C++ doesn't have this problem.
> I can create my own 5-parameter container template, and just apply
> std::sort to it. There are probably other type system gotchas besides
> this one in ML.
Is this a fundamental type-system gotcha or is this simply a consequence of
the authors choosing to use functors?
> * Speed. O'Caml simply won't optimize STL'ish polymorphic code the way
> C++ compilers are expected to optimize proxy objects (iterators). If
> only MLton hackers wasted their time on OCaml instead of SML! :-)
Yes. However, there is a trade-off between compile- and run-time here. OCaml
will compile such programs vastly more quickly than g++, MLton etc.
> * Syntax. Functor syntax is required. The user can't just say:
>
> sort i1 i2 (* sort all elements between these two iterators *)
>
> He has to say
>
> module V = ....
> module S = SortSequence(V)
> S.sort i1 i2
This begs the question: is that useful?
I've never wanted to use a generic algorithm to sort a subsequence of a
container. I've sorted arrays using one algorithm, lists using another
algorithm and I've used balanced binary trees that maintain their own
ordering. As there is no commonality, there is nothing to factor out.
In practice, I found the STL to be indispensable when I was programming in
C++. Since migrating to OCaml, I have not missed the STL. The functionality
provided by the STL that I used to use is provided more simply and more
effectively in OCaml.
In particular, the well-designed static checking provided by ML (including
OCaml) when using functors is vastly more productive that the reams of
irrelevant errors and code sited given in the error messages of many STL
errors.
Perhaps more importantly, I have found that although the STL's design goes
some way to circumventing the lack of closures in C++, it does so at the
expense of require larger amounts of more error-prone code.
Overall, I don't miss templates and I don't miss the STL.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html
Tomasz Zielonka
> Tomasz Zielonka wrote:
>> alex...@gmail.com wrote:
>> > * AFAIK Haskell satisfies 1 and 3 (slow, incorrect asymptotic
>> > complexity when working with graphs, actually - Stepanov talked about
>> > it in his interviews, which I referenced)
>>
>> Modern Haskell (beyond H98) has mutable data structures (arrays,
>> references (mutable cells)). Can we agree now that it satisfies all the
>> desired properties?
>>
>> BTW, could you point me to a place where Stepanov talked about Haskell?
>> I couldn't find it.
>
> He talked about pure functional programming in general
Let me repeat: Modern Haskell has mutable data structures. You can argue
that with them you are not programming in a purely functional *style*
anymore, but technically the code is still purely functional. But you
were talking about Haskell, not PFPiG, right?
> "There were some interesting ideas, but the research didn't lead to
> practical results because Tecton was functional.
So he says that functional programming languages are not practical. I
think he's wrong. Maybe it was true at that time.
> I realized during this activity that side effects are important,
> because you cannot really do graph operations without side effects.
That's an exaggeration, IMHO.
> You cannot replicate a graph every time you want to modify a vertex.
Even if you are programming in purely functional way, there is no need
to replicate the whole graph. You use persistent data structures where
creating a new structure which differs in one place from the original
has a small cost, usually O(log N) (balanced binary trees for example).
Of course, some operations on this structure will have an additional log
N factor.
> Therefore, the insight at that time was that you can combine high
> order techniques when building generic algorithms with disciplined use
> of side effects. Side effects are not necessarily bad; they are bad
> only when they are misused."
I wonder if side-effects are not misused in STL. Think about
iterator and reference validity, for example. It would be very nice to
have persistent, purely functional data structures in C++.
Luke Meyers
> Does STL do this stuff at the expense of exponential code bloat?
No, because templates are not instantiated unless used. As such, the
code grows linearly with respect to the number of types used to
instantiate each particular template. Which is not appreciably
different than the code size from hand-writing all those
implementations (cf. the (disingenuous) comparison of the template
system to a "fancy preprocessor"). The "code bloat" argument is
spurious unless someone offers the same functionality with appreciably
smaller code.
Luke
alex...@gmail.com
> alex...@gmail.com wrote:
> > Tomasz Zielonka wrote:
> >> alex...@gmail.com wrote:
> >> > * AFAIK Haskell satisfies 1 and 3 (slow, incorrect asymptotic
> >> > complexity when working with graphs, actually - Stepanov talked about
> >> > it in his interviews, which I referenced)
> >>
> >> Modern Haskell (beyond H98) has mutable data structures (arrays,
> >> references (mutable cells)). Can we agree now that it satisfies all the
> >> desired properties?
> >>
> >> BTW, could you point me to a place where Stepanov talked about Haskell?
> >> I couldn't find it.
> >
> > He talked about pure functional programming in general
>
> Let me repeat: Modern Haskell has mutable data structures.
I don't know what Modern Haskell is, frankly. I never heard this term
before. Are you talking about the language as defined by the latest
language report, or are you talking about a specific implementation
(either is fine, but you have to make clear what you are talking about)
If you actually wrote a Graph library in Haskell for others to use,
what would be the signature for functions disconnecting edges, given a
source and a destination vertex, or for changing the 'contents' of a
vertex? What would be the worst-case asymptotic complexity of these
operations?
Tomasz Zielonka
>> Let me repeat: Modern Haskell has mutable data structures.
>
> I don't know what Modern Haskell is, frankly. I never heard this term
> before.
OK, I've made it up (the term). I meant Haskell 98 plus common
extensions, like those implemented in Hugs, GHC, nhc. All of them have
mutable data structures (and are compatible with each other to a big
extent).
> Are you talking about the language as defined by the latest
> language report, or are you talking about a specific implementation
> (either is fine, but you have to make clear what you are talking about)
Not the report, but also not a specific implementation. It's just
the state of the art in Haskell implementations.
> If you actually wrote a Graph library in Haskell for others to use,
> what would be the signature for functions disconnecting edges, given a
> source and a destination vertex, or for changing the 'contents' of a
> vertex?
It depends, there are many choices. In the simplest case they can
be purely functional or imperative (inside IO or (ST s) monad).
But if you tried hard enough, then I think you could create a library
allowing both approaches.
Also, take a look at inductive graph approach taken in FGL - it seems
to achieve good efficiency with a pure interface, probably at the cost
of less operations (like changing the contents of a single vertex).
> What would be the worst-case asymptotic complexity of these
> operations?
Again, if all you care about is asymptotic complexity, you can
get the same as in C. However, many Haskell programmers have greater
care for other things, like convenience, safety, etc.
alex...@gmail.com
is practical, can be quickly foiled by Stepanov's graph argument:
"change this vertex in this graph". If you would trade tangibles for
ideology and style, use Haskell. I don't think there is any more to
discuss here.
Paul Rubin
> Any ideas that pure-functional programming (a raison d'etre of Haskell)
> is practical, can be quickly foiled by Stepanov's graph argument:
> "change this vertex in this graph".
Monads?
Thant Tessman
I'm not an advocate of "pure" functional programming style, but it
should be repeated that changing a node of a graph doesn't necessarily
imply the need to build an entire copy of the graph. So it's hard to
judge Stepanov's objection without more information about what it was he
was actually trying to do.
-thant
--
"Government is a broker in pillage, and every election is sort of an
advance
auction sale of stolen goods." -- H.L. Mencken
Greg Buchholz
http://okmij.org/ftp/Scheme/zipper-in-scheme.txt
Zipper is a very handy data structure that lets us replace an item
deep in a complex data structure, e.g., a tree or a term, without any
mutation. The resulting data structure will share as much of its
components with the old structure as possible. The old data structure
is still available (which can be handy if we wish to 'undo' the
operation later on). Zipper is essentially an `updateable' and yet
pure functional cursor into a data structure.
Jens Axel Søgaard
> Any ideas that pure-functional programming (a raison d'etre of Haskell)
> is practical, can be quickly foiled by Stepanov's graph argument:
> "change this vertex in this graph".
You (or he?) don't consider logarithmic time complexities
practical?
--
Jens Axel Søgaard
Chris F Clark
this graph", and I'm saying that from the perspective of a person who
writes "intermediate language transformers"--that is I write code that
is given a graph as input and is expected to write a modified graph as
output, where certain nodes (veriticies) in the graph have been
replaced with other nodes. Now clearly, as I have phrased the
problem, it involves taking the graph and replacing some verticies
with other verticies.
However, that is just an artifact of one way of looking at the
problem. It is also possible to look at the problem as "construct a
new graph that looks just like this old graph except that in the new
graph you will have the following verticies where the old graph has
these verticies." If you allow the construction to share the
unchanged portions of the graph with the old graph (and make that
occur conveniently and automatically), you have a nice description of
many functional programs.
It is argued that considering the output to be a new graph that is
distinct from the old graph simplifies one's thought processes,
especially if the underlying system takes care of optimizing the
sharing of portions that are redundant. However, one must make the
perspective shift first. If one thinks of the process as editing an
existing structure, it may not be clear to oneself that constructing a
new graph is simpler.
Hope this helps,
-Chris
*****************************************************************************
Chris Clark Internet : com...@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
Philippa Cowderoy
> Tomasz Zielonka wrote:
> > BTW, could you point me to a place where Stepanov talked about Haskell?
> > I couldn't find it.
> >
>
> He talked about pure functional programming in general
>
He didn't, however, talk about the monadic style in which the purity of
the underlying language is used to allow control over the use and
propagation of side-effects - something which a lot of Haskell programmers
are now using.
"My religion says so" explains your beliefs. But it doesn't explain
why I should hold them as well, let alone be restricted by them.
Philippa Cowderoy
> I don't know what Modern Haskell is, frankly. I never heard this term
> before. Are you talking about the language as defined by the latest
> language report, or are you talking about a specific implementation
> (either is fine, but you have to make clear what you are talking about)
>
It sounds a lot like "those features supported by both GHC and Hugs".
Andreas Rossberg
If so then that's not because you made a valid point, but because you
seem to prefer jumping into conclusions. (I don't know whether Stepanov
tried to make the same argument or you just misinterpreted him.)
To clarify: it's perfectly possible (and not particularly hard) to
implement pure graphs with logarithmic vertex and edge insertion and
removal. Hint: adjacency maps. For more special cases (e.g. with an
upper bound on the number of outgoing edges per node) you should even be
able to achieve amortized constant time using extensible arrays.
--
Andreas Rossberg, ross...@ps.uni-sb.de
Let's get rid of those possible thingies! -- TB
Brian Hurt
probably I'm not adding anything new. But I thought I'd throw in my two
cents worth anyways.
alex...@gmail.com writes:
>Is "STL" possible in ML and Lisp?
To the extent it is possible to write it in C++, yes.
>Most people, especially those with less than expert knowledge of C++,
>don't realize it, but the main idea of STL is *not* to provide a bunch
>of container classes with useful methods.
>
>While this is certainly how STL is most often used, its big idea is to
>separate data structures and algorithms. Imagine 10 algorithms that
>work on 10 data structures. Using the right abstractions over the data
>structures (iterators), we only have to describe each of the algorithms
>once instead of 10 times.
It is generally used as a container collection, because the idea of "generic
algorithms" doesn't work- in C++ or any other language. Or rather, it can
work, but it works very poorly.
Consider the linked list and the array. Both are similiar sorts of data
structures- both are sequences, and I can write a get() function, to get the
ith element of each, and I can write a prepend() function, adding an element
to the begining of the sequence. So far, so good- until you look at the
time complexity of the two operations. On an array, get()ing a random
element is O(1) complexity- I just do an array dereference. But
prepend()ing an element is O(N) complexity, as I have to move all the
elements of the array up one place to make room for the new element at the
head of the array. On the other hand, the linked list can prepend() an
element in O(1)- just allocate a new node of the list, and populate the data
fields in the obvious manner. However, get()ing the ith element is O(N)
complexity (well, O(i) technically), as I have to walk down the list to find
the right element.
So if the algorithm I'm doing does a heck of a lot of get()s, and very few
prepend()s, using an array instead of a linked list is an enormous speed up.
On the other hand, if my algorithm does a lot of prepend()s, and very few
get()s (other than get()s with low i's, like head()), then using a linked
list instead of an array will result in an enormous speed up.
Sometimes, the same algorithm can be implemented in two different ways. For
example, consider quick sort. The basic algorithm of quick sort (for the
readers who don't remember) is that we pick a pivot, split the sequence into
two subsequences, one of all the elements less than the pivot, and one of
all the elements greater than the pivot, sort the two subsequences
recursively, and then recombine the two subsequences. So the question is:
how do I create the subsequences? If I'm quick sorting an array, I want to
do it in place, by just moving elements around in the array using get() and
put(). If I'm quick sorting a linked list, I want to create new lists as I
go, using prepend(). But note, this requires two different implementations
of the "same" algorithm- one using get(), and one using prepend().
>O'Caml standard library and ExtLib are certainly not the right
>examples. They just provide a collection of data structures with
>specific algorithms, not a framework for writing structure-independent
>algorithms.
Ok, first of all, OCaml and ExtLib provide iterators, same as the STL-
ExtLib explicitly, and the Ocaml standard library uses lists as it's
iterators. My personal preference would be to use lazy lists as iterators,
but that's a different rant.
Second of all, Ocaml *does* provide a way to implement data-structure
neutral algorithms, via modules and functors (which, IIRC, Ocaml got from
SML). Basically, you can do:
module type Req = sig
(* Those functions I depend on the data structure to provide *)
type 'a t (* The type of the data structure *)
val length : 'a t -> int
val get : 'a t -> int -> 'a
end
module Make(DS: Req) = struct
let my_algo ds = ...
end
Then you could do:
module My_array = struct
type 'a t = 'a array
let length = Array.length
let get = Array.get
end
(* Implement my algorithm on arrays *)
module My_algo_array = Make(My_array);;
module My_list = struct
type 'a t = 'a list
let length = List.length
let get = List.nth
end
(* Implement my algorithm on lists *)
module My_algo_list = Make(My_list);
Notice that there is nothing special you need to do to a module (like List
or Array) in order to allow them to be used in this fasion. Also note that
this doesn't protect you from complexity problems.
>It is my understanding that even if it hadn't been for the type system
>limitations in ML, users would be stuck with doing "module arithmetic"
>to achieve STL-like functionality, whereas C++ programmers can
>basically state what they mean.
In what way is modules and functors less clear than C++ templates? I'm
assuming that's what you mean by "module arithmetic".
>Here are the interviews, by the way. Don't design yet another
>programming language, until you've read them! Not only he bashes
>"lesser" languages, takes shots at garbage collection, but also he
>decries OOP in general.
Do you really want me to take pot shots at C++? Seriouesly, if I started,
we could be here all day. Starting with, it wasn't that long ago that
simply being able to correctly compile and run the STL was a major
accomplishment for C++ compilers.
I will add one serious complaint. It's getting really clear to me that the
people in control of the C++ standard know dick about how compilers work.
Templates, as they were defined in the C++ standard, make the code
unparseable without semantic information. Consider the following sequence
of tokens:
a < b, c > d;
Now, is this a variable declaration using templates, and parsed like:
( a < b, c > ) d;
or is this two comparison operations combined using the comma operator, and
parsed like:
( a < b ) , ( c > d ) ;
? Granted, the second doesn't make a lot of sense (unless, of course, I've
overloading the < and > operators to have side effects)- but it was legal C,
and thus is legal C++.
The compiler can't tell unless it knows the type, the semantic information,
of a- is a a template or a variable? Basically, you can't use
semantics-free parsers like YACC or ANTLR to parse C++. Note that a single
implementation before the standard had gotten set would have shown this
problem clearly, when it could have been fixed trivially- just use some
other tokens instead of < and > to delineate templates. Say, <[ and ]>.
Then the template version would be a <[ b, c ]> d; - a different set of
tokens than the two compares.
This also would have solved the >> problem. A classic problem newbie C++
programmers hit is the nested template problem:
a<b<c>>d;
doesn't parse correctly (when a and b are templates), you need to do:
a<b<c> >d;
to get it to parse correctly. Of course, in a recent interview, Strousup is
going to wave his magic wand and make this disappear:
http://www.artima.com/cppsource/cpp0xP.html
Great. Now, instead of being just unparseable, C++ is going to become
unlexable. So the lexer- which is just concerned with seperating the
character stream into tokens (words)- is presented with >>. Is this one
>> token or two > tokens? Well, it depends. What does it depend upon?
Upon reading the programmers mind:
a<b<~0ul >> x >> y;
The lexer needs to magically know that the first >> is a single token,
shifting ~0ul right x places, and the second >> is closing the two
templates, and the above statement decalares the variable y. No, wait, it
needs to know that the first >> closes the two templates, declaring the
variable x, which we then shift right y bits. Um, or something.
All you need to implement to get a working C++ compiler is a working DWIM
instruction. Strousup and company have no freaking clue how a compiler
works- or they wouldn't be being this stupid.
As for GC, Stepanov is making a classic mistake- "I used GC back in the
seventies, and it sucked. Therefor, GC sucks." Um, right.
As an exercise, please show me a language that a) was designed in the last
20 years (post 1985), b) has more than a dozen users, *and* c) doesn't have
built in garbage collection.
Brian
Ben Rudiak-Gould
> I realized during this activity that side effects are important, because
> you cannot really do graph operations without side effects. You cannot
> replicate a graph every time you want to modify a vertex.
I'm sorry, but this is a really foolish thing to say. It's always possible
to turn an imperative algorithm into a pure algorithm with an additional
factor of at most log(n) in asymptotic time and space complexity. And as
I've argued here before ([1], though see also [2]), the factor of log(n) is
there already in the imperative algorithm.
Martin Erwig has done some interesting research on specifying graph
algorithms in a functional style [3].
I hate to participate in these discussions because of tribalism [4], but the
point above needs to be made. Please understand that it doesn't mean I'm on
the side of functional languages, whatever that means. Some of my best
friends are C++ classes.
-- Ben
[1] http://groups.google.com/group/comp.lang.functional/msg/19d6cfeaa661d3d6
[2] http://groups.google.com/group/comp.lang.functional/msg/9d98d54a110a4db5
[3] http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP01
[4] http://www.perl.com/pub/a/2000/12/advocacy.html
Brian Hurt
>> * Speed. O'Caml simply won't optimize STL'ish polymorphic code the way
>> C++ compilers are expected to optimize proxy objects (iterators). If
>> only MLton hackers wasted their time on OCaml instead of SML! :-)
>Yes. However, there is a trade-off between compile- and run-time here. OCaml
>will compile such programs vastly more quickly than g++, MLton etc.
I'd also point out ocamldefun, the defunctorizor. This is usefull for the
times when eliminating the abstraction can lead to large optimization
opportunities. The nice thing is that you can choose which functors get
devirtualized (increasing object code size but allowing greater
Brian
Brian Hurt
>So he says that functional programming languages are not practical. I
>think he's wrong. Maybe it was true at that time.
He was trying to do graph programming in a purely functional style (i.e. no
imperitive arrays). Unfortunately, the only ways I'm aware of doing this
replaces an O(1) operation (array dereference) with an O(log N) operation
(tree search). Which means that for even moderately sized graphs (1,000
nodes) we're talking about an order of magnitude slow down (or more).
To my knowledge, this is still true.
Brian
Tomasz Zielonka
> Any ideas that pure-functional programming (a raison d'etre of Haskell)
> is practical, can be quickly foiled by Stepanov's graph argument:
> "change this vertex in this graph".
All I want to tell is that *Haskell* is practical. Perhaps you are right
that for some application *purely functional style* is impractical.
However, Haskell, technically being a purely functional language, allows
you to use imperative operations, so if you want, you can "change this
vertex in this graph" in O(1) time (but you have to design your graph in
a way that allows it).
Haskell is a purely functional language in the sense that
_expressions_are_pure_ - there are no side effects arising
from evaluation of expressions (function applications).
Still, there are other means to get imperative features
into the language - in Haskell this is achieved by the
use of monads and abstract IO datatype.
Well, I agree this may seem a bit contradictory or schizophrenic, but
that's just the way it is.
> If you would trade tangibles for ideology and style, use Haskell.
I think that in my case the reasons for using Haskell are really
pragmatic - I seem to be most effective when I use this language. And I
am not a purity fanatic - when the most natural approach is imperative,
I write imperative code in Haskell.
> I don't think there is any more to discuss here.
I think there is, if you don't want to stay clueless ;-)
Ben Rudiak-Gould
> It's getting really clear to me that the people in control of the C++
> standard know dick about how compilers work.
I think they know quite a lot, actually.
> Templates, as they were defined in the C++ standard, make the code
> unparseable without semantic information.
C is already unparseable without semantic information. For example the
statement "x*y;" parses differently depending on whether x is a typedef or a
variable in the current scope.
Haskell, which generally has very clean syntax, is also unparseable without
semantic information, because of fixity declarations. The Revised Report
gives the example (let x = True in x == x == True). As far as I know all
Haskell implementations get this one wrong, not because they're unaware of
the problem but because it's too much of a pain to fix.
> Note that a single implementation before the standard had gotten
> set would have shown this problem clearly [...]
Commercial implementations of the template system existed long before the
standard was approved, and I'm sure that the committee members understood
the problem long before any implementations were written.
> Great. Now, instead of being just unparseable, C++ is going to become
> unlexable.
Heh. If you like that, you'll love this:
http://gcc.gnu.org/ml/gcc-bugs/2001-03/msg00496.html
In any case, you haven't seen unlexable until you've seen Perl.
> All you need to implement to get a working C++ compiler is a working DWIM
> instruction. Strousup and company have no freaking clue how a compiler
> works- or they wouldn't be being this stupid.
Look, everyone knows that C++ syntax is a mess. What I'm arguing with is
your idea that the C++ standards committee members are/were incompetent,
which is totally untrue. They have always been aware of all the problems you
mentioned, as well as many others (like that parsing ambiguity in C). They
made executive decisions after weighing various factors, some of which you
probably consider unimportant. Overall C++ is a fine programming tool for
many applications, and its designers are an extremely cool bunch of hackers.
-- Ben
Tomasz Zielonka
Tomasz Zielonka wrote:
> However, Haskell, technically being a purely functional language, allows
> you to use imperative operations, so if you want, you can "change this
> vertex in this graph" in O(1) time (but you have to design your graph in
your graph *library*
> Well, I agree this may seem a bit contradictory or schizophrenic, but
> that's just the way it is.
It's not contradictory, it just seems so.
Vesa Karvonen
[...]
> C++'s templates allow for specialization on type and even integers. But
> beside that, as far as I can tell, C++'s templates and SML's modules are
> equivalent in expressive power. The main difference is that SML requires
> that the interface be explicitly spelled out, whereas C++'s templates
It all depends on what you mean when you say "expressive".
The SML module system is clearly more expressive in terms of ability
to enforce abstraction and type safety. There is nothing truly
comparable to ML-like signatures in C++ (I'm not counting concept
checking kludges). Basically, once you get an ML functor to compile,
you will know that it is type correct. The same can't be said of C++
templates.
On the other hand, the C++ template mechanism is more expressive in
the sense that it allows forms of composition that simply are not
possible using the SML (or Ocaml) module system. This is mostly due
to the latent (and, basically, unsafe) type checking of template
instantiations.
-Vesa Karvonen
Joachim Durchholz
> Tomasz Zielonka <tomasz....@gmail.com> writes:
>
>>So he says that functional programming languages are not practical. I
>>think he's wrong. Maybe it was true at that time.
>
> He was trying to do graph programming in a purely functional style (i.e. no
> imperitive arrays). Unfortunately, the only ways I'm aware of doing this
> replaces an O(1) operation (array dereference) with an O(log N) operation
> (tree search).
Agreed, but:
> Which means that for even moderately sized graphs (1,000
> nodes) we're talking about an order of magnitude slow down (or more).
That would hold true if you had been talking about O(2^N) complexity. Or
even O(N) complexity.
An O(log N) algorithm that takes one additional step for 10 nodes will
take two for 100 nodes and three for 1000 nodes (yeah I know that's a
simplification).
That's quite the contrary of "orders of magnitudes for even moderately
sized graphs".
Going from imperative to functional data structures can incur a large
*constant* overhead. That can indeed be something to worry about, and
it's an area of active research - though I have to say that the more
common problems are solved, so the easy fruit is already plucked here :-)
O(log N) factors are utterly irrelevant.
Regards,
Jo
Neil Cerutti
> As an exercise, please show me a language that a) was designed
> in the last 20 years (post 1985), b) has more than a dozen
> users, *and* c) doesn't have built in garbage collection.
Inform, for writing Interactive Fiction. The first version that
was used much was Inform 4, released in, I think, 1994.
It's a niche user-base, and the number of users is probably less
than 5000. In an domain where most objects are a singletons, and
container-classes and standard algorithms are seldom needed, I
suppose GC wouldn't buy very much anyway. In short, Inform
doesn't provide for dynamic memory allocation of any kind.
Andrew Plotkin once published a garbage collected Scheme
intepreter written *in* Inform, though.
--
Neil Cerutti
We're not afraid of challenges. It's like we always say: If you
want to go out in the rain, be prepared to get burned.
--Brazillian soccer player
Joachim Durchholz
> What I'm arguing with is
> your idea that the C++ standards committee members are/were incompetent,
> which is totally untrue.
Um... at least for Bjarne, I have seen at least one report that he tried
yacc and dropped it because he couldn't figure out how to fix the error
messages.
In my eyes, this definitely counts as "not competent enough for doing
syntax for a new language".
(I don't know about the syntactic competence of the Committee as a
whole. I don't think that competence would have helped though; at the
time Committees came into play, the C++ syntax was already nailed down
and couldn't be changed, just augmented.)
Regards,
Jo
Thant Tessman
[...]
> Look, everyone knows that C++ syntax is a mess. What I'm arguing with is
> your idea that the C++ standards committee members are/were incompetent,
> which is totally untrue. They have always been aware of all the problems
> you mentioned, as well as many others (like that parsing ambiguity in
> C). They made executive decisions after weighing various factors, some
> of which you probably consider unimportant. Overall C++ is a fine
> programming tool for many applications, and its designers are an
> extremely cool bunch of hackers.
Of course there are talented people working on and with C++. The real
problem is that too many of them tend to wildly overestimate C++'s
relative contribution to the craft of computer programming.
As for C++ being a "fine programming tool for many applications," all I
can say is that it's better than C.
-thant
--
For the people wars do not pay. The only cause of armed conflict is the
greed of autocrats. -- Ludwig von Mises
Thant Tessman
[...]
> On the other hand, the C++ template mechanism is more expressive in
> the sense that it allows forms of composition that simply are not
> possible using the SML (or Ocaml) module system. This is mostly due
> to the latent (and, basically, unsafe) type checking of template
> instantiations.
I don't understand the concern with whether the instantiation process
itself is type safe. As long as one can verify statically (i.e. before
the program is run) that the generated code is type safe, what's the big
deal? And even then, I'm not convinced that this is where templates
derive their expressive power. I think the whole thing was an accident.
Regardless, what I meant about C++ templates being more expressive than
SML's modules is that their ability to be specialized on type and
integers, combined with compile-time evaluation of constants, has turned
C++'s template mechanism into a full-fledged language. It's the most f'd
up implementation of lisp you'll ever run across, but it *is* a
language. Yeah lisp of various flavors had been doing this macro thing
for decades, but the interesting thing is how templates interact with
the rest of C++'s type system.
-thant
--
"I do not need to explain why I say things. That's the interesting thing
about being president. Maybe somebody needs to explain to me why they
say something, but I don't feel like I owe anybody an explanation."
-- George W. Bush (Bob Woodward, "Bush at War", pp. 145-46)
alex...@gmail.com
alex...@gmail.com
> It's always possible
> to turn an imperative algorithm into a pure [functional] algorithm with an additional
> factor of at most log(n) in asymptotic time and space complexity.
Is this a general theorem proven for converting any Turing machine into
a Church machine? Published and peer-reviewed? What's N in it then? The
links you provided don't seem to be such theorems.
Ian Collins
--
Ian Collins.
Lauri Alanko
In computer science, as in mathematics in general, the base of the log
function depends on the context and is indicated with a subscript when
necessary.
When used to indicate the asymptotic complexity of an algorithm, the
subscript is omitted for the simple reason that it is irrelevant: a
function is O(log_2 n) if and only if it is O(log_10 n). This should
be obvious to anyone who knows what the big-O notation means.
Hence an input of size 1000 may yield an order of magnitude of
slowdown when compared to an input of size 1. Or it may not. You can't
say simply from the algorithm's asymptotic complexity.
Lauri
Vesa Karvonen
[...]
> > On the other hand, the C++ template mechanism is more expressive in
> > the sense that it allows forms of composition that simply are not
> > possible using the SML (or Ocaml) module system. This is mostly due
> > to the latent (and, basically, unsafe) type checking of template
> > instantiations.
> I don't understand the concern with whether the instantiation process
> itself is type safe. As long as one can verify statically (i.e. before
> the program is run) that the generated code is type safe, what's the big
> deal?
A C++ template library may have bugs in the form of using incorrect
type expressions (inside the template definitions) that (due to
various reasons) happen to (or almost) work in many cases, but not
all. It is not unheard of to find such bugs a long time (years) after
a C++ template library has already been in use. Similar problems do
not occure with the SML module system due to the enforcement of type
abstraction.
> And even then, I'm not convinced that this is where templates
> derive their expressive power.
Note: I'm talking about this from a practical point-of-view of
implementing STL:ish or "generative" libraries. It is clear to me
that from a computational point-of-view C++ templates are strictly
more expressive (than Standard ML modules and it is easy to prove
formally (or, rather, as formally as the C++ standard allows ;-)).
Sorry, I don't have enough time (I wish I had) to explain these issues
thoroughly. If you can, then look up, for example, the technique of
"parameterized inheritance" in the book Generative Programming by
Czarnecki and Eisenecker and try to simulate the way that the
technique is used in the list container example (chapter 12) using SML
modules. You'll find out that it is impossible to implement the
OptCounterList layer as a functor using SML modules (because
subsequent layers would simply hide the length function). This is
basically due to lack of (informally) "subsumption in module
extension". This is also noted by Robert Bruce Findler and Matthew
Flatt in their ICFP 1998 article Modular Object-Oriented Programming
with Units and Mixins (on page 8).
-Vesa Karvonen
Ben Rudiak-Gould
>Ben Rudiak-Gould wrote:
>>It's always possible
>>to turn an imperative algorithm into a pure [functional] algorithm with an additional
>>factor of at most log(n) in asymptotic time and space complexity.
>
>Is this a general theorem proven for converting any Turing machine into
>a Church machine? Published and peer-reviewed? What's N in it then?
You can simulate a Turing machine on a Church machine with only a constant
factor slowdown, representing the tape as two infinite lists. You can
simulate a random-access machine, which is what I was talking about, on a
Church machine with a "log n" slowdown, representing the memory as a
balanced tree. I made two mistakes in my statement, though. First, space
complexity only increases by a constant factor. Second, n here is the space
usage, which is not what "n" is normally used for. If the space usage is
polynomial in k then you get a factor of log k, but if the space usage is
Theta(2^k) then you get a factor of k. However the argument I made that the
factor of log k is present already in the imperative algorithm applies also
to the factor of k when space usage is exponential.
Both results are easy to see, but I imagine somebody famous published proofs
of them in the early days of computer science. Maybe someone else will have
a reference handy.
-- Ben
Tony Garnock-Jones
> He was trying to do graph programming in a purely functional style (i.e. no
> imperitive arrays). Unfortunately, the only ways I'm aware of doing this
> replaces an O(1) operation (array dereference) with an O(log N) operation
> (tree search). Which means that for even moderately sized graphs (1,000
> nodes) we're talking about an order of magnitude slow down (or more).
Interestingly, there are techniques that allow pure-functional array
operations in O(1)... so long as the arrays are used linearly. See
http://home.pipeline.com/~hbaker1/ShallowArrays.html
(This is quite aside from the fact that what seems to be an O(1)
access/update in an imperative system is in fact an O(log N)
access/update because of indirection through page tables. Of course, the
base of the logarithm is quite high, but nonetheless, it's not *really*
constant-time...)
Cheers,
Tony
Joe Marshall
Ben Rudiak-Gould wrote:
> Brian Hurt wrote:
> > It's getting really clear to me that the people in control of the C++
> > standard know dick about how compilers work.
>
> I think they know quite a lot, actually.
You must set the bar pretty damn low.
> > Note that a single implementation before the standard had gotten
> > set would have shown this problem clearly [...]
>
> Commercial implementations of the template system existed long before the
> standard was approved, and I'm sure that the committee members understood
> the problem long before any implementations were written.
You think they *intended* that mess? I was willing to give them the
benefit of the doubt and assume supreme idiocy.
> > Great. Now, instead of being just unparseable, C++ is going to become
> > unlexable.
>
> Heh. If you like that, you'll love this:
>
> http://gcc.gnu.org/ml/gcc-bugs/2001-03/msg00496.html
>
> In any case, you haven't seen unlexable until you've seen Perl.
>
> > All you need to implement to get a working C++ compiler is a working DWIM
> > instruction. Strousup and company have no freaking clue how a compiler
> > works- or they wouldn't be being this stupid.
>
> Look, everyone knows that C++ syntax is a mess. What I'm arguing with is
> your idea that the C++ standards committee members are/were incompetent,
> which is totally untrue.
So they are malicious.
> They have always been aware of all the problems you
> mentioned, as well as many others (like that parsing ambiguity in C).
This raises the question of why the standard kept changing in the face
of discovered problems. If they have always been aware of the
problems, what was the point of proposing one solution and then
adopting another once *everyone else* became similarly aware?
> They made executive decisions after weighing various factors, some of which you
> probably consider unimportant.
I don't think `executive' means `piss-poor', (except, perhaps, when
talking about branches of government). There is no evidence that
anything more complicated than a Magic 8 ball was considered in the
so-called `design' of the language.
> Overall C++ is a fine programming tool for
> many applications, and its designers are an extremely cool bunch of hackers.
C++ hackers get what they deserve.
Bruce Hoult
Ben Rudiak-Gould <br276d...@cam.ac.uk> wrote:
> Overall C++ is a fine programming tool for many applications, and its
> designers are an extremely cool bunch of hackers.
Hmm, I seem to have heard rather similar words applied to myself and my
friends and my favourite language a few months ago. And that is not C++
but Dylan.
I note you did not say C++ is the programming tool of choice for
discriminating hackers -- or even that it is not too shabby.
--
Bruce | 41.1670S | \ spoken | -+-
Hoult | 174.8263E | /\ here. | ----------O----------
Alan Morgan
Joachim Durchholz <j...@durchholz.org> wrote:
>Ben Rudiak-Gould schrieb:
>> What I'm arguing with is
>> your idea that the C++ standards committee members are/were incompetent,
>> which is totally untrue.
>
>Um... at least for Bjarne, I have seen at least one report that he tried
>yacc and dropped it because he couldn't figure out how to fix the error
>messages.
I thought it was the other way around. He originally wanted to do a recursive
descent parser but was convinced that all the cool kids were using yacc, so he
decided (reluctantly) to use it. He regretted that decision.
Alan
--
Defendit numerus
Brian Hurt
>Brian Hurt schrieb:
> > Which means that for even moderately sized graphs (1,000
>> nodes) we're talking about an order of magnitude slow down (or more).
>That would hold true if you had been talking about O(2^N) complexity. Or
>even O(N) complexity.
By "order of magnitude" I mean 10-fold. log2(1024) = 10. A 1,000 node tree
will generally be about 10 levels deep, and will take about 10 steps to get
to the average node. Each step will be *at least* as expensive as an array
dereference, making the whole process at least 10x slower than the array
dereference.
You can reduce the constant factor overhead by having more than two children
a node, but this increases the complexity of the implementing code- and each
step becomes signifigantly slower. You still end up signifigantly slower
than arrays (for this purpose- tree based sequences have some interesting
properties- inserting or removing an element anywhere in the sequence is an
O(log N) operation).
Note that these comments only apply to graph algorithms written for an
adjacency list representation.
Actually, if there was some way to keep adjacent nodes "near" each other,
it's fairly obvious that, given the "path" from the root to node i, going
from node i to node j can take only log |i-j| time. If the |i-j| values are
kept "small", on average, the cost of walking the graph can be kept
reasonable. Note that there will be graphs for which |i-j| can not be kept
small- Kn graphs (all nodes have edges with all other nodes) are an obvious
example.
>Going from imperative to functional data structures can incur a large
>*constant* overhead. That can indeed be something to worry about, and
>it's an area of active research - though I have to say that the more
>common problems are solved, so the easy fruit is already plucked here :-)
>O(log N) factors are utterly irrelevant.
In my experience, there is very little constant factor differences between
purely functional data structures and their imperative counterparts.
Even hash tables aren't that big of an advantage- people generally
underestimate the cost of calculating the hash vr.s the cost of a compare.
Consider strings- most CPUs today can compare 4 bytes (if not 8 bytes) in a
single 1-cycle instruction, while the cost of a multiply is generally about
4 cycles. So calculating a hash value that requires a multiply per byte is
as expensive as about 16 string compares. So the tree needs to have more
than 64K strings in it for the hash table to become faster.
It's only graph algorithms that keep me from advocating we should dump
imperitive over the side in it's entirity.
By the way, I have read Erwig's papers. With a built-in (imperitive?) ufold
and gfold, his method is a constant factor slower than array-based (about
2-fold). But with the non-built-in function, he's at best O(N log N), and
for functionalized gfold, it looks like O(N^2).
Brian
Brian Hurt
>Brian Hurt wrote:
>> He was trying to do graph programming in a purely functional style (i.e. no
>> imperitive arrays). Unfortunately, the only ways I'm aware of doing this
>> replaces an O(1) operation (array dereference) with an O(log N) operation
>> (tree search). Which means that for even moderately sized graphs (1,000
>> nodes) we're talking about an order of magnitude slow down (or more).
>Interestingly, there are techniques that allow pure-functional array
>operations in O(1)... so long as the arrays are used linearly. See
>http://home.pipeline.com/~hbaker1/ShallowArrays.html
As I recall, from the last time I looked at this issue, the Shallow Array
concept required underlying arrays.
One of the reasons I'm interested in purely functional data structures is
the comming need for massive parallelism, and I think purely functional code
is a necessary (if not sufficient) precondition to do that with any sort of
sanity.
The sudden popularity of dual-core transistors is a signal to me that
massive multithreading is going to be the hot issue in the comming decade.
The hardware designers have given up- for the first time since Moore's law
kicked into effect, the hardware designers could not use a doubling of
transistors to increase single-threaded speed by any signifigant amount.
Yeah, the transistors are faster, and when they solve the heat problem,
clock speeds will go up. But the only thing they can do with the increased
transistor budget is give us a second core. And, in 18 or so months,
they'll just give us quad core. Then eight-core, then sixteen core, and so
on. Moore's law is good for another 15 or so years at least, according to
the experts, so we're talking about another 8-10 doublings. Which means
chips with 256 to 1024 cores on them. And multi-chip computers are
becomming more common, not quite on a Moore's law tragectory, but still.
Worse yet, once the software for massive-multithreading is available, the
designs might regress. Comparing SpecInt performance from Ace's hardware,
the PPC 970 is only about 15% more efficient than the 604e was, per clock.
The 604e was about 5.1M transistors, while the 970 has about 55M. In other
words, if we could take advantage of it, we could put 10 604e's in the space
on one 970. Which goes to show how little gain the increasing transistor
count has given us in the last several years.
Imperitive data structures, heavy weight threads, and locks (or their
cousins monitors, like synchronized in Java) are simply not scalable to that
level in any sort of sane way. It's hard to "rescale" (to take advantage of
more, or run more efficiently on fewer, CPUs), plus it's deeply error prone.
In a sense, it's kind of like programming in assembly. You can do it, but
it's so hard to maintain and so error prone that you really shouldn't.
Instead, I'm thinking that something like Cilk-style microthreads, a small
selection of carefully choosen communication primitives (the current
suspects are channels and transactional memory), and purely functional data
structures would be a winning combination- allowing programmers to write
widely scalable code quickly and correctly.
>(This is quite aside from the fact that what seems to be an O(1)
>access/update in an imperative system is in fact an O(log N)
>access/update because of indirection through page tables. Of course, the
>base of the logarithm is quite high, but nonetheless, it's not *really*
>constant-time...)
Yeah- but the array access only has to do it 1 time, while the tree search
needs to do it O(log N) times. The tree lookup is still signifigantly
slower.
Brian
Brian Hurt
>I thought it was the other way around. He originally wanted to do a recursive
>descent parser but was convinced that all the cool kids were using yacc, so he
>decided (reluctantly) to use it. He regretted that decision.
IMHO, doing the official parser of a language in YACC (or the equivlent
LALR(1) grammer tool) is the equivelent of compiling your code with all
warnings turned on. Yeah, it's restrictive. That's the *point*. The stuff
it's bitching about are *problems* that need to be fixed.
Because if YACC complains (or you can't write a straightforward grammar for
your language in YACC without YACC complaining), your languages has gotchas
that will needless trip up programmers, even experienced programmers.
Reduce-reduce conflicts is a sign of something deeply wrong, while
shift-reduce conflicts just means that the programmers will write incorrect
code. Shift-reduce conflicts are dangling else problems, and how often do
dangling else's bit C/C++ programmers?
One of the biggest complaints I have about Ocaml is the number of
shift-reduce conflicts the grammar has (actually worse than C++, but I note
no reduce-reduce conflicts). These bite me regularly.
I have no doubt that YACC prevented Bjarne from constructing the language he
wanted to.
Brian
Alan Morgan
Brian Hurt <bhurt@AUTO> wrote:
>amo...@xenon.Stanford.EDU (Alan Morgan) writes:
>
>>I thought it was the other way around. He originally wanted to do a recursive
>>descent parser but was convinced that all the cool kids were using yacc, so he
>>decided (reluctantly) to use it. He regretted that decision.
>
>IMHO, doing the official parser of a language in YACC (or the equivlent
>LALR(1) grammer tool) is the equivelent of compiling your code with all
>warnings turned on. Yeah, it's restrictive. That's the *point*. The stuff
>it's bitching about are *problems* that need to be fixed.
Some of the problems certainly came from the C heritage. I believe he said
that an LALR(1) grammar for C didn't exist when he started work with C++.
That might indicate that yacc is not the right tool for the job (it might
also indicate that C is not the right starting point. I'm sure plenty of
people here will be happy to take the latter position).
>I have no doubt that YACC prevented Bjarne from constructing the language he
>wanted to.
That's an argument against him using YACC, surely?
>Brian
Alan
--
Defendit numerus
Paul Rubin
> Some of the problems certainly came from the C heritage. I believe
> he said that an LALR(1) grammar for C didn't exist when he started
> work with C++.
I thought pcc1 (Portable C Compiler) predated "C with classes" (later
called C++), and that pcc1 used yacc.
Tom Lord
Tony Garnock-Jones wrote:
> Brian Hurt wrote:
> > He was trying to do graph programming in a purely functional style (i.e. no
> > imperitive arrays). Unfortunately, the only ways I'm aware of doing this
> > replaces an O(1) operation (array dereference) with an O(log N) operation
> > (tree search). Which means that for even moderately sized graphs (1,000
> > nodes) we're talking about an order of magnitude slow down (or more).
>
> Interestingly, there are techniques that allow pure-functional array
> operations in O(1)... so long as the arrays are used linearly. See
> http://home.pipeline.com/~hbaker1/ShallowArrays.html
One should also point out that there is no such thing as a large O(1)
array of arbitrary size. At least in some sense. Pauli exclusion,
speed
of light, memory hierarchies, yadda yadda yadda.
If yr dealing with big (logical) arrays in a functional way you might
consider designing the physical data structure in such a way so that,
expected case at least, you get closer to O(1) measured CPU cycles
rather than O(1) measured in memory access (in the context of a
deep hierarchy and virtual memory subsystem). Where your access
patterns have the right locality properties, one of those O(log n) data
structures may actually be quite winning.
Anyway, when you do have state to update in place and that's
really the best way to do it -- some monadic approach or other
can still leave you with a pure program.
-t
(When I sometimes say "Space aliens program in [Scheme/Lisp/....]"
this is the kind of thing I mean. Cons pairs are a decent and
minimalist
abstraction describing memory, for example.)
Ivan Boldyrev
> ... You cannot really do graph operations without side effects...
This is a bug or a typo. Actual text is "I [Stepanov] cannot really
do ...". But he didn't prove that nobody can.
--
Ivan Boldyrev
Violets are red, Roses are blue. //
I'm schizophrenic, And so am I.
alex...@gmail.com
> the idea of "generic
> algorithms" doesn't work- in C++ or any other language. Or rather, it can
> work, but it works very poorly.
You can take the red pill and look at BOOST.Graph (BGL): it has a dozen
algorithms that work on half a dozen graph representations (two
built-in, several views, and adaptors for pre-existing graph
representations).
> Second of all, Ocaml *does* provide a way to implement data-structure
> neutral algorithms, via modules and functors (which, IIRC, Ocaml got from
> SML). Basically, you can do:
That's what happens when you don't read the article you are replying to
carefully, or the follow-ups (start with the second paragraph):
http://groups.google.com/group/comp.lang.functional/msg/1d8b8acd41f22a38
> a<b<~0ul >> x >> y;
>
> The lexer needs to magically know that the first >> is a single token,
> shifting ~0ul right x places, and the second >> is closing the two
> templates, and the above statement decalares the variable y. No, wait, it
> needs to know that the first >> closes the two templates, declaring the
> variable x, which we then shift right y bits. Um, or something.
>
> All you need to implement to get a working C++ compiler is a working DWIM
> instruction. Strousup and company have no freaking clue how a compiler
> works- or they wouldn't be being this stupid.
It's "Stroustrup", and you are welcome.
> As for GC, Stepanov is making a classic mistake- "I used GC back in the
> seventies, and it sucked. Therefor, GC sucks." Um, right.
You are misrepresenting what he said.
> As an exercise, please show me a language that a) was designed in the last
> 20 years (post 1985), b) has more than a dozen users, *and* c) doesn't have
> built in garbage collection.
Fortran 95, Fortran 2003, Ada 95. You can think of C++ as C 97.
Andreas Rossberg
>
> You'll find out that it is impossible to implement the
> OptCounterList layer as a functor using SML modules (because
> subsequent layers would simply hide the length function). This is
> basically due to lack of (informally) "subsumption in module
> extension".
I want row polymorphic structures then :).
- Andreas
--
Andreas Rossberg, ross...@ps.uni-sb.de
Let's get rid of those possible thingies! -- TB
Dr Jon D Harrop
> Brian Hurt wrote:
> > As for GC, Stepanov is making a classic mistake- "I used GC back in the
> > seventies, and it sucked. Therefor, GC sucks." Um, right.
>
> You are misrepresenting what he said.
AFAICT, Stepanov thought that constructors and destructors were an
adequate replacement for garbage collection. I don't think many people
would agree with him today.
> > As an exercise, please show me a language that a) was designed in the last
> > 20 years (post 1985), b) has more than a dozen users, *and* c) doesn't have
> > built in garbage collection.
>
> Fortran 95, Fortran 2003, Ada 95. You can think of C++ as C 97.
AFAIK, there are no Fortran 2003 compilers, so I think it is optimistic
to expect there to be more than a dozen users.
Cheers,
Jon Harrop.
Joachim Durchholz
> News flash: in Computer Science, log(1000) = 9.9657
News flash #2 (no pun intended):
O (log2 N) is the same as O(log10 N).
That's why the logarithm base is never given in O() expressions.
News flash #3:
I was expressly saying it's a simplification. The base argument is
unaffected by that simplification. So please stick with the obvious
meaning, not with wording. Thanks.
Regards,
Jo
alex...@gmail.com
News flash #4: I didn't say anything about "O". I'm objecting to your
earlier objecting to someone saying O(log 1000) \approx 10
Joachim Durchholz
> Joachim Durchholz <j...@durchholz.org> writes:
>
>
>>Brian Hurt schrieb:
>>
>>>Which means that for even moderately sized graphs (1,000
>>>nodes) we're talking about an order of magnitude slow down (or more).
>
>>That would hold true if you had been talking about O(2^N) complexity. Or
>>even O(N) complexity.
>
> By "order of magnitude" I mean 10-fold.
OK.
What you're describing in the text I snipped is a constant-factor
overhead. (Your mention of graph size threw me off track: I took it to
mean that there's no overhead with small graphs, implying some big-Oh
slowdown.)
You're right: there is a risk of a high (even order-of-magnitude)
constant-factor overhead. Good algorithms can eliminate a lot of that
overhead though.
> log2(1024) = 10. A 1,000 node tree
> will generally be about 10 levels deep, and will take about 10 steps to get
> to the average node. Each step will be *at least* as expensive as an array
> dereference,
Not always true, but I agree that's in general the case. It's slower at
the second level anyway, and single-level trees are essentially the same
as an array.
> making the whole process at least 10x slower than the array
> dereference.
Sure.
Note that the overhead doesn't continue that way. A 1,000,000 node tree
is 20x slower, not 20,000x slower.
Is this a problem? Then you need a faster language - and lose the
associated flexibility. It's the old trade-off between raw speed and
maintainability, and with increasing processor speeds, it becomes less
of a problem with every year.
Flexibility is even more important. It opens up the possibility of
trying entirely different algorithms.
There is the rare task where no amount of algorithmization will help.
(Moving a bunch of bits from RAM to screen memory, say.) In these cases,
optimizing by using a lower-level language can make a huge difference.
Particularly if it's in the bowels of an oft-used library.
For everything else, higher-level (non-imperative, side-effect-free)
languages massively decouple software. In other words, exchanging local
algorithms with something better, refactoring the software and similar
activities become easier by an order of magnitude.
That's why I'm not too concerned about constant factors of 10x, 20x, or
even 100x. Current-day processors are fast enough to handle that, at
least for desktop applications (big-time number-crunching and embedded
processors are an entirely different story).
The main performance bottleneck of modern desktop software is sheer
software size. If starting a word processor takes half a minute, that's
too slow.
A better-decoupled software is smaller, each component far more
flexible. This *should* result in much smaller executables, hence faster
startup. (Once it's loaded, almost all software is "fast enough", isn't
it? The only desktop exception that I know is games...)
Even for low-level stuff, functional approaches can be used to
advantage. The hallmark example is the FFTW package. It takes a few
parameters (matrix size etc.) and generates C code that does the optimum
Fast Fourier Transform for that specific set of parameters.
If would be conceivable to extend this kind of code generation. Let me
imagine something that's not even reasonable today: a system where
hardware drivers are just a bunch of specifications (accessing *this*
hardware registers has *that* effect), and the OS takes those
specifications and generates the appropriate driver code on the fly.
(This idea probably won't work as described, but I can imagine several
variations that would. Just imagine an entire programming language
working "the STL way" - FPLs are already there.)
>>Going from imperative to functional data structures can incur a large
>>*constant* overhead. That can indeed be something to worry about, and
Oops - that should have been "*constant-factor* overhead".
>>it's an area of active research - though I have to say that the more
>>common problems are solved, so the easy fruit is already plucked here :-)
>>O(log N) factors are utterly irrelevant.
>
> In my experience, there is very little constant factor differences between
> purely functional data structures and their imperative counterparts.
>
> Even hash tables aren't that big of an advantage- people generally
> underestimate the cost of calculating the hash vr.s the cost of a compare.
True :-)
The next big thing in that vein is hash table resizing. It's
astonishling rare that hash tables are grown by factors instead of by
increments.
> Consider strings- most CPUs today can compare 4 bytes (if not 8 bytes) in a
> single 1-cycle instruction, while the cost of a multiply is generally about
> 4 cycles. So calculating a hash value that requires a multiply per byte is
> as expensive as about 16 string compares. So the tree needs to have more
> than 64K strings in it for the hash table to become faster.
>
> It's only graph algorithms that keep me from advocating we should dump
> imperitive over the side in it's entirity.
>
> By the way, I have read Erwig's papers. With a built-in (imperitive?) ufold
> and gfold, his method is a constant factor slower than array-based (about
> 2-fold). But with the non-built-in function, he's at best O(N log N), and
> for functionalized gfold, it looks like O(N^2).
I haven't read that deeply. My reasoning comes from another line of thought:
O(N^2) shouldn't be required. In general, there's always a way to go
from imperative to functional with no more than an additional O(log N)
factor, so that O(N^2) figure should come from either a bad algorithm or
an error somewhere along the line.
Regards,
Jo
alex...@gmail.com
Scratch that.
I'm objecting to your earlier objection to someone's saying log(1000)
\approx 10, in the context of O-notation.
Lauri Alanko
<alex...@gmail.com> wrote:
> News flash #4: I didn't say anything about "O". I'm objecting to your
> earlier objecting to someone saying O(log 1000) \approx 10
The original post by Brian Hurt said:
> Unfortunately, the only ways I'm aware of doing this replaces an O(1)
> operation (array dereference) with an O(log N) operation (tree
> search). Which means that for even moderately sized graphs (1,000
> nodes) we're talking about an order of magnitude slow down (or more).
Whereas the fact of the matter is that the slowdown may be either more
_or_ less than an order of magnitude, depending on the details of the
tree implementation (mostly on the branching factor). It might even be
that the branching factor >= 1000, in which case accessing a tree with
a thousand nodes would be just as fast as accessing a tree with a
single node. Obviously, this would involve a space-time tradeoff that
would only rarely be worthwhile.
Lauri
alex...@gmail.com
You are missing the point. I'm aware that there may be an "unknown"
constant factor. Jo was the one who said: "log(1000) != 10, because
log(1000) = 3" . Maybe if you were reading more carefully, instead of
just looking for ways to attack anyone who's not buying into the
pure-functional programming dogma. Thanks.
Philippa Cowderoy
> Ben Rudiak-Gould schrieb:
> > What I'm arguing with is your idea that the C++ standards committee members
> > are/were incompetent, which is totally untrue.
>
> Um... at least for Bjarne, I have seen at least one report that he tried yacc
> and dropped it because he couldn't figure out how to fix the error messages.
>
Yeah, IIRC that's in his own book too. Thing is, I believe it also dates
back to C with Classes. It's fair to assume he may've learnt something
since then.
Ivanova is always right.
I will listen to Ivanova.
I will not ignore Ivanova's recomendations.
Ivanova is God.
And, if this ever happens again, Ivanova will personally rip your lungs out!
Alan Grover
> Any ideas that pure-functional programming (a raison d'etre of Haskell)
> is practical, can be quickly foiled by Stepanov's graph argument:
> "change this vertex in this graph". If you would trade tangibles for
> ideology and style, use Haskell. I don't think there is any more to
> discuss here.
All in all, a successful troll.
Marcin 'Qrczak' Kowalczyk
alex...@gmail.com writes:
> only C++ satisfies all three of the desired properties
>
> 1. Compile-time genericity
> 2. Mutable data structures
> 3. Sufficient genericity
[...]
> * AFAIK Haskell satisfies 1 and 3
Standard Haskell indeed doesn't support mutable data structures,
but common extensions in all major implementations do.
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Brian Hurt
No, that's an argument against him designing the language the way he wanted
to. Remember my main point: if YACC is complaining about it, it'll be a
problem for the users of the language.
Brian
Brian Hurt
>Brian Hurt wrote:
>> the idea of "generic
>> algorithms" doesn't work- in C++ or any other language. Or rather, it can
>> work, but it works very poorly.
>You can take the red pill and look at BOOST.Graph (BGL): it has a dozen
>algorithms that work on half a dozen graph representations (two
>built-in, several views, and adaptors for pre-existing graph
>representations).
I've looked at the BOOST library. This can be done just as easily under
Ocaml.
>> Second of all, Ocaml *does* provide a way to implement data-structure
>> neutral algorithms, via modules and functors (which, IIRC, Ocaml got from
>> SML). Basically, you can do:
>That's what happens when you don't read the article you are replying to
>carefully, or the follow-ups (start with the second paragraph):
>http://groups.google.com/group/comp.lang.functional/msg/1d8b8acd41f22a38
I did the read the article. Did you read my reply?
>It's "Stroustrup", and you are welcome.
Typo.
>> As for GC, Stepanov is making a classic mistake- "I used GC back in the
>> seventies, and it sucked. Therefor, GC sucks." Um, right.
>You are misrepresenting what he said.
1) His experience with Scheme and GC was in 70's
2) GC back in the 70's sucked (granted)
3) I have no evidence that he has any real experience with GC post
1980-something.
4) Therefor, his experience with GC is not indicitive of modern GC
5) Therefor, his conclusions regarding GC are suspect (at best).
>> As an exercise, please show me a language that a) was designed in the last
>> 20 years (post 1985), b) has more than a dozen users, *and* c) doesn't have
>> built in garbage collection.
>Fortran 95, Fortran 2003, Ada 95. You can think of C++ as C 97.
Fortran, Ada, C, and C++ all were designed and initially standardized more
than 20 years ago. Updates to the standard don't count. Built-in GC needs
to be built-in from the get-go, you can't bolt it on later.
Brian
Brian Hurt
>Note that the overhead doesn't continue that way. A 1,000,000 node tree
>is 20x slower, not 20,000x slower.
Yep. It's fairly easy to get ~10x slower, but basically impossible to get
~100x slower.
Hmm. Actually, the base of the logarithm is important in this discussion,
for two reasons:
1) Most programmers, in actuality, don't care much about 2x speed
differences. You can make arguments about the speed of computers, or
Moore's law, or what have you, but the evidence is that being 2x slower than
the competition language isn't a signifigant detriment to being adopted as a
language (see the success of Ruby, Python, etc.- which are *demonstratably*
slower than C/C++, but not enough slower than many people care).
2) Multithreading. See my comments on pure-functional as a key component to
super-multithreading. If language 1 implements the solution
single-threaded, but 10x faster, while language 2 implements the solution
multi-threaded and can use 10 CPUs, but 10x slower, then given 10 CPUs the
two implementations are equally fast. If 20 CPUs are available, and the
second algorithm can use them, then suddenly the second algorithm is 2x
faster.
The base of the logarithm is important in this case, because it changes how
much loss I have to make up (if any). If the base of the lograthim is 16
instead of 2, a 4,096 node tree is only 3x slower than an array, and a 1
million node tree is only 5x slower. Probably even less than that, because
the first couple of levels will almost certainly be in cache (under heavy
use), and thus be cheap compared to the cache-miss.
>The next big thing in that vein is hash table resizing. It's
>astonishling rare that hash tables are grown by factors instead of by
>increments.
Especially considering that it's only by growing by factors do you keep O(1)
behavior- resizes need to keep getting progressively rarer, otherwise their
cost dominates.
>> By the way, I have read Erwig's papers. With a built-in (imperitive?) ufold
>> and gfold, his method is a constant factor slower than array-based (about
>> 2-fold). But with the non-built-in function, he's at best O(N log N), and
>> for functionalized gfold, it looks like O(N^2).
>I haven't read that deeply. My reasoning comes from another line of thought:
>O(N^2) shouldn't be required. In general, there's always a way to go
>from imperative to functional with no more than an additional O(log N)
>factor, so that O(N^2) figure should come from either a bad algorithm or
>an error somewhere along the line.
Well, it's O(N) (when array based) algorithms getting turned into O(N^2)
algorithms in some worst-case scenarios. I can always implement them in O(N
log N), using Erwig's ideas. I just don't see how to get to O(N) without
arrays.
Brian
Ulrich Hobelmann
> 2) Multithreading. See my comments on pure-functional as a key component to
> super-multithreading. If language 1 implements the solution
> single-threaded, but 10x faster, while language 2 implements the solution
> multi-threaded and can use 10 CPUs, but 10x slower, then given 10 CPUs the
> two implementations are equally fast. If 20 CPUs are available, and the
> second algorithm can use them, then suddenly the second algorithm is 2x
> faster.
Sun's new architecture has 32 threads running on one die, with
"acceptable" power dissipation, so maybe it isn't the worst decision...
--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra
Bob Hairgrove
wrote:
Yes, he even got someone to feed him ... you!
--
Bob Hairgrove
NoSpam...@Home.com
alex...@gmail.com
> alex...@gmail.com wrote:
> > Any ideas that pure-functional programming (a raison d'etre of Haskell)
> > is practical, can be quickly foiled by Stepanov's graph argument:
> > "change this vertex in this graph". If you would trade tangibles for
> > ideology and style, use Haskell. I don't think there is any more to
> > discuss here.
>
> seem to prefer jumping into conclusions. (I don't know whether Stepanov
> tried to make the same argument or you just misinterpreted him.)
>
> To clarify: it's perfectly possible (and not particularly hard) to
> implement pure graphs with logarithmic vertex and edge insertion and
> removal. Hint: adjacency maps.
O(log(N)) is possible, but not for N = number of verteces, not on the
data structure you are suggesting.
If you have a dense graph with N verteces and O(N^2) edges, and you
need to replace all inbound edges, you will need to replace O(N)
inbound edges, each taking O(log(N)) time. Total: O(N * log(N))
Compare this with O(1) complexity, if you are using C++.
Even if the graph is not dense, with O(N) total memory consumption,
your worst case complexity can still be O(N * log(N)) if you are
modifying a well-connected vertex.
alex...@gmail.com
> I've looked at the BOOST library. This can be done just as easily under
> Ocaml.
Assuming that you are genuinely failing to understand (even though the
issue has been discussed in this thread many already), I'll give you a
specific example illustrating how ML modules are weaker than C++
templates, using your own example.
You proposed:
<QUOTE>
module type Req = sig
(* Those functions I depend on the data structure to provide *)
type 'a t (* The type of the data structure *)
val length : 'a t -> int
val get : 'a t -> int -> 'a
end
module Make(DS: Req) = struct
let my_algo ds = ...
end
Then you could do:
module My_array = struct
type 'a t = 'a array
let length = Array.length
let get = Array.get
end
(* Implement my algorithm on arrays *)
module My_algo_array = Make(My_array);;
module My_list = struct
type 'a t = 'a list
let length = List.length
let get = List.nth
end
(* Implement my algorithm on lists *)
module My_algo_list = Make(My_list);
</QUOTE>
Now would you please use your algorithm on my module:
module My_string = struct
type t = string
let length = String.length
let get = String.get
end
Uh? Get it? The analogous example will work in C++.
If you still don't get it, after all this, ask Vesa or Andreas, or
OCamlGraph authors. I think they get the typing issue.
Lauri Alanko
<alex...@gmail.com> wrote:
> Now would you please use your algorithm on my module:
>
> module My_string = struct
> type t = string
> let length = String.length
> let get = String.get
> end
>
> Uh? Get it? The analogous example will work in C++.
This is pretty trivial. Currently the container type is required to be
polymorphic, for no good reason. It can simply be changed to be
monomorphic with a specific element type, and everything will work.
See http://www.standardml.org/Basis/mono-array.html
Lauri
Benjamin Franksen
> Even for low-level stuff, functional approaches can be used to
> advantage. The hallmark example is the FFTW package. It takes a few
> parameters (matrix size etc.) and generates C code that does the optimum
> Fast Fourier Transform for that specific set of parameters.
> If would be conceivable to extend this kind of code generation. Let me
> imagine something that's not even reasonable today: a system where
> hardware drivers are just a bunch of specifications (accessing *this*
> hardware registers has *that* effect), and the OS takes those
> specifications and generates the appropriate driver code on the fly.
> (This idea probably won't work as described, but I can imagine several
> variations that would. Just imagine an entire programming language
> working "the STL way" - FPLs are already there.)
You might find this paper quite interesting (and encouraging):
http://citeseer.ist.psu.edu/kiselyov04relating.html
Ben
alex...@gmail.com
Lauri Alanko wrote:
> In article <1137711710.4...@g47g2000cwa.googlegroups.com>,
> <alex...@gmail.com> wrote:
> > Now would you please use your algorithm on my module:
> >
> > module My_string = struct
> > type t = string
> > let length = String.length
> > let get = String.get
> > end
> >
> > Uh? Get it? The analogous example will work in C++.
>
> This is pretty trivial. Currently the container type is required to be
> polymorphic, for no good reason. It can simply be changed to be
> monomorphic with a specific element type, and everything will work.
But then it won't work with polymorphic containers. See OCamlGraph FAQ.
Did you miss it earlier in the thread?
-----
Q: I have a graph implementation with polymorphic types for vertices or
edges
and thus I can't apply the algorithms functors
A: Here we bump into ocaml's type system limitations: the number of
type
parameters must be know when the functor is written and the simplest
choice for us was to assume no type parameter at all. (This is
exactly the
same for functors Set.Make or Map.Make from ocaml standard library.)
As a (bad) workaround, you can copy the functor body and substitute
your
own functions for the functor arguments.
-----
Lauri Alanko
> Q: I have a graph implementation with polymorphic types for vertices or
> edges and thus I can't apply the algorithms functors
They can, however, be applied to monomorphic instantiations of the
graph, although this requires some wrapper modules. The only thing you
lose is type inference, as you have to create each instantiation
explicitly. Granted, it may become something of a mess, but shouldn't
create unsurmountable problems. Especially if you have first-class
functors.
Lauri
Lauri Alanko
Lauri Alanko <l...@iki.fi> wrote:
> create unsurmountable problems. Especially if you have first-class
> functors.
_Higher-order_ functors, I meant. Must be getting sleepy.
Lauri
alex...@gmail.com
> In article <1137714513.9...@g43g2000cwa.googlegroups.com>,
> <alex...@gmail.com> wrote:
> > But then it won't work with polymorphic containers. See OCamlGraph FAQ.
>
> > Q: I have a graph implementation with polymorphic types for vertices or
> > edges and thus I can't apply the algorithms functors
>
> They can, however, be applied to monomorphic instantiations of the
> graph, although this requires some wrapper modules.
Let's say your job is to write a sorting algorithm on sequences, and
supply it to everyone who needs sorting. My job is to develop some
polymorphic type (in ML lingo; a template class in C++ lingo) and give
it to Bill. I can't use your monomorphic code in my polymorphic
library. I have to COPY-AND-PASTE-AND-EDIT it instead.
This kind of nonsense is what C++ templates let you avoid. I suggest
reading OCamlGraph FAQ, and when you are done with that, read Modern
C++ Design by Alexandrescu. Educate yourself.
Thant Tessman
>
> Let's say your job is to write a sorting algorithm on sequences, and
> supply it to everyone who needs sorting. My job is to develop some
> polymorphic type (in ML lingo; a template class in C++ lingo) and give
> it to Bill. I can't use your monomorphic code in my polymorphic
> library. I have to COPY-AND-PASTE-AND-EDIT it instead.
>
> This kind of nonsense is what C++ templates let you avoid. I suggest
> reading OCamlGraph FAQ, and when you are done with that, read Modern
> C++ Design by Alexandrescu. Educate yourself.
You've thoroughly demonstrated that you don't actually understand the
criticisms you think you're leveling at languages like SML. My advice to
you is to learn enough about functional programming to understand how to
solve the problem you describe without ever resorting to the module
language in the first place, and without giving up static type safety.
Hint: You can pass in a fully type-specified "before" function as an
argument to a fully generic sort function.
Once you've proved to us that you understand how to do this, then we can
have a civilized conversation. And BTW, yes you can do this in C++ too,
but in comparison it's a complete pain-in-the-ass.
-thant
--
"When fascism comes to America, it will be wrapped in the flag and
carrying the cross." -- Sinclair Lewis, "It Can't Happen Here" (1935)
Hermann Jurksch
>>
> O(log(N)) is possible, but not for N = number of verteces, not on the
> data structure you are suggesting.
> If you have a dense graph with N verteces and O(N^2) edges, and you
> need to replace all inbound edges, you will need to replace O(N)
> inbound edges, each taking O(log(N)) time. Total: O(N * log(N))
> Compare this with O(1) complexity, if you are using C++.
If you change the graph, the time complexity is not O(1), even
if you are using C++.
If you change only an attribute of a vertex, the time complexity
in functional languages is not O(N*log(N)).
Regards
Hermann
alex...@gmail.com
> Hint: You can pass in a fully type-specified "before" function as an
> argument to a fully generic sort function.
Hint 1: I knew about the ML type system limitations (which Vesa and
Andreas also grokked, but not yourself, Brian or Lauri, as witnessed by
your, Brian's and Lauri's embarrassing "examples" trying to show how to
do what C++ does, using ML modules.
Hint 2: I knew who Jeremy Siek was, whose authorship of BGL appeared
like a miraculous coincidence to you.
Hint 3: Whereas Brian claimed that generic programming does not work, I
showed him fine and widely used examples of software engineering, where
it does.
Perhaps I know more about ML, C++ and generic programming than you do.
You ever thought of that?
Thant Tessman
Okay, fine. So write a sort function in your favorite functional
programming language and post it here.
-thant
--
"Government is a broker in pillage, and every election is sort of an
advance
auction sale of stolen goods." -- H.L. Mencken
alex...@gmail.com
> understand how to solve the problem you describe without ever resorting to
> the module language in the first place
QUOTE: "SML's modules support the kind of data-structure
interchangeability you suspect they do. "
Here's where you make the claim:
http://groups.google.com/group/comp.lang.ml/msg/4642a2ff113e04ec
> So write a sort function in your favorite functional
> programming language and post it here.
Why? You've claimed that you could do what Stepanov did in STL, using
ML *modules* . I've already shown, again and again, that you can't do
it because of type system limitations in ML.
You claimed it, when you argued with Stepanov in 1997, when you tried
to tutor Siek in 2001, and you did it earlier in the thread.
Here's where you insult Alex Stepanov, who's like 1,000 times smarter
than you, and has 1,000,000 times more class:
http://groups.google.com/group/comp.lang.functional/msg/11af16e20b3b9424
It seems you haven't grown up since 1997. This conversation is over.
Brian Hurt
>Brian Hurt wrote:
>You proposed:
><QUOTE>
>Then you could do:
>module My_algo_list = Make(My_list);
></QUOTE>
Congratulations. Strings can't hold any type- they can only hold chars.
The proper equivelent implementation would be:
module type Req = sig
type m (* type held by the sequence *)
type t (* type of sequence holding type m's *)
val length : t -> int
val get : t -> int -> m
end;;
module Make(DS:Req) = struct
...
end;;
module IntArray = struct
type m = int
type t = int array
let length = Array.length
let get = Array.get
end
module IntArrayAlgo = Make(IntArray);;
module FloatArray = struct
type m = float
type t = float array
let length = Array.length
let get = Array.get
end
module FloatArrayAlgo = Make(FloatArray);;
module MyString = struct
type m = char
type t = string
let length = String.length
let get = String.get
end;;
module StringArrayAlgo = Make(MyString);;
Of course, the pain in this, as I've shown, is that you can't use one
implementation of the functor for all arrays. In my original
implementation, arrays of ints and arrays of floats use the same code. But
you can't do that in C++ either- every array of a different type will
trigger a new copy of the code.
Brian
Brian Hurt
>Thant Tessman wrote:
>> Hint: You can pass in a fully type-specified "before" function as an
>> argument to a fully generic sort function.
>Hint 1: I knew about the ML type system limitations (which Vesa and
>Andreas also grokked, but not yourself, Brian or Lauri, as witnessed by
>your, Brian's and Lauri's embarrassing "examples" trying to show how to
>do what C++ does, using ML modules.
See previous article.
Also, please provide why the hell I'm wanting to sort the characters in an
array. I will grant that the normal implementation an Ocaml programmer
would implement would not allow you to sort strings (arrays of char, yes,
but strings are not arrays of char). And I'm not sure this is a loss. It's
fairly trivial to write functions that convert strings to arrays or lists of
char, and back again.
>Hint 3: Whereas Brian claimed that generic programming does not work, I
>showed him fine and widely used examples of software engineering, where
>it does.
Bwuh? When did I claim that? Template work- they don't work *well*, mind
you, but they work. My reaction is not unlike that of a long-time BMW
driver driving his first Yugo. It runs (mostly), yeah...
>Perhaps I know more about ML, C++ and generic programming than you do.
>You ever thought of that?
Perhaps you don't know as much about ML as you think you do? You ever
thought of that?
Brian
Vesa Karvonen
[...]
> Uh? Get it? The analogous example will work in C++.
Actually, C++ has the same kind of distinction. Consider the difference
between the below two templates:
template<template<class> class DS, class T>
void my_algo(DS<T> ds) { /*...*/ }
template<class DS>
void my_algo(DS ds) { /* ... */ }
In the former template, DS is (in SML parlance) a type constructor.
In the latter template, DS is a type. The former template can not be
used with a monomorphic data structure. For example, suppose you have
the class (not a class template)
class MyString { ... }
then you can't use the former my_algo template with it.
Of course, this "problem" can be "solved" (or avoided) using traits
and [partial] specialization in C++. Using those techniques, you
wouldn't have the former version of the my_algo template. However,
these solutions do have their own problems. One problem is that
anyone can break any template by introducing a specialization, which
can be done anywhere. Also, you have to be very careful to #include
the proper specializations for template code to work correctly.
Managing template specializations is a non-trivial problem and can
cause a lot of headaches. This was a non-exhaustive explanation; much
more could be said on these matters.
-Vesa Karvonen
Andreas Rossberg
>
> module type Req = sig
> (* Those functions I depend on the data structure to provide *)
> type 'a t (* The type of the data structure *)
> val length : 'a t -> int
> val get : 'a t -> int -> 'a
> end
>
> module Make(DS: Req) = struct
> let my_algo ds = ...
> end
> Now would you please use your algorithm on my module:
>
> module My_string = struct
> type t = string
> let length = String.length
> let get = String.get
> end
>
> Uh? Get it? The analogous example will work in C++.
No, it won't. The analogous example would be
template <template<class A> Req_t>
class Make {
public:
template <class T>
static void my_algo(Req_t<T> ds) {...}
}
class My_string {
string &_s;
public:
My_string(string &s) : _s(s) {}
int length() { return _s.length(); }
char get(int i) { return _s[i]; }
}
My_string s(...);
Make<???>::my_algo(s);
Ouch.
> If you still don't get it, after all this, ask Vesa or Andreas, or
> OCamlGraph authors. I think they get the typing issue.
Maybe, but maybe you are not fully understanding their arguments yet ;-).
--
Andreas Rossberg, ross...@ps.uni-sb.de
Let's get rid of those possible thingies! -- TB
Jon Harrop
> Yep. It's fairly easy to get ~10x slower, but basically impossible to get
> ~100x slower.
If he really knuckled down, I think Thomas Fischbacher could get 100x with
my ray tracer:
http://www.cip.physik.uni-muenchen.de/~tf/raytracer/ocaml.html
;-)
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html
Joachim Durchholz
> The base of the logarithm is important in this case, because it changes how
> much loss I have to make up (if any). If the base of the lograthim is 16
> instead of 2, a 4,096 node tree is only 3x slower than an array, and a 1
> million node tree is only 5x slower. Probably even less than that, because
> the first couple of levels will almost certainly be in cache (under heavy
> use), and thus be cheap compared to the cache-miss.
Well, if that really becomes a factor, a larger than binary fan-out in
the tree could become relevant. No doubt it will be programmed at that time.
>>The next big thing in that vein is hash table resizing. It's
>>astonishling rare that hash tables are grown by factors instead of by
>>increments.
>
> Especially considering that it's only by growing by factors do you keep O(1)
> behavior- resizes need to keep getting progressively rarer, otherwise their
> cost dominates.
Exactly.
>>>By the way, I have read Erwig's papers. With a built-in (imperitive?) ufold
>>>and gfold, his method is a constant factor slower than array-based (about
>>>2-fold). But with the non-built-in function, he's at best O(N log N), and
>>>for functionalized gfold, it looks like O(N^2).
>
>>I haven't read that deeply. My reasoning comes from another line of thought:
>>O(N^2) shouldn't be required. In general, there's always a way to go
>>from imperative to functional with no more than an additional O(log N)
>>factor, so that O(N^2) figure should come from either a bad algorithm or
>>an error somewhere along the line.
>
> Well, it's O(N) (when array based) algorithms getting turned into O(N^2)
> algorithms in some worst-case scenarios. I can always implement them in O(N
> log N), using Erwig's ideas. I just don't see how to get to O(N) without
> arrays.
Replace the array with an integer-to-content mapping, implemented as a tree.
Reading an entry is O(1) with arrays, O(log N) with trees.
Creating a version that has a single entry replaced is O(1) with arrays,
O(log N) with trees (the constant-factor overhead will be higher than
with reading, so it's still write-unfriendly).
Regards,
Jo