Ask HN: Production Prolog in 2020? | Hacker News Reader

Ask HN: Production Prolog in 2020?

131 pointstimxor70 comments

Seeker of logic programmers!

Upcoming Rust lifetime analysis engine, Polonius.

http://smallcultfollowing.com/babysteps/blog/2018/04/27/an-a...

I think Prolog and logic programming will have a second renaissance. I think at the very least a general artificial intelligence would require a logical inference engine similar to Prolog.

Do any of the non-artificial intelligences walking around out there contain a logical inference engine similar to Prolog?

https://en.m.wikipedia.org/wiki/Datomic

Datomic is cool but not an intelligence, artificial or not. The GP was trying to point out that having a prolog-style inference engine is not required for intelligence and pointing to humans as a counterexample to prove why not.

Sorry, I parsed the grandparent as:

?- applicationof(prolog, X), domain(X, Y), nonai(Y).

> non-artificial intelligences walking around out there

I'm not sure what you mean by this. Do you mean people? I don't think our 'inference engine' is much like Prolog, no.

“The question of whether a computer can think is no more interesting than the question of whether a submarine can swim.” (Edsger W. Dijkstra)

--is what he means.

I got nice sentence

Do any birds flying around have engines?

I want to agree with you, but I also want to agree with the hypothetical rebuttal GP is making in my mind:

> Yes, they do have engines similar to those found in planes, cars, etc. and so do humans - fuel goes in, chemistry happens, and energy is provided for physical movement in the form of rotation, flapping, or one foot in front of the other.

Idk who I agree with, I suppose it's a fairly pointless exercise in 'how similar constitutes 'similar'' all the way down.

Yes. Logic wasn't conjured up from abstract ideas, but from a concerted effort to distill the essence of what humans (regular, average people) find reasonable and convincing. (To mention just one example, there is a reason one of George Boole's major works is called "The Laws of Thought".)

Our strategies for understanding language also involve inference and unification that is similar to logic programming. This is not to say the exact semantics and evaluation strategy of Prolog is what humans carry around, but part of our cognitive apparatus clearly operates in a manner similar to logic, and by extension Prolog.

I discussed this topic with one of the inventors of Prolog recently: https://thesearch.space/episodes/1-the-poet-of-logic-program...

I have no doubt that human or other intelligences can emulate and even to some extent intuit these rules. If you believe that's a _requirement_ for their intelligence, I think that's a stronger claim. Not one I'd vehemently argue against, but not one I'd personally be comfortable making.

I don't believe we emulate a set of rules that were somehow arbitrarily created at some point in history. I believe logic is something we discover (not invent) and it has roots in both human cognition and the physical world, and it's not fully known or understood exactly how they emerge. Hence, logic is still a developing field, and logic programming has indeed contributed to it.

"Intelligence" is a vague term, but if you mean the ability to act rationally or even in a coherently self-interested way, then surely logic has something to do with it.

I don't really mean anything special by intelligence, but let's flatter ourselves that humans are born with some measure of it. I personally find it more likely than not that our particular form of intelligence is able to then _learn_ various rules of logical inference as a kind of metapattern. When I say 'emulate' I mean that we can, if we want, sit down with a pencil and paper and _force_ ourselves to evaluate things exactly via these rules, even if we don't instinctively follow them (or do so fuzzily).

Obviously I could very easily be wrong, and we could possess hard coded rules of logical inference which form part of the basis for all the other things we do that you might call intelligence. But I'm not sure that anyone should claim "a general artificial intelligence would require a logical inference engine similar to Prolog".

Plotkin's thesis! You had an interview with Kowalski? Wow :)

You're on my wish list for interviewees too :)

Wot me? Haha! Wait another 20 years maybe! But thanks, that's so kind :D

I listened to this a few weeks ago -- looking forward to the next episode!

I think it's actually the complete opposite. The current biomimetism direction being privileged by the modern A.I. trends is most likely the correct way to achieve "True" A.I.

However, Inference-based A.I. is actually needed to properly tackle many of the business problems that are being thrown at ML systems today. Explainability and bias reduction can probably only be be taken so far with the current approaches, and I suspect that this "so far" is not far enough for many tasks. It's definitely the case from a practical standpoint today.

So inference-based A.I. is due for a comeback indeed, but I'd say AGI is looking like one of the main areas where the current techniques might work.

The inference-based methods in AI qre more likely to he of the "probabilistic graphical models" variety (there are already marriages of Bayesian and Deep Learning techniques), and less likely to be of the "first order predicate calculus" variety. We humans don't have a particularly strong logical inference engine either - unless properly trained, people make the silliest logical mistakes and arrive at wrong conclusions all the time.

Right, I meant "prolog-style formal inference engine". My point is that this "human imperfection" also present in probabilistic engines have artifacts that are fundamentally at odds with many business requirements where we are attempting to shoehorn then.

It's almost more of a cultural issue than a technical one. The level of explainability currently desired from automated systems is possibly not achievable, simply because we want to uphold them to a different standard.

I'm pretty sure reasoning is important towards that goal, but how that is achieved is much less clear. Perhaps some probabilistic additions at the least.

I don’t think it will come back as AI, the statistical/differentiable approach proved much more powerful given the amount of data.

I think it will come back in programming tools / program synthesis though. There are many use cases for it and not enough people using in production.

> There are many use cases for it

would you mind expanding on this?

it's been on my backburner to learn prolog, but i have gotten a sense that it could be useful as a side-tool during development.

Equational reasoning makes TDD and property based testing trivial (encode rules by examples, base cases and corner cases, which is the most natural way for humans to think); rule-based system are easier to extend and correct by design (bounded set of possible states); provides more powerful and elegant query languages (E.g. Datalog).

See https://youtu.be/OyfBQmvr2Hc (skip to 1h mark to see some examples)

I doubt it. Prolog is inherently based on DFS that usually leads to inefficient algorithms. Cut operator then turns any source into an unreadable mess.

Our pay software at work needs a Prolog engine (SWI). I think it's exactly where it shines : a complex logic with a lot of small rules that would be a nightmare to implement and maintain with a if / else logic.

I implemented something similar to that at a payments company a while back, but not with prolog because I couldn't get buy-in. I wrote a rules engine expressed as SQL tables, and it was absolutely better than if-else or switch. It let us delete thousands of lines of code and also slap on a UI so that the people managing the payments rules could make changes themselves. Highly recommend.

Yes, sort of rules engine like that is really nice when you have a hodgepodge of data and purposes for it: e.g. your users may supply names, countries, ID numbers, various documents, addresses, etc — often with branching flows. (If the user is a business you collect different information than if the user is investing through an IRA or investing individually. The ID verification process wants the front and back of the document if it's a US driver's license, but it is okay with the front only if the document is a passport.)

At some point, you have partial answers for everything, depending on what flows users have gone through, in what order, and what the validation requirements of those forms were at that time.

Logic engines can answer questions like: Do we need to ask the user for more info for the Invest In XYZ flow? If so, which forms will supply the needed information?

had exactly the same problems 15 years ago:

   - business payment logic that fits prolog perfectly.
   - no buy-in whatsoever for prolog.

In the end, they bought a rules engine. Ignorance is bliss I guess.

Well done! I would leave to read a blog post on this kind of work.

Do you have any more information on that technique and how you approached it? Sounds interesting.

In my experience, "logic wants to be code, and not data". Ie it's a dangerous (although sometimes necessary) step to move this into the data domain. Did you encounter any difficulties with missing source control, being able to use debugging tools, etc?

Logic doesn't want anything.

Highly regular logic is better expressed in generalizations, and inferable logic is better expressed in a compressed, normalized fashion rather than repeated and duplicated.

The more irregular logic becomes, the more it fights generalization and needs special cases. The ultimate special case is a programming language (and code is data too!). The risk in expressing rules in the form of data is that to handle all edge cases, you encode a custom programming language without all the resources that supports programming languages, like editors, debuggers, source control, developer mindshare, stack overflow, etc. But not all logic is irregular enough to warrant it.

Some insight into the problem and solution would be hugely appreciated.

SQL is a deductive logic engine (same maths root as prolog IIRC, predicate calculus) but to bend it to work outside its domain, well the one time I tried it didn't work out so I'm extremely interested in what you did - TIA!

I won't go into a ton of detail because payments companies are very protective of their secrets. But imagine the kind of workflow diagram that product managers tend to produce at the beginning of a project. It doesn't look too awful. Not a ton of decision points. But over time you discover edge cases and interactions. If you started by replicating the original diagram in your code, none of the changes seem to be very bad. Just add another if/then here and another one there. I don't know what the mathematical formula is, but there is some kind of tipping point where this goes from "this is fine" to "holy fucking hell this is a nightmare."

I was hired on to the team about 3 years after the nightmare tipping point. There were no tests. There were no real expected outcomes. Just angry customers sometimes. And angry product managers who were still pointing at the original workflow diagram telling us to just make it do that. And there were people who had been dealing with it who were all, "Yeah, that's not even close anymore."

So instead of trying to solve all that mess of code, I backed up the chain a little bit and looked at things from the point of view of what variables are getting passed into this shitshow and what are their possible valid values. I came up with about a dozen that matter. Really variable variables like the dollar amount of a transaction don't really matter. It's other things like has this transaction settled? Is this a chargeback? Etc. Lots of binary switches. Some of them could have 3-4 legit dispositions. But if you look at their sources and what they imply, the possible valid states isn't the combination of all possible positions of all 12 variables. Some of them are exclusive. So I figured out that there's about 100-ish valid ways for these 12 variables to be arranged. And that only those 12 variables were actually driving all the logical outcomes.

At that point I was able to go to the product managers with a spreadsheet and say, "Okay. Tell me what's supposed to happen when a=True, b=3, c=debit, d=whatever, etc." They would go huddle up for a day or two and then come back with an answer. X, Y, and Z should happen, but not A and B, and not-not-C. And over time we were able to get a mapping from all valid states to all valid outcomes.

We all know what a finite state machine is, and it would be trivial to implement in any language. But in this case, lots of different systems needed to be able to work with this, and the only thing they had in common was the ability to connect to the database. So that's where we did it.

I had two tables. One was the rule and one was the outcome. Each row of the rule table had vars/values of a valid state and a foreign key to the outcome table it mapped to. The outcome table columns where the names of transformation functions and bool flags on them. So the process was 1) query for the relevant variables, 2) bounce them off the rule table to find a match or error on no match (which was useful in finding bugs higher up the call chain), 3) query the outcome table from the foreign key and get the values of the transformations, 4) push all of that into a stored proc that had a totally flat if/else chain 5) exec state transformations where indicated. Very easy to grok, not hard to implement, and as I said, the rules and outcomes could be added to or changed very easily by the people who were expert in understanding the business rules.

I hope that's enough detail to be useful to the people who were asking for it. I don't really want to be more specific. I think it would be crude and maybe a tad unprofessional to go deeper than that.

If I may, however, I want to respond to the person that said logic wants to be code and not data. And that it's risky to do otherwise. Without getting on a LISPy high horse (I've ridden that horse only a few times), I disagree. Sometimes logic drives data and sometimes data drives logic. I don't think there's as clear a distinction as you are suggesting, and I don't understand how you draw the line.

E.g., if a ======== 1{ //No seriously, I mean really really equal return a }

What's happening here? Is your logic in the driver's seat? Or is the data in the driver's seat? Who is determining the behavior? Your holy code? Or the value that gets passed to it?

I feel like arguing about data and code is like arguing about the difference between putting a net in place on a river and letting the fish get caught and dragging a net behind a boat so fish get caught.

But I'm not going to dwell on it too much. I think it's kind of silly to get dogmatic about it.

At this point, I feel like it is verging into lost knowledge territory, but that use case is almost the exact use case for the Rete Algorithm. As long as your rules fit in memory and are not recursively applied, rule application is an O(1) operation.

https://en.wikipedia.org/wiki/Rete_algorithm

Not completely lost! In some sections of industry, Rete-based rules engines are used pretty extensively. A very interesting take is Clara, implemented in Clojure: www.clara-rules.org

There was a minor hype cycle with SMT solvers in 2019.

For a while I was extremely fascinated by SAT as an encoding for hard problems that somehow had heuristic fast solvers; particularly by SATPLAN, the blocks world, etc.

But there's an useful contrast with Lisp, the other thing everyone within a radius of HN would like to emerge as winner. Lisp is essentially a syntax concept. It isn't particularly opinionated about problems -- on the opposite, it's indefinitely extensible to accomodate nearly everything. So we have Clojure and Hy (a Lisp that superficially imitates Clojure but compiles to the Python AST) and people doing scikit-learn ML on Lisp.

Logic programming, on the other hand, wants problems to be formulated on its terms. It needs the world itself to change to "win big". Of course logic programming problems aren't going to disappear, as sparse linear algebra programs won't. But this isn't a paradigm, it's an application.

Prolog-style logic programming is very different from SAT, SMT and Answer Set Programming in this regard. Prolog has the same features that you describe in Lisp. It's homoiconic, infinitely malleable, meta-level programming is trivial, etc. I recommend having a look at:

https://www.metalevel.at/acomip/ (A Couple of Meta-interpreters in Prolog)

and

https://github.com/triska/lisprolog

Understanding the declarative vs. operational semantics of Prolog (and how things like tabling can bridge the gap in some cases) is one of the most important concepts to master. It's really a shame that that more Prologs don't support alternate operational models -- though it's pretty trivial to write meta-interpreters with your own semantics (such as breadth-first eval, etc.) it would be nice if there were canonical versions. For CLP & attributed-variables at least there is some universality.

TerminusDB is a new project being implemented in Prolog: https://github.com/terminusdb/terminusdb-server

I really like working with https://mercurylang.org/ ; I think there are a few companies that use it for production software.

Seems like it had some traction like 10 years ago. I like the idea of controlling backtracking, but then when I tried it I thought it got a bit verbose w/all the mode decls. I should take a look and see if there's been any changes recently.

I did some work with SWI-Prolog. It is useful when the problem can be effectively translated into Prolog's preferred form of terms and rules. But the solver mechanism only solves a subset of logical inference needs. Prolog's use of logic in AI should not be conflated with the AI/ML systems which use networks of floating point operations, i.e. not boolean operations.

As always, best to choose the tool / language that best suits the problem.

Datomic uses Datalog, a dialect of prolog, that's what I would look at first if I needed prolog in production in 2020.

Gerrit (code review) uses Prolog for submission rules. I guess that counts as production prolog.

https://gerrit-review.googlesource.com/Documentation/prolog-...

Kind of offtopic, but does anyone know a good resource around implementing a simple prolog/similar language? My previous attempts at learning logic programming have failed, and it just _feels_ like a thing that becomes clear after you've seen how it works under the hood.

Check out miniKanren (http://minikanren.org)!

Though as Kanren's biding-stream merging which is a bit different than Prolog's DFS backtracking, it's good to look at but doesn't work like Prolog, so one would still need to look at the latter separately.

Check out Paul Tarau's "A Hitchhiker's Guide to Reinventing a Prolog Machine"

Slides: https://software.imdea.org/Conferences/CICLOPS2017/files/tar...

Paper: https://drops.dagstuhl.de/opus/volltexte/2018/8453/pdf/OASIc...

- - - -

The canonical method is teh WAM: https://en.wikipedia.org/wiki/Warren_Abstract_Machine

Along with @btwillard's suggestion, check out The Reasoned Schemer, it goes about explaining miniKanren and gives enough information to implement it yourself. It's a fantastic exercise.

Yarn 2 uses Prolog for workspace constraints.

https://dev.to/arcanis/introducing-yarn-2-4eh1#workspace-con...

I'm writing a constraint solver-based scheduler for lab work with social distancing. It's going to be used by at least one lab.

(Reminds me I've got to get to work on it! Anybody ping me if you want to help.)

A tangeant question is: Which non-niche language are having push for integrating a subset of logic programming extensions ?

There was a (unlikely to be merged at least in its current form) proposal for Kotlin -> https://github.com/Kotlin/KEEP/pull/199/files

Maybe LINQ from .NET could be included

There is also chalk from Rust https://github.com/rust-lang/chalk

LINQ is just in-language SQL with type checks, unless I'm ignorant of a bunch of its functionality (which I really hope is true, now).

There's a lot more to LINQ than that.

LINQ is extensible and you can connect it to arbitrary data sources by writing a query provider.

awesome-linq[0] has some examples of what can be done with it.

[0] https://github.com/aloisdg/awesome-linq

Oh sure yeah, but I don't think it has any logic/constraint programming functionality.

Is this related to Datalog also? I've watched a few presentations by Rich Hickey (creator of the Clojure programming language) and I feel like he often name-drops Datalog as a great tool.

> Datalog is a declarative logic programming language that syntactically is a subset of Prolog.

https://en.wikipedia.org/wiki/Datalog

I have used Prolog in a few professional projects.

I think if they came out with a version in hardware like they use to have lisp machines, it would have much better performance.

There is the Warren Abstract Machine [1], the Lisp Machines usually compiled to a virtual machine that was implemented by the underlying hardware.

[1] https://en.wikipedia.org/wiki/Warren_Abstract_Machine

Build one.

That was one of the ideas of the Fifth Generation Computer Systems project, started in 1982 :)

timing was bad on that with the AI winter.

Wasn't the AI winter mostly a thing wrt. U.S. academia? 5th gen was a Japanese-led industry project.

To the degree that it counts as 'production' Prolog, DFS-Tools -- a toolkit for Distributional Formal Semantics -- is actively used in a number of ongoing scientific projects: https://github.com/hbrouwer/dfs-tools

I'm not a prolog or logic programming buff, but have you looked at something like Clojure's core.logic? https://github.com/clojure/core.logic

Any system that uses Datalog uses a subset of Prolog. Loosely, this would include systems using Clojure's Datalog. To the degree the goal is logic programming, the looseness is more appropriate. YMMV.

Reply on news.ycombinator.com