Nondeterminism and I/O

Nondeterministic computations are problematic if they appear in programs that use I/O. A declarative treatment of input/output, as implemented in Curry, can be obtained by the monadic I/O concept [24]. In this concept, an interactive program is considered as a function computing a sequence of actions which are applied to the outside world. An action changes the state of the world and possibly returns a result (e.g., a character read from the terminal). Thus, actions are functions of the type

(where $World$ denotes the type of all states of the outside world). This function type is also abbreviated by . If an action of type is applied to a particular world, it yields a value of type and a new (changed) world. For instance,  $$getChar  of type $IO\; Char$ is an action which reads a character from the standard input whenever it is executed, i.e., applied to a world. The important point is that values of type $World$ are not accessible to the programmer - she can only create and compose actions on the world. For instance, the action  $$getChar  can be composed with the action  $$putChar  (which writes a character to the terminal) by the sequential composition operator  $$>>= , i.e.,

getChar >>= putChar

is a composed action which prints the character typed in the keyboard to the screen (see [24] for more details).

An action, obtained as a result of a program, is executed when the program is executed. Since the world cannot be copied (note that the world contains at least the complete file system or the complete Internet in web applications), an interactive program having a disjunction as a result makes no sense. For instance consider the program

nonsense x | sq x =:= y = show y

                          where y free

where  $$show  is a function that writes its argument to the screen. If we call  $$nonsense x, what should be the output on the screen, 1 or 4? Since it is difficult to define a reasonable output behavior for such a program, a Curry program that uses I/O actions will result in a runtime error whenever a nondeterministic computation is detected.

To overcome this problem, all possible search must be encapsulated between I/O operations. In Curry one can use the mechanisms of encapsulated search, that will encapsulate nondeterministic steps and encode different computation branches into a data structure. Furthermore, it provides a flexible method of programming search strategies (see [11] for a more detailed description of encapsulated search).

To detect the program points where nondeterminism may occur, we can use the analysis described in the next section.