Hacker News new | ask | show | jobs
by mafribe 4023 days ago
Maybe the author plans to write about it in later parts of the article, but it's misleading to assume that (1) there is no work on types for interacting processes and (2) that types always have to be based on some underlying ideas form functional programming.

Much recent research in programming languages is about types for interacting processes. The most well-known, but by no means only example are the session types pioneered by K. Honda. The key idea is that each process has a bunch of interaction points, and the interaction at each interaction point is constrained by a type. Such types typically

- What direction does data flow? E.g. channel x is used for input while channel y does only output.

- What kind of data is exchanged on the channel? E.g. x is used to exchange a boolean, while y exchanges pairs, the first component of which is a double, and the second component is a channel name which is used for inputing a string.

- How often is a channel used? E.g. x is linear (used exactly once), y is affine (used at most once) while z can be used an arbitrary number of times.

This setup has been investigated from many angles, and one of the most beautiful results in this space is that normal types known from lambda-calculus (e.g. function space) can be recovered precisely as special cases of such interaction types, using Milner's well-known encoding of functional computation as interaction.

2 comments

> it's misleading to assume that ... types always have to be based on some underlying ideas form functional programming.

One of FP's more annoying achievements is somehow convincing people that it's the only way to make programs more verifiable or more "mathematical". Imperative, stateful computation can be (and is) just as mathematical (whatever that means) and just as verifiable as pure-FP (it must be constrained in some ways, but not as extreme as requiring complete referential-transparency).

It's good to learn about applying types to process calculi. I wasn't aware of that work at all.

   Imperative, stateful computation [...] is [...] as [...] verifiable as pure-FP
Exactly. When you verify your programs using some kind of program logic you realise that you have to keep track of all relevant data anyway.

The condescension towards languages like C/C++ and Java that some FP extremists have shown is probably one of the reasons for the rift between working programmers and PL theory. Fortunately, things are much better now, with most new languages (e.g. Scala, Rust, Clojure) bridging both worlds.

    applying types to process calculi. I wasn't aware of that work at all.
Maybe "A Gentle Introduction to Multiparty Asynchronous Session Types" http://goo.gl/FeVLv3 could be an introduction?
>The condescension towards languages like C/C++ and Java that some FP extremists have shown is probably one of the reasons for the rift between working programmers and PL theory. Fortunately, things are much better now, with most new languages (e.g. Scala, Rust, Clojure) bridging both worlds.

Look, if you want to build a whole language around Hoare logic, go ahead. We just think it's ugly.

You don't need to build a "whole language" around any kind of logic for it to be sufficiently verifiable. Types are useful, but it's not necessarily an all-or-nothing question. There are non-type-based verification tools (symbolic execution and deduction), and tests complete the picture. A language that doesn't let you write a program unless you yourself have worked hard to prove to the compiler that it's correct may be more trouble than it's worth. Verification does not necessarily have to be a part of compilation, and it does not necessarily require the proof to be spelled out in code.
I agree that it is good separate programming and verification. Otherwise the programmer is forced by the compiler to worry about correctness and termination from Day 1.

Moreover, Cury-Howard based approaches really work only for a restricted form of programming: pure and total functions.

I'm not sure I can follow you here. What is ugly, Hoare logic? What does it mean to "build a whole language around Hoare logic"? What in your opinion are the alternatives to Hoare-style program logics that are general-purpose enough to work for arbitrary programming languages?
Indeed, I was going to talk about session types in a follow-on post :) Well anticipated! Cheers!
Good. Session types are not the only approach to typing interaction, although probably the simplest.