Picat 表逻辑编程简介

于 2015 年 10 月 22 日

Picat 是一种新的基于逻辑的编程语言。在许多方面，Picat 与 Prolog 相似，特别是 B-Prolog，但它除了谓词之外还具有函数、谓词头中的模式匹配而不是合一、列表推导和可选的破坏性赋值。了解一些 Prolog 有助于学习 Picat，但绝不是必需的。

根据该语言的作者，Picat 是以下各项的首字母缩写：

模式匹配。
命令式。
约束。
Actor。
制表。

Picat 具有许多有趣的功能，例如约束逻辑编程支持以及与各种求解器的接口。在本文中，我将重点关注 Picat 的一个方面：制表和基于制表的 planner 模块。

首先，让我们安装并学习一些 Picat 的基础知识。安装 Picat 很简单；您可以下载 32 位和 64 位 Linux 系统的预编译二进制文件，以及其他平台的二进制文件。如果您想自己编译它，C 源代码在 Mozilla 公共许可证下可用。这里的示例使用 Picat 1.2 版本，但更新或稍旧的版本也应该可以工作。

安装完成后，您可以从命令行运行 picat 并看到 Picat 的提示符


Picat 1.2, (C) picat-lang.org, 2013-2015.
Picat>

您可以使用此界面以交互方式运行命令（查询）。

让我们从强制性的“Hello, World”开始


Picat> println("Hello, World!").
Hello, World!
yes

这里没有真正的惊喜。结尾的 yes 表示 Picat 成功执行了查询。

对于下一个示例，让我们将 2 赋值给一个变量


Picat> X = 2.
X = 2
yes

请注意变量名称的大写字母；所有变量名称都必须以大写字母或下划线开头（与 Prolog 中相同）。

接下来，将符号赋值给 X 变量（符号用单引号括起来；对于许多符号，引号是可选的，而双引号字符串，例如上面的“Hello, World！”，是符号列表）


Picat> X = a.
X = a
yes
Picat> X = 'a'.
X = a
yes

对于大写字母符号，单引号是强制性的（否则它将被视为变量名）


Picat> X = A.
A = X
yes
Picat> X = 'A'.
X = 'A'
yes

请注意，不同查询（用句点分隔）中的变量 X 是完全独立的变量。

列表

接下来，让我们处理列表


Picat> X = [1, 2, 3, a].
X = [1,2,3,a]
yes

列表在 Picat 中是异构的，因此您可以将数字作为前三个列表元素，并将符号作为最后一个元素。

您可以像这样计算算术表达式的结果


Picat> X = 2 + 2.
X = 4
yes
Picat> X = [1, a, 2 + 2].
X = [1,a,4]
yes

Picat> X = 2, X = X + 1.
no

如果您的背景是主流的命令式语言，这可能会让您感到非常惊讶。但从逻辑的角度来看，这完全有道理：X 不能等于 X + 1。

使用 := 而不是 = 会产生更符合预期的答案


Picat> X = 2, X := X + 1.
X = 3
yes

破坏性赋值运算符 := 允许您覆盖 Picat 通常的变量单次赋值“写入一次”策略。它的工作方式与您对命令式语言的期望相同。

您可以使用 [|] 表示法来获取列表的“头”（第一个元素）和“尾”（其余元素）


Picat> X = [1, 2, 3], [Tail | Head] = X.
X = [1,2,3]
Tail = 1
Head = [2,3]
yes

您可以使用相同的表示法将元素添加到列表的开头


Picat> X = [1, 2, 3], Y = [0 | X].
X = [1,2,3]
Y = [0,1,2,3]
yes
Picat> X = [1, 2, 3], X := [0 | X].
X = [0,1,2,3]
yes

第一个示例创建一个新变量 Y，第二个示例使用赋值运算符重用 X。

TPK 算法

尽管能够以交互方式运行小型查询来尝试不同的事物很方便，但对于较大的程序，您可能希望将代码写入文件并将其作为脚本运行。

为了学习 Picat 的一些语法特性，让我们为 TPK 算法创建一个程序（脚本）。TPK 是 D. Knuth 和 L. Pardo 提出的算法，用于展示“Hello, World！”程序之外的编程语言的基本语法。该算法要求用户输入 11 个实数 (a0...a10)。之后，对于 i = 10...0（按该顺序），该算法计算算术函数 y = f(ai) 的值，并输出一对 (i, y)，如果 y <= 400，否则输出 (i, TOO LARGE)。

清单 1. TPK


f(T) = sqrt(abs(T)) + 5 * T**3.
main =>
    N = 11,
    As = to_array([read_real() : I in 1..N]),
    foreach (I in N..-1..1)
        Y = f(As[I]),
        if Y > 400 then
            printf("%w TOO LARGE\n", I)
        else
            printf("%w %w\n", I, Y)
        end
    end.

首先，代码定义了一个函数来计算 f 的值（Picat 中的函数是一种特殊的谓词，它总是成功并返回一个返回值）。接下来是 main 谓词（main 是脚本执行期间将运行的谓词的默认名称）。代码使用列表推导（类似于 Python 中的列表推导，例如）将 11 个空格分隔的实数读取到数组 As 中。foreach 循环迭代数组中的数字；I 从 11 变为 1，步长为 -1（在 Picat 中，数组索引从 1 开始）。循环体计算每次迭代的 y 值，并使用“if-then-else”结构打印结果。printf 类似于相应的 C 语言函数；%w 可以看作是一个“通配符”控制序列，用于输出不同类型的值。

您可以将此程序保存到扩展名为 .pi 的文件中（我们称之为 tpk.pi），然后使用命令 picat tpk.pi 运行它。输入 11 个空格分隔的数字并按 Enter 键。

制表

现在您已经熟悉了 Picat 语法以及如何运行脚本，让我们直接进行制表。制表是一种自动缓存或记忆化的形式——可以存储先前计算的结果，以避免不必要的重复计算。

您可以通过比较两个版本的程序来了解制表的优点，这两个版本分别使用和不使用制表来计算斐波那契数。

清单 2 显示了 Picat 中朴素的递归斐波那契实现。

清单 2. 朴素斐波那契


fib(0) = 1.
fib(1) = 1.
fib(N) = F =>
  N > 1,
  F = fib(N - 1) + fib(N - 2).

main =>
  N = read_int(),
  println(fib(N)).

这种朴素的实现可以工作，但它的运行时间是指数级的。在我的机器上计算第 37 个斐波那契数需要两秒多


$ time echo 37 | picat fib_naive.pi
39088169
real	0m2.604s

计算第 100 个斐波那契数将永远花费这个程序的时间！

但是，您只需在程序开头添加一行（table）即可看到运行时间的显着改善。

现在您不仅可以立即获得第 37 个斐波那契数，甚至可以获得第 1,337 个斐波那契数（并且答案不会受到溢出的影响，因为 Picat 支持任意长度的整数）。

实际上，通过制表，您可以将渐近运行时间从指数级更改为线性级。

一个更有用的功能是“模式导向”制表。使用它可以指示 Picat 存储非确定性目标的所有可能答案的最小值或最大值。在实现动态规划算法时，此功能非常方便。但是，该主题超出了本文的范围；请参阅 Picat 的官方文档以了解有关模式导向制表的更多信息。

planner 模块

Picat 还具有基于制表的 planner 模块，该模块可用于解决人工智能规划问题。该模块提供了更高级别的抽象性和声明性。

要使用该模块，应用程序员必须指定 action 和 final 谓词。

final 谓词的最简单形式只有一个参数——当前状态——如果状态是最终状态，则成功。

action 谓词通常有多个子句——每个可能的动作或相关动作组一个子句。此谓词有四个参数：当前状态、新状态、动作名称和动作成本。

让我们使用 planner 模块构建一个迷宫求解器。迷宫求解程序将从标准输入读取迷宫地图，并输出到达出口的最佳步骤序列。这是一个示例地图


5 5
@.#..
=.#..
.##..
.#X..
.|...

第一行包含迷宫的尺寸：行数 R 和列数 C。

接下来，R 行描述迷宫的行。以下是地图符号的描述

@ — 初始英雄位置。
. — 空单元格。
# — 永久墙。
= — 钥匙。
| — 闭门。
X — 出口。

英雄可以向上、向下、向左和向右移动（没有对角线）到任何开放的单元格（没有墙壁或闭门的单元格）。英雄可以捡起钥匙并打开门。打开门并移动到新打开的单元格被认为是一个动作。要打开门，英雄必须有钥匙。

因为这是一个魔法迷宫，钥匙在打开门后会消失。所有钥匙都是相同的，因此打开门基本上只是将英雄拥有的钥匙数量减少一个。

目标是以最少的能量到达出口。移动到开放单元格消耗一个能量单位，捡起钥匙消耗一个能量单位，打开门并移动到先前被该门占据的单元格消耗两个能量单位。

让我们将此问题的状态表示为一个元组 (R, C, (ExitI, ExitJ), Walls, Doors, Keys, K, (HeroI, HeroJ))

R 和 C 是迷宫中的行数和列数。
(ExitI, ExitJ) 是出口的坐标。
Walls 是所有墙壁位置的列表。
Doors 是所有闭门位置的列表。
Keys 是尚未捡起的钥匙的位置列表。
K 是英雄拥有的钥匙数量。
(HeroI, HeroJ) 是英雄位置的坐标。

让我们首先做一些枯燥的工作，将迷宫的文本表示形式转换为之前定义的格式的初始状态。

main 谓词是一个命令式过程，用于从迷宫的文本表示形式构造初始状态：您逐行、逐符号地读取输入，然后构造墙壁、门和钥匙的列表，并记录英雄和出口的坐标。

清单 3. 读取迷宫描述


main =>
  R = read_int(), C = read_int(),
  Walls = [], Doors = [], Keys = [],
  (ExitI, ExitJ) = (_, _),
  (HeroI, HeroJ) = (_, _),
  foreach (I in 1..R)
    Line = read_line(),
    foreach (J in 1..C)
      Char = Line[J],
      if Char == '@' then
        HeroI := I, HeroJ := J
      end,
      if Char == 'X' then
        ExitI := I, ExitJ := J
      end,
      if Char == '#' then
        Walls := [(I, J) | Walls]
      end,
      if Char == '|' then
        Doors := [(I, J) | Doors]
      end,
      if Char == '=' then
        Keys := [(I, J) | Keys]
      end
    end
  end,
  InitState = (R, C, (ExitI, ExitJ),
               Walls, Doors, Keys,
               0, (HeroI, HeroJ)),
  println(InitState).

让我们将此程序保存到 maze_read.pi，将上面的迷宫描述保存到 maze.txt，并运行该程序（为了清晰起见，输出分为几行）


$ picat maze_read.pi < maze.txt
5,5,
(4,3),
[(4,2),(3,3),(3,2),(2,3),(1,3)],
[(5,2)],
[(2,1)],
0,1,1

因此，您拥有迷宫的尺寸（5x5）、出口的坐标 (4, 3)、所有五个墙壁的坐标列表、一个闭门的单元素列表和一个可捡起的钥匙的单元素列表。英雄有 0 把钥匙，并从单元格 (1, 1) 开始。

现在您有了状态，您可以定义一些谓词来解决问题。首先，planner 模块的 final 谓词


final((_, _, (I, J), _, _, _, _, (I, J))) =>
  true.

当英雄位于与出口单元格坐标相同的单元格中时，状态为最终状态。名称为 _ 的变量是抛弃型“无关紧要”变量，不需要具有任何特定值（Picat 在幕后为每个 _ 发明一个不同的名称，因此它们也不必相等）。

接下来，描述如果英雄在一个有钥匙的单元格中采取的动作


action(State, NewState, Action, Cost) ?=>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
    select((HeroI, HeroJ), Keys, NewKeys),
    Action = $take_key(HeroI, HeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, NewKeys,
                K + 1, (HeroI, HeroJ)).

首先，您将状态分解为组件，然后尝试从 Keys 列表中 select 一个具有英雄当前坐标的钥匙。如果存在这样的钥匙，这将成功，其余的钥匙将分配给“NewKeys”；否则，select 失败，Picat 将中断此动作子句的执行。

动作的名称是 take_key，括号中包含事件的坐标（$ 指示 Picat 将其视为字面量，如字符串，而不是尝试作为函数执行），成本为一个能量单位。

新状态与旧状态几乎相同，只是英雄拥有的钥匙数量增加了一个，并且当前的钥匙不再可捡起。

除了捡起钥匙外，还有两个可能的动作：移动到空单元格和打开门后移动到有门的单元格。将这两个动作组合到一个子句中是一个好主意，因为它们共享大量用于选择新的英雄位置并检查它是否在迷宫边界内的代码


action(State, NewState, Action, Cost) =>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
  (
    Di = 0, Dj = 1
  ;
    Di = 0, Dj = -1
  ;
    Di = 1, Dj = 0
  ;
    Di = -1, Dj = 0
  ),
  NewHeroI = HeroI + Di,
  NewHeroJ = HeroJ + Dj,
  NewHeroI >= 1, NewHeroI <= R,
  NewHeroJ >= 1, NewHeroJ <= C,
  (
    % move to open cell
    not membchk((NewHeroI, NewHeroJ), Walls),
    not membchk((NewHeroI, NewHeroJ), Doors),
    Action = $move(NewHeroI, NewHeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, Keys,
                K, (NewHeroI, NewHeroJ))
  ;
    % open a door and move to that cell
    K > 0,
    select((NewHeroI, NewHeroJ), Doors, NewDoors),
    Action = $open(NewHeroI, NewHeroJ),
    Cost = 2,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, NewDoors, Keys,
                K - 1, (NewHeroI, NewHeroJ))
  ).

再次，首先您将状态分解为组件。接下来，您尝试英雄的所有可能新位置，并使用非确定性析取：;。

位置必须在迷宫边界内：I 必须从 1 到 R，J 必须从 1 到 C。之后，有两种可能性：移动到开放单元格，或打开门并移动到该单元格。

只有当所需位置没有墙壁或闭门时，才有可能移动到开放单元格。两条 not membchk 行验证了此条件。如果满足条件，则动作名称为 move，成本为一个能量单位。状态的唯一变化是英雄的位置。

如果位置有门且英雄至少有一把钥匙，则可以打开门。这里的 select 行类似于 take 动作的行，但现在您选择的是门而不是钥匙。如果满足条件，则动作名称为 open，成本为两个能量单位。新状态与旧状态几乎相同，但门已从门列表中删除，英雄拥有的钥匙数量减少了一个，并且英雄已移动到新位置。

要使用定义的 final 和 action 谓词并找到计划，您需要将 maze_read.pi 程序中 main 中的 println(InitState) 更改为 best_plan_unbounded(InitState, Plan), println(Plan)。（注意：best_plan_unbounded 是 planner 模块中用于查找最佳计划的谓词之一。此特定版本使用内存来避免重新探索状态，从而将所有可能计划空间中的树搜索转换为图搜索。）

清单 4 显示了完整的迷宫程序。

清单 4. 完整迷宫程序


import planner.

action(State, NewState, Action, Cost) ?=>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
    select((HeroI, HeroJ), Keys, NewKeys),
    Action = $take_key(HeroI, HeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, NewKeys,
                K + 1, (HeroI, HeroJ)).

action(State, NewState, Action, Cost) =>
  (R, C, (ExitI, ExitJ), Walls, Doors, Keys,
    K, (HeroI, HeroJ)) = State,
  (
    Di = 0, Dj = 1
  ;
    Di = 0, Dj = -1
  ;
    Di = 1, Dj = 0
  ;
    Di = -1, Dj = 0
  ),

  NewHeroI = HeroI + Di,
  NewHeroJ = HeroJ + Dj,
  NewHeroI >= 1, NewHeroI <= R,
  NewHeroJ >= 1, NewHeroJ <= C,

  (
    % move to open cell
    not membchk((NewHeroI, NewHeroJ), Walls),
    not membchk((NewHeroI, NewHeroJ), Doors),
    Action = $move(NewHeroI, NewHeroJ),
    Cost = 1,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, Doors, Keys,
                K, (NewHeroI, NewHeroJ))
  ;
    % open a door and move to that cell
    K > 0,
    select((NewHeroI, NewHeroJ), Doors, NewDoors),
    Action = $open(NewHeroI, NewHeroJ),
    Cost = 2,
    NewState = (R, C, (ExitI, ExitJ),
                Walls, NewDoors, Keys,
                K - 1, (NewHeroI, NewHeroJ))
  ).

final((_, _, (I, J), _, _, _, _, (I, J))) =>
  true.

main =>
  R = read_int(), C = read_int(),
  Walls = [], Doors = [], Keys = [],
  (ExitI, ExitJ) = (_, _),
  (HeroI, HeroJ) = (_, _),
  foreach (I in 1..R)
    Line = read_line(),
    foreach (J in 1..C)
      Char = Line[J],
      if Char == '@' then
        HeroI := I, HeroJ := J
      end,
      if Char == 'X' then
        ExitI := I, ExitJ := J
      end,
      if Char == '#' then
        Walls := [(I, J) | Walls]
      end,
      if Char == '|' then
        Doors := [(I, J) | Doors]
      end,
      if Char == '=' then
        Keys := [(I, J) | Keys]
      end
    end
  end,
  InitState = (R, C, (ExitI, ExitJ),
               Walls, Doors, Keys,
               0, (HeroI, HeroJ)),
  best_plan_unbounded(InitState, Plan),
  println(Plan).

在对上面使用的迷宫运行后，您将获得解决迷宫的最佳计划（动作列表）（为了清晰起见，输出分为几行）


$ picat maze.pi < maze.txt
[
 move(2,1),
 take_key(2,1),
 move(3,1),
 move(4,1),
 move(5,1),
 open(5,2),
 move(5,3),move(4,3)
]

您可以尝试使用各种大小和不同功能的输入来运行此程序。例如，此输入要求英雄向右拿一把钥匙，然后向左走以获得更多钥匙，然后再向右走到出口


1 10 ==|=|@=||X

当然，您可以通过许多不同的方式改进迷宫程序

更好的用户界面：目前，输出不是很易于阅读，如果迷宫不可解，程序会因错误而退出。
使用集合或哈希表代替列表：在列表中查找钥匙或墙壁需要线性时间，而使用更合适的数据结构，这将是常数时间。
添加启发式方法：可以使用启发式方法改进搜索，使其成为 IDA* 算法的变体。
新的迷宫功能：您可以实现不同种类的钥匙、武器、宝藏和怪物。

总的来说，Picat 看起来像是进入基于逻辑的编程语言领域的绝佳起点。它提供了 Prolog 具有的许多优点，例如非确定性和带有回溯的内置深度优先搜索，同时，Picat 允许您退回到方便的命令式概念，如破坏性赋值和循环。更高级别的功能，如制表和 planner 模块，提供了编写简洁、声明式和高效程序的方法。

资源

Picat：http://picat-lang.org

Sergii Dymchenko 的“使用 Picat 进行人工智能规划”：http://sdymchenko.com/blog/2015/01/31/ai-planning-picat

Hakan Kjellerstrand 的 Picat 页面：http://www.hakank.org/picat

Sergii Dymchenko 和 Mariia Mykhailova 的“使用 Picat 声明式地解决 Google Code Jam 问题”：http://arxiv.org/abs/1504.00977

Neng-Fa Zhou 的“使用 Picat 进行组合搜索”：http://arxiv.org/abs/1405.2538