可逆树长关系 [英] Reversible tree length relation

问题描述

我正在尝试在纯" Prolog中写可逆关系(没有is，剪切或类似内容.是的，是家庭作业)，我必须承认我不知道该怎么做.我看不到创建此类东西的任何过程.

I'm trying to write reversible relations in "pure" Prolog (no is, cut, or similar stuff. Yes it's homework), and I must admit I don't have a clue how. I don't see any process to create such a thing.

我们被赋予了不纯"但可逆的算术关系(加，乘，等，少，...)，我们必须使用它们来创建这些关系.

We are given "unpure" but reversible arithmetic relations (add,mult,equal,less,...) which we must use to create those relations.

现在，我试图通过创建关系tree(List,Tree)来了解如何创建可逆函数，如果List是二叉树Tree的叶子列表，则为true.

Right now I'm trying to understand how to create reversible functions by creating the relation tree(List,Tree) which is true if List is the list of the leaves of the binary tree Tree.

为实现这种目的，我试图创建tree_size(Tree,N)关系，当Tree具有N叶子时，此关系成立.这是我天真，不可逆的关系:

To achieve such a thing I'm trying to create the tree_size(Tree,N) relation which is true when Tree has N leaves. Here is my naïve, un-reversible relation:

tree_len(n(_,leaf,leaf),1).
tree_len(n(op,G,D),N) :-
    tree_len(G,TG),
    tree_len(D,TD),
    add(TG,TD,N).

我可以执行查询tree_len(some tree, N)，但不能执行tree_len(X,3)，因此它是不可逆的.到目前为止，我已经尝试了一些方法，但是我必须承认我感到沮丧，因为我不知道该在哪里寻找什么.实际上有办法吗?

I can do the query tree_len(some tree, N), but not, say, tree_len(X,3), so it's not reversible. So far I've tried a few things, but I must admit that I feel discouraged as I do not know where and what to look for. Is there actually a way to do this?

推荐答案

不终止的原因

首先，让我们尝试理解为什么您的定义不可逆.我将使用 failure-slice 进行更好的解释.因此，请考虑查询tree_len(X,1).乍一看，一切都很完美，您甚至可以获得不错的答案！

Reason for non-termination

First, let us try to understand why your definition is not reversible. I will use a failure-slice to better explain it. So consider the query tree_len(X,1). At first sight, everything is perfect, you get even a nice answer!

?- tree_len(T,1).
T = n(_G267, leaf, leaf) 

但是不要再问其他答案，因为它会循环:

But never ask for another answer, for it will loop:

?- tree_len(T,1).
T = n(_G267, leaf, leaf) ;
** LOOPS **

所以我们得到的答案有点让人分心.乍一看一切似乎都还可以，只是在回溯时才遇到真正的问题.这是Prolog习惯的.显然，使用3的查询是更好的选择.但这很幸运.

So the answer we got was a bit of a distraction. It at first glance looked like everything was OK, and only on backtracking the real problem was encountered. This is something to get accustomed to in Prolog. Evidently, your query using 3 was better chosen. But that was luck.

通常可以通过一种简单的方法来确保这一点.只需将额外目标false添加到查询中.添加false意味着我们不再对任何答案感兴趣，因为它不再成功.这样就消除了所有干扰，我们直接面对了这个问题:

There is an easy way to ensure this in general. Simply add the extra goal false to the query. Adding false means, that we are no longer interested in any answers, since it can no longer succeed. In this manner all distraction is removed, and we face the problem directly:

?- tree_len(T,1), false.
** LOOPS **

那么，这个循环从何而来?

So, where did this loop come from?

在纯单调的Prolog程序(例如此程序)中，我们可以通过在程序中添加一些目标false来定位未终止的原因.如果生成的程序(称为 failure-slice )没有终止，则原始程序也不会终止.这是我们查询的最小失败切片:

In pure, monotonic Prolog programs (such as this one), we can localize a reason for non-termination by adding some goals false into our program. If the resulting program (called failure-slice) does not terminate, then the original program does not terminate either. This is the minimal failure-slice for our query:

?- tree_len(T,1), false.

tree_len(n(_,leaf,leaf),1) :- false.
tree_len(n(op,G,D),N) :-
    tree_len(G,TG), false,
    tree_len(D,TD),
    N is TG+TD.

我们的程序还剩很多！正是这个微小的片段导致了不终止.如果要解决此问题，则必须在这一小部分中做一些事情.其他一切都是徒劳的.

There is not much left of our program! It is this tiny fragment that is responsible for the non-termination. If we want to fix the problem, we have to do something in that tiny part. Everything else is futile.

所以我们需要做的是以某种方式更改程序，以使该片段不再循环.

So what we need to do is to somehow change the program such that this fragment no longer loops.

实际上，我们有两种选择，我们可以使用后继算法或

Actually, we have two choices, we could use successor arithmetics or constraints like clpfd. The former is available in any Prolog system, the latter is provided only in some like SWI, YAP, SICStus, GNU, B.

现在，3用s(s(s(0)))表示.

tree_lensx(T, s(N)) :-
   tree_lendiff(T, N,0).

tree_lendiff(n(_,leaf,leaf), N,N).
tree_lendiff(n(op,G,D), s(N0),N) :-
   tree_lendiff(G, N0,N1),
   tree_lendiff(D, N1,N).

我在这里使用了几种常见的编码技术.

I used here several common coding techniques.

实际关系是tree_lendiff/3，它不是通过一个参数而是使用两个参数来表示自然数.实际数字是两者之间的差.通过这种方式，可以保留可逆的定义.

The actual relation is tree_lendiff/3 which represents a natural number not by one argument, but rather using two. The actual number is the difference between both. In this manner it is possible to retain the definition reversible.

另一种技术是避免左递归. tree_lendiff/3描述的长度实际上是长度减去 1.还记得我们首先获得的失败切片吗?同样的故障片也会出现在这里！但是，通过将长度移动"一，递归规则的头现在可以确保终止.

The other technique was to avoid left-recursion. The length described by tree_lendiff/3 actually is the length minus one. Remember the failure-slice we got first? The very same failure-slice would be present here too! However by "shifting" the length by one, the head of the recursive rule now ensures termination.

最初，开发了有限域上的约束来解决组合问题.但是您也可以使用它们来获得可逆的算术. SWI和YAP中的实现甚至走得太远，它可以编译成通常与传统不可逆(is)/2效率相同但仍可逆的代码.

Originally, constrains over finite domains were developed to solve combinatorial problems. But you can use them also to get reversible arithmetics. The implementation in SWI and YAP even goes that far that it compiles into code which often equals in efficiency to the traditional non-reversible (is)/2 while still being reversible.

:- use_module(library(clpfd)).

tree_fdlen(n(_,leaf,leaf),1).
tree_fdlen(n(op,G,D),N) :-
   N #= TG+TD,
   TG #>= 1,
   TD #>= 1,
   tree_fdlen(G,TG),
   tree_fdlen(D,TD).

该程序与您的原始定义更加接近.不过，请注意两个目标TG #>= 1和TD #>= 1，它们添加了多余的信息以确保该程序的终止.

This program more closely corresponds to your original definition. Nevertheless, remark the two goals TG #>= 1 and TD #>= 1 which added redundant information to ensure the termination of this program.

我们现在可以枚举一定范围内的所有树，如下所示:

We can now enumerate all trees of a certain range like so:

?- Size in 0..4, tree_fdlen(T, Size).
Size = 1, T = n(_A,leaf,leaf) ;
Size = 2, T = n(op,n(_A,leaf,leaf),n(_B,leaf,leaf)) ;
Size = 3, T = n(op,n(_A,leaf,leaf),n(op,n(_B,leaf,leaf),n(_C,leaf,leaf))) ;
Size = 4, ... ;
Size = 4, ... ;
Size = 3, ... ;
Size = 4, ... ;
Size = 4, ... ;
Size = 4, ... ;
false.

请注意答案替换的确切顺序！这不仅是1,2,3,4！而是以 some 的顺序找到答案.哪一个都不重要，只要我们只对找到所有解决方案感兴趣！

Note the exact order of the answer substitutions! It's not just going 1,2,3,4! Rather, answers are found in some order. It does not matter which one, as long as we are only interested in finding all solutions!

这篇关于可逆树长关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！