puntoblogspot: declarative programming

domingo, 12 de marzo de 2017

CTMCP finished!

After a big hiatus of 6 months (space for CLtL The unix programming environment, Object-Oriented Programming in Common LISP
,To mock a mockingbird (part of it) , I continued reading Concepts, Techniques, and Models of Computer Programming.

And it's so good I'm gonna put it next to SICP, GEB, HOP and PAIP (when I get around finishing it). Here are some highlights:

The book covers a huge spectrum of programming techniques, and ponders lots of variants and different ways of achieving different tasks. It focuses a lot in declarative programming, which comes very natural for extending the model to streams, logic, relational and constraint programming.
The whole book examples are written in Oz/Mozart, which is a multi-paradigm language with a Prolog-ish syntax which seemed quite odd in the beginning but in the end I learned to like.
The tone of the book is so unopinionated and so 'formal', that I missed Eva Lu Ator, and Alyssa P. Hacker.
I had a lovely AHA moment when discovering difference lists. Very useful to understand the paradigm shift of Prolog style programming.
Concurrency is touched quite heavily, and the explanations on why the different models exist, and when to use what were very useful from a practical perspective. I loved how they introduced Active Objects.
Explanations of 'well known' concepts like recusion, accumulators, mapcar, transducers, closures, and streams are very nice, and made me remember of the times I discovered them for the very first time.
Overall, the book is very readable. Clear style and vocab makes it readable in bed.
There's an introduction to Constraint Programming. Which feels like total magic. I guess it deserves reading a whole book on that to know a bit more about it.

Really, if you tried SICP and/or HOP and liked it, this book will provide 940 pages of fun and enlightenment.

Next, I'm reading PoEAA (a bit old and enterprisey but it's Fowler). And I have Beautiful Data (O'Reilly) waiting....

In CTM, around page 145, the authors talk about a list implementation called Difference Lists. At the abstract level, a dlist is just a list. an ordered list, that has constant time for pushing elements on the front, and a way to iterate over its elements, one by one. It's made of Conses, and the last cdr points to nil.

The difference with normal lists is that it provides -- thanks to the way how Oz (and prolog) can unify unbound variables -- a way to append 2 lists in constant time. The same principle, when applied can lead to very efficient implementations of operations like flatten or reverse, and this leads to efficient ways to code other datastructures like Queues.

I could try to explain how they work, and how you can achieve this performance speedups, but It's definately better if I just link to a few links, and then you skim them and realize how smart and mind bending it is to start thinking declaratively. :)

According to Clocksin: "probably one of the most ingeinous programming techniques ever invented yet neglected by mainstream computer science".