Столкновение звездных объектов с помощью мультиметодов в OO Prolog?
Интересно, как можно объединить объединение и ОО в Прологе? Я хотел бы реализовать мультиметодическую рассылку для объектов термина.
Без терминологических объектов и простых терминов я бы сделал следующее и мог бы извлечь выгоду из много аргументной индексации:
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
3 ответа
Вы как бы повсюду задаетесь вопросом: терминологические объекты, мультиметодическая рассылка и т. Д. На самом деле у Пролога нет терминологических объектов или диспетчеризации, но я думаю, что дух вопроса интересен.
Прежде чем мы сможем иметь мультиметоды и многократную отправку, нам потребуется отправка. Насколько я понимаю, вы беспокоитесь о том, что хотите написать процедуру, которая выглядит следующим образом:
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
Используйте Metainterpreter
Написание собственного диалекта пролога возможно. Если вы добавите в базу данных некоторые факты о том, что ваши типы являются подтипами, ваш собственный metainterpreter может перехватить процесс оценки и повторить попытку с родительскими типами.
К сожалению, я не очень хорош в этом, и следующий метаинтерпретатор должен рассматриваться как ошибочный набросок / доказательство концепции, а не как модель, которой нужно следовать.
:- 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, чем я, мог бы, вероятно, очистить его и заставить его работать.
обсуждение
На самом деле в Прологе данные могут храниться только в двух местах: они могут находиться в стеке вызовов или в базе данных. Первый метод, который я показываю, действительно является примером первого: найдите способ переупаковки "подтипа" для ваших целей, чтобы он мог жить в стеке вызовов, не мешая (некоторым) объединению. Если вы тщательно структурируете термины (и тщательно программируете), вы, вероятно, сможете сделать это, и отладка будет не адской. Но это может быть немного сложнее читать.
Второй метод использует отдельную связь в базе данных для уточнения связи между различными "подтипами". Если у вас есть это, вам нужно изменить интерпретатор, чтобы использовать его. Это легче сказать, чем сделать, и немного сложно, но я не думаю, что это худшая идея в мире. Хотя, думая об этом, тот тип объединения, который вы хотите сделать, должен быть спроектирован метаинтерпретатором.
Вы обнаружите, что Logtalk также имеет схожую дихотомию между "параметрическими объектами", чьи идентификаторы по существу являются полными терминами Пролога, и обычными объектами, которые создают целое пространство имен, которое они инкапсулируют, как будто в отдельной базе данных. С непараметрическими объектами объединение не происходит в структуре объекта, как это происходит с термином.
Проблемы производительности
Предположим, я принимаю два объекта в качестве параметров в некотором методе. Если я использую первый метод, я думаю, что мне будет полезна индексация, если она доступна, и я не буду слишком углубляться в этот термин - я думаю, что общее программирование должно быть лучше. Я не знаю, как системы Prolog реагируют на объединение глубоко в какую-то структуру; Я бы предположил, что они преуспевают, но я не знаю об индексации аргументов. Такое ощущение, что это было бы чревато.
Второй подход не выдерживает этого. Если бы моя иерархия могла иметь N классов, я мог бы попробовать N^2 различных комбинаций. Это звучит непродуктивно. Ясно, что Пауло что-то понял в Logtalk, у которого, похоже, нет этой проблемы с производительностью.
Диверсия при двойной отправке
Это было откровением для меня, когда я изучал Smalltalk, так что прости меня, если ты уже это знаешь. Вы можете получить преимущество типа многократной отправки на языке с одной отправкой, используя "двойную отправку". По сути, все ваши объекты реализованы collide_with принимая "другой" объект в качестве параметра, так что у вас есть Asteroid::collide_with(Other) а также Ship::collide_with(Other) а также Bullet::collide_with(Other), Затем каждый из этих методов вызывает другие collide_with_type Проходя в себя. Вы получаете кучу методов (многие из которых вы делегируете другой стороне), но вы можете безопасно воссоздать всю информацию о недостающем типе во время выполнения.
Некоторое время назад я написал дурацкий клон астероидов в Lua, в котором вы можете увидеть, как он работает:
-- 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) в 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 очень редко!
Обновление: как ни печально, Ян Бурс (автор "Прозвища Jekejeke") отметил, что оператор разреза нанесет двойной удар. Это не обязательно означает, что многократная отправка с подтипом несовместима с объединением, но это означает, что двойная отправка как обходной путь несовместима с разрезом, что усложнит недетерминизм и может разрушить этот подход. Смотрите комментарии ниже для дальнейшего обсуждения.
Заключение
Я не думаю, что подтипы и унификация являются взаимоисключающими, потому что они есть у Logtalk. Я не думаю, что субтипирование и множественная диспетчеризация с индексацией аргументов также являются взаимоисключающими, но Logtalk не имеет множественной диспетчеризации, поэтому я не уверен. Я избегаю подтипов даже в Java, по большей части, поэтому я, вероятно, предвзятый. Многократная отправка - своего рода языковая особенность за 100 $; Я не могу сказать, что у многих языков есть это, но вы можете подделать это довольно эффективно с двойной отправкой.
Я бы тщательно изучил Logtalk, если вы заинтересованы в этом. В частности, параметрический пример довольно убедителен.
У меня есть некоторые сомнения, что это действительно ответило на ваш вопрос или даже приземлилось на том же стадионе, но я надеюсь, что это поможет!
В CLOS универсальные функции, используемые для множественной диспетчеризации, не инкапсулированы в классы, а сгруппированы по имени функции. Таким образом, эквивалент здесь был бы простыми правилами Пролога. Более того, предполагая многократное индексирование аргументов, аргументы в заголовках правил должны быть в достаточной степени созданы для "типов", над которыми мы хотим выполнить множественную диспетчеризацию, чтобы правильное правило выбиралось каждый раз без ложных точек выбора. В качестве примера можно привести:
collide_with(asteroid(_), asteroid(_)) :-
...
collide_with(asteroid(_), spaceship(_)) :-
...
collide_with(spaceship(_), asteroid(_)) :-
...
collide_with(spaceship(_), spaceship(_)) :-
...
Учитывая, как объединение работает в Прологе, если мы хотим иметь специализации базовых "типов" астероидов и космических кораблей, и, следуя предложению Дэниела, мы можем использовать составные термины asteroid/1 а также spaceship/1 как обертки для реальных объектов, определяющих "типы" и "подтипы". В таком случае отсутствует способ использовать одну диспетчеризацию, как, например, в Logtalk, для перенаправления на правильное правило. Даниэль уже описал, как использовать двойную диспетчеризацию в качестве возможного решения. Альтернативой может быть определение параметрического объекта, такого как:
:- 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 Предикат получит (обернутые) идентификаторы объектов, для них тривиально отправить сообщения этим объектам, запрашивающие любую необходимую информацию для реализации любого поведения, которое мы хотим, когда сталкиваются два объекта.
collide_with/2 Параметрический объект абстрагирует детали реализации этого решения для множественной диспетчеризации. Одно из преимуществ решения двойной диспетчеризации, описанного Дэниелом, заключается в том, что нам не нужно выделять один из объектов для сообщения о столкновении. Одним из недостатков является то, что нам нужно дополнительное сообщение, bump/0 в кодовой обители, чтобы запустить вычисление.
Просто пришла следующая прикольная идея. Предположим, у нас есть предикат isinst/2, зеркало instof/2. Если мы хотим проверить, что X является астероидом соответственно космический корабль мы бы сделали:
isinst(asteroid, X). /* checks whether X is an asteroid */
isinst(spaceship, X). /* checks whether X is a spaceship */
Таким образом, код Пролога прост:
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.