Swi Prolog的源码的略微解读
目录
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 interruptPL_next_solution()
but callingPL_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)
编译指令参考
|
|
编译成功之后会在 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
- 第一代: 因为存在事实
- 可以编写复杂的规则, 使用更多的变量完成自己的需求。
- 但是因为执行上是简单的遍历操作, 所以性能不高, 获的结果将会是一个缓慢的过程。