Deductive database (datalog)

Post your FreeBASIC tips and tricks here. Please don’t post your code without including an explanation.
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Deductive database (datalog)

Postby AGS » Nov 20, 2014 7:22

Datalog is a language used to create/query a deductive database. A deductive database consists of facts and rules (rules are based on facts).
An example of a couple of facts.

Code: Select all

programmer(carl).
programmer(john).
programmer(linus).


A fact can contain a list of terms enclosed between parens (much like a parameter list). Lets add the programming abilty of programmers to the programmer facts.

Code: Select all

programmer(carl,good).
programmer(john,average).
programmer(linus,excellent).


If you'd want to get all the names of all programmers and their ability you could query the database like so.

Code: Select all

programmer(X,Y)?


Answers.

Code: Select all

programmer(john,average)
programmer(linus,excellent)
programmer(carl,good)


X and Y are called variables. Variables start with an uppercase letter and continue with any character that is not one of ‘(’, ‘,’, ‘)’, ‘=’, ‘:’, ‘.’, ‘~’, ‘?’, ‘"’ or ‘%’. Or: stick with fb-style identifiers when naming a variable and you can't go wrong.
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)


You can use a freebasic string as input for dl_loadbuffer. Using strptr on the string will get you the zstring pointer needed by dl_loadbuffer.

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
Roland Chastain
Posts: 948
Joined: Nov 24, 2011 19:49
Location: France
Contact:

Re: Deductive database (datalog)

Postby Roland Chastain » Nov 20, 2014 11:37

Hello AGS!

Very interesting. I got "undefined reference" errors until I removed the old liblua.a file which was in my lib/win32 directory.

But after I replaced it with your file, I could no longer compile the code examples of this tutorial.
anonymous1337
Posts: 5494
Joined: Sep 12, 2005 20:06
Location: California

Re: Deductive database (datalog)

Postby anonymous1337 » Nov 20, 2014 18:41

AGS,

Seems very interesting. Would you mind posting the expected output of the application in a code block for me to drool at?
AGS
Posts: 1284
Joined: Sep 25, 2007 0:26
Location: the Netherlands

Re: Deductive database (datalog)

Postby AGS » Nov 24, 2014 19:15

It is always a gamble when you put an example on the forum that has dependencies beyond what's in the fb distribution. Sometimes the example works and sometimes it doesn't.

@anonymous1337
Output to drool at :) Output should look something like this

Code: Select all

high level interface example

number of answers = 2
name of the predicate: excellent
length of predicate name: 9
arity of predicate: 1
answers:
The name of excellent programmer number  1 is ben
The name of excellent programmer number  2 is linus
number of answers = 21
name of the predicate: path
length of predicate name: 4
arity of predicate: 2
answers:
path(e,g)
path(c,d)
path(a,d)
path(b,f)
path(b,d)
path(a,g)
path(b,g)
path(c,f)
path(d,e)
path(b,e)
path(b,c)
path(c,e)
path(a,e)
path(e,f)
path(f,g)
path(c,g)
path(d,g)
path(a,c)
path(d,f)
path(a,b)
path(a,f)

low level interface example

number of answers = 2
name of the predicate: excellent
length of predicate name: 9
arity of predicate: 1
answers:
The name of excellent programmer number  1 is ben
The name of excellent programmer number  2 is linus


There is a better/faster implementation of datalog that can also be used in combination with FreeBASIC.
It's called xsb http://xsb.sourceforge.net/ and it's still under active development.

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 9 guests