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 solutionsemidet
zero or one solutionmulti
one or more solutionsnondet
zero or more solutionscc_multi
/cc_nondet
committed choice (only first solution)
- Functions and Predicates
- semidet / det predicates with one
out
argument can be expressed as functions
- semidet / det predicates with one
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
- unique input:
- 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
Mercury Mailing Lists
Automatic Parallelization / Declarative Debugging
Parallelization / FFI /
mercury_gmp
"Adventures in Mercury"