Page 60 - 《软件学报》2025年第8期

王榕 等: 基于记忆策略的元解释学习 3483

1. 初始化: DB ← ∅,H ← ∅
2. for Atom ∈ E do
3. for n ∈ [1,N] do
4. for m ∈ [0, M] do
5. get Sig
6. Depth = n−length(H)
7. while Atom = [P|Args] ∈ SLD-tree do
8. if Atom 是一个常量化目标
9. Goal f = [Depth,Sig,P|Args]
10. else
′
11. extract(Atom,[P|Args )
Goal f = [Depth,Sig,P,Args |H]
′
12.
13. end if
( )
14. 检查 faulty Goal f 是否已经在失败数据库 DB 中
( )
15. if faulty Goal f ∈ DB
16. 失败并回溯
17. else
{ ( )}
18. DB ← DB∪ faulty Goal f
19. 证明 Atom
20. if true
21. H ← H ∪clause(Atom : −Body)
22. 证明子句体中的下一个目标
23. else
24. 失败并回溯
25. end if
26. end if
27. end while
28. end for
29. end for
30. end for
31. return H
定义 7 (常量化目标和非常量化目标). 设 P 为一个确定性程序, G 0 为初始目标, T 为 P∪{G 0 } 的 SLD-树. T 上
的每一个原子目标都需要被证明. 当原子目标不包含任何变量时, 称其为常量化目标. 当其包含匿名变量时, 称其
为非常量化目标.
为了更好地理解常量化目标和非常量化目标之间的区别, 考虑图 3 和图 4 中描述的两个例子. 在图 3 中, 蓝色
f1([1,1,−1,0,−1],[−1,−1,0,1,1]), 作为一个常量化目标的例子. 这是因为它完全由具体值
子树的根节点被表示为
组成, 没有任何变量, 表明目标中的所有参数都是确定的. 相反, 在图 4 中, 红色子树的根节点被表示为 f2([1,1,0,
−1,−1],Var), 代表了一个非常量化目标. 这里, 变量 Var 的存在意味着目标中的并非所有参数都是指定的, 这使得
它包含了未知元素.
对于给定的目标, SLD-树的路径将按深度优先顺序进行探索, 直到返回一个成功的分支. 受此启发, 在迭代过
程中提取失败分支的失败信息以避免冗余证明是合理的. 相应地, 我们在 MIL 中设计了一种记忆策略, 从 SLD-树