2018-01-16

Waiting on a build, so now seems like a good time to update this.

Started learning prolog from the Learn Prolog Now using SWI Prolog. Unfortunately, I don't have this working on the Pixelbook (yet!). One of the exercises that was most interesting to me was solving a crossword. Right now, all the source code for Prolog is called a "knowledge base" in the tutorial, and you then load that knowledge base into the interpreter and run queries against it. Accordingly, the crossword knowledge base that you are started with is

%% Exercise 2.4: Here are six Italian words:                                                                                           
%%                                                                 
%%     - astante                                                   
%%     - astoria
%%     - baratto
%%     - cobalto
%%     - pistola
%%     - statale
%%
%% They are to be arranged, crossword puzzle fashion, in the following grid:
%%
%%      V1  V2  V3
%%      .   .   .
%% H1 . 1 . 4 . 7 .
%%      .   .   .
%% H2 . 2 . 5 . 8 .
%%      .   .   .
%% H3 . 3 . 6 . 9 .
%%      .   .   .
%%
%% The following knowledge base represents a lexicon containing these words:

word(astante, a,s,t,a,n,t,e).
word(astoria, a,s,t,o,r,i,a).
word(baratto, b,a,r,a,t,t,o).
word(cobalto, c,o,b,a,l,t,o).
word(pistola, p,i,s,t,o,l,a).
word(statale, s,t,a,t,a,l,e).

%% Write a predicate crossword/6 that tells us how to fill in the
%% grid. The first three arguments should be the vertical words from
%% left to right, and the last three arguments the horizontal words
%% from top to bottom.

It took me a little bit to figure out how to express this; my first attempt was

crossword(V1, V2, V3, H1, H2, H3) :-
    word(V1, _, _1, _, _2, _, _3, _),
    word(V2, _, _4, _, _5, _, _6, _),
    word(V3, _, _7, _, _8, _, _9, _),
    word(H1, _, _1, _, _4, _, _7, _),
    word(H2, _, _2, _, _5, _, _8, _),
    word(H3, _, _3, _, _6, _, _9, _)

Interestingly, this came up with a solution where one of the words was used more than once. While this wasn't an explicit goal of the exercise, it seems reasonable to expect (given how crosswords usually work) that there should be a uniqueness constraint. That leads to a revised form that adds these constraints:

crossword(V1, V2, V3, H1, H2, H3) :-
    word(V1, _, _1, _, _2, _, _3, _),
    word(V2, _, _4, _, _5, _, _6, _),
    word(V3, _, _7, _, _8, _, _9, _),
    word(H1, _, _1, _, _4, _, _7, _),
    word(H2, _, _2, _, _5, _, _8, _),
    word(H3, _, _3, _, _6, _, _9, _),
    V1 \= V2, V1 \= V3, V1 \= H1, V1 \= H2, V1 \= H3,
    V2 \= V3, V2 \= H1, V2 \= H2, V2 \= H3,
    V3 \= H1, V3 \= H2, V3 \= H3,
    H1 \= H2, H1 \= H3, H2 \= H3.

Note that this requires pairs to be checked; I don't yet know how to express a uniqueness constraint among multiple variables.

Executing the query in the swipl prompt gives a pair of solutions; they're mirrors of each other, swapping the words in the vertical columns with the words in the horizontal columns:

$ swipl -q
1 ?- [crossword].
true.

2 ?- crossword(A, B, C, D, E, F).
A = astante,
B = cobalto,
C = pistola,
D = astoria,
E = baratto,
F = statale ;
A = astoria,
B = baratto,
C = statale,
D = astante,
E = cobalto,
F = pistola ;
false.

A tiny trick, but it's fascinating to see it at work. When I was working through the AI course, the knowledge base we used for the air cargo problem was fascinating to me, and I'd like at some point to write a C++ (and Rust) embeddable knowledge base built on FOL. This would make it easier to integrate a KB into existing systems without needing some kind of Prolog interop.

I also picked up a copy of The Practice of Prolog and Logic for Computer Science. That should give some background in the area besides just two chapters in AIMA. I had started writing a library for this in C++ while at my parents' place over Christmas, but it wasn't anything worth talking about (or keeping in git, really), though I might throw it in my new sandbox repo.

I've also started keeping an exocortex. It would be nice if the C-s shortcut worked, but it's not a deal breaker. I mentioned it earlier, but I also have a sandbox repo now for storing experiments. It's similar to the basement repo I had before where I stuck early-stage and prototype code in. This is more focused on learning, though. I guess I could have repurposed the basement, but I like the sandbox name more.


Tags: ,