4 ms·

Datalog in miniKanren

134 points by deosjr 1y ago

deosjr 1y ago
Seems like interest in Datalog is high this week, so I thought I'd share a write-up of a minimal Datalog implementation I did a while ago. Runs in the browser using Hoot (https://spritely.institute/hoot/ https://spritely.institute/hoot/) which compiles Guile Scheme to WebAssembly.
- davexunit 1y ago
  Wow this might be the coolest use of Hoot I've seen! I need to run this for myself soon.
  - deosjr 1y ago
    Thanks Dave, high praise! I was inspired after seeing you all take over the declarative & minimalist programming room at FOSDEM this year. If you thought this was cool, wait until you see what I ended up using it for: https://deosjr.github.io/dynamicland/ https://deosjr.github.io/dynamicland/ I personally think this is much cooler :) But it needs some more explaining before I can broadly share, I think. Now that I have you here, a question: am I correct in thinking that in Hoot, eval in the browser does not currently work with macros?
    - davexunit 1y ago
      I'm glad you felt inspired! This Dynamicland implementation looks awesome. I look forward to this being shared to a wider audience. :) Regarding your question, as of Hoot 0.6.1 we now have a psyntax-based macro expander integrated with eval so you can use syntax-rules and syntax-case. There are still rough edges, though. I'm currently focused on some non-Hoot tasks but the next Hoot priority is to implement a Guile-like REPL and really kick the tires on the interpreter before the 0.7.0 release.
fithisux 1y ago
What scheme is this?
- deosjr 1y ago
  Guile Scheme. See https://github.com/deosjr/deosjr.github.io/blob/master/dynamicland/modules/datalog.scm https://github.com/deosjr/deosjr.github.io/blob/master/dynam... for more.
upghost 1y ago
Datalog is a syntactic subset of Prolog[1], which this is... not. I think the most misunderstood thing about Prolog (and Datalog, the functor-free subset of pure Prolog) is that the syntax is really, really important. It's like, the whole gimmick of the language. It is designed to efficiently and elegantly query and transform itself. If you lose the syntax you lose all of intermediate and advanced Prolog (and Datalog). [1]: https://en.m.wikipedia.org/wiki/Datalog https://en.m.wikipedia.org/wiki/Datalog
- kragen 1y ago
  Semantics are more important than syntax. Prolog's flexible syntax is a nice-to-have rather than essential when you're in Lisp. And Datalog is purely first-order, so the advanced Prolog you're talking about doesn't exist in it. However, syntax does matter, and this is not acceptable (dl-find (fresh-vars 1 (lambda (?id) (dl-findo dl ((,?id reachable ,?id))))))) as a way to ask reachable(Id, Id). I think you could, however, write a bit more Scheme and be able to ask (?id reachable ?id) which would be acceptable. However, the ordering betrays a deeper semantic difference with orthodox Datalog, which is about distinct N-ary relations, like a relational database, not binary relations. This implementation seems to be specific to binary relations, so it's not really Datalog for reasons that go beyond mere syntax. On the other hand, this (from the initial goal) would be perfectly fine: (dl-rule! dl (reachable ,?x ,?y) :- (edge ,?x ,?z) (reachable ,?z ,?y)) The orthodox Datalog syntax is: reachable(X, Y) :- edge(X, Z), reachable(Z, Y).
  - jitl 1y ago
    Shouldn’t lisp macros make it easy to present such a nice syntax? Perhaps the author could easily implement that bit, if not the wide rows. Or is that the point you’re making? There is a dl-rule here: https://github.com/deosjr/deosjr.github.io/blob/15b5f7e021537e008d1bbccc86c6b0f16503f259/dynamicland/modules/datalog.scm#L91 https://github.com/deosjr/deosjr.github.io/blob/15b5f7e02153...
    - kragen 1y ago

134 points by deosjr 1y ago

Seems like interest in Datalog is high this week, so I thought I'd share a write-up of a minimal Datalog implementation I did a while ago. Runs in the browser using Hoot (https://spritely.institute/hoot/ https://spritely.institute/hoot/) which compiles Guile Scheme to WebAssembly.

davexunit 1y ago
Wow this might be the coolest use of Hoot I've seen! I need to run this for myself soon.
- deosjr 1y ago
  Thanks Dave, high praise! I was inspired after seeing you all take over the declarative & minimalist programming room at FOSDEM this year. If you thought this was cool, wait until you see what I ended up using it for: https://deosjr.github.io/dynamicland/ https://deosjr.github.io/dynamicland/ I personally think this is much cooler :) But it needs some more explaining before I can broadly share, I think. Now that I have you here, a question: am I correct in thinking that in Hoot, eval in the browser does not currently work with macros?
  - davexunit 1y ago
    I'm glad you felt inspired! This Dynamicland implementation looks awesome. I look forward to this being shared to a wider audience. :) Regarding your question, as of Hoot 0.6.1 we now have a psyntax-based macro expander integrated with eval so you can use syntax-rules and syntax-case. There are still rough edges, though. I'm currently focused on some non-Hoot tasks but the next Hoot priority is to implement a Guile-like REPL and really kick the tires on the interpreter before the 0.7.0 release.

fithisux 1y ago

What scheme is this?

deosjr 1y ago
Guile Scheme. See https://github.com/deosjr/deosjr.github.io/blob/master/dynamicland/modules/datalog.scm https://github.com/deosjr/deosjr.github.io/blob/master/dynam... for more.

upghost 1y ago

Datalog is a syntactic subset of Prolog[1], which this is... not. I think the most misunderstood thing about Prolog (and Datalog, the functor-free subset of pure Prolog) is that the syntax is really, really important. It's like, the whole gimmick of the language. It is designed to efficiently and elegantly query and transform itself. If you lose the syntax you lose all of intermediate and advanced Prolog (and Datalog). [1]: https://en.m.wikipedia.org/wiki/Datalog https://en.m.wikipedia.org/wiki/Datalog

kragen 1y ago
Semantics are more important than syntax. Prolog's flexible syntax is a nice-to-have rather than essential when you're in Lisp. And Datalog is purely first-order, so the advanced Prolog you're talking about doesn't exist in it. However, syntax does matter, and this is not acceptable (dl-find (fresh-vars 1 (lambda (?id) (dl-findo dl ((,?id reachable ,?id))))))) as a way to ask reachable(Id, Id). I think you could, however, write a bit more Scheme and be able to ask (?id reachable ?id) which would be acceptable. However, the ordering betrays a deeper semantic difference with orthodox Datalog, which is about distinct N-ary relations, like a relational database, not binary relations. This implementation seems to be specific to binary relations, so it's not really Datalog for reasons that go beyond mere syntax. On the other hand, this (from the initial goal) would be perfectly fine: (dl-rule! dl (reachable ,?x ,?y) :- (edge ,?x ,?z) (reachable ,?z ,?y)) The orthodox Datalog syntax is: reachable(X, Y) :- edge(X, Z), reachable(Z, Y).
- jitl 1y ago
  Shouldn’t lisp macros make it easy to present such a nice syntax? Perhaps the author could easily implement that bit, if not the wide rows. Or is that the point you’re making? There is a dl-rule here: https://github.com/deosjr/deosjr.github.io/blob/15b5f7e021537e008d1bbccc86c6b0f16503f259/dynamicland/modules/datalog.scm#L91 https://github.com/deosjr/deosjr.github.io/blob/15b5f7e02153...
  - kragen 1y ago