Prolog: Interesting Things about Prolog

prolog_interesting_things.md

Interesting Things about Prolog

1. Facts = Axioms
2. Rules = Relations = Predicates

There are 2 types of knowledge in Prolog: Axiomatic Knowledge and Consequent Inferred Knowledge.

Axiomatic knowledge is the knowledge that you write as facts (and as rule predicates) in Prolog. Prolog cannot retract any of these axioms after being written (you can't do this at compile time nor at run time). This is called non-monotonic logic.

Prolog is a closed world assumption (CWA) system with negation as failure and unique name assumption. In this model, any knowledge that is not known as an axiom or as a consequence is simply defaulted as false.

In an open world assumption (OWA) system, any fact that is not known as an axiom or as a consequence is considered to be "Unknown". It seems that there is some relationship of this CWA vs OWA to classical logic to constructive/intuitionistic logic.

SQL databases also operate as a CWA system. However in SQL databases, you can use NULL to model the OWA. However adding the possibility of NULL means you need to consider 3-valued logic. If a field is used in a conditional operation, and that field can be NULL, then you need to think about the 3-valued truth table, which is quite a bit more complex!

Prolog itself can also model OWA, as you need to just define predicates like Known and Unknown.

Note that since Prolog still allows consequent inferred knowledge to be retracted or expanded, things that were unprovable can become provable with an enlarged set of axioms or relations.

An OWA system should be able to also retract its axioms, as it learns more about the world. But this results in an inconsistency, since retracting an axiom means the axiom is contradicted. How is this resolved? It turns out that some OWA reasoners will try to make an inference that allows the knowledge set to still be consistent. This can be done by not having the unique name assumption. See this OWL/RDF example:

Let’s continue with the example of “Juan is a citizen of USA” and assume the following statement is true: “a person can only be citizen of one country.” Up to now, everything is fine. Now consider we add the following statement: “Juan is a citizen of Colombia.” In a CWA system, this would be an error because we previously stated that person can only be a citizen of one country and we assume that USA and Colombia are different countries. In an OWA system, instead of generating an error, it would infer a new statement. The logic is the following: “If a person can only be citizen of one country, and if Juan is a citizen of USA and Colombia, then USA and Colombia must be the same thing!” Note that in the CWA case, we assumed that USA and Colombia are different countries. With OWA, this is not assumed. This is what is called Unique Named Assumption (UNA). CWA systems have UNA. OWA systems do not have UNA. However, one could manually add the UNA. In other words, if I have a list of all the countries, I would have to explicitly state that each country is different from each other. In our example, if we add the following statement: “USA is different from Colombia,” the OWA would now generate an inconsistency. The OWA logic is the following: “If a person can only be a citizen of one country, and if Juan is a citizen of USA and Colombia, then USA and Colombia must be the same thing; but hold on, USA and Colombia are different, so they can’t be the same! Something is wrong.” http://www.dataversity.net/introduction-to-open-world-assumption-vs-closed-world-assumption/

In some cases, an inference cannot be made that will make the world consistent again, at that point you've got a problem! It seems like this would be punted to the user to resolve (there are also OWL based systems that you can use to automatically find inconsistencies).

However a logical development called probabilistic programming languages, could potentially assign weights and probabilities to knowledge, and when new evidence is acquired, that may shift the weight of one axiom/consequence over another axiom/consequence.

This makes me think that my progression of research into logical languages should proceed in this manner:

Prolog
    - OWL Reasoners/Semantic Web
      Mercury/Logtalk
        - Problog
          MC-Stan
          BayesDB

Another idea could be to scope the world of knowledge, so that in particular scope, an axiom can be retracted.

OWA more accurately models the real world, but it does get complicated to reason about!

Comparing CWA to OWA: http://www.mkbergman.com/852/the-open-world-assumption-elephant-in-the-room/

The backtracking proof search that Prolog performs sometimes is called "generate and test". This type of proof search does not scale well. There are alternative ways called constraint programming which can restrict the amount of things to search, and there's also alternative search strategies.

Funny things (mostly from SWI-Prolog):

• = is Prolog unification, while unify_with_occurs_check is standard unification. The difference is that Prolog unification doesn't perform an occurs check. This means we don't check if the variable we are unifying with occurs within the term we are trying to unify against.

• Unification doesn't involve evaluation, specifically arithmetic evaluation requires an is operator.

• The \ is often used as a prefix to an operator which means not. So \= means not equals, while \+ means not provable.

• p(V), writeln(V), false. - this is how you declaratively print all possible results. This can result in non-termination! This is because , false. means AND false., which will result in the entire expression resolving to false, which causes Prolog to backtrack and find further solutions, but writeln(V) has a side-effect of printing the intermediate solutions that have been found.

• You can use ; or space in the interactive shell to print the next solution for any given query.

• Difference lists in Prolog are just a data structure/pattern where you have two lists. The second list is a sublist of the first list from the right. For example: [1,2,3] and [2,3]. This can be used for parsing, where you have a predicate like statement(T, R), the T is the input tokens and the R is the remaining tokens. The difference between T and R is the tokens consumed by statement. The Rvariable is passed as the input to the next predicate to consume. Preferably at the very end, theR` should just be an empty list, indicating all input has been consumed.

• Definite clause grammars (DCG) make the difference list pattern into a first class primitive with the --> operator.

• DCG seems to make Prolog parsing the equivalent of recursive descent with backtracking, which limits grammar expressiveness to LL(k) if you want to guarantee termination. The DCG can also support extra parameters, which makes DCGs the equivalent of attribute grammars with both inherited and synthesised attributes.

• Remember to keep the base case on top of the inductive predicate, otherwise this can cause an infinite loop. We can call this the "base-case-first" rule.

• Due to ordered pattern matching, in addition to the base-case-first rule, we also have a longest-match/maximal-munch rule. Basically make sure your predicate options state the longest pattern match first, it can avoid costly backtracking later down the line. This is relevant to logic but also Prolog parsing using definite clause grammars. This rule specifically applies when some cases of a multi-case predicate have a pattern match expression that is a (ordered) subset of of another case's pattern match expression.

• Left recursion is a problem in both top-down parsing and backwards-chaining depth-first-search logical reasoners like Prolog. This happens whenever something declaratively left recursive is executed procedurally.

  Since Prolog does not have automatic left recursion elimination, we need to manually eliminate the left recursion.

  In a pure logic expression, order shouldn't matter between the sub-goals, so reordering the sub-goals should eliminate the left-recursion. However in parsing and in side-effectful predicates, the order between sub-goals may matter, in which case we need to use a more sophisticated algorithm.

  Here's an example:

  statement_1 --> noun_phrase, verb_phrase.
  statement_1 --> statement_1, conjunction, statement_1.
  
  statement_2 --> noun_phrase, verb_phrase, statement_rest.
  statement_rest --> epsilon.
  statement_rest --> conjunction, statement_2, statement_rest.
  epsilon --> [].
  
  statement_3 --> simple_statement.
  statement_3 --> simple_statement, conjunction, statement_3.
  simple_statement --> noun_phrase, verb_phrase.
  
  conjunction --> [and].
  conjunction --> [or].
  conjunction --> [but].
  
  noun_phrase --> determiner, noun.
  
  verb_phrase --> verb, noun_phrase.
  verb_phrase --> verb.
  
  determiner --> [the].
  determiner --> [a].
  
  noun --> [roger, qiu].
  noun --> [roger].
  noun --> [woman].
  noun --> [man].
  
  verb --> [shoots].

  The statement_1, statement_2 and statement_3 are 3 variations of writing the same recursive predicate.

  The statement_1 is the most natural, and closest to the original context free grammar. While it works for most cases, it will result in an infinite loop if given a query like statement_1([woman, shoot], []). This query should evaluate to a false. But statement_1 cannot give back an answer.

  The statement_2 follows direct left recursion elimination, and it requires introducing statement_rest and epsilon.

  The statement_3 is another variant, however this may not be scalable.

  Beware that eliminating left recursion into right recursion can convert the associativity of operators!

• Infix operatior definitions has associativity specification in its Type parameter. Basically xfx means equal associativity, yfx means left associativity and xfy means right associativity. The y specifies an operand that has less or equal precedence as f, while x specifies an operand that has less precedence than f. In Haskell, you only get to choose between left associativity or right associativity, and equal associativity operators simply default to left associativity.