Re: Generic Programming

Discussion in 'C++' started by alex.gman@gmail.com, Jan 17, 2006.

  1. Guest

    Thant Tessman wrote:
    > wrote:
    > > Thant Tessman wrote:
    > >
    > >> 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.
    , Jan 17, 2006
    #1
    1. Advertising

  2. Paul Rubin Guest

    writes:
    > * 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?
    Paul Rubin, Jan 17, 2006
    #2
    1. Advertising

  3. Guest

    You might also be interested in a comparative study of generics in
    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.
    , Jan 17, 2006
    #3
  4. wrote:

    [...]

    > 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, Jan 17, 2006
    #4
  5. I (Thant Tessman) wrote to alex.gman:

    >> 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
    Thant Tessman, Jan 17, 2006
    #5
  6. 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.

    Best regards
    Tomasz

    --
    I am searching for programmers who are good at least in
    (Haskell || ML) && (Linux || FreeBSD || math)
    for work in Warsaw, Poland
    Tomasz Zielonka, Jan 17, 2006
    #6
  7. Guest

    Tomasz Zielonka wrote:
    > 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."

    http://www.sgi.com/tech/stl/drdobbs-interview.html
    , Jan 17, 2006
    #7
  8. wrote:
    > Tomasz Zielonka wrote:
    >> 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++.

    Best regards
    Tomasz

    --
    I am searching for programmers who are good at least in
    (Haskell || ML) && (Linux || FreeBSD || math)
    for work in Warsaw, Poland
    Tomasz Zielonka, Jan 18, 2006
    #8
  9. Luke Meyers Guest

    Paul Rubin wrote:
    > 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
    Luke Meyers, Jan 18, 2006
    #9
  10. Guest

    Tomasz Zielonka wrote:
    > wrote:
    > > Tomasz Zielonka wrote:
    > >> 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?
    , Jan 18, 2006
    #10
  11. wrote:
    >> 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.

    Best regards
    Tomasz

    --
    I am searching for programmers who are good at least in
    (Haskell || ML) && (Linux || FreeBSD || math)
    for work in Warsaw, Poland
    Tomasz Zielonka, Jan 18, 2006
    #11
  12. Guest

    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.
    , Jan 18, 2006
    #12
  13. Paul Rubin Guest

    writes:
    > 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?
    Paul Rubin, Jan 18, 2006
    #13
  14. 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.


    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
    Thant Tessman, Jan 18, 2006
    #14
  15. 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.


    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, -sb.de

    Let's get rid of those possible thingies! -- TB
    Andreas Rossberg, Jan 18, 2006
    #15
  16. 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.


    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.

    http://haskell.org/hawiki/TheZipper
    Greg Buchholz, Jan 18, 2006
    #16
  17. 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".


    You (or he?) don't consider logarithmic time complexities
    practical?

    --
    Jens Axel S√łgaard
    =?ISO-8859-1?Q?Jens_Axel_S=F8gaard?=, Jan 18, 2006
    #17
  18. Yes, but I don't think one's typical problem is "change this vertex in
    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 :
    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)
    ------------------------------------------------------------------------------
    Chris F Clark, Jan 18, 2006
    #18
  19. On Tue, 17 Jan 2006 wrote:

    > 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, Jan 18, 2006
    #19
  20. On Wed, 18 Jan 2006 wrote:

    > 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".

    --


    A problem that's all in your head is still a problem.
    Brain damage is but one form of mind damage.
    Philippa Cowderoy, Jan 18, 2006
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Hung Jung Lu
    Replies:
    6
    Views:
    667
    Neal Gafter
    Nov 18, 2003
  2. Paul O'Grady
    Replies:
    19
    Views:
    692
    Patricia Shanahan
    Feb 18, 2005
  3. Murat Tasan
    Replies:
    1
    Views:
    8,007
    Chaitanya
    Feb 3, 2009
  4. Replies:
    2
    Views:
    407
  5. minlearn
    Replies:
    2
    Views:
    435
    red floyd
    Mar 13, 2009
Loading...

Share This Page