Type-based Nondeterminism Checking in Functional Logic Programs
Michael Hanus and Frank Steiner
To appear at the 2nd International Conference on Principles and Practice of
Declarative Programming (PPDP 2000), Montreal, Canada, September 20-22, 2000
Functional logic languages combine nondeterministic search facilities of
logic languages with features of functional languages, e.g., monadic
I/O to provide a declarative method to deal with I/O actions.
Unfortunately, monadic I/O cannot be used in programs which split the
computation due to nondeterministic reductions. This problem can be
avoided if nondeterministic computations are encapsulated by search
operators which are available, for instance, in the multi-paradigm
language Curry. To support the programmer in identifying
nondeterministic parts of a program, we develop a method based on a
type and effect system that will find every possible source of
nondeterminism. Additionally, such information can be exploited in
compilers to optimize deterministically reducible parts of a program.