A.I. programming in Prolog and Assembler

September 20, 2007

Bridging gaps between Prologs (SWI-Prolog predicates implented in LPA Win-Prolog)

Filed under: Code Conversion, LPA Win-Prolog, Prolog, source code, SWI-Prolog — Omadeon @ 4:36 pm

Today I spent too much time trying to force a SWI-Prolog project (of timetable scheduling, custom-made for a specific company) to run in a different compiler: LPA Win-Prolog. I needed badly to use certain graphics routines and other goodies of LPA Prolog (a commercial compiler), entire volumes of them in fact. So, I ended up writing code in LPA Prolog that implements some quite common SWI-Prolog predicates. Here are some of them:

The SWI-Prolog predicate ‘between/3’ generates (non-deterministically) a number, ranging from a minimum value to a maximum Value (as ‘bound’ 1st and 2nd arguments). I.e., in the SWI-Prolog console:

?- between(1,3,X).
X = 1 ;
X = 2 ;
X = 3 ;

Well, here is an LPA Win-Prolog implementation of this predicate (also valid in any other ISO-compatible Prolog):

between(Min,Max,Out):- M2 is Min+1, M2 =< Max, between(M2,Max,Out).

OK, This was an easy example, while most probably the same code already exists in elementary Prolog textbooks. Here are some other (not-so-obvious) examples:

In LPA Prolog there are some very special, very efficient unique commands, like ‘find/3, which operates on ‘input streams’ to locate (sub-)strings inside them. Now, the so-called ‘input stream’ can itself (effectively) be just another string (turned into a stream through the special LPA command ‘<~’). The use of this predicate, ‘find/3’ to write quickly efficient code for non-deterministic search (of substrings inside larger strings) is a natural happy consequence. E.g.

findsubs(SubSTR,STR,Px):- len(SubSTR,Len), findrep(SubSTR,Len,Px) <~ STR.

findrep(_,Len,Px):- inpos(EndP), EndP > 0, Px is EndP-Len.
findrep(SubSTR,Len,Px):- find(SubSTR,0,Sx), +Sx=``, findrep(SubSTR,Len,Px). 

I wrote this code after understanding the (well-documented) similar non-deterministic predicate ‘replace’ (not a built-in command but given as simple source-code in LPA-Prolog’s Reference Quide, page 226). The reason I wrote it is because I needed it as a sub-predicate to implement of SWI-Prolog‘s superb predicate ‘sub_atom‘. (This was already used -alas in several places- inside the SWI-Prolog project, which was to be converted into LPA WIn-Prolοg).So, here is the resulting LPA-Prolog implementation of ‘sub_atom‘, valid for (almost) all possible flow-patterns (at least those used in my project, plus a few more):

(a description of sub_atom/5 from SWI-Prolog's Open Source documentation):
sub atom(+Atom, ?Before, ?Len, ?After, ?Sub)
    ISO predicate for breaking atoms. It maintains the following relation: Sub is a sub-atom of Atom
    that starts at Before, has Len characters and Atom contains After characters after the match.
?- sub_atom(abc, 1, 1, A, S).
 A = 1, S = b
   The implementation minimises non-determinism and creation of atoms. This is a very flexible
   predicate that can do search, prefix- and suffix-matching, etc.
% HERE is my LPA Win-Prolog (exact) implementation of 'sub_atom/5':
%%%%%%%%%% (also valid in most other ISO-ish Prologs) %%%%%%%%%%%%
% (i,i,i,o,o)
   nonvar(Atom), nonvar(Start), nonvar(Len), var(LenAfterX), var(SubX),
   cat(Lx,Atom,[Start,Len]), Lx = [_,SubX,End], len(End,LenAfterX).
% (i,o,i,i,o)
   nonvar(Atom), nonvar(Len), nonvar(LenAfter), var(Start), var(SubX),
   len(Atom,LenTotal), Start is LenTotal - LenAfter - Len,
   cat(Lx,Atom,[Start,Len]), Lx = [_,SubX,_].
% (i,o,o,o,i)  (effectively a non-deterministic search-function)
   nonvar(Atom), nonvar(Sub), var(SubLenx), var(LenAfterx), var(Startx),
   len(Sub,SubLenx),  atom_string(Atom,STR), atom_string(Sub,SubSTR), len(STR,Slen),
   findrep(SubSTR,SubLenx,Startx) <~ STR, LenAfterX is Slen-Startx-SubLenx.
% where 'findrep/3' was written previously as a part of 'findsubs' (top of this post).
   nonvar(Atom), nonvar(Start), var(Len), var(LenAfterX), var(SubX),
  cat(Lx,Atom,[Start]), Lx = [_,End], len(End,Len2),
  between(0,Len2,Lenx), cat(Lxx,End,[Lenx]),
  Lxx = [SubX,End2], len(End2,LenAfterX), Len=Lenx.
   nonvar(Atom), var(Start), var(Len), var(LenAfterX), var(SubX),
   len(Atom,Len1), between(0,Len1,Pos),
  cat(Lx,Atom,[Pos]), Lx = [_,End], len(End,Len2),
  between(0,Len2,Lenx), cat(Lxx,End,[Lenx]),
  Lxx = [SubX,End2], len(End2,LenAfterX), Len=Lenx, Start=Pos.
   nonvar(Atom), var(Start), nonvar(Len), var(LenAfterX), var(SubX),
   len(Atom,Len1), LenPre is Len1-Len, between(0,LenPre,Pos),
  cat(Lx,Atom,[Pos,Len]), Lx = [_,Mid,End],
  SubX = Mid, LenAfterX is Len1-Pos-Len, Start=Pos.

%%%%%%%%%% (end of code) %%%%%%%%

Well, that’s it, for the moment, I’m afraid.

I must go back to my project now, but (rest assured) I will be coming back here, soon, again and again, and again…

Blog at WordPress.com.