Introduction
Raymond Smullyan posed this riddle inspired by a story from Lewis Carroll.
One day Alice met the lion and the unicorn resting under
a tree. They made the following statements:Lion: Yesterday was one of my lying days.
Unicorn: Yesterday was one of my lying days.From these statements, Alice, who was a bright girl,
was able to deduce the day of the week. What was it?
A Prolog solution was given in a Paper from 1986 about VM/Prolog. The paper discussed theorem proving versus logic programming with Prolog. We give a variant of this solution and discuss the involved meta predicates.
Meta Solution
The background information for the riddle reads as follows:
When Alice entered the forest of forgetfulness, she did not forget everything, only certain things. She often forgot her name, and the most likely thing for her to forget was the day of the week. Now, the lion and the unicorn were frequent visitors to this forest. These two are strange creatures. The lion lies on Mondays, Tuesdays, and Wednesdays and tells the truth on the other days of the week. The unicorn, on the other hand, lies on Thursdays, Fridays, and Saturdays, but tells the truth on the other days of the week.
As was already done in the 1986 Paper, the above background information can be modelled as Prolog facts. We take the argument order such that later the compared Prolog systems will use first argument indexing:
yesterday(monday , sunday ).
yesterday(tuesday , monday ).
yesterday(wednesday, tuesday ).
yesterday(thursday , wednesday).
yesterday(friday , thursday ).
yesterday(saturday , friday ).
yesterday(sunday , saturday ).
lies(monday , lion).
lies(tuesday , lion).
lies(wednesday, lion).
lies(thursday, unicorn).
lies(friday, unicorn).
lies(saturday, unicorn).
To model the statements about lying we make use of a meta predicate contrary/2. A meta predicate is a predicate that takes Prolog goal arguments and not simply only Prolog term arguments. We do not optimize this predicate much and use only Prolog conjunction (',')/2 and Prolog negation as failure:
contrary(S, T) :- S, \+ T.
contrary(S, T) :- \+ S, T.
By use of the meta predicate contrary/2 we can now quite handily formulate when the lion was lying and when the unicorn was lying. The main predicate solve/1 then searches a week day:
solve(D) :- yesterday(D, Y),
contrary(lies(D, lion), lies(Y, lion)),
contrary(lies(D, unicorn), lies(Y, unicorn)).
We can replicate the 1986 Paper result in a Prolg top-level by posing a query. There is only one solution which is the weekday thursday:
?- solve(D).
D = thursday ;
false.
Negation Compatibility
We might ask, is the above solution portable across different Prolog systems. Theoretically negation as failure (\+)/1 is defined in the ISO core standard. Practically a Prolog system might have negation as failure (\+)/1 with a semantics that doesn't exactly match the ISO core standard.
We made this test case showing the ISO core standard outcome:
p(a).
p(b).
q(b).
q1 :- \+((Y=!,p(X),Y,q(X))).
q2 :- Y=!,\+((Y=!,p(X),Y,q(X))).
?- q1.
no
?- q2.
yes
Not all Prolog systems agree with this outcome. We found:
A rational for realizing a different semantics than the ISO core standard could be performance considerations. A Prolog implementor might want to inline negation as failure and it might come handy to have the semantics such that call/1 is greedily applied to naked goals, which would explain the faults. But does the ISO core standard semantics need to be slow?
Negation Implementation
We do not have yet a fully conclusive answer to whether the ISO core standard semantics is slow. So far we can only demonstrate that with a relative simple approach to meta predicates a Prolog system can provide negation as failure that can exceed the majority of Prolog systems. In the ISO core standard negation as failure is basically defined as:
\+(X) :- call(X), !, fail.
\+(_).
As can be seen from the above bootstrapping a fast call/1 will surely help. In Dogelog Player call/1 is practically a no-op, all that it does is as follows. In this implementation call/1 is basically dereferencing its argument, type checking its argument and then puts the argument as a new subgoal on the goal list. An ordinary goal meta argument will be immediately executed afterwards:
function special_call() {
let goal = call.args[0];
goal = deref(goal.args[0]);
check_callable(goal);
cont(new Compound(".", [goal, call.args[1]]));
return true;
}
As can be seen no compilation is done by call/1 itself. Compilation is done by subgoals that are control constructs in that they have received an according definition that includes compilation. This applies for the control constructs (',')/2, (;)/2 and (->)/2. Here is an example how (',')/2 is implemented:
A, B :-
sys_trans_body(A, nothing, J, R, H),
sys_trans_body(B, J, M, H, []),
'$SEQ'(M, R).
The conjunction (',') taps into the Albufeira code compiler. This compiler provides a transpile and a encode service. We only use the transpile service and don't invoke a more costly encode service, that does also some low-level optimization. This gives a compromise between compilation time performance and runtime time performance.
Benchmark Results
Fortunately the riddle is not bugged by the ISO core standard semantic differences. Further the requirements for negation as failure and call/1 inside contrary/2 are relatively tame, they are only invoked with ordinary goals and not with control constructs. Lets see how different Prolog systems fare, even those with a different semantics:
We were running the Lion and Unicorn riddle 1'000'000 times to perform the benchmark. SWI-Prolog amazingly excells, whereas GNU Prolog, Trealla and Scyer lag behind. Recent Dogelog Player 1.1.3 for Java, which was the result of a tuning campaign, can currently occupy the middle. But the race is on, we are highly motivated to close the gap to SWI-Prolog.
Conclusions
We presented a solution based on a user defined meta predicate contrary/2. Differences in negation of failure made us curious how other Prolog systems perform. Dogelog Player with a simple strategy for meta predicates without sacrificing ISO core standard compatibility, lands in the middle. Hence we could demonstrate that one can have the cake and eat it too.
The lion and the unicorn met PROLOG
Bruce D. Ramsey, 1986 - Free Access
https://dl.acm.org/doi/10.1145/382278.382395