Embedding Prolog in Haskell

Luke once pointed to Peter Norvig's embedding of Prolog in Lisp as an example of the power of the language, and asked whether (or if) it could be done in Haskell. I said I would think about it, but never got around to working out the details.

Well, it turns out it's been done, and the essential bits are quite simple and intuitive, though macros would help to hide some of the abstract syntax-looking stuff (not apparent from the paper's append example).

J. M. Spivey and S. Seres. Embedding Prolog in Haskell. In Proceedings of Haskell '99 (E. Meijer, ed.), Technical Report UU-CS-1999-28, Department of Computer Science, University of Utrecht.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Last time

Same subject mentioned here in the past (the links to older messages end up with Seres's paper).

The Fun of Programming includes a chapter on the same topic (using a slightly different technique, IIRC).

Prolog in Javascript

Also mentioned before: Prolog in Javascript. Apparently Prolog is pretty easy to implement, it's only 15k, parser included. Look up the unify function in the source!

Update: That was an old version, new version is here.

Prolog in Scala

Dear All,

Just found a nice implementation of Prolog in Scala. Unfortunately I didn't have time to try it, so my impression is only based on looking at the source code that can be found here:

https://github.com/sonoisa/Prolog-in-Scala/blob/master/PrologInScalaSample.scala

The above points to a couple of test programs. The Prolog interpreter is written in Scala in such a way that Prolog clauses can be embedded as Scala objects written in Scala. I don't fully understand the magic behind it, here is a sample how the tak function is written:

tak('X, 'Y, 'Z, 'A) :- (
'X =< 'Y, CUT, 'Z === 'A
)
tak('X, 'Y, 'Z, 'A) :- (
'X1 is 'X - 1,
'Y1 is 'Y - 1,
'Z1 is 'Z - 1,
tak('X1, 'Y, 'Z, 'A1),
tak('Y1, 'Z, 'X, 'A2),
tak('Z1, 'X, 'Y, 'A3),
tak('A1, 'A2, 'A3, 'A)
)

Why do I mention it here? Well a git branch (click on Network) by akimichi mentions the paper by J. M. Spivey and S. Seres. But the Scala implementation looks rather continuation based and less stream based.

So it would be difficult to change the search strategy,
by simply changing the implementation of a connective, right?

Bye

and in lisp/qi/shen

qi prolog, for whatever it is worth.

Prolog in Scheme

Again Mini Karen:

http://okmij.org/ftp/Scheme/sokuza-kanren.scm
; For more detail, please see `The Reasoned Schemer'

Already covered on LtU in a couple of places.

Note 1: It has a simpler unification than Norvigs, no occurs check. And the code is cleaner since deref is not convoluted into unify.

Note 2: One might find much older Prolog in Lisp implementations from
around 1983 by Ken Kahn and Mats Carlsson (LM-Prolog).

One more Prolog in Scala: Styla

Cited from Paul Taraus post on comp.lang.prolog:

"Styla is a fairly complete Prolog interpreter written in Scala,
derived from Kernel Prolog (see Fluents: A Refactoring of Prolog for
Uniform Reflection and Interoperation with External Objects in
CL'2000).

The genuinely open sourced (Apache license) code is hosted at:

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

and it is designed with simplicity and extensibility in mind - hoping
it would be useful to people experimenting with new Prolog extensions
or alternative logic programming languages."

Best features for embedded Prolog influenced module?

This is an old thread where the focus has been on the features of the language a more or less regular Prolog interpreter is to embedded in, and how they enable the implementation. I periodically find myself thinking of a different question: "What features would be most useful in an embedded Prolog-like library/module?" I mean the answer to include things like:

  1. Will there be a mapping between data structures and functions of the embedding language and the analogs of atoms and facts in the module? How the facts/terms be typed if the embedding language has types?
  2. How can the module construct and return data structures to the caller?
  3. Should the module use an occurs check? I assume 'yes'.
  4. Should the Prolog-like language be cut-free?
  5. Should there be assert/retract and if so, should they be more namespace oriented?
  6. Should execution with instances of the module be asynchronous with an input queue for new queries?
  7. Should instances of the module be objects that can be named and passed around in the parent program?
  8. Would it be important for performance to compile the embedded program? If so, what strategy should be used?

I think that's an

I think that's an interesting question. I'm not sure that a newly-resurrected thread from 2004 about a tangentially-related paper is the best place to ask it.

Datalog, Dedalus

I would simply suggest you favor Datalog or Dedalus instead of Prolog.

Included in "Prolog influenced"

Thanks for the comment. I'm familiar with Datalog as a more declarative Prolog influenced language. Dedalus is new to me, though I have a long standing belief that many reasoning and AI related problems are best tackled by including an explicit time-interval argument in the every representation.

I'll also add that what is most useful for a special purpose embedded module might be different than what works best for something trying to be the main language. If I had thought of it earlier, I might have included in my list

9. Should a choice of breadth first vs. depth first and optional depth-limited goal search
be available as explicit query options?


I see Prolog as a cool, but also somewhat arbitrarily bundled collection of mechanisms. I mean to be talking about which particular bundle of related mechanisms would be most beneficial as an add-in to another general purpose language.

I've used Datalog as a basis

I've used Datalog as a basis for data types - i.e. values as databases (sets of propositions) - and I find it interacts very nicely with functional abstraction and composition mechanisms.

Basically, each function says how to take one or more databases and extract and combine facts from them to generate new databases. This offers much more modularity and compositionality than Datalog has on its own, and `lazy evaluation` works very well since we want to direct the final search (with both forwards and backwards chaining) based on the full composition rather than wastefully generating every intermediate database. The composition functions essentially embed the logic, constructing and refining searches.

If you haven't heard about it, then you could look up the functional-relational programming model (the other meaning of `FRP`). Similarly, Bloom extends the work done on Dedalus with a more modular composition structure.

Pursuant to that, I developed a technique for abstracting identity away from its arbitrary representation (e.g. surrogate keys). I've also examined a few different inspirations for representing these sets - including extended set theory and generative grammars. However, I've yet to be entirely satisfied with any of these approaches (in particular, with respect to my goal of predictable performance) and I've tabled further research on them to pursue the reactive elements of my programming model.

Anyhow, when I suggest using Dedalus or Datalog instead of Prolog, I didn't mean that at a shallow "these are interesting, go see them" level. I mean that "these are the answer, they fill the gaps in expressiveness quite effectively, and all the additional features Prolog provides are unnecessary and undesirable."

When you say "these are the

When you say "these are the answer" it's not clear to me exactly which problems you are claiming were the important ones that got answered. I think we are both fairly clear about problems related to the non-declarative aspects of Prolog, but my the scope of my topic includes a lot more than that. You also mention more flexible approaches to search, but it isn't clear to me where F-R-P or Bloom stands in relation to the type of flexibility demanded by many CLP algorithms. Mozart/Oz was somewhat Prolog influenced and seemed to focus on hosting generic (roll your own or use a library) CLP.

I'm not mainly trying to ask "What's the best descendant of Prolog?" I'm mainly trying to ask "If you've already settled on general purpose language L which doesn't provide the things Prolog does easily as a builtin, what would be the most practically useful way of adding those capabilities to L?" To the extent that Datalog, Dedalus, or Bloom fix problems with Prolog and provide other interesting functionality then they are relevant to the answer, but don't say anything about how best to embed that in L. One of my implicit premises is that I may have put together numerous and complicated data structures in L that I want to perform relational reasoning with, and that other things being equal, I much prefer an embedding of my relational reasoner that can work directly with the existing data data structures rather than requiring me to "serialize" and "deserialize" them to exchange info with the relational inference engine.

Perhaps you wish to argue "Forget about L, go with Bloom" or something along those lines? That's kind of a different topic.

What features would be most

"What features would be most useful in an embedded Prolog-like library/module?" Datalog and Dedalus are the answer to the primary question you asked.

I'm assuming the embedding is in some other language, which already handles the orthogonal issues like concurrency.

One of my implicit premises

One of my implicit premises is that I may have put together numerous and complicated data structures in L that I want to perform relational reasoning with, and that other things being equal, I much prefer an embedding of my relational reasoner that can work directly with the existing data data structures rather than requiring me to "serialize" and "deserialize" them to exchange info with the relational inference engine.

You will always need some translation layer to distinguish which structures should be understood as propositions in the embedded logical model. If your language L supports a sufficient degree of `reflection`, it might be possible to automate some of this translation. Otherwise, the translation will need to be by hand, but one might still avoid `serialization` by use of lenses or laziness. My own interests pertain to maintaining and interacting with such views in heterogeneous data models.

In any case, your desire here pertains to L, not to the embedded logical model.

it isn't clear to me where F-R-P or Bloom stands in relation to the type of flexibility demanded by many CLP algorithms.

CLP can be understood as using requiring observations in the host language L to generate (or guard generation of) some propositions for the logical model. Functional relational programming assumes an embedding in a functional language. Bloom is an embedded language, whose L happens to be Ruby in its initial incarnation.

You will always need some

You will always need some translation layer to distinguish which structures should be understood as propositions in the embedded logical model. If your language L supports a sufficient degree of `reflection`, it might be possible to automate some of this translation. Otherwise, the translation will need to be by hand, but one might still avoid `serialization` by use of lenses or laziness.

Some translation/notification is, of course, required. But let's separately consider the runtime overhead and programmer overhead of that translation. By saying I wanted to avoid "serialization" I meant avoiding the runtime overhead of unpacking and repacking many large data structures. Writing the analog of SWIG interfaces might still be required of the programmer. If I'm allowed to modify L - either as language designer, with sufficiently powerful macros, or via runtime algorithms using reflection, then I can, as you say, possibly get rid of a lot of programmer overhead. Even if L was C++ or Java, a lot of programmer overhead could be saved by writing generic code for the generic containers.

it isn't clear to me where F-R-P or Bloom stands in relation to the type of flexibility demanded by many CLP algorithms.

CLP can be understood as using requiring observations in the host language L to generate (or guard generation of) some propositions for the logical model. Functional relational programming assumes an embedding in a functional language. Bloom is an embedded language, whose L happens to be Ruby in its initial incarnation.

I'm not sure what that means or relates to the specifics of the discussion. I was saying that one issue for evaluation of the embedded Prolog-influenced language is the set of primitives it supplies out of the box for doing various kinds of CLP and various types of search, and also how easy it is to do other types that are not supplied out of the box. What L supplies isn't the issue. What Bloom supplies would be.

Serialization

By saying I wanted to avoid "serialization" I meant avoiding the runtime overhead of unpacking and repacking many large data structures.

Sure. But, I repeat, whether this is feasible will depend more on language L than on the embedded logic language. Related issues include mutation of observed data structures and maintaining indexes for logical searches.

one issue for evaluation of the embedded Prolog-influenced language is the set of primitives it supplies out of the box for doing various kinds of CLP and various types of search, and also how easy it is to do other types that are not supplied out of the box. What L supplies isn't the issue. What Bloom supplies would be.

Embedded languages are not standalone languages. They don't come "out of the box". The relationship and interaction between an embedded language and its host is of prominent importance to understanding how the embedded language is used and what features are offered by the embedding.

Multi-threading

Hi,

6) Should execution with instances of the module be asynchronous with an input queue for new queries?

7) Should instances of the module be objects that can be named and passed around in the parent program?

Well one typically ends up with this kind of questions if the architecture is a Prolog consumer thread that is loosly coupled with the application as a producer of queries.

But many Prolog systems are multi-threaded nowadays and can be directly coupled with the application. A typicall application could be a web server, where multiple interpreter threads serve requests and share the same knowledgebase.

In the web server scenario there are two kinds of instances: Knowledgebases and Interpreters. They don't need names, they are just objects on the heap programmatically managed by the application.

The pooling of the threads can be delegated to the web server framework, when the Interpreter object is separated from the thread object.

Bye

Namespaces are important in

Namespaces are important in (even) compiled languages because programmers re-use the same names for different stuff. The nature and applications of Prolog make it especially prone to name re-use. So I understand what you are saying, but that wasn't really my concern with regard to namespaces.

Multi-threading <> Namespaces

I didn't refer to namespaces in my post. Namespaces are usually called modules in Prolog systems. Many modern Prolog systems support modules. And also many modern Prolog systems support multi-threading. These are two independent dimensions of a Prolog system.

There is a little nameclash since your questions starts asking for a Prolog library/module. And then you start talking about namespaces. But by Prolog library/module I understand a Prolog library for a Prolog system that can hold multiple Prolog modules, which are names inside a namespace. (*)

There is ISO document for Prolog modules, but I guess most Prolog systems divert from it, and implement something along what SICStus Prolog does. There are also further extensions around for object orientation. But all this happens inside the Prolog language and not in the interface between the host language and the Prolog system.

For the multi-threading dimension, the instances that appear are outside of the language, respectively seldom represented inside the language. We hardly find a Prolog system that will represent its own knowledge base as a reference object, since this would eventually only be useful when communicating with other instances. But it would be also conceivable.

Bye

(*)
Although most Prolog systems only allow a flat namespace backed-up by a hierarchical file system instead of a namespace that knows about packages and modules.

The naming issues may be

The naming issues may be clearer if we list them all at once:

  1. Names for terms/atoms and the objects that they map to - these can be written/queried in different parts of a program written by different people at different times, so traditional namespace issues apply. As you say, the Sicstus module system is a namespace mechanism for Prolog that is not ISO standard. In the context of the embedding project, there would be a question of whether this approach plays well with the namespace system of the host language. My thought is that it would be better to replace it with something that takes the namespaces from the host and is not based on files where Prolog only code lives.
  2. Names for interpreter instances - you seem to say that these are not needed if there is only one interpreter per thread, but I don't know why our library design should assume that restriction
  3. Names for different "databases" (containing overlapping sets of facts) within a given interpreter - this idea is non-traditional to Prolog in the sense that Prolog has named variables and a global database modified by assert/retract. Some Prolog-like alternatives to Prolog identify the global state as problematic and eliminate it (see discussion with dmbarbour). Other Prolog influenced alternatives like Mercury eliminate the global database but have richer variable types for holding state. Personally, I would like my embedded Prolog like thing to potentially provide a convenient and powerful interface to actual relational databases/tables, so I'm interested in finer grained representations of state.

Since you are talking of a library/module

1)
Since you are talking of a library/module I assume that you will have a set of procedure calls for example written in C that will give you C pointers.

On the level of terms/atoms you will receive such C pointers. Usually people don't call C pointers names. Also C pointers might be provided to the procedures or received from the procedures at various places in the application, as long as the application is one process with a shared heap. So I don't see that some namespace is needed for the terms/atoms.

If you don't want to go one process with a shared heap, then embedding of the Prolog system is probably not the right name in the first place. Then the architecture will be a loosely coupled one, and for such an architecture we would need to start the discussion all over again.

2)
Actually I didn't say in any place that there is one interpreter per thread. I said that it is possible to separate interpreters from threads, and that this is for example useful in the web server scenario, where the threads are provided by the web server framework. And therefore the library/module has only to provide the interpreter object.

But again if an interpreter is referenced by a C pointer for example or some equivalent in your host language, than you don't need a namespace for that. But again this works only when we look at the web server as one process where the threads share the heap. If this assumption is not given than maybe we would also need to start all over again the discussion here.

3)
Why do you have different names for databases and then overlapping facts? What do you mean by that? In the Prolog module systems the idea is of course to have inside a module private and/or public facts that are different from facts in other modules. If one wants facts across multiple files, then one can use the multifile directive, which is already defined in the ISO core standard. But the multifile directive does hardly carry over to modules.

Since a fact is identified by its predicate name and its arguments, and predicates in different modules are considered different predicate names. Eventually something can be done with import and export. So eventually you can import a predicate name in your module, and when this predicate is dynamic, you can eventually add more facts to the predicate. But I doubt that this can be done for a static predicate. Not sure.

On the other hand the name of a Prolog variable has a very small scope. Its scope is only the clause or query it occurs in. So not really a big namespace. But the extend of a Prolog variable can be greater, will be found in its continuation as long as the continuation runs. But when you assert a clause with a variable a new internal object for the variable is generated.

To represent more state one can extend the notion of a variable. For example this is done in variables with attributes used in constraint solving. Or one can reserve special compounds to denote special data. For example the ISO core standard allows that there is an implementation dependent compound that will denote a stream. Some Prolog systems even allow a generic way to embed objects from the host language in the Prolog term model by means of a reference data type.

The later, the reference data structure (*), is only needed when you want to manipulate some objects both from within the host language and the Prolog system. An example can be the interaction with a database management system (**).

Bye

(*) Prolog Reference Data Type:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/03_interface/05_concepts/05_reference.html

(**) SQL Statements as Prolog References:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/08_deploy/09_database/01_driver.html

1)Since you are talking of

1)
Since you are talking of a library/module I assume that you will have a set of procedure calls for example written in C that will give you C pointers.

On the level of terms/atoms you will receive such C pointers. Usually people don't call C pointers names. Also C pointers might be provided to the procedures or received from the procedures at various places in the application, as long as the application is one process with a shared heap. So I don't see that some namespace is needed for the terms/atoms.

I'm not making any assumptions about the implementation. For the moment, assume that the people writing a compiler for the host language L are also designing and implementing some embedded "Prolog influenced" language K. I'm going to refer to dynamic instances of K as "interpreter objects" below even though they may well be compiled as well. The exact nature of the mapping between functions and data structures in L and K is yet to be defined.

For the sake or argument, let's say that some statements of the syntactic form maps_as_func(Lfunc1,"kname1") and maps_as_data(Lobject2,"kname2") can be used by application programmers to define a mapping. Then the namespace issue in item list "1." is about avoiding collisions between either the same "kname1" or "kname2" being re-used at different points in the parent program, or Lfunc1 or Lobject2 actually being short for longer fully qualified names in L that need to be understood and referenced somehow within K to avoid conflating unrelated code or objects.

2)
Actually I didn't say in any place that there is one interpreter per thread. I said that it is possible to separate interpreters from threads, and that this is for example useful in the web server scenario, where the threads are provided by the web server framework. And therefore the library/module has only to provide the interpreter object.

But again if an interpreter is referenced by a C pointer for example or some equivalent in your host language, than you don't need a namespace for that. But again this works only when we look at the web server as one process where the threads share the heap. If this assumption is not given than maybe we would also need to start all over again the discussion here.

In the particular implementation you describe, the pointers to the interpreter objects are using in naming a particular interpreter. In C/C++ actions on a given interpreter are qualified as ptrToInterpreter->funcCall(...). We are in agreement that this form of naming doesn't require namespace mechanisms. We might however have a separate naming issue for brand new terms that dynamically defined within different interpreter instances. It's reasonable to suppose that the new terms could appear in queries directed from L. In the absence of programmer mistakes, the queries would be directed at a particular interpreter object and only reference terms defined by that object, but if code in L can potentially query multiple interpreter objects in close proximity, it might be good software engineering to have something like a namespace associated with the terms defined within a given interpreter object for K.

3)
Why do you have different names for databases and then overlapping facts? What do you mean by that?

I'm thinking of functors as relations and relations like tables in a relational database. I want to be able to re-use the same base functor name for more than one "table" by qualifying it in some other way. Of course it could be done with an extra argument, but that is not always ideal for either convenience or implementation.

Terminology

Hi,

You wrote:

For the sake or argument, let's say that some statements of the syntactic form maps_as_func(Lfunc1,"kname1") and maps_as_data(Lobject2,"kname2")

I am not sure whether a Prolog system integration would offer such a mapping. To retrieve data from the K Prolog processor in the L host language there are usually the following means:

a) A constructor of the K Prolog processor API is invoked, this might involve a name (for atoms) or not (for numbers, for variables). Or it might involve already available data (for compounds). (Not all APIs deal with variable construction in an annonymous way, but assume now).

b) A parser of the K Prolog processor API is invoked, names are involved similar to for constructors, except that variables now typically have names.

c) A text consulting via the K Prolog processor API is invoked and thus clause data is added to the knowledge base. What names are involved now depends on the Prolog text.

d) A query execution via the K Prolog processor API is invoked and the result is retrieved. What names are involved now depends what kind of query is run against what Prolog text.

You wrote:

Then the namespace issue in item list "1." is about avoiding collisions between either the same "kname1" or "kname2" being re-used at different points in the parent program, or Lfunc1 or Lobject2 actually being short for longer fully qualified names in L that need to be understood and referenced somehow within K to avoid conflating unrelated code or objects.

I don't understand how this should happen. All 4 approaches constructor, parser, consulting and execution basically generate new Prolog terms. And an eventual reference by the host language L is in each time a new reference. Unused reference by the host language can either be explicitly returned via a dispose function or implicitly via garbage collection.

You wrote:

but if code in L can potentially query multiple interpreter objects in close proximity, it might be good software engineering to have something like a namespace associated with the terms defined within a given interpreter object for K.

See above, since the host language gets new pointers anyway by the methods constructor, parse, consult and execute the host language should not be confused about terms comming from one interpreter object I1 versus terms coming from another interpreter object I2. Usually they will be different pointers.

But YES, integrity of the interpreters might be destroyed if a pointer from interpreter I1 is used inside an interpreter I2. But there are more integrity constraints for a Prolog interpeter, for example there are sequencing constaints in the query API etc.. But I don't see that they are related primarily to names.

I'm thinking of functors as relations and relations like tables in a relational database. I want to be able to re-use the same base functor name for more than one "table" by qualifying it in some other way.

You can use the same name accross knowledgebases bases, with different meaning. At least in the model for a Prolog processor
API that I am aware of. In this model with have the following relationship:

   +---------------+ 1    m+-------------+
   | Knowledgebase |-------| Interpreter |
   +---------------+       +-------------+

That is you can have multiple knowledgebases. And an interpreter is uniquely associate with one knowledgebase, whereby there can be one or many interpreters for a knowledgebase (multi-threading). Of course a name has a different meaning in a knowledgebase W1 compared to its meaning in a knowledgebase W2.

The meaning does not influence the API operations constructor, parse they will just return new pointers, and consulting is also not much influenced, except that consulting via an interpreter I1 associated with W1, will of course add clauses in W1 whereby consulting via an interpreter I2 associated with W2, will add clauses in W2.

The meaning difference is most seen when executing a query. A query executed against a knowledgebase W1 might differ in side effect and result compared to a query executed against a knowledgebase W2, when diese knowledgebases contain different clauses. So any name contained in the query might be considered as having different meaning in the two different knowledgebases. The meaning difference happens not only for relation names but also for function names.

The logical consequence relation that is behind execution, if we don't look so much at side effects, is a two place relation, that relates a knowledge base with a query:

    W |- Q S

So a different knowledge base W leads to a different answer substitution S for the same query Q. Interestingly in the Scala solution the Prolog text of a knowledge base is not consulted, but constructed. Well such an approach might also be followed, but I guess it doesn't change some of the above observations.

But there could be a subtle difference, that the constructors are not free in the Scala approach. So instead of constructing just an atom later used as a functor:

    new TermAtom("name")

One eventually does a construction inside a context, which also sees to it to return the same pointer for same names. Namely:

    lookupFunctor("name", parentKnowledgebase)

YES such variations can happen and are found in practical systems. Terms that have variables in it usually are bound to an interpreter context. For example because variables get internal serial numbers dependent on the interpreter. Uninstatiated clauses are usually not seen from the API and are bound to a knowledgebase context.

As result to run the same query against multiple knowledgebases W1 and W2:

    W1 |- Q,    W2 |- Q

The query Q has to be constructed twice.

Bye

P.S.: I use the name interpreter here, but it can be replaced by compiler. I am not assuming that the Prolog processer only "interprets" the knowledge base and the query, it might also compile it to some machine representation etc..

We've gotten really focused

We've gotten really focused on issues related to naming. It seems a small part of the topic to me, but I say that with the intent of asking you whether you see it that way also, and not to be dismissive or curtail discussion.

You wrote:

For the sake or argument, let's say that some statements of the syntactic form maps_as_func(Lfunc1,"kname1") and maps_as_data(Lobject2,"kname2")

I am not sure whether a Prolog system integration would offer such a mapping.

I'm explicitly not focused on what existing Prolog systems offer.

To retrieve data from the K Prolog processor in the L host language there are usually the following means:

The mapping I described would be used in a few different ways, but basically I am imaging that some terms in K are evaluated in a special way, as a kind of callback. I imagine that when this callback is a functor with N arguments then an actual function of L (or the guts of L's underlying implementation) gets called with at least N arguments. The namespace works to make sure that one can non-ambiguously call the right functions with the intended arguments. My thought about returning query output from K is that it involves putting, at the top level, some special known object type on an asynchronous FIFO queue.

I think the text above describes something different than what your message assumes, but it wasn't clear to me where we started talking past each other.

You can use the same name across knowledgebases bases, with different meaning...
That is you can have multiple knowledgebases. And an interpreter is uniquely associate with one knowledgebase...
One eventually does a construction inside a context, which also sees to it to return the same pointer for same names. Namely:

lookupFunctor("name", parentKnowledgebase)

When I first described the idea you are responding to above, I mentioned explicitly that it is an idea apart from Prolog that Prolog would treat by using an extra argument, and that I thought there were reasons to choose a different approach. One of the issues with the form above is that the programmer needs to be aware of the existence of multiple knowledge bases at the time they write code lookupFunctor, whereas namespace constructions are often considered for situations where this overlap is only apparent in retrospect - e.g. some other code can call KB1::lookupFunctor("name") or KB2::lookupFunctor("name") if both are needed together, and it can indicate a default choice when only one or the other is to be mainly used in a given context.

Foreign Function Interface (FFI)

What you describe here, except for the FIFO queue:

The mapping I described would be used in a few different ways, but basically I am imaging that some terms in K are evaluated in a special way, as a kind of callback. I imagine that when this callback is a functor with N arguments then an actual function of L (or the guts of L's underlying implementation) gets called with at least N arguments. The namespace works to make sure that one can non-ambiguously call the right functions with the intended arguments. My thought about returning query output from K is that it involves putting, at the top level, some special known object type on an asynchronous FIFO queue.

Is usually archived by a foreign function interface. I exclude the FIFO since query answers could also directly be populated into a GUI table etc.. And also a FFI does not preclude that it is used in this continuation style. It can also often be used inverted, like an iterator with open(), next() and close().

But lets turn to the naming issue you mention with a FFI. Well there are at least two name spaces involved. The name space of the foreign language, i.e. something like modules or classes, and inside these modules or classes, something like procedures or methods. And there is the name space for the Prolog predicates.

If you only have a couple of unorganized FFI predicates, than you can explicitly map these two name spaces. The mapping can either be done inside the foreign language, when it registers a FFI procedure or method, or it can be done inside the Prolog system, when it registers a FFI procedure or method. For the later approach it is useful when the foreign language has a reflection capability, so that the Prolog system can find the procedure or method at runtime. Otherwise compile time approaches have to be pursued.

Here is an example of such a mapping, from within a Prolog system via Java reflection:

   :- foreign(write_result/1, 'myPackage.myClass', myMethod('Term')).

What do we have in the above:

   write_result/1: The predicate indicator from the 
                   Prolog name space.
   myPackage.myClass: The class from the foreign 
                      name space, i.e. Java.
   myMethod('Term'): The method and formal parameters from the   
                     foreign name space, i.e. Java.

Now if you have a bulk of organized FFI predicates, there are a
couple of methods to do this. Or lets better say how to avoid
doing this. I guess it will never happen that you have a method
for each table, it will rather be the case that there is a
small number of foreign procedure responsible for all tables.

Something along:

  • Open Cursor
  • Issue Select Statement
  • Close Cursor
  • Etc..

For the above we end up with the references I already gave (*). So I guess the problem is more on the Prolog side. Probably we have to put aside the idea that a term P(x,..,y) will access a table P'. Why not use a term of the following form:

   ft(P',[x,..,y]).

ft is an acronym for Foreign Table. You need to implement this binary predicate once, with the help of the above FFI (Open Cursor, Issue Select Statement, Close Cursor, etc..) and you can define what ever mapping you like between P and P'.

You might then implement a goal expansion rule (**), that converts P(x,...,y) into ft(P',[x,...,y]) for execution, so that you can go along and write P(x,...,y) in your Prolog code. Clause expansion and goal expansion is widely available in Prolog systems. You can define a goal expansion rule by hooking into the multi file predicate goal_expansion/2. Something along:

   :- multifile(goal_expansion/2).
   goal_expansion(C,ft(Q,L)) :-
        callable(C),
        functor(C,P,A),
        /* is P/A in Prolog table name space */,
        /* determine Foreign table name Q */,
        C=..[_|L].

You have to provide the check and the mapping by yourself.
callable/1, functor/3 and =../2 (univ) are standard
Prolog predicates.

Bye

(*) SQL Statements as Prolog References:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/08_deploy/09_database/01_driver.html

(**) Clause Expansion
http://jekejeke.ch/idatab/doclet/prod/en/docs/05_run/02_reference/07_theories/02_consult/02_rewriting.html

Interesting. I would

Interesting. I would probably have gone in a different direction with the syntax and the design trade offs than what you are working on. A lot depends, of course, on the use cases that one has in mind. My use cases would be more about adding constructive relational inference to L (Java in your implementation), keeping the type checking of L, rather than trying to embed a full traditional (fully dynamic) Prolog within L.

Type checking of L and K is still done in a FFI

Type checking of L is still done. But the type system of K is not very fine grained. I only showed how to register a method which has as argument an object that belongs but is not necessarely an instance of the Java class Term. Actually the Java class Term is abstract, so there can be no direct instances of this class.

Usually through a FFI you can register a couple of formal parameters types from L that are derived from the data types in K. When K is the Prolog languages these usually contain atoms, variables, compounds, floats and integers. Lets add references as well to it.

Type checking is now done at two time instances. The first instance is during registering, Since Java has reflection it is really checked whether the a corresponding method exists. Also it is checked whether the given arity matches the number of formal parameter. This match can involved counting return types as a special last argument of the predicate and skipping some control parameters, such as a formal parameter of type interpreter.

The second time instance when the type is check is during the invokation of the predicate that has been associated with the method during the registration. Depending on the given formal type in language L, there are some rules for the language K what is allowed and what mapping does happen, whether some narrowing or widening is implied etc.. This has nothing to do with the Java reflection mechanism but solely how the datatypes between the language K and the language L map.

For example an atom from the language K might easily map to a string in the language L. But some Prolog systems that table atoms might also offer other mappings. Then typically the floats and integers of the language K map to the floats and integers of the language L. For variables and compounds of K the API provides datatypes in L so that these datatypes of K can be mapped to L.

The mapping can lead to exceptions. For example when an atom/string is expected and the predicate is invoked with an uninstantiated variable. Then the ISO instantiation error is throw in the language K by, since it is a errorneous call out. No exception is thrown in the language L. But the exception might ripple back to the language L where a call in happened. Other errors than instantiation error might be thrown such as type error, domain error or representation error.

The ISO standard requires that an ISO compliant Prolog features a full exception mechanism. So a decent implementation of the language K will have exceptions. The mechanism is also used in the Prolog language itself to indicate errors of arguments of built-ins, since it does not have type declarations. There are Prolog like languages that have type declarations which would allow compile time checks, but when I hear Prolog I am identifying it with the language defined in the ISO standard.

A FFI for languages with declarations should also be possible. I guess one then would not only register methods but also types, i.e. the mapping between types of K and L. A very tight integration where practically K=L and introducing a type in L automatically introduces it in K is not evident. If you study for example the code:

https://github.com/sonoisa/Prolog-in-Scala/tree/master/prolog

You will find that the data structures of K must implement the protocoll of the class Term. But then in some places it is even a little bit more complex, for example the method unify has two Term arguments. So it is usually not part of the protocol of Term but rather part of the Interpreter protocoll, since it changes the state of the Interpreter.

So if you introduce a new type in L and want to mirror this in K, there are many places that need to be changed. And there are no general rules how a type L should propagate to the protocoll of K. It depends on how you want to see your type L behave in K. In the end you invest a lot of time mapping your types and you will recognize that they don't behave much different than atom, compound or reference.

What would be handy would be a record type in the language K. There are some Prolog systems that have special support for record types. But it is not part of the ISO Prolog core standard. But the support is thin, a record is basically modelled as a compound plus a declaration. You could try adopt this if you are interested in automatic the mapping between L and K. For more information how this is practically done see for example this Prolog system:

The ECLiPSe Constraint Programming System
5.1 Structure Notation
http://eclipseclp.org/doc/userman/umsroot022.html

What kind of types are you interested in having available?

Term Centric Protocoll

Contrary to the strategy of the Scala example, I remember once writing an interpreter by postulating the following protocoll. So making it as Term centric as possible:

public abstract class Term {
    public abstract boolean eq(Term other);
    public abstract int cmp(Term other, Interpreter inter);
    public abstract Term deref();
    public abstract boolean unify(Term other, Interpreter inter);
    [...]
}

The above is also contrary to the Lisp example and to the Haskell example. In the Haskell example we have for example unify : Subst -> (Term, Term) -> List Subst, but nothing via some class mechanism or so. Dito in the JavaScript example, it has also: function unify(x, y, env). The Scheme example is also subject to the same problem. Means people are not very innovative and simply copy each other... (Pun)

But it was not very performant for various reasons, so I abandoned it. But if the objects of your language L implement this protocoll, then they can be used by the language K. The problem that usually renders this approach not feasible is the fact that one might deal with objects from foreign libraries that don't implement this protocoll. One would then need to wrap these objects.

Some better ideas around?

Sketching an example of what

Sketching an example of what I mean to clarify.

The SOCI C++ library is an attempt to make a pleasant embedded interface to generic relational databases, with the capabilities of various actual relational db's exposed through a factory pattern.

The Mercury language is a Prology-influenced language that is compiled, typed with respect to the read/write status of variables, and more declarative than Prolog.

What I am imagining is an embedded compiled language with a query syntax similar Mercury (which is similar to Prolog), special types of functors that are know by declaration to be evaluated as regular function calls in the host runtime for the host language L, and variables which are typed not only by their read/write status but also by inheriting types from L in a way that's similar to the way iterators in C++ STL (of which C++ pointers are a special case) inherit a relationship to the type that they reference. L would "input" queries to K that are typed in the same way (possibly to an asynchronous FIFO input queue) and get back corresponding answer objects (possibly from an asynchronous FIFO output queue) that contain iterators of the the type described. Both how dynamic the embedded K system is and how strong its typing is would depend on the nature of L.

SOCI looks to me like mixing

SOCI looks to me like mixing approaches already mentioned here:

  • Constructor The into construct designates a result set column, the use construct designates a place holder.
  • Parser The skeleton of the select statement is parsed from a string, the parsing I guess is delegated to the database.
  • Query Execution It looks like there are different methods to retrieve the query result, i.e. STL integration and whatever.

Note most Prolog system ALREADY OFFER similar programming interfaces to their system. In principle the toy systems mentioned in this thread, i.e. the Scala, Lisp, Haskell, JavaScript, you name it examples offer already a programming integration with their host language. And also more mature systems that already exist for years, typically offer programming interfaces.

Of course you could make your hands dirty, and start implementing your language K. But it will take you a couple of months to arrive at a non toy level.

So why not go with an existing system, for example to gain some experience first and maybe later implement your own system. I have already mentioned Jekejeke Prolog. Here is a maybe outdated survey that lists more Prolog systems and shows a feature map of their FFI:

http://clip.dia.fi.upm.es/papers/Prolog-FLI-survey-newsletter.pdf

There might be a certain

There is a certain composting of logic languages. I encountered "logic engines" two times in my career.

In one case it was about filling action tables within an Excel sheet that was compiled via VB into a "fact base" of some test tool. Those facts were then used by the tool to verify response data of a system-under-test. Half of the team used it, the other half tried to work around it.

The other time it was a simple "reasoning engine" which was fed with facts written in an "in-house" XML language designed by some guy who left the company. It was very semantic web or so - I don't remember exactly the rhetoric packaging used to sell it to the engineers. There was one fan in the team who kept it alive.

In neither case it was used for anything sophisticated like solving NP complete problems declaratively, but even the little it could do, was done badly or cumbersome.

So the experience curve goes like this: very sophisticated rule based engines usable by only a minority of trained expert programmers are replaced by dumbed down versions of such engines which are meant to be used by average programmers for occasional use which gets replaced by nothing like that at all. The final backtracking step was to dump the backtracking engines into the dustbins and track back to a mixture of procedural / OOP approaches.

This could be seen as an entirely negative result but there was at least a desire for declarative programming methodologies and moving from step 1 to step 2 and becoming "mainstream" if only within an organization, something which is quite a lot.

In defence of cut, or in search of alternatives

I'll just note that it is the simplest mechanism I know of that extends resolution to model the closed world assumption.

Since CWA is pretty frequently wanted, what is there in the way of attractive alternatives?

I'm not sure if that's what

I'm not sure if that's what you're looking for, but there are datalog with negation, e.g. via stratification.

In offense of cut

Prolog cut isn't the simplest mechanism at all -- it is a combination
of committed choice with negation. At the very least we should
separate the two. The main problem with cut is that it is unsound. See

http://okmij.org/ftp/Prolog/index.html#impure


for a thorough explanation. The links after the article describe
alternatives and variations, and the ways to ensure soundness.

Intended semantics

it is a combination of committed choice with negation. At the very least we should
separate the two.

Possibly. But then you would be able to synthesise cut again, so the language in toto is not going to become easier to reason about.

See http://okmij.org/ftp/Prolog/index.html#impure

I had not read this piece of yours and am pleased to have it pointed out to me: it is clever and well-argued, and would probably make good front-page material, especially given it has been 3 weeks since we have had a new story.

That said it is not altogether to the point: I am talking about the case where the CWA is intended and so negation-as-failure is almost certainly the intended semantics. I'm familiar with a fair bit of the literature around LF, so I did know that there are simple, principled mechanisms for doing logic programming efficiently that ditch negation-as-failure.

Furthermore, predicates like var/1 may make the semantics of Prolog hard to understand, but they are essential to how reflection and metaprogramming work in Prolog. It is like criticising Common Lisp because macros can make code hard-to-read: it is not so much criticising one of Lisp's language features, but condemning a whole ethos of program construction.

So to rephrase my question: if we want a Prolog-like language and we want to model a problem using CWA, is there a mechanism that is not much more complex than cut which is cleaner? Which might be the first part of a larger question, can we clean up Prolog without destroying it?

Lee Naish's argument

Lee Naish has argued that without cut or a similar committed choice operator one cannot write any large practical logic program.

Oleg,

I am familiar with George Boolos's Don't Eliminate Cut paper but am unfamiliar with Lee Naish's argument. (I assumed Charles Stewart's "In defense of cut" was a play on Boolos's paper title.) Thanks for the reference.

CWA not only supported by cut

Hi,

The CWA is not only supported by cut. It already starts
with how (=)/2 is implemented via unification. In normal
logic we have:

?- a=b & b=c -> a=c
true

Try this in prolog. So when investigates CWA one has not
only to look at negation but also equality. Domain
independence and Clark's Equational Theory (1978) come
to mind. Unfortunately I am not able to write down in a
few lines what these are all about.

I also read somewhere that we are about to experience
the first semantic web war, to CWA or to open world
assumption (OWA). Given the many dimensions that influence
CWA I guess there are many shades between CWA and OWA.

A language that covers all shades would be useful. I
guess some of the proof assistants, verification or
automation systems around can do it. But retrofiting
Prolog is probably impossible, doesn't it?

Equational logic is expensive

It's not clear to me that the failure to model Leibniz's rule is part of the CWA and not a not-quite-orthogonal design choice made for efficiency reasons. We do know how to extend resolution to encompass Leibniz's rule, and it seems to me that the CWA makes perfect sense together with Leibniz's rule.

Equational Logic vs Logic with Equality

It seems that the term equational logic is a rather a new term, and not exactly the same as some logic with equality. Actually I wanted to stay first order and point out that Prolog is not based on FOL_= but rather on FOL_CET where CET is the Clark Equational Theory.

Leibniz's rule, if stated as s=t -> (P(...s...) -> P(...t...)), neither fails in FOL_CET nor in FOL_=. In pure Prolog if s and t unify and the call P(...s...) succeeds, then the call P(...t...) also succeeds. Whether Leibniz's rule is then stated as an inference rule or an axiom is not essential, some quantifier shuffling makes them the same.

What makes FOL_CET partly CWA is that =/2 is fixed, compared to FOL_=. We cannot have =/2 on the left hand side of the consequence
relation in Prolog, since FOL_CET is categoric on (=)/2 and having it there therefore woudn't make sense. But you are right, resolution for FOL_= is also around, i.e. para-modulation etc...

But then in Equational Logic more happens. It is essentially higher order, for example the Equanimity rule, we have equality between propostions. This is not anymore FOL. But higher order logics can be subject to the same equational problems as FOL, and thus being rather OWA than CWA.

But if we mingle to much with HOL, and fix equality similarly as is done by CET for FOL, we end up with something that is close to CWA concerning equations. For example in set theory, via extensionality, equality is bootstrapped from the membership relation. But I havent much looked into HOL concerning domain independence etc.. There is a notion of absoluteness in set theory, which could eventually cover some of the concerns.

Bye

P.S.: Equational OWA is useful for solving murder riddles. Bob saw Alice carring a dagger. Carlo saw Eva running away from Debby, the victim. It later turns out that Alice, resp. Eva was the murderer, but they were known by different names to Bob and Carlo.

P.S.S.: And this is how equational OWA makes the simple negation as failure wrong. Take the train table example. There is no train from Ragusa on the timetable, therefore today no train from Ragusa will arrive? Wrong, what if Ragusa is a different name for Dubrovnik, and a train from Dubrovnik is on the timetable?

See Schroeder-Heister on definitional reflection

Schroeder-Heister has written quite extensively on the logical principles of definitional reflection/closure, which IMO serves as a good logical foundation for the closed-world assumption. The basic idea is that if you assume that a set of clauses define an atomic proposition, then that justifies (in the Martin-Lof/Prawitz/Dummett sense) an elimination principle for them. Basically it starts to give atomic propositions some actual logical content.

(I've been meaning to look at definitional reflection again to see if it can also be used to give a better account of datatype declarations in ML and Haskell than the usual method of desugaring them to sum/product/recursive types. I've been implementing a language, and have come to dislike giving semantics by elaboration.)

On an unrelated note, Girard discusses negation-as-failure in The Blind Spot, though I forget what he said about it (it was not wholly uncomplimentary, which I guess means he likes it).

Indeed

Dale Miller has thought about this in the context of uniform provability, with applications to logic programming. I don't know where this line of work went.

I dare say it is worth digging out those notes of Girard. I never did get around to reading them.

A real basher

Girard seems to be a real basher on Prolog:

http://iml.univ-mrs.fr/~girard/coursang/coursang.html
(corsang1.pdf, 4.D.4)

"[...] The amateur logicians recruited by hundreds
around the fifth generation wrote whatever came to their
mind on this. For instance that a query that does not
succeed is false. Since non-success in PROLOG est recessive,
one is in front of a non axiomatisable notion, the closed
world assumption or CWA. [...]"

"[...] Too much joggling with negations, and one slipped up
the hands : provability was mistaken with truth in a
professed smallest Herbrand model. What is factually
true for formulas ∃x1 ...∃xp(R1 ∧...∧Rq), but which is
a conceptual nonsense. Such an error of perspective
mechanically entailed a conceptual and technical
catastrophe : the truth of a universal formula in a
bizarre model, what is it, exactly ? It is the CWA, a
pretext for ruining a lot of paper and for discrediting
an approach after all interesting and original. [...]"

Instead of disputing the charges, I will go about
and buy the following book, to generally cheer me up:
Formalizing Common Sense: Papers by John McCarthy
(Ablex Series in Artificial Intelligence)

But I guess one can draw an analogue between uniform proofs
and polarized proofs, later found in the tome. (Didn't verify)

Vulgar proof theory

At least part of Girard's complaint about Prolog is that its theory makes use of structural proof theory in a very coarse and unrefined manner - he's criticising the Prolog crowd for being vulgar logicians, not bad programmers. And I guess he's particularly sharp about the kind of logician who passes off work on the theory of Prolog as being a contribution to proof theory.

He's been much friendlier about work on logic programming coming from the contribution of people like Dale Miller and the uniform provability crowd, and has said flattering (by his standards) things about Jean-Marc Andreoli's work on focussing proofs.

Girard's point connecting the CWA to least Herbrand models is well put: thank you for posting that. I'll defend it so: it is perfectly legitimate to model a problem in this way if you know what you are doing. Herbrand models, least or otherwise, aren't the private property of logicians.

I guess one can draw an analogue between uniform proofs and polarized proofs

If polarised proofs are the same kind of thing as focusing proofs, then there is a connection.

Collapsible

I saw this term in John McCarthy's writing. He deals with
Circumscription and not with CWA. There are subtle
differences and there are also overlaps.

Idea is that although some of these concepts (CWA,
Circumscription, etc..) are inherently not only non-
monotonic but also higher order and/or hyper arithmetic.
There are collapsible cases, i.e. where matters become
first order and/or semi-decidable.

So if Girards focus is on linear logic and its perfection,
ignoring many application areas of logic, then it is clear
for me that Girards blind spot are all these results. If
these results are formulated proof theoretical than they
contribute to proof theory, despite what Girard values. if
these results are done model theoretic, then they contribute
to model theory.

Here is an example of a nice proof theoretic result:
Take the Schroeder-Heister formulation of definitions,
most probably inspired by negation as failure, I guess
we get an easy cut elimination of definitions. And thus
consistency of theories extended by definitions. There
are a couple of other ways to show this, but this
looks nice. (Didn't verify)

Structural proof theory is also possible to do without
the introduction of exponentials etc.. there have been
for example results about contraction etc.. before Girard.
Eventually one more blind spot of Girard. But I must admit
Girard had a positive impact on logic, here and then one
sees nice expositions successively building on subsets
of linear logic.

But I guess one has to find the right balance between
the means and the end. (*)

Bye

(*) You probably don't take the airplane to fetch
some bread around the corner.

Academic Freedom, response to Charles Stewart

There is some inconsistency in either Girards original view or your interpretation of it. I consider Andreoli also part of the Prolog crowd, he developed his Linear Logic stuff while at ECRC, Munich, right?

But I guess that Girard or you forget that there is a notion of academic freedom, or lets better call it there should be room for unconditioned explorative research if one desires (which ECRC, Munich was able to provide I guess). Labeling some proof theory as vulgar versus non-vulgar automatically gives a special status to the non-vulgar proof theory.

So that there is the danger that we arrive at a point of mental inertia, because we believe that we have found the holy grail. If we spinn this further like some islam has found mohamad or some christians have found jesus, we might start a relgious war.

Although linear logic is appealing, the two polarities are like matter and anti matter and suggest a first principle that cannot further be reduced (kind of a more radical bivalence than already found in Aristoteles), but one never knows what else might come in proof theory. Remember Πάντα ῥεῖ (panta rhei) "everything flows".

But my main argument against dogmatism runs as follows. Although powerful first principles might be very useful, there is a danger in a fixation on a particular set of first principles. Namely an emergent phänomena might not only have one reduction. Theoretical computer science was very successful in showing that: Take the phänomena of computation and the reductions to turing machine, lambda calculus, etc..

That's also why I read the title "LtU" of this forum rather ironical than verbatim, won't you?

Bye

Some publications from 1991 - 1994 by ECRC:
http://plus.kaist.ac.kr/~kwang/paper/others/ECRC.techreports

ECRC viewed as an internet pionier
http://de.wikipedia.org/wiki/ECRC

An error of perspective

I have expressed myself badly if I there is a suggestion in what I wrote that the criticism of some work in logic as vulgar is something like defending a citadel. It is rather about people who pick up theories and insights and use them in a vulgar way, failing to really appreciate them - I could lift Girard's words: "an error of perspective mechanically entailed a conceptual and technical catastrophe". He is criticising a kind of error of taste that can undermine the judgement of whole cliques of scientists. This part I agree with, even as I agree that vulgarity sometimes gets results.

I certainly don't regard myself as being a Girardian, if that means revering whatever comes from Marseille.

Just a Carricature

The picture that Girard draws is just a carricature. And has maybe the same value like when today somebody draws a carricature of Merkel and Sarkozy. It raises some emotions, but then one can proceed as usual.

But I agree that there can be an error of perspective, respectively a too narrow perspective. Take for example this thread, and my pondering that CWA involves an ingredient that has to do with equality and for example your response here.

So why is there still such a lack of a widely available full understanding of the programming language Prolog. Probably you are also right here, that the vulgar reception of Prolog, especially the many light handed introductions to Prolog that are offered to miriad of students by professors all over the world do probably some harm.

But historically Prolog is often explained based on resolution theorem proving. Contributions from for example the Dale Miller camp take an other route and identify the minimal logic resp. linear logic in Prolog. These new explanations and partly new discoveries did not yet find the way into the mainstream.

I guess it will take a couple of years and we will have a different view point here. There is a little danger that the homework is not correctly done, I have the feeling that an alternative perspective has not yet been fully worked out and is not yet available in one piece of work, but I would appreciate pointers. Non-dogmatism helps here.

The danger is in a drifting away and a possible abandonment of Prolog altogether, for example in favor of the many fancy dependent type systems. Very exciting scientific thriller to watch over the next years.

Still there is implication and equations

You name it Schroeder-Heister, Robert Stärk (1989), etc.. it all amounts to Clark Completion (how to deal with implication) and Clark Equational Theory (how to deal with equation). Lets first show that Robert Stärks axioms are essentially Schroeder-Heisters inferences rules. Robert Stärk says (*) (now only looking at the propositional case):

Section 7.1:

     D_1 -> P
     ..
     D_n -> P

Section 7.2:

     
     P -> D_1 v ... v D_n

The former axiom is already seen in Schroeder-Heister (**), the implication is just written the other way around. The later can be turned into the following inference rule and vice versa:

     G, D_1 |- C    ...    G, D_n |- C
     ---------------------------------
                G, P |- C

So much for the implication. But what happens with the equations? We only looked at the propositional case. Robert Stärks approach is extrem since it confronts us with an infinite axiom system, just instantiating the axioms based on the term model.

But CET is present in 5) and 6) of Robert Stärk. On the other hand Schroeder-Heisters rule with variables is directly defined via some mgu and does not have equation in the first place. On page 19 he then discussses what a definition X=X would do. He basically shows that it implies Robert Stärks 5) and 6).

Not sure whether this tie could be easily broken for Schroeder-Heister, except if we mix the definition part with arbitrary logical reasoning. For example would like to be able to reason as follows, which is rather unlikely to be done directly in the discussed definition framework:

   P(a), a=b |- P(b)
   P(a), a=b |/- ~P(c)

Bye

(*)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.2393

(**)
http://esslli2009.labri.fr/documents/InversionPrinciples07_esslli.pdf

Thanks!

I wasn't aware of Stark's work before, so now I have something more to read. :)

The SOCI approach is

The SOCI approach is apparently different than what you are thinking of in a few different ways. Some of those ways are relevant to our discussion and some are not. There is no parsing involved, but that's not too relevant. What is relevant is that "into()" and "use()" are fully typed by L (C++ in this case) and work with the actual C++ variables designated. SOCI used typed wrappers which know how to data conversion between C++ types and SQL types for some set of standard choices, and it provides an interface to adding custom object mappings.

SOCI is designed for talking to relational databases, so it is natural to assume that data needs to be serialized in order to be passed between a program and a database, and so it is general to access collections serially via iterators. However, here I mean to be discussing design of an ideal embedded language, so for passing something in a collection type data structure to a Prolog like thing, it would be interesting to see if the data can stay in the efficient data structure and be accessed from where it is as needed (assuming it is read only). That idea again leads to the desirability of read/write typing. Being able to access facts based on data in a relational database - jit as needed by a query - would also be an interesting feature.

So why not go with an existing system, for example to gain some experience first and maybe later implement your own system. I have already mentioned Jekejeke Prolog. Here is a maybe outdated survey that lists more Prolog systems and shows a feature map of their FFI:

http://clip.dia.fi.upm.es/papers/Prolog-FLI-survey-newsletter.pdf

The use cases I am most interested in might well be different than the ones that Jekejeke is designed or optimized for. But I'm independently interested in your presentation of what you think the most interesting use cases for embedded Jekejeke or any other existing Prolog system are. You could describe them here or make a new thread. That survey paper would also have benefited from examples illustrating the concrete details of what they are abstractly (and subjectively) classifying.

Not specific to relation languages resp. Prolog

However, here I mean to be discussing design of an ideal embedded language, so for passing something in a collection type data structure to a Prolog like thing, it would be interesting to see if the data can stay in the efficient data structure and be accessed from where it is as needed (assuming it is read only).

This is indeed possible if the language K exhibits a data protocoll which can be satisfied by the language L. See this response here. If no such protocol is available we must shift data around as in SOCI. There are then basically 4 technical use cases. Technical use cases are the means for the technical interactions in your business use cases/workflow of your application which is to satisfy the business case of your customer. Lets abstract from FIFO/iterator issues for the moment:

  • Interpreter allocation
  • Function registering
  • Call in
  • Call out

See the concepts described here ff.:
http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/03_interface/05_concepts/02_interpreter.html

What technical use cases do you have in mind?

Please note that all the Prolog Forreign Function Interfaces (FFI) have typed "into"/"use" in some way or the other. "into"/"use" are part of both the Call in technical use case and the Call out technical use case. In both use cases data might flow from L to K and vice versa. But "into"/"use" are sub steps in the technical use cases and are not considered technical use cases here in itself.

Here is how a typed "use" can be done for a float and for an atom when L=Java:

     
      /* query construction */
     ... new TermFloat(<language L float>) ...
     ... new TermAtom(<language L string>) ...

And here is how a "into" can be done for a float and for an atom when L=Java:

     /* result destruction */
     <language L float> = ((TermFloat)var.deref()).getValue()
     <language L string> = ((TermAtom)var.deref()).getValue()

It has a similar safety like the SQL interface SOCI. In SOCI you
can specify a flag holder for an into. And inspect the flag whether
a null value was the result, or whether a coversion error occured
in the result, or whether the value was successfully submitted.

A Prolog system is usually stricter. It does not support the many conversions that an SQL API usually supports, i.e. string to number and vice versa. Although you can retrieve from the SQL API the native column type. In a Prolog system you get an object which belongs to some class along the Term hierarchy.

In the simple case as above you simply cast to what type you expect. But I guess some trickery with Java generics might eliminate some keyboard strokes needed to put down the code. Eventually with C type templates the most keystrokes can be saved. But you said yourself the language L should be a determinant of the interface.

So I guess our whole discussion is not about Prolog the language K, but about the language L. Since the FFI interface is usually written in L itself, changing L also changes the possibilities for building the FFI. So maybe you found an interesting case for the application of C templates. Or for type inference in general.

But I think it is not very specific to a relation language or Prolog. Any interfacing problem with a variety of types would do. Imaging interfaceing with MatLab. The exact same questions pop up.

When I wrote "use case" I

When I wrote "use case" I meant it with the common usage of "Here is an application programming task that this software module would be particularly useful for." In the case of your jekejeke, it would be something that a Java programmer wants to do that is cumbersome to do in native Java.

Most of data conversions in SOCI are designed and coded by a library programmer who is writing the factory implementations for a particular database backend. The appropriateness of the type conversion, and whether or not a round trip store and retrieve from the database is always bijective, is something that, from the POV of the SOCI user, is determined by the correctness of the library programmer's implementation. For example, if the programmer is storing a signed 64 bit integer and a given database didn't support such a type natively, then a correct backend implementation should convert to and from strings in order to maintain a bijective mapping between the application and the database. I have no association with SOCI and was not proposing it an ideal design - there are many things I would have done differently. It was just brought up as an example of relatively clean "query" interface that works with the native types of the library client and is optimized for the convenience of and efficient use by the library client.

Coming back to jekejeke, it would help me to understand your POV better if you'd provide some examples of both "use case" in the general sense and what you mean by "technical use case" to show where you think jekejeke would be particularly appealing.

Nothing specific to Jekejeke Prolog

In the case of your jekejeke, it would be something that a Java programmer wants to do that is cumbersome to do in native Java.

I am more thinking of "make or buy" scenarios that would make a business case for the integration of various components. And of course I am happy if I don't have to care in which language a component is implement. This is slightly different meaning than "cumbersom", and more in the spirit of what CORBA tried to archive in the early days. The free posibility to mix and match arbirary components. But I am heading more for a tight integration in the first place and not an RPC like integration, i.e. I am interested in the embedding/library idea.

But I am not advocating that Jekejeke Prolog implements something different from the main-stream. I have already mentioned the main stream in this post here. If you look at the paper cited there, you will find a more fine grained discussion of FFIs.

http://clip.dia.fi.upm.es/papers/Prolog-FLI-survey-newsletter.pdf

The 64-bit example where a conversion to a string happens is a good point in favour of a broader mapping utility inside the FFI. Which is not so much a problem for Prolog systems since they anyway feature arbitrary long integers. But a type mismatch happens for example in the area of decimals, many databases feature large decimals, for example oracle with up to a mantissa of 36 digits in the old times. But Prolog systems have not adopted this type. Here Jekejeke stands out since it has a arbitrary long decimal datatype. It is internally derived from java.math.BigDecimal.

But this feature, the data mapping, is on another level than the technical use cases. It is a property inside the technical use cases I have already mentioned. The paper does not distingusih between these level of aspects, it does not discuss the different criteria in a hierarchical way, like for example first checking what technical uses cases the various Prolog system and then looking into the details how the technical use cases are supported.

Here is a little account how the technical use casse are covered by the paper. This corresponds probably also to the average awareness that the author had at the time of writing. Most likely influcended by the systems he considered an their state of the art at the time (2000). Here is the little list already mentioned here:

  • Interpreter allocation: not covered by 3.1 Data Interface, not covered by 3.2 Control Interface, not covered by 3.3 Compiling and Linking Procedures, not covered by 3.4 Miscellaneous
  • Function registering: not covered by 3.1 Data Interface, not covered by 3.2 Control Interface, partly covered by 3.3 Compiling and Linking Procedures, partly covered by 3.4 Miscellaneous
  • Call in:: covered by 3.1 Data Interface, covered by 3.2 Control Interface, partly covered by 3.3 Compiling and Linking Procedures, partly covered by 3.4 Miscellaneou
  • Call out:: covered by 3.1 Data Interface, covered by 3.2 Control Interface, partly covered by 3.3 Compiling and Linking Procedures, partly covered by 3.4 Miscellaneou

So we see some weakness in the first two technical use cases. So we would need to consult other sources to see what is around. The first technical use case is tied a little bit to the aspect whether your language K is supposed to be multi-threaded or not. A little blind spot I have already mention early on in this thread. But which we have more or less resolved during the discussion.

Here is a FFI example for multi-threading:

http://www.sics.se/sicstus/docs/3.12.7/html/sicstus/Another-Multi-Threaded-Example-_0028Prolog-Top-Level_0029.html

You find all kind of "Interpreter allocation". Their is a data type "Prolog" and a data type "SICStus". I can not tell you so much about these. It is not exactly the same design as in Jekejeke Prolog. Most likely the SICStus object corresponds to the Interpreter object in Jekejeke Prolog. And the Prolog object corresponds to the CallOut object in Jekejeke Prolog. But these would be the details of the technical use cases, important is that there is this concept and that we do not build upon some notion of a globally available Prolog system or Prolog application.

Next comes "Function registering". This was to some extend part of your bullet list, namely the issue of namespace related to predicates. Again the aspect is not extremly good covered in the paper. This is a result of the globally available Prolog system or Prolog application view. If the Prolog system or Prolog application is globally evailable, then of course the predicates inside it are also globallay available. This amounts to the "external" keyword of C and the linking of C against your application with the Prolog system or Prolog application.

What I have tried to convey is a more dynamic "function registering" model. It assumes in the first place a dynamic interpreter allocation, and underlying a dynamic knowledge base allocation. From this "function registering" is derived as dynamically establishing a relationship between two objects. The function of the language L and the predicate of the function K. The relationship is usually only used in the "Call out" scenario when the Prolog system or Prolog application calls the foreign language. In the "Call in" scenario, when the foreign language calls the Prolog system or Prolog application, the foreign language simply picks the desired predicate name when building the query against the interpreter.

But we find systems that skip the technical use case of "function registering" and use the same approach for "Call out" as for "Call in". Pick what you need and do what you need. This is seen in the last part of the SICStus example. We have there:

     :- use_module(library(jasper)).
     main:-
             jasper_initialize(JVM),
             jasper_new_object(JVM,
                               'MultiSimple2',
                               init,
                               init,
                               Obj),
             jasper_call(JVM,
                         method('', 'CallBack', [instance]),
                         'CallBack'(+object('')),
                         'CallBack'(Obj)).

So the "Call out" happens in that the Prolog system dynamically looks up an object instance and then dynamically invokes a method of this object instance. No registering of a function happens. There is one little drawback of this approach. When we have a separate "function registering" technical use case, we can already do some validation during this step. In the case of Jekejeke Prolog, and in the case of some other Prolog systems, the "function registering" is done in a directive fashion. So when these directives succeed we know that we have established a valid mapping, so that we don't get some runtime errors concerning the mapping during our "Call out". Here is how the same would look like with function registering. (*)

:- foreign(callback/0, "MultiSimple2", 'CallBack').

main :- callback.

In the SICStus example, where this separation is not seen, we might get exceptions at runtime that either stem from invalid FFI mappings or from errors inside the "Called out" objects, when these execute. For example we might get an error at runtime when the "MultiSimple2" class is not available at runtime, since it was not put into the class path or whatever. In the "function registering" technical use case we would get the error already at consult time of the little Prolog text that does the callback.

Bye

(*)
Currently one would need to redesign the code a little and make 'CallBack' static and no separate process would automatically be spawn. This could be done inside the 'CallBack' implementation if really needed.

Logical Metaphysics

Why is Prolog such a polarizing subject? We really shouldn't blame Prolog for this. The problem has to do with many unresolved issues in logic itself. The subject of "logic programming" has put these issues into sharp contrast. This is what I mean. Consider two old papers from the early days of Logic programming. The first is Kowalski and Emden, The Semantics of Predicate Logic as a Programming Language , and the second is Non-Resolution Theorem Proving.

Here we have two entirely correct but contrasting visions of what logic is and what it can do. One has a practical foundation and the other is more theoretical. On the one hand we have model theory and algebra and on the other we have the school of Frege and Russell. It is becoming clear already in the early years of the twenty first century that this is nothing but bad metaphysics. Perhaps it is time to clean up the shop, and throw out the trash?

Leave Behind Classical Logic

I guess we must be aware that over the last 50 years probably some progress has been made in understanding non-classical logics and putting them to use. But there has been even further progress in the form of linear logic, since it deals with a much deeper idea than only refuting the excluded middle.

If I look at the two papers, and the two contrasts they represent. Namely resolution theorem proving and non-resolution theorem proving, then I find that there is no awareness for classical vs. non-classical logic in them. I guess in both cases logic is identified with classical logic. The non-resolution theorem paper also lacks a little bit in its promis, since it uses much of terminology and apparatus from resolution theorem proving, i.e unification, skolem etc..

But how can we convey the feeling for the two approaches? Without looking at the idea whether something is classical or not for the moment? The view of resolution theorem proving I like best is the one of the thinking soup. We have a soup of "clauses", which might collide and reshape into new "clauses". There is basically only one collision/reshape rule, namely the resolution step.

On the other hand the picture I like most for non-resolution theorem proving is the one of a Gentzen proof. Namely we start with a set of premisses and conclusions, and then built a proof tree. There is not anymore a single rule that says when a node in the proof tree is valid, but a whole set of rules. The rules are sometimes grouped along the connective they deal with.

Now when Prolog enters the stage, for the thinking soup, the viewpoint is typically that some "clause" shapes are excluded, i.e. everything non-horn and as a consequence some collision patterns can be preferred i.e. input resolution, where at least one of the "clauses" has to be from the initial soup, can be pursued. But conceptually also something else happens. The original means of classical logic is not anymore needed in full for the new end.

But Prolog can also enter the stage in the Gentzen proof world. And if worked out correctly it becomes much more clearer there that the full terrain of classical logic is not anymore needed. And one can then also clearly work out the logical limitations of Prolog. Unfortunately in the case of Prolog, applying linear logic doesn't
give any further insight about the logical limitations in my opinion.

I have rather the feeling when applying linear logic we get some insight from below, if we compare Prolog with more primitive languages. So it shows us more reductions, but it wouldn't for example explain better some of the para-consistency or para-completness properties of Prolog, which we can already explain by applying for example minimal logic instead of classical logic.

But the reductions are also of interest, since they can be transfered back to minimal logic, and give us a deeper insight why certain Gentzen proof tree methods are possible. These are then not anymore meta-logical properties about admissibility of certain conclusions but meta-logical properties about proof objects. Which puts us again closer to programming languages and lambda calculus.

The later is the reason why I expect that the resolution theorem proving explanation of Prolog will be abandoned in the near future by the mainstream in favor of another explanation. But I am not sure whether this coincidences with your "clean up the shop".

Bye

P.S.: It is also not that easy to design a thinking soup for intuitionistic logic from start. There is an attempt in:

Basic Proof Theory, 2nd Edition
A.S.Troelstra & H. Schwichtenberg
Cambridge University Press, 2000
Section 7.5: Resolution for Ip

But not sure whether somebody is using it.

Neoclassical logic

As you point out the two approaches seem to have a lot in common; so why is it such a big deal. I think it has to do with the intent of the practitioner not with logical theory. Non-resolution is an inductive agenda, while resolution is deductive. This is why metaphysics is important. Logic is not really a self contained answer to everything. You can't solve logical problems simply by being meta-logical. Logic is not the foundation of everything, not even of mathematics.

But the inductive and deductive categories have also failed to solve our metaphysical dilemma. Personally, I like Pragmatism and its close cousin Cybernetics. And since this is about logic we should probably mention Modal logic, the brain child of the last great pragmatist C. I. Lewis, introduced as a counter argument to Principia Mathematica. Apparently Lewis thinks that possible and necessary are better categories than T or F. It makes sense if you think pragmatically.

Same Skeptical Reasoning

If Non-Resolution would be on the inductive agenda, then there would be something wrong. By changing the explanation of Prolog we don't want to loose some fundamental properties of the ascribed underlying logical reasoning. Resolution or Non-Resolution, both should model the same skeptical reasoning for example in terms of answer computation.

But of course when somebody sees this thread, which contains a couple of inquiries into the explanation of Prolog und the ascribed underlying logical resoning, one might loose track and propel one self into spheres with a different frame and questions. And exhilarate on revolutionizing these spheres.

But back to the Prolog sphere, I guess the revolution already happened. But it did not yet reach the main stream. And maybe some of the revolutionaries (Girard, etc..) are simply frustrated that they were not allowed to start from scratch, and that Prolog was already tainted by their precursors.