Sentence: A sentence is something that can be true or false on a given turn of a game. It is made up of a name (which is a constant) and (optionally) a body consisting of terms. In GGP-Base, a sentence with no body is called a proposition, while a sentence with a body is called a relation. (Note that this is different from the sense of "proposition" used in propositional network, which is equivalent to a sentence in this terminology.)
Term: A term is a constant, variable, or function. It's what fills one "slot" in a sentence body.
Constant: A constant is a "word" of the language for a particular game, or one of the GDL keywords. If it's a single word without parentheses (and not a variable) it's a constant.
Variable: A "word" in a sentence starting with
?. It can represent a constant or a function.Function: A complex term that contains other terms. It has a name (which is a constant) and a body consisting of other terms, much like a sentence. Unlike a sentence, it does not have a truth value.
Arity: The number of terms in a sentence body or function body. This should be constant across every use of a sentence name or function name.
Rule: A rule in a GDL description starts with the <= operator, follows it with a sentence (whatever is implied by the rule), and then has a body consisting of literals.
Literal: A literal is a condition for a rule. This can be a sentence; a negated sentence; a declaration that two terms are distinct; or a disjunction of other literals. These last three get their own types in GGP-Base: GdlNot, GdlDistinct, and GdlOr, respectively.
And a few examples:
terminal can be either a constant/term or a sentence/proposition, depending on the context. The constant terminal is the name of the sentence terminal.(init (cell 1 1 b)) is a sentence/relation. Its name is init. Its arity is one, because the only term in its body is the function (cell 1 1 b). This function in turn has arity three, and its body consists of the constants 1, 1 again, and b.(true (cell 1 1 b)) is also a sentence/relation. Its name is true. Note that (cell 1 1 b) is still just a function, even though it looks like we're talking about its truth value.(line ?player) could be either a function/term or a sentence/relation, depending on the context and the game description it appears in. If it appears on its own in the head or tail of a rule, it's a sentence. If it is part of a larger sentence, such as (next (line ?player)), then it's a function instead. Whichever it is, it should be consistently one or the other throughout the game description.(distinct ?x king) is a literal/distinct, and its two terms are a variable and a constant, respectively. Note that it doesn't get to count as a sentence; instead, it's considered just a language construct.(Edited on 8/25/13: Added an example of an ambiguous sentence/function.)
Thanks for this! Slowly coming to understand the language.
ReplyDeleteFWIW, I think that "function" is misleading. Logical or mathematical functions come to mind for me -- and both of those have the property that when you apply arguments you get a value back.
Is it fair to say that in GDL, functions do not have a value? Perhaps instead they are just, as you stated, "complex terms".
Right -- functions don't evaluate to a true or false value, at least not on their own.
DeleteThe terminology does come from first-order logic, by way of Prolog. Prolog calls these "compound terms" consisting of "functors" and associated "arguments" (at least according to the Wikipedia page).
The first-order logic sense of "function" still applies, simply going from one logical entity to another. For example, if we have a function (cell h 1), we could think of cell as a function that takes in a row entity and a column entity and returns the cell entity at their intersection.
This would be more intuitive as an interpretation if it weren't for the semantics of GDL's logic, which say that two things are the same if and only if they have the same name, so every function ends up with its own unique domain of "stuff" that never overlaps with anything else. This is different from the usual semantics of first-order logic, in which, say, plus(3, 5) and 8 can refer to the same entity.
Thanks for the rapid response! I should set email notifications, since I just saw it x_X.
DeleteOne thing about functions still confuses me.
1) I think that a Rule is made up of a head and a tail, where a head is a sentence that is true if each "thing" in the tail is true.
2) I've seen Functions in the tails of rules
3) Functions (I learned from this post) do not have a truth value.
So what does it mean for a function to be in the tail of a rule?
As an example (from http://games.ggp.org/base/games/2pffa/2pffa.kif)
(<= (onboard ?x ?y)
(index ?x)
(index ?y)
(distinct ?x 1)
(distinct ?x 7)
(distinct ?y 1)
(distinct ?y 7))
In this case, (index ?x) and (index ?y) are sentences, not functions.
DeleteThe distinction can be particularly confusing for a couple of reasons. First, you can't tell if the string "(index ?x)" is a sentence or a function just from looking at it; the context in which it appears determines that. Second, the term "true" is used as a name for some sentences but not others, even though both kinds of sentences have truth values. The "true" name just denotes that its truth values are carried over from the previous turn (or "init" sentences, on the first turn).
Looking back at the post, I should add an example of a non-"true" type of sentence to make this clear.
Am I right in thinking that GdlOr should no longer be needed - i.e. that it's no longer valid to include a disjunction in the body of a rule? If not, can you show me an example? If so, do you know if there are any historical examples checked into the base repository (but presumably no longer on rotation on the Tiltyard)?
ReplyDeleteThanks,
Andrew
"Or" literals are never necessary to express a given set of rules, but they can still be used in the body of rules to improve human readability. For example, they make a few appearances in Speed Chess: http://games.ggp.org/base/games/speedChess/speedChess.kif
DeleteIn GGP-Base, they are generally removed by the DeORer class before any complex work is done on game rules; this is why several places in the codebase don't bother to handle GdlOr objects, which may have given you this impression.