Matthias Güdemann - Introduction to the Mercury language

Introduction to the Mercury language

Matthias Güdemann

matthias.guedemann@googlemail.com

Augsburg, Curry-Club 13/08/2015

What is Mercury?

  • Mercury is a logic/functional programming language which combines the clarity and expressiveness of declarative programming with advanced static analysis and error detection features. (Mercury Webpage - advertisment)
  • Mercury is a purely declarative logic language. It is related to both Prolog and Haskell. It features a strong, static, polymorphic type system, as well as a strong mode and determinism system. (Mercury Webpage - description)
  • The current system for building Mercury is an utter fucking disaster. It is quite possibly the single dumbest thing ever put down in code in the past fifty years. (unhappy user on mailing list)

How to get Mercury?

  • go to http://dl.mercurylang.org/index.html download a "release of the day"
  • ./configure --disable-most-grades; make install (better with PARALLEL make)
  • wait
  • wait longer …
  • wait …
  • it will be installed in /usr/local/mercury-rotd-$DATE
  • PROTIP: use stow to symbolically link files in directory above to /usr/bin
  • use emacs :-) M-x package-list and install flycheck-mercury (shameless plug)

Why Mercury?

  • for functional programming: static type checking
  • logic programming: determinism and mode checking
  • compilation to:
    • low level C (gcc + extensions)
    • high level C (gcc, clang)
    • Java
    • Erlang/OTP
    • C#
  • module system
  • fast code (C as "portable assembler")

Language Syntax

  • very similar to Prolog, i.e., predicates, logic variables
  • unification term1 = term2
  • conjunction pred_1/n, pred_2/m (pred_1/n & pred_2/m for parallel execution)
  • disjuntion pred_1; pred_2
  • if A then B else C (A -> B; C) (declaratively equivalent to (A, B; not(A), C))
  • also: higher order predicates, functions, module definitions etc.
  • for more, see: http://www.mercurylang.org/information/doc-release/mercury_ref/Goals.html#Goals

Type System

  • based on many-sorted logic with parametric polymorphism
  • static type system, similar to Haskell
  • typeclasses (but no Typeclassopedia)
  • type inference for functions / predicates

Determinism

  • Predicates can have different (and multiple) determinism declarations
    • det exactly one solution
    • semidet zero or one solution
    • multi one or more solutions
    • nondet zero or more solutions
    • cc_multi / cc_nondet committed choice (only first solution)
  • Functions and Predicates
    • semidet / det predicates with one out argument can be expressed as functions

Mode System

  • instantiation state of arguments
  • basic modes: in, out
    • :- mode in == bound >> bound
    • :- mode out == free >> bound
  • uniqueness modes
    • unique input: :- mode ui == unique >> unique
    • unique output: :- mode uo == free >> unique
    • destructive input: :- mode di == unique >> dead
  • mode inference re-orders predicates to respect instantiations

Use of Mode System

  • special instantiations
    • non-empty lists

      :- inst non_empty_list == bound([ground | ground]).

    • empty lists (not too useful!)

      :- inst empty_list == bound([]).

  • Input/Output: "Threading World State"
  • General State Threading
    • Destructive Update (Arrays, Hashtables)
    • external Objects (most often C structs, C++ objects etc.)

A small example: natural numbers

DEMO

More real world example: Pollard's algorithm

  • Finds factors for composite numbers
  • Factoring Fermat Number F8 (2256 + 1)
Language time factor
UNIVAC 1110/42 - 1980 2h 1x
OCaml 12s 600x
Haskell 13s 553x
SWI 25s 288x
YAP 45s 160x
Mercury 39m 3x

Mercury FFI

  • declare external type
:- pragma foreign_type("C", gmp_int, "mpz_t *", [can_pass_as_mercury_type])
    where equality is equal, comparison is cmp.
  • initialize library / define memory allocation strategy
:- initialise gmp_initialize/0.
:- impure pred gmp_initialize is det.
:- pragma foreign_proc("C", gmp_initialize, [will_not_call_mercury, thread_safe],
"
  mp_set_memory_functions(&gmp_int_alloc_function,
                          &gmp_int_realloc_function,
                          &gmp_int_free_function);
").

Mercury FFI contd.

  • define functions, here infix addition, i.e., C = A + B
:- pragma foreign_proc("C", +(A::in, B::in) = (C::out),
                      [will_not_call_mercury, promise_pure, thread_safe],
"
  C = MR_GC_NEW_ATTRIB(mpz_t, MR_ALLOC_ID);
  mpz_init(*C);
  mpz_add(*C, *A, *B);
").
  • and predicates, here is_even(X)
:- pragma foreign_proc("C", is_even(A::in),
                      [will_not_call_mercury, promise_pure, thread_safe],
"
  SUCCESS_INDICATOR = mpz_even_p(*A) ? MR_TRUE : MR_FALSE;
").

mercury mp_int / gmp_int

Language time factor
UNIVAC 1110/42 - 1980 2h 1x
OCaml 12s 600x
Haskell 13s 553x
Mercury / gmp_int.m 15s 480x
SWI 25s 288x
YAP 45s 160x
Mercury / mp_int.m 93s 75x
Mercury / integer.m 39m 3x

Conclusion

  • Nice language, very fast for logic / functional
    • use as pure "core language"
    • purity / non-determinism challenge for efficiency
    • "there's more to complexity than O(f(n))"
  • Many advances in 1995 - 2010, now big features done
  • large standard library with standard data-structures
  • not many "external" libraries (also not many users :-( )
  • Good and easy to use FFI
  • Compilation into C / high-level C / Java / Erlang / C#

Further Reading