3 ms·
Category theorists have made this promise since the early 1990s, when the overlap between categorical methods and pure functional programming (think type theori
by GregarianChild 6y ago
Category theorists have made this promise since the early 1990s, when
the overlap between categorical methods and pure functional
programming (think type theories) became clear. The really big win
here was Moggi's discovery that monads neatly generalise many similar
ideas in programming. (Moggi/Plotkin should have won a Goedel award for this!) This led to a great deal of activity towards
generalising this to other forms of computation, in particular
parallel computing (key problem: generalise the beautiful
relationship between cut-elimination and beta-reduction in type
theory, to cut-elimination and parallel composition + hiding). In my
opinion, this has comprehensively failed to date, in the sense that
(A) while you can express some parallelism in a way that can be read as
a generalisation of cut-elimination / category theory, that is not
surprising since (simplifying a great deal for brevity) category
theory is a foundation of mathematics; but
(B) when you express non
purely functional computation categorically, you get extremely
complicated formal systems that obscure the fundamental simplicity of
what they abstract from and generally have only what they abstract
from as actual model of the abstraction.
Let's take Example 47 from the Native Type Theory paper: what exactly is the formal property the typing system induces? (The paper makes vague allusions to a "foreign function interface" with rho-calculus, but there is no published understanding of even the equational theory of rho-calculus. Why should I trust this paper?) What is the logic that the paper promises ("Native Type Theory gives provides a shared framework of reasoning")? What are the proof rules, so I can type them into Lean or Coq? Show me that they are better than the simple logics I get from looking at lambda-calculus operationally.
Each abstraction has costs and benefits. As of 2021, the costs of
categorical methods outside of pure functional languages outweigh
their benefits. I worked in categorical methods for programming and
changed the field, when I realised this.
- siraben 6y ago> generalise the beautiful relationship between cut-elimination and beta-reduction in type theory, to cut-elimination and parallel composition + hiding How would you generalize the correspondence between cut-elimination and beta-reduction to cut-elimination and parallel composition, and what is meant by hiding here? I would be curious to know of relevant work in the area.
- GregarianChild 6y agoThe generalisation of Curry-Howard to parallelism was outlined in early interpretations of linear logic, I think Abramsky's [1] was the first, there has been a lot more work in this direction since. A good place to start to understand the relationship between functional and concurrent computation is Milner's Functions as Processes [2], it's incredibly simple, my mind was blown when I understood it (if you understand CPS transforms, you will find it natural, indeed, I'd say the Milner translation is the essence of CPS, see also [4]). A Curry-Howard correspondence of sorts has now been produced for linear logic and session-typable name passing processes [3]. [1] S. Abramsky, Computational Interpretations of Linear Logic. https://www.sciencedirect.com/science/article/pii/030439759390181R https://www.sciencedirect.com/science/article/pii/0304397593... [2] R. Milner, Functions as Processes. https://hal.inria.fr/inria-00075405/document https://hal.inria.fr/inria-00075405/document [3] L. Caires, F. Pfenning, Session Types as Intuitionistic Linear Propositions. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.220.3453&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.22... [4] H. Thielecke, Continuations, functions and jumps. https://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf https://www.cs.bham.ac.uk/~hxt/research/Logiccolumn8.pdf
- siraben 6y agoThanks! What sort of work did you do in the field of applying categorical methods to programming?