3 ms·

Mercury's roots are indeed the explanation and justification for many of these points: Mercury syntax is deliberately designed to be very close to Prolog syntax

by triska 8y ago

Mercury's roots are indeed the explanation and justification for many of these points: Mercury syntax is deliberately designed to be very close to Prolog syntax. In fact, it is so close to Prolog that if you remove the declarations, then many Mercury programs are also valid Prolog code. Regarding ":-", there is a difference between writing: :- implementation. and implementation. The latter is a fact and can be read as "implementation holds". The former is a directive that tells the compiler something. As in Prolog, :- is an ASCII transliteration of ←, i.e., an arrow from right to left. A clause of the form: Head :- Body. is read as: "If Body is true, then Head is true.". Such clauses are sufficient to describe every known computation. In Mercury, !Var is a state variable. It is a shorthand for naming intermediate values in a sequence. Without using state variables, you can write the code equivalently as: main(IO0, IO) :- write_string("Hello, world!\n", IO0, IO). State variables are more explicit than using DCG notation, and at the same time still easier to write than pairs of variables that are threaded through. The "." at the end of clauses is likewise inspired by Prolog syntax. Please note that Prolog programs are, syntactically, also Prolog terms, and "." is used at the end of each clause.

YeGoblynQueenne 8y ago
>> Please note that Prolog programs are, syntactically, also Prolog terms, and "." is used at the end of each clause. Heh. You won't believe how much trouble I got into for using Prolog terminology like "term" and "predicate" when speaking to logic programming people, even though they all know Prolog perfectly well. You can probably imagine why- in FOL, and so in logic programming, a "term" is a variable, a constant or a function, and a "predicate" is a concept. In Prolog, a "term" is - well, everything! And "predicate" is either a clause or what LP people call an atom. Oh, and, btw, an "atom" in Prolog is either a predicate symbol, a non-ary function, or a constant, whereas in LP it's a predicate symbol followed by a vector of terms in parentheses. How all this terminological confusion came about, I don't know, but I'm sure suffering because of it, and because I first learned Prolog, before really studying logic programming, as such.
- triska 8y ago
  The terminology of first-order logic is indeed quite different from that of Prolog. A key reason for this is that in FOL, we have to distinguish between the syntactic entities and their interpretations. So, in FOL, we have predicate symbols that are assigned to relations by an interpretation, we have constant symbols that are assigned to domain elements by an interpretation, we have function symbols that are assigned functions by an interpretation. In addition, many theorems also require that we distinguish between countable and uncountable signatures. In contrast, Prolog is confined to a single kind of interpretations, namely to Herbrand structures, where each term "stands for itself", and where we only need symbols that already occur in the clauses we are considering: https://en.wikipedia.org/wiki/Herbrand_structure https://en.wikipedia.org/wiki/Herbrand_structure So, in Herbrand structures, the interpretation of a term T is simply the symbolic representation of T, i.e., "T". Importantly, one can show that a set of clauses has a model if and only if it has a Herbrand model. This also has important semantic consequences: For example, due to the compactness theorem (and its consequence, the upward Löwenheim–Skolem theorem), one can show that important concepts such as the transitive closure of a relation, the class of connected graphs, and the natural numbers with only the intended model (up to isomorphism) cannot be expressed in first-order logic! https://en.wikipedia.org/wiki/Compactness_theorem https://en.wikipedia.org/wiki/Compactness_theorem Yet, we can readily express these things in Prolog, and in fact almost every Prolog program also does that or needs them! Why? Because Prolog (implicitly) only considers least Herbrand models, so we do not need this layered syntactic view, and also do not run into these semantic issues when programming in Prolog. An argument can be made that in this case, what at first seems like a restriction in fact extends the usefulness of the language. A similar argument can be made also for several constructs within the language.
  - nmadden 8y ago
    While Prolog’s operational semantics are given in terms of least Herband models (at least, before you consider negation), you can also view a Prolog program as a subset of FOL and give a traditional model-theoretic account of the semantics. This may be less useful practically, for the reasons you give, but sometimes it’s nice to consider that a symbol “fred” might actually refer to a person called Fred rather than just be symbols all the way down... (It always surprises me when Prolog texts refer to the least Herband model as the “intended model” - it’s definitely not what I intend when I write Prolog!) So while we can say that an “ancestor” relation in Prolog correctly defines transitive closure within the least Herbrand semantics, at some point we actually have to relate that “semantics” to the real world if we want to know what our programs mean. Edit: putting this all another way, my understanding of (pure, positive) Prolog’s operational semantics is that the least Herbrand model contains exactly those sentences that are true in all models of the program, whether those models are Herbrand or otherwise. So it’s not quite true to say that Prolog only considers the least Herbrand model, but that it may as well only do so because the (operational) result will be the same. It’s been a while since I’ve looked at this any great depth though.

by triska 8y ago

YeGoblynQueenne 8y ago

>> Please note that Prolog programs are, syntactically, also Prolog terms, and "." is used at the end of each clause. Heh. You won't believe how much trouble I got into for using Prolog terminology like "term" and "predicate" when speaking to logic programming people, even though they all know Prolog perfectly well. You can probably imagine why- in FOL, and so in logic programming, a "term" is a variable, a constant or a function, and a "predicate" is a concept. In Prolog, a "term" is - well, everything! And "predicate" is either a clause or what LP people call an atom. Oh, and, btw, an "atom" in Prolog is either a predicate symbol, a non-ary function, or a constant, whereas in LP it's a predicate symbol followed by a vector of terms in parentheses. How all this terminological confusion came about, I don't know, but I'm sure suffering because of it, and because I first learned Prolog, before really studying logic programming, as such.

triska 8y ago
The terminology of first-order logic is indeed quite different from that of Prolog. A key reason for this is that in FOL, we have to distinguish between the syntactic entities and their interpretations. So, in FOL, we have predicate symbols that are assigned to relations by an interpretation, we have constant symbols that are assigned to domain elements by an interpretation, we have function symbols that are assigned functions by an interpretation. In addition, many theorems also require that we distinguish between countable and uncountable signatures. In contrast, Prolog is confined to a single kind of interpretations, namely to Herbrand structures, where each term "stands for itself", and where we only need symbols that already occur in the clauses we are considering: https://en.wikipedia.org/wiki/Herbrand_structure https://en.wikipedia.org/wiki/Herbrand_structure So, in Herbrand structures, the interpretation of a term T is simply the symbolic representation of T, i.e., "T". Importantly, one can show that a set of clauses has a model if and only if it has a Herbrand model. This also has important semantic consequences: For example, due to the compactness theorem (and its consequence, the upward Löwenheim–Skolem theorem), one can show that important concepts such as the transitive closure of a relation, the class of connected graphs, and the natural numbers with only the intended model (up to isomorphism) cannot be expressed in first-order logic! https://en.wikipedia.org/wiki/Compactness_theorem https://en.wikipedia.org/wiki/Compactness_theorem Yet, we can readily express these things in Prolog, and in fact almost every Prolog program also does that or needs them! Why? Because Prolog (implicitly) only considers least Herbrand models, so we do not need this layered syntactic view, and also do not run into these semantic issues when programming in Prolog. An argument can be made that in this case, what at first seems like a restriction in fact extends the usefulness of the language. A similar argument can be made also for several constructs within the language.
- nmadden 8y ago
  While Prolog’s operational semantics are given in terms of least Herband models (at least, before you consider negation), you can also view a Prolog program as a subset of FOL and give a traditional model-theoretic account of the semantics. This may be less useful practically, for the reasons you give, but sometimes it’s nice to consider that a symbol “fred” might actually refer to a person called Fred rather than just be symbols all the way down... (It always surprises me when Prolog texts refer to the least Herband model as the “intended model” - it’s definitely not what I intend when I write Prolog!) So while we can say that an “ancestor” relation in Prolog correctly defines transitive closure within the least Herbrand semantics, at some point we actually have to relate that “semantics” to the real world if we want to know what our programs mean. Edit: putting this all another way, my understanding of (pure, positive) Prolog’s operational semantics is that the least Herbrand model contains exactly those sentences that are true in all models of the program, whether those models are Herbrand or otherwise. So it’s not quite true to say that Prolog only considers the least Herbrand model, but that it may as well only do so because the (operational) result will be the same. It’s been a while since I’ve looked at this any great depth though.