Mercury Crash Course
Table of Contents
- 1. Is Socrates mortal?
- 1.1. Can I compile and run this code?
- 1.2. Taking that piece by piece, what is
mortal(X)
? - 1.3. What's a predicate?
- 1.4. Failure? Do you mean an exception?
- 1.5. What does that /1 mean in mortal/1?
- 1.6. A module?
- 1.7. OK, so Mercury has polymorphism. Is it multiple dispatch? Single dispatch?
- 1.8. What does
:-
mean? - 1.9. What about
man(X)
? - 1.10. And the two
X
es? - 1.11. How do we know that
X
is a variable butsocrates
is a value? - 1.12. How about the period at the end?
- 1.13. How about
man(socrates).
? - 1.14. So, taken altogether, what does this code mean?
- 1.15. How might you use that code?
- 1.16. How else might you use this code?
- 2. Hello, world!
- 2.1. Is this really the smallest 'hello world' in Mercury?
- 2.2. Well, let's go through it. Does
:- module hello.
name the module this code is defined in? - 2.3. Is `:- module hello.` a rule?
- 2.4. Does
:- interface.
start the interface section of the module? - 2.5. Wait, is there any point to that?
- 2.6. Moving on,
:- import_module io.
imports the 'io' module, right? - 2.7. Wouldn't simple output normally be in an always-included module, like Pervasives or Prelude?
- 2.8. OK,
:- pred main(io::di, io::uo) is det.
… can you break that down? - 2.9. Is there a simpler way to explain what this line is doing?
- 2.10. After that,
:- implementation
starts the implementation section of the module. - 2.11. The rest is familiar, but what's this
!IO
? - 2.12. Wait, this is new. What's that
,
that you have in these state-variable examples? - 2.13. isn't that awful?
- 2.14. but why permit that at all? Why not require that evaluation follow lexical order?
- 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?
- 2.16. OK, how can this 'hello world' be run?
- 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?
- 3. Weekdays and workdays
- 3.1. What file would this appear in?
- 3.2. How would you compile it and use it?
- 3.3. Why is this importing the 'string' and 'list' modules?
- 3.4. So the list module is introducing new syntax? Am I going to run into lots of project-specific syntax with Mercury?
- 3.5. What functions are those?
- 3.6. So how flexible is Mercury's syntax? Obviously it doesn't have read macros.
- 3.7. Moving on, is
days
an enum type? - 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?
- 3.9.
:- func
? Is that like a predicate declaration? - 3.10. So this declares a
datatype/1
function that accepts adays
and returns astring
. - 3.11. What is
daytype(D) = R :-
doing? - 3.12. And then… what's all this punctuation about? Are these parentheses used like curly braces in C?
- 3.13. OK, but what is this code doing? How would this look if written in another programming language?
- 3.14. OK, so you have a single variable that you test and it's magically interpreted as a case structure?
- 3.15. How else might
daytype/1
be defined? - 3.16. Which of those should I use, though?
- 3.17. Why is if/then/else what's recommended?
(A -> B; C)
looks nice too. - 3.18. Moving on, it looks like you get the command line arguments into
Args
. - 3.19. And then, are these parentheses required?
- 3.20. That's four different goals in the
might_fail
, is that OK? - 3.21. How do I know which goal failed, though? Which of these can fail?
- 3.22. OK, but what are these goals doing? What's the test?
- 3.23. How does that
read_from_string
know we're looking for adays
value? - 3.24. OK. What's this
s(Var)
stuff about? - 3.25. What might that pattern matching look like?
- 4. Cast of characters
- 4.1. How would you summarize all of the declarations in this code?
- 4.2. What's that 'name', 'age' stuff in the declaration of
person/0
? - 4.3. Is
majority
a constant? - 4.4. What's the type of
People
? - 4.5. Is that
foldl/4
passing each element ofPeople
toprint/3
, along with the IO arguments? - 4.6. Why is it
people.print
instead of justprint
? - 4.7. Wait a moment, that error's saying that a 'print' call could refer to
io.print/3
orio.print/4
. Doesn't the number of arguments make it obvious that it can only be one of these? - 4.8. Could you use a 'lambda' or a rule literal in place of that
people.print
? - 4.9. You can't use
!IO
in the parameters of a 'higher-order predicate term'? - 4.10. So, this list is statically known, and short. Does Mercury unroll the foldl loop?
- 4.11. How could you process the list without
list.foldl
?
- 5. The secret Zebra-keeper
- 5.1. Could I solve it the same way I would in Prolog?
- 5.2. Could I solve it the same way I would in a non-logical language?
- 5.3. And what does Mercury offer, that's so helpful?
- 5.4. What does it mean, that this is a 'multi' predicate?
- 5.5. So, big picture, how do I solve this puzzle?
- 5.6. Alright, so, a module that'll do I/O, with puzzle data…
- 5.7. I then need a way to generate valid houses …
- 5.8. What are those conditionals doing?
- 5.9. That's really tedious though, with the "else true", and two conditionals per puzzle rule. Can it be done better?
- 5.10. I looked at that Mercury goals page and– how the heck is this the same??
- 5.11. OK, now I need a way to generate valid rows of houses.
- 5.12. How would I print out all the possible solutions for row/3 ?
- 5.13. What's the type of
Solutions
? - 5.14. Do I really need that 'lambda' there? Why not define a new
row/1
predicate? - 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?
- 5.16. And altogether…
- 6. Pure randomness
- 6.1. Is this really the smallest dice-roller in Mercury?
- 6.2. Why do it this way, then?
- 6.3. OK. What's that
some
about? - 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"? - 6.5. And
:- mutable(seed, int, 0, ground, [untrailed]).
? - 6.6. Uh, instantiation?
- 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?
- 6.8. Moving on, what's the
initialize
doing? - 6.9. What does it mean to promise that
seed/0
is pure? - 6.10. Isn't
seed/0
actually semipure then? Since its meaning will change ifinit_seed/0
is called again. - 6.11. Looking at the clause for
init_seed/0
, is it impossible to have a semipure or impure expression? - 6.12. So the rest of this is Mercury's C FFI. With those strings… how well is this checked?
- 6.13. Eh, this sort of FFI is easier? Really?
- 7. Troubleshooting and optimizing a function
- 7.1. Is there anything new in this code?
- 7.2. Are the 'two problems' that it's wrong and slow?
- 7.3. Trace it, by rewriting it to use I/O and using 'print debugging'?
- 7.4. Trace it, by using a function-tracing feature of the compiler, that shows each function invocation with parameter and return values?
- 7.5. By the pattern so far, is that
trace [Variables] Goal
? - 7.6. Is that
io/2
creating the I/O variables out of thin air, for use in the goal? - 7.7. What's this trace output look like?
- 7.8. Alright. So first I'll fix
fib/1
, and then I'll remove the trace goal, and then-- - 7.9. Can a trace goal be conditional, then?
- 7.10. Can a trace goal throw exceptions? Can this be used for assertions?
- 7.11. So
expect/3
, it takes abool
as its first argument, provided by thatunify/2
function call, and… - 7.12. Er, so
expect/3
is a macro? - 7.13. What is that
$pred
? Is it a zero-arity function call, used as a constant? - 7.14. Going back to the TRACE runtime flag, how to I provide it?
- 7.15. Onto efficiency, normally you'd memoize a function like this. How can you do that in Mercury?
- 7.16. How effective is that?
- 8. Hello, <thing I can say 'hello' to>!
- 8.1. Is this OOP? Is this a class definition?
- 8.2. What is that
:- typeclass
declaration doing then? - 8.3. What's the point of that though? Why not just write the generic code and use whatever operations that come up?
- 8.4. What's that
<= (greetable(T))
comment about wheretraffic/1
is defined? Is that actually code? Does it have an effect? - 8.5. How do you read the same
<= (greetable(T))
in the following predicates? - 8.6. What are the parentheses around
greetable(T)
for? - 8.7. For multiple type variables in the same predicate type?
- 9. Ramping down
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?
- As a rule, something is mortal if it is a man.
- 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:
- if no
:- module
is provided, use the filename. - if no
:- interface.
is provided, then assume an interface with a singlemain/2
predicate, suitable for an application entry point. - 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
- programming stuff: declarations.
- logical stuff: clauses that define rules and facts.
- 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?
:- 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.
main(..., ...)
, the predicate rule is named main/2io::..., io::...
, the arguments are both of type 'io'.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.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.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
- determine (with unification) if two values of this type are the same value
- produce (with
string.string/1
) a string representation of values of the type with "sunday", etc. - parse a value of this type out of a string, as shown with this
code's use of
io.read_from_string/6
. - order
days/0
values (withbuiltin.compare/3
and such, but not automatically with operators like<
and such) by their order in the type's definition:monday
is less thantuesday
,sunday
is less thansaturday
.
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
- they have return values and so can appear within other goals as expressions (so you can write
do_something(daytype(sunday))
) - functions have an assumed mode: all arguments are
in
, the return value isout
, 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
- is
Args
a list with just one element, which I'll callDayString
? - always true:
Lowered
is the lowercase version ofDayString
- always true:
Term
isLowered
with a trailing dot. - 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) - 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
andfemale/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 aperson
and returns a string. - and a
print/3
predicate rule that takes aperson
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,
- it's a function that takes no arguments.
- 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.
- the set of all possible arguments has only one member: no arguments.
- 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?
- create types for the data the puzzle requires (the pets, etc.)
- create 'multi' predicates, defined by predicate facts clauses, for all of this data
- write a 'nondet' predicate that binds variables with puzzle data and then asserts the puzzle's relationships
- 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
, thenH = 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?
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.- 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
andout
modes for the new type. - Predicates and atypical functions are not
ground
, so higher order code can easily require some custom insts. - 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:
- the meaning of
foo(A, B)
depends only on the meaning and values offoo/2
,A
, andB
. - the meaning of
semipure foo(A, B)
depends on that but also on the invocations of impure predicates. - 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.