Comment by adamnemecek | Hacker News Reader

Comment by adamnemecek | Hacker News Reader

I've been recently trying to make my way though Elements of Programming (https://www.amazon.com/Elements-Programming-Alexander-Stepan...) by Alexander Stepanov and Paul McJones and it makes me say abstract algebra. It's the first and only rigorous foundation of software engineering that I've seen. It basically maps abstract algebra to this somewhat simple subset of C++, introduces new algebraic objects (such as memory) and then shows this really nice correspondence between the the C++-- and the abstract algebra.

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.

Favorite Stepanov quote below - apparently mixing mathematics and bad fish is quite potent:

Question: 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?

Answer: 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:

http://www.stlport.org/resources/StepanovUSA.html

I just picked this up after having finished 'From Mathematics to Generic Programming' which is a ride in the park compared to what you're reading now. Looking forward to the task of slowly working my way through it.

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

Giving devs a way out of ObjC is a pretty big draw :).

I'm using a very similar approach in the design of my library of data structures and algorithms:

(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++.

Keean Schupke has started to explore the Elements of Programming in Rust. See: http://lambda-the-ultimate.org/node/5330

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.

Good ideas are often reinvented by different people in different contexts: An STL concept is a type class equipped with laws is an algebraic variety. Universal algebra tells us that we can gain a lot from paying attention not just to individual varieties in isolation, but also to homomorphisms of varieties, which translated back to programming languages correspond to bootstrapping data structures from simpler ones in a generic way.

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.

Reply on news.ycombinator.com