Osnova

• Základní pojmy - připomenutí
  (přesné definice viz přednášky, literatura a manuál, zde jenom stručné připomenutí a příklady)
• Syntaxe logického programu
• Anatomie logického programu
• Sémantika logického programu
• Sicstus Prolog minimum
• Procvičení
• Mechanizmus backtrackingu - Příklady - Řešení
• Mechanizmus unifikace - Příklady - Řešení
• Vícesměrnost predikátů - Příklady - Řešení
• Operátory
• Závěr

---

• Syntaxe logického programu

  Univerzální datová struktura (slouží také pro příkazy jazyka) - term - definovaný rekurzivně

  • konstanty - číselné, alfanumerické (začínají malým písmenem), ze speciálních znaků (operátory)
  • proměnné - pojmenované (alfanumerické řetězce začínající velkým písmenem), anonymní (začínají podtržítkem)
  • složený term - funktor, arita, argumenty struktury jsou opět termy

• Anatomie logického programu

  Program je množina predikátů (v jednom nebo více souborech).
  Predikát (procedura) je seznam klauzulí s hlavou stejného jména a arity, tyto klauzule musí být uvedeny za sebou v jednom souboru (bez proložení klauzulemi jiného predikátu, protože další části původního predikátu by byly chápány jako redefinice).
  Klauzule, věty ukončené tečkou, se skládají z hlavy a těla. Prázdné tělo mají
  fakta, neprázdné pak
  pravidla, existují také klauzule bez hlavy -
  direktivy. Hlavu tvoří
  literál (složený term), tělo seznam literálů. Literálům v těle nebo v dotazu říkáme
  cíle. Dotazem v prostředí interpretu se spouští programy či procedury.
  

• Sémantika logického programu

  procedury <==> databáze faktů a pravidel <==> logické formule

• Sicstus Prolog minimum
  • Spuštění interpretu
    V unixu přidáme modul
    module add sicstus
    a spustíme příkazem
    sicstus
    pracovním adresářem je aktuální (tam kde byl spuštěn)
    V MS Windows standardně z nabídky Start/Programs nebo pomocí ikony,
    nastavíme pracovní adresář pomocí File/Working directory,
    v případě potřeby nastavíme font Settings/Font a uložíme nastavení Settings/Save settings.
  • Načtení programu - tzv. konzultace
    Editor není integrován, takže program editujeme externě ve svém oblíbeném editoru. Pak ho načteme z příkazové řádky v interpretu příkazem
    ?- consult(jmeno).
    nebo pomocí zkrácené syntaxe
    ?- [jmeno]. (předpokládá se přípona .pl)
    pokud uvádíme celé jméno případně cestu, dáváme jej do apostrofů
    ?- ['D:\prolog\moje_programy\jmeno.pl'].
    V MS Windows lze také pomocí nabídky File/Consult
  • Spouštění programů/procedur/predikátů je zápis dotazů, př.
    ?- muj_predikat(X,Y).
    ?- suma(1,2,Y), vypis('Vysledek je ',Y).
    Každý příkaz ukončujeme tečkou.
    
  • Přerušení a zastavení cyklícího programu
    Ctrl-C a
    
  • Ukončení interpretu příkazem
    ?- halt.

• Mechanizmus backtrackingu

  Příklad Rodokmen - definice jednoduchých predikátů, backtracking

  rodic(petr, filip).
  rodic(petr, lenka).
  rodic(pavel, jan).
  rodic(adam, petr).
  rodic(tomas, michal).
  rodic(michal, radek).
  rodic(eva, filip).
  rodic(jana, lenka).
  rodic(pavla, petr).
  rodic(pavla, tomas).
  rodic(lenka, vera).
  
  muz(petr).
  muz(filip).
  muz(pavel).
  muz(jan).
  muz(adam).
  muz(tomas).
  muz(michal).
  muz(radek).
  
  zena(eva).
  zena(lenka).
  zena(pavla).
  zena(jana).
  zena(vera).
  
  otec(Otec,Dite):-rodic(Otec,Dite),muz(Otec).
  
  

• Backtracking - příklady

1. Do pracovniho adresare si stahnete program rodokmen.pl. Načtěte program v interpretu (konzultujte).

2. V interpretu Sicstus Prologu pokládejte dotazy:
   a) Je Petr otcem Lenky?
   b) Je Petr otcem Jana?
   c) Kdo je otcem Petra?
   d) Jaké děti má Pavla?
   e) Ma Petr dceru?
   f) Které dvojice otec-syn známe?
   
   Řešení
   (středníkem si vyžádáme další řešení)

   | ?- otec(petr,lenka).
   yes
   | ?- otec(petr,jan).  
   no
   | ?- otec(Kdo,petr).
   Kdo = adam ? ;
   no
   | ?- rodic(pavla,Dite).
   Dite = petr ? ;
   Dite = tomas ? ;
   no
   | ?- otec(petr,Dcera),zena(Dcera).
   Dcera = lenka ? ;
   no
   | ?- otec(Otec,Syn),muz(Syn).
   Syn = filip,
   Otec = petr ? ;
   Syn = jan,
   Otec = pavel ? ;
   Syn = petr,
   Otec = adam ? ;
   Syn = michal,
   Otec = tomas ? ;
   Syn = radek,
   Otec = michal ? ;
   no
   | ?- 
   

3. Naprogramujte predikáty
   a) potomek(Potomek,Predek)
   b) prababicka(Prababicka,Pravnouce)
   c) nevlastni_bratr(Nevlastni_bratr,Nevlastni_sourozenec)
   
   Řešení

   potomek(Potomek,Predek):-rodic(Predek,Potomek).
   potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X).
   
   prababicka(Prababicka,Pravnouce):-
           rodic(Prababicka,Prarodic),
           zena(Prababicka),
           rodic(Prarodic,Rodic),
           rodic(Rodic,Pravnouce).
   
   nevlastni_bratr(Bratr,Sourozenec):-
           rodic_v(X,Bratr),
           muz(Bratr),
           rodic_v(X,Sourozenec),
           Bratr \== Sourozenec,  /* tento test neni nutny, ale zvysuje efektivitu
   */
           rodic_v(Y,Bratr),
           Y \== X,
           rodic_v(Z,Sourozenec),
           Z \== X,
           Z \== Y.
   
    
   /* nevhodne umisteni testu - vypocet "bloudi" v neuspesnych vetvich */       
   nevlastni_bratr2(Bratr,Sourozenec):-
           rodic_v(X,Bratr),
           rodic_v(X,Sourozenec),
           rodic_v(Y,Bratr),
           rodic_v(Z,Sourozenec),
           Y \== X,
           Z \== X,
           Z \== Y,
           muz(Bratr).
   

4. Prohledávání stavového prostoru:
   a) Zkuste předem odhadnout (odvodit) pořadí, v jakem budou nalezeni potomci Pavly?
   b) Jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci?
   c) Nahraďte ve svých programech volání predikátu rodic/2 následujícím predikátem rodic_v/2
   

   rodic_v(X,Y):-rodic(X,Y),print(X),print('? ').
   

   Pozorujte rozdíly v délce výpočtu dotazu nevlastni_bratr(filip,X) při změně pořadí testů v definici predikátu nevlastni_bratr/2
   Řešení

   /* varianta 1a */
   
   potomek(Potomek,Predek):-rodic(Predek,Potomek).
   potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X).
   
   /* varianta 1b - jine poradi odpovedi, neprimi potomci maji prednost */
   
   potomek(Potomek,Predek):-rodic(Predek,X),potomek(Potomek,X).
   potomek(Potomek,Predek):-rodic(Predek,Potomek).
   
   /* varianta 2a - leva rekurze ve druhe klauzuli,
   na dotaz potomek(X,pavla) vypise odpovedi, pak cykli */
   
   potomek(Potomek,Predek):-rodic(Predek,Potomek).
   potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X).
   
   /* varianta 2b - leva rekurze v prvni klauzuli,
   na dotaz potomek(X,pavla) hned cykli */
   
   potomek(Potomek,Predek):-potomek(Potomek,X),rodic(Predek,X).
   potomek(Potomek,Predek):-rodic(Predek,Potomek).
   
   

   Po nahrazení predikátu rodic/2 predikatem rodic_v/2 v predikátech nevlastni_bratr/2 a nevlastni_bratr2/2 a spuštění uvidíme:

   
   | ?- nevlastni_bratr(X,Y). 
   petr? petr? petr? petr? eva? petr? jana? 
   X = filip,
   Y = lenka ? ;
   petr? pavel? pavel? adam? adam? tomas? tomas? michal? michal? eva? eva? jana?
   pavla? pavla? pavla? adam? pavla? pavla? pavla? pavla? pav
   la? pavla? lenka? 
   no
   | ?- nevlastni_bratr2(X,Y).
   petr? petr? petr? petr? eva? eva? petr? eva? petr? petr? petr? jana? eva? petr?
   jana? 
   X = filip,
   Y = lenka ? ;
   petr? petr? petr? petr? eva? jana? petr? eva? petr? petr? petr? jana? jana?
   petr? jana? pavel? pavel? pavel? pavel? adam? adam? adam? ad
   am? pavla? pavla? adam? pavla? tomas? tomas? tomas? tomas? michal? michal?
   michal? michal? eva? eva? petr? petr? eva? eva? petr? eva? ja
   na? jana? petr? petr? jana? jana? petr? jana? pavla? pavla? adam? adam? pavla?
   pavla? adam? pavla? pavla? adam? pavla? pavla? pavla? pav
   la? pavla? pavla? adam? pavla? pavla? pavla? pavla? lenka? lenka? lenka? lenka? 
   no
   | ?- 
   
   

• Unifikace - příklady

  Které unifikace jsou korektní, které ne a proč? Co je výsledkem provedených unifikací?

  a) a(X)=b(X)
  b) X=a(Y)
  c) a(X)=a(X,X)
  d) X=a(X)
  e) jmeno(X,X)=jmeno(Petr,plus)
  f) s(1,a(X,q(w)))=s(Y,a(2,Z))
  g) s(1,a(X,q(X)))=s(W,a(Z,Z))
  h) X=Y,P=R,s(1,a(P,q(R)))=s(Z,a(X,Y))
  

  Řešení
  
  Neuspěje volání a) a c), ostatní ano, cyklické struktury vzniknou v případech d),g) a h) přestože u posledních dvou mají levá a pravá strana unifikace disjunktní množiny jmen proměnných.

• Mechanizmus unifikace

  Unifikace v průběhu dokazování predikátu odpovídá předávání parametrů při provádění procedury, ale je důležité uvědomit si rozdíly. Celý proces si ukážeme na příkladu predikátu Suma

  suma(0,X,X).                       /*klauzule A*/
  suma(s(X),Y,s(Z)):-suma(X,Y,Z).    /*klauzule B*/
  

  pomocí substitučních rovnic při odvozování odpovědi na dotaz

  ?- suma(s(0),s(0),X0).
  

  (indexace je zde pro odlišení instancí v jednotlivých voláních, proměnné mají pouze lokální platnost - v rámci jedné klauzule)

  1. dotaz unifikujeme s hlavou klauzule B, s A nejde unifikovat (1. argument)

  suma(s(0),s(0),X0) =
  suma(s(X1),Y1,s(Z1))         (unifikace
  základního volání a hlavy z B)
  ==> X1 = 0, Y1 = s(0), s(Z1) = X0
  (substituce proměnných při této unifikaci)
  ==> suma(0,s(0),Z1)                               (v těle klauzule B
  tedy voláme s těmito substituovanými parametry)         
  
  

  2. dotaz (nový podcíl) unifikujeme s hlavou klauzule A, klauzuli B si poznačíme jako další možnost

  suma(0,s(0),Z1) = suma(0,X2,X2)
  (unifikace nového (vnořeného) voláni a hlavy z A)
  X2 = s(0), Z1 = s(0)                    (substituce
  proměnných při této unifikaci)
  ==> X0 = s(s(0))                        (dosadíme i do rovnic z 1.
  kroku)
  
  X0 = s(s(0)) ;                          (výsledek výpočtu, vyžádáme
  si další řešení)
  
  

  2'. vracíme se k poznačenému místu, ale dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument)

  no                                      (výsledek pokračování výpočtu)
  

• Vícesměrnost predikátů

  Logický program lze využít vícesměrně, například jako

  • výpočet
    kdo je otcem Petra? ?-otec(X,petr).
    kolik je 1+1? ?- suma(s(0),s(0),X).
  • test
    je Jan otcem Petra? ?-otec(jan,petr).
    Je 1+1 2? ?- suma(s(0),s(0),s(S(0))).
  • generátor
    které dvojice otec-dítě známe? ?-otec(X,Y).
    Které X a Y dávají v součtu 2? ?- suma(X,Y,s(s(0))).

  ... ale pozor na levou rekurzi, volné proměnné, asymetrii, a jiné záležitosti

• Vícesměrnost - příklady

  Následující dotazy

  ?-suma(X,s(0),Z).
  

  a

  ?-suma(s(0),X,Z).
  

  nedávají stejné výsledky. Zkuste si je odvodit pomocí substitučních rovnic.

• Operátory
  definice operátorů umožňuje přehlednější infixový zápis binárních a unárních predikátů, příklad: definice op(1200,Y,':-') umožňuje zápis

  a:-print(s(s(0))),b,c).
  

  pro výraz

  :-(a,,(print(s(s(0))),,(b,c))).
  

  Prefixovou notaci lze získat predikátem display/1 .

  Vyzkoušejte

  
            display((a:-print(s(s(0))),b,c)). 
            display(a+b+c-d-e*f*g-h+i).
            display([1,2,3,4,5]).
            

  Definice standardních operátorů najdete na konci manuálu.

• Závěr
  Dnešní látku jste pochopili dobře, pokud víte
  • jaký vliv má pořadí klauzulí a cílu v predikátu potomek/2 na jeho funkci,
  • jak umisťovat testy, aby byl prohledávaný prostor co nejmenší (příklad nevlastni_bratr/2),
  • k čemu dojde po unifikaci X=a(X),
  • a umíte odvodit pomocí substitučních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z).

^