The Mercury programming language

> apparently

Can confirm... we use a mix of Mercury and Rust :)

Yes, Prince XML is written in Mercury. I had mentioned this on HN a few times earlier:

https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

Apropos of the hn.algolia.com search used in the above link, it seems pretty good and accurate. I could put my HN user name into the text box along with words like prince and xml, and it worked right. Only returned comments by me. I did not have to put my name in a separate user name field. I'm guessing this a full-text search feature.

I think the difference is that in Prolog you have imperative state management while Mercury only has pure functions, and manages state through linear types.

EDIT: the "about" page may explain this a tad better https://mercurylang.org/about.html

> Wikipedia says it's essentially a pure subset of Prolog, but Prolog is not classified as a functional language

That statement used “pure” in the sense of “functionally pure” (I'm not sure about “subset”; it certainly lacks some prolog features that are impure, but seems to have features that Prolog lacks; it seems more like it contains a pure subset of Prolog than that it is one.)

> I assume there must be some significant language features that e.g. functions.

I think you missed something I. that sentence, but, yes, Mercury has first-class and higher-order functions.

> Can someone explain why it is called a "functional" language?

Not sure why the title only includes "functional", the site itself says "Mercury is a logic/functional programming language".

You should look at Icon [0][1], which is a lot like... Pascal, or any Algol family language, but which has pervasive depth-first search and backtracking built-in. Icon is and feels very procedural.

Or jq, which also has pervasive depth-first search and backtracking built-in. jq is and feels very functional.

  [0] https://www2.cs.arizona.edu/icon/
  [1] https://en.wikipedia.org/wiki/Icon_%28programming_language%29

Here's a full example I wrote in Prolog for doing small scale sysadmin: https://github.com/larsyencken/marelle

It mixes logic programming as imperative programming, with more logicky features like facts and rules.

I think it's more related to Prolog than functions. In prolog you can use a predicate in many ways. For example append(L1, L2, L3) declared that the concatenation of the list L1 and L2 result in L3, but you can use it in a "reverse" way too (thx to Prolog awesomeness) like append(L1, L2, [1,2,3]) and Prolog will enumerate all possibilities for L1 and L2. This can be slow though, and I think 'mode' is a way to declare all this different way to use prediate (in, int, out), (out, out, in), etc. and maybe compile things efficiently. See https://www.mercurylang.org/information/doc-latest/mercury_r...

Mode declarations aren't really a feature so much as they are additional information provided by the programmer to the compiler. In Prolog if you have a predicate

  foo(X,Z) :- 
    bar(X,Y), 
    baz(Y,Z). 

Traditionally if you call foo(1,Z) it will try to find an answer for bar(1,Y) first then feed that Y value into baz, if you call foo(X,3) it will still try to find values for bar(X,Y) first. Sometimes that's okay because the engine will be like well yeah there's something that'll work so we'll say bar is true and move on to baz but some times it tell you to go suck eggs.

You could write two different versions of foo

  %foo(in,out)
  foo(X,Z) :- 
    ground(X),
    bar(X,Y), 
    baz(Y,Z).
  %foo(out,in)
  foo(X,Z) :- 
    ground(Z),
    baz(Y,Z),
    bar(X,Y).

but having to do that sucks. First it's forcing you to think about Prolog's implementation rather than the logical relationship between X and Z; second it's repetitive and forces you to keep both versions in sync with each other which is gonna get rough for more complex predicates.

One of the things Mercury uses that mode info for is to re-arrange the body of foo(X,Y). So if you tell it that you will use both foo(in,out) and foo(out,in) it will compile two different versions of foo and dispatch appropriately.

It's Saturday and I'm on my third coffe (in a very tiny cup) so I hope you will excuse me a mini-essay to asnwer your question :)

Logic programming languages like Mercury adopt the syntax and semantics of the predicate calculus, a.k.a. First Order Logic. FOL is the language of predicates, where predicates are _relations_ between propositional terms. "Propositional" here means that a term is a, well, propositional logic object or variable. For example the objects "stassa" and "mercury" are propositions while the formula "likes(stassa, mercury)" is a relation between the two (and "likes" itself is the predicate of the relation).

Now, a "relation" is a generalisation of a function. Recall that functions are mathematical objects that map input terms to output terms, for example the function ƒ: X → Y maps elements of the set X to elements of the set Y.

Unlike functions, relations have no concept of "inputs" and "outputs". For example, take "likes(stassa, mercury)". Suppose "stassa" is an element in the set of persons (sorry) and "mercury" is an element of the set of programming languages. The following FOL atomic formulae are both true:

  ∃y: likes(stassa, y)
  ∃x: likes(x, mercury)

More precisely, they are true given an interpretation (an assingment of truth values to atomic formulae) that assigns the value "true" to the atomic formula "likes(stassa,mercury)". "Atomic" just means these are the simplest kinds of formulae in FOL syntax. The thing to keep from this is that a truth value can be assigned to atomic formulae in FOL regardless of which argument is a variable or a constant term.

By contrast, to implement likes/2 as a function [1] we would have to split it in two: one function taking as input a "person" and returning a "language" and the other taking as input a "language" and returning a "person":

  ƒ₁: P → L, e.g. ƒ₁(stassa) = mercury
  ƒ₂: L → P, e.g. ƒ₂(mercury) = stassa

How this translates in logic programming, and particularly Prolog, practice, is that Prolog programs can be called with different combinations of instantiated and non-instantiated arguments.

Here's an example (the typical example is the "append" predicate, mentioned in the mercury site above, but this should be simpler). The "%" denotes a comment in Prolog an the example works in Swi-Prolog:

  ?- length([a,b,c,d], N). % (1)
  N = 4.
  
  ?- length(List, 3). % (2)
  List = [_11524, _11530, _11536]

(Note that the underscored terms are variables created by the Swi-Prolog internals).

length/2 is a Prolog predicate (a logic program) that determines the length of a Prolog list (a linked list represented as [H|T] where H is the head element and T is the rest of the list). The two queries above show that length/2 can be called with either the first or second argument instantiated to a fully-ground term (a term that has no variables) and length/2 will work in a way that makes sense.

The first call, in (1), is made with a ground list "bound" (instantiated) to the first argument of length/2 and with a free variable (N) as its second argument (variables start with uppercase letters or the underscore, in Prolog). When length/2 exits, it binds the constant "4" (an integer) to the second argument and Prolog reports that the variable N is now bound to 4. Thus length/2 has determined the length of the list [a,b,c,d]. The second call leaves the first argument as a variable and binds the integer "3" to the second argument. Now length/2 _generates_ a list of the given length. The elements of the generated list are all free variables, a detail of the implementation of length/2.

It is also possible to call length/2 with _both_ arguments as free variables:

  ?- length(List, N).
  List = [],
  N = 0 ;
  List = [_13650],
  N = 1 ;
  List = [_13650, _14782],
  N = 2 ;
  List = [_13650, _14782, _15914],
  N = 3 .

In this case, length/2 generates lists of increasing length, again a detail of its implementation ("[]" is the empty list, of length "0" and ";" asks for more results).

Now, try to think what would happen if we made the following query; the findall/3 predicate is used to generate all results of a predicate call:

  ?- findall(List-N, length(List,N), LNs). % (3)

Well, here's what happens (the output is from Swi-Prolog):

  ?- findall(List-N, length(List,N), LNs).
  ERROR: Stack limit (1.0Gb) exceeded

What happens is that there is no limit to the number of lists of arbitrary length that can be generated by length/2, so findall/3 continues to generate them until the Prolog interpreter runs out of its allocated resources. Even given infinite resources the query in (3) would never terminate- it would continue to generate lists of increasing length for ever.

A straightforward way to avoid this situation is to avoid calling length/2 with both arguments as free variables, at least when we want to generate all solutions. So we could mandate that if one argument is a variable, the other one must be bound to an at least partially ground term.

In logic programming convention, we represent these acceptable instantiations with various notations, the most commoon of which is to use "+" to mean that an argument must be instantiated on call, "-" to mean that an argument must be left as a free variable and "?" to mean that either is acceptable.

For length/2, we could declare:

  length(+, -).
  length(-, +).

These are the "modes" in which the programmer of length/2 communicates to users how the program can be called. We can add some additional information:

  length(+, -) is det.
  length(-, +) is det.

"det" meaning that the predicate is deterministic _in that mode_, where "deterministic" means that a call of the predicate at the declared mode succeeds once, yielding one result, or fails if a result cannot be produced given the arguments. We could also declare the (?,?) mode as _nondeterministic_ meaning that it generates multiple results (or fails, once):

  length(?, ?) is nondet.

This last mode declaration still allows the dangerous call in (3) above, but at least now the programmer knows to expect this.

Now, these call and determinism modes are a _convention only_ in Prolog and most other logic programming languages, meaning that they are solely used for documentation purposes and are not enforced by interpreters or compilers.

Mercury instead makes mode declarations a part of the syntax of the language. The Mercury website claims that this helps to catch a lot of bugs. While I have not actually used Mercury, I certainly agree that having no clear inputs and outputs, or determinism constraints, is a major source of bugs in Prolog code and enforcing mode declarations is sure to help avoid some major sources of pain when programming in Prolog. How good is Mercury at doing that, I can't tell. As the website says, detecting determinism is undecidable but there seem to be some heuristics that work "often enough".

________________

[1] I'm fudging the definition of "function" between mathematical functions, that are typically not discussed in terms of "inputs" and "outputs", or "returns" and programming-language functions, which are. Apologies, I hope the meaning is clear from the context.

To try and put it another way to the other answers, Python functions take inputs in parentheses, do a calculation, and return results to the left of the name. A definite arrow-of-time, inputs first, then calculation, then results. e.g. in this line of code you pass in a width and height, and out comes an area, no other way round:

    area = rectangle_area(width, height)

Prolog doesn't have that arrow-of-time, instead (subtle difference) you declare that Area, Width and Height are related by equality and multiplication in some abstract sense:

    rectangle_length_width_area(Length, Width, Area)

It's a pattern, not a computation; as well as the obvious giving Legnth, Width and calculating Area, you can fill in Area and Width and get Length. You can fill just Length and get Widths and Areas (plurals) that could go with a fixed Length. You give whichever values you have and Prolog will search for the missing ones trying to match the pattern of how they relate to each other. If you give values for all of them, it will check them out and see if they do relate to each other in this rectangular way and tell you yes or no. If there might be more than one value that can fill in the gap(s) you left, it can generate many answers.

This is one of the ways Prolog can do impressive things - the code you write can express more and do so at a more abstract level than the same amount of code in Python. Downside is is can bloat past what any computer could run in a reasonable time. Function modes remove some of the Prolog magic and add constraints e.g. Length and Width are inputs, Area is an output. Slap on an arrow-of-time, lose the general purpose search and solve, bring Prolog down from magic to mortal realms, gain something that runs on a normal computer.

Maybe not, but Mercury predates LLVM by almost a decade, so I can see why they targeted GCC rather than LLVM.

It seems that the crash course is more suitable for people who know haskell. Perhaps you'd have a better time with the book instead:

https://www.mercurylang.org/documentation/papers/book.pdf

Things gets better if you try a couple of hours rather than minutes. If you've never been exposed to the logic programming paradigm this is completely understandable. Isn't it?