Interaction nets with McCarthy's amb: properties and applications
Maribel Fernández, Lionel Khalil · Research Portal (King's College London) · 2003
Interaction nets are graphical rewrite systems which have been successfully used to implement various efficient evaluation strategies in the lambda -calculus (including optimal reduction). However, they are intrinsically deterministic and this prevents from applying these techniques to concurrent languages where non-determinism plays a key role. In this paper we show that a minimal extension - the addition of one agent in the spirit of McCarthy's amb operator - allows us to define non-deterministic processes such as angelic and infinity merge, and more generally, to encode process calculi and wide classes of term rewriting systems (including systems defining parallel functions). We show that Alexiev's INMPP (interaction nets with multiple principal ports) can be encoded, for which we give a textual calculus and a type system that ensures the absence of deadlock. (19 References).