The golden language at my current place of work is Python. But we have some pretty gnarly business logic in some places (decision tree of average height 10 and branching factor of maybe 3).
To better understand how all the pieces fit together, I took on the challenge of writing the decision tree out in SWI-Prolog over the weekend, since I figured it would be the most “expressive” way to capture the logic.
I’d taken a PL class in college, and used prolog for a couple weeks therein. But this was the first time I’d used it in years. The first 30 minutes were a struggle, as I tried to remember how predicates worked, and tried to translate my mental model into a series of iteratively applied predicates. But after a couple hours of very satisfying top-down programming, I’d written pretty much the whole thing.
And it worked!
My grand theory is that we’d be able to get compliance, legal, and finance (main stakeholders of the program), to interface with some exposed subset of the predicates, to tweak to their hearts content.
This program could be the Golden source of truth that all implementations would have to live up to. Maybe, we could even hook in python programs to do I/O (fetch inputs from the databases, write decisions to the database), and use this prolog program directly to drive decisions in a python program.
It’s all a fantasy at this point, but it’s a fun one. The idea’s lingered since that weekend, many months ago.
Has anybody pulled off anything similar? Replacing a complex component of a bigger program with a prolog core?
Factually, it is more legible, maintainable, easy to extend. However, imo, this is mostly because all of the I/O had been abstracted away.
In the python program, I/O and logic were interspersed in a way that made it difficult to reason about only one or the other. You have to understand our data models to understand the code, and vice versa.
If I were to rewrite the python program today, it would "look" a lot like the Prolog one, and probably be equally as legible and maintainable.
I think it's an example where Prolog (as a "logic" language) "shepherds" you do the right thing with respect to I/O separation. I imagine if I tried writing it in Haskell or OCaml, the effect would be similar. I'm reminded of this article: https://news.ycombinator.com/item?id=22696229.
Python, meanwhile, is a blank canvas and a full set of paints, which is its great strength in experienced hands, but also its great downfall. When I leave the company, there's nothing stopping another engineer (a junior, or even an experienced engineer with different skill trees) from rewriting things in a way that "works" but compromises legibility or extensibility.
With discipline, you can develop a program in Python that looks quite similar to the Prolog one, but the only guardrails against writing it in spaghetti is psychological.
In any case, it was a fun exercise. It makes me want to try writing more things in different languages, if for no other reason than to improve my usage of the subset of Python I like best. :)
In my experience python gives the best results when you add a little bit of computer science to the mix. It is well within reason to use state machines[0] and constraint programming[1] libraries all from within python, no real need for an extra language.
Reading the wiki for Constraint Satisfaction Problems (CSP) brought back good memories of the time I decided to use Knuth’s Dancing Links and Algorithm X (DLX)[1] to solve sudoku (which apparently can be modeled as a CSP as well) for my Object Oriented class when I was still an Undergrad at University. I really wish I would have generalized my Algorithm X program (like Knuth did) to solve any of the possible exact cover constraint problems, but a lot of what was going on in his paper was unclear to me at the time and I didn’t see that he solved it more generally until later. It was really quite fun to finally see the program working and it was surprising how quick the program ran given that DLX is basically a brute force search backtracking algorithm.
I don’t know much of CSPs to know whether Knuth’s Dancing Links or his DLX was used all that often for them. I’m guessing an exact cover problem is one such CSP, but it seems that CSPs also use backtracking which it seemed to me that Dancing Links and sparse matrices were a good combo for that. Anyone have thoughts or inputs or corrections on whether what I said is correct about CSPs?
Yep, totally agree. Python's metaprogramming is powerful enough that you can twist it into any shape you like! :)
My favorite gem, especially before python3 and typehinting were more widely in-use, is attrs [0]. It allows you to define rich data types (which python is great for) in a declarative/expressive/legible manner (which python sometimes isn't great for).
imo, it's a fantastic example of how metaprogramming allows libraries to actually enhance a language. Another one that demonstrates the power of MP is fire[1], a tool that allows you to drive classes with a MP-generated CLI.
This is true regardless of language. There's a reason I insist on teaching what should be core CS topics to my new graduate coworkers (many of whom have been EEs with limited programming experience, their solutions tend to be brute force and unmaintainable for the first few years). These things simplify many programs and increase their clarity.
I meant to compare python with languages that support logic programming or functional programming which help convert the problem from loops and nested conditionals into declarative statements, but you are right, it makes their job, and in return your job much easier.
It’s a actually quite easy to write a prolog interpreter, so you could probably just emed the code in Python so that you have a better integration with the rest of your codebase. You can probably just look for some logic programming libraries in Python.
I heartily recommend "The Search Space" podcast to anyone interested in learning more about logic programming. The host is very good at introducing concepts in an easily understandable manner, and
at chaining them in the right order so that you don't feel overwhelmed. I'm a complete noob, plus not a native english speaker, yet I didn't feel the need the rewind things at any point while listening to it.
I have many Prolog books and by far the most practical or "real world" of them is "Prolog Programming in Depth" by Covington/Nute/Vellino, which the lead author has made freely available as a PDF:
I love Prolog -- the problem I find is that it makes hard stuff easy, but things that should be easy, hard - most of which comes from abuse of backtracking. When you realize that default Prolog SLD resolution is just a depth-first search and that every predicate you define really has a implicit "foreach" in front of it, it's easier to wrap your brain around. To get efficiency however, you need to embrace logical vars and use them as "holes" in data-structures (such as diff-lists) that will be filled in later, which does require some restructuring of your thinking sometimes.
>> When you realize that default Prolog SLD resolution is just a depth-first search and that every predicate you define really has a implicit "foreach" in front of it, it's easier to wrap your brain around.
Depth-first search is used to find matching literals, but SLD resolution is
not depth-first search; or it would be called "depth-first search".
SLD resolution is an algorithm that eliminates literals from a clause until
the empty clause is derived, at which point a refutation of the original goal
succeeds.
For example, let P = {q(a,b) ∧ (p(X,Y) ∨ ¬q(X,Y))} be a definite (logic) program
and G = ¬p(X,Y) be a Horn goal. A refutation proof of ¬p(X,Y) by resolution
might go like this:
a) p(X,Y) unifies with ¬p(X,Y) with substitution θ = ∅
b) ¬q(X,Y) ∧ q(a,b) is derived from (a) (by elimination of the two unifying
literals with opposing signs)
c) ¬q(X,Y) unifies with q(a,b) with substitution θ = {X/a,Y/b}
d) □ [the empty clause] is derived from (c)
Thus, ¬p(X,Y) is refuted, with substitution {X/a,Y/b}, i.e. p(X,Y) is true
with those variable bindings.
Note that in Prolog, P = {q(a,b), p(X,Y):-q(X,Y)} and G = :-p(X,Y). I've
written it in clausal form above to help with the elimination of literals.
So, depth-first search is used in Prolog (but not mandated by any description
of resolution) to find unifying literals for a "query" (i.e. a goal) but
depth-first search is not resolution and resolution is not depth-first
search. Resolution allows us to derive a set of literals from another set of
literals, by elimination of literals that unify but have opposite signs.
Indeed, resolution can be notated as:
p,q ¬q
--------
p
Or, from p OR q and NOT q we can infer p.
[Note: "elimination" is my own terminology, not often used in logic
programming books. The correct description is that from p and ¬p we can
derive empty clause.]
All true, but I stand by my assertion (pardon the pun) that "Prolog SLD resolution" is depth first -- unless you're using a non-standard Prolog or some meta-predicate that implements another strategy. And any other strategy that's not WAM-inspired and depth first is prohibitive and unwarranted for the actual running of Prolog programs with all its assumed operational semantics. General resolution (SLD or otherwise) works for some theorem-proving, but not for running general Prolog programs.
Hey. If you are still reading this, I must apologise for my other sibling comment right under yours. I sound like a formalism nazi! I understand what you mean that "Prolog SLD resolution is depth first". You have probably implemented a Prolog meta-interpreter and noticed that it works by putting literals on the stack, then deriving new literals and putting those on the stack, recursively and by creating a new "branch" between each literal. In fact, resolution itself is often described (or rather reasoned about) in terms of resolution trees. It's definitely not the same as depth first search, because it's not a search, but it doesn't take a lot of effort to see what you mean by "depth first" in this case. I should not have been such a terminology miser here. I'm upset myself sometimes when people demand absolute terminological clarify of me when it's obvious what I'm trying to say (and it's obvious to them, they just like to nitpick). So I apologise for the nitpicking.
Your original comment said that "default Prolog SLD resolution is just a depth-first search". SLD resolution is not "depth-first search", "just" or with additions. Depth-first search is a search algorithm. In Prolog, depth-first search is used to find literals that unify with a goal, in order to perform resolution. But depth-first search is not part of SLD resolution and depth-first search and SLD resolution are not the same algorithm.
You seem to be reformulating your assertion. In the last comment you say that "default Prolog SLD resolution is depth-first". That reformulation also doesn't make sense. The search used by Prolog is depth-first search. But SLD resolution is not "depth-first". There is no context in which "depth-first" makes sense outside of depth-first search and there is no context in which SLD resolution can be said to be "depth-first". That's regardless of implementation.
>> General resolution (SLD or otherwise) works for some theorem-proving, but not for running general Prolog programs.
I'm sorry, I don't understand this. If I understand correctly, "general" resolution refers to resolution for arbitrary clauses? SLD resolution operates on definite clauses and is sound and refutation complete for definite logic programs. SLDNF resolution is also sound for normal programs. So, yes, resolution "works" for running general Prolog programs.
A buddy worked at the University of Amsterdam (closely associated with swi of swi-prolog fame) and worked on garp, qualitative modeling software.
Their codebase was tens of thousands of lines of code, most of it was pretty readable.
Do not make a gui in prolog though, you will regret it. It was pretty hard to troubleshoot and maintain at scale. The paradigm does not lend itself to that kind of thing.
Prolog is pretty cool for search and symbolic ai though. It was awesome as a first language in uni.
I'd never heard of Garp. Thanks for sharing! Really interesting approach to modeling.
Garp is part of the European NaturNet-Redime Project. The full name of the project is: "New education and decision support model for active behaviour in sustainable development based on innovative web services and qualitative reasoning. Say that 10 times fast!
GARP provodes" a methodology that structures and supports the capture of conceptual knowledge about sustainable development using a qualitative approach. The framework defines a protocol for describing content (knowledge and expertise) that supports the development of conceptual understanding of systems and how they behave. In addition to structuring the work involved in building models, the framework also facilitates easier comparison and evaluation of the results of modelling efforts".
From my limited experience, prolog is perfect for describing the shape of the valid state space for almost any domain. But its default execution strategy -- just depth-first search -- doesn't enable you to efficiently navigate that state space from diverse perspectives.
Is there a publicly available code repository with a program written in Prolog that does some non-trivial task? #3 looks the closest, but I'm looking for an example of something complete that people are using.
I believe the main use case for Prolog is to create other languages and DSLs on top of the Prolog engine, especially rule based and logic-aware languages. This is the kind application for which Prolog shines due to its characteristics. A huge example is the early implementation of Erlang, but also some more niche stuff related to the semantic web like [1].
To better understand how all the pieces fit together, I took on the challenge of writing the decision tree out in SWI-Prolog over the weekend, since I figured it would be the most “expressive” way to capture the logic.
I’d taken a PL class in college, and used prolog for a couple weeks therein. But this was the first time I’d used it in years. The first 30 minutes were a struggle, as I tried to remember how predicates worked, and tried to translate my mental model into a series of iteratively applied predicates. But after a couple hours of very satisfying top-down programming, I’d written pretty much the whole thing.
And it worked!
My grand theory is that we’d be able to get compliance, legal, and finance (main stakeholders of the program), to interface with some exposed subset of the predicates, to tweak to their hearts content.
This program could be the Golden source of truth that all implementations would have to live up to. Maybe, we could even hook in python programs to do I/O (fetch inputs from the databases, write decisions to the database), and use this prolog program directly to drive decisions in a python program.
It’s all a fantasy at this point, but it’s a fun one. The idea’s lingered since that weekend, many months ago.
Has anybody pulled off anything similar? Replacing a complex component of a bigger program with a prolog core?