Почему мой код пролога в обратном порядке?

Question

Мой код в прологе отображается в обратном ожидаемом порядке. Вот код:

room(homermargeroom, donuts). 
room(homermargeroom, tv). 
room(ensuite, nothing). 
room(lisaroom, beer). 
room(bartroom, donuts). 
room(hallway, nothing). 
room(bathroom, nothing). 
room(maggieroom, nothing). 


/* These are the locations where Bart, Lisa and Maggie are hiding */ 
hiding(bart, cupboard). 
hiding(lisa, ensuite). 
hiding(maggie, bathroom). 

canHomerGet(Start, End, Item) :- 
    homermove(Start, End), 
    canTravelThrough(Start, Item), 
    canTravelThrough(End, Item), 
    write('Homer moves from '), write(Start), write(' to '), write(End), nl. 

canHomerGet(Start, End, Item) :- 
    homermove(Start, Somewhere), 
    canTravelThrough(Somewhere, Item), 
    canHomerGet(Somewhere, End, Item), 
    write('Homer moves from '), write(Start), write(' to '), write(Somewhere), nl. 


canTravelThrough(Somewhere, _Item) :- 
    room(Somewhere, nothing). 

canTravelThrough(Somewhere, Item) :- 
    room(Somewhere, tv), 
    Item == portableTV. 

canTravelThrough(Somewhere, Item) :- 
    room(Somewhere, donuts), 
    Item == nachos. 

canTravelThrough(Somewhere, Item) :- 
    room(Somewhere, sistersinlaw), 
    Item == blindfold. 

canTravelThrough(Somewhere, Item) :- 
    room(Somewhere, beer), 
    Item == margarita. 


canHomerFind(Child, Item) :- 
    hiding(Child, Destination), 
    canHomerGet(garage, Destination, Item). 

Здесь выход:

Гомер перемещается из фойе Купбоарда
Гомера перемещается из столовой в фойе
Гомер перемещается из кухни в столовой
Гомер перемещается из sidehall на кухню
Гомер перемещается из гаража в боковой проход

Как я это написал, я ожидаю, что это напечатает «Гомер движется из гаража в кулак», а затем распечатает этот список в обратном порядке. Любые предложения по устранению этого?

Answer 1

Ваше определение предиката canHomerGet/3 записывает только вывод перемещения в конце. Во втором предложении рекурсивный вызов предшествует написанию хода. Это делает этот предикат non tail-recursive. То есть запись движений сохраняется на неявном рекурсивном стеке, а затем выталкивается из стека при успешном вызове предиката. Таким образом, первое напечатанное движение является последним, и последнее напечатанное движение является первым.

Вы могли бы возникнуть соблазн решить эту проблему, изменив второе предложение, чтобы:

canHomerGet(Start, End, Item) :- 
    homermove(Start, Somewhere), 
    canTravelThrough(Somewhere, Item), 
    write('Homer moves from '), write(Start), write(' to '), write(Somewhere), nl, 
    canHomerGet(Somewhere, End, Item). 

Это сделало бы предикат хвостовой рекурсией, таким образом, работает в постоянном пространстве стека, но встает новая проблема: движения ведущих нигде не было бы напечатано, так как откат для поиска успешного маршрута не отменяет печать движений. Обычное решение состоит в том, чтобы создать список шагов (используя дополнительный аргумент), а затем распечатать список (после его реверсирования) в конце. Я оставлю это вам как упражнение.