André van Delft
Independent computer science researcher
André van Delft is an independent computer science researcher in the Netherlands. He has studied Mathematics and Business Administration. He loves math and applies it in programming language extensions.
ACP and PGA: Two Algebraic Theories in Computer Science
This talk is about 2 fundamental algebraic theories in computer science that deserve much more attention than they currently get: the Algebra of Communicating Processes (ACP) and Program Algebra (PGA).
ACP is an algebraic process theory, initiated by Jan Bergstra and Jan Willem Klop in 1982. It builds on Kleene’s formal languages and automata of the 1950. ACP provides a solid algebraic approach, and adds high level constructs such as concurrency and communication. ACP has been made operational in SubScript, an extension to the Scala language, created by André van Delft (presented at Lambda Days 2015). Process lambda’s are supported like in Milner’s π-calculus; this enables a simple definition of dataflow constructs. I will outline some example applications in SubScript: a GUI controller and an “async” program.
In 1997 Jan Bergstra studied the semantics of Java programs and found out that the official language specification was of little help. He then started working on PGA: like the Turing machine this is a computational model, but based on simple algebraic laws concerning linear text specifications. PGA may be seen as a very low level assembly language with many goto’s; on this higher-level layers are be defined, even to the level of programming languages such as Ruby. I will briefly layout an application of PGA to reasoning about static variable initialization in Java, which is a known brainteaser.
Our field is flooded with more or less ad-hoc engineering solutions. Functional Programming is an exception to this, being strongly rooted in Lambda Calculus. ACP and PGA are similar Computing Science jewels. Students deserve to have these in their curricula; for CS researchers there is plenty of low hanging fruit.
For links to ACP and PGA see http://subscript-lang.org/
Video ←Back
