7 ms·

Implementing Logic Programming

217 points by sirwhinesalot 1y ago

sirwhinesalot 1y ago
Or more accurately, a super simple Datalog implementation.
kragen 1y ago
I second the recommendation in Sir Whinesalot's post (which I haven't fully read yet) to look at miniKanren and microKanren. I found it extremely educational to port microKanren to OCaml a few years ago, and I think the result is somewhat more comprehensible than the original Scheme, though you'll still probably have to read the paper to understand it: http://canonical.org/~kragen/sw/dev3/mukanren.ml http://canonical.org/~kragen/sw/dev3/mukanren.ml The most astonishing result of miniKanren is a Scheme interpreter that you can run forwards, backwards, or both. http://webyrd.net/quines/quines.pdf http://webyrd.net/quines/quines.pdf demonstrates using it to generate a Scheme quine, that is, a Scheme program whose output when run is itself ("miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl)", Byrd, Holk, and Friedman). §4.4 of SICP http://sarabander.github.io/sicp/html/4_002e4.xhtml http://sarabander.github.io/sicp/html/4_002e4.xhtml also has an implementation of logic programming in Scheme which is extremely approachable. Unlike the post, I don't think Datalog is the place to look for deep insights about logic programming. Instead, it's the place to look for deep insights about databases.
- fcatalan 1y ago
  I concur that SICP 4.4 is very approachable. I once took a class that had a simple Prolog assignment, I recall we were given some building plans and had to program a path solver through the building. I thought it was a bit too easy and I wanted to dig deeper, because just doing the task left you with a taste of "this is magic, just use these spells". I looked at how to implement Prolog and was stumped until I found that SICP section. So I ported it to JavaScript and gave it a Prolog-like syntax and made a web page where you could run the assignment but also exposed the inner workings, and it was one of the neatest things I've ever handed in as coursework.
- sirwhinesalot 1y ago
  Insights shminsights, the database connection is where it is at :P (Thank you for reading the article, I also implemented microKanren before and it's insane how little code it takes to get full a logic programming engine going)
- anthk 1y ago
  Among SICP, https://t3x.org/amk/index.html https://t3x.org/amk/index.html Same approach. I think an older version of the book it's freely available, or maybe the one on Scheme itself. Scheme being homoiconic makes far easier to create quines.
xlii 1y ago
Lately I’ve been dabbling with different Prolog implementations and Constraint Handling Rules which led me to CLIPS [0] (in Public Domain, but developed at NASA - sounds neat doesn’t it?) It’s not very easy to get into, but it’s very fast on rule resolution and being pure C is easy to integrate. I’m trying to get smart code parsing using logic language and this seems promising. I’m also a Lisp nerd so that works for me :) [0]: https://www.clipsrules.net/ https://www.clipsrules.net/
- veqq 1y ago
  https://ryjo.codes/ https://ryjo.codes/ has done a lot of work with it, and made a course!
  - xlii 1y ago
    Whoa, awesome! Thanks for the link.
- 7373737373 1y ago
  CLIPS is also used by the Magic the Gathering Arena game engine to implement part of the game logic: https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-naps-and-living-breakthrough https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-n...
fracus 1y ago
I think it would be really impactful to start with a problem and describe how logic programming solves that problem better than the other paradigms.
- cjonas 1y ago
  The only production experience I have with logic programming is OPA Rego for writing security policies (not sure it's a "pure" logic language but feels like the primary paradigm). I found it pretty interesting for that use case, although the learning curve isn't trivial for traditional devs. https://www.openpolicyagent.org/ https://www.openpolicyagent.org/
- dkjaudyeqooe 1y ago
  Generally speaking, the advantage of logic programming is that it's (more) declarative: you describe the problem and it derives a solution.
  - taeric 1y ago
    Ish? Is only really true if what you are programming can be seen as a search for the completion of a statement? For an easy example to consider, what would the logical program look like that described any common fractal? https://rosettacode.org/wiki/Koch_curve#Prolog https://rosettacode.org/wiki/Koch_curve#Prolog shows that... it is not necessarily a win for this idea. For the general task asked in the OP here, I would hope you could find an example in rosettacode that shows prolog gets a good implementation. Unfortunately, I get the impression some folks prefer code golf for these more so than they do "makes the problem obvious."
    - rabbits77 1y ago
      I’d argue that is not the most ideal Prolog solution. More like it’s simply a recursive implementation of an imperative solution. For fractals you’ll want to be able to recognize and generate the structures. It’s a great use case for Definite Clause Grammars (DCGs). A perfect example of this would be Triska’s Dragon Curve implementation. https://www.youtube.com/watch?v=DMdiPC1ZckI https://www.youtube.com/watch?v=DMdiPC1ZckI
deleted 1y ago
[deleted]
ashton314 1y ago
I did a detailed write-up of implementing miniKanren here: https://codeberg.org/ashton314/microKanren https://codeberg.org/ashton314/microKanren By the end of it, I implement a small type checker that, when you run it backwards (by giving the checker a type), it proceeds to enumerate programs that inhabit that type!
- kragen 1y ago
  Isn't that amazing‽ I wonder if you could guide its search with an LLM...
  - ashton314 1y ago
    There is some research work I’m aware of that’s trying to make type-safe LLM generation a thing.
    - whitten 1y ago
      Is that research publically available, and where ?
      - lucascdotnet 1y ago
        Not sure if this is what you mean, but 'inductive logic programming' and more generally 'program synthesis' are fairly active research areas.
      - ashton314 1y ago
        This paper appeared at PLDI '25: https://arxiv.org/abs/2504.09246 https://arxiv.org/abs/2504.09246 Discussed on HN at the time: https://news.ycombinator.com/item?id=43978357 https://news.ycombinator.com/item?id=43978357
xelxebar 1y ago
https://github.com/Seeker04/plwm https://github.com/Seeker04/plwm This window manager implemented in Prolog popped up here recently. It's really cool! I jumped to it as a new daily driver in the hope that I'd learn some Prolog, and it's been quite the success, actually. The developer is really nice, and he's generously helped me with some basic questions and small PRs. Definitely recommended. I have a Guix package for it if anyone's interested. Any reading recommendations for high quality logic programming codebases?
- johnisgood 1y ago
  You should publish the Guix package somewhere.
philzook 1y ago
Nice! I'll note there is a really shallow version of naive datalog I rather like if you're willing to compromise on syntax and nonlinear variable use. edge = {(1,2), (2,3)} path = set() for i in range(10): # path(x,y) :- edge(x,y). path |= edge # path(x,z) :- edge(x,y), path(y,z). path |= {(x,z) for x,y in edge for (y1,z) in path if y == y1} Similarly it's pretty easy to hand write SQL in a style that looks similar and gain a lot of functionality and performance from stock database engines. https://www.philipzucker.com/tiny-sqlite-datalog/ https://www.philipzucker.com/tiny-sqlite-datalog/ I wrote a small datalog from the Z3 AST to sqlite recently along these lines https://github.com/philzook58/knuckledragger/blob/main/kdrag/solvers/datalog.py https://github.com/philzook58/knuckledragger/blob/main/kdrag...
- kragen 1y ago
  That's exciting!
- ulrikrasmussen 1y ago
  Thank you! I have been searching for something like this but for some reason couldn't find your work. I am currently implementing a Datalog to PostgreSQL query engine at work as we want to experiment with modeling authorization rules in Datalog and then run authorization queries directly in the database. As I want to minimize the round trips to the database I use a different approach than yours and translate Datalog programs to recursive CTEs. These are a bit limited, so we have to restrict ourselves to linearly recursive Datalog programs, but for the purpose of modeling authorization rules that seems to be enough (e.g. you can still model things such as "permissions propagate from groups to group members").
  - whitten 1y ago
    What does CTE stand for, and how do I research it ?
    - burakemir 1y ago
      Common Table Expression, a SQL concept that enables more expressive programming with SQL queries. They are introduced using WITH ...
vvern 1y ago
Some time ago I worked on cockroachdb and I was working on implementing planning for complex online schema changes. We really wanted a model that could convincingly handle and reasonably schedule arbitrary combinations of schema change statements that are valid in Postgres. Unlike mysql postgres offers transactional schema changes. Unlike Postgres, cockroach strives to implement online schema changes in a protocol inspired by f1 [0]. Also, you want to make sure you can safely roll back (until you’ve reached the point where you know it can’t fail, then only metadata updates are allowed). The model we came up with was to decompose all things that can possibly change into “elements” [1] and each element had a schedule of state transitions that move the element through a sequence of states from public to absent or vice versa [2]. Each state transitions has operations [3]. Anyway, you end up wanting to define rules that say that certain element states have to be entered before other if the elements are related in some way. Or perhaps some transitions should happen at the same time. To express these rules I created a little datalog-like framework I called rel [4]. This lets you embed in go a rules engine that then you can add indexes to so that you can have sufficiently efficient implementation and know that all your lookups are indexed statically. You write the rules in Go [5]. To be honest it could be more ergonomic. The rules are written in Go but for testing and visibility they produce a datomic-inspired format [6]. There’s a lot of rules now! The internal implementation isn’t too far off from the search implementation presented here [7]. Here’s unify [8]. The thing has some indexes and index selection for acceleration. It also has inverted indexes for set containment queries. It was fun to make a little embedded logic language and to have had a reason to! 0: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41376.pdf https://static.googleusercontent.com/media/research.google.c... 1: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scpb/elements.proto#L24 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 2: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scplan/internal/opgen/opgen_column.go#L16 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 3: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scop/immediate_mutation.go#L52 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 4: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/rel/doc.go#L6 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 5: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scplan/internal/rules/release_25_2/dep_add_column.go#L16 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 6: https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/schemachanger/scplan/internal/rules/release_25_2/testdata/deprules https://github.com/cockroachdb/cockroach/blob/master/pkg/sql... 7: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/rel/query_eval.go#L97 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 8: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/rel/query_eval.go#L339 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
cartucho1 1y ago
Not really logic programming, but a while ago I made this, also in Python: https://github.com/ariroffe/logics https://github.com/ariroffe/logics (mainly for educational purposes). Parts of the implementation kind of reminded me of it.
michae2 1y ago
Something I’ve wondered about Datalog is whether integers can be added to the language without losing guarantees about termination of query evaluation. It seems like as soon as we add integers with successor() or strings with concat() then we can potentially create infinite relations. Is there a way to add integers or strings (well, really basic scalar operations on integer or string values) while preserving termination guarantees? This bit at the end of the article seems to imply it’s possible, maybe with some tricks? > We could also add support for arithmetic and composite atoms (like lists), which introduce some challenges if we wish to stay “Turing-incomplete”.
- ulrikrasmussen 1y ago
  Not without a termination checker. Take a look at Twelf, it is a logic programming language and proof assistant based on the dependently typed LF logical framework. You can use general algebraic types in relations, and in general queries can be non-terminating. However, the system has a fairly simple way of checking termination using moded relations and checking that recursive calls have structurally smaller terms in all arguments. Twelf is quite elegant, although not as powerful as other proof assistants such as Coq. Proofs in Twelf are simply logic programs which have been checked to be total and terminating. Edit: Here's a link to a short page in the manual which shows how termination checking works: https://twelf.org/wiki/percent-terminates/ https://twelf.org/wiki/percent-terminates/ The syntax of Twelf is a bit different from other logic languages, but just note that every rule must have a name and that instead of writing `head :- subgoal1, subgoal2, ..., subgoaln` you write `ruleName : head <- subgoal1 <- subgoal2 <- ... <- subgoaln`. Also note that this approach only works for top-down evaluation because it still allows you to define infinite relations (e.g. the successor relation for natural numbers is infinite). Bottom-up evaluation will fail to terminate unless restricted to only derive facts that contribute to some ground query. I don't know if anyone have looked into that problem, but that seems interesting. It is probably related to the "magic sets" transformation for optimizing bottom-up queries, but as far as I understand that does not give any hard guarantees to performance, and I don't know how it would apply to this problem.
- wduquette 1y ago
  It’s all about the terms. As soon as rules can create an infinite sequence of new terms for a single relation, e.g. by addition, you’ve got non-termination.
kriro 1y ago
I love Prolog but haven't used it in ages. I should really give it a go again. Whenever I used it my brain needed some adjustment time and then switched to declarative mode. It's a really unique experience and hard to describe. It was also my first contact with immutable data. Is implementing a Kanren and embedding it as suggested by the author really the recommended approach? Back in the day I used Sicstus mostly but tried to use SWI whenever possible (because I'm a FLOSS guy at heart). I'm asking because we went the opposite direction and used Prolog as the first language and called Java or C when needed (io, GUI). I'd describe the result as a "hot mess". Random note: "Art of Prolog" and "Craft of Prolog" remain two of my favorite CS books to this day. I'd be curious what the "state of the art" is these days and would love ve to hear from some folks using Prolog in the trenches.
- sirwhinesalot 1y ago
  I can't claim it's the recommended approach, just my own personal recommendation. I apologize if I made it seem like I'm some authority on the subject, I'm just some rando that dislikes SQL. Funny enough, I made the same mistake you did back in the day. Used Prolog as the "boss" that just called back to Java as needed. My professor gave me a shitty grade because the idea was to make the opposite, a Java program that queries a Prolog database to make decisions, the Prolog part itself wasn't directly supposed to make any. I was pissed at the time since I was showing off my Prolog skills which in a Logic Programming course I expected would give me a good grade, but that professor was 100% right. The power of logic programming is tainted when you mix it with IO and expect a specific ordering to the rule applications. Cuts are a sin.
  - deleted 1y ago
    [deleted]
  - YeGoblynQueenne 1y ago
    Cuts are perfectly fine. What's the problem cuts have caused you?
    - sirwhinesalot 1y ago
b0a04gl 1y ago
i tried writing a tiny logic engine once after reading the SICP chapter and yeah, the syntax part was easy to mimic but the actual backtracking logic hit me harder than expected. what helped was thinking of it less like solving and more like building a lazy search tree. once that clicked, i stopped trying to force control flow and just let the tree expand. one thing i didn’t see many mention handling stateful part or side effects blows up fast. even printing during backtracking messes the whole thing. most tutorials avoid that part completely
- sirwhinesalot 1y ago
  That's one of the reasons I tell people to avoid Prolog. Leave the side effects to the host language and embed either a miniKanren or Datalog engine.
  - b0a04gl 1y ago
    [dead]
deosjr 1y ago
I recently implemented a version of Bret Victor's Dynamicland in the browser using miniKanren, Datalog, and WebAssembly: https://deosjr.github.io/dynamicland/ https://deosjr.github.io/dynamicland/ Knowing how to implement a small logic programming language from scratch really feels like a superpower sometimes.
tracnar 1y ago
For logic in Python this project looks pretty neat, it encodes facts as typed objects and rules as functions, then allows you to run the model using a solver like soufflé: https://py-typedlogic.github.io/ https://py-typedlogic.github.io/ I haven't found an excuse to really use it though!
usgroup 1y ago
Prolog seems cursed to be forgotten and re-discovered in a never ending cycle.
scapbi 1y ago
This thread was the final push I needed to add logic programming to Mochi https://github.com/mochilang/mochi https://github.com/mochilang/mochi — a small statically typed scripting language I’m building for agents and real-time data. I gave OpenAI Codex a single prompt with a sample like: fact parent("Alice", "Bob") rule grandparent(x, z) :- parent(x, y), parent(y, z) let gps = query grandparent(x, z) And it generated a working Datalog engine in Go with: - fact storage + recursive rule support - bottom-up fixpoint evaluation - unification and `!=` constraints - FFI bindings to expose `fact`, `rule`, and `query` to scripts Full thinking process: https://chatgpt.com/s/cd_684d3e3c59c08191b20c49ad97b66e01 https://chatgpt.com/s/cd_684d3e3c59c08191b20c49ad97b66e01 Total implementation was ~250 LOC. Genuinely amazed how effective the LLM was at helping bootstrap a real logic layer in one go. The PR is here https://github.com/mochilang/mochi/pull/616 https://github.com/mochilang/mochi/pull/616
IamDaedalus 1y ago
I was thinking of an idea very similar to this some weeks ago where you define the "rules" that structure your program and I think prolog is the one! I'll looking into getting a taste this weekend
jpfr 1y ago
Microkanren et al are nice! But it is becoming sort of a mono-culture where other approaches get ignored. Before Microkanren, the rite of passage for logic programming was to build a Prolog using Warren's Abstract Machine (WAM). https://direct.mit.edu/books/monograph/4253/Warren-s-Abstract-MachineA-Tutorial-Reconstruction https://direct.mit.edu/books/monograph/4253/Warren-s-Abstrac...
- sirwhinesalot 1y ago
  Well, the blog post has a Datalog implementation, so there is that.
sundarurfriend 1y ago
The only real experience I've had with logic programming is via Brachylog[1], and I enjoyed it very much. It's a golfing language that I used on codegolf.SE, so my experience is probably very different from that of someone who used logic programming for "real" coding. But I found the experience very pleasurable: the fun in codegolfing is largely from bending your mind in unusual ways to approach the problem (and its sub-problems) differently to solve it with terser code. Brachylog added to this by providing its own set of (what to me were) unusual approaches, thus making sure that the process was always fresh and weird enough to be fun. [1] https://github.com/JCumin/Brachylog/wiki https://github.com/JCumin/Brachylog/wiki
YeGoblynQueenne 1y ago
>> The main issue is that Prolog is not truly declarative; how you write the rules has a major impact on how the interpreter behaves. You might end up with repeated answers for a query or it might enter an infinite loop. Prolog also allows IO, so the order in which things get executed is critical. It’s Turing-complete, for better or worse. Yeah, sounds like a real show-stopper. Prolog is not 100% declarative, which is really what every programmer wants from a programming language. Better use a language like C# or Java, or Python, which are 0% declarative. Or try to implement datalog (only not really) so that you can't even use lists because that's what real-word programmers are looking for in a real-world programming language: 100% declarative, 0% real-world uses. Ah well, at least the author has heard of SLD-Resolution which is more than one can say about the authors of SICP. But they haven't heard of SLG Resolution with tabulation (a.k.a. "tabling") which is a way to execute Prolog programs while preserving the Turing-completeness but without getting stuck in left-recursions. Among other things. https://www.swi-prolog.org/pldoc/man?section=tabling https://www.swi-prolog.org/pldoc/man?section=tabling Edit: >> Prolog also allows IO, so the order in which things get executed is critical. I paid €7 to make this post because I'm on a boat in the middle of the Adriatic sea and my Vodafone contract is AWOL, so listen closely: no, Prolog's IO is not what makes it Turing Complete. That comes from definite logic, i.e. a fragment of the First Order Predicate Calculus (a.k.a. First Order Logic) restricted to formulae in clausal form with at most one positive literal a.k.a Horn clauses, that nevertheless retains the full expressivity of full FOL. Definite logic is semi-decidable and when evaluated by Resolution, as SLD-Resolution (restricted to definite program clauses and Horn goals), it is refutation-complete (and sound, to boot). Meaning, in summary, that any true sentence can be proved true but if a sentence is false then it cannot always be proved false, by SLD-Resolution. So far, so theoretically good. What Prolog does which is really dangerous and makes the order of execution "critical" is that it allows the programmer to edit the program database i.e. the database of facts and rules, in other words, the program itself, programmatically, i.e from the program itself. This means that not all your program's state is known before the program runs and database operations are completed. That sucks hairy balls but it is also a very useful mechanism that requires experience and understanding of the language, its core concepts, and programming in general, to use right. But Prolog's Turing completeness has nothing to do with IO, or database ops. That was not worth €7.
sytelus 1y ago
This is great article but it is ruined because author chose to use substack. I don't know why people keep following herd and endup publishing on substack. If you already don't know, Substack has disallowed ChatGPT to crawl anything so you cannot take AI assistance to work on the content. They got this content for free but they want to gatekeep it for profiting from it. Additionally, substack is intentionally horrible at letting allow nicely formatted pdf or readable versions downloaded to lock out the content even further. No one in their right mind should be using substack. Folks, really, using GitHub pages with static website generator is all you need. Your content will be nice and truly freely accessible to everyone.
- vdqtp3 1y ago
  > Substack has disallowed ChatGPT to crawl anything so you cannot take AI assistance to work on the content Is that really a criticism?

217 points by sirwhinesalot 1y ago

Or more accurately, a super simple Datalog implementation.

I second the recommendation in Sir Whinesalot's post (which I haven't fully read yet) to look at miniKanren and microKanren. I found it extremely educational to port microKanren to OCaml a few years ago, and I think the result is somewhat more comprehensible than the original Scheme, though you'll still probably have to read the paper to understand it: http://canonical.org/~kragen/sw/dev3/mukanren.ml http://canonical.org/~kragen/sw/dev3/mukanren.ml The most astonishing result of miniKanren is a Scheme interpreter that you can run forwards, backwards, or both. http://webyrd.net/quines/quines.pdf http://webyrd.net/quines/quines.pdf demonstrates using it to generate a Scheme quine, that is, a Scheme program whose output when run is itself ("miniKanren, Live and Untagged: Quine Generation via Relational Interpreters (Programming Pearl)", Byrd, Holk, and Friedman). §4.4 of SICP http://sarabander.github.io/sicp/html/4_002e4.xhtml http://sarabander.github.io/sicp/html/4_002e4.xhtml also has an implementation of logic programming in Scheme which is extremely approachable. Unlike the post, I don't think Datalog is the place to look for deep insights about logic programming. Instead, it's the place to look for deep insights about databases.

fcatalan 1y ago
I concur that SICP 4.4 is very approachable. I once took a class that had a simple Prolog assignment, I recall we were given some building plans and had to program a path solver through the building. I thought it was a bit too easy and I wanted to dig deeper, because just doing the task left you with a taste of "this is magic, just use these spells". I looked at how to implement Prolog and was stumped until I found that SICP section. So I ported it to JavaScript and gave it a Prolog-like syntax and made a web page where you could run the assignment but also exposed the inner workings, and it was one of the neatest things I've ever handed in as coursework.
sirwhinesalot 1y ago
Insights shminsights, the database connection is where it is at :P (Thank you for reading the article, I also implemented microKanren before and it's insane how little code it takes to get full a logic programming engine going)
anthk 1y ago
Among SICP, https://t3x.org/amk/index.html https://t3x.org/amk/index.html Same approach. I think an older version of the book it's freely available, or maybe the one on Scheme itself. Scheme being homoiconic makes far easier to create quines.

xlii 1y ago

Lately I’ve been dabbling with different Prolog implementations and Constraint Handling Rules which led me to CLIPS [0] (in Public Domain, but developed at NASA - sounds neat doesn’t it?) It’s not very easy to get into, but it’s very fast on rule resolution and being pure C is easy to integrate. I’m trying to get smart code parsing using logic language and this seems promising. I’m also a Lisp nerd so that works for me :) [0]: https://www.clipsrules.net/ https://www.clipsrules.net/

veqq 1y ago
https://ryjo.codes/ https://ryjo.codes/ has done a lot of work with it, and made a course!
- xlii 1y ago
  Whoa, awesome! Thanks for the link.
7373737373 1y ago
CLIPS is also used by the Magic the Gathering Arena game engine to implement part of the game logic: https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-naps-and-living-breakthrough https://magic.wizards.com/en/news/mtg-arena/on-whiteboards-n...

fracus 1y ago

I think it would be really impactful to start with a problem and describe how logic programming solves that problem better than the other paradigms.

cjonas 1y ago
The only production experience I have with logic programming is OPA Rego for writing security policies (not sure it's a "pure" logic language but feels like the primary paradigm). I found it pretty interesting for that use case, although the learning curve isn't trivial for traditional devs. https://www.openpolicyagent.org/ https://www.openpolicyagent.org/
dkjaudyeqooe 1y ago
Generally speaking, the advantage of logic programming is that it's (more) declarative: you describe the problem and it derives a solution.
- taeric 1y ago
  Ish? Is only really true if what you are programming can be seen as a search for the completion of a statement? For an easy example to consider, what would the logical program look like that described any common fractal? https://rosettacode.org/wiki/Koch_curve#Prolog https://rosettacode.org/wiki/Koch_curve#Prolog shows that... it is not necessarily a win for this idea. For the general task asked in the OP here, I would hope you could find an example in rosettacode that shows prolog gets a good implementation. Unfortunately, I get the impression some folks prefer code golf for these more so than they do "makes the problem obvious."
  - rabbits77 1y ago
    I’d argue that is not the most ideal Prolog solution. More like it’s simply a recursive implementation of an imperative solution. For fractals you’ll want to be able to recognize and generate the structures. It’s a great use case for Definite Clause Grammars (DCGs). A perfect example of this would be Triska’s Dragon Curve implementation. https://www.youtube.com/watch?v=DMdiPC1ZckI https://www.youtube.com/watch?v=DMdiPC1ZckI

deleted 1y ago

[deleted]

ashton314 1y ago

I did a detailed write-up of implementing miniKanren here: https://codeberg.org/ashton314/microKanren https://codeberg.org/ashton314/microKanren By the end of it, I implement a small type checker that, when you run it backwards (by giving the checker a type), it proceeds to enumerate programs that inhabit that type!

kragen 1y ago
Isn't that amazing‽ I wonder if you could guide its search with an LLM...
- ashton314 1y ago
  There is some research work I’m aware of that’s trying to make type-safe LLM generation a thing.
  - whitten 1y ago
    Is that research publically available, and where ?
    - lucascdotnet 1y ago
      Not sure if this is what you mean, but 'inductive logic programming' and more generally 'program synthesis' are fairly active research areas.
    - ashton314 1y ago
      This paper appeared at PLDI '25: https://arxiv.org/abs/2504.09246 https://arxiv.org/abs/2504.09246 Discussed on HN at the time: https://news.ycombinator.com/item?id=43978357 https://news.ycombinator.com/item?id=43978357

xelxebar 1y ago

https://github.com/Seeker04/plwm https://github.com/Seeker04/plwm This window manager implemented in Prolog popped up here recently. It's really cool! I jumped to it as a new daily driver in the hope that I'd learn some Prolog, and it's been quite the success, actually. The developer is really nice, and he's generously helped me with some basic questions and small PRs. Definitely recommended. I have a Guix package for it if anyone's interested. Any reading recommendations for high quality logic programming codebases?

johnisgood 1y ago
You should publish the Guix package somewhere.

philzook 1y ago

Nice! I'll note there is a really shallow version of naive datalog I rather like if you're willing to compromise on syntax and nonlinear variable use. edge = {(1,2), (2,3)} path = set() for i in range(10): # path(x,y) :- edge(x,y). path |= edge # path(x,z) :- edge(x,y), path(y,z). path |= {(x,z) for x,y in edge for (y1,z) in path if y == y1} Similarly it's pretty easy to hand write SQL in a style that looks similar and gain a lot of functionality and performance from stock database engines. https://www.philipzucker.com/tiny-sqlite-datalog/ https://www.philipzucker.com/tiny-sqlite-datalog/ I wrote a small datalog from the Z3 AST to sqlite recently along these lines https://github.com/philzook58/knuckledragger/blob/main/kdrag/solvers/datalog.py https://github.com/philzook58/knuckledragger/blob/main/kdrag...

kragen 1y ago
That's exciting!
ulrikrasmussen 1y ago
Thank you! I have been searching for something like this but for some reason couldn't find your work. I am currently implementing a Datalog to PostgreSQL query engine at work as we want to experiment with modeling authorization rules in Datalog and then run authorization queries directly in the database. As I want to minimize the round trips to the database I use a different approach than yours and translate Datalog programs to recursive CTEs. These are a bit limited, so we have to restrict ourselves to linearly recursive Datalog programs, but for the purpose of modeling authorization rules that seems to be enough (e.g. you can still model things such as "permissions propagate from groups to group members").
- whitten 1y ago
  What does CTE stand for, and how do I research it ?
  - burakemir 1y ago
    Common Table Expression, a SQL concept that enables more expressive programming with SQL queries. They are introduced using WITH ...

vvern 1y ago

Some time ago I worked on cockroachdb and I was working on implementing planning for complex online schema changes. We really wanted a model that could convincingly handle and reasonably schedule arbitrary combinations of schema change statements that are valid in Postgres. Unlike mysql postgres offers transactional schema changes. Unlike Postgres, cockroach strives to implement online schema changes in a protocol inspired by f1 [0]. Also, you want to make sure you can safely roll back (until you’ve reached the point where you know it can’t fail, then only metadata updates are allowed). The model we came up with was to decompose all things that can possibly change into “elements” [1] and each element had a schedule of state transitions that move the element through a sequence of states from public to absent or vice versa [2]. Each state transitions has operations [3]. Anyway, you end up wanting to define rules that say that certain element states have to be entered before other if the elements are related in some way. Or perhaps some transitions should happen at the same time. To express these rules I created a little datalog-like framework I called rel [4]. This lets you embed in go a rules engine that then you can add indexes to so that you can have sufficiently efficient implementation and know that all your lookups are indexed statically. You write the rules in Go [5]. To be honest it could be more ergonomic. The rules are written in Go but for testing and visibility they produce a datomic-inspired format [6]. There’s a lot of rules now! The internal implementation isn’t too far off from the search implementation presented here [7]. Here’s unify [8]. The thing has some indexes and index selection for acceleration. It also has inverted indexes for set containment queries. It was fun to make a little embedded logic language and to have had a reason to! 0: https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/41376.pdf https://static.googleusercontent.com/media/research.google.c... 1: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scpb/elements.proto#L24 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 2: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scplan/internal/opgen/opgen_column.go#L16 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 3: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scop/immediate_mutation.go#L52 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 4: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/rel/doc.go#L6 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 5: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/scplan/internal/rules/release_25_2/dep_add_column.go#L16 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 6: https://github.com/cockroachdb/cockroach/blob/master/pkg/sql/schemachanger/scplan/internal/rules/release_25_2/testdata/deprules https://github.com/cockroachdb/cockroach/blob/master/pkg/sql... 7: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/rel/query_eval.go#L97 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa... 8: https://github.com/cockroachdb/cockroach/blob/f48b3438a296aad0ff6e2ce88875c6021dfea872/pkg/sql/schemachanger/rel/query_eval.go#L339 https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...

cartucho1 1y ago

Not really logic programming, but a while ago I made this, also in Python: https://github.com/ariroffe/logics https://github.com/ariroffe/logics (mainly for educational purposes). Parts of the implementation kind of reminded me of it.

michae2 1y ago

Something I’ve wondered about Datalog is whether integers can be added to the language without losing guarantees about termination of query evaluation. It seems like as soon as we add integers with successor() or strings with concat() then we can potentially create infinite relations. Is there a way to add integers or strings (well, really basic scalar operations on integer or string values) while preserving termination guarantees? This bit at the end of the article seems to imply it’s possible, maybe with some tricks? > We could also add support for arithmetic and composite atoms (like lists), which introduce some challenges if we wish to stay “Turing-incomplete”.

ulrikrasmussen 1y ago
Not without a termination checker. Take a look at Twelf, it is a logic programming language and proof assistant based on the dependently typed LF logical framework. You can use general algebraic types in relations, and in general queries can be non-terminating. However, the system has a fairly simple way of checking termination using moded relations and checking that recursive calls have structurally smaller terms in all arguments. Twelf is quite elegant, although not as powerful as other proof assistants such as Coq. Proofs in Twelf are simply logic programs which have been checked to be total and terminating. Edit: Here's a link to a short page in the manual which shows how termination checking works: https://twelf.org/wiki/percent-terminates/ https://twelf.org/wiki/percent-terminates/ The syntax of Twelf is a bit different from other logic languages, but just note that every rule must have a name and that instead of writing `head :- subgoal1, subgoal2, ..., subgoaln` you write `ruleName : head <- subgoal1 <- subgoal2 <- ... <- subgoaln`. Also note that this approach only works for top-down evaluation because it still allows you to define infinite relations (e.g. the successor relation for natural numbers is infinite). Bottom-up evaluation will fail to terminate unless restricted to only derive facts that contribute to some ground query. I don't know if anyone have looked into that problem, but that seems interesting. It is probably related to the "magic sets" transformation for optimizing bottom-up queries, but as far as I understand that does not give any hard guarantees to performance, and I don't know how it would apply to this problem.
wduquette 1y ago
It’s all about the terms. As soon as rules can create an infinite sequence of new terms for a single relation, e.g. by addition, you’ve got non-termination.

kriro 1y ago

I love Prolog but haven't used it in ages. I should really give it a go again. Whenever I used it my brain needed some adjustment time and then switched to declarative mode. It's a really unique experience and hard to describe. It was also my first contact with immutable data. Is implementing a Kanren and embedding it as suggested by the author really the recommended approach? Back in the day I used Sicstus mostly but tried to use SWI whenever possible (because I'm a FLOSS guy at heart). I'm asking because we went the opposite direction and used Prolog as the first language and called Java or C when needed (io, GUI). I'd describe the result as a "hot mess". Random note: "Art of Prolog" and "Craft of Prolog" remain two of my favorite CS books to this day. I'd be curious what the "state of the art" is these days and would love ve to hear from some folks using Prolog in the trenches.

sirwhinesalot 1y ago
I can't claim it's the recommended approach, just my own personal recommendation. I apologize if I made it seem like I'm some authority on the subject, I'm just some rando that dislikes SQL. Funny enough, I made the same mistake you did back in the day. Used Prolog as the "boss" that just called back to Java as needed. My professor gave me a shitty grade because the idea was to make the opposite, a Java program that queries a Prolog database to make decisions, the Prolog part itself wasn't directly supposed to make any. I was pissed at the time since I was showing off my Prolog skills which in a Logic Programming course I expected would give me a good grade, but that professor was 100% right. The power of logic programming is tainted when you mix it with IO and expect a specific ordering to the rule applications. Cuts are a sin.
- deleted 1y ago
  [deleted]
- YeGoblynQueenne 1y ago
  Cuts are perfectly fine. What's the problem cuts have caused you?
  - sirwhinesalot 1y ago

b0a04gl 1y ago

i tried writing a tiny logic engine once after reading the SICP chapter and yeah, the syntax part was easy to mimic but the actual backtracking logic hit me harder than expected. what helped was thinking of it less like solving and more like building a lazy search tree. once that clicked, i stopped trying to force control flow and just let the tree expand. one thing i didn’t see many mention handling stateful part or side effects blows up fast. even printing during backtracking messes the whole thing. most tutorials avoid that part completely

sirwhinesalot 1y ago
That's one of the reasons I tell people to avoid Prolog. Leave the side effects to the host language and embed either a miniKanren or Datalog engine.
- b0a04gl 1y ago
  [dead]

deosjr 1y ago

I recently implemented a version of Bret Victor's Dynamicland in the browser using miniKanren, Datalog, and WebAssembly: https://deosjr.github.io/dynamicland/ https://deosjr.github.io/dynamicland/ Knowing how to implement a small logic programming language from scratch really feels like a superpower sometimes.

tracnar 1y ago

For logic in Python this project looks pretty neat, it encodes facts as typed objects and rules as functions, then allows you to run the model using a solver like soufflé: https://py-typedlogic.github.io/ https://py-typedlogic.github.io/ I haven't found an excuse to really use it though!

usgroup 1y ago

Prolog seems cursed to be forgotten and re-discovered in a never ending cycle.

scapbi 1y ago

This thread was the final push I needed to add logic programming to Mochi https://github.com/mochilang/mochi https://github.com/mochilang/mochi — a small statically typed scripting language I’m building for agents and real-time data. I gave OpenAI Codex a single prompt with a sample like: fact parent("Alice", "Bob") rule grandparent(x, z) :- parent(x, y), parent(y, z) let gps = query grandparent(x, z) And it generated a working Datalog engine in Go with: - fact storage + recursive rule support - bottom-up fixpoint evaluation - unification and `!=` constraints - FFI bindings to expose `fact`, `rule`, and `query` to scripts Full thinking process: https://chatgpt.com/s/cd_684d3e3c59c08191b20c49ad97b66e01 https://chatgpt.com/s/cd_684d3e3c59c08191b20c49ad97b66e01 Total implementation was ~250 LOC. Genuinely amazed how effective the LLM was at helping bootstrap a real logic layer in one go. The PR is here https://github.com/mochilang/mochi/pull/616 https://github.com/mochilang/mochi/pull/616

IamDaedalus 1y ago

I was thinking of an idea very similar to this some weeks ago where you define the "rules" that structure your program and I think prolog is the one! I'll looking into getting a taste this weekend

jpfr 1y ago

Microkanren et al are nice! But it is becoming sort of a mono-culture where other approaches get ignored. Before Microkanren, the rite of passage for logic programming was to build a Prolog using Warren's Abstract Machine (WAM). https://direct.mit.edu/books/monograph/4253/Warren-s-Abstract-MachineA-Tutorial-Reconstruction https://direct.mit.edu/books/monograph/4253/Warren-s-Abstrac...

sirwhinesalot 1y ago
Well, the blog post has a Datalog implementation, so there is that.

sundarurfriend 1y ago

The only real experience I've had with logic programming is via Brachylog[1], and I enjoyed it very much. It's a golfing language that I used on codegolf.SE, so my experience is probably very different from that of someone who used logic programming for "real" coding. But I found the experience very pleasurable: the fun in codegolfing is largely from bending your mind in unusual ways to approach the problem (and its sub-problems) differently to solve it with terser code. Brachylog added to this by providing its own set of (what to me were) unusual approaches, thus making sure that the process was always fresh and weird enough to be fun. [1] https://github.com/JCumin/Brachylog/wiki https://github.com/JCumin/Brachylog/wiki

YeGoblynQueenne 1y ago

>> The main issue is that Prolog is not truly declarative; how you write the rules has a major impact on how the interpreter behaves. You might end up with repeated answers for a query or it might enter an infinite loop. Prolog also allows IO, so the order in which things get executed is critical. It’s Turing-complete, for better or worse. Yeah, sounds like a real show-stopper. Prolog is not 100% declarative, which is really what every programmer wants from a programming language. Better use a language like C# or Java, or Python, which are 0% declarative. Or try to implement datalog (only not really) so that you can't even use lists because that's what real-word programmers are looking for in a real-world programming language: 100% declarative, 0% real-world uses. Ah well, at least the author has heard of SLD-Resolution which is more than one can say about the authors of SICP. But they haven't heard of SLG Resolution with tabulation (a.k.a. "tabling") which is a way to execute Prolog programs while preserving the Turing-completeness but without getting stuck in left-recursions. Among other things. https://www.swi-prolog.org/pldoc/man?section=tabling https://www.swi-prolog.org/pldoc/man?section=tabling Edit: >> Prolog also allows IO, so the order in which things get executed is critical. I paid €7 to make this post because I'm on a boat in the middle of the Adriatic sea and my Vodafone contract is AWOL, so listen closely: no, Prolog's IO is not what makes it Turing Complete. That comes from definite logic, i.e. a fragment of the First Order Predicate Calculus (a.k.a. First Order Logic) restricted to formulae in clausal form with at most one positive literal a.k.a Horn clauses, that nevertheless retains the full expressivity of full FOL. Definite logic is semi-decidable and when evaluated by Resolution, as SLD-Resolution (restricted to definite program clauses and Horn goals), it is refutation-complete (and sound, to boot). Meaning, in summary, that any true sentence can be proved true but if a sentence is false then it cannot always be proved false, by SLD-Resolution. So far, so theoretically good. What Prolog does which is really dangerous and makes the order of execution "critical" is that it allows the programmer to edit the program database i.e. the database of facts and rules, in other words, the program itself, programmatically, i.e from the program itself. This means that not all your program's state is known before the program runs and database operations are completed. That sucks hairy balls but it is also a very useful mechanism that requires experience and understanding of the language, its core concepts, and programming in general, to use right. But Prolog's Turing completeness has nothing to do with IO, or database ops. That was not worth €7.

sytelus 1y ago

This is great article but it is ruined because author chose to use substack. I don't know why people keep following herd and endup publishing on substack. If you already don't know, Substack has disallowed ChatGPT to crawl anything so you cannot take AI assistance to work on the content. They got this content for free but they want to gatekeep it for profiting from it. Additionally, substack is intentionally horrible at letting allow nicely formatted pdf or readable versions downloaded to lock out the content even further. No one in their right mind should be using substack. Folks, really, using GitHub pages with static website generator is all you need. Your content will be nice and truly freely accessible to everyone.

vdqtp3 1y ago
> Substack has disallowed ChatGPT to crawl anything so you cannot take AI assistance to work on the content Is that really a criticism?