What Is Abstract Algebra? [video]

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

Question -- clearly, when you look at Haskell, you see abstract algebra. Were Stepanov's ideas big influencers of Haskell, or vice versa, or neither?

Jeez, was about to buy it but it's about 90. What's the deal with this pricing?

I 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/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]

I'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.

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

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

Reducing a single bubble sort in code size doesn't do much, because it is used many times and its code size cost is well amortized. However, if you had many bubble sorts coded in your program with special cases, then consolidating those into one very abstract/parametric version could be a big win.

The reduction comes from making the code way more abstract and much more difficult to reason about in concrete contexts. So ya, it is probably possible, but no, our heads might not be very capable in writing/maintaining/debugging such code even if the computer could execute it. As an extreme, consider "very small code" contests in the demo scene, where various crazy tricks (self modifying code) are used to drastically reduce code sizes, none of which would ever be used in practice and have little SE value.

Do you mean Michael Artin's Algebra? Just took his Algebra I (18.701) at MIT last semester. An incredibly challenging class, but he's a really excellent lecturer and a very likeable guy. Still really sharp.

I think watching something like this before watching a deep dive or reading a text book could be useful, just to give you kind of a lay of the land and some intuition.

I disagree very rarely does one explanation take that long. It can normally be built up by lots of little videos. Once someone has completely 10 videos on the basics you can do slightly longer ones that span the concepts and explains tradeoffs between techniques.

If you don't mind the chipmunk-voices, that could work :)