Fanstasy Player / 幻想系玩家
Fanstasy Player / 幻想系玩家

Swi Prolog的源码的略微解读

Aincvy
  约 2000 字 预计阅读 4 分钟 

swi prolog 是prolog 语言的一个解释器的实现， 源码可在 https://github.com/SWI-Prolog/swipl-devel 上找到。

一些吐槽和说明：

  • 因为刚开始实现的时候的年代比较久远，所以源码的对齐格式 笔者非常不习惯。
  • 使用了大量的宏， 代码阅读比较费劲。
  • 宏的使用也不是特别统一， 比如两个宏 #define FALSE (0), #define fail return FALSE 会在同一个函数里面混用，就是有几个是 return FALSE;， 有一两个是 fail;
  • swi prolog的作者实现了一个虚拟机机制，即存在 字节码和GC的功能。
  • 笔者想寻找一下查询相关的原理， 但是并没有完全找到是如何进行实现的。

主要内容

部分文件的简单介绍

  • pl-incl.h 类型定义文件， 几乎定义所有的关键类型
  • pl-comp.c 字节码编译
  • pl-proc.c 谓语相关
  • pl-vmi.c 虚拟机指令实现
  • pl-setup.c 初始化swi prolog 运行需要的各个模块， 以及前置。
  • pl-main.c main函数

部分函数的简单介绍

  • PL_open_query, PL_close_query 开启和关闭一个查询
  • PL_next_solution 寻求下一个解决方案， 本函数是虚拟机循环的入口
  • PL_initialise, setupProlog 初始化函数
  • prologToplevel("$toplevel") 表示打开一个交互式的 窗口
  • compileClause() 编译从句/子句
  • nextClause() 下一条从句/子句
  • assertProcedure() 添加一个 Procedure

一些 prolog 内部的概念的简单介绍

  • Procedure/predicate 谓语 
    • 1
2

        mortal(X) :- 
      person(X).
    • mortal 和 person 都是谓语
    • X是参数， 参数可以是 整数，原子，变量， 结构中的一个
  • atom 原子 是由小写字母开头的字符串
  • variable 变量是由大写字母或者 下划线开始的字符串
  • functor 数据结构， 参考： object(candle, red, small, 1).
  • Unification 联合， 使用 = 号建立联合
    • X=Y, Y=3 这样的语句结束之后， X的值也是3， 像引用一样。
  • 列表： [apple, broccoli, crackers]

虚拟机指令的一些简单介绍

  • VMI(Name, Flags, #Args, (ArgType, …))
  • VMH(Name, #Args, (ArgType, …), (ArgName, …))
  • 虚拟机指令基本上都是使用上面两个宏进行定义出来的。
  • D_BREAK 断点
  • H_ATOM 用于子句头部的原子 (is used for an atom in the head of the clause)
  • H_SMALLINT 用于子句头部的小整数 (is used for small integer in the head of the clause)
  • h_const 作用是绑定常量 (binds a constant)
  • H_NIL 用于子句头部的 [] (is used for [] in the head)
  • H_STRING 绑定字符串常量 (binds a string constant)
  • H_VOID 子句头部的单一变量，只增加参数指针 (A singleton variable in the head. Just increment the argument pointer)
  • H_VAR 子句头部的变量，既不是匿名的，也不是第一次使用的 (A variable in the head which is not an anonymous one and is not used for the first time)
  • H_FIRSTVAR 子句头部的变量，既不是匿名的，但第一次遇到 (A variable in the head, which is not anonymous, but encountered for the first time)
  • H_FUNCTOR 子句头部的函数符 (A functor in the head)
  • H_LIST 类似 H_FUNCTOR，但使用 ./2 作为预定义函数符 (As H_FUNCTOR, but using ./2 as predefined functor)
  • H_POP 弹出由 H_FUNCTOR 和 H_LIST 推送的保存的参数指针 (Pop the saved argument pointer pushed by H_FUNCTOR and H_LIST)
  • B_VAR, B_VAR<N> 子句体中的变量，既不是匿名的，也不是第一次使用的 (A variable in the body which is not an anonymous one and is not used for the first time)
  • matched against 配对
  • a choice point 选择点
  • The clause must start with I_CHP 子句必须以 I_CHP 开头
  • I_ENTER 进入子句体 (Enter the body of the clause)
  • I_CALL 由编译器生成的调用谓词的正常代码 (forms the normal code generated by the compiler for calling predicates)
  • depart_or_retry_continue
  • I_DEPART 表示这是子句的最后一个子句，这是最后调用优化的入口点 (implies it is the last subclause of the clause. This is the entry point for last call optimisation)
  • I_EXIT 一次查询就是一个帧？当然这里也分成了好几种帧，并不是只有一种帧
  • I_EXITFACT 用于关闭一个事实的生成 (generated to close a fact)
  • I_EXITQUERY
  • I_YIELD 从这个引擎中让出控制权，会中断 PL_next_solution()，但再次调用 PL_next_solution() 会恢复虚拟机 (Yield control from this engine. It will interrupt PL_next_solution() but calling PL_next_solution() again will resume the virtual machine)
  • C_OR 在子句中创建选择点 (Create choice-point in the clause)
  • S_VIRGIN 新鲜的、未使用的谓词，任何新谓词都是使用这个监督器创建的 (Fresh, unused predicate. Any new predicate is created using this supervisor)
    • setGenerationFrame 函数应该是设置了一个关于世代的帧，就是本次查询相关的 这是一个函数
  • S_UNDEF 未定义的谓词 (Undefined predicate)
  • S_STATIC 这里好像是查询子句的地方
  • I_USERCALL0 如果遇到一个变量作为子句，编译器生成 (is generated by the compiler if a variable is encountered as a subclause)
  • i_usercall_common 确定与目标相关的函数符定义以及目标的参数向量的指针 (Determine the functor definition associated with the goal as well as the arity and a pointer to the argument vector of the goal)

编译指令参考

1
2
3
4
5
6
7
8

# 在linux机器上进行编译
# 安装 zlib
sudo apt install zlib1g-dev

# 下载代码并安装
git clone https://github.com/SWI-Prolog/swipl-devel.git
cd build
cmake -DSWIPL_PACKAGES_X=OFF -DSWIPL_PACKAGES_QT=OFF -DSWIPL_PACKAGES_JAVA=OFF -DSWIPL_PACKAGES_PYTHON=OFF  -DINSTALL_DOCUMENTATION=OFF -DCMAKE_EXPORT_COMPILE_COMMANDS=ON ..

编译成功之后会在 build/src 目录里面 swipl 程序， 运行 chmod +x ./swipl 就可以添加运行权限了。

程序使用简述

  • 先编写一个包含了事实的 pl 文件， 比如 test.pl。 随便可以使用 ./swipl test.pl 来打开一个交互式窗口。 在窗口里面只能输入查询语句。

查询原理的推测

在 SWI-Prolog 中，unify 是指将两个术语（terms）进行统一（unification）的过程。统一是 Prolog 的核心操作之一，它用于匹配和绑定变量，使得两个术语变得相同。统一操作在 Prolog 的推理引擎中扮演着重要角色。

来源： chat gpt

根据chatgpt所述， swi prolog 的核心是 unify , 即统一， 统一就是两个“东西” 是一模一样， 完全匹配的存在。

一个从句里面是可以存在变量的， pl.comp.c 的 clause 函数应该是在 子句和目标的 统一检测的工作。

  • room(office) 和 room(office) 可以统一， 因为谓词 room 一样， 参数个数一样， 参数值一样都是值为 office 的原子
  • room(X) 和 room(office) 可以统一， 因为谓词 room 一样， 参数个数一样， 参数值X是一个变量， 会自动绑定为 office， 随后就变成了上面一条的结论
  • room(X,Y) 和 room(office) 是不可以统一的， 因为参数数目不一样
  • 只有上面的功能可能还没啥， 但是变量的绑定值可以传给下一个查询就变得有意思了
  • 现在有事实：room(office). location(computer,office).
    • room(X), location(Y,X) 语句经过运算之后， Y的值将为computer
      • 第一代： 因为存在事实room(office) 所以 X=office, 语句会变成： room(office). location(Y,office)
      • 第二代： 因为存在事实location(computer,office) 所以 Y=computer
  • 可以编写复杂的规则， 使用更多的变量完成自己的需求。
  • 但是因为执行上是简单的遍历操作， 所以性能不高， 获的结果将会是一个缓慢的过程。
更新于 2024-07-21 
Released under CC BY-NC 4.0
cpp
返回 | 主页
0%