README

PHP 实现 Jason Hemann 和 Daniel P. Friedman 的 µKanren，详情请见 论文。

安装

将以下内容添加到您的 composer.json

{
    "require": {
        "mudge/php-microkanren": "v0.1.0"
    }
}

使用方法

require_once 'vendor/autoload.php';

use MicroKanren\Core as U;

$f = U\callFresh(function ($q) {
  return U\eq($q, 5);
});

echo $f(U\emptyState());
/* => (((#(0) . 5)) . 1) */

在 MicroKanren\Core 命名空间内，有 µKanren 核心函数的实现，以及用于执行所需的常见 Lisp 基础功能。由于参考实现是在 Chez Scheme 中，此实现尽可能模仿该特定的 Lisp。

Lisp 基础功能

cons($car, $cdr)

$c = cons(1, cons(2, cons(3, nil())));

返回一个新的 cons单元，其中包含 $car 和 $cdr（这是创建列表的最基本原语）。

car($alist)

$c = cons(1, cons(2, nil()));
car($c);
/* => 1 */

返回 $alist 的第一个元素。

cdr($alist)

$c = cons(1, cons(2, nil()));
cdr($c);
/* => cons(2, nil()) */

返回 $alist 的其余部分。

nil()

$n = nil();
$n === nil();
/* => true */

返回空列表。注意，所有 nil 实例都是相同的。

isPair($obj)

isPair(cons(1, nil())); /* => true  */
isPair(4);              /* => false */
isPair(nil());          /* => false */

如果 $obj 是一个有效的对（即非空列表的 cons 单元，等同于 Petite Scheme 的 pair?），则返回 true。

isNull($obj)

isNull(nil());          /* => true  */
isNull(cons(1, nil())); /* => false */

如果 $obj 是空列表（等同于 Petite Scheme 的 null?），则返回 true。

assp($proc, $alist)

$list = alist(cons(1, 'a'), cons(2, 'b'));
$isEven = function ($x) { return $x % 2 === 0; };

assp($isEven, $list);
/* => cons(2, 'b') */

"返回 $alist 中第一个 car 值为 $proc 返回 true 的元素，或 false。" — Petite Scheme 的 assp

alist(...)

alist(1, 2, 3);
/* => cons(1, cons(2, cons(3, nil()))) */

一个用于构建 cons 单元的便利函数，等同于 Petite Scheme 的 list。

length($alist)

length(alist(1, 2, 3));
/* => 3 */

返回 $alist 的长度。

map($proc, $alist)

$list = alist(1, 2, 3);
map(function ($x) { return $x + 1; }, $list);
/* => alist(2, 3, 4) */

返回一个列表，其中每个值都应用了 $proc。

µKanren 函数

variable($c)

返回一个新的包含索引 $c 的变量（等同于 var）。

isVariable($x)

如果 $x 是一个变量（等同于 var?），则返回 true。

isVariableEquals($x1, $x2)

如果 $x1 和 $x2 指向相同的变量（等同于 var=?），则返回 true。

mzero()

返回空流（等同于 mzero）。

walk($u, $s)

在替换中搜索变量的值。如果对非变量项进行遍历，则返回该项。

extS($x, $v, $s)

扩展替换为新绑定（等同于 ext-s）。

unit($sC)

将状态提升到只有一个元素的流中。

unify($u, $v, $s)

在替换中对两个项进行统一。

eq($u, $v)

返回一个目标，如果两个项在接收状态中统一，则成功（等同于论文中的 ≡ 和参考实现中的 ==）。

callFresh($f)

返回一个给定一元函数的目标，其主体是一个目标（等同于 call/fresh）。

mplus($d1, $d2)

合并流。

bind($d, $g)

在流中的每个元素上调用目标。

disj($g1, $g2)

返回一个目标，如果给定目标中的任何一个成功，则成功。

conj($g1, $g2)

返回一个目标，如果给定目标中的两个都成功，则成功。

emptyState()

返回一个具有空替换和变量索引设置为 0 的状态（等同于 empty-state）。

pull($d)

推进流直到成熟。

takeAll($d)

返回流中的所有结果（等同于 take-all）。

take($n, $d)

从流中返回 $n 个结果。

reifyName($n)

返回给定数字的字符串名称（相当于 reify-name）。

reifyS($v, $s)

相对于变量对状态进行代换（相当于 reify-s）。

walkStar($v, $s)

等同于 walk*。

reifyFirst($sC)

等同于 reify-1st。

有关使用示例的更多信息，请参阅 测试套件。

参考文献

• Justin S. Leitgeb 的 Ruby 版本 microKanren;
• Scott Vokes 的 microKanren Lua 端口;
• Jason Hemann 和 Daniel P. Friedman 的参考 Scheme 实现.

许可证

版权所有 © 2014 Paul Mucur。

在 MIT 许可证下分发。