The Wonderous Declarative World of Prolog
There are a lot of programming languages out there. Some are well known, others are not. Go through this journey of the Prolog programming language and its derivates with their own use cases. Instead of imperative programming, Prolog needs declarative programming. You describe the problem and it finds a solution for it instead of describing the actual solution to the problem. Each of these programming languages are not what you’re used to, they require a different way of thinking.
Prolog
Complete code can be found on my GitHub and the paper is available here.
Prolog (Programmation en Logique) is based on Horn clauses, a Turing-complete subset of first-order predicate logic. Prolog will try to find a solution for any given problem which is defined within first-order predicate logic. Prolog can be used to find the solution of the infamous Einstein’s riddle. The most used example is the family tree, you define the family relations and Prolog will evaluate how 2 people are related to each other.
mother(X,Y) :- parent(X,Y), female(X).
sibling(X,Y) :- parent(P,Y), parent(P,X), X \= Y.
sister(X,Y) :- sibling(X,Y), female(X).
grandparent(X,Y) :- parent(P,Y), parent(X,P).
greatgrandparent(X,Y) :- parent(P,Y), grandparent(X,P).
entwined(X,Y) :- parent(X,Child), parent(Y,Child), X \= Y. uncle(Uncle, N) :-
parent(Par,N),
sibling(Uncle,Par),
male(Uncle).
uncle(Uncle, N) :-
parent(Par,N),
sibling(Par, Aunt),
entwined(Aunt, Uncle),
male(Uncle).cousin(X,Y) :-
grandparent(GP, X),
grandparent(GP, Y), X \= Y,
\+sibling(X,Y).ancestor(X,Y) :- parent(X,Y). % Base case.
ancestor(X,Y) :- parent(P,Y), ancestor(X,P). % Recursive rule.
More complicated problems such as the Tower of Hanoi, which is perfectly describable as a set of rules, can also be modeled and executed with Prolog.
hanoi(N) :-
move(N, source, dest, spare).
move(1, Source, Dest, _) :-
write('Move disk from '),
write(Source),
write(' to '),
write(Dest),
nl.
move(N, Source, Dest, Spare) :-
N > 1,
N1 is N - 1,
move(N1, Source, Spare, Dest),
move(1, Source, Dest, Spare),
move(N1, Spare, Dest, Source).Execution
Installation is done with brew install swipl , which stands for swi-prolog. Another variant gnu-prolog, better known as gprolog is also available but has some subtle differences. Running it is as easy as typing siwpl in your command line. Loading Prolog files are done by for example[factorial]. , this will load in the factorial.pl file or typing [temperature]. , this will load in the temperature.pl file. Prolog can also be used for some more generic problems like calculating factorials. It will always try to fill in undefined variables, such in this case Fact .
factorial(N, Fact) :-
N > 0,
N1 is N — 1,
factorial(N1, Fact1),
Fact is N * Fact1.
factorial(0, 1).Simple arithmetic is also possible by for example converting temperatures.
convert(Cel, Fahr):-
Fahr is 9.0 / 5.0 * Cel + 32.Now it is possible to execute the factorial function.
?- factorial(3,Fact).
Fact = 6.And after you loaded the [temperature]. file, you can convert temperatures.
?- convert(10.0, Fahr).
Fahr = 50.0.More examples include writing a predicate eval/2 which will reduce a boolean formula to true or false. So, for example, the following formula will reduce to false.
?- eval(and(or(not(true),true),false),X).
X = false.The Prolog code behind this formula will have to parse the and , or , and not rules recursively and evaluate them. Note that everything can be found on my GitHub page.
and(true,true,true).
and(_, false,false).
and(false, _, false).or(true,_,true).
or(_,true,true).
or(false,false,false).not(true,false).
not(false,true).eval(true).
eval(false).eval(X,X):-
eval(X).
eval(and(X,Y),R):-
eval(X,XV),
eval(Y,YV),
and(XV,YV,R).
eval(or(X,Y),R):-
eval(X,XV),
eval(Y,YV),
or(XV,YV,R).
eval(not(X),R):-
eval(X,XV),
not(XV,R).
Golog
Complete code can be found on my GitHub and the paper is available here.
Golog is based on situation calculus and is a logic programming language. It is derived from AlGOl in LOGic. The goal is to obtain a goal through what’s called Generalized Planning (it uses a kplanner which is Prolog code for an iterative planner). It is based on first-order logic or better known as predicate logic. The language appears well suited for applications in high-level control of robots and industrial processes, intelligent software agents, discrete event simulation, etc. It is run by ECLiPSe, it contains constraint solver libraries, a high-level modeling and a superset of Prolog. You can install it by downloading the binaries here, and unpack and add them to your path.
In situation calculus, it's hard to describe every effect of each action. If a robot picks up a box, you will have to define that everything else stays the way it is, except for the picked-up box. Everything has to be described that is not affected by an action. This is known as the frame problem.
You describe your initial situation, actions that can happen and causal connections between those actions. Let’s clarify this with an example. Let’s say you want to do some mineral mining, the goal is to get the mineral by removing sand layers and/or ice layers that lay on top of it. You start by describing how that world can be interacted with through actions. This plan can consist of, for example, getting finished on true.
top :- kplan(finished=yes).Execution
The plan is finished when we put away a mineral which can be defined as an action, which I will explain later on. This will set finishedon true.
causes(putAwayMineral,finished,yes,true).primary actions
prim_action(A,RL) => A as a primitive action with RL as a list of possible sensing results.
Those actions specify what action can take place. You can put away a mineral, you can remove ice or sand layers, and sense which layer it is. Putting away a mineral is an action which only has one result ok , whereas sensing layers can be for example both noIceLayer or iceLayer.
prim_action(putAwayMineral,[ok]).
prim_action(removeIceLayer,[ok]).
prim_action(removeSandLayer,[ok]).
prim_action(senseSandLayer,[noSandLayer,sandLayer]).
prim_action(senseIceLayer,[noIceLayer,iceLayer]).initial states
init(F,V) => V is a possible initial value for F.
You’ll also need to define what your initial state can be made of. It can be made of ice or no ice layers and sand or no sand layers.
init(ilayers,iceLayer).
init(ilayers,noIceLayer).
init(slayers,sandLayer).
init(slayers,noSandLayer).causal connections
causes(A,R,F,V,C) => when A occurs with sensing result R, then F is caused to have the possible values of each V for which C is possibly true.
The primary actions can cause the initial states to be altered. For example, removing a layer will subtract a layer from the initial state. And obtaining a mineral will result in a finished plan. Removing a sand layer can both result in another sand layer or not a sand layer (and potentially an ice layer).
causes(putAwayMineral,finished,yes,true).causes(removeSandLayer,layers,X,X is layers-1).
causes(removeSandLayer,slayers,noSandLayer,true).
causes(removeSandLayer,slayers,sandLayer,true).causes(removeIceLayer,layers,X,X is layers-1).
causes(removeIceLayer,ilayers,noIceLayer,true).
causes(removeIceLayer,ilayers,iceLayer,true).
preconditions
poss(A,C) => declares C is the precondition for action A
Before some action can be fulfilled, it needs to comply with some preconditions. These can be defined as follows. If you want to remove an ice or sand layer, there has to be one. It seems kind of obvious for us humans, but everything needs to be specified in order for a plan to be constructed. You can also only put a mineral away if there are no more ice and sand layers.
poss(removeIceLayer,ilayers=iceLayer).
poss(removeSandLayer,slayers=sandLayer).
poss(putAwayMineral,and(ilayers=noIceLayer,slayers=noSandLayer)).stop criteria
- settles(A,R,F,V,C) => when A occurs with sensing result R, and C is known, then F is known to have value V
- rejects(A,R,F,V,C) => when A occurs with sensing result R, and C is known, then F is known not to have value V
The only thing left is to specify when to stop and define criteria for when there are still layers or no layers at all. If sensing for a sand layer results in no sand layer, the number of layers cannot be 0 because there can always be ice layers. If it results in a sand layer, the number of layers cannot be 0 because there are still sand layers. If sensing a layer results in X then you have slayers which has X layers.
settles(senseSandLayer,X,slayers,X,true).
settles(senseIceLayer,X,ilayers,X,true).rejects(senseSandLayer,noSandLayer,layers,0,true).
rejects(senseSandLayer,sandLayer,layers,0,true).rejects(senseIceLayer,noIceLayer,layers,0,true).
rejects(senseIceLayer,iceLayer,layers,0,true).
final plan
If we execute this and let the program figure out a plan to go mineral mining, it will find the following planning solution. Run eclipse and load the [robot]. file, you can then execute top which will find a plan.
A plan is found after 0.00999999999999998 seconds.
-------------------------------------------
LOOP
CASE senseSandLayer OF
-noSandLayer:
CASE senseIceLayer OF
-noIceLayer: EXIT
-iceLayer:
removeIceLayer ;
NEXT
ENDC
-sandLayer:
removeSandLayer ;
NEXT
ENDC
ENDL ;
putAwayMineralProbLog
Complete code can be found on my GitHub and the paper is available here.
ProbLog is simply Prolog with probabilities. As you can see on their GitHub page, it can calculate the probability of a coin toss. When you press evaluate on their online editor, this will result in 0.8 (P(someHeads) = 1 — (1-P(heads1)) (1-P(heads2)) = 1 — (1–0.5) (1–0.6) = 0.8).
% Probabilistic facts:
0.5::heads1.
0.6::heads2.
% Rules:
someHeads :- heads1.
someHeads :- heads2.
% Queries:
query(someHeads).It can also be modeled to predict how likely it is, that a person buys a specific drink. This can be done by specifying a probability of the ‘likeness’ of a drink.
preference(john,whiskey,like_little).
preference(john,gin,like_little).
preference(john,lager,like_much).
preference(mary,whiskey,like_verymuch).
preference(mary,redwine,like_much).
preference(peter,whiskey,like_much).
preference(peter,stout,like_much).
preference(peter,whitewine,like_no).
preference(paul,whiskey,like_no).
preference(paul,coffee,like_verymuch).
preference(ann,gin,like_verymuch).
preference(ann,lager,like_little).0.0::buy(Person,Beverage) :- preference(Person,Beverage,like_no).
0.1::buy(Person,Beverage) :-
preference(Person,Beverage,like_little).
0.5::buy(Person,Beverage) :-
preference(Person,Beverage,like_much).
0.9::buy(Person,Beverage) :-
preference(Person,Beverage,like_verymuch).query(buy(Person,whiskey)).
TL;DR
Instead of imperative programming, Prolog needs declarative programming. You describe the problem and it finds a solution for it instead of describing the actual solution to the problem. Prolog is based on Horn clauses, a Turing-complete subset of first-order predicate logic. Golog is based on situation calculus and is a logic programming language. It is derived from AlGOl in LOGic. The goal is to obtain a goal through what’s called Generalized Planning, it is based on first-order logic or better known as predicate logic. ProbLog is simply Prolog with probabilities.
