4 ms·
If you are curious how does Abstract Algebra relate to software engineering, this book might be of your interest https://smile.amazon.com/Elements-Programming-
by adamnemecek 10y ago
If you are curious how does Abstract Algebra relate to software engineering, this book might be of your interest
https://smile.amazon.com/Elements-Programming-Alexander-Stepanov/dp/032163537X https://smile.amazon.com/Elements-Programming-Alexander-Step...
The main selling point of this approach is that it can cut out a lot of code
In this talk, Sean Parent, at that time working on Adobe Photoshop, estimated that the PS codebase could be reduced from 3,000,000 LOC to 30,000 LOC (=100x!!) if they followed ideas from the book
https://www.youtube.com/watch?v=4moyKUHApq4&t=10s https://www.youtube.com/watch?v=4moyKUHApq4&t=10s
Another point of his is that the explosion of written code we are seeing isn't sustainable and that so much of this code is algorithms or data structures with overlapping functionalities. As the codebases grow, and these functionalities diverge even further, pulling the reigns in on the chaos becomes gradually impossible.
Bjarne Stroustrup (aka the C++ OG) gave this book five stars on Amazon (in what is his one and only Amazon product review lol).
https://smile.amazon.com/review/R1MG7U1LR7FK6/ https://smile.amazon.com/review/R1MG7U1LR7FK6/
- RossBencina 10y agoI have not yet read "Elements of Programming," but there is another book "From Mathematics to Generic Programming," also co-authored by Alexander Stepanov, which links Abstract Algebra to program design. I found the latter very approachable: https://smile.amazon.com/Mathematics-Generic-Programming-Alexander-Stepanov/dp/0321942043 https://smile.amazon.com/Mathematics-Generic-Programming-Ale...
- stillworks 10y agoI always had a strong belief that principles of Group Theory must correlate into writing type systems. Just looked at the ToC of this book and there is an entire chapter on Groups in that book ! Not only Groups but also goes into Rings as well... Must read this book.
- RossBencina 10y agoIn a Group, every element has an inverse element. If you drop this property, you get a Monoid.[0] Functions under function composition form a Monoid (or Monoidal Category). Brian Beckman did a nice intro video to this at MS Channel 9 a few years back.[1] [0] https://en.wikipedia.org/wiki/Monoid https://en.wikipedia.org/wiki/Monoid [1] "Brian Beckman: Don't fear the Monad" https://www.youtube.com/watch?v=ZhuHCtR3xq8 https://www.youtube.com/watch?v=ZhuHCtR3xq8
- tel 10y agoGroupoids, a generalization of groups, factor heavily into type theory!
- empath75 10y agoI think what you want is Category Theory.
- charlieflowers 10y agoQuestion -- clearly, when you look at Haskell, you see abstract algebra. Were Stepanov's ideas big influencers of Haskell, or vice versa, or neither?
- RossBencina 10y agoStepanov and Musser were working on generic programming in the 80s[0][1], which predates Haskell. I suspect parametric polymorphism was common in the FP world by that time, but I don't know whether it was used as an organising principle to the extent that Stepanov promotes. [0] https://en.wikipedia.org/wiki/Alexander_Stepanov https://en.wikipedia.org/wiki/Alexander_Stepanov [1] https://en.wikipedia.org/wiki/David_Musser https://en.wikipedia.org/wiki/David_Musser
- mpweiher 10y agoNote: apparently both Sean Parent and Bjarne Stroustrup contributed to the book, so their evaluation may not be entirely unbiased. Still sounds interesting.
- contravariant 10y agoThe book 'The science of programming' of David Gries is also a nice introduction to writing programs using mathematical logic and reasoning. The book is inspired by the techniques of Dijkstra and Hoare, and written in a way that's easy to follow.
- miloshadzic 10y agoJeez, was about to buy it but it's about 90. What's the deal with this pricing?
- KurtMueller 10y agoI did a google search of the book and found a pdf as the first result: http://blg89.net/blog/wp-content/uploads/2013/11/The-Science-Of-Programming-Gries-038790641X.pdf http://blg89.net/blog/wp-content/uploads/2013/11/The-Science...
- happynewyear 10y agoI guess this is a whimsical aside/ I looked that up and got this sample of that book: http://www.cs.cornell.edu/courses/CS5860/2011fa/documents/Gries-WhyUseLogic-Aug25.pdf http://www.cs.cornell.edu/courses/CS5860/2011fa/documents/Gr... Looking up Stepanov's book, landed on his slide deck about the book. Interestingly enough, both are about the remainder algorithm, and Gries' mentions a "large program" of "3000 lines", which reminded me of the other comment and the 3000000 to 30000 figure. [Stepanov's deck: http://stepanovpapers.com/EoP-StanfordEE380.pdf http://stepanovpapers.com/EoP-StanfordEE380.pdf]
- stiff 10y agoestimated that the PS codebase could be reduced from 3,000,000 LOC to 30,000 LOC (=100x!!) I challenge anyone making such claims to construct an even _moderately_ realistic example of where such reduction would be possible. Here is a very simple and already very optimistic model that is still way below a 100x reduction: say my program consists nearly exclusively of sorting of various arrays and I write out bubble sort in full each time using for loops etc. rather than call a sort() procedure. Bubble sort takes roughly 20 lines of code to implement, so I would at best get a reduction of close to a 20x, rather than a 100x one.
- catnaroek 10y agoI'd expect more opportunities for reduction in code size to arise when you use fancy algorithms (not sorting) on generic algebraic structures that have many models in your program. For example, when I was a student, I implemented a library of numerical methods for my own use in class. It benefited a lot from being implemented as generically as possible. That being said, a 100x reduction in code size seems like an exaggeration.
- Someone 10y agoI doubt the 100x range, too, but Photoshop is decades old and, likely, has lots of its filters written in assembly for speed, with zillions of variants for all kinds of sometimes long gone CPUs and GPUs. It also still may have its own memory manager. It that is true, it should be possible to get large wins in LOC if one either is willing to give up orders of magnitude in speed and memory usage, or is equipped with a sufficiently advanced compiler. There likely also is some room for improvement if one is willing to change the file format (.psd is not known for its consistency), but that would likely be a rounding error.
- jules 10y agoI don't doubt that your conclusion is correct, but what if the sort is used in 10 other functions, each of which is used 10 times? If you inlined everything you would end up with 100 copies of bubble sort. The code blowup is exponential in the level of nesting.
- 10y ago
- nerdponx 10y agoSorry for a fluff comment, but +1 for using Amazon Smile links.