Prolog végrehajtási modellek: keresési fa, doboz modell

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

• fejezetek: 3.5 bevezető, 3.5.2,
• fóliák: I.75-87

3.5 Bevezetője

• sekély visszalépés: egy eljárás klózából uagyanezen eljárás egy későbbi klózába kerül a vezérlés
• mély egy már lefutott lejárás belsejébe térünk vissza és új megolásokat keresünk.

Egy célsorozat keresési fája egy olyan irányított gráf, amelynek csúcsaiban célsorozatok vannnak és két csúcs közt akkor van él, ha a kiinduló csúcs célsorozatából egyetlen redukciós lépéssel eljuthatunk a cél csúcs célsorozatához. A fa gyökerében a teljes kiindulási célsorozat van. Az újabb megoldás kérésére ; választ adhatjuk a Prolognak, ezt úgy lehet felfogni mint egy mesterséges meghiúsulást, amit a felhasználó vált ki, mély visszalépés történik.

KÉP2

3.5.2 4 dobozos modell

Az eljárás doboz modell (procedure box model) is alkalmas a Prolog végrehajtását megjeleníteni. Az eljáráshívást egy olyan dobozzal ábrázoljuk melynek 4 úgynevezett kapuja van:

• hívás (*call*): eljárás meghívása
• kilépés (*exit*): sikeres kilépés
• újra (*redo*): sikeresen lefutott eljárás visszalépése -> új megoldás keresése
• sikertelenség (*fail*)

A Prolog eljárás-végrehajtás két fázisa:

• előre menő végrehajtás: egymásba skatulyázott eljárás-belépések és ?kilépések
• visszafelé menő végrehajtás: újabb megoldás kérése egy már lefutott eljárástól

"Kapcsolási" alapelvek

• előre menő végrehajtás
  • A szülő Call kapuját az első klóz első hívásának Call kapujára kötjük.
  • Egy rész-eljárás Exit kapuját
    • a következő hívás Call kapujára, vagy
    • ha nincs következő hívás, akkor a szülő Exit kapujára kötjük.
• visszafelé menő végrehajtás
  • Egy rész-eljárás Fail kapuját
    • az előző hívás Redo kapujára, vagy
    • ha nincs előző hívás, akkor a következő klóz első hívásának Call kapujára, vagy
    • ha nincs következő klóz, akkor a szülő Fail kapujára kötjük
  • A szülő Redo kapuját mindegyik klóz utolsó hívásának Redo kapujára kötjük

*mindig arra a klózra térünk vissza, amelyben legutoljára volt a vezérlés

Ezen a helyen volt linkelve a SHOT083.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)