Home     Termíny     Cvičení     Projekty     Rezervace termínu

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í
• Aritmentika - Příklady - Řešení
• Operátory
• Závěr
• Zpět na stránku jen se zadáním

---

• 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))
  ==> X1 = 0, Y1 = s(0), s(Z1) = X0
  ==> suma(0,s(0),Z1)
  

  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)
  X2 = s(0), Z1 = s(0)
  ==> X0 = s(s(0))
  X0 = s(s(0)) ;
  

  2'. dotaz z kroku 1. nejde unifikovat s hlavou klauzule B (1. argument)

  no
  

• 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.

• Aritmetika

  zavádíme z praktických důvodů, ale aritmetické predikáty již nejsou vícesměrné, protože v každém aritmetickém výrazu musí být všechny proměnné instaciovány číselnou konstantou

  Důležitý rozdíl ve vestavěných predikátech is/2 vs. =/2 vs. =:=/2

  is/2
  < konstanta nebo proměnná > is < aritmetický výraz >
  výraz na pravé straně je nejdříve aritmeticky vyhodnocen a pak unifkován s levou stranou

  =/2
  < libovolný term > = < libovolný term >
  levá a pravá strana jsou unifikovány

  "=:="/2 "=/="/2 ">="/2 "=<"/2
  < aritmetický výraz > =:= < aritmetický výraz >
  < aritmetický výraz > =/= < aritmetický výraz >
  < aritmetický výraz > =< < aritmetický výraz >
  < aritmetický výraz > >= < aritmetický výraz >
  levá i pravá strana jsou nejdříve aritmeticky vyhodnoceny a pak porovnány

• Aritmetika - příklady

1. Jak se liší následující dotazy (na co se kdy ptáme)? Které uspějí (kladná odpověď), které neuspějí (záporná odpověď), a které jsou špatně (dojde k chybě)? Za jakých předpokladů by ty neúspěšné případně špatné uspěly?

   a) X = Y + 1
   b) X is Y + 1
   c) X = Y
   d) X == Y
   e) 1 + 1 = 2
   f) 2 = 1 + 1
   g) 1 + 1 = 1 + 1
   h) 1 + 1 is 1 + 1
   i) 1 + 2 =:= 2 + 1
   j) X \== Y
   k) X =\= Y
   l) 1 + 2 =\= 1 - 2
   m) 1 <= 2
   n) 1 =< 2
   o) sin(X) is sin(2)
   p) sin(X) = sin(2+Y)
   r) sin(X) =:= sin(2+Y)
   

   Vyzkoušejte :-)
   Nápověda: '='/2 unifikace, '=='/2 test na identitu, '=:='/2 aritmetická rovnost, '\=='/2 negace testu na identitu, '=\='/2 aritmetická nerovnost

2. Jak se liší predikáty s1/3 a s2/3? Co umí s1/3 navíc oproti s2/3 a naopak?

   s1(0,X,X).
   s1(s(X),Y,s(Z)):-s1(X,Y,Z).
   
   s2(X,Y,Z):- Z is X + Y.
   

   s1/3 je vícesměrný - umí sčítat, odečítat, generovat součty, ale pracuje jen s nezápornými celými čísly
   s2/3 umí pouze sčítat, ale také záporná a reálná čísla

3. Domácí úkol: upravte následující predikát s aritmetikou na vícesměrný (využijte některé metalogické predikáty pro testování "typů" argumentů, např. var/1, nonvar/1, number/1, integer/1 , definice těchto vestavěných predikátů najdete zde)

   soucet(X,Y,Z):- Z is X+Y.
   

• 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),
  • proč neuspěje dotaz
    ?- X=2, sin(X) is sin(2).
  • za jakých předpokladů uspějí tyto cíle X=Y, X==Y, X=:=Y,
  • a umíte odvodit pomocí substitučních rovnic odpovedi na dotazy suma(X,s(0),Z) a suma(s(0),X,Z).

^