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
,
such as
(restrict
in output
along
) can undergo
infinitely many different transitions, one for each fresh
.
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
and a type of names
,
is the type of elements of
with a name in
bound.
If
is a datatype of
-calculus processes and
a datatype of labels,
the type
models
-calculus transitions.
The bound name is a fresh name if the transition generates one.
For example:
represents the transition(s)
.
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.