Source: http://webyrd.net/scheme-2013/papers/HemannMuKanren2013.pdf

摘要

本论文提出了 µKanren ，关系编程/逻辑编程中的 miniKanren 家族的最小语言。 其实现不到 40 行 Scheme 代码。

关键词：miniKanren 、关系编程（renational programming）、逻辑编程（logical programming）、Scheme

正文

介绍

miniKanren 是关系（逻辑）编程语言中这对同名家族的主要成员。 其中很多关键设计决定是在 Prolog 以及其他知名的第五代编程语言（5GL）影响下的反应。 其中一个不同是，当典型的 Prolog 实现需要几千行 C 语言代码时，一个 miniKanren 解释器仅仅需要不到一千行。 虽然 miniKanren 语言存在很多的变体以及功能集（参见 https:// miniKanren.org ），最早被发布的实现仅仅包含了 265 行 Scheme 代码。 在这短短的百来行代码中，展现了可以和 Prolog 的真子集的实现相比的表现力。

不过，我们认为，在那 265 行的 miniKanren 实现中还藏着一个小而美的关系编程语言亟待发掘。 我们相信 µKanren 就是那个语言。 通过最小化那些紧密关联的算子……

µKanren 语言

在这里，我们简短地介绍 µKanren 程序的语法，尤其是其关注的领域和早期的 miniKanren 语言不同的地方。

设计哲学

µKanren 实现

有限深度优先搜索

无线流

数据交织（Interleaving）

用户层函数

重塑 miniKanren 的控制符

结论及未来的工作

在本论文中，我们介绍了 µKanren ，一个羽量级的纯关系（逻辑）编程语言的实现。 µKanren 是 miniKanren 家族的最小集。 其内核是纯函数的，没有任何宏，仅包括了 14 个定义以及 39 行代码。 因此，我们相信该实现相比其他的 miniKanren 家族，即更易于理解，也更开箱即用。

由于它旨在成为一个最简练的实现方式，因此某些功能不可避免地会被舍弃。……

致谢

我们要向 Will Byrd 以及 Will Ness 因其提供的灵感表示感谢。 我们同时也要感谢 Adam Foltzer 以及 Andre Kulenschimidt ，他们在早期提出了评论以及建议。 我们在这里尤其要感谢 Chung-chieh Shan 、 Jeremy Siek 、 Cameron Swords 以及 Sam Tobin-Hochstadt ，因为他们协助阐明本文的表述方式。

附录

Glossary

A

(define (var c) (vector c))
(define (var? x) (vector? x))
(define (var==? x1 x2) (== (vector-ref x1 0) (vector-ref x2 0)))

;; TBD