Introduction to logic programming with Prolog
matchilling.com
matchilling.com
Q. How many Answerset programmers does it take to change a lightbulb? A. {1}, {1,2}, {1,2,3}, {2,1}, {2,1,3}, {2,3,1}
https://www.reddit.com/r/programming/comments/7hp2xw/introdu...
In modern Prolog systems, you would use more declarative features such as constraints to model combinatorial tasks like map coloring.
Make sure to check out modern Prolog features if you are interested in learning the language seriously!
The set of CLP languages is generally implemented as a superset or add-on package(s) to a Prolog implementation. For example, SICStus Prolog and SWI-Prolog have CLP modules, e.g.:
https://sicstus.sics.se/sicstus/docs/3.7.1/html/sicstus_32.h...
http://www.swi-prolog.org/pldoc/man?section=clp
and "Constraint Handling Rules(CHR):
http://www.swi-prolog.org/pldoc/man?section=chr
To the best of my knowledge the modules are written in Prolog. A look at those links will give you an idea of how CLP is used. There are modules available for CLP(X) where X is one of:
B = boolean,
Z = integers,
Q = rational numbers,
R = real(floating point) numbers,
FD = finite domains (see "CLP(FD) Constraint Logic Programming over Finite Domains" http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html )
etc.
One can understand how constraining the domain of interest (reducing the search space) to say, the integers, might make search more efficient.
Devising and implementing such suitable interface predicates is quite hard, and only a very small number of Prolog systems have succeeded with this so far.
For example, the SWI interface for CLP is too limited in practice, and its constraint solvers have elementary mistakes also because of the limitations of the interface predicates it provides.
In contrast, SICStus Prolog provides a much more general interface to attributed variables that supports all widely used constraint solvers (finite domains, Boolean variables, rational numbers etc.) with good performance and no known mistakes.
The tutorial you link to has several rather severe shortcomings, and I cannot recommend it for learning CLP(FD). Please see my profile page if you are interested in Prolog resources.
An example of such a construct is dif/2, which is a constraint that was provided in even the very first Prolog system, sometimes called Prolog 0, several decades ago. However, it was not widely available in Prolog systems until much more recently, even though professional Prolog systems such as SICStus have provided it for longer. Also arithmetic constraints were available in early implementations such as Prolog IV. So, in a sense, we are now going "back to the roots" of Prolog by making very old features widely available.
In my personal view, calling modern Prolog an "incompatible paradigm" with the way that Prolog is still being taught is not completely fitting, yet still more right than wrong: The new features are not meant to be used "on top" of old features, but instead! When using modern Prolog features to their fullest extent, you can completely eschew those language constructs that traditionally cause the worst problems for beginners.
Moded arithmetic is a prime example for this, which can be replaced completely by arithmetic constraints in modern Prolog systems. dif/2 is also a good example, which lets you avoid (\+)/1 in many cases by using a more general predicate instead.
Due to their operational semantics that is very hard to explain and understand, rather limited constructs often take significant room in many Prolog courses, and replacing them by more modern alternatives will entail a paradigm shift towards better methods and also make room for even more new material that can be covered instead. This is because on top of being more general, the new language constructs are often also easier to understand for beginners.
That is very powerful indeed. From incompetently playing around with stuff like that, my impression was that "constraints everywhere" is also extremely slow. That's not surprising, there's a lot of machinery working below the surface to deliver all that power. To recover performance whenever the full generality of the paradigm is not needed, I expect we'd need to work hard, say very smart static analysis, or JIT specialization, or...
But certainly my incompetence made me miss a lot. If you know how "constraints everywhere" can be made "fast everywhere", I'd love to hear about it:-)
Every predicate you impose on the set of solutions can be regarded as a constraint, because it can at most restrict the set of solutions, never increase it.
So, in fact, every Prolog goal you invoke is a constraint. When reasoning over Herbrand terms, the only constraints are equality and disequality of terms, which are implemented by the predicates (=)/2 and dif/2, respectively.
In addition to these basic constraints over terms, modern Prolog systems also provide constraints over more specialized domains, such as constraints on integers, rational numbers and Boolean values. For combinatorial tasks such as map coloring, constraints over integers are especially useful.
For example, here is a constraint on integers, using GNU Prolog:
| ?- 3 #= 1+Y.
Y = 2
Constraints implement relations between their arguments and can be used in all directions. This is the reason why Prolog predicates are typically more general than functions in other languages. However, to truly benefit from this, you must consistently use these comparatively new language features instead of lower-level ones. I say comparatively because these language features have been available for several decades by now in professional Prolog systems such as SICStus.
From the perspective of Prolog and its users, a constraint solver is simply available just like any other predicate! All the internal reasoning a constraint solver performs is completely abstracted away. The only interface is typically a few Prolog predicates that let you access the features of the solver by stating what must hold about the involved variables.
So, to use a constraint solver in Prolog, you simply use the predicates it provides, just as you would use any other Prolog predicate. In the example above, I am using the constraint (#=)/2, which is a predicate that is true iff its arguments evaluate to the same integer.
From the perspective of implementors, Prolog is a great implementation language for constraint solvers due to its built-in search and backtracking mechanisms. It also allows you to use the standardized Prolog syntax that many users are already familiar with, instead of having to devise yet another modeling language on top of your solver.
Thus, I would describe the relation as a natural symbiosis: It is natural to use constraint solvers in Prolog, and natural to implement them in Prolog.
> It is for this reason that Prolog falls short of the ideals of logic programming. Specifically it is necessary to be concerned with the operational interpretation of the program whilst writing the axioms.
I haven't heard of any approach that generalizes the goals of logic programming in a far better way. Is there any? (on specific usecases, having a sort of rule engine for running your "business rules" can indeed be an excellent approach)
[1] https://github.com/papers-we-love/papers-we-love/blob/master...
It is not that we can't come up with a logic language that is more declarative, it is just that telling the program everything about the universe is so damn dull. For example, ordering of your body predicates will often be based on what you think intuitively their sizes of solutions are going to be e.g. `plus(A,B,C), solution(C,X).` You know that plus is injective, so you put it first but from a logical perspective putting solution predicate first is just as sensible. If the language allowed you to express relative sizes of the predicates, then this could have been done automatically, but it would involve coding the order of predicates somewhere else in the program!
You also need to get rid of cuts in Prolog, if you want to be closer to true declarative programming. You might like to then try Datalog (alas, not Turing complete).
Another approach is to separate concerns more clearly. The part of Prolog that encodes and solves a logical problem is often different than the one dealing with IO for example. Ideally, you want to be more declarative in the former domain and more imperative in the latter. This can (and probably have been done) with a monadic approach.
`plus(1, 2, C). C = 3.`
`plus(0, 3, C). C = 3.`
Isn't that a counterexample, showing how it is not injective?
https://ggweb.gradegrinder.net/tarskisworld
https://web.stanford.edu/group/cslipublications/cslipublicat...
Might help, instead of jumping straight into Prolog.
Edit - this one: https://web.stanford.edu/group/cslipublications/cslipublicat...
Logo used to be very popular for kids here in the '80s. I learnt Logo when i was 7, then i "progressed" over the years to Basic, C, Pascal, C++, Java, C#, Python and now, after about 28 years, Lisp. And now I realize Logo is close to Lisp in many ways and a far more powerful language than some of the ones I "progressed" to.
It deserves a blog post, but I'd say Lisp (at least Lisp in its mainstream Common Lisp incarnation) is easy to learn but extremely hard to master, since it allows many possibilities and paradigms, and because of the power of meta programming. So to master it, you would be familiarized with all the paradigms and you would know how to leverage meta programming, etc. Also, since it allows improving performance by going to low-level details (like observing the assembly output of your function), you would better know a bit of assembly/machine language if you want to be able to improve the performance of Lisp to approach (or equal) C code. So previous experience with low-level programming, at least with C, would be a good prerequisite.
But yes, using it for simple stuff is easy, and in fact, while I consider Python a great "first language to learn", sometimes I feel that Lisp isn't much difficult than Python, for the same tasks. Python is much easier to master, but then it is much more limited.
Usually, the people who genuinely had a "hard to wrap head around experience" weren't actually using Lisp but a different language called Scheme which is hard to do for anything practical, if you stick just to the standard-defined dialect.
Chances are that when they used Scheme, it was a school setting, and they were complete or almost complete programming newbies, and were asked to do everything with recursion, and also given demanding homework, like interpreting Scheme in Scheme and whatnot.
The child was encouraged to build general solutions to homework, and suddenly a lot of schoolwork with tedious arithmetic seems boring to the child.
You can write a quicksort in a few lines. You can traverse over a tree very easily. But understanding these few lines takes me more time than writing it in C, Java, PHP etc.. But I guess it is all training...
I am not saying that one way or language is better than the other. But I'm saying that, like you are faster to rewrite in c or java, there are people that can rewrite or understand faster the other way. :)
Programming is fun!
But when you've spent many years writing imperative code it feels so alien. It reminds me of the first time I attempted to write Verilog, it's hard to break the mold and change the way you think about the flow of a program and how you construct algorithms. Eventually it clicked for me and Verilog though, so I expect with enough dedication one could do the same with Prolog.
On our degree, we had three logic programming classes, starting from logic programming as pure math all the way to deep Prolog exercises.
P.S: Vocé é Portuguese, lisper e tambén fá de Prolog? You impress me more each day, pjmlp!
BTW, I hate Prolog too.
I'm still only a beginner at Prolog, but that's what I enjoy about it: it's an entirely different way of tackling problems that really stretches my brain, not just new syntax on the same old paradigm that I already know.
Since doing a whole program in prolog isn't really practical for me, is there any way to use the logic programming paradigm in mainstream programming languages to deal with specific problems that fit it?
- Using OWL in Java (with OWL API). So you use Java in combination with XML
- Use a Prolog embedding in Haskell.
Applications domains I've used Prolog for: discrete planning, game logic, limited/rule-based NLP such as postal address checking, combinatorial test case generation, decision problems in formal language theory used for eg. deciding properties of business processes, other small problems in software engineering such as code generation from domain models with roundtripping, or O/R mapping.
I feel like I might be missing something obvious, but I'm not getting what the "compatibility" you refer to would give me in my specific situations? It looks like you're saying "if you write a Prolog program, it's compatible across Prolog platforms." Well, sure, but how is that fundamentally more portable situation than (for example) "if I have a logic programming framework in ES16, it works in all browsers that run modern JavaScript"?
If I'm specifically trying to do something in the browser (again, for example) and have a problem within that context where logic programming might be useful, having a way to use logic programming in JS makes more sense, doesn't it?
For CSV, you could write a DCG grammar for the particular file format at hand.
Integration with a relational DB, itself being based on logic, would be very different. Most Prologs have APIs to map tables to predicates.
Yes, for example is easy to embed Prolog code in Common Lisp by using a suitable library. For example the LispWorks implementation includes a full Prolog package. Example:
https://news.ycombinator.com/item?id=12251046
With this, you can use the logic paradigm within the same project, along with the other paradigms supported by Common Lisp: Procedural, functional, meta, imperative, dsl-based and OOP.
Racket should also allow very easy mixing of Prolog source with the rest of the project, since Racket was designed to support different languages at once.
[1] https://bernardopires.com/2013/10/try-logic-programming-a-ge...
[0] https://github.com/thagomizer [1] https://confreaks.tv/videos/rubyconf2017-4-programming-parad...
Yeah, and no. This skips over the fact that this will not work in swipl, and you need to write those rules in a separate file, and compile/load them.
This is mentioned way after the entire introduction, after the reader has already given up on trying anything with prolog
Can I build something in particular, can I look for specific jobs?
You don't truly appreciate the declarative paradigm until you are able to describe (and find the best among) all billions of complex possibilities of configurations of nuts and bolts following all these engineering laws, practices and rules of thumb... in a hundred lines or less
I love Python and I'll introduce myself as a Python programmer, but part of me will always have a deep respect for prolog and how utterly awesome it is in the right context
As a corollary: Prolog will negate anything that can't be proven true from the rules you give it. A ML algorithm will always give you some answer, though the quality depends on the learning data.
He did say systems though so you are probably right
Btw, Prolog and ML might look like distant cousins: e.g. you use recursion and pattern matching in both. But under the hood there are big differences that arise from Prolog's logic programming paradigm: for instance, you can use append(L1, L2, L3) both to concatenate and split a list, depending on the variables you set:
append([1,2], [3,4], X) % ==> X=[1,2,3,4]
append([1,2], Y, [1,2,3,4]) % ==> Y=[3,4]It could be fun to retry Prolog now.