Witch of Git - web/blog/blob - drafts/2020/logic-programming.md

   1 ---
   2 title: "Logic Programming Is Also Pretty Easy?"
   3 date: 2020-02-26
   4 draft: true
   5 tags:
   6 - unification
   7 - logic programming
   8 summary: "I've been hearing about MiniKanren and MicroKanren for a while, and I finally just decided to go and read the paper to see if I could understand it. Here's my understanding of it."
   9 prev: posts/2020/syntatic-unification
  10 ---
  11
  12 Last time we implemented unification, with a few paths forward in mind.
  13 One of those was logic programming.
  14
  15 In a logic program, you write equations that describe what things are true, and then the logic program engine searches for a solution to those equations.
  16 For certain types of problems, this can be a great way to implement things.
  17 For instance, the Rust compiler is currently trying to [reimplement some of their type system this way][chalk] in order to make it simpler and support more features.
  18 There are some full-featured logic programming languages like [Prolog][] that have a long history.
  19 When someone talks about logic programming, they mention Prolog most of the time.
  20 There are other smaller languages like [Datalog][] which is designed for queries and analysis, but it's still a large language, much more than we can implement.
  21 We want something smaller.
  22
  23 [chalk]: https://smallcultfollowing.com/babysteps/blog/2017/01/26/lowering-rust-traits-to-logic/
  24 [prolog]: https://en.wikipedia.org/wiki/Prolog
  25 [datalog]: https://en.wikipedia.org/wiki/Datalog
  26
  27 Luckily, we've got some options.
  28 The [Kanrens][] are a family of small logic languages that are embedded in a host language, letting you write normal code and getting all the features of the host language included for free.
  29 They were originally made for Scheme and ["The Reasoned Schemer"][reasoned-schemer], with the miniKanren language.
  30 Later, microKanren was created with the goal "how simple can we make this?"
  31 [The microKanren paper][] is very readable.
  32 But if you don't want to go read a paper, I'm gonna explain it here.
  33
  34 [kanrens]: http://minikanren.org/
  35 [reasoned schemer]: https://mitpress.mit.edu/books/reasoned-schemer-second-edition
  36 [the microkanren paper]: http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf
  37
  38 ### What's In A Logic Program?
  39
  40 Facts
  41 Rules
  42 ->
  43 Goals
  44 Solving
  45
  46 ### #goals
  47
  48 How we'll represent goals in Python
  49
  50 #### The `orr` Goal
  51
  52 #### The `andd` Goal
  53
  54 #### The `fresh` Goal
  55
  56 ### Writing Intersting Logic Programs
  57
  58 ### User Interface