One important feature of functional logic languages is the ability to deal with nondeterministic computations to compute solutions for partially instantiated goals. This can lead to problems when using I/O operations, because these are usually not backtrackable. For instance in Prolog, output made by a failing branch of the search tree will remain on the screen and disturb the output of a possibly successful computation. In languages like Curry [12], a multi-paradigm declarative language, the problem becomes more serious, because different branches of a nondeterministic computation might be computed concurrently. Thus, different branches of the search tree would compete for the input and output devices.
To provide a clean, declarative method of I/O, one can use the monadic I/O concept [24] which was developed for Haskell [16] and adapted in Curry. In this concept, I/O operations are seen as transformations that act on the outside world, which contains the file system, the Internet etc. This world can of course not be copied. Thus, nondeterminism in combination with monadic I/O leads to an unexpected behavior, e.g., runtime errors. To avoid a nondeterministic splitting of the top-level computation (which is a sequence of actions in interactive programs), Curry allows to encapsulate nondeterministic computations [11, 22].
The remaining problem is to detect all possible sources for nondeterminism in a program. This can be very difficult even for small programs and often also depends on the form of queries the user may ask.
Thus, our aim is to develop a program analysis which is able to detect all possible sources of nondeterminism. With techniques like encapsulated search, it will then be possible to transform a program such that all nondeterministic computations are encapsulated, thus increasing program stability and safety.
Additionally, the information computed by our program analysis can be used for
compiler optimizations. In general, the code for a Curry function that could
reduce nondeterministically must contain instructions for checking the arguments and
deciding if the actual call of this function reduces deterministically or
not. For functions that are proven to reduce deterministically
by our analysis, such instructions can be eliminiated. If larger program parts or the
complete program do not cause nondeterminism, code for
handling nondeterminism, for instance for spawning new computation branches, can be dropped
(dead code elimination). Such optimizations can be applied for instance
to the Curry2Java compiler [10] which is part of our current
Curry system PACS [13] and
compiles Curry programs into code for an abstract machine implemented in Java.
For our analysis we will use a type and effect system (see [19] for an overview), which can be seen as an extension of classical type systems known from functional languages. The basic idea is to annotate function types with some effect to describe the runtime behaviour of the function. In our case we will annotate the names of those functions as an effect that might cause nondeterministic computations. Then our analysis will return all function names that could split the computation when applied during the evaluation of a certain expression (i.e., the goal to be solved).
Note that existing determinism analyses for (functional) logic languages cannot be carried over to Curry directly because the same function might reduce deterministically or not depending on its arguments. Thus, we need to derive groundness information for arguments in function calls which is not trivial due to the lazy evaluation mechanism in Curry. Therefore, analyses for languages like Prolog [23, 4], Mercury [15], or HAL [5] do not apply because they do not deal with lazy evaluation. In contrast, analyses proposed for narrowing-based functional logic languages dealing with lazy evaluation cannot handle residuation, which additionally exists in Curry, and rely on the non-ambiguity condition [18] which is too restrictive for Curry programs. Furthermore, these analyses are either applied during runtime (like in Babel [18] and partially in K-Leaf), or are unable to derive groundness information for function calls in arguments (like in K-Leaf [17]).
In the next section we will briefly introduce the language Curry which we use as target language for our analysis. Note that the analysis itself should be adaptable also to other functional logic languages that suffer from similar problems. In Section 3 the type and effect system will be described and some examples will be given to clarify the ideas behind our analysis. Section 4 sketches future work and Section 5 contains our conclusions.