microKanren Reading

microKanren Reading

4 Jul 2022
programming-languages, racket

μKanren (“micro-Kanren”) is a tiny, embeddable logic programming language. It’s easy to understand and implement in almost any language. It’s a great case study of an embedded language: unlike other common “embedded” languages like SQL or regex, which normally are represented as just plain-old strings, μKanren takes more advantage of the host language’s features.

I recommend reading the original paper: it’s short, well-written, and easy to understand.

I did a write-up which you can read on Sourcehut. The README is my set of notes that I made while walking through the implementation of the paper, and the repository contains an implementation in Racket. I’ve included some fun use cases like a type checker/inference engine that takes up only 37 lines of code!

It’s a fun little language, and I might be able to use it at work soon actually. It’s definitely specialized for solving a particular class of problem, but you might be surprised how many things fall into that category. Have you used μKanren? Drop me a line—I’d love to hear about it!