interpreter structure

[Philipp Kraus]

Hello,

I need some help, because I would like to implementate a Prolog interpreter in Lua, because for some scriptable structures.

I have found http://yieldprolog.sourceforge.net/ which implements Prolog in JS. I have worked with Prolog, but at the moment

I need some help for the interpreter structure. I don't want to use a builded interpreter, because my datasets are small

but I have a lot of changes in the database. 

I know Prolog uses backtracking to create the answer, but at the moment I haven't got any idea to create it in Lua.

Hope for some tips to create the idea.

Thanks a lot

Phil

[Jan Burse]

Hi,

Philipp Kraus schrieb:

> I know Prolog uses backtracking to create the answer, but at the moment
> I haven't got any idea to create it in Lua.

Maybe check out picoProlog:
http://spivey.oriel.ox.ac.uk/corner/Logic_Programming

"The book gives a simple introduction to the theory of
logic programming, and also describes in detail an
implementation of a small Prolog dialect called
picoProlog by an interpreter written in Pascal."

e-book and source code can be found at the link above.

Bye

P.S.: But somehow it doesn't understand
the usual facts syntax:

/* flights.pp */

flight(london, paris) :- .
flight(london, dublin) :- .
flight(paris, berlin) :- .
flight(paris, rome) :- .
flight(berlin, london) :- .

journey(A, A) :- .
journey(A, C) :- flight(A, B), journey(B, C).

But you might be able to fix that by yourself.

[Philipp Kraus]

Thanks for this answer, that helps a lot for understanding.
Do you know a Prolog interpreter, that is only based on a DLL which can
be used on Linux, OSX and Windows?

For a short view to my problem: I have got Lua objects, each object
stores two databases, in each database I will
implementate a Prolog program for planning structure / expert systems.
So the Prolog script must be run in the local
object context. I have a lot of modification on the Prolog database, so
many retract calls, but my database are very
small.

So my first idea is: Implement a own Prolog interpreter in native lua
or my second idea is: Use a general Prolog interpreter in a DLL with a
C/C++ interface and create only wrapper structures
for Lua.

I need on the Prolog-side only the default buildins no additional
packages. I have worked only with SWI-Prolog but I don't
know a only DLL-based Prolog component.

Thanks

Phil

[Jan Burse]

Philipp Kraus schrieb:

> Thanks for this answer, that helps a lot for understanding.
> Do you know a Prolog interpreter, that is only based on a DLL which can
> be used on Linux, OSX and Windows?

A list of Prolog systems is given here:
https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations

But I don't think DLLs work on Linux and MacOSX,
in case this refers to the Microsoft's implementation
of the shared library concept.

Bye

P.S.: If you allow .jar's as your shared libraries
you find also a couple of Prolog systems here:
https://en.wikipedia.org/wiki/List_of_JVM_languages
(See Prolog section)

[Jan Burse]

Jan Burse schrieb:

> P.S.: If you allow .jar's as your shared libraries
> you find also a couple of Prolog systems here:
> https://en.wikipedia.org/wiki/List_of_JVM_languages
> (See Prolog section)

You could combine it with LuaJ.
http://sourceforge.net/projects/luaj/

And even run it on Android.

[Philipp Kraus]

On 2013-08-29 09:06:05 +0000, Jan Burse said:

> Philipp Kraus schrieb:
>> Thanks for this answer, that helps a lot for understanding.
>> Do you know a Prolog interpreter, that is only based on a DLL which can
>> be used on Linux, OSX and Windows?
>
> A list of Prolog systems is given here:
> https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations
>
> But I don't think DLLs work on Linux and MacOSX,
> in case this refers to the Microsoft's implementation
> of the shared library concept.

DLL is the name of "dynamic link library", under Linux there exists
*.so files and under OSX *.dylib
(Windows *.dll) but it is equal. DLL is general.

[Philipp Kraus]

I don't have installed any Java JRE. I have only a C, C++ and Fortran compiler.
So I can create a native Lua implementation only or I can use a DLL
with a C / C++
interface, so I can write a Lua wrapper (Lua interpreter is written in
native C)

Phil

[Jan Burse]

Philipp Kraus schrieb:

>> But I don't think DLLs work on Linux and MacOSX,
>> in case this refers to the Microsoft's implementation
>> of the shared library concept.
>
> DLL is the name of "dynamic link library", under Linux there exists *.so
> files and under OSX *.dylib
> (Windows *.dll) but it is equal. DLL is general.

Most of the Prolog systems, especially those written in C,
come with a C foreign function interface. But I guess there
is no standard.

GNU-Prolog: Calling Prolog from C
http://www.gprolog.org/manual/html_node/gprolog065.html

SWI-Prolog: Calling Prolog from C
http://www.swi-prolog.org/pldoc/doc_for?object=section%283,%279.4.9%27,swi%28%27/doc/Manual/foreigninclude.html%27%29%29

YAP: Using YAP as a Library
http://www.dcc.fc.up.pt/~vsc/Yap/documentation.html#YAPLibrary

SICStus Prolog: Calling Prolog from C
http://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_11.html#SEC134

Ciao Prolog: Calling Prolog from C
http://ciao-lang.org/docs/ciao/foreign_interface_doc.html#Calling%20Prolog%20from%20C

ECLiPSe: Embedding and Interfacing Manual
http://eclipseclp.org/doc/embedding.pdf

[Jan Burse]

Jan Burse schrieb:

> Most of the Prolog systems, especially those written in C,
> come with a C foreign function interface. But I guess there
> is no standard.

B-Prolog: Calling C from Prolog
http://www.probp.com/manual/node139.html

[Oleh]

Hi Phil

indeed, you can use SWI-Prolog (or other as already listed by Jan B.) by attaching DLL/SO.

I'm doing this with Java (via JNA with a DLL/so), so one could write a thin c/c++ glue-wrapper, to access i.e. SWI-PRolog's libswipl.dll/so.

Cheers
Oleh

[Ulrich Neumerkel]

Jan Burse <janb...@fastmail.fm> writes:
>Philipp Kraus schrieb:
>>> But I don't think DLLs work on Linux and MacOSX,
>>> in case this refers to the Microsoft's implementation
>>> of the shared library concept.
>>
>> DLL is the name of "dynamic link library", under Linux there exists *.so
>> files and under OSX *.dylib
>> (Windows *.dll) but it is equal. DLL is general.
>
>Most of the Prolog systems, especially those written in C,
>come with a C foreign function interface. But I guess there
>is no standard.

The last documented effort I am aware of is Copenhagen 2002.
From the minutes of the standard-related meeting at ICLP:

"Roberto Bagnara had agreed to continue with the work he
started with M. Carro on the foreign language interface."

[Philipp Kraus]

I have found these systems too, but I would like to use a GPL Prolog
version. My favorites are GnuProlog, SWIProlog or YAP.
Which version would you take for the problem? IMHO Yap are the system
with the best performance and the MPI interface is pretty,
SWIProlog has got very nice addons and GnuProlog are a compact
minimalistic system, it is a very difficult decision.

Phil

[graham...@gmail.com]

VTProlog (very tiny prolog) is about 30kb of TurboPascal 3. (DOS)

Just checked, Win7 is ok, Win8 didn't work.

http://phpprolog.com/vt-prolog.jpg




Herc
--
www.phpPROLOG.com

[Philipp Kraus]

On 2013-08-30 05:19:10 +0000, graham...@gmail.com said:
>
> VTProlog (very tiny prolog) is about 30kb of TurboPascal 3. (DOS)
>
> Just checked, Win7 is ok, Win8 didn't work.
>
> http://phpprolog.com/vt-prolog.jpg

Thanks, but it can not be a stand-alone system, because I need a DLL or
something else,
for including it in my system. Also the system must run unter Windows 8.

Phil

[graham...@gmail.com]

On Tuesday, August 27, 2013 10:44:28 AM UTC-7, Philipp Kraus wrote:
> Hello,
>
>
>
>
> I need some help, because I would like to implementate a Prolog interpreter in Lua, because for some scriptable structures.
>
> I have found http://yieldprolog.sourceforge.net/ which implements Prolog in JS. I have worked with Prolog, but at the moment
>

Is this a full Prolog interpreter - compound predicates with recursive descent unification?



Yield Prolog lets you embed Prolog programs directly in Python, C# [1] or Javascript [2] by using the yield keyword. For example, here is the classic "uncle" predicate in Prolog:


uncle(Person, Uncle) :-
parent(Person, Parent),
brother(Parent, Uncle).


(This says that a person has an uncle if the person has a parent and that parent has a brother.) And here it is from the Yield Prolog compiler:

Python

C#
def uncle(Person, Uncle):
Parent = Variable()
for l1 in parent(Person, Parent):
for l2 in brother(Parent, Uncle):
yield False

IEnumerable<bool> uncle(object Person, object Uncle) {
Variable Parent = new Variable();
foreach (bool l1 in parent(Person, Parent)) {
foreach (bool l2 in brother(Parent, Uncle))
yield return false;
}
}


Javascript
function uncle(Person, Uncle) {
var Parent = new Variable();
for each (var l1 in parent(Person, Parent)) {
for each (var l2 in brother(Parent, Uncle))
yield false;
}
}


As you can see, the flow of the code in Yield Prolog is similar to Prolog. The Tutorial explains how these examples work, without expecting you to know Prolog. And the benchmarks show that Yield Prolog in C# can be faster than efficient Prolog systems like Yap Prolog and XSB.

Yield Prolog is made possible by the yield keyword, which automatically creates iterators that you can nest, combined with Yield Prolog's Variable class which can unify a variable with other values (just like in Prolog). There is no "API" standing between your code and Yield Prolog, because you just use the yield keyword to make "iterator functions" wherever you need them. Yield Prolog is part of your code, which can mix Prolog-style predicates directly with ordinary arrays, file I/O, GUI calls and all your own classes. Because it lets you mix these, Yield Prolog unifies the declarative and procedural programming models.






Hmmmm... Prolog in 3 lines of code???



Herc
--
www.phpPROLOG.com

[graham...@gmail.com]

Can you run LISP on your system?

Then just code UNIFY() in LISP (about 30 lines of code).






-----------------------------------------


LISP

;;; This is one of the example programs from the textbook:
;;;
;;; Artificial Intelligence:
;;; Structures and strategies for complex problem solving
;;;
;;; by George F. Luger and William A. Stubblefield
;;;
;;; These programs are copyrighted by Benjamin/Cummings Publishers.
;;;
;;; We offer them for use, free of charge, for educational purposes only.
;;;
;;; Disclaimer: These programs are provided with no warranty whatsoever as to
;;; their correctness, reliability, or any other property. We have written
;;; them for specific educational purposes, and have made no effort
;;; to produce commercial quality computer programs. Please do not expect
;;; more of them then we have intended.
;;;



;;; This is the unification algorithm from section 7.6 of the text.

;;; recursive unification algorithm, takes two patterns and a list of
;;; substitutions found so far and returns either "failed" or the
;;; substitution-list augmented with those bindings needed for a match

(defun unify (pattern1 pattern2 substitution-list)
(cond ((equal substitution-list 'failed) 'failed)
((varp pattern1)
(match-var pattern1 pattern2 substitution-list))
((varp pattern2)
(match-var pattern2 pattern1 substitution-list))
((is-constant-p pattern1)
(cond ((equal pattern1 pattern2) substitution-list)
(t 'failed)))
((is-constant-p pattern2) 'failed)
(t (unify (cdr pattern1) (cdr pattern2)
(unify (car pattern1) (car pattern2)
substitution-list)))))

;;; will attempt to match a variable to a pattern, first
;;; checking for existing bindings on the variable, then
;;; performing an occurs check.

(defun match-var (var pattern substitution-list)
(cond ((equal var pattern) substitution-list)
(t (let ((binding (get-binding var substitution-list)))
(cond (binding
(unify (get-binding-value binding)
pattern substitution-list))
((occursp var pattern) 'failed)
(t (acons var pattern substitution-list)))))))


;;; occursp will check if a variable occurs in a pattern.

(defun occursp (var pattern)
(cond ((equal var pattern) t)
((or (varp pattern) (is-constant-p pattern))
nil)
(t (or (occursp var (car pattern))
(occursp var (cdr pattern))))))

;;; is-constant-p determines if an item is a constant. In this simple
;;; program, we are assuming that all constants are atoms.

(defun is-constant-p (item)
(atom item))

(defun varp (item)
(and (listp item)
(equal (length item) 2)
(equal (car item) 'var)))


;;; get-binding takes a variable and a substitution list, and returns
;;; a (variable . binding-value) pair

(defun get-binding (var substitution-list)
(assoc var substitution-list :test #'equal))

;;; get-binding-value returns the binding value from
;;; a (variable . binding-value) pair

(defun get-binding-value (binding) (cdr binding))

;;; add-substitution adds a variable and a binding-value to a
;;; substitution-list

(defun add-substitution (var pattern substitution-list)
(acons var pattern substitution-list))








-------------------------------------------------



Or modify the source code of VTProlog or some other small interpreter.

It doesn't get simpler than TurboPascal 3.0.



www.phpprolog.com/VTPROLOG.zip

[Philipp Kraus]

On 2013-08-31 00:55:10 +0000, graham...@gmail.com said:

> Can you run LISP on your system?
>
> Then just code UNIFY() in LISP (about 30 lines of code).

Please read my first posting. I need a DLL structure with a C or C++
interface. I don't run a shell script or anything else.

> Or modify the source code of VTProlog or some other small interpreter.
>
> It doesn't get simpler than TurboPascal 3.0.

Equal argumentation here. I have a system that is written in C++, so I
can not call a stand-alone programm and
TurboPascal binaries can not be called from C++ / C with a DLL call,
because binaries are not compatible.
TurboPascal is also out-of-date and my system must run on Linux, OSX
and Windows (XP, Vista, 7, 8), so
TurboPascal does not work on these systems.

[graham...@gmail.com]

On Tuesday, September 3, 2013 5:46:01 AM UTC-7, Philipp Kraus wrote:
> On 2013-08-31 00:55:10 +0000, graham...@gmail.com said:
>
>
>
> > Can you run LISP on your system?
>
> >
>
> > Then just code UNIFY() in LISP (about 30 lines of code).
>
>
>
> Please read my first posting. I need a DLL structure with a C or C++
>
> interface. I don't run a shell script or anything else.
>

You can easily get a LISP interpreter in C.

And PROLOG is often just a LISP interpreter + 30 lines of LISP
which I gave you.

>
>
> > Or modify the source code of VTProlog or some other small interpreter.
>
> >
>
> > It doesn't get simpler than TurboPascal 3.0.
>
>
>
> Equal argumentation here. I have a system that is written in C++, so I
>
> can not call a stand-alone programm and
>
> TurboPascal binaries can not be called from C++ / C with a DLL call,
>
> because binaries are not compatible.
>
> TurboPascal is also out-of-date and my system must run on Linux, OSX
>
> and Windows (XP, Vista, 7, 8), so
>
> TurboPascal does not work on these systems.

Right but C is based on Pascal.


You'd have to convert the source code into C, this is a linked
lists implementation.

Both the LISP solution and the LL solution are very slow.






{.PW132}
{.IN+}
{.HE VTPROLOG.PAS Page #}
{$V-,R+,B- }
PROGRAM very_tiny_prolog ;

(* Copyright 1986 - MicroExpert Systems
Box 430 R.D. 2
Nassau, NY 12123 *)

(* Revisions - 1.1 Nov. 1986 - Edinburgh list syntax added *)

(* VTPROLOG implements the data base searching and pattern matching of
PROLOG. It is described in "PROLOG from the Bottom Up" in issues
1 and 2 of AI Expert.

This program has been tested using Turbo ver 3.01A on an IBM PC. It has
been run under both DOS 2.1 and Concurrent 4.1 .

We would be pleased to hear your comments, good or bad, or any applications
and modifications of the program. Contact us at:

AI Expert
Miller Freeman Publications
500 Howard St.
San Francisco, CA 94105

Bill and Bev Thompson *)

CONST
debug = false ;
back_space = ^H ;
tab = ^I ;
eof_mark = ^Z ;
esc = #27 ;
quote_char = #39 ;
left_arrow = #75 ;
end_key = #79 ;
del_line = ^X ;
return = ^M ;
bell = ^G ;

TYPE
counter = 0 .. maxint ;
string80 = string[80] ;
string132 = string[132] ;
string255 = string[255] ;
text_file = text ;
char_set = SET OF char ;
node_type = (cons_node,func,variable,constant,free_node) ;
node_ptr = ^node ;
node = RECORD
in_use : boolean ;
CASE tag : node_type OF
cons_node : (tail_ptr : node_ptr ;
head_ptr : node_ptr) ;
func,
constant,
variable : (string_data : string80) ;
free_node : (next_free : node_ptr ;
block_cnt : counter) ;
END ;

(* node is the basic allocation unit for lists. The fields are used as
follows:

in_use - in_use = false tells the garbage collector that this node
is available for re-use.
tag - which kind of node this is.
cons_node - cons_nodes consist of two pointers,
one to the head (first item)
the other to the rest of the list. They are the "glue" which
holds the list together. The list (A B C) would be stored as
------- -------- --------
| .| . |-----> | .| . |------> | .| . |---> NIL
--|----- --|------ --|-----
| | |
V V V
A B C

The boxes are the cons nodes, the first part of the box
holds the head pointer, then second contains the tail.
constant - holds string values, we don't actually use the entire 80
characters in most cases.
variable - also conatins a string value, these nodes will be treated as
PROLOG variables rather than constants.
free_node - the garbage collector gathers all unused nodes and puts
them on a free list. It also compacts the free space into
contiguous blocks. next_free points to the next free block.
block_cnt contains a count of the number of contiguous 8 byte
free blocks which follow this one. *)


VAR
line,saved_line : string132 ;
token : string80 ;
source_file : text_file ;
error_flag,in_comment : boolean ;
delim_set,text_chars : char_set ;
data_base,initial_heap,free,saved_list : node_ptr ;
total_free : real ;

(* The important globals are:
source_file - text file containing PROLOG statements.
line - line buffer for reading in the text file
saved_list - list of all items that absolutely must be saved if garbage
collection occurs. Usually has at least the data_base and
the currents query attached to it.
initial_heap - the value of the heap pointer at the start of the program.
used by the garbage collector
free - the list of free nodes.
total_free - total number of free blocks on the free list.
data_base - a pointer to the start of the data base. It points to a
node pointing to the first sentence in the data base. Nodes
pointing to sentences are linked together to form the data
base.
delim_set - set of characters which delimit tokens. *)


(* ----------------------------------------------------------------------
Utility Routines
---------------------------------------------------------------------- *)

PROCEDURE noise ;
(* Make a noise on the terminal - used for warnings. *)
BEGIN
write(bell) ;
END ; (* noise *)


FUNCTION open(VAR f : text_file ; f_name : string80) : boolean ;
(* open a file - returns true if the file exists and was opened properly
f - file pointer
f_name - external name of the file *)
BEGIN
assign(f,f_name) ;
(*$I- *)
reset(f) ;
(*$I+ *)
open := (ioresult = 0) ;
END ; (* open *)


FUNCTION is_console(VAR f : text_file) : boolean ;
(* return true if f is open on the system console
for details of fibs and fib_ptrs see the Turbo Pascal ver 3.0 reference
manual chapter 20. This should work under CP/M-86 or 80, but we haven't
tried it. *)
TYPE
fib = ARRAY [0 .. 75] OF byte ;
VAR
fib_ptr : ^fib ;
dev_type : byte ;
BEGIN
fib_ptr := addr(f) ;
dev_type := fib_ptr^[2] AND $07 ;
is_console := (dev_type = 1) OR (dev_type = 2) ;
END ; (* is_console *)


PROCEDURE strip_leading_blanks(VAR s : string80) ;
BEGIN
IF length(s) > 0
THEN
IF (s[1] = ' ') OR (s[1] = tab)
THEN
BEGIN
delete(s,1,1) ;
strip_leading_blanks(s) ;
END ;
END ; (* strip_leading_blanks *)


PROCEDURE strip_trailing_blanks(VAR s : string80) ;
BEGIN
IF length(s) > 0
THEN
IF (s[length(s)] = ' ') OR (s[length(s)] = tab)
THEN
BEGIN
delete(s,length(s),1) ;
strip_trailing_blanks(s) ;
END ;
END ; (* strip_trailing_blanks *)



FUNCTION toupper(s : string80) : string80 ;
(* returns s converted to upper case *)
VAR
i : byte ;
BEGIN
IF length(s) > 0
THEN
FOR i := 1 TO length(s) DO
s[i] := upcase(s[i]) ;
toupper := s ;
END ; (* toupper *)


FUNCTION is_number(s : string80) : boolean ;
(* checks to see if s contains a legitimate numerical string.
It ignores leading and trailing blanks *)
VAR
num : real ;
code : integer ;
BEGIN
strip_trailing_blanks(s) ;
strip_leading_blanks(s) ;
IF s <> ''
THEN val(s,num,code)
ELSE code := -1 ;
is_number := (code = 0) ;
END ; (* is_number *)


FUNCTION cardinal(i : integer) : real ;
VAR
r : real ;
BEGIN
r := i ;
IF r < 0
THEN r := r + 65536.0 ;
cardinal := r ;
END ; (* cardinal *)


FUNCTION head(list : node_ptr) : node_ptr ;
(* returns a pointer to the first item in the list.
If the list is empty, it returns NIL. *)
BEGIN
IF list = NIL
THEN head := NIL
ELSE head := list^.head_ptr ;
END ; (* head *)


FUNCTION tail(list : node_ptr) : node_ptr ;
(* returns a pointer to a list starting at the second item in the list.
Note - tail( (a b c) ) points to the list (b c), but
tail( ((a b) c d) ) points to the list (c d) . *)
BEGIN
IF list = NIL
THEN tail := NIL
ELSE
CASE list^.tag OF
cons_node : tail := list^.tail_ptr ;
free_node : tail := list^.next_free ;
ELSE tail := NIL ;
END ;
END ; (* tail *)










Just change BEGIN and END to { and }

C!



Herc
--
www.phpPROLOG.com