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.

Applicative Programming (acm D.1.1), Semantics of Programming Languages (acm F.3.2), Mathematical Logic (acm F.4.1)
Logic programming (msc 68N17), Theory of computing (msc 68Qxx), Grammars and rewriting systems (msc 68Q42), Abstract data types; algebraic specification (msc 68Q65)
CWI
Department of Computer Science [CS]
Extensible programming environments

Walters, H.R, & Kamperman, J.F.T. (1995). A model for I/O in equational languages with don't care non-determinism. Department of Computer Science [CS]. CWI.