🚀 go-pugleaf

This contribution was inspired by the recent discussion of the
Triangle Puzzle by Richard O'Keefe.

A wide class of problems, the triangle puzzle is one of them
(see below), calls for a natural solution in the form of a
sequence of complex data structures describing the successive states
of the problem being solved by a series of steps.

The general situation is as follows:

  Problem(initparams,Solution) <-
    Initialstate(initparams,State),
    Path(params,State,Solution).

  Path(params,State,[]) <-
    Endstate(params,State).
  Path(params,Oldstate,[onestep,Tail]) <-
    Onestep(params,Oldstate,Newstate),
    Path(params,Newstate,Tail).

Basically we deal with a class of graph traversal problems.
The adjacent nodes are described by the predicate "Onestep".
The states of the problem are usually described by complex lists which
are copied over and over with only slight changes. A state for the
triangle puzzle was given by a description of the board giving the
empty and occupied holes.

The declarative languages (Prolog and Lisp)
are clearly at disadvantage for two reasons:

 i) the new state must be obtained from the old one by creating
    a fresh copy of the old state.

 ii) A state must be described by a complicated list even if the problem
     naturally calls for arrays.

The solution of such a problem in a procedural language will modify the
state data structure in place. Clever Prolog programmers have discovered
long ago that certain degree of in-place-modification can be obtained
directly in Prolog by the employment of the "var" predicate. There is
only one list describing a state. The list consists initially of
unbound variables. As the solution progresses the unbound variables
are bound to values describing the new states. If a part of the state,
usually denoting a "not visited" situation, is
found unbound by a call to the "var" predicate, the part can be marked
by a value signifying the "visited" situation.

This technique applies only to such problems (maze traversal, tiling problems,
constraint satisfaction problems, etc.)
where the state changes exactly once for each of its parts.
I will mention here two examples, both of which appeared in the Prolog digest:
T. Evans's solution of the Cube Packing Problem and the Baage's solution
of the Christmas Puzzle. During the solution of the Triangle Puzzle
a hole in the board changes the state from occupied to empty and back many
times. This means that "var" cannot be used.

I would like to stress here that a logically clean solution of the Cube packing
and Christmas puzzles logically calls for the encoding of the situation by the
old state/new state technique.
Needless to say this would be terribly inefficient.
The reduction of the declarative Prolog to the procedural Pascal by the
use of "var" seems to be a lesser evil questioned only by the purists. 
The majority
of Prolog programmers grew up with the procedural languages and they simply
do not care about the logic. Ironically, quite often one hears
the same programmers to praise the declarative style
"of specifying only what and not how" just as they specify the "how"
by the use of "var" and "assert".

Is it possible to have both the cake and eat it?  The answer is yes
if one allows modifiable variables in a declarative setting.
A natural, and logically elegant, solution is to have the language
processor recognize the copying situation: the old state will
never be used after the new state has been obtained. The processor can reuse
the storage in such a case. There is a large amount of research going on
in this direction. The problem is a difficult one with no acceptable
solution in sight.

Alternatively, and admittedly as a slightly less elegant solution, one can
employ the declarative reading of procedural programs as proposed
by Rick Hehner and Tony Hoare. (See for instance the two 84 CACM papers
on the "Predicative Programming" by Hehner).
Certain arguments
can be designated as being 'input/output'. They will be modified in place
whereas logically they are a pair of arguments: one 'input' and one
'output'. For instance the following predicate

   Incr(x) iff x := x + 1

Is only an abbreviation for the predicate

   Incr(x_in,x_out) iff x_out = x_in + 1.

The formula

    x := 6 & Incr(x) & Incr(x) & P(x)

is only an abreviation for the formula

    x1 = 6 & Incr(x1,x2) & Incr(x2,x3) & P(x3)

Of course, only a madman would employ this style of programming
with short values such as integers, but with the list-typed arguments
the technique is certainly faster than copying and it is logically cleaner
than the use of the "var" predicate.

An implementation of reassignable variables calls for the specification
of modes for the arguments. I have employed this in the programming
language Trilogy. The arguments of Trilogy have four modes: 'input' (x:<T)
where the value x of type T is fully known upon the predicate call,
'output' (x:>T) where the argument x obtains a full value before the
predicate call is exited,
'input/output' (x:.T) which is logically a pair of variables, and finally
the 'symbolic' or 'logical' mode (x::T) where x is specified by constraints
(of which "no constraint" yields the "unbound" variable).

Following is the implementation of the Triangle Puzzle in Trilogy.
I briefly explain the constructs employed after the text of the program.

{   TRIANGLE PUZZLE IN TRILOGY }
{  Triangle Puzzle: A triangle-shaped board has 15 holes numbered
   0 to 14. There is a peg in each hole. Remove arbitrary peg
   and perform 13 jumps by jumping with a peg over another peg
   into a hole and removing the peg jumped over.
   At the end there will be only one peg on the board.

          0
        1   2
      3   4   5             the query:
    6   7   8   9              one Triangle(0,p)
  10 11   12  13  14        finds  a solution starting with the hole 0 empty
}

Hole = [0..14]      {Interval type describing the holes}
                    {Array type describing a state of the board:}
Board = Hole->I     { b(i) is 0 if i-th hole empty; 1 if there is a peg}

                    {Constant array of lists describing the legal jumps}
                    { "(o,t) in Jumprom(f)" holds if it is possible
                     to jump from the hole f over the hole o to the hole t}
Jumpfrom :< Hole->list (I,I) =
     [ ((1,3),(2,5),Nil),                       {from 0}
       ((3,6),(4,8),Nil),                       {from 1}
       ((4,7),(5,9),Nil),                       {from 2}
       ((1,0),(4,5),(7,12),(6,10),Nil),         {from 3}
       ((7,11),(8,13),Nil),                     {from 4}
       ((2,0),(4,3),(8,12),(9,14),Nil),         {from 5}
       ((3,1),(7,8),Nil),                       {from 6}
       ((4,2),(8,9),Nil),                       {from 7}
       ((7,6),(4,1),Nil),                       {from 8}
       ((8,7),(5,2),Nil),                       {from 9}
       ((6,3),(11,12),Nil),                     {from 10}
       ((7,4),(12,13),Nil),                     {from 11}
       ((11,10),(7,3),(8,5),(13,14),Nil),       {from 12}
       ((12,11),(8,4),Nil),                     {from 13}
       ((13,12),(9,5),Nil) ]                    {from 14}

pred Triangle(h:<Hole, p:>list(I,I,I)) iff
  { h is the starting hole and p solves the puzzle by giving a list
    of 13 triples of the form (from,over,to) }
  b:.Board & b := [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] & {all pegs in}
  b(h) := 0 &      {the starting hole is removed}
  Jumps(13,b,p)    {13 jumps are performed yielding p}

pred Jumps(i:<I, b:.Board, p:>list (I,I,I)) iff
  { i jumps given by p from the board in state b_in lead to b_out}
  if i > 0 then                    {there are jumps to be performed}
    b(from) = 1 &                  {from is a hole with a peg in it}
    (over,to) in Jumpfrom(from) &  {over,to is a jump from the hole from}
    b(over) = 1 & b(to) = 0 &      {the hole over contains a peg, to is empty}
    b(from) := 0 & b(over) := 0 & b(to) := 1 & {new situation on the board}
    Jumps(i-1,b,t) &               {t solves the puzzle from the board pos b}
    p = (from,over,to),t           {thus p is a solution for i-jumps}
  else                             {no jumps to be performed}
    p = Nil
  end

Explanation:

i) The variables of Trilogy start with small letters. Predicates,
  types and constants, being identified by proper names, are
  capitalized.

ii) "Hole" and "Board" are type declarations.
  Hole is an interval type whereas the type
    Board = Hole->I
  is an array (finite mapping) of integer values indexed by the holes.

iii) The constant array "Jumpfrom" of the type "Hole->list (I,I)"
  can be visualized as a set of indexed Prolog facts describing
  the possible jumps. The formula

      (over,to) in Jumpfrom(from)

  used in the predicate "Jumps" is to be read as follows: The
  array subscription "Jumpfrom(from)" denotes the list of possible
  jumps from the hole "from". Each element of the list is a pair
  "(over,to)" giving the jumped over and the destination holes.
  "in" is the infix list membership relation primitive in Trilogy.

  Thus the formula holds iff it is possible to jump from the hole "from"
  over the hole "over" to the hole "to".

iv) A state of the board is described by the 'input/output' array
    "b:.Board", where "b(i) = 1" if the i-th hole contains a peg,
    "b(i) = 0" otherwise.

v) A solution to the puzzle is found by the query

      one Triangle(0,p)

   which constructs the path "p" describing the solution of the
   puzzle as a list. The input argument "0" indicates that
   initially the hole zero is empty.
   The first solution is found on an 8MHz AT in 0.8 seconds as follows:

     p = (3,1,0),(5,4,3),(0,2,5),(6,3,1),(9,5,2),(11,7,4),(12,8,5),
         (1,4,8),(2,5,9),(14,9,5),(5,8,12),(13,12,11),(10,11,12),Nil

 vi) The predicate "Jumps" has an input/output argument "b" describing
   the states. It has the following declarative reading:

     Jumps(i,(b_in,b_out),p) holds iff the board b_out is obtained
     from the board b_in by performing i jumps given by the list p.

   The procedural reading is that given the number i and the state b
   the predicate will return the path p.

 vii) The reader will note that the arrays of Trilogy allow fast indexing
    as opposed to the list traversal of Prolog.