Mercury (programming language)

Mercury is a typed logic-functional programming language whose central design goal is efficient, dependable declarative programming. The language was created by Fergus Henderson, Thomas Conway, and Zoltan Somogyi at the University of Melbourne, with the first public release appearing in the mid-1990s.¹ A Mercury program describes relations, functions, data types, and modules rather than prescribing every operational step. The compiler then uses static information to select efficient execution strategies.

Mercury grew out of experience with Prolog, but it deliberately rejects several forms of unrestricted runtime behavior that make large Prolog systems difficult to analyze. Predicates have declared types, modes, and determinisms; modules control interfaces and implementation details; and many errors that would otherwise appear during execution can be reported during compilation. The result is a language aimed less at interactive theorem-proving style programming than at maintainable software engineering.

Mercury’s distinctive static analyses describe both the values a predicate manipulates and the ways its arguments may be instantiated. A mode records whether an argument is expected to be bound or free at a call, allowing the compiler to check that a predicate is used in a supported direction. The same logical relation can therefore support different modes, such as taking a list and producing a result or checking a supplied result against a list.

Determinism describes how many solutions a computation can produce and whether it can fail. Common categories include det for exactly one solution, semidet for zero or one, multi for one or more, and nondet for zero or more. Mercury also distinguishes erroneous or unsupported cases through additional determinism categories. These declarations let the compiler detect unexpected nondeterminism, missing cases, and mode errors while enabling specialized code generation.

The type system supports algebraic data types, higher-order values, type classes, existential types, and parameterized modules. Type classes provide ad hoc polymorphism in a style related to those in Haskell, while Mercury’s mode system extends the usual type-level account of a function’s behavior.

Mercury programs are organized into modules with separate interface and implementation sections, which supports abstraction and incremental compilation. The standard library provides lists, maps, sets, streams, parsing tools, I/O, concurrency facilities, and other data structures. Input and output are commonly expressed through a unique state-threading convention: an I/O state is passed in and returned in a way that permits the compiler to enforce single use while retaining a declarative interface.

The Mercury compiler performs type, mode, determinism, and several optimization analyses before generating executable code. It can target native code through back ends based on C and other implementation technologies, and it supports foreign-language interfaces for selected targets.¹ Back ends and runtime details vary, but the language definition aims to preserve the same declarative semantics across them.

Mercury is particularly suited to symbolic processing, compilers, interpreters, constraint-oriented applications, natural-language tools, and programs containing complex tree or graph data. Its compile-time discipline can require more declarations and design work than a dynamically typed scripting language, especially when a relation has many legitimate calling patterns.

Mercury’s logic programming is deliberately stratified by purity and determinism rather than treating every predicate as an unrestricted search procedure. Pure predicates can be reasoned about through their logical meaning, while explicitly marked impurity is used for operations such as foreign calls, mutable state, or effects that cannot be represented as ordinary relations. This boundary makes effects visible in interfaces and gives optimization analyses clearer assumptions.

The language also supports several less familiar forms of controlled state. Unique modes can represent destructive updates safely when the compiler can establish that no other reference remains, and unique data structures can therefore provide efficiency without exposing general aliasing. Tabling, higher-order calls, constraint-related libraries, and parallel or concurrent execution facilities extend Mercury beyond simple list-processing examples, although their availability and performance depend on implementation and program structure.

Mercury remains a relatively small specialist language rather than a mainstream commercial platform. Its principal legacy is methodological: it demonstrates how logic programming’s relational notation can be combined with strong static checking and aggressive compilation instead of relying primarily on runtime search and dynamic conventions.

Predicate

A relation-like procedure that may succeed, fail, or produce one or more solutions.

Mode

A declaration describing which arguments are initially instantiated and which are produced by a predicate call.

Determinism

A classification of the number of solutions and possible failure behavior of a computation.

Type class

An interface-like collection of operations that supports ad hoc polymorphism over types.

Unique mode

A mode discipline that permits controlled destructive update when an object has no other usable reference.