C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Re: Generic Programming Goto page 1, 2, 3, 4, 5, 6  Next          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message alex.gman@gmail.com Guest Posted: Tue Jan 17, 2006 5:15 am    Post subject: Re: Generic Programming Thant Tessman wrote: Quote: alex.gman (AT) gmail (DOT) com wrote: Thant Tessman wrote: [email]alex.gman (AT) gmail (DOT) com[/email] 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 Quote: 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. Back to top Paul Rubin Guest Posted: Tue Jan 17, 2006 5:50 am    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] writes: Quote: * 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? Back to top ajkenn@gmail.com Guest Posted: Tue Jan 17, 2006 10:02 am    Post subject: Re: Generic Programming 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. Back to top Thant Tessman Guest Posted: Tue Jan 17, 2006 3:48 pm    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] wrote: [...] Quote: 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.) Quote: 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 Back to top Thant Tessman Guest Posted: Tue Jan 17, 2006 5:59 pm    Post subject: Re: Generic Programming I (Thant Tessman) wrote to alex.gman: Quote: 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 Back to top Tomasz Zielonka Guest Posted: Tue Jan 17, 2006 7:00 pm    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] wrote: Quote: 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 Back to top alex.gman@gmail.com Guest Posted: Tue Jan 17, 2006 9:05 pm    Post subject: Re: Generic Programming Tomasz Zielonka wrote: Quote: alex.gman (AT) gmail (DOT) 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." http://www.sgi.com/tech/stl/drdobbs-interview.html Back to top Tomasz Zielonka Guest Posted: Wed Jan 18, 2006 6:13 am    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] wrote: Quote: Tomasz Zielonka wrote: [email]alex.gman (AT) gmail (DOT) com[/email] 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? Quote: "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. Quote: 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. Quote: 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. Quote: 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 Back to top Luke Meyers Guest Posted: Wed Jan 18, 2006 6:31 am    Post subject: Re: Generic Programming Paul Rubin wrote: Quote: 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 Back to top alex.gman@gmail.com Guest Posted: Wed Jan 18, 2006 9:23 am    Post subject: Re: Generic Programming Tomasz Zielonka wrote: Quote: alex.gman (AT) gmail (DOT) com wrote: Tomasz Zielonka wrote: [email]alex.gman (AT) gmail (DOT) com[/email] 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? Back to top Tomasz Zielonka Guest Posted: Wed Jan 18, 2006 10:04 am    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] wrote: Quote: 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). Quote: 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. Quote: 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). Quote: 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 Back to top alex.gman@gmail.com Guest Posted: Wed Jan 18, 2006 2:12 pm    Post subject: Re: Generic Programming 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. Back to top Paul Rubin Guest Posted: Wed Jan 18, 2006 4:07 pm    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] writes: Quote: 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? Back to top Thant Tessman Guest Posted: Wed Jan 18, 2006 4:09 pm    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] wrote: Quote: 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 Back to top Andreas Rossberg Guest Posted: Wed Jan 18, 2006 4:32 pm    Post subject: Re: Generic Programming [email]alex.gman (AT) gmail (DOT) com[/email] wrote: Quote: 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, [email]rossberg (AT) ps (DOT) uni-sb.de[/email] Let's get rid of those possible thingies! -- TB Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Goto page 1, 2, 3, 4, 5, 6  Next Page 1 of 6   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.