6

我想知道如何在 Prolog 中结合统一和 OO。我想在术语对象上实现多方法调度。

如果没有术语对象和简单术语,我将执行以下操作,并且可以从多参数索引中受益:

collide_with(asteroid(_), asteroid(_)) :- /* case 1 */
collide_with(asteroid(_), spaceship(_,_)) :- /* case 2 */
collide_with(spaceship(_,_), asteroid(_)) :- /* case 3 */
collide_with(spaceship(_,_), spaceship(_,_)) :- /* case 4 */

但上面只给出了精确的类型匹配。

如果我想要一个子类类型匹配,我应该怎么做(可能还有更多的宇宙飞船子类,如 excelsior、galaxy 等。在案例 2,3 和 4 中也应该匹配)。

我还能使用统一和索引吗?

再见

PS:示例来自这里,它没有 Prolog 解决方案:
https ://en.wikipedia.org/wiki/Multiple_dispatch

4

3 回答 3

3

你的问题到处都是:术语对象,多方法调度等。Prolog 没有术语对象或调度,真的,但我认为这个问题的精神很有趣。

在我们拥有多方法和多调度之前,我们需要调度。我认为您担心的是您希望能够编写一个如下所示的过程:

frob(spaceship(X, Y...)) :- % do something with spaceships
frob(asteroid(X, Y...))  :- % do something with asteroids

然后你希望能够说出来,frob(excelsior(X, Y, ...))并以某种方式在第一个子句中结束。这显然不会开箱即用,但这并不意味着你不能让它工作。以下是我会尝试的方法:

选择更简单的函子形状

与其尝试使它与 . 一起工作excelsior(...),不如更改您的表示以使其更容易内省。一个非常通用的方法可能如下所示:

object(Type, Properties...)

如果您不关心继承,这可能会起作用,但您确实关心。那么,如果你为子类型信息创建一个槽呢?然后你可以在你关心的情况下匹配它,否则忽略它。您的结构将如下所示:

type(SubtypeInfo, Properties...)

然后你可以这样写:

frob(spaceship(_, X, Y)) :- % stuff

如果你用 Excelsior 调用它,它可能看起来像这样:

?- frob(spaceship(excelsior(SpecialProperties...), X, Y)).

换句话说,使您的术语在外部具有最通用的类​​型,并在内部内容中包含更具体的信息。

frob2(spaceship(excelsior(_, ...), X, Y)) :- % do something with excelsiors

使用元解释器

编写自己的 Prolog 方言是可能的。如果您向数据库添加一些关于您的类型是子类型的事实,您自己的元解释器可以拦截评估过程并使用父类型重试。

不幸的是,我对此并不擅长,下面的元解释器应该被视为一个有缺陷的草图/概念验证,而不是一个要遵循的模型。

:- op(500, xfx, is_kind_of).

excelsior is_kind_of spaceship.

frob(spaceship(X, Y)) :- !, write('I frobbed a spaceship'), nl.
frob(_) :- write('I frobbed something else'), nl.

execute(true).
execute((A,B)) :- execute(A), execute(B).
execute(A) :-
    predicate_property(A, built_in)
       -> call(A)
       ;  execute_goal(A).

execute_goal(Goal) :- clause(Goal, Body), call(Body).
execute_goal(Goal) :- supertype_goal(Goal, NewGoal), execute_goal(NewGoal).

supertype_goal(Goal, NewGoal) :-
    Goal =.. [Head, Term],
    Term =.. [Type|Args],
    Type is_kind_of Supertype,
    NewTerm =.. [Supertype|Args],
    NewGoal =.. [Head, NewTerm].

这里的想法是尝试按原样执行目标,然后重新执行已重写部分目标的目标。虽然supertype_goal不是很笼统,替换例程也不全面,但可以说明意图:

?- execute(frob(excelsior(this,that))).
I frobbed something else
true ;
I frobbed a spaceship
true ;
I frobbed something else
true ;
false.

是的,所以,不是很好,但是比我更熟练的 Prolog 用户可能会清理它并使其工作。

讨论

在 Prolog 中实际上只有两个数据可以进入:它可以存在于调用堆栈中,或者它可以存在于数据库中。我展示的第一种方法实际上是第一种方法的一个示例:找到一种方法来为您的目的重新打包“子类型化”,以便它可以存在于调用堆栈中而不会干扰(某些)统一。如果您仔细地构造这些术语(并仔细编码),您可能可以完成这项工作,而且调试起来也不会是地狱。但它可能有点难以阅读。

第二种方法使用数据库中的单独关系来具体化不同“子类型”之间的关系。一旦你有了它,你需要修改解释器以使用它。这说起来容易做起来难,而且有点棘手,但我不认为这是世界上最糟糕的想法。虽然,在考虑它时,你想要做的那种统一必须由元解释器设计。

您会发现 Logtalk 在“参数对象”(其标识符本质上是完整的 Prolog 术语)和普通对象之间也有类似的二分法,它们创建了一个完整的命名空间,它们就像在一个单独的数据库中一样封装。对于非参数对象,对象结构上的统一不会像术语那样发生。

性能问题

假设我在某个方法中将两个对象作为参数。如果我使用第一种方法,我认为如果索引可用,我会从索引中受益,并且我不会深入研究这个术语——我认为通用编程应该更好。我不知道 Prolog 系统如何响应深入统一到某个结构中。我想他们做得很好,但我不知道参数索引。感觉会很紧张。

第二种方法根本没有那么好。如果我的层次结构可以深 N 个类,我可能会尝试 N^2 种不同的组合。这听起来没有效率。显然 Paulo 已经在 Logtalk 中找到了一些东西,它似乎没有这个性能问题。

双发分流

当我学习 Smalltalk 时,这对我来说是一个很大的启示,所以如果你已经知道,请原谅我。您可以使用“双分派”在单分派语言中获得多分派的类型优势。基本上,您拥有所有对象 implement collide_with,将“其他”对象作为参数,因此您拥有Asteroid::collide_with(Other)andShip::collide_with(Other)Bullet::collide_with(Other)。然后,这些方法中的每一个都调用 Other 的collide_with_type,传入 self。你会得到一堆方法(很多你会委托给另一方),但是你可以在运行时安全地重新创建所有丢失的类型信息。

前段时间我在 Lua 中写了一个糟糕的 Asteroids 克隆,你可以在其中看到它是如何工作的:

-- double dispatch for post collision handling
function Asteroid:collideWith(other)
   return other:collideWithAsteroid(self)
end

function Asteroid:collideWithShot(s) 
   -- remove this asteroid from the map
   if index[self] then
      table.remove(asteroids, index[self])
      index[self] = nil
      s:remove()
   end
end

function Asteroid:collideWithPlayer(p) 
   p:collideWithAsteroid(self)
end

function Asteroid:collideWithAsteroid(ast) end

所以你可以看到那里的一切:Asteroid:collideWithShot从游戏中移除小行星,但它委托Asteroid:collideWithPlayer(p)to Player:collideWithAsteroid(a),两个小行星碰撞没有做任何事情。

这在 Logtalk 中的外观的基本草图是:

:- protocol(physical).

  :- public(collides_with/1).

:- end_protocol.

:- object(asteroid, implements(physical)).

  collides_with(Other) :- self(Self), Other::collides_with_asteroid(Self).

  collides_with_asteroid(AnotherAsteroid).
  collides_with_ship(Ship) :- % do stuff with a ship

:- end_object.

请耐心等待,我很少使用 Logtalk!

更新:可悲的是,Jan Burse(Jekejeke Prolog 的作者)指出,cut 操作员将对双重调度造成严重破坏。这并不一定意味着带有子类型的多重分派与统一不兼容,但它确实意味着作为一种解决方法的双重分派与剪切不兼容,这将使不确定性复杂化并可能破坏这种方法。有关更多讨论,请参阅下面的评论。

结论

我不认为子类型和统一是相互排斥的,因为 Logtalk 两者都有。我不认为子类型和带有参数索引的多重分派是互斥的,但是 Logtalk 没有多重分派,所以我不能确定。在大多数情况下,即使在 Java 中我也避免子类型化,所以我可能有偏见。不过,多分派是一种 100 美元的语言功能;我不能说很多语言都有它,但你可以通过双重调度非常有效地伪造它。

如果你对这些东西感兴趣,我会大量研究 Logtalk。特别是参数示例非常引人注目。

我怀疑这是否真的回答了您的问题,甚至落在了同一个球场上,但我希望它有所帮助!

于 2016-01-26T06:50:55.197 回答
1

在 CLOS 中,用于多次调度的泛型函数没有封装在类中,而是按函数名分组。因此,这里的等价物将是普通的 Prolog 规则。此外,假设多参数索引,规则头中的参数必须充分实例化为我们想要执行多分派的“类型”,以便每次都选择正确的规则而没有虚假的选择点。正如 OP 举例说明的那样:

collide_with(asteroid(_), asteroid(_)) :-
    ...
collide_with(asteroid(_), spaceship(_)) :-
    ...
collide_with(spaceship(_), asteroid(_)) :-
    ...
collide_with(spaceship(_), spaceship(_)) :-
    ...

鉴于统一在 Prolog 中的工作方式,如果我们想要对基本的小行星和宇宙飞船“类型”进行专门化,并按照 Daniel 的建议,我们可以使用复合术语asteroid/1spaceship/1作为定义“类型”和“子”的实际对象的包装器。类型”。那么缺少的是一种使用单一调度的方法,例如在 Logtalk 中找到的,以重定向到正确的规则。Daniel 已经描述了如何使用双重调度作为一种可能的解决方案。另一种方法是定义一个参数对象,例如:

:- object(collide_with(_, _)).

    :- public(bump/0).
    bump :-
        % access the object parameters
        this(collide_with(Obj1, Obj2)),
        % wrap the object parameters
        wrap(Obj1, Wrapper1), wrap(Obj2, Wrapper2),
        % call the plain Prolog rules
        {collide_with(Wrapper1, Wrapper2)}. 

    wrap(Obj, Wrapper) :-
        wrap(Obj, Obj, Wrapper).

    wrap(Obj, Wrapper0, Wrapper) :-
        (   extends_object(Wrapper0, Parent) ->
            wrap(Obj, Parent, Wrapper)
        ;   Wrapper =.. [Wrapper0, Obj] 
        ).

:- end_object.

我们还将拥有所有必要的对象来表示小行星和星际飞船的层次结构(为了简单起见,我在这里使用原型而不是类/实例)。例如:

:- object(spaceship).
    ...
:- end_object.

:- object(galaxy, extends(spaceship)).
    ...
:- end_object.

:- object(asteroid).
    ...
:- end_object.

:- object(ceres, extends(asteroid)).
    ...
:- end_object.

典型的用法是:

?- collide_with(ceres, galaxy)::bump.
...

由于collide_with/2谓词的普通 Prolog 规则将接收(包装的)对象标识符,因此它们向那些对象发送请求任何必要信息的消息以实现我们在两个对象碰撞时想要的任何行为是微不足道的。

参数对象抽象了这种多分派解决方案的collide_with/2实现细节。与 Daniel 描述的双重调度解决方案相比,一个优点是我们不需要为碰撞消息挑选出其中一个对象。一个缺点是我们需要bump/0在代码中添加一条额外的消息来触发计算。

于 2016-01-27T16:22:34.320 回答
0

刚刚有了以下时髦的想法。假设我们有一个谓词 isinst/2,它是 instof/2 的镜像。如果我们想检查 X 是否是小行星。我们会做的宇宙飞船:

 isinst(asteroid, X). /* checks whether X is an asteroid */
 isinst(spaceship, X). /* checks whether X is a spaceship */

所以 Prolog 代码很简单:

 collide_with(X, Y) :- isinst(asteroid, X), isinst(asteroid, Y), /* case 1 */
 collide_with(X, Y) :- isinst(asteroid, X), isinst(spaceship, Y), /* case 2 */
 collide_with(X, Y) :- isinst(spaceship, X), isinst(asteroid, Y), /* case 3 */
 collide_with(X, Y) :- isinst(spaceship, X), isinst(spaceship, Y), /* case 4 */

现在假设我们的 Prolog 系统提供属性变量,以及属性变量的可读概念,例如 X{...}。然后我们可以继续,并定义:

 collide_with(X{isinst(asteroid)}, Y{isinst(asteroid)}) :- /* case 1 */
 collide_with(X{isinst(asteroid)}, Y{isinst(spaceship)}) :- /* case 2 */
 collide_with(X{isinst(spaceship)}, Y{isinst(asteroid)}) :- /* case 3 */
 collide_with(X{isinst(spaceship)}, Y{isinst(spaceship)}) :- /* case 4 */

这可能会导致代码稍微快一些,因为属性变量会直接帮助统一,而不是主体必须检查。

目前我还不清楚它是否也会导致更好的索引,问题是继承层次结构可能会在运行时发生变化,这可能会影响索引并需要重新索引。如果我们可以保证继承层次结构不是开放世界,例如通过将类标记为最终的,这也成立。如果 Prolog 系统被视为动态的,这也可以改变。

除此之外,如果继承层次结构不是开放世界,即是否可以枚举子类,则有一些明显的索引想法。这里唯一的问题是,如果可能的话,由同一个主体有效地共享不同的头部。否则,条款可能会激增。

再见

PS:从正文检查到属性变量时会有轻微的语义转移,因为属性变量可能会延迟钩子,

所以我们可能会在使用主体检查时得到 collide_with(X,Y) 失败,因为 X 和 Y 未实例化,另一方面 collide_with(X,Y) 在使用属性变量时成功。

但是当实例化 collide_with/2 的参数时,结果应该或多或少相同。

于 2016-01-28T18:30:26.230 回答