An example of a couple of facts.
Code: Select all
programmer(carl).
programmer(john).
programmer(linus).
Code: Select all
programmer(carl,good).
programmer(john,average).
programmer(linus,excellent).
Code: Select all
programmer(X,Y)?
Code: Select all
programmer(john,average)
programmer(linus,excellent)
programmer(carl,good)
john, linus, carl etc... are examples of constants (identifiers that start with a lowercase letter, strings are allowed as well).
The result of a query consists of facts (or rather predicates) with variables replaced with constants (strings).
To use datalog you'll need two libraries: the datalog library and the lua libary. I have created a package containing both libraries.
You can download the package from here http://www.sarmardar.nl/FreeBASIC/datalog.rar
Link to datalog library website: http://datalog.sourceforge.net/
Datalog user manual: http://www.ccs.neu.edu/home/ramsdell/to ... talog.html
The datalog library has two types of interfaces: a low level one and a high level one.
The low - level interface requires you to communicate with the datalog library as you would with lua. Which is by means of pushing things on a stack and popping things from a stack explicitly. The high level interface is a lot easier to use. This example shows how to use both high level
and low level interface. The example given for the low level interface creates exactly the same database as the first example that uses the high level interface.
The high level interface consists of
--> functions to create- and initialize a database;
--> functions to add facts and rules to the database by means of a character buffer or a file;
--> a function to query the database;
--> functions to interpret query - answers.
Adding facts and rules is done by a call to dl_loadbuffer. This function expects a string that contains a datalog program. Facts and rules should end with a period, whitespace is insignificant.
If a datalog program ends with a query then that query will be put on the stack. You can execute that query by calling dl_ask(database,answer). If the datalog program loaded did not end with a question then there will be a query on top of the stack regardless. This query can be removed by using
Code: Select all
dl_pop(database)
A query returns a pointer to a variable of type dl_answers_t ptr. That variable can be used to gain access to the answers returned in response to a query.
The writers of the datalog library did not include a function that returns the number of answers returned by a query. I added such a function to the datalog package myself (it is called dl_getanswers). You can use it to process the answers one at a time. If there were are any answers iteration should go from 0 to the number of answers - 1. If there were no answers then there is nothing to iterate.
Given a dl_answers_t you can get the following info concerning the answers returned as result of a query
--> the number of answers (returns 0 if there are none);
--> the name and the length of the predicate returned (this predicate is shared by all answers);
--> term j of answer i (both length of the term and it's content which is a zstring pointer).
The example shows how to use the high level interface and how to create a query/execute a query/get the different answers associated with a query. The first example is a straightforward one.
The second example involves the use of a rule that utilizes recursion. Given a graph (format: a list of edges) it computes the transitive closure of the graph.
Answers in datalog have no particular ordering (answers are returned in random order).
Some concluding remarks. It is important to make sure that both libdatalog.a and liblua.a can be found by the compiler otherwise
compilation of the example will fail. liblua.a is a static library version of lua version 5.2
Code: Select all
#ifndef DATALOG_BI
#define DATALOG_BI
#inclib "datalog"
#inclib "lua"
#include once "crt/stddef.bi" ''size_t is defined in stddef.bi
#include once "crt/stdio.bi" ''FILE is defined in stdio.bi
extern "C"
/' The object manipulated by functions in the API. '/
type dl_db_t as any ptr
/' A list of answers--the structure returned by dl_ask. '/
type dl_answers_t as any ptr
/' Create a Datalog database. '/
declare function dl_open() as dl_db_t
/' Initialize a database. Used when a database structure exists that
lacks Datalog specific initializations. This initialization is one
of the actions performed by dl_open. '/
declare function dl_init(byval db as dl_db_t) as integer
/' Dispose a database and all its associated resources. '/
declare sub dl_close(byval db as dl_db_t)
/' Return package name and version information. '/
declare function dl_version() as const zstring ptr
/' There are two ways to build literals and clauses, and assert and
retract clauses. The low-level interface builds items by pushing
each of its component on a stack, and then inserting it into the
result. Using this interface requires great care.
If space permits, consider using the high-level, Datalog program
loader provided by function dl_load. It is implemented on top of
the low-level interface. The high-level interface is described in
the Datalog User Manual. '/
/' The remaining int returning functions in this interface return zero
on success, unless othewise noted. The maximum size of the stack
manipulated by the functions is four, but implementations may
provide a larger stack. '/
/' Strings '/
/' Push a string on the top of the stack. The string may contain
zeros. '/
declare function dl_pushlstring(_
byval db as dl_db_t,_
byval s as const zstring ptr,_
byval n as size_t) as integer
/' Push a string on the top of the stack. The string must be zero
terminated. '/
declare function dl_pushstring(_
byval db as dl_db_t,_
byval s as const zstring ptr) as integer
/' Concatenate two strings. Pops two strings off the top of the stack
and then pushes the concatenation of the two strings on the top of
the stack. '/
declare function dl_concat(byval db as dl_db_t) as integer
/' Literals '/
/' Starts a literal. Pushes an incompleted literal on the top of the
stack. '/
declare function dl_pushliteral(byval db as dl_db_t) as integer
/' Predicate Symbols '/
/' Make a string and then use this to add a predicate symbol to a
literal. Pops the string from stack. For each literal, this must
be done once, and can be done after some number of terms have been
added. '/
declare function dl_addpred(byval db as dl_db_t) as integer
/' Terms '/
/' Make a string and then use this to add a variable to the list of
terms of a literal. Pops the string from stack. '/
declare function dl_addvar(byval db as dl_db_t) as integer
/' Make a string and then use this to add a constant to the list of
terms of a literal. Pops the string from stack. '/
declare function dl_addconst(byval db as dl_db_t) as integer
/' Finish making a literal after adding all terms and one predicate
symbol. Leaves a completed literal on the top of the stack. '/
declare function dl_makeliteral(byval db as dl_db_t) as integer
/' Clauses '/
/' Make a literal and then use this to start a clause. Pops a
literal from the stack and leaves a newly created, incomplete
clause on top of the stack. The head of the clause is the
literal. '/
declare function dl_pushhead(byval db as dl_db_t) as integer
/' Make a literal and then use this to add it to the clause's body.
Pops a literal from the stack, and inserts it into the incomplete
clause on the top of the stack. '/
declare function dl_addliteral(byval db as dl_db_t) as integer
/' Finish the clause. Leaves a completed clause on the top of the
stack. '/
declare function dl_makeclause(byval db as dl_db_t) as integer
/' Actions '/
/' Asserts the clause on the top of the stack. The clause is added to
the database and popped off the stack. Returns -1 when a clause is
not safe. '/
declare function dl_assert(byval db as dl_db_t) as integer
/' Retracts the clause on the top of the stack. The clause is removed
from the database and popped off the stack. '/
declare function dl_retract(byval db as dl_db_t) as integer
/' Computes a list that contains all ground instances of a literal
that are a logical consequence of the clauses stored in the
database. Pops the literal from the stack and returns a freshly
allocated list of answers via the a paramater, or the null pointer
when there are errors or no answers. '/
declare function dl_ask(_
byval db as dl_db_t,_
byval a as dl_answers_t ptr) as integer
/' Frees the space associated with a list of answers. '/
declare sub dl_free(byval a as dl_answers_t)
/' Answers '/
/' Gets the number of answers '/
declare function dl_getanswers(byval a as dl_answers_t) as size_t
/' Gets the predicate associated with the answers. If the length of
the predicate is n, n + 1 character locations are returned, and the
last location is zero. Other character locations in the predicate
may be zero. This function returns the null pointer if given
it. '/
declare function dl_getpred(byval a as dl_answers_t) as zstring ptr
/' Gets the length of the predicate associated with the answers.
Returns zero if given the null pointer. '/
declare function dl_getpredlen(byval a as dl_answers_t) as size_t
/' Gets the arity of the predicate associated with the answers.
Returns zero if given the null pointer. '/
declare function dl_getpredarity(byval a as dl_answers_t) as size_t
/' Gets the constant associated with term j in answer i. Zero-based
indexing is used throughout. If the length of the constant is n,
n + 1 character locations are returned, and the last location is
zero. Other character locations in the constant may be zero. If
there is no specified term or no answers at all, the null pointer
is returned. '/
declare function dl_getconst(_
byval a as dl_answers_t,_
byval i as integer,_
byval j as integer) as zstring ptr
/' Gets the length of the constant associated term j in answer i. the
jth term. Zero-based indexing is used throughout. If there is no
jth term in the ith answer, or no answers at all, zero is
returned. '/
declare function dl_getconstlen(_
byval a as dl_answers_t,_
byval i as integer,_
byval j as integer) as size_t
/' Pop an item from the stack. '/
declare function dl_pop(byval db as dl_db_t) as integer
/' Returns the height of the stack. For this function, the return
value does not indicate success or failure. '/
declare function dl_mark(byval db as dl_db_t) as integer
/' Resets the height of the stack to a value returned by dl_mark. '/
declare function dl_reset(_
byval db as dl_db_t,_
byval m as integer) as integer
/' Datalog loader using a Prolog-like syntax. '/
/' A reader used to supply buffers to the loader. When called by the
loader, the reader is given the data supplied to the loader as its
first argument. If there is no more input available, the reader
returns a null pointer, otherwise it assigns the size of the buffer
to the size parameter, and then returns a pointer to the buffer. '/
type dl_reader_t as function cdecl(byval data_ as any ptr, byval size as size_t ptr) as zstring ptr
/' A function used to report errors generated by the loader. When a
loader error occurs, this function is called with the data supplied
to the loader, the location of the error as a line number and
column number, and an error message. '/
type dl_loaderror_t as sub cdecl (byval data_ as any ptr, byval lineno as integer, byval colno as integer,_
byval msg as const zstring ptr)
/' A loader for Datalog programs. It uses a reader to obtain a
sequence of buffers that contain the program. The load error
reporter is invoked when the loader detects an error, and then a
non-zero value is returned. '/
declare function dl_load(_
byval database as dl_db_t,_
byval reader as dl_reader_t,_
byval loaderror as dl_loaderror_t,_
byval data as any ptr) as integer
/' A loader for a program contained in a single buffer. '/
declare function dl_loadbuffer(_
byval database as dl_db_t,_
byval buffer as const zstring ptr,_
byval size as size_t,_
byval loaderror as dl_loaderror_t) as integer
/' Support for printing using the loader's syntax for constants. '/
/' Print a constant of a given length. The function assumes the
constant has n + 1 character locations, and the last location is
zero. Other character locations in the constant may be zero. '/
declare sub dl_putlconst(_
byval out as FILE ptr,_
byval s as const zstring ptr,_
byval n as size_t)
/' Print a zero terminated constant. '/
declare sub dl_putconst(_
byval out as FILE ptr,_
byval s as const zstring ptr)
/' Determine the columns needed for a constant with a given length.
The function assumes the constant has n + 1 character locations,
and the last location is zero. Other character locations in the
constant may be zero. '/
declare function dl_widthoflconst(_
byval s as const zstring ptr,_
byval n as size_t) as size_t
/' Determine the columns needed for a zero terminated constant. '/
declare function dl_widthofconst(byval s as const zstring ptr) as size_t
end extern
#endif
sub load_error cdecl (byval data_ as any ptr, byval lineno as integer,_
byval colno as integer,byval msg as const zstring ptr)
if msg <> 0 then
print *msg
end if
print "col";colno
print "line";lineno
return
end sub
sub mymain()
''high level interface examples
''create a database
var database = dl_open()
if (database = 0) then
print "datalog could not create database"
return
end if
dl_init(database)
dim buffer as string = _
"programmer(john,lousy)."_
"programmer(ben,excellent)."_
"programmer(carl,average)."_
"programmer(linus,excellent)."_
"excellent(X) :- programmer(X,excellent)."_
"excellent(X)?"
var error_ = dl_loadbuffer(database,strptr(buffer),len(buffer),@load_error)
if error_ then
print "datalog load problem"
dl_close(database)
return
end if
''query should be on top of stack
dim answers as dl_answers_t
var ask_error = dl_ask(database,@answers)
if (ask_error <> 0 ) then
print "datalog query problem"
dl_close(database)
end if
print "high level interface example"
print
var num_answers = dl_getanswers(answers)
if (num_answers) then print "number of answers = ";num_answers
var predname = dl_getpred(answers)
var predlen = dl_getpredlen(answers)
var predarity = dl_getpredarity(answers)
if len(predname) <> 0 then print "name of the predicate: ";*predname
if predlen <> 0 then print "length of predicate name: ";predlen
if predarity <> 0 then print "arity of predicate: ";predarity
print "answers:"
for i as integer = 0 to num_answers - 1
for j as integer = 0 to predarity - 1
var termlen = dl_getconstlen(answers,i,j)
var termtext = dl_getconst(answers,i,j)
print "The name of excellent programmer number ";i+1;" is ";*termtext
next j
next i
dl_free(answers)
dl_close(database)
buffer = _
"edge(a,b)."_
"edge(b,c)."_
"edge(c,d)."_
"edge(d,e)."_
"edge(e,f)."_
"edge(f,g)."_
"path(A,B) :- edge(A,B)."_
"path(A,B) :- path(A,C),path(C,B)."_
"path(A,B)?"
''add to database
database = dl_open()
if (database = 0) then
print "datalog could not create database"
return
end if
dl_init(database)
error_ = dl_loadbuffer(database,strptr(buffer),len(buffer),@load_error)
if error_ then
print "datalog load probem"
dl_close(database)
return
end if
ask_error = dl_ask(database,@answers)
''error in ask->assume there is a problem with datalog
if (ask_error <> 0) then
print "datalog query problem"
dl_close(database)
return
end if
num_answers = dl_getanswers(answers)
predname = dl_getpred(answers)
predlen = dl_getpredlen(answers)
predarity = dl_getpredarity(answers)
if num_answers then print "number of answers = ";num_answers
if len(predname) <> 0 then print "name of the predicate: ";*predname
if predlen <> 0 then print "length of predicate name: ";predlen
if predarity <> 0 then print "arity of predicate: ";predarity
print "answers:"
for i as integer = 0 to num_answers - 1
for j as integer = 0 to predarity - 1
var termlen = dl_getconstlen(answers,i,j)
var termtext = dl_getconst(answers,i,j)
if j = 0 then
print "path(";*termtext;",";
else
print *termtext;")"
end if
next j
next i
dl_free(answers)
dl_close(database)
''low level interface example (creates same database as created in first high level example)
dim programmers(0 to 7) as zstring ptr => _
{_
@"john",@"lousy",_
@"ben",@"excellent",_
@"carl",@"average",_
@"linus",@"excellent" _
}
''create database
database = dl_open()
if (database = 0) then
print "datalog could not create database"
return
end if
dl_init(database)
''create facts programmer(name,skills)
''no error handling (assuming all will go well?)
dim err_ as integer
for i as integer = 0 to 7 step 2
err_ = dl_pushliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"programmer")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addpred(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,programmers(i))
if err_ = 1 then
goto error_handler
end if
err_ = dl_addconst(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,programmers(i+1))
if err_ = 1 then
goto error_handler
end if
err_ = dl_addconst(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_makeliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushhead(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_makeclause(database)
if err_ = 1 then
goto error_handler
end if
''dl_assert adds a clause to the database
err_ = dl_assert(database)
if err_ = 1 then
goto error_handler
end if
next i
''create excellent(X) :- programmer(X,excellent)
''create left hand side => excellent(X) :-
err_ = dl_pushliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"excellent")
if err_ then
goto error_handler
end if
err_ = dl_addpred(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"X")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addvar(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_makeliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushhead(database)
if err_ = 1 then
goto error_handler
end if
''create right hand side => programmer(X,excellent)
err_ = dl_pushliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"programmer")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addpred(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"X")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addvar(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"excellent")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addconst(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_makeliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_addliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_makeclause(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_assert(database)
if err_ = 1 then
goto error_handler
end if
''create the query
err_ = dl_pushliteral(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"excellent")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addpred(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_pushstring(database,@"X")
if err_ = 1 then
goto error_handler
end if
err_ = dl_addvar(database)
if err_ = 1 then
goto error_handler
end if
err_ = dl_makeliteral(database)
if err_ = 1 then
goto error_handler
end if
''the rest is the same as in the high level example: query is on top of stack and dl_ask will pop it
''query should be on top of stack
ask_error = dl_ask(database,@answers)
if (ask_error <> 0 ) then
print "datalog query problem"
dl_close(database)
end if
print
print "low level interface example"
print
num_answers = dl_getanswers(answers)
if (num_answers) then print "number of answers = ";num_answers
predname = dl_getpred(answers)
predlen = dl_getpredlen(answers)
predarity = dl_getpredarity(answers)
if len(predname) <> 0 then print "name of the predicate: ";*predname
if predlen <> 0 then print "length of predicate name: ";predlen
if predarity <> 0 then print "arity of predicate: ";predarity
print "answers:"
for i as integer = 0 to num_answers - 1
for j as integer = 0 to predarity - 1
var termlen = dl_getconstlen(answers,i,j)
var termtext = dl_getconst(answers,i,j)
print "The name of excellent programmer number ";i+1;" is ";*termtext
next j
next i
dl_free(answers)
dl_close(database)
return
error_handler:
print "problem while using low level interface"
dl_close(database)
return
end sub
mymain