A nyelv végrehajtási mechanizmusa (redukciós lépés, visszalépés)

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.2.2, 3.5.1

3.2.2 Végrehajtási algoritmus

A végrehajtási algoritmus két pillére: a mintaillesztés és a visszalépéses mélységi keresés.

A mintaillesztés alaplépése a redukciós lépés, mely során a bemenetre érkező célsorozatok első célját kíséreljük meg egyesíteni a klóz fejével. Siker esetén a klóz törzsét az első cél helyébe rakjuk. Két kifejezés egyesíthető, ha a bennük lévő változók helyébe tetszőleges kifejezést helyettesítve a két kifejezés azonossá tehető.

Ha egy változó többször is előfordul, akkor minden előfordulását azonos kifejezésere kell cserélni.

Redukciós lépés

Bemenete egy célsorozat és egy klóz, először elkészítjük a klóz másolatát, minden változóját szisztematikusan lecserélve új változókra, ez az ismételt felhasználáshoz (rekurzió) nélkülözhetetlen. Ezután megkísérlejük a célsorozat első hívását egyesíteni a megadott fejjel (link=egyesítési algoritmus). Siker esetén a keletkezett behelyettesíteéseket elvégezzük a klóz belsejében és a maradék célsorozaton. Végül a törzset rakjuk az első hívás helyébe.

1. A klózt lemásoljuk, minden változót szisztematikusan új változóra cserélve.
2. A célsorozatot szétbontjuk az első hívásra és a maradékra.
3. Az első hívást helyettesítjük a klózfejjel.
4. A szükséges behelyettesítéseket elvégezzük a klóz törzsén és a célsorozat maradékán.
5. Az új célsorozat: a klóztörzs és utána a maradék célsorozat.
6. Ha a hívás és a klózfej nem egyesíthető, akkor a redukciós lépés meghiúsul.

Végrehajtási algoritmus

Célsorozat futása az adott prolog programra vonatkozatva. Eredménye lehet siker (változók behelyettesítésével járhat) vagy meghiúsulás (nem törtnéneik változó behelyettesítés)

• beépítettt eljárás hívása:
  

végrehajtása során siker esetén behelyettesítés után új célsorozatott készít az első hívás elhagyásával. Sikertelenség visszalépést eredményez.

• felhasználói eljárás hívása:
  

első olyan klóz megkeresése, melyre a redukciós lépés sikeresen lefut. Ha nincs ilyen, visszalépés.

Visszalépés történik tehát akkor, ha

• egy beépített eljárás meghiúsul, vagy
• ha egy felhasználói eljáráshívást nem lehet (több) klózfejjel egyesíteni (nincs olyan klózfej, amelyre a redukciós lépés sikerrel futna le)

Amennyiben nincs visszalépés az új célsorozat feldolgozása kezdődik meg. Visszalépés esetén visszatér a legutolsó sikeres redukciós lépéshez (minden azóta történt behelyettesítés érvényét veszti) és új klóz illezstésével próbálkozik, meghiúsulás esetén további visszalépés következik.

• 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 visszalépés: egy már lefutott eljárás belsejébe térünk vissza és új megoldásokat keresünk.

Ha nincs hova vissazlépni a teljes hívás meghiúsul. Ha a visszalépés során üres lesz a célsorozat a hívás sikeres lesz.

3.5.1 Teljes végrehajtási algoritmus

1. (Kezdeti beállítások:) A verem üres, CS := célsorozat.
   
2. (Beépített eljárások:) Ha CS első célja beépített, akkor hajtsuk végre.
   

• • Ha sikertelen => 6. lépés
  • Ha sikeres, elvégezzük a behelyettesítéseket, CS-ből elhagyjuk az első hívást, => 5. lépés.

1. (Klózszámláló kezdőértékezése:) I = 1.
   
2. (Redukciós lépés:) CS első hívásához tartozó eljárásdefinícióban N klóz van.

• • Ha I > N => 6. lépés
  • Redukciós lépés az I-edik klóz és a CS célsorozat között.
  • Ha sikertelen, akkor I := I+1, és => 4. lépés.
  • Ha I < N (nem utolsó), akkor vermeljük <CS,I>-t.
  • CS := a redukciós lépés eredménye.

1. (Siker:) Ha CS üres, akkor sikeres vég, egyébként => 2. lépés.
   
2. (Sikertelenség:) Ha a verem üres, akkor sikertelen vég.
   
3. (Visszalépés:) Ha a verem nem üres, akkor leemeljük a veremből <CS,I>-t, I := I+1, és => 4. lépés.