User loginNavigation 
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 highorder 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 ;) 
Browse archivesActive forum topics
New forum topics

Recent comments
2 days 13 hours ago
4 days 8 hours ago
2 weeks 1 day ago
3 weeks 13 hours ago
4 weeks 11 hours ago
5 weeks 5 days ago
6 weeks 1 day ago
7 weeks 2 days ago
7 weeks 5 days ago
7 weeks 5 days ago