Home

Ralf Hinze: An algebra of scans

Ralf Hinze. An algebra of scans. Proceedings of the Seventh International Conference on Mathematics of Program Construction (MPC 2004).

In this paper we show that parallel prefix circuits enjoy a very pleasant algebra. Using only two basic building blocks and four combinators all standard designs can be described succinctly and rigorously. The rules of the algebra allow us to prove the circuits correct and to derive circuit designs in a systematic manner.

Parallel prefix computations, or scans if you speak APL, determine the sums of all prefixes of a given sequence. Obviously the term sum is used loosely: scan is a high-order function, and any associative operation can be used. In J talk scan is an adverb.

I wonder when we will be seeing courses called Algebra Design in Computer Science departments around the world...

Ah right, just after all universities offer language design courses ;-)

By Ehud Lamm at 2004-10-20 21:33 | Functional | other blogs | 7884 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Seems unaware of Yves Lafont's work...

...when he claims that one cannot do useful algebraic manipulations on graphical representations. Lafont's theory of algebraic manipulations, although possibly not supporting the same generality of assocaitive algebras, does go beyond the boolean cicuits he names, and are strikingly well-behaved.

I generally like Hinze's work, but he's not being very conscientious in his literature search here.

[1]Y. Lafont, Towards an Algebraic Theory of Boolean Circuits, Journal of Pure and Applied Algebra 184 (2-3), p. 257-310 (2003)

By Charles A Stewart at Fri, 2004-10-22 13:06 | login or register to post comments