Kanren – Logic Programming in Python

Does it look like this: https://en.wiktionary.org/wiki/%EF%BF%BC

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.)



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.

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.

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-ma...

I don’t see it mentioned in the readme that the name is from Japanese, maybe it isn’t?