Palindrom dates
@lizettegagne re-tweeted as follows earlier today (or yesterday +/-): "RT @mashable: Happy Palindrome Day everyone - 01022010! Last one was 10022001, prior to that 08311380!! Wow! They don't come around often." I hacked up the following Prolog code to get some certainty. Simple modification reveals that European ordering or YYYYMMDD ordering would lead to entirely different results. Try it out!
PF
?- main.
08311380
10022001
01022010
true.
% This is what a palindrom is ...
palindrom(S) :- reverse(S,S).
% Generate all palindrom dates; ignoring leap years.
special(MDYS) :-
year(_,YS),
month(M,MS),
day(M,_,DS),
append(MS,DS,MDS),
append(MDS,YS,MDYS),
palindrom(MDYS).
% Here is an over-approximation of dates.
year(X,S) :- ranges(4,1380,2010,X,S).
month(X,S) :- ranges(2,1,12,X,S).
day(1,X,S) :- ranges(2,1,31,X,S).
day(2,X,S) :- ranges(2,1,29,X,S).
day(3,X,S) :- ranges(2,1,31,X,S).
day(4,X,S) :- ranges(2,1,30,X,S).
day(5,X,S) :- ranges(2,1,31,X,S).
day(6,X,S) :- ranges(2,1,30,X,S).
day(7,X,S) :- ranges(2,1,31,X,S).
day(8,X,S) :- ranges(2,1,31,X,S).
day(9,X,S) :- ranges(2,1,30,X,S).
day(10,X,S) :- ranges(2,1,31,X,S).
day(11,X,S) :- ranges(2,1,30,X,S).
day(12,X,S) :- ranges(2,1,31,X,S).
% Generate all strings of values in that range with that length
ranges(L,Min,Max,X,S2) :-
( Min =< Max, X = Min, name(Min,S1), pad(L,S1,S2)
; Min < Max, Min1 is Min + 1, ranges(L,Min1,Max,X,S2)
).
% Extend a string to the length given
pad(L,S1,S2) :-
length(S1,L1),
( L1 > L, abort
; L1 = L, S2 = S1
; L1 < L, pad(L,[0'0|S1],S2)
).
% Print all solutions
print(S) :- atom_codes(A,S), write(A), nl.
main :- findall(S,special(S),Ss), maplist(print,Ss).
Hi,
ReplyDeleteMuch of this (and other) Prolog code looks like it is written with precise knowledge of the Prolog execution order. In other words, it does not look very "declarative" to me (although I know that is not a precise term).
I find that you can convert such Prolog code to any programming language that has closures almost directly. For example, this is the result of my short effort of converting your code to Ocaml:
http://codepad.org/lcs662c8
(Unfortunately, Ocaml does not have a String.reverse in its standard library, which is the reason why palindrom does not look nicer. On the other hand, it does have a "sprintf", which allows me to do padding much more easily.)
My code is much faster than the Prolog version (with swipl). I'm sure you could achieve much the same result with Haskell.
Being an expert in both languages, do you have any thoughts on the relation between the two?
Happy new year,
Bruno
Hi Bruno,
ReplyDeletethanks for the Ocaml code. This is great. If we continue like this, we get a collection of samples like this one here for Factorial (for Haskell alone). :-)
http://www.willamette.edu/~fruehr/haskell/evolution.html
Yes, without having SLD-Resolution in mind, it would be harder to solve such problems in Prolog. But then again, the program does have a declarative semantics. (Well, using findall/3 requires some argument.) It's just efficiency that gives us our SLD-based insight. And efficiency sucks, as you note, but let me make a few points:
1) This is a little script (in fact, an informal proof) for the special days in question. Writing it with efficiency in mind would be a total waste of time. Would you write proofs optimized for efficiency of automated proving (say in Isabelle)? I just wanted to find out what these days are. If the encoding would not terminate in time, I could always optimize. The code should be optimized for ease of writing and potentially ease of program comprehension. I think it is ...
2) SWI-Prolog by itself is slow on the scale of Prolog implementations.
3) If you can translate that sort of backtracking heavy code into say explicit loops, a major speedup should be achievable (as you obviously guessed and leveraged). Please note that my code is declarative enough not to work out any explicit loops; it rather leaves a number of choice points open.
I like my Prolog code more than your OCaml code :-)
Yes, someone should try Haskell.
Perhaps we can file an entry for the language shootout:
http://shootout.alioth.debian.org/
Ralf
PS: Prolog has things like sprintf (see format & Co.). I was too lazy to use any non-101 predicates.
Hello Ralf,
ReplyDeleteThanks for your reply. I see that I might have blurred my argument by talking about performance, which was not really the main point.
Actually, I agree with you that the Prolog code usually looks better: I see it as a nice DSL for describing a search problem (with backtracking in the search space and so on). However, I wonder why Prolog - and specifically its implementation - is not more integrated with other (non-logic) programming languages.
For example, you've talked about JPL for integrating Prolog and Java, but as far as I understand this retains SWI-Prolog's runtime and uses the foreign interfaces of both systems. So while you can integrate programs in both languages, the implementation is separate. However, I tried to make the point that it seems that Prolog programs can be quite easily translated to an equivalent program in language with closures, which removes the need for a dedicated Prolog runtime. Someone could easily build something like that on top of Haskell for example.
A related approach that I found is the following, which uses the yield keyword of some languages rather than the sort of continuation-passing-style that I've employed:
http://yieldprolog.sourceforge.net/
Best,
Bruno
Cool stuff this yieldprolog, Bruno. As to Prolog and Java integration, there seem to be a few interpreters out there that interpret Prolog in Java, and there is something like Prolog Cafe which translates Prolog to Java. My feeling is that none of these approaches are widely used. Perhaps, the heavy lifting use cases of Prolog eventually need a full-fledged Prolog system, and so the burden of foreign-language interfacing may be less than the disadvantages of a castrated Prolog system (interpreter, translator), but I haven't thought much about it.
ReplyDeleteRalf