Prolog 中的选择点和重做 [英] Choice points and Redo's in Prolog
问题描述
提出问题后
有人能指出我在这种情况下会发生什么的正确方向吗?
谢谢.
索引.
来自 SWI-Prolog 术语表
<块引用>索引是一种用于快速选择候选子句的技术特定目标的谓词.在大多数 Prolog 系统中，索引是done (仅)在 head 的第一个参数上.如果这个论点是实例化为原子、整数、浮点数或带有函子的复合项，散列用于快速选择第一个参数的所有子句可以与目标的第一个参数一致.SWI-Prolog 支持即时和多参数索引.见第 2.18 节.
这是概念和实现出现分歧的情况之一.
这样想，如果您要为 Prolog 编写逻辑引擎，然后用户希望它运行得更快，您将添加使其更快的增强功能，但这样做时，它的工作方式将不是与概念模型相同.
既然引擎具有增强功能，您应该真的有一个开关，可以在调试时关闭这些增强功能，以便您了解实际发生的情况.
来自Prolog 深度编程 作者
迈克尔·A·科文顿
唐纳德·努特
安德烈·韦利诺
秒.4.14.索引页.111
<块引用>当 Prolog 系统执行查询时，它不必在整个知识库中搜索匹配的子句.所有 Prolog 都使用 INDEXING(散列函数或查找表)直接转到正确的谓词.例如，对于 FAMILY.PL，对 mom/2 的查询不会搜索father/2 的子句.
大多数现代 Prolog 使用索引来实现更远的目标.它们不仅索引谓词和元数，还索引第一个参数的主函子.例如，如果您有知识库
a(b).一(三).d(e).d(f).<块引用>
那么查询‘?- d(f).’不仅不会搜索a/1的子句，也不会查看d(e).它直接进入 d(f)，这是唯一一个谓词、元数和第一个参数与查询中的匹配的子句.
评论中的问题
<块引用>是否有某种针对初学者的普通"或标准"Prolog 环境，这些环境的增强功能有限，以便更清楚地了解所有小细节如何工作和交互?
元解释器
<块引用>用于与其自身实现语言相似或相同的语言的解释器称为元解释器 (MI).
了解 Prolog MI 是了解 Prolog 工作原理以及了解非常有用的 MI 的绝佳方式，例如
用另一种语言实现
查看统一如何工作的另一种方法是使用统一算法和以另一种语言实现的回溯，然后使用它来增强代码输出您想要查看的信息.有一个miniProlog 用OCaml写的，但我不怀疑很多人知道OCaml.
很多关于人工智能的更广泛的书籍都实现了它.
人工智能编程范式"，作者 Perter Norvig (Lisp)
解决复杂问题的人工智能结构和策略" 作者 George F Luger(伪代码)
Prolog 实现可以在 GitHub 上找到.smallProlog 非常基础，使用 C 语言完成.
对于统一理论，有经典之作
《自动推理手册》第 8 章
统一理论 作者:Franz Baader 和 Wayne Snyder
派生树
请参阅:Prolog 派生树、选择和统一
After asking a question here about when exactly a Redo is called in Prolog with new variables, or when it is attempted with the same, I thought I figured it out. In the following piece of code, however, I thought that an additional Redo were to be called, but that does not seem to be the case.
My knowledge base is the following:
location(desk,office).
location(apple,kitchen).
location(flashlight,desk).
location('washing machine',cellar).
location(nani,'washing machine').
location(broccoli,kitchen).
location(crackers,kitchen).
location(computer,office).
edible(apple).
edible(crackers).
My query was
?-location(X,kitchen),edible(X).
with the following trace:
Call: (9) location(_5612, kitchen) ? creep
Exit: (9) location(apple, kitchen) ? creep
Call: (9) edible(apple) ? creep
Exit: (9) edible(apple) ? creep
X = apple ;
Redo: (9) location(_5612, kitchen) ? creep <====
Exit: (9) location(broccoli, kitchen) ? creep
Call: (9) edible(broccoli) ? creep
Fail: (9) edible(broccoli) ? creep
Redo: (9) location(_5612, kitchen) ? creep
Exit: (9) location(crackers, kitchen) ? creep
Call: (9) edible(crackers) ? creep
Exit: (9) edible(crackers) ? creep
X = crackers.
Why is there not an additional Redo after the first solution along the lines of Redo: (9) edible(apple) (which would then fail, before going on to the next Redo) since there is still another fact in the code with the functor edible, which would mean that there was a choice point that created? I found an annotated trace of the same query here. I will post a short snippet from it, because it has the additional Redo that I feel is missing here:
Can someone point me in the right direction as to what is to be expected in this case?
Thanks.
It has to do with Indexing.
From SWI-Prolog Glossary of Terms
Indexing is a technique used to quickly select candidate clauses of a predicate for a specific goal. In most Prolog systems, indexing is done (only) on the first argument of the head. If this argument is instantiated to an atom, integer, float or compound term with functor, hashing is used to quickly select all clauses where the first argument may unify with the first argument of the goal. SWI-Prolog supports just-in-time and multi-argument indexing. See section 2.18.
This is one of those cases where the concept and implementation diverge.
Think of it like this, if you were to write the logic engine for Prolog and then the users wanted it to work faster you would add enhancements that made it faster, but in so doing, the way it works would not be the same as the conceptual model.
Now that the engine has enhancements you should really have a switch that turns off those enhancements when debugging so that you see what is really happening.
From Prolog Programming in Depth by
Michael A. Covington
Donald Nute
Andr´e Vellino
Sec. 4.14. Indexing pg. 111
When a Prolog system executes a query, it doesn’t have to search the entire knowledge base for a matching clause. All Prologs use INDEXING (a hashing function or lookup table) to go directly to the right predicate. For example, with FAMILY.PL, a query to mother/2 does not search the clauses for father/2.
Most modern Prologs use indexing to go further than that. They index, not only on the predicate and arity, but also on the principal functor of the first argument. For example, if you have the knowledge base
a(b).
a(c).
d(e).
d(f).
then the query ‘?- d(f).’ not only won’t search the clauses for a/1, it also won’t look at d(e). It goes straight to d(f), which is the only clause whose predicate, arity, and first argument match those in the query.
Question in comment
Is there some kind of 'vanilla' or 'standard' Prolog environment for beginners where those kinds of enhancements are limited, in order to see more clearly how all the small details work and interact?
Meta-interpreters
From: A Couple of Meta-interpreters in Prolog
An interpreter for a language similar or identical to its own implementation language is called meta-interpreter (MI).
Learning about Prolog MIs are an excellent way to understand how Prolog works and also learn about MIs which are extremely useful, e.g.
Use of Prolog for developing a new programming language
Implementation in another language
Another way to see how unification works is to use the unification algorithm with backtracking implemented in another language and then use that to enhance the code outputting information you want to see. There is a miniProlog written in OCaml, but I don't suspect that many people know OCaml.
A lot of the more extensive books on Artificial Intelligence implement it.
"Paradigms of Artificial Intelligence Programming" by Perter Norvig (Lisp)
"Artificial Intelligence Structures and Strategies for Complex Problem Solving" by George F Luger (Pseudo Code)
Prolog implementations can be found on GitHub. smallProlog is very basic and done in C.
And for the theory of unification there is the classic in
"Handbook of automated reasoning" Chapter 8
Unification theory by Franz Baader and Wayne Snyder
Derivation trees
See: Prolog derivation trees, choices, and unification
这篇关于Prolog 中的选择点和重做的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
