A model for I/O in equational languages with don't care non-determinism
H. R. J. Walters, Jasper F.T Kamperman · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1995
Existing models for I/O in side-effect free languages focus on functional languages, which are usually based on a largely deterministic reduction strategy, allowing for a strict sequentialization of I/O operations. In concurrent logic programming languages a model is used which allows for don't care non-determinism; the sequentialization of I/O is extensional rather than intensional. We apply this model to equational languages, which are closely related to functional languages, but exhibit don't care non-determinism. The semantics are formulated as constrained narrowing, a relation that contains the rewrite relation, and is contained in the narrowing relation. We present constrained narrowing and some of its properties; a constructive method to transform conventional term rewriting systems to constrained narrowing systems; and a discussion on requirements for an implementation. CR Subject Classification (1991): D.1.1 [Programming Techniques]: Applicative (Functional) Programm...