Prolog and Logic Programming Historical Sources Archive(softwarepreservation.org)

Prolog and Logic Programming Historical Sources Archive

http://www.softwarepreservation.org/projects/prolog/

8 comments

triska6 anni fa

Very interesting, thank you for sharing this!

Knowing the history of Prolog can be very useful to make progress in this area, because quite often, progress in this area means returning to what earlier systems already did.

For instance, already in the very first Prolog system, Marseille Prolog, a string like "hello" was treated as a list of characters, i.e., [h,e,l,l,o]. This was great for usability, as one would expect from a language that was designed for natural language processing.

Later systems switched this to lists of character codes, denoting code points in the used encoding. For instance, when using ASCII or one of its supersets, "hello" would then mean [104,101,108,108,111], which is much less readable in answers.

Still other systems introduced their own ad hoc types that were not lists and therefore could not be handled with Prolog's built-in mechanisms for reasoning about lists, most notably Definite Clause Grammars (DCGs), and thus even required their own dedicated and usually moded predicates for reasoning about them, thereby severely limiting their generality while increasing the complexity of application code.

Only the most recent Prolog systems, such as Tau Prolog and Scryer Prolog, are now doing what Marseille Prolog did, namely treating strings as lists of characters, and are also beginning to combine this with efficient internal representations to finally get all advantages at once: usability, generality, simplicity and efficiency.

Type checks are another example where Prolog systems are now going back to the solid foundations of Marseille Prolog, after decades of errands. For instance, to preserve monotonicity of Prolog programs, type checks must raise instantiation errors or delay the check if no decision can be made, e.g., the following would be a logically well-justified response because X can still become an integer:

    ?- integer(X).
    ERROR: Arguments are not sufficiently instantiated

This is also what Marseille Prolog did, for very solid reasons that were very clearly outlined by Battani and Meloni. Prolog vendors soon found out that Prolog systems would sell better to customers who did not care about logical properties if such — to them strange and likely worrying — errors were not shown, and opted to instead answer such queries with silent failure, which is logically wrong and prevents for example declarative debugging techniques and different execution strategies such as iterative deepening:

    ?- integer(X).
    false.

Now, logically sound type tests are appearing again in Prolog systems. For instance, Scryer Prolog already ships with library(si), where we have:

    ?- integer_si(X).
       caught: error(instantiation_error,functor/3)

This is correct: We get an instantiation error, because no definite answer can be made at this point. X can become an integer, or a term that is not an integer, so answering either "yes" or "no" would not be appropriate, because the type of X cannot yet be determined.

A third example for this are constraints like dif/2, which is a relation with very desirable logical properties, denoting syntactic disequality of terms, i.e., it is true if and only if its arguments are different, and it delays checks until a definite decision can be made. This was present even in the predecessor of Marseille Prolog, Prolog 0, and then treated at best as a strange curiosity or not present at all in many later systems before it became more widely available again.

Using constraints also enables an even more elegant solution for the above cases. For instance, using CLP(ℤ), constraint logic programming over integers, we can constrain a variable to integers in the most general way:

    ?- X in inf..sup.
    X in inf..sup.

Another very interesting aspect is the commercial context in which these systems were developed. There was a lot of money involved, Prolog vendors would give you a licence for thousands and tens of thousands of dollars, and still do today. Not that long ago, when you did a research project as a university student in cooperation with one of the Prolog vendors, the vendor would personally fly over and hand you a hardcopy of the system manual. Then, after you finished the project, the vendor would visit you again to take away the manual.

YeGoblynQueenne6 anni fa

    ?- integer(X).
    ERROR: Arguments are not sufficiently instantiated

Can you explain how raising an error preserves the monotonicity of a program?

Perhaps it's habit, but I expect integer(X) to fail rather than raise an error because X is a variable and not an integer. I'm not sure what the ISO standard says here, but if integer(X) fails this is a natural way to test the type of an object:

  test(X):-
    integer(X).
  test(X):-
    var(X).

Otherwise you have to order the two clauses carefully to avoid an instantiation error.

Also, the following is consistent behaviour:

  ?- integer(X).
  false.

  ?- var(X).
  true.

Whereas this is not:

  ?- integer(X).
  ERROR: Arguments are not sufficiently instantiated

  ?- var(1).
  false.

triska6 anni fa

Suppose integer/1 does not raise such an error. So we have:

    ?- integer(X).
    false.

Here, the system tells us: “There are no solutions whatsover.“, because this is what "false" means: No solutions whatsoever. But that's wrong, because in fact there are solutions, as we can also verify:

    ?- integer(0).
    true.

So, in fact there are solutions! But that's not what the system said initially. So, this means that we can no longer rely on what the system is saying: In the above example, it tells us that there are no solutions, even though there are solutions.

By monotonicity, I expect that if a query succeeds unconditionally, then a generalization certainly does not fail (otherwise, adding a constraint would increase the set of solutions). But this is obviously the case here, so monotonicity is violated: Adding a constraint can make a query succeed that previously failed.

    ?-        integer(X).
    false.

    ?- X = 0, integer(X).
    X = 0.

If an instantiation error is raised, then that clearly indicates that no decision can be made at this point, whereas "false" means that there are no solutions whatsoever, which in this case violates monotonicity, a core property we expect to hold when reasoning about logic programs.

If monotonicity is broken, then iterative deepening is no longer applicable, because increasing the depth of the search may now invalidate conclusions that were derived earlier. However, one of the foremost attractions of Prolog is the prospect of executing the same program with different evaluation strategies.

And, yes: The above behaviour of integer/1 is in fact prescribed by the ISO standard. Unfortunately, DEC 10 Prolog chose to replace instantiation errors by silent failures, and this has been perpetuated in the Edinburgh tradition for type tests including the standard.

A way to correct this is therefore to introduce a new family of type tests, the ..._si/1 family of predicates as available in library(si). They are what the standard type tests should have been in the first place to preserve these desirable logical properties.

YeGoblynQueenne6 anni fa

>> By monotonicity, I expect that if a query succeeds unconditionally, then a generalization certainly does not fail (otherwise, adding a constraint would increase the set of solutions).

Thank you for clarifying. If I understand correctly you are saying that the success set of a query should increase monotonically with the generality of the query. If so, I don't think that's an unreasonable demand, but I do think it is a bit ideological, given that normal _programs_ are non-monotonic anyway (because negation as finite failure is non-monotonic).

Now, I have to point out that both type-checking and errors are extra-logic features of Prolog (there are no types in first-order logic and of course there are no exceptions). In that sense, it's a bit arbitrary how a predicate "should" be defined. The decision must be made in the context of Prolog, not logic, and the needs of Prolog as a programming language.

In that context, the problem that I see with raising an error on "integer(X)" is that integer/1 is performing a type-check in the context of the datatypes recognised by Prolog. So it makes sense that it should succeed when its argument is of the "integer" datatype and fail if its argument is any other datatype. In this context "X" is not an uninstantiated term, but a term of type "variable", where variable is a Prolog datatype, like "integer".

I think of it as a membership test. If the argument of integer/1 belongs to the set of integers, then the query should succeed. If not, it should fail. A variable is not in the set of integers, so the query should fail.

I also suspect that iterative deepening and, indeed, any kind of nondeterministic program, would be made a lot more complicated if type checks raise errors left and right (a problem you've highlighted with respect to Prolog meta-interpreters and instantiation errors raised by clause/2 in another discussion we had here I think).

Personally I dislike errors: not only are they extra-logical, they force the programmer to add all sorts of boilerplate to her program to handle them and make for code that is harder to read and parse at a glance. The automatically caught exception in Scryer Prolog that you list above is even worse to my mind: it enshrines the boilerplate in the behaviour of the language (if I understand correctly what is being done). So now errors are a first-class citizen of the language. That's awful! I would much prefer a language that helps the programmer identify and eliminate programming errors _before_ the program gets to the point where it has to exit abnormally.

mthom6 anni fa

To be clear, the "automatically caught" exception Markus lists in his integer_si example was caught and displayed by the Scryer toplevel.

falsissime6 anni fa

There are already many built-ins that behave in exactly the same manner as integer_si/1 does. Take T =.. [F|Args]. which produces an instantiation error, idem functor(T,F,1).

The nice thing when you have (such) errors is that if they do not happen you can be sure that the result is correct (in an appropriate pure subset). Without errors, you never know.

YeGoblynQueenne6 anni fa

With univ, it makes sense to raise an error because its first argument becomes the predicate symbol of an atom and you can't have an atom with a free variable as a predicate symbol in a first order language (because it wouldn't be a first-order variable anymore).

What I mean is, if:

  A =.. [P,X,Y]

Did not raise an error, it would produce an atom:

  A = P(X,Y)

Which is not a first order atom. So that would violate core assumptions of the language and the syntax of first-order logic to boot.

(I use "atom" in the non-Prolog sense, to mean a predicate symbol followed by terms in parentheses).

Edit: that said, Win-LPA Prolog allows P(X,Y), but that is a quirk of the interpreter and not standard at all.

falsissime6 anni fa

(I do not agree, but let's rather take a sharper example) Consider atomic(T) and T =.. [_] or functor(T,_,0) which describe exactly the same except that atomic(T) similar to integer(T) silently fails and T =.. [_] and functor(T,_,0) produce an instantiation error.

YeGoblynQueenne6 anni fa

Here, also, atomic/1 is a type test and "T" is of type "variable" rather than "atom" or "integer" etc.

falsissime6 anni fa

There are two different notions of type here. One is determined by the abstract syntax, in this context a variable is a type, that's what you are referring to. With this type no desirable algebraic properties hold like commutativity, since atomic(T), T = a and T = a, atomic(T) differ: one says yes, the other no. As a consequence, the meaning of a program is fixed by the very precise control of Prolog, no way to change this in some context. Many consider this a central weakness of Prolog. Say, Peter Norvig: However, Prolog's depth-first control structure is just too inflexible for me. https://www.quora.com/What-do-Lisp-Haskell-programmers-think...

The other meaning of type is the pure, declarative one. Here, variables do not belong to the valid types. In that context, atomic_si/1 and the other predicates fit in. Here, commutativity (modulo errors) holds. And thus alternative search procedures may be used.

(There is a third meaning similar to the second, but it is only standard related.)

YeGoblynQueenne6 anni fa

That's correct but both the things you bring up are a matter of taste. Regarding the ordering of goals, as far as I know there is no straightforward way to make it not matter, that is also efficient to run on a modern computer (but I might be wrong about this because I haven't looked recently). With all due respect to Peter Norvig who is one of my AI heroes, that bit about "not knowing whether a particular ordering of goals is essential or arbitrary" is just picking at nits.

Regarding pure, declarative types those again are extra-logical and so, in the context of a first-order logic language, they are arbitrary and conventional. You can say "it's better this way", someone else can say "no, it's better this other way" but in the end of the day there's nothing set in stone. Far as I can tell.

Anyway I really think all those little complaints about Prolog's lack of absolute, pure perfection are always bordering on nitpicky- and from the wrong side of the border, at that. Peter Norvig says Prolog is not a general purpose relational solver, but it's a general purpose programming language. Well, yes, because it was, from the start, designed to be a general purpose programming language! That is, a language that can be used for, you know, actual programming in first order logic. Of course it's not perfect. That has always created a rift in the community, with some people taking the issue more seriously than others. Some have always been happy that they (we) have a language that's 90% of the way to pure, declarative perfection and that lets you express yourself in code in ways that would be really painful in any other language (just think of DCGs vs. the pain that compiler writing is in anything else). Others are always unhappy because they're missing that idealistic 10% that remains on the road to clean and pure declarative perfection. Well, we're not in a pure world. We don't have perfect computers. In fact, our computers just suck. We have to accept compromises, if we want to get anything done. Prolog is almost perfectly balanced in between shitty languages that abuse imperfections in computer architectures and mathematical purity. Personally, I'm grateful to Colmerauer and Kowalski for creating it. I can only imagine the mess I'd make of it if I had to do it myself.

sesuximo6 anni fa

False is a way to say "this is impossible given the current constraints"

It's possible that X could be an integer, but Prolog can't do anything with that, so it just throws an error. I suppose an alternative would be to return 0 and then 1 and then -1 and then 2 etc but I have no idea why anyone would care.

falsissime6 anni fa

Right, that would be a valid answer too! Unfortunately it has very bad termination properties and is also quite inefficient when larger numbers are involved.

And yet, there is a further possibility why not say `when(nonvar(X), integer(X))`. One system tried to go that path: Mu- and Nu-Prolog. However, the practical result was that an erroneous predicate just succeeded and you got an answer with tons of constraints (at that time in that context called floundering goals). A lot of research was put into detecting such flounders, but nothing came out of this effort that is in current use.

galaxyLogic6 anni fa

Wouldn't that be the way to generate infinite lists?

tr3526 anni fa

Thanks for that interesting write up! This makes me want to toy around with Tau and Scryer Prolog.

7thaccount6 anni fa

We often don't learn from the greats of computer science (all sorts of APL goodness from the 70s is being rediscovered for data science today).

As far as modern Prolog. I know commercial systems still exist, but I assume most work has switched to SWI-Prolog?

falsissime6 anni fa

Do not forget SICStus, it´s jitter is truly excellent.

7thaccount6 anni fa

Yeah, I've heard a bit about that one, but have lumped it into the commercial ones that you'd have to have a solid need to justify a license cost like running something important in production that requires support or you'd probably need an academic license.

falsissime6 anni fa

https://sicstus.sics.se/order4.html

Includes an evaluation license (free) and a personal license for EUR 165.

7thaccount6 anni fa

The personal license cannot be used for any commercial purposes (basically just academic research or play). The single-user commercial license is over $2000. Not that any of that is unreasonable in industry, but you're making it out to be cheaper than it is.

falsissime6 anni fa

$2250 is the first year. Then $750 a year. This includes support. To my understanding, development alone without distribution falls under the personal license.

falsissime6 anni fa

Should have been EUR in place of $

raarts6 anni fa

Can anyone point to prolog systems still in production?

7thaccount6 anni fa

Michael Hendricks has a few neat talks on YouTube and InfoQ on how they use Prolog in production.

[deleted]6 anni fa

verdverm6 anni fa

I've been using https://cuelang.org, a new logical language.

It's frickin awesome, logical + engineering = get things done

We just released an initial dependency tool for Cuelang based on go mods

https://github.com/hofstadter-io/mvs

pmcjones6 anni fa

Some background on the project: https://mcjones.org/dustydecks/archives/2020/03/18/1064/

Twisol6 anni fa

I've been fascinated by concurrent constraint programming (CCP) for a few years now, but it's hard to find source code for any of the system from back then. My reference for most of this topic is Vijay Saraswat's monograph of the same name, and he mentions systems like "Concurrent Prolog", "GHC" (no relation to the Glasgow Haskell Compiler!), and most importantly for me, "Herbrand", the instantiation of CCP over the Herbrand term universe that Saraswat developed.

If anyone is familiar with these topics, any pointers would be much appreciated!

bobbane6 anni fa

Did not see it mentioned in the article, but I believe Quintus Prolog was the base for Prolog on the Xerox Lisp machine line.

They went to the effort of writing special microcode for the unifier, which meant the basically 16-bit 1100 series workstations were competitive in performance with other Prologs at the time.

carapace6 anni fa

Does anybody know where I can find the Mixtus partial evaluation system? It's mentioned all over the place (e.g. The Art of Prolog) but I haven't yet been able to locate the actual source. Any help would be greatly appreciated.

fizixer6 anni fa

Rant alert: I've realized there is a big problem with logic programming: the two cultures of mathematical logic, and logic programming.

In math logic, you learn propositional/sentential logic, then spend a lot of time with predicate/first-order logic. At this point, you can "return to mathematics" to do any math stuff imaginable under the sun. However, if you want to spend more time being a logician, you can delve into a wide variety of topics, second-order logics, constructive logic, model theory, proof theory, etc, etc, etc.

Computer-science/logic-programmers on the other end?

First they don't start with prop or pred logic. Absolutely zero building-from-the-ground up about how you could do computations using prop, then maybe move to more sophisticated stuff like pred logic.

No, they will throw Hoare logic at you, and Horn clauses, and relational databases, and bound and free variables, and cuts, and what not. And if you complain, I guess you're just not cut out for logic programming. (I guess hardcore full-time mathematical logicians are not cut-out for that either, including Godel mind you).

You think they'd stop there. I'm afraid not, far from it.

Next they want you to spend all your time about learning about Church and Turing, and Curry-Howard correspondence, and to pretend like "real" logic started in 1933, and 1936, because anything before lambda-calculus is too inferior to be used in computers.

Oh but wait, they're not done yet.

Now they want you learning a brand new foundation of logic, math, and CS, that even mathematicians hardly need or use for 99% of their work. They want you to think in terms of type theory, and category theory. (So I guess when they say 'brand new foundation' they really mean 'brand new pair of foundations from which you can pick').

I'm starting to think there is something seriously wrong with the way logic is approached in theoretical CS, and logic programming. It's not minimal, and appears to serve as an elitist gatekeeping device, while mathematicians are going about their daily lives producing spectacular results with just prop+pred logic, and category theory has only started getting used in a tiny fraction of mathematical work.

Twisol6 anni fa

You're right that it's hard. However, I think you're missing one significant point that, at least to some extent, justifies the hardness: computability.

Systems like Prolog are based on the idea of "proof search": given a logical statement, find a proof of that statement. Humans do this all the time with classical logic, you might say -- but then, there are very famous statements expressible purely in first-order logic that nobody has found a proof of. This is anathema to computing! We want an "effective method", a "decision procedure", that allows us to compute for finite time and terminate with a positive (or negative!) proof. And we know, thanks to Gödel, that no such procedure exists for first-order logic: any decision procedure will miss proofs for some first-order statements.

In order to give ourselves more options for proof search, we need to enrich our logics somehow. This enrichment usually comes in the form of restrictions relative to classical logic. For example, Horn clauses are a fragment of classical logic that we _can_ assign a reasonable decision procedure to -- of which the most basic is probably SLD resolution. But these restrictions traditionally sacrifice more power than we'd like, so we add various things back in, trading computational difficulty (but not decidability!) for expressivity. This is a significant source of complexity, no doubt!

Computational logic is hard because we're asking more of it. Classical logic has been around since at least Aristotle, so it's perhaps no surprise that it's been refined into such a simple, well-understood form. Even then, I think if you traveled into various classical modal logics, you'd find those just as inscrutable at first as the logics we use in logic programming.

> Hoare logic

Mmh... For the most part, Hoare logic is back on the "for humans" side of things, as it's about verifying software rather than implementing software. It brings to bear the full power of classical logic(1), but since you're applying it to programs, most of which have incredibly non-monotonic semantics, you have to consider truth at each point in the program. Most of the machinery in Hoare logic over classical logic is about relating all of those points -- all of those worlds, in a model-theoretic sense.

I personally find Hoare logic easier from a mathematical reasoning perspective than any of the logic systems designed for implementation. I think that makes sense, though, because Hoare logic is not about automation.

(1) You can instantiate Hoare logic over any particular logical system, so you could apply it for automated verification, but I don't think that's the case the parent was considering.

falsissime6 anni fa

Some of your points are taken seriously! Think of purifying Prolog such that cuts and the like are (for many cases) no longer needed, yet you get comparable efficiency. See library(reif), library(pio), ...

Think about implication in propositional logic. Take two entirely unrelated propositions a and b. According to this logic either a → b or b → a is true. This, btw, cannot happen in Prolog.

kensai6 anni fa

Is there for other languages as well? For example Functional?