ANN: open source Prolog compilers: BinProlog and Jinni Prolog

[Paul Tarau]

BinProlog is now opensourced under GPL 3.0.

It is at

http://code.google.com/p/binprolog/

and you can download it from:

http://code.google.com/p/binprolog/downloads/list

or get a git clone with:

git clone https://code.google.com/p/binprolog/


Jinni Prolog is now opensourced under GPL 3.0.

It is at http://code.google.com/p/jinniprolog/ and you can
download its Eclipse workspace from:

http://code.google.com/p/jinniprolog/downloads/list

or get a git clone with:

git clone https://code.google.com/p/jinniprolog/

BinProlog is a fast C-based Prolog compiler and runtime system. It can generate bytecode or C-code and it supports multithreading and networking.

Jinni Prolog is a Java-based Prolog compiler and runtime system, featuring objects, agents, multi-threading, networking, remote predicate calls, GUI, 2D and 3D graphics.

Both compilers are the result of 10++ person/years effort and run happilly on Mac OS X, Linux and Windows.

Enjoy,

Paul Tarau

[Jan Burse]

Paul Tarau schrieb:
> http://code.google.com/p/jinniprolog/

Not sure whether this is the right way to start it,
but I guess it requires JDK 1.7, right?

Jan-Burses-MacBook-Pro:MainProlog janburse$ java -jar prolog.jar
Exception in thread "main" java.lang.UnsupportedClassVersionError:
prolog/kernel/Main : Unsupported major.minor version 51.0
at java.lang.ClassLoader.defineClass1(Native Method)

[Ulrich Neumerkel]

Paul Tarau <pta...@gmail.com> writes:
...
>BinProlog is a fast C-based Prolog ...
>
>Jinni Prolog is a Java-based Prolog ...

>
>Both compilers are the result of 10++ person/years effort and run happilly on Mac OS X, Linux and Windows.

Are these the only Prolog you are maintaining currently?

What are your plans for ISO/IEC conformance?

http://www.complang.tuwien.ac.at/ulrich/iso-prolog/

[Jan Burse]

Ulrich Neumerkel schrieb:

> Are these the only Prolog you are maintaining currently?
>
> What are your plans for ISO/IEC conformance?
>
> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/

I would embrace if *all* JVM Prolog systems would
try to reach ISO/IEC comformance.

And I would embrace if there are test suites for
syntax and predicates, that can be executed *unattended*.

I have already once proposed some predicates that
would support such test suites. Namely:

with_out_to(+Goal,?Container)
with_in_from(+Goal,?Container)

http://www.jekejeke.ch/idatab/doclet/blog/en/docs/std/07_compliance/07_diagnosis/01_runner/02_helper.p.html

With the above write/read side effects can be tested
resp. emulated. I already use them in a predicate
test suite.

I guess they would be also suitable for a syntax test
suite, although a very small fraction of the syntax
test cases would probably not work.

There is a caveat for this helper predicates. They make
use of setup_call_cleanup/3 (*) which is not yet standardized.
So I didn't yet check the JVM Prolog systems, but
those that don't have setup_call_cleanup/3 would need
to find a workaround, either implement the helper
natively or find a substitution for setup_call_cleanup/3.

But those that have a substitute for setup_call_cleanup/3
could probably provide setup_call_cleanup/3 in the
first place?

Bye

(*)
http://www.complang.tuwien.ac.at/ulrich/iso-prolog/cleanup

BTW.: We might also have a hard time for Jinni:
?- setup_call_cleanup(true,true,true).
prolog.kernel.Machine prolog 0 returned::
exception(error(undefined_predicate_in_metacall,setup_call_cleanup(true,true,true)))
Restarting Prolog Machine: prolog.kernel.Machine prolog 0

[Ulrich Neumerkel]

Jan Burse <janb...@fastmail.fm> writes:
>Ulrich Neumerkel schrieb:
>> Are these the only Prolog you are maintaining currently?
>>
>> What are your plans for ISO/IEC conformance?
>>
>> http://www.complang.tuwien.ac.at/ulrich/iso-prolog/
>
>I would embrace if *all* JVM Prolog systems would
>try to reach ISO/IEC comformance.
>
>And I would embrace if there are test suites for
>syntax and predicates, that can be executed *unattended*.

There are a lot of properties that cannot be tested unattended. I mean
just for syntax:

http://www.complang.tuwien.ac.at/ulrich/iso-prolog/conformity_assessment#2

The point being, that after the two characters "'\n" there should be already
a syntax error.

Or ")\n" should wait.

The current table I have collected covers these issues. How do you
propose that an unattended test suite should hanlde these?

[Paul Tarau]

Both BinProlog and Jinni provide essential logic programming services and a lot of experimental extensions but none of them is very strong on most of the "gourmet features" of the ISO specification.

My hope by opensourcing them as Google projects is to provide a good starting point with 90% of the work done (WAM, networking, multi-threading, objects, agents, GUI etc.) for someone who would like to build on them.

In particular, if there's enough interest in their other features, someone could provide the remaining 10% needed for full ISO conformance.

Paul

P.S. My newest Prolog-like system is Scala based (see

http://code.google.com/p/styla/

) and it is the only one that I am actively developing.

Still, it might end up diverging radically from Prolog-as-we-know-it, so
in this case ISO conformance would be like requiring an airplane to
flap its wings just because birds do so :-)

[Ulrich Neumerkel]

Paul Tarau <pta...@gmail.com> writes:
>> > What are your plans for ISO/IEC conformance?
>

>Both BinProlog and Jinni provide ... but none of them is very strong

>on most of the "gourmet features" of the ISO specification.

Such "gourmet features" include the ability to read back what
was written.

>Still, it might end up diverging radically from Prolog-as-we-know-it, so
>in this case ISO conformance would be like requiring an airplane to
>flap its wings just because birds do so :-)

I read this as a clear No.

[Jan Burse]

Paul Tarau schrieb:

> P.S. My newest Prolog-like system is Scala based (see
>
> http://code.google.com/p/styla/
>
> ) and it is the only one that I am actively developing.
>
> Still, it might end up diverging radically from Prolog-as-we-know-it, so
> in this case ISO conformance would be like requiring an airplane to
> flap its wings just because birds do so:-)

How do Styla and Jinniprolog relate performance wise?

Is Styla an interpreter only implementation?

Bye

[Paul Tarau]

Styla is an interpreter only, but it might end turned into a compiler one day - somewhat similar to Jinni's, but simpler, "goal stacking" based.

On the Pereira benchmark at:

http://code.google.com/p/styla/source/browse/progs/pbm.pro

Jinni Prolog is about 4 secs, Styla is about 18 on my Mac Air.

Paul Tarau

P.S. As functional-style Scala with case classes transliterates almost one-to-one to/from deterministic Prolog and built-ins are just "drop-ins", one can still develop fast "logic programming" applications by easily combining the two languages.

[Jan Burse]

Paul Tarau schrieb:

> Jinni Prolog is about 4 secs, Styla is about 18 on my Mac Air.

Ok

> P.S. As functional-style Scala with case classes transliterates almost
> one-to-one to/from deterministic Prolog and built-ins are just "drop-ins",
> one can still develop fast "logic programming" applications by easily
> combining the two languages.

Do I read this as: Prolog for non-determinism, and Scala for
determinism, and heavy interaction between the two?

But I guess you need a low level interface for the heavy interaction,
something that most Prolog systems provide for their implementation
language.

I noticed that a low level interface has one disadvantage besides
it obvious advantage. It can make your interpreter code hard
to change. For example, in Jekejeke Prolog there is a private
invisible low level interface something along (simplified sketch):

my_pred_low_level(Skeleton goalskel, Display goaldisp)

The provider of a low level predicate has to walk the Goal by
himself, and extract the arguments. Also the provider of a
low level predicate has use to use term routines on (skel, disp)
pairs, since this is the current low level term representation.

Now if anything changes in the low level implementation of the
interpreter, for example changes in the term routines etc.. Then
all the low level predicates have to be adapted.

Jekejeke Prolog has also a high level interface, the FFI (Foreign
Function Interface). This is an artificial wrapper, where one
can provide a predicate via:

my_pred_high_level(Term arg1, ..., Term arg2)

The wrapper does a lot of work for the provider of a high level
predicate. For example the walking of the Goal to produce the
Goal arguments is done via reflection. It is also possible to
use other types than Term. Further the Term class is an abstraction
of the (skel, disp) pairs, and provides its own set of routines
which map to the low level routines.

Now if anything changes in the low level implementation of the
interpreter, for example changes in the term routines etc.. Then
all the high level predicates do not have to be adapted.

I guess the above low level/high level is an instance of the
fragile base class problem, where the high level interface is an
attempt to solve the problem for a certain type of clients of
the interpreter.

But I don't see yet how I could eliminate the overhead of the
high level interface. The wrapper is more or less one simple
indirection, but I don't think the JVM can eliminate it. So high
level FFI calls are much more expensive then low level built-in
calls.

I guess the problem could be better solved, in a Jekejni that
would somehow compile the high level predicate definitions into
low level stubs, instead of intrepreting the high level predicate
definitions. Don't know if Scala has some mechanism to somehow
define such translations in the language. This would be an
interesting programming language I would immediately embrace.

Meanwhile the strategy is to avoid heavy use of the high level
FFI, provide some crucial built-ins via the low level interface,
and be happy that the internals of the interpreter can be easily
changed without impacting the applications that use the high level
FFI.


Bye

[Jan Burse]

Jan Burse schrieb:

> Meanwhile the strategy is to avoid heavy use of the high level
> FFI, provide some crucial built-ins via the low level interface,
> and be happy that the internals of the interpreter can be easily
> changed without impacting the applications that use the high level
> FFI.

i.e only use the FFI for low frequency call-ins and call-outs. Which
forces the application design (which makes use of the high level FFI)
to use more Prolog, also for deterministic stuff. Which is not the
Style/Scala pattern you suggest I guess. :-(

Bye

[Paul Tarau]

The Styla to Scala (or Java, implicitely) calls are implemented with built-ins

(see http://code.google.com/p/styla/source/browse/#git%2Fsrc%2Fprolog%2Fbuiltin s)

that are recognized at parsing time through a reflection-based mechanism. Calling them is quite fast, that might explain why Styla is not "dramatically" slower than Java-based compiled Prologs on the Pereira benchmark.

While there's also a calling mechanism from Scala (or Java) to Styla

(see http://code.google.com/p/styla/source/browse/#git%2FJavaCallsStyla )

the communication is better done through Akka Actors

(see http://code.google.com/p/styla/source/browse/src/prolog/builtins/actor_akka_new.scala )

They force the programmer to design genuinely modular code that also scales up in a cloud-computing setting to millions of actors, all automatically (i.e. with no work to do, from the Prolog implementor's perspective).

The overhead for sending messages from Prolog is quite light, see:

http://code.google.com/p/styla/source/browse/src/prolog/builtins/actor_send.scala

Paul Tarau


P.S. There's also a Java version of the Akka Actor system,

(see http://doc.akka.io/docs/akka/snapshot/java/ )

One might want to look at it as an addition to Java-based Prologs, along the lines of their Styla embedding.

[Ulrich Neumerkel]

Paul Tarau <pta...@gmail.com> writes:

Paul, can you in one word say how you implement logical variables?

The reason I am asking is that a new way has been taken here for Curry.

[Jan Burse]

Paul Tarau schrieb:

> The Styla to Scala (or Java, implicitely) calls are
> implemented with built-ins
>

> (seehttp://code.google.com/p/styla/source/browse/#git%2Fsrc%2Fprolog%2Fbuiltin s)

>
> that are recognized at parsing time through a
> reflection-based mechanism. Calling them is quite fast,
> that might explain why Styla is not "dramatically" slower
> than Java-based compiled Prologs on the Pereira benchmark.

The built-in implementation itself looks something between
low-level and high-level too me:

package prolog.builtins
import prolog.terms._
import prolog.interp.Prog

final class abolish() extends FunBuiltin("abolish", 2) {
override def exec(p: Prog) = {
val f = getArg(0).asInstanceOf[Const]
val n = getArg(1).asInstanceOf[Num].getValue.toInt
val g = new Fun(f.sym)
g.init(n)
p.db.cleanUpKey(g)
1
}
}


I see getArg(), and a parameter of type Prog. But
eventually, in your scala application, stability of
mid level implementation of predicates is not that
a problem. Maybe you have found the right abstraction.

From the above it looks to me that you will use an
instance of the above class, otherwise I don't see how
getArg(0) can find its data. Especially if you want to
execute predicates concurrently (can Styla do this?).
Concurrently you cannot use a singleton pattern where
you pass the arg data via setting the data in
the singleton.

In Jekejeke Prolog, when using the high level API, one
could define the above as follows (simplified sketch):

public static void abolish(Interpreter i, String f, Integer n) {
Predicate pick = getPredByNameArity(f, n.intValue(), i);
if (pick != null)
abolishPred(pick, i);
}

The wrapper will then do what we find in your Style code
as "asInstanceOf[Const]", "asInstanceOf[Num]", etc..

But since the wrapper is interpreted, means it has to
travel the meta information of the abolish method, i.e.
work with a java.lang.reflect.Method, it is not that fast.
Maybe a Jekejin could do some stuff at compile time, so
that the runtime overhead can be minimized. But with your
abstraction, via getArg() etc.., this seems not to be
an issue and thus probably also not written on some agenda.

Maybe something can be done with the new invokedynamic
byte code instruction, especially since we have abolish!
invokedynamic would be ideal, according to some blog by
John Rose @ Oracle, I saw already an implementation of
a switcher, which can do method switching (i.e. replace
an old method for a new method at some call site) via
invokedynamic. But can't find the blog link right now.


Bye

[Jan Burse]

Jan Burse schrieb:

> John Rose @ Oracle, I saw already an implementation of
> a switcher, which can do method switching (i.e. replace
> an old method for a new method at some call site) via
> invokedynamic. But can't find the blog link right now.

Not without a challenge when code is executed concurrently,
how to do it without a costly synchronized statement?

Bye

[Jan Burse]

Jan Burse schrieb:

> Maybe something can be done with the new invokedynamic
> byte code instruction, especially since we have abolish!
> invokedynamic would be ideal, according to some blog by

Since invokedynamic is from >2008, I guess it did
not find its way into Jinni. Otherwise I would eagerly
start grabbing the code. Maybe there is some other
research / industry project around which already tried
it. Or maybe my expectations are too high...

Bye

[Paul Tarau]

On Friday, November 23, 2012 10:43:14 AM UTC-6, Ulrich Neumerkel wrote:

> Paul Tarau <> writes:
>
>
>
> Paul, can you in one word say how you implement logical variables?
>
>
>
> The reason I am asking is that a new way has been taken here for Curry.

They are just part of an object oriented hierarchy - unification is implemented by each participant doing its share. The code is at:

http://code.google.com/p/styla/source/browse/src/prolog/terms/Var.scala

Paul

P.S. As Terms are serializable one does not have to worry about writing out terms and read them back accurately. In the JVM serialized objects are written out "in C" so that is also really hard to beat performance-wise.

[Paul Tarau]

The trick to avoid (expensive) reflection at each call is to do it once, when you parse. You still have things like functor/3 and univ/2 watch for the same, but that's a small price to pay for very fast built-in calls. So if you
have in a clause

a(X):-assert(nice(X)).

assert/1 is assigned the class FunBuiltin when parsed - and then "it knows" what to do - i.e. its "exec" method is called directly.

A good example is Styla's fast deterministic append:

http://code.google.com/p/styla/source/browse/src/prolog/builtins/det_append.scala

where you can also notice that all related small functions are collected together - so this also encourages a modular design.

Paul Tarau

[Jan Burse]

Paul Tarau schrieb:

> The trick to avoid (expensive) reflection at each call
> is to do it once, when you parse. You still have things
> like functor/3 and univ/2 watch for the same, but that's
> a small price to pay for very fast built-in calls. So if you
> have in a clause
>
> a(X):-assert(nice(X)).
>
> assert/1 is assigned the class FunBuiltin when parsed - and
> then "it knows" what to do - i.e. its "exec" method is
> called directly.

Don't understand me wrong, but this doesn't solve the
problem. Of course one can lookup predicates during read,
and for example for forward reference predicates add an
empty definition, which is later completed.

So if you have:

mul(n,X,n).
mul(s(X),Y,Z) :- mul(X,Y,H), add(Y,H,Z).

add(n,X,X).
add(s(X),Y,Z) :- add(X,Y,s(Z)).

Then add/3 is a forward reference in the second clause of
mul/3. But what you call reflection is not the reflection
I need to make my high level predicates in Jekejeke Prolog
work. What you call reflection is only the lookup to make
your mid level predicates work, in the sense that the "exec"
method can be called.

But the "exec" method encapsulates already the getArg()
and putArg() stuff. For my high level predicates reflection
is used inside the wrapper, and translates the meta information
about the method into getArg() and putArg(). For example
a method of the form:

Character charLowerCase(Character c) {
}

The wrapper would need to generate a getArg(0) and check/
unpacking of the character type. And then putArg(1) and
packing of the character type after invokation of the method.
In your mid level predicates this is all already manually
coded at compile time inside the exec(). For my high level
predicates this is all interpreted at runtime and therefore
slower.

This interpretation step for my high level predicates is
not only slower in itself, it can also not be subject to
JVM JIT-ing, for example inlining at runtime some of the
getArg() or putArg() code when the JIT kicks in.

> A good example is Styla's fast deterministic append:
>
> http://code.google.com/p/styla/source/browse/src/prolog/builtin

> /det_append.scala
>
> where you can also notice that all related small functions are
> collected together - so this also encourages a modular design.

You are right, it only shows modular design, but not
more. And can be done in any language with a notion of
"modules". Even if in my high level predicate model I
can do this. I would just make many small classes,
and collect the helpers that belong to a builtin in
a class:

public class MyBuiltIn {

MyHelper1

MyHelper2

public static MyPred

}

But since in the high level predicate model of
Jekejeke Prolog a predicate is a method pointer I
can do a little bit more, I can also group related
prediates. This is not possible with an exec method:

public class MyBuiltIn {

MyHelper1

MyHelper2

public static MyPred1

public static MyPred2

public static MyPred3
}

The interesting point in your example is the question
whether the helpers can call getArg() and putArg(),
although this would lead to a less functional design
of the helpers and should probably be avoid. I also
still wonder whether Styla built-ins are reentrant.

Bye

[Paul Tarau]

Maybe I was not clear enough, the mechanism I am mentioning applies to "built-ins" seen as calls from Prolog to Scala (or Java).

Prolog parsing happens before execution so if the "link" between a Prolog function symbol and the implementation of the corresponding Scala (or Java) built-in is established at that time, no further look-up is needed at execution time which (obviously) happens after parsing.

The mechanism even applies to higher order predicates like call/N if you ensure that functor and univ check their newly built compound terms.

This would also apply to your example where you "compile"
Prolog predicates to Java methods, provided that you do it before you execute the code.
In this sense, it will not matter if "add" in your example is a forward reference or not.
So if you morph your interpreter into a compiler you can make use of the same mechanism - if I remember well, we did something similar in jProlog - around 1997 or so.


About reentracy of built-ins: if their code is purely functional and relies on immutable Scala objects, the code is reentrant provided that one synchronizes the putArg method. Otherwise it is not - and as usual in Scala (and Java) it requires things like concurrent collection classes and explicit synchronization.

Paul Tarau

[Jan Burse]

Paul Tarau schrieb:

> About reentracy of built-ins: if their code is purely functional
> and relies on immutable Scala objects, the code is reentrant
> provided that one synchronizes the putArg method. Otherwise it is
> not - and as usual in Scala (and Java) it requires things like
> concurrent collection classes and explicit synchronization.

I still don't see how an instance with an exec() method and
getArg() and putArg() gets reentrant. But you also mentioned
in another post that you use "goal stacking". And the Var class
has only one bind pointer.

So most probably the mechanics is such that during clause
invokation the body is copied, so that a new instance of
the predicate is created. And then there is no issue with
reentrance, since the body copy is only used by the executing
thread.

Bye

[Jan Burse]

Paul Tarau schrieb:

> This would also apply to your example where you "compile"
> Prolog predicates to Java methods, provided that you do it before you execute the code.
> In this sense, it will not matter if "add" in your example is a forward reference or not.
> So if you morph your interpreter into a compiler you can make use of the
> same mechanism - if I remember well, we did something similar in jProlog -
> around 1997 or so.

I am currently using PICs (from 1991)
in my Interpreter setting:

Optimizing Dynamically - Typed Object - Oriented
Languages with Polymorphic Inline Caches
Urs H�lzle, Craig Chambers, David Ungar
ECOOP '91 Proceedings of the European
Conference on Object-Oriented Programming
http://selflanguage.org/_static/published/pics.pdf

One can manage to implement the cachingmechanism concurrently
without an expensive synchronize statement, and last but not
least it is possible to detect abolished predicates. For a blog
post on their use in Jekejeke Prolog see for example:
https://plus.google.com/u/0/103259555581227445618/posts/d4ECiZu4CCA

Bye

[Paul Tarau]

On Tuesday, November 13, 2012 8:34:03 AM UTC-6, Paul Tarau wrote:

Good guess, that (copying of the clause body) is indeed the case! And it is easy to compile - clauses are known in advance so you can generate custom code for each copying.

Paul

Paul