Does the conclusion boil down to "use functional programming"? The author doesn't specify the way data or functions are encapsulated in the final figure. But my gut reaction is that this describes FP better than OO or any other paradigm.
Not really, it's basically 'composition over inheritance', and laying out data structures in a cache-friendly way, and only then build the functions that work on those data structures (the common term is 'data-oriented design').
It's the mantra that game developers have been preaching for at least the last 5..10 years and which slowly makes its way into the general programming world, because the CPU/memory performance gap is getting wider, not narrower. The bitsquid engine blog (now: Autodesk Stingray engine) has a lot of really great articles on that topic (for instance http://bitsquid.blogspot.de/2014/08/building-data-oriented-e...).
No. Because the data structures he is referring to need not be immutable. Think "C struct". Structs in C are more closely aligned with components and lend themselves to composition much easier than a tower of inheritance. If you ever try Unity after bashing your head in with C++, you'll know what a godsend components are.
I admire the combination of theoretical audacity and sweeping pragmatism taken by the authors of that paper.
They mention Oz a few times. I am big fan of "Concepts, Techniques, and Models of Computer Programming" by Van Roy and Haridi, which shows the reader how different computing paradigms can be constructed from a kernel language in Oz. That makes the text something of a kindred spirit to the paper, insofar as it tries to aid the student in grasping many different paradigms of computation (functional, object-oriented, concurrent, and relational are covered).
The Haskell using folks at Standard Chartered Bank have been implementing some of the "Out of the Tarpit" ideas for a few years now. I can confirm, functional relational programming does work really well in practice.
