One is often amazed that, once two functions are identified as a Galois connection, a long list of nice and often useful properties follow from one concise, elegant defining equation. But how does one construct a program from a specification given as a Galois connection?
Shin-Cheng Mu and José Nuno Oliveira. Programming from Galois connections — principles and applications. Technical Report TR-IIS-10-009, Academia Sinica, December 2010.
Shin-Cheng Mu and José Nuno Oliveira. Programming from Galois connections. In the 12th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS #12), LNCS 6663, pages 294-313. May 30 – June 3, 2011.
Shin-Cheng Mu, Yu-Han Lyu, and Akimasa Morihata. Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning. In the 6th ACM SIGPLAN workshop on Generic programming (WGP 2010), pages 97-108, Sep. 2010. [PDF]
I had a chance to show the students, in 25 minutes, what functional program calculation is about. The student have just been exposed to functional programming a week ago in a three-hour course, and I have talked to them about maximum segment sum way too many times.
Given an array of integers having at least two elements, compute the sum of squares of the difference between all pairs of elements. It is not hard to quickly write up a
O(N²) program using nested loops, which, I have to confess, is what I would do before reading Kaldewaij’s book and realised that it is possible to do the task in linear time using one loop.
In the recent work of Sharon and me on maximally dense segments we needed quite a number of functions to be monotonic, idempotent, etc. It only occurred to me after submitting the paper: could they be defined as Galois connections?
Sharon and I have finally concluded, for now, our work on the maximally dense segment problem (download the draft here), on which we have been working on and off for the past two years. Considering the algorithm itself and its derivation/proofs, I am quite happy with what we have achieved. The algorithm is rather complex, however, and it is a challenge presenting it in an accessible way. Sharon has done a great job polishing the paper, and I do hope more people would be interested in reading it and it would, eventually, inspire more work on interesting program derivations.
Sharon Curtis and Shin-Cheng Mu. Functional pearl: maximally dense segments. Submitted.
In a previous paper of mine, regrettably, I wrongly attributed the origin of the maximum segment sum problem to Dijkstra and Feijen’s Een methode van programmeren. In fact, the story behind the problem was told very well in Jon Bentley’s Programming Pearls.
I learned the function derivation of the maximum segment sum problem from one of Jeremy’s papers and was very amazed. It was perhaps one of the early incident that inspired my interest in program calculation.