Mercury (programming language)

From Bauman National Library
This page was last modified on 2 June 2016, at 08:36.
Mercury
Mercury (programming language) logo.jpg
Paradigm Functional and Logic Programming
Designed by Zoltán Somogyi
First appeared 1995
Stable release 14.0.01 / 14.10.2014
Typing discipline Strong, Static
Website https://www.mercurylang.org/

Mercury is a functional logic programming language geared for real-world applications. It was initially developed at the University Of Melbourne Computer Science department under the supervision of Zoltan Somogyi. The first version was released on April 8, 1995. It was developed by Fergus Henderson, Thomas Conway and Zoltan Somogyi. Mercury is based on the logic programming language Prolog and has the same syntax, and the same basic concepts such as the SLD resolution algorithm.It is compared to its predecessor in terms of capacity and time record. Due to the use of information obtained at compile time (such as type and mode information), programs written in Mercury typically perform significantly faster than equivalent programs written in Prolog.Mercury is the fastest logic language in the world, by a wide margin.

Goals

Declarative programming (for example in Prolog) has always been very powerful. However creating large pieces of software is difficult. We aim to make programming in the large easier:

  • large programs
  • large teams
  • better program reliability
  • better program maintainability
  • program efficiency

Syntax

The allowed declarations are:

 :- type
 :- solver type
 :- pred
 :- func
 :- inst
 :- mode
 :- typeclass
 :- instance
 :- pragma
 :- promise
 :- initialise
 :- finalise
 :- mutable
 :- module
 :- interface
 :- implementation
 :- import_module
 :- use_module
 :- include_module
 :- end_module

The ‘type’, ‘pred’ and ‘func’ declarations are used for the type system, the ‘inst’ and ‘mode’ declarations are for the mode system, the ‘pragma’ declarations are for the foreign language interface, and for compiler hints about inlining, and the remainder are for the module system.

A function fact is an item of the form ‘Head = Result’. A predicate fact is an item of the form ‘Head’, where the top-level functor of Head is not :-/1, :-/2, -->/2, or =/2. In both cases, the Head term must not be a variable.

A function rule is an item of the form ‘Head = Result :- Body’. A predicate rule is an item of the form ‘Head :- Body’ where the top-level functor of ‘Head’ is not =/2. In both cases, the Head term must not be a variable. The top-level functor of the Head determines which predicate or function the clause belongs to; the predicate or function must have been declared in a preceding ‘pred’ or ‘func’ declaration in this module.

State variables

Clauses may use ‘state variables’ as a shorthand for naming intermediate values in a sequence. That is, where in the plain syntax one might write

 main(IO0, IO) :-
 io.write_string("The answer is ", IO0, IO1),
 io.write_int(calculate_answer(...), IO1, IO2),
 io.nl(IO3, IO).

using state variable syntax one could write

 main(!IO) :-
 io.write_string("The answer is ", !IO),
 io.write_int(calculate_answer(...), !IO),
 io.nl(!IO).

A state variable is written ‘!.X’ or ‘!:X’, denoting the “current” or “next” value of the sequence labelled X. An argument ‘!X’ is shorthand for two state variable arguments ‘!.X, !:X’; that is, ‘p(..., !X, ...)’ is parsed as ‘p(..., !.X, !:X, ...)’. Within each clause, a transformation converts state variables into sequences of ordinary logic variables. The syntactic conversion is described in terms of the notional ‘transform’ function defined next. The transformation is applied once for each state variable X with some fresh variables which we shall call ThisX and NextX.

For instance, the following clause employing a lambda expression

 p(A, B, !S) :-
         F = (pred(C::in, D::out, !.S::in, !:S::out) is det :-
                 q(C, D, !S)
         ),
         ( F(A, E, !S) ->
              B = E
         ;
              B = A
         ).

Types

Mercury has a strong, static type system similar to Haskell's.

Certain special types are builtin, or are defined in the Mercury library:

  • Primitive types: char, int, float, string. There is a special syntax for constants of type int, float, and string. (For char, the standard syntax suffices.)
  • Predicate types: pred, pred(T), pred(T1, T2)
  • Function types: (func) = T, func(T1) = T
  • Tuple types: {}, {T}, {T1, T2}
  • Universal type 'univ'

And all the Prolog types.

Developers can define new types easily.

 :- type playing_card
     ---> normal_card(
              c_suit :: suit,
              c_num :: int
          )
     ;    joker.
 :- type suit
     ---> heart
     ;    diamond
     ;    spade
     ;    club.

A predicate's arguments' types are declared in its pred declaration.

 :- pred fibs(int, int).
 fibs(N, F) :-
      ( N < 2 ->
          F = 1
      ;
          fibs(N - 1, FA),
          fibs(N - 2, FB),
          F = FA + FB
      ).

Modes

The mode of a predicate, or function, is a mapping from the initial state of instantiation of the arguments of the predicate, or the arguments and result of a function, to their final state of instantiation. To describe states of instantiation, we use information provided by the type system. Types can be viewed as regular trees with two kinds of nodes: or-nodes representing types and and-nodes representing constructors. The children of an or-node are the constructors that can be used to construct terms of that type; the children of an and-node are the types of the arguments of the constructors. We attach mode information to the or-nodes of type trees.

When an instantiatedness tree tells us that a variable is bound, there may be several alternative function symbols to which it could be bound. The instantiatedness tree does not tell us which of these it is bound to; instead for each possible function symbol it tells us exactly which arguments of the function symbol will be free and which will be bound. The same principle applies recursively to these bound arguments. Mercury’s mode system allows users to declare names for instantiatedness trees using declarations such as

 :- inst listskel == bound( [] ; [free | listskel] ).

A predicate mode declaration assigns a mode mapping to each argument of a predicate. A function mode declaration assigns a mode mapping to each argument of a function, and a mode mapping to the function result. Each mode of a predicate or function is called a procedure. For example, given the mode names defined by

 :- mode out_listskel ==
 free >> listskel.
 :- mode in_listskel ==
 listskel >> listskel.

the (type and) mode declarations of the function length and predicate append are as follows:

 :- func length(list(T)) = int.
 :- mode length(in_listskel) = out.
 :- mode length(out_listskel) = in.
 :- pred append(list(T), list(T), list(T)).
 :- mode append(in, in, out).
 :- mode append(out, out, in).

Determinism

For each mode of a predicate or function, we categorise that mode according to how many times it can succeed, and whether or not it can fail before producing its first solution. If all possible calls to a particular mode of a predicate or function which return to the caller (calls which terminate, do not throw an exception and do not cause a fatal runtime error):

  • have exactly one solution, then that mode is deterministic (det);
  • either have no solutions or have one solution, then that mode is semideterministic (semidet)
  • have at least one solution but may have more, then that mode is multisolution (multi)
  • have zero or more solutions, then that mode is nondeterministic (nondet)
  • fail without producing a solution, then that mode has a determinism of failure.

If no possible calls to a particular mode of a predicate or function can return to the caller, then that mode has a determinism of erroneous.

See also

Mercury