Determinism analysis in the Mercury compiler

Mercury is a new purely declarative logic programming language. The Mercury determinism system allows programmers to specify which predicates never fail and which predicates succeed at most once. This information allows the compiler to check the program for errors, pinpointing predicates that do not satisfy their declarations. This makes programmers significantly more productive and enhances the reliability of their programs. The Mercury compiler also uses determinism information to generate much faster code than any other logic programming system. This paper presents the algorithms used by the Mercury compiler to infer determinism information. Keywords Programming language implementation, program analysis, logic programming, determinism, Mercury. 1 Introduction One of the fundamental differences between logic programming and other programming paradigms is the presence of so-called "don't-know" nondeterminism, whereby a predicate may return more than one solution, and the associated..