[HN Gopher] Implementing Logic Programming
___________________________________________________________________
Implementing Logic Programming
Author : sirwhinesalot
Score : 179 points
Date : 2025-06-13 21:32 UTC (1 days ago)
(HTM) web link (btmc.substack.com)
(TXT) w3m dump (btmc.substack.com)
| sirwhinesalot wrote:
| Or more accurately, a super simple Datalog implementation.
| kragen wrote:
| 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
|
| The most astonishing result of miniKanren is a Scheme interpreter
| that you can run forwards, backwards, or both.
| 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).
|
| SS4.4 of SICP 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 wrote:
| 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 wrote:
| 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 wrote:
| Among SICP, 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 wrote:
| 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/
| veqq wrote:
| https://ryjo.codes/ has done a lot of work with it, and made a
| course!
| xlii wrote:
| Whoa, awesome! Thanks for the link.
| fracus wrote:
| 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 wrote:
| 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/
| dkjaudyeqooe wrote:
| Generally speaking, the advantage of logic programming is that
| it's (more) declarative: you describe the problem and it
| derives a solution.
| taeric wrote:
| 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 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 wrote:
| 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
| taeric wrote:
| I would agree. I was actually hoping to be proven wrong
| with that example. I have yet to see anything other than
| a constraint program that looks easier to understand in
| logic programming, sadly.
| taeric wrote:
| Adding late to this, as I didn't get to actually look at
| this video yesterday.
|
| I would still agree that you can do better than the
| examples I'm finding, but I am not entirely clear why/how
| the dragon curve is honestly any better here? The prolog,
| notably, does not draw the curve. Just being used to
| generate the sequence of characters that describes it.
| But... that is already trivial in normal code.
|
| Actually drawing it will get you something like this:
| https://rosettacode.org/wiki/Dragon_curve#Prolog.
| Contrast that with the Logo version and you can see how
| the paradigm of the programming language can make a giant
| difference in how the code solution looks.
| trealira wrote:
| I've been reading a bit about it, and it seems easier to make
| goal-driven backwards chaining AI from it, like the block world
| example. You could in theory use that for something like a
| video game AI (like GOAP, Goal-Oriented Action Planning, which
| is based on STRIPS). Whenever I read about GOAP though, they
| seem to have used a graphical editor to declaratively input
| rules rather than a logic programming language.
|
| Note that I'm not an expert in any of this, I've just been
| reading about this kind of AI recently. I haven't actually done
| this myself.
| sirwhinesalot wrote:
| I mention the intuition in passing (you have an object graph
| with complex bidirectional and derived relationships). Any
| example that would truly show the benefit would be too big to
| show on a blog post. Treat it like the world's smartest
| database, that's the key.
|
| Another example would be something like an Entity Component
| System. The moment it starts getting complex (i.e., you have
| fancy queries and joins), then you're actually implementing a
| really shitty relational programming engine, and you might as
| well just implement Datalog instead at that point and reap the
| benefits.
|
| Other kinds of search problems are probably better tackled by
| constraint programming instead.
| ashton314 wrote:
| I did a detailed write-up of implementing miniKanren here:
|
| 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 wrote:
| Isn't that amazing!? I wonder if you could guide its search
| with an LLM...
| ashton314 wrote:
| There is some research work I'm aware of that's trying to
| make type-safe LLM generation a thing.
| whitten wrote:
| Is that research publically available, and where ?
| xelxebar wrote:
| 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 wrote:
| You should publish the Guix package somewhere.
| philzook wrote:
| 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/
|
| I wrote a small datalog from the Z3 AST to sqlite recently along
| these lines
| https://github.com/philzook58/knuckledragger/blob/main/kdrag...
| kragen wrote:
| That's exciting!
| ulrikrasmussen wrote:
| 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 wrote:
| What does CTE stand for, and how do I research it ?
| burakemir wrote:
| Common Table Expression, a SQL concept that enables more
| expressive programming with SQL queries. They are
| introduced using WITH ...
| philzook wrote:
| My suspicion is that if you can get away with it that
| recursive CTEs would be more performant than doing the
| datalog iteration query by query. AFAIK for general rules the
| latter is the only option though. I had a scam in that post
| to do seminaive using timestamps but it was ugly. I recently
| came across this new feature in duckdb and was wondering if
| there is some way to use it to make a nice datalog
| https://duckdb.org/2025/05/23/using-key.html . Anything that
| adds expressiveness to recursive CTEs is a possibility in
| that direction
| barrenko wrote:
| This requires some discrete math knowledge?
| sirwhinesalot wrote:
| If I ever get around to writing my own at least somewhat
| serious Datalog engine, I definitely want to add a "translate
| to SQL" capability. Your work looks like the perfect
| inspiration, thanks!
|
| (Also added a link to your article on what you can do with
| Datalog, excellent stuff, couldn't have written it better
| myself)
| philzook wrote:
| Thanks! I wouldn't so much say it was written so much as it
| was vomited out in a year of enthusiasm, but I'm glad it has
| some value.
| richard_shelton wrote:
| Or you can use Python AST + Z3 :) Here is a toy implementation:
|
| https://github.com/true-grue/python-dsls/blob/main/datalog/d...
| philzook wrote:
| Love it! I was trying to use python as a dsl frontend to Z3
| in a different way https://github.com/philzook58/knuckledragg
| er/blob/ecac7a568a... (it probably has to be done
| syntactically rather than by overloading in order to make
| `if` `and` etc work). Still not sure if it is ultimately a
| good idea. I think it's really neat how you're abusing `,`
| and `:` in these examples
| vvern wrote:
| 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.c...
| 1:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| 2:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| 3:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| 4:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| 5:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| 6:
| https://github.com/cockroachdb/cockroach/blob/master/pkg/sql...
| 7:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| 8:
| https://github.com/cockroachdb/cockroach/blob/f48b3438a296aa...
| cartucho1 wrote:
| Not really logic programming, but a while ago I made this, also
| in Python: https://github.com/ariroffe/logics (mainly for
| educational purposes). Parts of the implementation kind of
| reminded me of it.
| michae2 wrote:
| 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 wrote:
| 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/
|
| 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 wrote:
| 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.
| fogzen wrote:
| Yes, for some kinds of operations on some kinds of data
| structures. The keyword/property is "monotonicity". Monotonic
| functions are guaranteed to terminate under fixed-point
| semantics.
|
| Look into Datafun: A total functional language that generalizes
| Datalog. Also be sure to watch Datafun author Michael
| Arntzenius's Strangeloop talk.
|
| https://www.rntz.net/datafun/
|
| https://www.youtube.com/watch?v=gC295d3V9gE
| sirwhinesalot wrote:
| Hey, author here. The one time I go straight to bed after
| posting on hackernews is the one time I get a bunch of comments
| hahaha.
|
| Yes you can add support for integers in various ways where
| termination is still guaranteed. The simplest trick is to
| distinguish predicates (like pred(X, 42)) from constraints
| (like X > 7). Predicates have facts, constraints do not. When
| checking that every variable in the head of a rule appears in
| the body, add the condition that it appears in a _predicate_ in
| the body.
|
| So if you have a predicate like age(X:symbol, Y:int), you can
| use its facts to limit the set of integers under consideration.
| Then, if you write:
|
| age(X, A), A + 1 >= 18.
|
| You'd get everyone that becomes an adult next year. Fancier
| solutions are also possible, for example by employing
| techniques from finite domain constraint solving.
| michae2 wrote:
| Thanks, this is really helpful! And great article.
| judofyr wrote:
| Here's a quite recent interesting paper about this:
| https://dl.acm.org/doi/abs/10.1145/3643027
|
| > In this article, we study the convergence of datalog when it
| is interpreted over an arbitrary semiring. We consider an
| ordered semiring, define the semantics of a datalog program as
| a least fixpoint in this semiring, and study the number of
| steps required to reach that fixpoint, if ever. We identify
| algebraic properties of the semiring that correspond to certain
| convergence properties of datalog programs. Finally, we
| describe a class of ordered semirings on which one can use the
| semi-naive evaluation algorithm on any datalog program.
|
| It's quite neat since this allows them to represent linear
| regression, gradient decent, shortest path (APSP) within a very
| similar framework as regular Datalog.
|
| They have a whole section on the necessary condition for
| convergence (i.e. termination).
| kriro wrote:
| 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 wrote:
| 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.
| b0a04gl wrote:
| 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 wrote:
| 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 wrote:
| yeah agree. keeping side effects in host lang makes life
| easier. tried forcing it in prolog once and instantly
| regretted. miniKanren with clean boundaries felt way more
| maintainable
| deosjr wrote:
| I recently implemented a version of Bret Victor's Dynamicland in
| the browser using miniKanren, Datalog, and WebAssembly:
| https://deosjr.github.io/dynamicland/
|
| Knowing how to implement a small logic programming language from
| scratch really feels like a superpower sometimes.
| tracnar wrote:
| 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 souffle: https://py-
| typedlogic.github.io/
|
| I haven't found an excuse to really use it though!
| usgroup wrote:
| Prolog seems cursed to be forgotten and re-discovered in a never
| ending cycle.
| scapbi wrote:
| This thread was the final push I needed to add logic programming
| to 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
|
| 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
| IamDaedalus wrote:
| 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 wrote:
| 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-Abstrac...
| sirwhinesalot wrote:
| Well, the blog post has a Datalog implementation, so there is
| that.
| sundarurfriend wrote:
| 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
___________________________________________________________________
(page generated 2025-06-14 23:00 UTC)