Theory in Programming Practice

✨ Summary

Summary

Theory in Programming Practice is a set of course notes presenting practical applications of computer-science theory. It covers lossless compression through Huffman and Lempel–Ziv coding; error detection and correction using parity, Hamming, and Reed–Muller codes; cryptographic concepts including RSA, digital signatures, oblivious transfer, and Diffie–Hellman key exchange; finite-state machines, transducers, regular expressions, and structured state machines; recursive and functional programming in Haskell; relational data models and query optimization; exact string-matching algorithms including Rabin–Karp, Knuth–Morris–Pratt, and Boyer–Moore; and powerlists for expressing and reasoning about recursive parallel algorithms.

The central methodological theme is that formal structures, algebraic laws, invariants, induction, and abstraction can reduce implementation effort while supporting correctness arguments and efficiency analysis. The final chapter develops powerlists as a recursive data structure for parallel computation and uses them to give compact formulations of permutations, prefix sums, Gray codes, FFT, and parallel sorting.

The document is primarily an educational text rather than a conventional research paper. Its most identifiable research influence is the powerlist framework. Misra’s powerlist work was subsequently extended to hypercube-oriented parallel algorithms and additional list structures by Kornerup and collaborators. (researchgate.net) Powerlist algebra was also mechanically formalized in ACL2, including correctness studies of Batcher sorting, prefix sums, FFT-related algorithms, Gray codes, and adders. (cs.uwyo.edu) Later work continued to describe PowerLists as a high-level abstraction for recursive, data-parallel algorithms and applied the ideas to parallel-programming frameworks. (scitepress.org) The University of Texas course materials confirm that the text was used as the textbook for CS 337, whose stated goal was to demonstrate applications of theory in practical programming. (cs.utexas.edu)