Mercury Crash Course

Table of Contents

BIG WARNING: this document will probably be much better received as your second Mercury tutorial, rather than your first. It's a very thorough tour through the language, but it's not gentle and it doesn't get you started compiling applications very quickly.

1 Is Socrates mortal?

Consider this fragment of Mercury code:

mortal(X) :- man(X).

man(socrates).

1.1 Can I compile and run this code?

No, it's incomplete.

1.2 Taking that piece by piece, what is mortal(X)?

It is the head of the predicate rule mortal/1.

1.3 What's a predicate?

You can think of it like a function without a return value, such as a void function in C, or a procedure in Ada. It comes from predicate logic in mathematics.

You could also think of it as a special kind of boolean function where the boolean return value is hidden away and then handled by the language, such that a false return results in a 'failure' in the caller of the function.

1.4 Failure? Do you mean an exception?

No, not an exception. In Mercury, predicates have determinism categories such as 'det', 'multi', etc.:

Can fail? 0 solutions 1 more than 1
no erroneous det multi
yes failure semidet nondet

When predicates have more than one answer, backtracking will be used to find a combination of answers that doesn't lead to an eventual failure. When predicates can fail, they can appear as goals in a rule that can fail, or they can appear as goals in conditional code (Mercury's if/then/else uses failure rather than a boolean expression).

1.5 What does that /1 mean in mortal/1?

It means that mortal has one argument, or that it's of arity 1. A module could also have mortal/2 (of two arguments; arity 2), mortal/3 (arity 3), and so on. These are distinct predicates which could have their own unrelated meanings.

1.6 A module?

Although we don't see it in this fragment, Mercury code is organized into modules. If the module were named "mortality", for example, then the full name of the predicate rule defined would be mortality.mortal/1, to distinguish it from any mortal/1 predicates from other modules.

1.7 OK, so Mercury has polymorphism. Is it multiple dispatch? Single dispatch?

Not quite. Polymorphism in OOP languages permits print(A) to refer to one of several functions that could be in the same module, disambiguated by the type of A. In Mercury such a duplication is just an error. Mercury symbols that differ by type must also differ by module or by arity. So you can have an addition operator defined in the 'int', 'float', etc. modules, but you couldn't have an 'addition' module that defines the same operator for int, float, etc. types.

Clause definitions would very easily be type-ambiguous, otherwise.

1.8 What does :- mean?

Symbolically it's an arrow, pointing from the body of the rule (on the right) to the head of the rule (on the left). If the body is true, then the head is true. Reversing it: "X is a man –> X is a mortal".

1.9 What about man(X)?

It's the only goal in the body of the mortal/1 predicate rule, and it's a call to the predicate man/1.

1.10 And the two X es?

It's the same variable X, scoped to the rule it's in. You can mostly get away with treating it like a mathematical variable or like a variable in other programming languages.

1.11 How do we know that X is a variable but socrates is a value?

In Mercury, variables begin with a capital letter or an underscore: _

The lone _ is an anonymous throwaway, a way to discard a predicate's output.

A variable that begins with _ is expected to be a named throwaway, a way to discard a predicate's output while naming that output. But for multinationalization reasons (not all languages have uppercase letters) you can use such variables like normal, with just a warning to indicate that you're violating the expectation.

1.12 How about the period at the end?

All toplevel syntax elements in Mercury end in a dot. It has no meaning other than to indicate that the rule (in this case) is done.

1.13 How about man(socrates).?

It's equivalent to man(socrates) :- true., where the body of the rule is always successful, so the head of the rule is always implied.

In such cases we call it a fact. "It's a fact that Socrates is a man."

1.14 So, taken altogether, what does this code mean?

  1. As a rule, something is mortal if it is a man.
  2. Socrates is a man.

1.15 How might you use that code?

You could confirm that Socrates is mortal according to the rules and facts of this code, by seeing that the goal mortal(socrates) succeeds.

1.16 How else might you use this code?

You could answer the question, "who is a mortal?", by seeing that the goal mortal(X) binds X to Socrates.

2 Hello, world!

Consider this complete application:

SRC: hello.m

:- module hello.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.

main(!IO) :-
    io.write_string("Hello, world!\n", !IO).

2.1 Is this really the smallest 'hello world' in Mercury?

Yes. We could easily imagine a system of implicit defaults that would permit a much shorter file:

  1. if no :- module is provided, use the filename.
  2. if no :- interface. is provided, then assume an interface with a single main/2 predicate, suitable for an application entry point.
  3. if no :- implementation. is provided, assume the body of the file is the module implementation.

But, of Mercury, the Language Reference states:

Mercury … was designed to be useful for the development of large and robust "real-world" applications.

The language is very explicit in other respects, as well.

2.2 Well, let's go through it. Does :- module hello. name the module this code is defined in?

Yes. The module name should match the file name. The 'hello' module goes in the 'hello.m' file.

2.3 Is `:- module hello.` a rule?

That's a declaration, as it begins with a :-.

Mercury modules consist of just

  1. programming stuff: declarations.
  2. logical stuff: clauses that define rules and facts.
  3. non-code: whitespace, comments.

2.4 Does :- interface. start the interface section of the module?

Yes. If another module were to use this module, that other module would gain a hello.main/2 predicate for its use.

2.5 Wait, is there any point to that?

Well, it's how all modules work. The main/2 predicate is special though, so it would actually be difficult to use this module as anything but the main entry point for an application.

If instead the hello module exported a hellomain/2 predicate, it could be used like so, to print "Hello, world!" in an infinite loop:

:- hello_repeatedly.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module hello.

main(!IO) :-
    hellomain(!IO),
    main(!IO).

2.6 Moving on, :- import_module io. imports the 'io' module, right?

Right. This line exposes the entire interface of the 'io' module to this module, allowing reference to those exports without a mandatory 'io.' in the name. This is used by hello's interface when it refers to io types in main/2's parameters: the type is actually io.io. Even if io. isn't mandatory, you can still include it to disambiguate or to clarify code, as in the call to io.write_string/3.

If you want to require that the module name be included in any reference to the module's exports, you can use :- use_module instead.

2.7 Wouldn't simple output normally be in an always-included module, like Pervasives or Prelude?

Mercury does have a builtin module, but it's very small. Far from having a rich prelude, in Mercury you can't even construct a list literal or perform integer addition without (at least) module imports to those purposes.

2.8 OK, :- pred main(io::di, io::uo) is det. … can you break that down?

  1. :- pred, this is a declaration of types for a predicate rule. As a convenience this declaration includes the single mode of this rule; otherwise you'd need another declaration, :- mode main(di, uo) is det.
  2. main(..., ...), the predicate rule is named main/2
  3. io::..., io::..., the arguments are both of type 'io'.
  4. io::di, the first 'io' has the mode 'di': it is a destructive input to main/2. Meaning, after main/2 gets that 'io', nothing else can get it. It's gone.
  5. io::uo, the second 'io' has the mode 'uo': it is a unique output from main/2. Meaning, this isn't a copy of data that exists elsewhere. The second 'io' is something that you could go on to provide as a destructive input to another rule.
  6. is det., this predicate always succeeds, and it succeeds exactly once.

2.9 Is there a simpler way to explain what this line is doing?

It's the signature of a main/2 predicate that does I/O. Because main/2 has this signature, it'll also be the entry point of a Mercury application.

2.10 After that, :- implementation starts the implementation section of the module.

Correct.

2.11 The rest is familiar, but what's this !IO ?

That's the state variable IO. The following code

main(!IO) :-
    io.write_string("Hello,", !IO),
    io.write_string(" world!\n", !IO).

expands to

main(!.IO, !:IO) :-
    io.write_string("Hello,", !.IO, !:IO),
    io.write_string(" world!\n", !.IO, !:IO).

which is similar to

main(IO0, IO) :-
    io.write_string("Hello,", IO0, IO1),
    io.write_string(" world!\n", IO1, IO).

!.X is always the current, bound variable, and !:X is always the next, free variable, that gets bound by the predicate it's an argument of, and !X as an argument is the pair of arguments !.X, !:X

For example, here's a series of updates to a number:

example(!.X, !IO) :-
    !:X = !.X + 1,
    !:X = !.X * 100,
    !:X = !.X / 3,
    !:X = !.X + 55,
    io.format("final value of X: %d\n", [i(!.X)], !IO).

2.12 Wait, this is new. What's that , that you have in these state-variable examples?

Oh. Up to this point rules have only had a single, simple goals, but all of the examples just now have complex goals. A, B is a conjunction goal, which succeeds if A and B both succeed. Likewise A, B, C succeeds if A, B, and C all succeed. It's more like A && B && C in C-like languages, rather than { A; B; C; } in those languages.

An important point about conjunctions is that the order of the subgoals mostly doesn't matter. The last main/2 example from the previous question,

main(IO0, IO) :-
    io.write_string("Hello,", IO0, IO1),
    io.write_string(" world!\n", IO1, IO).

prints out "Hello, world!", as does this modification of it:

main(IO0, IO) :-
    io.write_string(" world!\n", IO1, IO),
    io.write_string("Hello,", IO0, IO1).

Those two examples have exactly the same effect, because of the data dependency (of one io.write_string/3 requiring an IO1 input, and the other providing that IO1) between the sub-goals.

2.13 isn't that awful?

Obviously, it's not desirable for code to look like it does one thing when it really does another. State variables solve this by creating a data dependency that follows the lexical order of the goals that the variables appear in. If you take the first example and modify it similarly, to

main(!IO) :-
    io.write_string(" world!\n", !IO),
    io.write_string("Hello,", !IO).

then the behavior follows the new lexical order and what's printed is "world!" and then "Hello," on the next line.

2.14 but why permit that at all? Why not require that evaluation follow lexical order?

Mercury's based on logic and logical conjunctions and disjunctions aren't ordered. When programming languages have a consistent model, it's easier to predict how the language will work.

This also makes it easier for Mercury to compile the same code multiple times for different modes. Consider:

:- pred frob(int::in) is det.

:- pred foo(int, int).
:- mode foo(in, out).
:- mode foo(out, in).
foo(A, B) :-
    frob(A),
    ...

If Mercury couldn't reorder goals within the bounds of logic, this example would already be in error because frob(A) requires that 'A' is bound, but per second mode it could be a free variable at this point.

Finally, it makes Mercury easier to read and understand. When you see do_this(); do_that(); in C, or similar code in most other languages, you have to assume that the order is deliberate–that changing it to do_that(); do_this(); will change the behavior of the program. You have to assume this even when the order doesn't matter, because it might matter. Worse, it might matter in the future, as changes are made to the codebase over time.

This might sound like a lot of quibbling over nothing, but there's a definite mental burden that goes unnoticed due to how omnipresent the burden is. It's why style guides often discourage very long functions. They note that it becomes hard to understand what the function is doing. What, precisely, makes it hard? It's that in these languages you can't just focus on the meaning of any single statement of the function; you always have to consider each statement in the full context of the rest of the function, and a larger context is more to have to keep in mind. In Mercury, when state variables aren't involved, only the goal you're looking at matters to the meaning of the goal. Even any variables referenced by the goal are like 'single-assignment' variables that you can be sure aren't having their meaning changed elsewhere in the function.

2.15 What if you have logical tests that vary in how expensive they are? Is there no way to position the cheap tests before the expensive ones?

OK, declaratively it doesn't matter. The outcome should be the same regardless of the order.

But operationally, yes there are more and less expensive tests, and code might run fast or slower (or use more or less resources) depending on how goals are ordered. Consider this example:

:- pred test(list(int)::in) is semidet.
test([]).
test([X | Xs]) :-
    test(Xs),
    X < 5.

This code is ordered so that the relatively expensive test of "see if the entire rest of this list has ints < 5" comes before "see if this first element is < 5". There are optimizations in Mercury that can fix this code, and there are ways to get Mercury to complain if this doesn't compile in a tail-recursive way, but really you should just swap those two goals.

So you might still apply two rules, for efficiency's sake:

  • lead with cheaper tests
  • perform your tail-calls from a tail position

And for readability's sake:

  • don't try to make code look like it does one thing when it really does another.

2.16 OK, how can this 'hello world' be run?

If it's in a file named `hello.m',

$ mmc --make hello
Making Mercury/int3s/hello.int3
Making Mercury/ints/hello.int
Making Mercury/cs/hello.c
Making Mercury/os/hello.o
Making hello
$ ./hello 
Hello, world!

2.17 I benchmarked it and there's a lot of overhead compared to some other languages' programs that just print out "hello world". Should I set aside my dreams of writing CGI scripts and build system utilities with Mercury?

Some good optimization flags are -O4, or -O4 --intermodule-optimization.

The high level C grade also has a noticeably lighter runtime, which benefits little applications that spawn frequently. 'hello' on my machine:

# average of 10 runs. hlc.gc grade. -O4 --intermodule-optimization
User time      : 0 s, 10282 us
System time    : 0 s, 25086 us
Time           : 35.368 ms (3.537 ms/per)
Max RSS        : 5.7 MB
Page reclaims  : 5006
Page faults    : 0
Block inputs   : 0
Block outputs  : 0
vol ctx switches   : 10
invol ctx switches : 0

# average of 10 runs. asm_fast.gc grade. -O4 --intermodule-optimization
User time      : 0 s, 56627 us
System time    : 0 s, 142326 us
Time           : 198.953 ms (19.895 ms/per)
Max RSS        : 39.1 MB
Page reclaims  : 89032
Page faults    : 0
Block inputs   : 0
Block outputs  : 0
vol ctx switches   : 10
invol ctx switches : 3

3 Weekdays and workdays

Consider this complete application:

SRC: daytype.m

:- module daytype.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module string, list.

:- type days
    --->    sunday
    ;       monday
    ;       tuesday
    ;       wednesday
    ;       thursday
    ;       friday
    ;       saturday.

:- func daytype(days) = string.
daytype(D) = R :-
    (
        (D = sunday ; D = saturday),
        R = "weekend"
    ;
        (D = monday ; D = tuesday ; D = thursday ; D = friday),
        R = "workday"
    ;
        D = wednesday,
        R = "humpday"
    ).

main(!IO) :-
    io.command_line_arguments(Args, !IO),
    ( if
        Args = [DayString],
        Lowered = to_lower(DayString),
        Term = Lowered ++ ".",
        io.read_from_string("args", Term, length(Term),
            ok(Day), io.posn(0, 0, 0), _)
    then
        io.format("daytype(%s) = ""%s"".\n",
            [s(Lowered), s(daytype(Day))], !IO)
    else
        io.progname_base("daytype", Program, !IO),
        io.format(io.stderr_stream, "usage: %s <weekday>\n", [s(Program)], !IO),
        io.set_exit_status(1, !IO)
    ).

3.1 What file would this appear in?

It'd have to be 'daytype.m', to match the module name.

3.2 How would you compile it and use it?

With $ indicating the shell prompt:

$ mmc --make daytype
Making Mercury/int3s/daytype.int3
Making Mercury/ints/daytype.int
Making Mercury/cs/daytype.c
Making Mercury/os/daytype.o
Making daytype

$ ./daytype
usage: daytype <weekday>

$ ./daytype monday
daytype(monday) = "workday".

$ ./daytype Tuesday
daytype(tuesday) = "workday".

$ ./daytype wed
usage: daytype <weekday>

$ ./daytype wednesday
daytype(wednesday) = "humpday".

3.3 Why is this importing the 'string' and 'list' modules?

'list' is needed for the list literals in main/2, such as [DayString]. 'string' is needed for, not the string literals at least, but for the string operations, such as ++. 'string' is also required for any real use of io.format/4, as it contains the s/1, i/1, etc. functions, used to pass variously-typed data in a list.

3.4 So the list module is introducing new syntax? Am I going to run into lots of project-specific syntax with Mercury?

No, list literals are baked into Mercury, and they get translated to nested function calls; what the list module does is implement those functions, so that the translated literals result in a list.

3.5 What functions are those?

In the 'list' module they're actually type constructors. If you forget to include the 'list' module in some code that includes list literals, Mercury will give you some good hints:

daytype.m:033: In clause for predicate `main'/2:
daytype.m:033:   error: undefined symbol `[|]'/2
daytype.m:033:   (the module `list' has not been imported).
daytype.m:033: In clause for predicate `main'/2:
daytype.m:033:   in argument 2 of functor `[|]/2':
daytype.m:033:   error: undefined symbol `[]'/0.

3.6 So how flexible is Mercury's syntax? Obviously it doesn't have read macros.

Mercury doesn't have macros at all, and it doesn't let you define new operators, but it does have a large set of potential operators, with fixed fixity and priority, that you could use in your own modules.

Here's a very silly example of list literals that actually form strings:

:- module sillylist.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module string.

:- func [] = string.
[] = "end\n".

:- func [T | string] = string.
[X | S] = string(X) ++ ", " ++ S.

main(!IO) :-
    io.write_string([1, 2, 3, 4], !IO),
    io.write_string(["hello", "world"], !IO).

With output:

1, 2, 3, 4, end
"hello", "world", end

3.7 Moving on, is days an enum type?

It's a discriminated union, or an ML datatype. But where you would use an enum type in other languages, you can use a type declaration in Mercury (:- type) in this way.

The name of the resulting type is days/0 and it has seven type constructors or possible values: sunday/0, etc.

3.8 In some languages an enum can be converted to an int or a string; Ada has special attributes that remember the first and last enum, etc. Does Mercury have any 'value-added' information like this?

As soon as this type is defined, Mercury knows how to

  1. determine (with unification) if two values of this type are the same value
  2. produce (with string.string/1) a string representation of values of the type with "sunday", etc.
  3. parse a value of this type out of a string, as shown with this code's use of io.read_from_string/6.
  4. order days/0 values (with builtin.compare/3 and such, but not automatically with operators like < and such) by their order in the type's definition: monday is less than tuesday, sunday is less than saturday.

This functionality corresponds to the Haskell typeclasses Eq, Show, Read, and Ord, respectively.

3.9 :- func? Is that like a predicate declaration?

It's a function declaration. Function rules are very similar to predicate rules, but

  1. they have return values and so can appear within other goals as expressions (so you can write do_something(daytype(sunday)))
  2. functions have an assumed mode: all arguments are in, the return value is out, and the function is deterministic. You can override this, but you should probably use a predicate rule instead.

3.10 So this declares a datatype/1 function that accepts a days and returns a string.

Correct.

3.11 What is daytype(D) = R :- doing?

This is the head of a clause defining the datatype/1 function rule (the :- 'arrow' points from the body, which follows, to the head on the left.) It resembles a function call when the return value is bound to a variable, like DayType = daytype(friday) (or, in Mercury, the completely equivalent daytype(friday) = DayType).

3.12 And then… what's all this punctuation about? Are these parentheses used like curly braces in C?

The parens actually have the exact same meaning that they would have in a mathematical expression. In 1+(2*4), the parens keep you from reading this as "one plus two, making three …". Mercury has goals such as A, B, where the goal is true if A and B are both true, and it has goals such as A; B, where the goal is true if either A or B are true. So how would you read A, B; C, D? The answer, per precedence rules, is that this is true if either A, B is true or C, D is true. If what you wanted in fact was "for all of A, D, and one of B and C to be true", then you'd need parentheses: A, (B; C), D.

In fact, this clause without the outer parentheses is completely equivalent to the clause from the example:

daytype(D) = R :-
    (D = sunday; D = saturday),
    R = "weekend";

    (D = monday; D = tuesday; D = thursday; D = friday),
    R = "workday";

    D = wednesday,
    R = "humpday".

Style not recommended. The main problem with this style is that it is easy to miss the semicolons, or to read them as commas. Mercury code therefore tends to emphasize semicolons by padding them with spaces ((A ; B) rather than (A; B)) and by leading with the semicolon on the next line, rather than leaving it on the end of the previous line.

3.13 OK, but what is this code doing? How would this look if written in another programming language?

It's similar to a case statement, or to a pattern-matching control flow structure (case ... end in Erlang or match ... with in OCaml).

The basic form is (X = one, do_stuff; X = two, other_stuff; X = many, final_stuff), given a type defined with just one; two; many variants. Note that there's no 'default` or 'catch other cases' possible with just this syntax.

C:

switch (d) {
case sunday:
case saturday:
    r = "weekend";
    break;
case monday:
case tuesday:
case thursday:
case friday:
    r = "weekday";
    break;
case wednesday:
    r = "humpday";
    break;
}

Ada:

case D is
   when Sunday | Saturday => "weekend";
   when Monday | Tuesday | Thursday | Friday => "weekday";
   when Wednesday => "humpday";
end case;

3.14 OK, so you have a single variable that you test and it's magically interpreted as a case structure?

No, multiple variables are OK, and the case-like functionality is just how disjunctions work. Consider:

:- module fizzbuzz.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int, bool, string.

:- pred fizzbuzz(int::in, io::di, io::uo) is det.
fizzbuzz(N, !IO) :-
    DivBy3 = ( if N mod 3 = 0 then yes else no ),
    DivBy5 = ( if N mod 5 = 0 then yes else no ),
    (
        DivBy3 = yes, DivBy5 = yes, R = "FizzBuzz"
    ;
        DivBy3 = yes, DivBy5 = no,  R = "Fizz"
    ;
        DivBy3 = no, DivBy5 = yes,  R = "Buzz"
    ;
        DivBy3 = no, DivBy5 = no,   R = string.string(N)
    ),
    io.print_line(R, !IO).

main(!IO) :-
    iorange(fizzbuzz, 1, 100, !IO).

:- pred iorange(pred(int, io, io), int, int, io, io).
:- mode iorange(pred(in, di, uo) is det, in, in, di, uo) is det.
iorange(P, N, Limit, !IO) :-
    ( if N =< Limit then
        P(N, !IO),
        iorange(P, N + 1, Limit, !IO)
    else
        true
    ).

And this alternate implementation of fizzbuzz/3:

fizzbuzz(N, !IO) :-
    DivBy3 = ( if N mod 3 = 0 then yes else no ),
    DivBy5 = ( if N mod 5 = 0 then yes else no ),
    ( if
        (
            DivBy3 = yes, DivBy5 = yes, R = "FizzBuzz"
        ;
            DivBy3 = yes, DivBy5 = no,  R = "Fizz"
        ;
            DivBy3 = no, DivBy5 = yes,  R = "Buzz"
        )
    then
        io.print_line(R, !IO)
    else
        io.print_line(N, !IO)
    ).

The first example uses a deterministic disjunction, as it exhausts every possible combination of its 'inputs' (DivBy3 and DivBy5), and the second uses a semideterministic disjunction, which fails in the 'no, no' case.

3.15 How else might daytype/1 be defined?

Briefly, simulating a case statement with an 'otherwise' by using an incomplete 'case' within an 'if/then/else':

daytype(D) = R :-
    % ( this_might_fail -> it_succeeded; it_failed )
    (
        % this 'case structure' is incomplete, it doesn't have wednesday,
        % so it can fail in that case
        % ... if you look closely, this example is repeated in itself
        (
            (D = sunday; D = saturday),
            R0 = "weekend"
        ;
            (D = monday; D = tuesday; D = thursday; D = friday),
            R0 = "workday"
        )
    ->
        % success:
        R = R0
    ;
        % failure:
        R = "humpday"
    ).

With function facts:

daytype(sunday) = "weekend".
daytype(monday) = "workday".
daytype(tuesday) = "workday".
daytype(wednesday) = "humpday".
daytype(thursday) = "workday".
daytype(friday) = "workday".
daytype(saturday) = "weekend".

With nothing but if/then/elses (and using an expression in the head, rather than a goal in the body):

daytype(D) = (D = wednesday -> "humpday"; (D = sunday; D = saturday) -> "weekend"; "workday").

An if/then/else with horizontal formatting:

daytype(D) =
    (
        D = wednesday               ->  "humpday";
        (D = sunday; D = saturday)  ->  "weekend";
                                        "workday"
    ).

And more typical formatting:

daytype(D) = R :-
    (
        D = wednesday  % if test1
    ->
        R = "humpday"
    ;
        (D = sunday; D = saturday)  % elsif test2
    ->
        R = "weekend"
    ; % else
        R = "workday"
    ).

Or with if/then/else syntax:

daytype(D) = R :-
    ( if D = wednesday then
        R = "humpday"
    else if D = sunday ; D = saturday then
        R = "weekend"
    else
        R = "workday"
    ).

3.16 Which of those should I use, though?

In general, in an exhaustive case like this where you're mapping every single possible value of a type to some other values, I'd consider the version in the original example and the "function facts" version, and here I'd chose the original because so many of the resulting values are the same (four days are all "workday"; there are seven possible inputs and three possible outputs).

The original and the "function facts" version both have a safety net: if you forget a case, or if an eighth day of the week is added in the future and you forget to update this function, then Mercury will complain and you'll know to fix it. This safety net is easily dropped when you involve conditionals.

If conditional code is more appropriate, then the last version with if/then/else is generally recommended.

3.17 Why is if/then/else what's recommended? (A -> B; C) looks nice too.

First, (A -> B; C) has B; C in it, which is visually identical to a disjunction, until you notice the connected A ->. This syntactic vagueness is more seriously felt in chained conditionals where you have to do a lot of reading ahead to be sure of what you're looking at.

:- func daytype(days) = string.
daytype(D) = R :-
    (
        D = wednesday                % is this intended to be a test?
    ->                               % ok that -> tells me it is
        R = "humpday"
    ;
        (D = sunday; D = saturday)   % is this a test or an 'else' case?
    ->                               %  ok that -> tells me it's a test
        R = "weekend"
    ;
        R = "workday"                % is this a test or an 'else' case?
    ).                               % no -> so this time it's an 'else'.

Second, and due to the same similarity with disjunctions, a mistake while reformatting code or when intentionally mixing conditionals and disjunctions can result in very confusing errors.

Third, if you have a background in Prolog, then (A -> B; C) in Mercury isn't quite what you're used to.

Fourth, you can more conveniently mix disjunctions with if/then/else syntax. The following example would need parentheses around the D = sunday; D = saturday disjunction if it used the other syntax.

daytype(D) = R :-
    ( if D = wednesday then
        R = "humpday"
    else if D = sunday ; D = saturday then
        R = "weekend"
    else
        R = "workday"
    ).

3.18 Moving on, it looks like you get the command line arguments into Args.

Yep.

3.19 And then, are these parentheses required?

Yes, even though there's no ambiguity with the if clearly marking where the conditional begins. With the other syntax, ( might_fail -> it_succeeded; it_failed ) , dropping the parentheses results in the call to io.command_line_arguments/3 getting included in the might_fail.

(I/O code isn't allowed to fail.)

3.20 That's four different goals in the might_fail, is that OK?

Absolutely. This is just A, B, C, D, where all of A and B and C and D must be true, or must succeed, for the overall goal to succeed.

This is similar to if (a && b && c && d) ... in C.

3.21 How do I know which goal failed, though? Which of these can fail?

If zero arguments are passed, or if two or more arguments are passed, then Args = [DayString] will fail, as Args is unified with a list with a single element. The other possible failure is in the fourth argument to io.read_from_string/6 (despite being from the io module, it doesn't accept !IO parameters so it's OK for it to appear in code that can fail): this argument is unified with ok/1.

If you care which failed, say to produce different error messages, you'll have to have nested conditional code: an if (a) { if (b) rather than this if (a && b).

3.22 OK, but what are these goals doing? What's the test?

In English, the test is

  1. is Args a list with just one element, which I'll call DayString?
  2. always true: Lowered is the lowercase version of DayString
  3. always true: Term is Lowered with a trailing dot.
  4. always true: try and read a term from the string Term (with a bunch of extra arguments for error messages and more complex uses of this predicate)
  5. did #4 successfully read a term? I'll call the term Day if so.

Those last two points might be more clear if written like so:

io.read_from_string("args", Term, length(Term),
    Result, io.posn(0, 0, 0), _),
Result = ok(Day)

3.23 How does that read_from_string know we're looking for a days value?

That predicate's polymorphic, with a type declaration that includes type variables: it returns an io.read_result(T), where T is "whatever type here".

As used here, however, Mercury knows that T can only be days, because the code goes on to pass the value of type T to daytype/1, which only accepts days. (If it weren't clear, Mercury would complain at compile-time and you could explicitly annotate the type. The need for this is rare.)

3.24 OK. What's this s(Var) stuff about?

If you look up io.format/4 for example you'll find this:

    % Formats the specified arguments according to the format string,
    % using string.format, and then writes the result to the current
    % output stream or to the specified output stream.
    % (See the documentation of string.format for details.)
    %
:- pred format(string::in, list(poly_type)::in, io::di, io::uo) is det.
:- pred format(io.text_output_stream::in, string::in, list(poly_type)::in,
    io::di, io::uo) is det.

That part about string.format leads you to much more extensive documentation, but the key part is the list(poly_type) argument, which is what we're providing with [s(Lowered), s(daytype(Day))] in one call, or [s(Program)] in the other. That poly_type is defined in the string module as:

:- type poly_type
    --->    f(float)
    ;       i(int)
    ;       s(string)
    ;       c(char).

So s(Var) constructs a poly_type, and this code passes a list of poly_type to io.format, which can then use pattern matching to print out floats, ints, etc.

3.25 What might that pattern matching look like?

This example shows two different ways to do it:

:- module poly_ex.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module string, list, int, float.

main(!IO) :-
    foldl((pred(X::in, !.IO::di, !:IO::uo) is det :-
        io.print(typename(X), !IO), io.nl(!IO),
        io.print(doubled(X), !IO), io.nl(!IO)), Stuff, !IO),
    Stuff = [s("hi"), i(42), i(101), s("lol")].

:- func typename(poly_type) = string.
typename(i(_)) = "int".
typename(f(_)) = "float".
typename(s(_)) = "string".
typename(c(_)) = "char".

:- func doubled(poly_type) = poly_type.
doubled(P) = R :-
    (
        P = i(N),
        R = i(N + N)
    ;
        P = f(N),
        R = f(N + N)
    ;
        P = s(S),
        R = s(S ++ S)
    ;
        P = c(C),
        R = s(from_char_list([C, C]))
    ).

Output:

string
s("hihi")
int
i(84)
int
i(202)
string
s("lollol")

4 Cast of characters

Consider this complete application:

SRC: people.m

:- module people.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module string, list, int.

:- type sexes ---> male; female.
:- type person
    --->    person(
                name :: string,
                age :: int,
                sex :: sexes
            ).

:- func majority = int.
majority = 17.

:- func youth(person) = string.
youth(person(_, Age, male)) = (if Age > majority then "man" else "boy").
youth(person(_, Age, female)) = (if Age > majority then "woman" else "girl").

main(!IO) :-
    foldl(people.print, People, !IO),
    People = [
        person("Alice", 24, female),
        person("Bob", 42, male),
        person("Eve", 51, female),
        person("Malice", 15, male)
    ].

:- pred print(person::in, io::di, io::uo) is det.
print(P, !IO) :-
    io.format("%s is a %d-year-old %s\n",
        [s(P^name), i(P^age), s(youth(P))], !IO).

4.1 How would you summarize all of the declarations in this code?

  • There's a module named people
  • this module is the entry point of an application
  • this module's implementation uses the 'string', 'list', and 'int' modules (in addition to 'io')
  • a type sexes/0 has two constructors, male/0 and female/0.
  • a type person/0 has a single constructor, person/3
  • there's a function rule majority/0 that returns an int.
  • and a function rule youth/1 that takes a person and returns a string.
  • and a print/3 predicate rule that takes a person and does I/O.

4.2 What's that 'name', 'age' stuff in the declaration of person/0?

Those are optional field names. You can see them elided in the definition of youth/1 where the contents of person/3 are pattern-matched out by position, and you can see them used in the definition of print/3, where P^name fetches the name, etc.

4.3 Is majority a constant?

Well,

  1. it's a function that takes no arguments.
  2. because the code doesn't say otherwise, and because it's a function, it's also deterministic, which means it has exactly one solution for a given set of arguments.
  3. the set of all possible arguments has only one member: no arguments.
  4. therefore, this function can only ever return the same value.

So, yes. If you look at compiled code you'll just see 17 where it's used.

4.4 What's the type of People?

list(person)

4.5 Is that foldl/4 passing each element of People to print/3, along with the IO arguments?

Yep. It threads the I/O arguments appropriately. There are many, many other variants of list.foldl, but this one is useful for simple "do some I/O with the contents of this list" kinda loops.

4.6 Why is it people.print instead of just print ?

io.print/3 is included into this module and it can also print a person/0 type, so a bare print is ambiguous and you get a compile-time error about it:

people.m:020: In clause for predicate `main'/2:
people.m:020:   error: ambiguous overloading causes type ambiguity.
people.m:020:   In clause for predicate `main'/2:
people.m:020:   warning: highly ambiguous overloading.
people.m:020:   The following symbols were overloaded in the following
people.m:020:   contexts.
people.m:021:   The predicate symbol predicate `foldl'/4.
people.m:021:   The possible matches are:
people.m:021:     predicate `string.foldl'/4,
people.m:021:     predicate `list.foldl'/4.
people.m:021:   The function symbol `print'/0.
people.m:021:   The possible matches are:
people.m:021:     predicate `people.print'/3,
people.m:021:     predicate `io.print'/3,
people.m:021:     predicate `io.print'/4,

4.7 Wait a moment, that error's saying that a 'print' call could refer to io.print/3 or io.print/4. Doesn't the number of arguments make it obvious that it can only be one of these?

Mercury also supports currying. Here's a example of just that:

:- module curry.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int.

:- func add_four(int, int, int, int) = int.
add_four(A, B, C, D) = A + B + C + D.

main(!IO) :-
    F1 = add_four(1, 2, 3),
    F2 = add_four(1, 2),
    io.write_line(add_four(5, 5, 5, 5), !IO),
    io.write_line(F1(-6), !IO),
    io.write_line(F2(0, 0), !IO),

    io.nl(!IO),

    io.write_line(type_of(F1), !IO),
    io.write_line(type_of(F2), !IO),
    io.write_line(type_of(F2(0, 0)), !IO).

With output:

20
0
3

func(int) = int
func(int, int) = int
int

Ambiguity due to potential currying is when you'll most often run into a need for type annotations.

4.8 Could you use a 'lambda' or a rule literal in place of that people.print ?

Sure. Using a higher-order predicate term:

main(!IO) :-
    foldl(Print, People, !IO),
    People = [
        person("Alice", 24, female),
        person("Bob", 42, male),
        person("Eve", 51, female),
        person("Malice", 15, male)
    ],
    Print = (pred(P::in, !.IO::di, !:IO::uo) is det :-
                io.format("%s is a %d-year-old %s\n",
                [s(P^name), i(P^age), s(youth(P))], !IO)).

Or equivalently:

main(!IO) :-
    foldl((pred(P::in, !.IO::di, !:IO::uo) is det :-
            io.format("%s is a %d-year-old %s\n",
            [s(P^name), i(P^age), s(youth(P))], !IO)), [
        person("Alice", 24, female),
        person("Bob", 42, male),
        person("Eve", 51, female),
        person("Malice", 15, male)
    ], !IO).

4.9 You can't use !IO in the parameters of a 'higher-order predicate term'?

No, with this syntax you need to provide a variable with a mode for each argument, and the !Var syntax doesn't come with a way to pass the two modes for the two variables it expands to. After all you could pass an array through a higher-order predicate term with !.A::array_di, !:A::array_uo args, which differs from di / uo.

4.10 So, this list is statically known, and short. Does Mercury unroll the foldl loop?

It does with -O4 --intermodule-optimization flags, yes.

4.11 How could you process the list without list.foldl?

Lists are recursively defined data structures (the tail of a list is a list), so write a recursive rule:

main(!IO) :-
    print_list(People, !IO),
    People = [
        person("Alice", 24, female),
        person("Bob", 42, male),
        person("Eve", 51, female),
        person("Malice", 15, male)
    ].

:- pred print_list(list(person)::in, io::di, io::uo) is det.
print_list([], !IO).
print_list([P | Ps], !IO) :-
    people.print(P, !IO),
    print_list(Ps, !IO).

5 The secret Zebra-keeper

Consider this puzzle, copied from stackoverflow:

There is a street with three neighboring houses that all have a different color. They are red, blue, and green. People of different nationalities live in the different houses and they all have a different pet. Here are some more facts about them:

  • The Englishman lives in the red house.
  • The jaguar is the pet of the Spanish family.
  • The Japanese lives to the right of the snail keeper.
  • The snail keeper lives to the left of the blue house.

Who keeps the zebra?

Solve this puzzle in Mercury.

5.1 Could I solve it the same way I would in Prolog?

Partially, for a puzzle this simple. You would want to loop over valid solutions with the 'solutions' module and print the solutions out, and this relatively mundane code would be very different in Mercury.

5.2 Could I solve it the same way I would in a non-logical language?

You certainly could, but it would be much more difficult to confirm that the resulting code actually implements the task, and it would be much more difficult to change the code if the specifics of the task (like real-world, non-puzzle tasks) were to change over time. You should take advantage of what Mercury has to offer here.

5.3 And what does Mercury offer, that's so helpful?

Let's start the colors of houses. In Mercury you can make 'colors' a type, and then define a 'multideterministic' predicate that provides the colors.

:- type colors ---> red; blue; green.

:- pred color(colors::out) is multi.
color(red).
color(blue).
color(green).

5.4 What does it mean, that this is a 'multi' predicate?

It can succeed more than one time. In this case, a goal like color(X) can bind X against any of those three colors.

The value of this is easier to see when it's used:

:- type person ---> alice; bob.

:- pred likes(person::in, color::in) is semidet.
likes(alice, red).
likes(alice, green).
likes(bob, blue).

:- pred acceptable_color(person::in, color::out) is nondet.
acceptable_color(P, C) :-
    color(C),
    likes(P, C).

This defines two people, Alice and Bob, and establishes their tastes in colors. Thus, if acceptable_color(bob, C) is a goal, it'll succeed with C bound to blue.

You can imagine it happens like this:

  • acceptable_color(bob, Color) is a goal.
  • in acceptable_color/2:
    • color binds C to red.
    • likes(bob, red) fails.
    • (backtrack) color binds C to blue.
    • likes(bob, blue) succeeds.
  • acceptable_color/2 succeeds
  • Color is bound to blue

(And with well-positioned trace goals you can see exactly how the search space is navigated, for a real application.)

5.5 So, big picture, how do I solve this puzzle?

  1. create types for the data the puzzle requires (the pets, etc.)
  2. create 'multi' predicates, defined by predicate facts clauses, for all of this data
  3. write a 'nondet' predicate that binds variables with puzzle data and then asserts the puzzle's relationships
  4. print out all the possible solutions to this predicate

5.6 Alright, so, a module that'll do I/O, with puzzle data…

It might start like this:

:- module puzzle.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.

:- type races ---> english; japanese; spanish.
:- type colors ---> red; blue; green.
:- type pets ---> jaguar; snail; zebra.
:- type house
    --->    house(
                race :: races,
                color :: colors,
                pet :: pets
            ).

:- pred race(races::out) is multi.
race(english).
race(japanese).
race(spanish).

:- pred color(colors::out) is multi.
color(red).
color(blue).
color(green).

:- pred pet(pets::out) is multi.
pet(jaguar).
pet(snail).
pet(zebra).

main(!IO) :-
    io.write_string("Something about the solutions module?\n", !IO).

5.7 I then need a way to generate valid houses …

You might start with this:

:- pred house(house::out) is nondet.
house(house(R, H, P)) :-
    race(R), color(H), pet(P),

    % The Englishman lives in the red house.
    ( R = english -> H = red; true ),
    ( H = red -> R = english; true ),

    % The jaguar is the pet of the Spanish family.
    ( R = spanish -> P = jaguar; true ),
    ( P = jaguar -> R = spanish; true ),

    % The Japanese lives to the right of the snail keeper
    % (for this predicate's purposes: the Japanese is *not* the snail keeper)
    ( R = japanese -> not P = snail; true ),
    ( P = snail -> not R = japanese; true ),

    % The snail keeper lives to the left of the blue house
    ( P = snail -> not H = blue; true ),
    ( H = blue -> not P = snail; true ).

5.8 What are those conditionals doing?

Taking the first one,

  • if R = english, then H = red, otherwise it's OK
  • H = red either succeeds or fails. It succeeds only if H happens to be red.
  • result: house/1 cannot generate a house that contains an Englishman that isn't red. For Englishmen, all the non-red colors would fail at this point.

The second conditional reverses the logic: if it's a red house, then any inhabitant but an Englishman should result in a failure.

5.9 That's really tedious though, with the "else true", and two conditionals per puzzle rule. Can it be done better?

It certainly can, if you study Mercury goals and think through the logic. This is equivalent to the previous example:

:- pred house(house::out) is nondet.
house(house(R, H, P)) :-
    race(R), color(H), pet(P),
    R = english <=> H = red,
    R = spanish <=> P = jaguar,
    not (R = japanese, P = snail),
    not (P = snail, H = blue).

5.10 I looked at that Mercury goals page and– how the heck is this the same??

Consider these two goals:

% goal 1
( R = english -> H = red; true )

% goal 2
R = english => H = red 

Think of them as a pure predicate that takes the success of the two goals as inputs, then either succeeds or fails. The set of all possible inputs is 4 in size, and each input yields success or failure, so it's easy to just consider every possible case.

5.10.1 goal #1 (conditional)

R = english H = red result?
true true true
true fail fail
fail true true
fail fail true

if R = english, then the result is the result of H = red.

If not R = english, then the result is always true.

5.10.2 goal #2 (implication)

It's an abbreviation for not (R = english, not H = red)

R = english H = red result?
true true true
true fail fail
fail true true
fail fail true

if R = english, then not H = red is tried. If H = red then the not reverses that, and the parenthesized conjugation fails, which is reversed by the outer not into success.

When R = english and not H = red are both true, then the parenthesized conjugation is true, which is reversed by the outer not into failure.

if not R = english, then the parenthesized conjugation always fails and this failure is reversed by the outer not, always resulting in success.

5.10.3 conclusion

These goals map the same inputs to the same outputs.

QED, they're the same.

5.11 OK, now I need a way to generate valid rows of houses.

You might do that this way:

:- pred distinct(house::in, house::in) is semidet.
distinct(house(R1, C1, P1), house(R2, C2, P2)) :-
    not (R1 = R2; C1 = C2; P1 = P2).

:- pred row(house::out, house::out, house::out) is nondet.
row(A, B, C) :-
    house(A), house(B), house(C),
    A^pet = snail       <=> B^race = japanese,
    B^pet = snail       <=> C^race = japanese,
    C^color = blue      <=> B^pet = snail,
    B^color = blue      <=> A^pet = snail,
    not A^race = japanese,
    not C^pet = snail,
    distinct(A, B), distinct(B, C), distinct(A, C).

5.12 How would I print out all the possible solutions for row/3 ?

You can import the 'solutions' module and do this:

main(!IO) :-
    solutions((pred([A, B, C]::out) is nondet :-
        row(A, B, C)), Solutions),
    ( if Solutions = [] then
        io.write_string("Impossible puzzle.\n", !IO)
    else
        foldl((pred(L::in, !.IO::di, !:IO::uo) is det :-
            io.print(L, !IO),
            io.nl(!IO)), Solutions, !IO)
    ).

Thet gets all the rows of houses, each row into its own list, and these lists are collected into the Solutions list.

5.13 What's the type of Solutions?

list(list(house))

5.14 Do I really need that 'lambda' there? Why not define a new row/1 predicate?

You could certainly do that. The line in main/2 would then be this simple:

solutions(row, Solutions),

5.15 I notice that if I add a fourth house color, but don't update anything, that Mercury doesn't complain. Can I get it to warn me about 'multi' predicates that don't output all possible values?

You can do this:

:- pred color(colors).
:- mode color(out) is multi.
:- mode color(in) is det.
color(red).
color(blue).
color(green).

So you get the 'multi' mode that you want to supply color values, but Mercury now also requires that it be deterministic if you pass a color into the predicate. So if you add a new yellow color to the type but forget to update this predicate, you'll get an error:

puzzle.m:062: In `color'(in):
puzzle.m:062:   error: determinism declaration not satisfied.
puzzle.m:062:   Declared `det', inferred `semidet'.
puzzle.m:063:   The switch on HeadVar__1 does not cover
puzzle.m:063:     `yellow'/0.

It's inferred semidet as the goal color(yellow) would fail.

The HeadVar__1 comes from something like the following, an equivalent transformation of the last example:

color(HeadVar__1) :-
    (
        HeadVar__1 = red
    ;
        HeadVar__1 = blue
    ;
        HeadVar__1 = green
    ).

5.16 And altogether…

SRC: puzzle.m

:- module puzzle.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module list, string, solutions.

:- type races ---> english; japanese; spanish.
:- type colors ---> red; blue; green.
:- type pets ---> jaguar; snail; zebra.
:- type house
    --->    house(
                race :: races,
                color :: colors,
                pet :: pets
            ).

:- pred distinct(house::in, house::in) is semidet.
distinct(house(R1, C1, P1), house(R2, C2, P2)) :-
    not (R1 = R2 ; C1 = C2 ; P1 = P2).

:- pred row(list(house)::out) is nondet.
row([A, B, C]) :-
    house(A), house(B), house(C),

    A^pet = snail       <=> B^race = japanese,
    B^pet = snail       <=> C^race = japanese,

    C^color = blue      <=> B^pet = snail,
    B^color = blue      <=> A^pet = snail,

    not A^race = japanese,
    not C^pet = snail,

    distinct(A, B), distinct(B, C), distinct(A, C).

:- pred house(house::out) is nondet.
house(house(R, H, P)) :-
    race(R), color(H), pet(P),

    R = english <=> H = red,
    R = spanish <=> P = jaguar,

    not (R = japanese, P = snail),
    not (P = snail, H = blue).

main(!IO) :-
    solutions(row, Solutions),
    ( if Solutions = [] then
        io.write_string("Impossible puzzle.\n", !IO)
    else
        foldl((pred(L::in, !.IO::di, !:IO::uo) is det :-
            io.print(L, !IO),
            io.nl(!IO)), Solutions, !IO)
    ).

:- pred race(races::out) is multi.
race(english).
race(japanese).
race(spanish).

:- pred color(colors).
:- mode color(out) is multi.
:- mode color(in) is det.
color(red).
color(blue).
color(green).

:- pred pet(pets::out) is multi.
pet(jaguar).
pet(snail).
pet(zebra).

6 Pure randomness

Consider this complete application:

SRC: roll.m

:- module roll.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- use_module random.
:- import_module list, string.

main(!IO) :-
    some [!RS] (
        random.init(seed, !:RS),
        random.random(0, 100, Roll, !.RS, _)
    ),
    io.format("You rolled %d on the d100 die.\n", [i(Roll)], !IO).

:- mutable(seed, int, 0, ground, [untrailed]).
:- initialise init_seed/0.

:- pragma promise_pure seed/0.
:- func seed = int.
seed = N :-
    semipure get_seed(N).

:- impure pred init_seed is det.
init_seed :-
    impure Time = epochtime,
    impure set_seed(Time).

:- pragma foreign_decl("C", "#include <time.h>").

:- impure func epochtime = int.
:- pragma foreign_proc("C",
    epochtime = (Time::out),
    [will_not_call_mercury],
"
    Time = time(NULL);
").

6.1 Is this really the smallest dice-roller in Mercury?

No. You'd save a lot by attaching epochtime to I/O and by not bothering with the state variable:

main(!IO) :-
    epochtime(Now, !IO),
    random.init(Now, RS),
    random.random(0, 100, Roll, RS, _),
    io.format("You rolled %d on the d100 die.\n", [i(Roll)], !IO).

:- pragma foreign_decl("C", "#include <time.h>").
:- pred epochtime(int::out, io::di, io::uo) is det.
:- pragma foreign_proc("C",
    epochtime(Time::out, _IO0::di, _IO::uo),
    [promise_pure, will_not_call_mercury],
"
    Time = time(NULL);
").

6.2 Why do it this way, then?

In the attach-to-IO example, epochtime's output isn't a constant: the exact answer depends on when it's called, or on the 'state of the world' argument. In the impure example, seed is constant at runtime, but can vary between runs. So if you have any data like this, that doesn't mutate as far as your program is concerned, but which can't be set in stone until your program starts, then this example might be a model for you to follow. You could still structure such programs by getting this data with I/O predicates at the start of the program, and then passing the data to what needs it.

And generally random.supply is precisely what you'd want to keep in a state variable, as you want to use it repeatedly to get multiple random results, and want to avoid reusing randomness.

6.3 OK. What's that some about?

It's an existential quantification, from predicate logic. some [X] Goal means "there exists a variable X for which Goal is true", as opposed to all [X] Goal, a universal quantification, which means "for all possible values of X, Goal is true".

6.4 … isn't it enough to say Goal, if it includes an X? If we're talking about an X at all, isn't it obviously already true that we're talking about "some X"?

Well, yeah, which is why you've seen lots of variables up til now, with neither of these quantifiers. Mercury implicitly quantifies variables into their natural scope, as documented.

For state variables though, it's a deliberate design decision to not implicitly quantify them unless they're in the head of the variable. This makes for more readable code. It also makes more readable error messages in the case that state variables are misused. So this example needs some [X] Goal just to have the !RS state variable at all.

Explicit quantification also lets you naturally and efficiently write conditionals that make localized use of nondeterministic predicates, to test for example whether "p(X) is true of some member X of this list". Here's a quick example:

:- module numbers.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module list, string.

main(!IO) :-
    io.command_line_arguments(Args, !IO),
    ( if all [Arg] (member(Arg, Args) => to_int(Arg, _)) then
        io.write_string("all arguments are valid numbers\n", !IO)
    else
        io.write_string("an argument isn't a number!\n", !IO)
    ).

With usage:

$ ./numbers 
all arguments are valid numbers

$ ./numbers 1 2 3
all arguments are valid numbers

$ ./numbers 1 two 3
an argument isn't a number!

6.5 And :- mutable(seed, int, 0, ground, [untrailed]). ?

This establishes a module-scoped mutable variable named 'seed', of type 'int', of initial value '0', of instantiation 'ground', and with the attribute 'untrailed'. The manual is pretty clear about how mutable variables can be used.

6.6 Uh, instantiation?

In the way that a variable's type tells you about the set of values that a variable might be bound to, a variable's instantiation tells you how or whether it's bound to a value. The easiest way to see this is in motion, such as in these standard modes that map a before inst to an after inst:

:- mode in == ground >> ground.
:- mode out == free >> ground.

So when you see a goal foo(A, B), of which there's a declaration :- pred foo(int::in, int::out), you know that before the call to foo/2, A is already bound to a value, but B isn't yet, and then that after the call, A is still bound to a value, and B is newly bound to a value.

6.7 OK, but other languages have in/out variables and they don't invoke instantiation to talk about what's going on. What's the point?

  1. unique is also an inst, and uniqueness is critical to how Mercury can have efficient side effects while retaining the advantages of a pure functional language.
  2. a compound type in Mercury can have members with different instantiations, which is especially important when some of those members are unique, and which can prevent you from using normal in and out modes for the new type.
  3. Predicates and atypical functions are not ground, so higher order code can easily require some custom insts.
  4. Mercury can use insts to gain some limited compile-time guarantees similar to those provided by dependent-typed languages (ATS, Idris, etc.). For example, the standard library occasionally deals in non_empty_list variables, which are list-typed variables that cannot be bound to the empty list, [].

(By 'atypical function' I mean a function that isn't "all in parameters, one out return, is det".)

6.8 Moving on, what's the initialize doing?

It's actually 'initialise' with an 's' in the example, but Mercury accepts either spelling. This declaration causes the following function to be called prior to the application main/2, to perform any initialization needed by the module it's in.

The manual's pretty clear, again.

6.9 What does it mean to promise that seed/0 is pure?

It means that seed/0 can appear in pure code and doesn't need to be invoked like semipure seed = Seed. In short, it means that this function is pure. It's up to the programmer to ensure that it really is pure. To confirm that, consider the precise meanings of the purity levels in Mercury.

The manual is (again!) very easy to understand on purity, but:

  1. the meaning of foo(A, B) depends only on the meaning and values of foo/2, A, and B.
  2. the meaning of semipure foo(A, B) depends on that but also on the invocations of impure predicates.
  3. the meaning of impure foo(A, B) depends on all that, but also can alter the meaning of semipure and impure goals.

Note that impure foo(A, B) still isn't chaos foo(A, B): it's only semipure and impure goals that can be altered by the invocation of an impure goal. So Mercury still can't be as flexible as self-altering assembler, in which a routine might reach out and arbitrarily change the rest of the program.

6.10 Isn't seed/0 actually semipure then? Since its meaning will change if init_seed/0 is called again.

The basis of the promise is that it isn't called again. You could guard against that by changing init_seed/0 to throw an error on a second invocation, or to have no effect.

This is a good example though of the dangers of the promise_pure pragma, though. Mercury can't check the validity of your promises for you.

6.11 Looking at the clause for init_seed/0, is it impossible to have a semipure or impure expression?

Indeed, that couldn't be written impure set_seed(impure epochtime).

6.12 So the rest of this is Mercury's C FFI. With those strings… how well is this checked?

When Mercury's compiled to C, your C declarations get put in the generated C by other declarations, and your C procedure bodies get put in the generated code like other predicates. If you look, you'll often see the literal string inlined right in the middle of a larger generated C function.

So, not checked at all except by the C compiler. Mercury's FFI is feather-light and feather-cheap. On the downside, Mercury library wrappers can much longer than they'd be in a language that puts more work into its FFI, and you can already see this by how a single line of C requires 4-6 additional lines of Mercury. On the upside, Mercury's FFI can be enormously easier to work with, as the ability to write free-hand C saves you from the otherwise universal restriction of language FFIs, that you have to map, 1:1, foreign functions and types to your functions and types.

6.13 Eh, this sort of FFI is easier? Really?

Very. For example:

:- pred server_2(string::in, int::in, server_failures::out,
                 int::out, server::out, io::di, io::uo) is det.
:- pragma foreign_proc("C",
    server_2(Port::in, Backlog::in, Result::out,
             Error::out, Server::out, IO0::di, IO::uo),
    [will_not_call_mercury, promise_pure, tabled_for_io, thread_safe],
"
    int yes = 1;
    struct addrinfo hints, *res;

    memset(&hints, 0, sizeof hints);
    hints.ai_family = AF_UNSPEC;
    hints.ai_socktype = SOCK_STREAM;
    hints.ai_flags = AI_PASSIVE;
    if (getaddrinfo(NULL, Port, &hints, &res) < 0) {
        Server = -1;
        Result = NSF_GETADDRINFO;
        Error = errno;
    } else {
        Server = socket(res->ai_family, res->ai_socktype, res->ai_protocol);
        if (Server < 0) {
            Result = NSF_SOCKET;
            Error = errno;
        } else {
            setsockopt(Server, SOL_SOCKET, SO_REUSEADDR, &yes, sizeof yes);
            if (bind(Server, res->ai_addr, res->ai_addrlen) < 0) {
                Result = NSF_BIND;
                Error = errno;
            } else {
                Result = NSF_LISTEN;
                if (listen(Server, Backlog) < 0) {
                    Error = errno;
                } else {
                    Error = 0;
                }
            }
        }
    }

    IO = IO0;
").

This defines a single predicate, server_2/7, that creates a server socket, binds it using the modern getaddrinfo interface, and sets it up to receive client connections, while returning a Mercury value (those NSF_ symbols are exported and transformed from Mercury so that C can use them) indicating what failed, if anything did.

This may not look very pretty because the socket interface isn't pretty, but all of the ugliness is encapsulated in this code, which is easy (for the C programmer) to understand, and easy (for the Mercury programmer) to use. The typical alternative to this is a bunch of individual FFI mappings of socket, getaddrinfo, etc. into your language, and God help you when it comes to populating that hints structure, or portably providing those socket option constants.

Sometimes the FFI you get from other languages is so annoying that you'll find yourself writing a C library that you can build the FFI against, that itself has code like the above in a single function. This is just recreating Mercury's style of FFI with more overhead.

7 Troubleshooting and optimizing a function

Consider this complete application:

:- module fib.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module int, list, string.

main(!IO) :-
    io.command_line_arguments(Args, !IO),
    ( if
        Args = [NStr],
        to_int(NStr, N)
    then
        io.format("fib(%d) = %d\n", [i(N), i(fib(N))], !IO)
    else
        io.set_exit_status(1, !IO)
    ).

:- func fib(int) = int.
fib(N) = R :-
    ( if N < 2 then
        R = N
    else
        R = fib(N - 1) + fib(N - 3)
    ).

7.1 Is there anything new in this code?

There's nothing new in it, but there are two problems with it. But let's look at how this program runs:

$ time ./fib 20
fib(20) = 277

real	0m0.021s
user	0m0.008s
sys	0m0.013s

$ time ./fib 40
fib(40) = 578949

real	0m0.033s
user	0m0.019s
sys	0m0.014s

$ time ./fib 50
fib(50) = 26467299

real	0m0.567s
user	0m0.553s
sys	0m0.014s

$ time ./fib 55
fib(55) = 178955183

real	0m3.675s
user	0m3.658s
sys	0m0.013s

$ time ./fib 60
fib(60) = 1209982081

real	0m24.797s
user	0m24.737s
sys	0m0.036s

7.2 Are the 'two problems' that it's wrong and slow?

Indeed. Let's try tracing the function's inputs and outputs.

7.3 Trace it, by rewriting it to use I/O and using 'print debugging'?

That wouldn't be a lot of work in this specific case, but in general it could be really hellish if that's what you had to do to trace a pure function. Consider the case where your I/O code is very far removed from the function that you want to trace: you'd have to ferry the I/O variables through all of the intermediate code, and then it'd be a pain to reverse all that afterwards.

7.4 Trace it, by using a function-tracing feature of the compiler, that shows each function invocation with parameter and return values?

That could be useful in this case, but it'd probably be hard for a feature like that to be generally useful. You might only care about certain inputs, or you might need to do some extra work to actually be able to print a human-understandable version of the arguments, or you might want information about some variables internal to a function.

In Mercury you can add trace goals:

fib(N) = R :-
    trace [io(!IO)] (io.format("fib(%d) = %d.\n", [i(N), i(R)], !IO)),
    ( if N < 2 then
        R = N
    else
        R = fib(N - 1) + fib(N - 3)
    ).

7.5 By the pattern so far, is that trace [Variables] Goal?

It's trace [Params] Goal, as you can have stuff like that io/2 rather than just variables.

7.6 Is that io/2 creating the I/O variables out of thin air, for use in the goal?

Sure. The code outside of the trace goal is normal Mercury, and the code inside of the trace goal is normal Mercury, but there's a logical disconnect there as the inner Mercury is referring to variables that it shouldn't have access to. The manual says a lot about other parameters that you can provide to trace goals.

7.7 What's this trace output look like?

$ ./fib 5
fib(1) = 1.
fib(-1) = -1.
fib(2) = 0.
fib(0) = 0.
fib(3) = 0.
fib(1) = 1.
fib(4) = 1.
fib(1) = 1.
fib(-1) = -1.
fib(2) = 0.
fib(5) = 1.
fib(5) = 1

Apart from confirming the wrongness, the trace shows that the application is recalculating Fibonnaci on each recursion, such that there are 1278 invocations of fib(10) in the calculation of fib(30):

$ ./fib 30|grep -cF 'fib(10)'
1278

7.8 Alright. So first I'll fix fib/1, and then I'll remove the trace goal, and then--

Wait! You don't have to remove it. If it came up once that you wanted to trace that function, it might come up again. For example after the efficiency problem is fixed, you might want to use the trace to confirm that there are fewer recursions.

7.9 Can a trace goal be conditional, then?

Yep. Go ahead and fix the fib function and then make the trace goal depend on a runtime flag:

fib(N) = R :-
    trace [io(!IO), runtime(env("TRACE"))] (
        io.format("fib(%d) = %d.\n", [i(N), i(R)], !IO)
    ),
    ( if N < 2 then
        R = N
    else
        R = fib(N - 1) + fib(N - 2)
    ).

The manual will tell you how you can make it a compile-time flag instead, but this is convenient.

7.10 Can a trace goal throw exceptions? Can this be used for assertions?

You're free to use normal Mercury in a trace goal, which includes exceptions. Here's an example from Mercury's 'tree234' module, that uses expect/3 from the 'require' module (one line blurb: "This module provides features similar to <assert.h> in C."):

from_sorted_assoc_list(List, Tree) :-
    list.length(List, Len),
    ( if Len = 0 then
        % We can handle the Len = 0 case here just once, or we can handle it
        % lots of times in do_from_sorted_assoc_list. The former is more
        % efficient.
        Tree = empty
    else
        find_num_234_levels(Len, Level, AllThrees),
        do_from_sorted_assoc_list(Len, List, LeftOver, Level, AllThrees, Tree),
        trace [compiletime(flag("tree234_sanity_checks"))] (
            expect(unify(LeftOver, []), $pred, "leftovers")
        )
    ).

7.11 So expect/3, it takes a bool as its first argument, provided by that unify/2 function call, and…

It actually takes a zero-arity predicate as its first argument, and unify/2 is a semidet predicate; it doesn't return anything.

7.12 Er, so expect/3 is a macro?

No, it's a perfectly normal predicate. The unify(LeftOver, []) in the previous example is not a goal in which unify/2 is called; it's an expression with a higher-order type, and in this case what it evaluates to is a zero-arity currying of the unify/2 predicate.

Without currying this line would likely read expect(((pred) is semidet :- LeftOver = []), $pred, "leftovers").

This might seem strikingly unusual as it doesn't come up in other languages: the languages with currying don't have zero-arity functions, and the languages with zero-arity functions don't have currying. But now that you've seen it, it shouldn't be any harder to read than the more familiar ambiguity where foo(A) could, depending on the context, refer to any of

    % foo(N): succeeds if N is 42
:- pred foo(int::in) is semidet.
foo(42).  % arg must be 42

    % foo(N, M): succeeds if args are the same int
:- pred foo(int::in, int::in) is semidet.
foo(X, X).

    % foo(N, M, X): calculate X from N and M
:- pred foo(int::in, int::in, int::in) is det.
foo(N, M, X) :-
    X = N + M.

… where the bad names are the real problem for readability, which you could have to deal with even in a much simpler language.

7.13 What is that $pred ? Is it a zero-arity function call, used as a constant?

That would be an invalid name for a function. Symbols that begin with $ can only be provided by the compiler, where they're known as implementation-defined literals. The manual has a list of them, and this one expands to the name of the predicate it appears in.

7.14 Going back to the TRACE runtime flag, how to I provide it?

You just need to ensure that TRACE is set in the (Unix process) environment, like so.

$ ./fib 3
fib(3) = 2

$ TRACE= ./fib 3
fib(1) = 1.
fib(0) = 0.
fib(2) = 1.
fib(1) = 1.
fib(3) = 2.
fib(3) = 2

7.15 Onto efficiency, normally you'd memoize a function like this. How can you do that in Mercury?

You could do it yourself, with the likes of

:- pragma promise_pure fib/1.

:- func fib(int) = int.
fib(N) = R :-
    ( if semipure get_fib_cache(N, R0) then
        R = R0
    else
        normal_fib_function(N, R),
        impure set_fib_cache(N, R)
    ).

But since this is so common, Mercury offers flexible memoization as a language extension, and you only need to add a single additional line to this code to fix its performance:

:- pragma memo(fib/1).

7.16 How effective is that?

Oh it's only an improvement, for fib(60), of a factor of 1180:

$ time ./fib 60
fib(60) = 1548008755920

real	0m0.021s
user	0m0.009s
sys	0m0.012s

And since that trace goal is still there, we can confirm that fib(10) is calculated only once instead of 1278 times in the calculation of fib(30):

$ TRACE= ./fib 30|grep -cF 'fib(10)'
1

8 Hello, <thing I can say 'hello' to>!

Consider this module and an application using it:

SRC: salut.m

SRC: salut​_example.m

:- module salut.
:- interface.
:- import_module io, list.

:- typeclass greetable(T) where [
    func the(T) = string,
    func name(T) = string
].

:- type traffic(T)  % <= (greetable(T))
    --->    arriving(T)
    ;       leaving(T)
    ;       nothing(int).  % nothing for N seconds

    % announce(TrafficEvents, !IO)
    %
    % Make grand announcements according to a list of traffic events.
    %
:- pred announce(list(traffic(T))::in, io::di, io::uo) is det <= (greetable(T)).

    % hello(TrafficEvent, !IO)
    %
    % Respond appropriately to a greetable in motion.
    %
:- pred hello(traffic(T), io, io) <= (greetable(T)).
:- mode hello(in, di, uo) is det.

:- implementation.
:- import_module string.

announce(Events, !IO) :- foldl(announcement, Events, !IO).

hello(nothing(_), !IO).
hello(arriving(Who), !IO) :-
    io.format("Hello, %s.\n", [s(name(Who))], !IO).
hello(leaving(Who), !IO) :-
    io.format("See you again, %s.\n", [s(name(Who))], !IO).

:- pred announcement(traffic(T)::in, io::di, io::uo) is det <= (greetable(T)).
announcement(nothing(N), !IO) :-
    sleep(N, !IO).
announcement(arriving(W), !IO) :-
    io.format("Now arriving: %s %s!\n", [s(the(W)), s(name(W))], !IO).
announcement(leaving(W), !IO) :-
    io.format("%s %s has left the party.\n", [s(the(W)), s(name(W))], !IO).

:- pred sleep(int::in, io::di, io::uo) is det.
:- pragma foreign_decl("C", "#include <unistd.h>").
:- pragma foreign_proc("C",
    sleep(N::in, _IO0::di, _IO::uo),
    [will_not_call_mercury, promise_pure],
"
    sleep(N);
").
:- module salut_example.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module salut, list.

:- type world ---> world.
:- type animal
    --->    dog(string)
    ;       cat(string).

:- instance greetable(world) where [
    the(world) = "The",
    name(world) = "World"
].

:- instance greetable(animal) where [
    the(dog(_)) = "The dog",
    the(cat(_)) = "The Right Honorable Purr",

    name(dog(X)) = X,
    name(cat(X)) = X
].

main(!IO) :-
    hello(arriving(world), !IO),
    announce([
        arriving(dog("Spot")),
        nothing(1),
        arriving(cat("Ruffles")),
        nothing(1),
        leaving(cat("Ruffles"))
    ], !IO),
    hello(leaving(world), !IO).

8.1 Is this OOP? Is this a class definition?

If you think about it this as OOP, and 'greetable' as a class, then there are tons of potential implications that you could make that will turn out to be untrue. For example, there's no late binding and there's no inheritance here, at all. So it's better to think of this as just a way to add some restrictions to generic code.

What is similar is that you have these mirroring options:

:- type payment_method
    --->    cash
    ;       check(banking_number, routing_number)
    ;       credit(ccn, csc, expiration)
    ;       crypto(coin, wallet).

% vs.

:- typeclass payment_receivable(T) where [
    pred get_money(T::in, pay_result::out, io::di, io::uo) is det
].

On the first case you exhaust all the possible payment methods and then with some discipline (determinstic disjunctions > conditional pattern-matching) Mercury will ensure that all of your payment code will handle all the methods, so that when you later add a Paypal-specific payment method, Mercury will help you find and update every part of your code that should be updated.

It's also very easy for someone, even a non-programmer, to look at this and say "hey, we don't accept all credit cards. You need to add a brand to the credit type constructor".

In the second case, you say "for this type, all that I care about is that someone's defined this predicate for it", and responsibility for making the payment code correct is distributed to instances of the typeclass, which might be in different modules.

8.2 What is that :- typeclass declaration doing then?

It's saying, "A type is greetable if these two functions exist for it". So if you want to write a bunch of code that relies on being able to perform those operations, this typeclass guarantees that they are available.

8.3 What's the point of that though? Why not just write the generic code and use whatever operations that come up?

Consider a module where one predicate takes a list(T) and stores its contents away, and then other predicates can be called that actually perform operations on the stored contents. Without typeclasses, there's no good way to stop the first predicate from accepting data that will later be found to be unsuitable. (Putting aside for a moment how this would actually compile.) The first predicate says it accepts any list(T) at all. A typeclass is a good way, both for compiler and for a reader of the code, to see that the predicate is not really so permissive of its inputs.

8.4 What's that <= (greetable(T)) comment about where traffic/1 is defined? Is that actually code? Does it have an effect?

It's purely a comment. Mercury actually won't permit a typeclass constraint here, so even though the intent is that 100% of code that involves traffic(T) will also constrain T to the greetable(T) typeclass, there's no way to enforce this. As traffic/1 is in the interface of this module, someone using the module could create a arriving(string) or whatever they want without caring about the typeclass.

8.5 How do you read the same <= (greetable(T)) in the following predicates?

Reading the first: "there's a predicate 'announce' that accepts a list of traffic(T), and it does IO, and it's deterministic. Oh and that T has to be greetable."

In other languages with typeclasses, the "oh and" part comes before the parameters rather than after them, but it's otherwise very similar.

8.6 What are the parentheses around greetable(T) for?

You could actually leave them off in this case, but you would need them if you had multiple typeclass constraints.

8.7 For multiple type variables in the same predicate type?

Or just for when multiple constraints apply to the same type variable. You could split greetable(T) up unto the_able(T) and named(T), and replace every constraint with <= (the_able(T), named(T)), and the effect would be the same.

9 Ramping down

9.1 That was a whole lot to keep in mind. How do you write anything?

Well, the aim of this crash course was to introduce most aspects of Mercury as quickly as possible. It's not the case though that all of those aspects are always involved when you're writing Mercury.

Suppose I described Earth as a planet with flowing molten lava, frozen glaciers, barren desserts, and deadly tornadoes. That's a whole lot of environmental extremes to have to deal with! How does anyone live on this planet?

People mostly live away from the extremes. Likewise a lot of the Mercury you'll write will be relatively mundane and easy to think about. (And I wouldn't describe any particular feature of Mercury as 'flowing molten lava'.)

Or suppose I described a car as a vehicle that can move at 5 miles per hour, and at 60 miles per hour, and forwards, and also backwards. It would certainly be crazy to think that cars can do all these things simultaneously, or that drivers of cars need to be in a mindset to deal with all those behaviors at the same time – that while you're driving at high speed down a highway you should also be turned around in your seat and staring out your back window to make sure you don't reverse over a pedestrian.

Cars have physical gears that shift to permit different modes of operation, and drivers have mental gears that shift correspondingly, and when you're writing Mercury you can shift between describing logical relations (when writing clauses and facts), or modelling your data with types (when writing type declarations), or crafting new Mercury insts to permit some higher-order programming (when writing inst and mode declarations and the pred/func declarations that use them), and so on.

Far from having to keep all this in mind when you write a single line of Mercury, the language is such that visually distinct parts of Mercury programs map to different subsets of the language.

9.2 Where should I go from here?

Write something in Mercury! I recommend that you have Mercury docs open in a browser as you do so, especially the library and language references.

You could also send some feedback about this course to jfondren@minimaltype.com.

There will eventually be some more documents about Mercury at this website. Your feedback about this will go far to influencing the order that these other documents are written.

Cheers.

Author: J Fondren

Created: 2019-08-04 Sun 23:46

Validate