Playing Prolog

Richard Suchenwirth 2000-12-04 -- Job requirements have reawakened my interest in Prolog, while I still love, and work with, Tcl. Reading Richard A. O'Keefe's The Craft of Prolog, of course I kept comparisons to Tcl in mind. I agree at once that most Prolog features like implicit backtracking are not Tcl's cup of tea, but some, like unification, can at least be emulated. Take O'Keefe's very first example (p.7), where he maps directions (north, east, south, west) to scholarly Latinized adjectives -- or the other way -- or checks map compliance, all in four lines:

 direction_adjective(north, boreal).
 direction_adjective(south, austral).
 direction_adjective(east, oriental).
 direction_adjective(west, occidental).

You can call this in Prolog with an unbound direction


to (temporarily) assign "south" to the variable D (variable names have to start with uppercase in Prolog), or the other way round


to get "oriental" in A, check a match or a partial match (by giving the don't care variable "_"), and get truth values in return, e.g.

  direction_adjective(west, occidental) => true
  direction_adjective(_, boreal) => true
  direction_adjective(foo, _) => false %% (no such direction!)

Pretty much power for four lines declaring a relation ;-) It's hardly conceivable how to reproduce this behavior in C(++)?, but with some slightly more effort (eight lines) we can do it in Tcl:

 % proc direction_adjective {dir adj} {
    set d_a {north boreal south austral west occidental east oriental}
    if {[set i [lsearch $d_a $adj]]>=0 && [regexp {^[A-Z_]} $dir]} {
                uplevel set $dir [lindex $d_a [incr i -1]]
    } elseif {[set j [lsearch $d_a $dir]]>=0 && [regexp {^[A-Z_]} $adj]} {
                uplevel set $adj [lindex $d_a [incr j]]
    } elseif {$j==$i-1} {return 1 } else {return 0}

Now for the testing:

 % direction_adjective D boreal
 % set D
 % direction_adjective west A
 % set A
 % direction_adjective north _
 % direction_adjective _ austral
 % direction_adjective south austral
 % direction_adjective west austral
 % direction_adjective _ _

The last example comes out different from Prolog, but even there it's pretty nonsensical, basically just asking: "Do you have direction_adjective/2 at all?", and Smart Programmers Are Required to Know ;-) so I didn't bother to treat this special case. Neither did I care to always return truth values (other return values in Prolog happen only in the arguments), and _ is always the same variable (having "south" in the final example).

Tcl's Not Prolog, agreed, but it's still a mighty powerful, and extremely versatile language, as seen in this trivial example. In Prolog you can do logical surfing up and down your code, while in Tcl you can surf between upvar names, strings, lists, integers... what have you. Some people hate this "shimmering", and it may cost performance. But CPUs are getting ever so fast, and the runtime won often doesn't compensate for the coding time lost, so my wish is Tcl stays that way, possibly gaining new power, but never give up the old!

Final note: the given proc is mostly generic except for the data specified in the second line. By pulling that out into an argument, we'd have a general 2-arg relation handler - if people were happy with upcase-starting variable names...(i myself avoid the Shift key too ;-)

Another Prolog feature is that the same predicate name can be implemented several times, with different "arities" (numbers of arguments). Here's how to do this in Tcl, even mimicking the Prolog habit of appending arity, with a slash, to the predicate name:

 proc foo args {eval foo/[llength $args] $args } ;# the wrapper
 proc foo/1 {x} {puts "only one, thats $x"}
 proc foo/2 {x y} {puts "got $x and $y"}
 proc foo/3 {x y z} {puts "called me with $x, $y, and $z"}

Instead of the puts you'd insert real work code. Now testing:

 % foo
 invalid command name "foo/0"
 % foo what
 only one, thats what
 % foo what else
 got what and else
 % foo what else again
 called me with what, else, and again
 % foo what else again then
 invalid command name "foo/4"

We notice that arity is expressed two times, both in number and the arg list, so instead of writing "proc foo/N" we can compute N like this:

 proc predicate {name argl body} {
        proc $name/[llength $argl] $argl $body
 % predicate foo {x y} {puts "got $x and $y"}
 % predicate foo {a b c d} {puts "take $a and $b and $c and $d!"}

But what we cannot do (so easily ;-) is several declarations of a predicate with same arity, which will be tried in the given order until one succeeds, and backtrack else, except if cut, and..

Parsing lists: In Prolog, you can specify patterns like [H|T] to split up a list into its first element H and the rest (T). This can extend over several comma-separated elements: [First,Second,Third|Rest] assign the 1st element to variable First, 2nd to Second, 3rd to Third, 4th through last to Rest. Here's a Tcl proc that emulates that behavior partly (not usable in proc arglists or conversely for building lists from parts; no brackets - they are used often enough in Tcl, but you may brace your patterns):

 proc lparse {pattern list} {
   # assigns variables to parts of a list
   set restvar ""
   regexp {([^|]+)([|](.+))?} $pattern -> singlevars - restvar
   set index 0
   foreach i [split $singlevars ,] {
      upvar 1 $i name
      if {$index && $index>[llength $list]-1} {error "list too short"}
      set name [lindex $list $index]
      incr index
   if [string length $restvar] {
        if {$index>[llength $list]-1} {error "list too short"}
        upvar 1 $restvar name
        set name [lrange $list $index end]
   } elseif {$index<=[llength $list]-1} {error "list too long"}


 lparse {H1,H2|T} {a b c d e f g} ;#=> H1=a, H2=b, T={c d e f g}

Error handling was added so you can measure the success of parsing in a catch. I tried to model the behavior that [H] matches an empty list, but [H|T] doesn't match a one-element list - so the tail must not be empty(?).

NEM: This type of structural pattern-matching is often associated with Algebraic Types (as used in Haskell, ML etc). Monadic TOOT also has a small implementation. At the heart of Prolog is a unification pattern matcher -- see a little database with unification.

Playing predicate logic shows how to emulate predicates with generated procs, whose bodies are rewritten by assertions (Horn clauses) - but without backtracking (yet)...

Solving cryptarithms shows one trick that can be used to express a backtracking search compactly in Tcl.