A.I. programming in Prolog and Assembler

May 8, 2009

Ultra-Fast Hybrid Genetic Algorithm in Assembly Language for the Travelling Salesman Problem (DLL for LPA Prolog)

UPDATE (8 Oct. 2009): new HD YouTube video about this project:

You can also watch a (slightly dated) slide-show about this algorithm here:


I am currently using this algorithm’s DLL inside a large-scale Scheduling Application for Multiple Tasks, in LPA WIN-Prolog. Some screen-shots from the program’s main window are shown in the following animated GIF:

O.G.T.S.P. Algorithm sample screen-shots

O.G.T.S.P. Algorithm sample screen-shots

Enhanced by Zemanta

July 20, 2008

Assembly Language for Visual Prolog Meta-programming

Visual Prolog Integrated...Image via Wikipedia
Back in 2005, while working in large-scale programming projects for data-mining in G.I.S. and Hydrology, I wrote a Prolog interpreter called G.I.S. Prolog, equipped with many extra predicates (such as functions to locate points inside polygons, etc).The G.I.S. Prolog interpreter was originally based on the “PIE interpreter” (included as free source-code in Visual Prolog) but it ended up enhanced with many extra predicates, as well as an improved core-level inference mechanism.
Ever since I started using the Visual Prolog compilers (and the PDC Prolog compilers preceding them) I was fascinated by the possibilities of implementing additional ISO-Prolog functionality in Visual Prolog through Assembly Language and ‘C’. Of course, such attempts are inherently limited by the internal design of Visual Prolog compilers. So, the only way to implement ISO-Prolog functionality in Visual Prolog is to extend the “PIE Interpreter” (and G.I.S. Prolog as its offspring). A multitude of extra predicates, implemented in pure Assembly language, became available through G.I.S. Prolog for easy immediate experimentation: Coding in G.I.S. Prolog produced immediate results, without any need for (often tedious) EXE-file compilation. Code modifications could therefore be done very quickly and most mistakes were (semi-)automatically corrected by the interpreter’s own enhanced error-checking capabilities.

Recently, I discovered some Assembly language techniques to enhance G.I.S. Prolog even further, potentially valuable for a multitude of other purposes. They also have an intrinsic fascination in themselves, as general tools for Prolog meta-programming.

E.g. here is an Assembly language predicate, that takes as inputs another (external) predicate’s memory-address and a (Visual Prolog-) argument-list, and calls this (external) predicate, using the (arbitrary-length-) list of N arguments, as arguments of “arity N”:

apply_func(PRED, [Arg,Arg2,…]) <=> PRED(Arg1,Arg2,…)

Now, in ISO-Prolog there is a standard predicate known as “univ”, written as “=..“, which turns a list like [PRED,ARG1,ARG2,ARG3…] into a predicate call such as PRED(ARG1,ARG2,…). However, this does not exist in Visual Prolog, which sacrifices such “luxuries” for speed (which is the reason I also often use ISO-Prolog compilers, such as LPA-WinProlog and SWI-Prolog).

Anyway… The code you are about to see can be useful more generally, as an example of Prolog meta-programming, implemented in Assembly Language. The only difference between the way it works for Visual Prolog and the way it might work for another Prolog (or -indeed- ANY programming language, using a ‘C’-calling convention) is the Visual-Prolog-specific structure of a LIST, which in Visual Prolog has a different form than in all other languages. If you understand Assembly Language and intend to use this code for other (meta-programming) tasks, all you have to do is modify just a couple of lines in the code that follows. However, before you (even begin to) look at the Assembly Language Code, the following simple definitions in Visual Prolog (5.*) are a prerequisite for easier understanding:

 	-(i,i,i) language c % <-- example domain
apply_func(DWORD,ListDomain) -(i,i) language c
% where arg-1 is a predicate-domain, such as "dom_iii"

After you compile the Assembly language code, you could create a simple “EasyWin” Visual Prolog project, with the following ines:

 % converts a predicate to a doubleword/address

 add3: dom_iii
func2dword(FUNC,DW):- DW = cast(dword,FUNC).

add3(_X,_Y,_Z,Out):- Out = _X+_Y+_Z,
 	write("out = ",Out), nl, !
 	write("error!\n"), Out=-1, !.
Out = apply_func(DW,[10,20,30]),
write("result = ",Out), nl, readchar(_).

%This program should produce "result = 60" (sum of [10,20,30]).

OK, so here is the Assembly language code:

; ==================== _apply_func.asm =====================
; Code for TASM 5 Assembler, command-line call for compilation:
; C:\TASM\BIN\TASM32.EXE /p /z /w2 /m2 /ml _apply_func.asm
MODEL    flat
public _apply_func    ; (i,i)
PROC _apply_func near
ARG    func:dword, list:dword
LOCAL    fcnt:dword
push    esi        ;
push    edi        ;
push    ebx        ;
push    ecx        ;
mov    ecx,[func]  ; function............ ARG 1
mov    esi,[list]  ; list................ ARG 2
xor    ebx,ebx     ; make EBX=0
mov    [fcnt],ebx  ; initialize local variable 'fcnt' to 0
lodsd              ; load the 1st list-element's "element-flag"
dec    al          ; decrement it, to check if it was a 1
jnz short @@x1     ; exit if not (i.e. if it's the list's end)
; ----------------- else...
@@L1:             ; loop to read the (Visual-Prolog-) arg-list
inc    ebx        ; increment ebx (counter for number_of_args)
lodsd             ; load next list-element (arg. of function)
push    eax       ; push it into the stack (for a function-call)
lodsd             ; load the pointer to next list-element in EAX
mov    esi,eax    ; now ESI = (pointer-to-) next list-element
lodsd             ; load element-flag of next list-element
dec    al         ; decrement it, to check if it was a 1
jz short @@L1     ; if so, not yet the list's end, so repeat!
; ================= else...
mov    [fcnt],ebx  ; store the number_of_args in local var. 'fcnt'
call   ecx         ; call the (external) function (given in ARG-1)
mov    ecx,[fcnt]  ; get the function's number of args from 'fcnt'
jcxz @@x2          ; if the called function had NO args, exit
; ------------------ else...
@@L3:              ; loop to POP function-args after the call
pop        edx     ; recover next argument from the stack
dec        ecx     ; decrement the remaining number_of_args
jnz short @@L3     ; if not zeroed, continue popping args...
; ------------------
pop        ecx     ;
pop        ebx     ;
pop        edi     ;
pop        esi     ;
ENDP _apply_func


  • A not-so-obvious advantage of this code is that any Prolog interpeters written on the basis of Visual Prolog’s “PIE engine” (such as G.I.S. Prolog) make extensive use of calls such as this, inside their inference engine; using Prolog-lists of arguments to be called by turning them into proper predicate calls of arity=N (where N is the size of the list). So, an Assembly language implementation of such a calling mechanism can speed up such an interpreter considerably, especially inside recursive calls or loops, which call other predicates repeatedly countless times…
  • Another not-so-obvious advantage is that -in this way- we managed to… trick Visual Prolog into doing “forbidden” predicate calls, such as PRED(arg1,arg2,….), where both the predicate’s functor and the arguments may appear as static data, stored in a Visual Prolog facts’ database.
  • Don’t ask me (yet) how to implement such tricks in Visual Prolog 6.* or 7.*; I still use the version 5.* compilers a lot, because of their speed, as well as robustness in foreign language calls.
Zemanta Pixie

September 21, 2007

Reading EXCEL CSV-files as Prolog Clauses (SWI-Prolog source-code)

stylized depiction of a csv text file
Image via Wikipedia

If you need to convert into Prolog terms “raw data” supplied in EXCEL csv-files, read on! The source code in this posting will read any CSV file, converting each semicolon-delimited line (or record) of the CSV file into a Prolog clause, asserted in RAM. It is also possible to use the same code to read data deliberately provided (e.g. by another application) as a CSV-file, but which is specifically intended for use as a set of Prolog clauses.

This code also uses a couple of specification predicates: time_field_type/1, field1_as_functor/1, and conv_csvhead/2. These predicates control the behaviour of the conversion process, as follows:

time_field_type/1 :

  • time_field_type(0). In this case, time-fields in the CSV file (of the form “HH:MM” or “HH:MM:SS…”) are translated into minutes, ignoring seconds or hundredths of a second.
  • time_field_type(1). In this case, time-fields in the CSV file (of the form “HH:MM” or “HH:MM:SS…”) are translated into seconds, ignoring hundredths of a second.
  • time_field_type(2). In this case, time-fields in the CSV file are kept as they are, as atoms (e.g. ’03:35′, ’12:45:20′, etc).


  • field1_as_functor(0): Each line in the CSV-file is interpreted as a prolog clause, where the functor of the clause is the first field of the record, and the other fields are arguments.
  • field1_as_functor(foo) (where ‘foo’ can be any atom): Each line in the CSV file is interpreted as a prolog clause, where the functor of the clause is foo (or any atom supplied as 1st argument to field1_as_functor/1) and all the fields are arguments.


  • This predicate is used to convert the contents of the first field (of the CSV-file) into a (user-defined) internal Prolog representation. It is used only if “time_field_type(0)” exists. For example, to convert records where the first field is a Prolog functor ‘job’ but the actual contents of this field are ‘j’ (for brevvity), using a definition “conv_csvhead(j,job)” will convert each ‘j’ into a functor ‘job’. (Use of conv_csvhead/2 is optional; in the default case, it does nothing!)

Finally, some notes:

  • The main predicate to call is “loaddb(CSVfile)“, where CSVfile can be e.g. “test.csv”.
  • Provision has been taken for special fields which contain Lists of items, comma-delimited. In EXCEL these fields will appear as longish strings, but this code was written to parse them as Prolog atom-lists. (Comment-out this section if you don’t need it).
  • The only type of field that is currently not converted into any meaningful internal representation is DATE. Dates are converted to atoms, just as they appear, without parsing their actual contents. (As an exercise, you can re-use parts of the same code to parse date-fields!) The honest reason for this omission is that… I didn’t need dates (in an application I am developing, for which this code was also written).

The source-code follows. There are useful comments inside this code. You can just copy and paste what follows from this point onwards, into a text file saved for compilation by SWI-Prolog, ending in “.pl”: (more…)

Blog at WordPress.com.