Wednesday, October 31, 2012

Programming by Homomorphism

In 1978 we proposed to exploit the idea of homomorphisms as a foundation for simplifying program design.
We framed the idea as a visual tool enabling to Program by Examples:

  • G. Attardi and M. Simi, Extending the Power of Programming by Examples, Proc. of SIGOA Conference on Office Information Systems, SIGOA Newsletter Vol. 3, Nos. 1 and 2, June 1982.

  • Nowadays, the idea has become popularl through the Map/Reduce programmig metaphor.
    Indeed Map/Reduce can be considered as a low level mechanism for running homomorphic transformations. It is a conveniet solution to parallelize processing over large amounts of data.
    Still it lacks some of the relevant features of homomorphims, i.e. an algebraic foundation, which would allow exploiting features of the homomorphic operators like simmetry and unit values, that can be exploited to optimize the performance.

    Simdoop is a preliminary attempt to provide support for homomorphisms on top of an Hadoop layer. 

    No comments: