Home » forums » LtU Forum

Point free pi calculus

Does anyone know if there is a point free translation of the pi calculus similar to using SK combinators to translate the Lambda calculus?

Specifically, I would like to express the Pi calculus in terms of combinators only (no mechanism for new variable names), and although I think I can do this with SK combinators plus a couple primitives, I am wondering if there is any existing work on this.

By procyon at 2007-05-04 17:29 | LtU Forum | previous forum topic | next forum topic | other blogs | 5814 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Different approaches, not completely point-free

There are essentially 2 different kinds of binding constructs in the pi-calculus (at least if we limit ourselves to the simple asynchronous subset): input prefix and scope restriction of channel names. It appears easier to deal away with the former kind of bindings than with the latter.
Specifically, in Combinatory Representation of Mobile Processes, Kohei Honda, Nobuko Yoshida, Conference Record of POPL '94, the nu-calculus is introduced, which replaces input and output prefixes with a set of 7 (process) combinators. Scope-restriction bindings remain in the calculus, however.
An interesting alternative appears in Combinatory Formulations of Concurrent Languages, N.Raja, R.K.Shyamasundar, ACM TOPLAS, V.19. (Incidentally, these authors apply the same approach to the lambda-calculus, leading to a system of combinators quite different from classical combinatory logic.) This system is also geared towards eliminating input-prefix bindings.
On the other hand, the generation of new, globally unique names by scope restriction is addressed in Handling Locally Names of Mobile Agents, Chiara Bodei, Pierpaolo Degano and Corrado Priami, 1996.
Finally, the recently discussed system of Radestock and Meredith might be relevent, but I have not studied it in details yet, so I am not sure.

By dnk at Fri, 2007-05-04 21:47 | login or register to post comments