Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Towards a linear algebra of programming
Oliveira J. Formal Aspects of Computing24 (4-6):433-458,2012.Type:Article
Date Reviewed: Jul 29 2014

We are, by now, quite used to relational interpretations of program semantics. Such interpretations live in a rich algebraic world. What if we wanted to use a probabilistic interpretation instead? Well, it turns out that this is a conservative extension of the relational setting, and the algebraic formalism smoothly extends. Unsurprisingly, given the title, the key is linear algebra.

After a brief review of typed linear algebra, relation algebra, and their interrelation, the author introduces a crisp formalism for doing elementary probability theory with linear algebra. This formalism is then leveraged to develop an elegant (point-free) calculus for probabilistic functions, well illustrated with relevant examples. Lastly, this is applied to finding faults in certain programs, namely those expressible as folds. This gives a method to evaluate the quantitative impact of faults in such programs.

This paper is superbly written. Given the amount of mathematics involved, including many full proofs, one expects leaden, dense text. But no, the author goes to great lengths to motivate and illustrate everything, without ever being imprecise or overly verbose.

Reviewer:  Jacques Carette Review #: CR142562 (1410-0878)
Bookmark and Share
  Editor Recommended
Featured Reviewer
 
 
Numerical Algorithms (G.1.0 ... )
 
 
Algebraic Algorithms (I.1.2 ... )
 
 
Math (I.7.2 ... )
 
 
Mathematical Software (G.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms": Date
Performance evaluation of programs related to the real gamma function
Cody W. ACM Transactions on Mathematical Software 17(1): 46-54, 1991. Type: Article
Oct 1 1991
Plotting contour surfaces of a function of three variables
Sewell G. ACM Transactions on Mathematical Software 14(1): 33-41, 1988. Type: Article
Oct 1 1988
Polynomial evaluation with scaling
Hansen E., Patrick M., Wang R. ACM Transactions on Mathematical Software 16(1): 86-93, 1990. Type: Article
May 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy