使谓词可逆 [英] Make a predicate reversible

问题描述

我是 prolog 的新手；我来自结构化编程背景，这将变得显而易见:)

我正在构建一个涉及反转数字的序言查询；例如.reverse_num(123,X) 结果为 X = 321.我想出了以下定义，但它仅在我提供数字作为第一个参数时才有效.

reverse_num(Num, Revnum) :-number_chars(Num, Atoms),反向(Revatoms，原子)，number_chars(反转，Revatoms)，反转 = Revnum.

number_chars/2 谓词不喜欢未经证实的变量，如果我这样做:reverse_num(X,123)(我期待 X 为 321).

我是否太努力让 reverse_num 做一些它不应该做的事情(是否应该理解为仅使用数字作为第一个参数和变量作为第二个参数)?

或者是否有一种简单/直接的方法来处理变量作为第一个参数?

解决方案

关系命名

在开始编码之前，让我们先退一步.毕竟，Prolog 中的想法是定义关系.你的名字 reverse_num/2 而不是暗示了一些动作，num_reversed/2 可能是一个更好的名字.

确定关系

你的定义还不错，让我改写为¹:

num_reversed(Num, Reversed) :-number_chars(Num, Chars),反向(字符，Revchars)，number_chars(反转，Revchars).?- num_reversed(123,X).X = 321.?- num_reversed(1230,X).X = 321.?- num_reversed(12300,X).X = 321.

你看到图案了吗?所有数字 N*10^I 都有相同的结果！

现在，让我们再问一些:

?- num_reversed(Num, 321).错误:number_chars/2:参数未充分实例化

嗯，我们期待什么?实际上，我们希望打印所有 123*10^I .那是无限多的解决方案.所以上面的查询，如果正确回答，将需要打印无限多个解决方案.如果我们直接打印它们，那将花费我们整个宇宙的生命，甚至更多！

正是因为这个原因，Prolog 反而产生了一个实例化错误.据此，Prolog 基本上声明:

<块引用>

这个目标太笼统了，我没法好好回答.也许有无数个解决方案，也许没有.我不知道.但至少我通过发出错误来表明这一点.要消除此错误，您需要更多地实例化参数.

所以 Prolog 给出的答案根本没有那么糟糕！事实上，产生一个干净的错误比错误地失败要好得多.一般来说，Prolog 的错误通常是对您可能遇到的语义问题的非常有用的提示.请参阅所有错误类方法.

协调

正如其他答案所建议的那样，协调使用 when/2 可能会解决这个问题.但是，协程本身存在很多语义问题.并非没有原因，像 XSB 这样的系统不提供它，因为与包含检查相关的许多问题.与其兼容的实现将出乎意料地低效.

但是为了重点，我们可以通过像这样查询来使我们的定义更加通用

 ?- when(nonvar(Num), num_reversed(Num, Reversed)).when(nonvar(Num), num_reversed(Num, Reversed)).

现在我们返回的正是我们输入的查询的答案.这也称为挣扎.因此， 有一种方法可以以紧凑的方式表示无限可能的解决方案！但是，这需要付出相当高的代价:您不再知道解决方案是否存在.想想:

?- when(nonvar(Num), num_reversed(Num, -1)).当(非变量(Num)，num_reversed(Num，-1)).

其他人建议也等待 nonvar(Reversed)，这只有在我们产生无限多个答案时才是正确的 - 但是，正如我们所见 - 这需要太多时间.>

在 80 年代初期，协同工作看起来是一条非常有前途的道路.然而，它从来没有真正流行过作为一种通用的编程方法.大多数情况下，您会遇到太多的挣扎，这只是一种痛苦，甚至比实例化错误更难处理.

然而，这种发展的一个更有前途的后代是制约因素.在那里，机制的定义更加清晰.出于实际目的，程序员将只使用现有的库，如 CLPFD、CLPQ 或 CHR.实现自己的库本身就是一个非常重要的项目.事实上，甚至可以使用 library(clpfd) 来提供 num_reversed/2 的实现，即限制与整数大小写的关系.

模式依赖条件

传统上，许多此类问题都是通过显式测试实例化来解决的.使用 nonvar/1 和 ground/1 专门执行此操作是一种很好的方式，就像 when/2 - 其他类型的测试谓词很容易导致错误，例如 另一个答案.

num_reversed(Num, Reversed) :-(非变量(数量)->original_num_reversed(Num, Reversed);original_num_reversed(反向，基数)，( 基数 =:= 0->编号为 0;长度(_，我)，Num 是 Base*10^I)).

对于使用基数为 2 的浮点数，上面的代码很快就会中断，而对于基数为 10 的浮点数则稍晚一些.实际上，对于经典的基数 2 浮点数，这种关系本身没有多大意义.

至于number_chars/2的定义，ISO/IEC 13211-1:1995有如下模板和模式子句:

<块引用>

8.16.7.2 模板和模式

number_chars(+number, ?character_list)
number_chars(-number, +character_list)

第一种情况是实例化第一个参数时(因此是 nonvar).第二种情况，当第一个参数未实例化时.在这种情况下，必须实例化第二个参数.

但是请注意，由于非常相似的问题，number_chars/2 不是关系.例如，Chs = ['0','0'], number_chars(0, Chs) 成功，而 number_chars(0, Chs), Chs = ['0','0'] 失败.

_非常精美

1 这种重写是必要的，因为在许多 Prolog 中 reverse/2 只有在第一个参数已知时才会终止.在 SWI 中，由于一些特殊的低效率，这种重写是必要的.

I'm new to prolog; I'm coming from a structured programming background, as will become obvious :)

I am building up a prolog query that involves reversing a number; eg. reverse_num(123,X) results in X = 321. I came up with the following definition, but it only works when I provide a number as the first parameter.

reverse_num(Num, Revnum) :-
  number_chars(Num, Atoms),
  reverse(Revatoms, Atoms),
  number_chars(Reversed, Revatoms),
  Reversed = Revnum.

the number_chars/2 predicate doesn't like an unsubstantiated variable if I do: reverse_num(X,123) (where I'm expecting X to be 321).

Am I trying too hard to make reverse_num do something it shouldn't (should it be understood to work only with a number as the first parameter and variable as the second)?

Or is there an easy / straight-forward way to handle a variable as the first parameter?

解决方案

Relational naming

Before jumping into coding, let's take a step back. After all, the idea in Prolog is to define relations. Your name reverse_num/2 rather suggests some actions, num_reversed/2 might be a better name.

Determine the relation

Your definition is not that bad, let me rewrite it to¹:

num_reversed(Num, Reversed) :-
   number_chars(Num, Chars),
   reverse(Chars, Revchars),
   number_chars(Reversed, Revchars).

?- num_reversed(123,X).
X = 321.

?- num_reversed(1230,X).
X = 321.

?- num_reversed(12300,X).
X = 321.

Do you see the pattern? All numbers N*10^I have the same result!

Now, let's ask some more:

?- num_reversed(Num, 321).
ERROR: number_chars/2: Arguments are not sufficiently instantiated

Hm, what did we expect? Actually, we wanted all 123*10^I to be printed. That's infinitely many solutions. So above query, if correctly answered, would require infinitely many solutions to be printed. If we print them directly, that will take all our universe's lifetime, and more!

It is for this reason, that Prolog produces an instantiation error instead. By this, Prolog essentially states:

This goal is too general that I can make a good answer. Maybe there are infinitely many solutions, maybe not. I know not. But at least I indicate this by issuing an error. To remove this error you need to instantiate the arguments a bit more.

So the answer Prolog produced was not that bad at all! In fact, it is much better to produce a clean error than to, say, fail incorrectly. In general, Prolog's errors are often a very useful hint to what semantic problems you might have. See all error classes how.

Coroutining

As have other answers suggested, coroutining, using when/2 might solve this problem. However, coroutining itself has many semantic problems. Not without reason, systems like XSB do not offer it, due to the many problems related to subsumption checking. An implementation that would be compatible to it would be unexpectedly inefficient.

But for the sake of the point, we could make our definition more versatile by querying it like

 ?- when(nonvar(Num), num_reversed(Num, Reversed)).
 when(nonvar(Num), num_reversed(Num, Reversed)).

Now we get back as an answer exactly the query we entered. This is also known as floundering. So there is a way to represent infinitely may solutions in a compact manner! However, this comes at a rather high price: You no longer know whether a solution exists or not. Think of:

?- when(nonvar(Num), num_reversed(Num, -1)).
when(nonvar(Num), num_reversed(Num, -1)).

Others have suggested to wait also for nonvar(Reversed) which would only be correct if we would produce infinitely many answers - but, as we have seen - this just takes too much time.

Coroutining looked as a very promising road at the beginning of the 1980s. However, it has never really caught on as a general programming methodology. Most of the time you get much too much floundering which is just a pain and even more difficult to handle than, say instantiation errors.

However, a more promising offspring of this development are constraints. There, the mechanisms are much cleaner defined. For practical purposes, programmers will only use existing libraries, like CLPFD, CLPQ, or CHR. Implementing your own library is an extremely non-trivial project in its own right. In fact it might even be possible to provide an implementation of num_reversed/2 using library(clpfd) that is, restricting the relation to the integer case.

Mode dependent conditionals

Traditionally, many such problems are solved by testing for instantiations explicitly. It is good style to perform this exclusively with nonvar/1 and ground/1 like the condition in when/2- other type test predicates lead easily to errors as exemplified by another answer.

num_reversed(Num, Reversed) :-
   (  nonvar(Num)
   -> original_num_reversed(Num, Reversed)
   ;  original_num_reversed(Reversed, Base),
      (  Base =:= 0
      -> Num is 0
      ;  length(_, I),
         Num is Base*10^I
      )
   ).

Above code breaks very soon for floats using base 2 and somewhat later for base 10. In fact, with classical base 2 floats, the relation itself does not make much sense.

As for the definition of number_chars/2, ISO/IEC 13211-1:1995 has the following template and mode subclause:

8.16.7.2 Template and modes

number_chars(+number, ?character_list)
number_chars(-number, +character_list)

The first case is when the first argument is instantiated (thus nonvar). The second case, when the first argument is not instantiated. In that case, the second argument has to be instantiated.

Note, however, that due to very similar problems, number_chars/2 is not a relation. As example, Chs = ['0','0'], number_chars(0, Chs) succeeds, whereas number_chars(0, Chs), Chs = ['0','0'] fails.

_{Very fine print}

1 This rewrite is necessary, because in many Prologs reverse/2 only terminates if the first argument is known. And in SWI this rewrite is necessary due to some idiosyncratic inefficiencies.

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