6 ms·

Kanren – Logic Programming in Python

136 points by ausjke 8y ago

MauiWarrior 8y ago
There is already Problog with probability and logic. Could somebody help me understand benefits of Kanren?
- zimablue 8y ago
  I think you maybe need to know quite a lot about both in order to have a good answer. If you want to learn a bit, the reasoned schemer is the best jumping off point imo. This is maybe the best internet answer, by the author: https://stackoverflow.com/questions/28467011/what-are-the-main-technical-differences-between-prolog-and-minikanren-with-resp/28556223#28556223 https://stackoverflow.com/questions/28467011/what-are-the-ma...
agumonkey 8y ago
similarly, pydatalog https://sites.google.com/site/pydatalog/ https://sites.google.com/site/pydatalog/ found on this 5yo thread https://www.reddit.com/r/Python/comments/18y1mj/logpy_logic_programming_in_python/ https://www.reddit.com/r/Python/comments/18y1mj/logpy_logic_...
na85 8y ago
When viewing HN in Firefox Mobile on Android, this submission's title has a square with "OBJ" in it after the word Kanren. Is that intended? It doesn't look like the "your device lacks this Unicode character" glyph.
- ChrisSD 8y ago
  Does it look like this: https://en.wiktionary.org/wiki/%EF%BF%BC https://en.wiktionary.org/wiki/%EF%BF%BC
  - na85 8y ago
    Yup
    - ChrisSD 8y ago
      Looking at the source, it seems to be part of the title. Chrome (and Chromium based browsers don't appear to display it. It was probably just a bad copy paste. I have seen invisible characters used intentionally as markers or invisible water marks but I doubt that's happening here.
      - na85 8y ago
        Looking at the link, wondering if perhaps the Travis CI logo got pulled into the title? Either way, thanks!
- gus_massa 8y ago
  It's better to send an email to the mods hn@ycombinator.com They usually remove the strange character as soon as they get the email. (They are probably sleeping now.)
- jumelles 8y ago
deleted 8y ago
[deleted]
chrstphrhrt 8y ago
I am currently using PyKnow (https://github.com/buguroo/pyknow/ https://github.com/buguroo/pyknow/) as a rules engine for dialog management (to drive topic stack frame selection). It's just a prototype so far and I have barely scratched the surface of expert systems, GOFAI and logic programming in general. It is based on CLIPS [1] which is a knowledge-oriented expert systems thing developed at NASA. It allows encoding logic as "gates" that solve for constraints with left-hand-side facts triggering right-hand-side consequences. I like to tell the business people it's like "IFTTT for X". Can someone with experience contrast this kind of thing with real logic programming? Is it just the level of formality and provability? Are there many logics like we have in philosophy (symbolic, predicate etc.) that are used in programming? [1] http://clipsrules.sourceforge.net/documentation/v640/ug.pdf http://clipsrules.sourceforge.net/documentation/v640/ug.pdf
- deleted 8y ago
  [deleted]
bayesian_horse 8y ago
Is there any utility in logic programming like this? I'm not trolling, I really don't know. All examples I've seen so far seem to be easier to achieve from "normal" Python or similar...
- bobjordan 8y ago
  I work a lot with nested BOMs (bill of materials) for products, and just looking at the examples here, I can think of several areas where adding this to some python data structures to deal with parents and children, would be more elegant than what we currently have. Might be useful enough to pull in as a dependency.
- tobmlt 8y ago
  I've recently completed my PhD in the automated design/generation of constrained ship hull form geometry. This is a method that originated in the 90s for generating the basic geometry of a ship from "scratch" - well actually from lists of "form parameters" which are really constraints. The method uses nonlinear programming to solve for B-splines (other representations could be used) which minimize some functional and satisfy constraints. Ship hull shapes can get pretty complicated. Now the trick is to specify, ahead of time, constraints which are consistent with each other, so that, in the first place, the nonlinear solvers don't waste time on bad designs, and really, we'd like to be able to search the design space without such waste. The way I found to address this issue was to view the design space as interval valued. (By the way the design space is usually viewed as the space of all possible combinations of real valued constraints). With intervals we could reason about the design space using our constraints, but we need some kind of solver to narrow down the answers. There is an enormous amount of interval and constraint solving literature here, of course. First, being from a numerics background, I tried working only with the intervals themselves. Nonlinear interval solvers for constraint systems. Long story short, the global methods need local help to make progress when the domain contains singular points and other places where the numerics are not so nice, in real or floating point. Local methods are really simple - just invert a single constraint at a time, in the simplest case. The issue here is that you need to solve for each constraint variable in terms of all the others. This is relational constraint programming and is something that Will Byrd has stated that miniKanren is good for. (Will is co-author of miniKanren, and a really nice guy) Now, the second trick is that we want to compose with any random constraint that the ship designer dreams up (within reason, and my personal time constraints ;). So I hacked out an interval valued version of "miniKanren" which lived within Python. (think reverse mode automatic differentiation facilitated by operator overloading to embed the math operations directly into numpy. Take that programming idea, and change it to compose a computational graph of constraints, instead of differentiation.) In short, it worked as well as I'd hoped. The relational logic front end can "quickly enough" narrow the design space as new rules come in, and then even a random number generator can select feasible designs. (Hint hint, time to add more efficient design space learners.) It's a long story, shortly told, but I'd claim there are applications in the engineering space.
wodenokoto 8y ago
Kanren is Japanese and means connection or relation. 関連 The "kan" is not the same kan as in Kanban. 看板 Why the Japanese name?
- teacpde 8y ago
  I don’t see it mentioned in the readme that the name is from Japanese, maybe it isn’t?
  - Twisol 8y ago
    From the readme, this is based on miniKanren, so the name is a reference to that language. miniKanren itself has a Wikipedia page that also mentions the Japanese etymology of the name. Logic languages like Prolog are usually based on relations (or "constraints"), which is likely where the name ultimately came from. As for why Japanese, I don't think there's going to be a particularly good answer to that question.
    - nikofeyn 8y ago
      probably just because it’s fun to use foreign words as the name of things since you can have something sound like a name and not just a word but have a direct meaning or represent a concept. also, weren’t (maybe it should be “aren’t”) the japanese heavy users of prolog?
      - Twisol 8y ago
        > it’s fun to use foreign words as the name of things Oh definitely! I wrote a FAT16 stack for an embedded system and called it "FutoiFS" (ha, ha) [1]. I think whimsy is a perfectly good reason. It sounded like the OP wanted a reason for choosing Japanese specifically, though, and I don't think such exists. [1] Definition of "futoi": https://jisho.org/word/%E5%A4%AA%E3%81%84 https://jisho.org/word/%E5%A4%AA%E3%81%84
  - wodenokoto 8y ago
    No it doesn't. But it ought to have a line about its name. And yes, I am assuming it is Japanese.
evertheylen 8y ago
These kind of Prolog-like systems are actually not very hard to make using Python generators. I think it's a nice exercise to really understand the intricacies of Prolog! My own try is here: https://github.com/evertheylen/logicpy https://github.com/evertheylen/logicpy (not as extensive as kanren though)..

136 points by ausjke 8y ago

MauiWarrior 8y ago

There is already Problog with probability and logic. Could somebody help me understand benefits of Kanren?

zimablue 8y ago
I think you maybe need to know quite a lot about both in order to have a good answer. If you want to learn a bit, the reasoned schemer is the best jumping off point imo. This is maybe the best internet answer, by the author: https://stackoverflow.com/questions/28467011/what-are-the-main-technical-differences-between-prolog-and-minikanren-with-resp/28556223#28556223 https://stackoverflow.com/questions/28467011/what-are-the-ma...

agumonkey 8y ago

similarly, pydatalog https://sites.google.com/site/pydatalog/ https://sites.google.com/site/pydatalog/ found on this 5yo thread https://www.reddit.com/r/Python/comments/18y1mj/logpy_logic_programming_in_python/ https://www.reddit.com/r/Python/comments/18y1mj/logpy_logic_...

na85 8y ago

When viewing HN in Firefox Mobile on Android, this submission's title has a square with "OBJ" in it after the word Kanren. Is that intended? It doesn't look like the "your device lacks this Unicode character" glyph.

ChrisSD 8y ago
Does it look like this: https://en.wiktionary.org/wiki/%EF%BF%BC https://en.wiktionary.org/wiki/%EF%BF%BC
- na85 8y ago
  Yup
  - ChrisSD 8y ago
    Looking at the source, it seems to be part of the title. Chrome (and Chromium based browsers don't appear to display it. It was probably just a bad copy paste. I have seen invisible characters used intentionally as markers or invisible water marks but I doubt that's happening here.
    - na85 8y ago
      Looking at the link, wondering if perhaps the Travis CI logo got pulled into the title? Either way, thanks!
gus_massa 8y ago
It's better to send an email to the mods hn@ycombinator.com They usually remove the strange character as soon as they get the email. (They are probably sleeping now.)
jumelles 8y ago

deleted 8y ago

[deleted]

chrstphrhrt 8y ago

I am currently using PyKnow (https://github.com/buguroo/pyknow/ https://github.com/buguroo/pyknow/) as a rules engine for dialog management (to drive topic stack frame selection). It's just a prototype so far and I have barely scratched the surface of expert systems, GOFAI and logic programming in general. It is based on CLIPS [1] which is a knowledge-oriented expert systems thing developed at NASA. It allows encoding logic as "gates" that solve for constraints with left-hand-side facts triggering right-hand-side consequences. I like to tell the business people it's like "IFTTT for X". Can someone with experience contrast this kind of thing with real logic programming? Is it just the level of formality and provability? Are there many logics like we have in philosophy (symbolic, predicate etc.) that are used in programming? [1] http://clipsrules.sourceforge.net/documentation/v640/ug.pdf http://clipsrules.sourceforge.net/documentation/v640/ug.pdf

deleted 8y ago
[deleted]

bayesian_horse 8y ago

Is there any utility in logic programming like this? I'm not trolling, I really don't know. All examples I've seen so far seem to be easier to achieve from "normal" Python or similar...

bobjordan 8y ago
I work a lot with nested BOMs (bill of materials) for products, and just looking at the examples here, I can think of several areas where adding this to some python data structures to deal with parents and children, would be more elegant than what we currently have. Might be useful enough to pull in as a dependency.
tobmlt 8y ago
I've recently completed my PhD in the automated design/generation of constrained ship hull form geometry. This is a method that originated in the 90s for generating the basic geometry of a ship from "scratch" - well actually from lists of "form parameters" which are really constraints. The method uses nonlinear programming to solve for B-splines (other representations could be used) which minimize some functional and satisfy constraints. Ship hull shapes can get pretty complicated. Now the trick is to specify, ahead of time, constraints which are consistent with each other, so that, in the first place, the nonlinear solvers don't waste time on bad designs, and really, we'd like to be able to search the design space without such waste. The way I found to address this issue was to view the design space as interval valued. (By the way the design space is usually viewed as the space of all possible combinations of real valued constraints). With intervals we could reason about the design space using our constraints, but we need some kind of solver to narrow down the answers. There is an enormous amount of interval and constraint solving literature here, of course. First, being from a numerics background, I tried working only with the intervals themselves. Nonlinear interval solvers for constraint systems. Long story short, the global methods need local help to make progress when the domain contains singular points and other places where the numerics are not so nice, in real or floating point. Local methods are really simple - just invert a single constraint at a time, in the simplest case. The issue here is that you need to solve for each constraint variable in terms of all the others. This is relational constraint programming and is something that Will Byrd has stated that miniKanren is good for. (Will is co-author of miniKanren, and a really nice guy) Now, the second trick is that we want to compose with any random constraint that the ship designer dreams up (within reason, and my personal time constraints ;). So I hacked out an interval valued version of "miniKanren" which lived within Python. (think reverse mode automatic differentiation facilitated by operator overloading to embed the math operations directly into numpy. Take that programming idea, and change it to compose a computational graph of constraints, instead of differentiation.) In short, it worked as well as I'd hoped. The relational logic front end can "quickly enough" narrow the design space as new rules come in, and then even a random number generator can select feasible designs. (Hint hint, time to add more efficient design space learners.) It's a long story, shortly told, but I'd claim there are applications in the engineering space.

wodenokoto 8y ago

Kanren is Japanese and means connection or relation. 関連 The "kan" is not the same kan as in Kanban. 看板 Why the Japanese name?

teacpde 8y ago
I don’t see it mentioned in the readme that the name is from Japanese, maybe it isn’t?
- Twisol 8y ago
  From the readme, this is based on miniKanren, so the name is a reference to that language. miniKanren itself has a Wikipedia page that also mentions the Japanese etymology of the name. Logic languages like Prolog are usually based on relations (or "constraints"), which is likely where the name ultimately came from. As for why Japanese, I don't think there's going to be a particularly good answer to that question.
  - nikofeyn 8y ago
    probably just because it’s fun to use foreign words as the name of things since you can have something sound like a name and not just a word but have a direct meaning or represent a concept. also, weren’t (maybe it should be “aren’t”) the japanese heavy users of prolog?
    - Twisol 8y ago
      > it’s fun to use foreign words as the name of things Oh definitely! I wrote a FAT16 stack for an embedded system and called it "FutoiFS" (ha, ha) [1]. I think whimsy is a perfectly good reason. It sounded like the OP wanted a reason for choosing Japanese specifically, though, and I don't think such exists. [1] Definition of "futoi": https://jisho.org/word/%E5%A4%AA%E3%81%84 https://jisho.org/word/%E5%A4%AA%E3%81%84
- wodenokoto 8y ago
  No it doesn't. But it ought to have a line about its name. And yes, I am assuming it is Japanese.

evertheylen 8y ago

These kind of Prolog-like systems are actually not very hard to make using Python generators. I think it's a nice exercise to really understand the intricacies of Prolog! My own try is here: https://github.com/evertheylen/logicpy https://github.com/evertheylen/logicpy (not as extensive as kanren though)..