# miniKanren

miniKanren is a DSL for relational programming. It can be used to declare the relations between the parameters of a problem, and let the computer find the values of the parameters that satisfy these relations. While the original implementation is in Scheme, I will be focusing in these notes on an implementation in Python.

## Learn

The goal is to fully understand the python implementation. Here's a diagram that roughly summarizes what I need to understand:

## Projects

### Term rewriting

I am using miniKanren in the following contexts/projects:

• In AeMCMC to walk through the possible parametrizations of a probabilistic model to find the most efficient sampler;
• In Aesara to simplify computation graphs.

### Solving puzzles

Puzzles are a good introduction to relational programming: they have a fixed number of rules, were designed to be solved by humans.

• To solve the Zebra riddle (blog post).
• To solve Sudoku puzzles (blog post)
• The solver returns correct solution
• Hangs for simple grids. condp should help with this.
• To solve the NYT's Spelling Bee (draft)
• A Wordle solver (TODO)
• Miracle Sudoku (TODO)
• Knight's tour, a chess puzzle where we need to find a way for a knight to step on every square of a chessboard, only once (TODO).
• The N-Queen problem, which is to position N queens on a NxN chessboard such that no queen beats the others. (TODO)

### Gardening

Gardening is typically an area where we are trying to find solutions that satisfy some constraints. We could definitely use miniKanren to plan garden if the search scaled : we can enter informations about the different plants in a database, then some information about the garden we are trying to design, and look at the combinations that come out of it.

## References

• The Reasoned Schemer (2nd ed.)
• Proceedings of the 2019 Workshop on miniKanren and relational programming including towards a miniKanren with fair search strategies
• "Neural Guided Constraint Logic Programming for Program Synthesis" (paper)
• "A surprisingly competitive conditional operator" (paper)
• "$$\mu\text{Kanren}$$: a functional core for relational programming\$" (paper repo)
• Faster miniKanren (repo)
• Temporal logic programming with miniKanren (repo)
• cKanren: miniKanre with constraints (paper)
• "A unified approach to solving 7 programming problems" (paper)
• AskHN: Why logic programming is not widely used in the industry? (post on HN)
• Clojure's core.logic is a miniKanren implementation in Clojure.
• "A relational language - Parasat" (post) The authors starts from the logic programming language Picat and ends up suggesting something that's close to miniKanren. We also learn that William Byrd recommended the autho tries faster-miniKanren.