If you are not familiar with the author, Alexander Stepanov is the guy who basically figured out generic programming, was instrumental in the design of C++ templates and the C++ STL. C++ gets a lot of flak but templates are very powerful (if you disregard the complexity). I think that they are actually one of the main reasons why C++ is still relevant. Also I'm starting to think that generic programming might actually be the most powerful paradigm out there (this is just a hunch). This book doesn't take the middle road, only the low level (C++) and extreme high level (abstract algebra) and totally cuts out the middle part (aka boiler plate).
Funnily enough, this C++-like language actually translates very nicely to the modern C++ successors like Swift and Rust (or it seems, I'm in the progress of exploring this).
Has anyone here tried to explore the contents of this book in either Swift or Rust?
But remember that this is not an easy book, I've met very smart people who told me they read only a part of this and are still wrapping their heads around that.
What is the origin of STL? Has STL been conceived to be what it is now, that is "the" C++ Standard Library, or does it come from some other project? Could you tell us a history of STL?
In 1976, still back in the USSR, I got a very serious case of food poisoning from eating raw fish. While in the hospital, in the state of delirium, I suddenly realized that the ability to add numbers in parallel depends on the fact that addition is associative. (So, putting it simply, STL is the result of a bacterial infection.) In other words, I realized that a parallel reduction algorithm is associated with a semigroup structure type.
The full interview can be found at:
[Edit] Interested in Rust for the same reason, but I'm not attracted to Swift. It looks so much like Kotlin, I am not sure I understand the fuss over it other than it gives Apple devs a way out of ObjC.
Anyway, I am going full on Android now, not in the hopes of app money, but the sheer numbers of devices out there, Google's backing, and it is more of a hacker's platform than iOS. I will most likely try Kotlin again, and this will prepare me for any possible switch to Swift.
(0) The interface of an abstract data type (set, heap, etc.) is the signature of a variety in the universal algebra sense. Implementations are concrete algebras of this variety.
(1) Homomorphisms of varieties can be used to bootstrap abstract data types from simpler ones in a generic way. Chapter 10 of Okasaki's book “Purely Functional Data Structures” is entirely dedicated to this technique, although he doesn't make the connection to universal algebra.
But are also some differences:
(2) I'm using a functional programming language (Standard ML), rather than an imperative one (C++).
(3) I emphasize persistent data structures over ephemeral ones. I don't reject destructive updates that are compatible with persistence (e.g. laziness).
(4) I use algebraic data types to statically rule out unreachable code paths. Inexhaustive pattern matching is considered a bug. Raising an exception saying “this path was supposed to be unreachable” is also considered a bug. This would be at best very difficult to enforce in C++.
I know Alexander Stepanov personally, and Paul McJones through him, and they are both interested in seeing the ideas in the book implemented in other languages. Rust is a particularly compelling candidate, because it allows you to specify type constraints on generic functions through traits. This is similar in some ways to "concepts" which Alex has been hoping to see implemented in C++ for a very long time but which keeps getting kicked down the road.
Also, a while back, I reinvented InputIterators, OutputIterators and `std::copy` in a more type-safe way, using algebraic data types: https://github.com/eduardoleon/shit . (Sorry for the repo's name!) Although I only provide Standard ML and Scala implementations, this is perfectly doable in Rust as well. (In fact, my code is linearly typed, not just affinely typed.) The only requirements for a port to another language are parametric polymorphism and algebraic data types.