RC W5D1 - First day with Prolog

 On occasion I start working on something but then forget the reason I got started in the first place. This time at RC, I find it helpful to go back to SICP to answer the questions like “why learn Prolog?”.

Section 4.3 of SICP is on non-deterministic computing, which involves building an ‘automatic search’ into the evaluator. Here expressions can have more than one possible value, so the evaluator chooses a possible value and checks if requirements are met. If not, the evaluator tries out new choices or backtracks to an earlier state where there are choices. The evaluation either end successfully or fails when there are no more choices.

What’s new here is the notion of ‘requirements being met’. In other words, declaring the desired state and getting the evaluator to find it rather than declaring the exact steps. It’s Day 1, but what comes to mind is querying a database. Instead of instructions, the user declares relations.

Prolog first appeared in 1972. I became more intrigued when I learned Datalog is a successor (how they relate will have to be a different post).

Perhaps it’s helpful to look an example, here from section 4.3.2.

Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that  contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper, Smith does not live on a floor adjacent to Fletcher’s. Fletcher does not live on a floor adjacent to Cooper’s. Where does everyone live?

The Prolog solution on Rosetta Code is compact. Symbols are denoted with quotes, variables are uppercased. Chelsea Troy has a modified (to be non-deterministic) Scheme solution here.

select([A|As],S) :- select(A,S,S1), select(As,S1).
select([],_). 

dinesmans(X) :-
    %% Baker, Cooper, Fletcher, Miller, and Smith on different floors 
    %% of an apartment house with five floors. 
    select([Baker,Cooper,Fletcher,Miller,Smith],[1,2,3,4,5]),

    %% Baker does not live on the top floor. 
    Baker =\= 5,

    %% Cooper does not live on the bottom floor.
    Cooper =\= 1,

    %% Fletcher does not live on either the top or the bottom floor.
    Fletcher =\= 1, Fletcher =\= 5,

    %% Miller lives on a higher floor than does Cooper. 
    Miller > Cooper,

    %% Smith does not live on a floor adjacent to Fletcher's.
    1 =\= abs(Smith - Fletcher),

    %% Fletcher does not live on a floor adjacent to Cooper's.
    1 =\= abs(Fletcher - Cooper),

    %% Where does everyone live?
    X = ['Baker'(Baker), 'Cooper'(Cooper), 'Fletcher'(Fletcher), 
         'Miller'(Miller), 'Smith'(Smith)].

main :-  bagof( X, dinesmans(X), L ) 
         -> maplist( writeln, L), nl, write('No more solutions.') 
         ;  write('No solutions.’).

Verse and Mercury are functional logic languages; Mercury even calls itself 'Prolog meets Haskell’. Details will follow in later posts.