• FM binding for π-calculus transitions.
    Murdoch Gabbay (U Cambridge, UK).
    May 30, 2003, Friday, 16h 30m.
    Abstract: It can be a problem in the theory of the π-calculus that a process P, such as P=νb.a!b (restrict b in output b along a) can undergo infinitely many different transitions, one for each fresh b. Theoretical treatments usually come with α-equivalence results to show that they only need to consider one of these fresh names. They are specific to the theorem of interest; a general formal treatment of why such results hold is lacking, as is a programming framework for them. FreshML is a dialect of ML with an abstraction type-former which supplies such a programming framework. Given a type X and a type of names Atoms , < Atoms >X is the type of elements of X with a name in Atoms bound. If Π is a datatype of π-calculus processes and L a datatype of labels, the type Π*< Atoms >(L*Π) models π-calculus transitions. The bound name is a fresh name if the transition generates one. For example: (νb.a!b,<b>(a!b,0)) represents the transition(s) νb.a!b-a!(b)->0. We find that the programming principles associated to such datatypes model our hitherto informal understanding of names and binding. Thus FreshML is an intuitive tool. I shall give some theory, show some programs, and discuss how they work.