prolog.tex

\documentclass[blue]{beamer}
\usetheme{Warsaw}
\usepackage{polski}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{listings}
\usepackage{tikz}
\usepackage{url}
\author{matma6 (tech. Michał Gabor)}
\title{Wyraź wszystko w Prologu}
\date{26 marca 2013 r.}
\lstset{language=Prolog}
%to coś dodaje numery slajdów
\newcommand*\oldmacro{}%
\let\oldmacro\insertshorttitle%
\renewcommand*\insertshorttitle{%
  \oldmacro\hfill%
  \insertframenumber\,/\,\inserttotalframenumber}
%slajd tytułowy
\newcommand{\tytul}[1]{\begin{frame}\begin{center}\begin{Huge}#1\end{Huge}\end{center}\end{frame}}
\newcommand{\tytulprz}[2]{\begin{frame}\begin{center}\begin{Huge}Ciekawe przykłady\end{Huge}

\hspace{20pt}

\begin{huge}#1\end{huge}

\hspace{10pt}

\begin{large}#2\end{large}\end{center}\end{frame}}
\begin{document}
\begin{frame}
\titlepage
\end{frame}
\begin{frame}{Nasze motto}
\textit{,,Chodzi mi o to, aby język giętki\\Powiedział wszystko, co pomyśli głowa:\\A czasem był jak piorun jasny, prędki,\\A czasem smutny jako pieśń stepowa,\\A czasem jako skarga nimfy miętki,\\A czasem piękny jak aniołów mowa...\\Aby przeleciał wszystka ducha skrzydłem.\\Strofa być winna taktem, nie wędzidłem.''}
\begin{flushright}
J. Słowacki
\end{flushright}
\end{frame}
\begin{frame}
\begin{small}
\tableofcontents
\end{small}
\end{frame}
\section{Co to jest Prolog}
\tytul{Co to jest Prolog}
\subsection{Fakty}
\begin{frame}{Fakty}
\begin{itemize}
\item Francja, Marsylia, rok 1972
\item Alain Colmerauer i Philippe Roussel
\item Programowanie w logice (PROgrammation en LOGique)
\end{itemize}
\end{frame}
\subsection{Implementacje i instalacja}
\begin{frame}{Implementacje}
Istnieje wiele implementacji Prologu.
\begin{itemize}
\item SWI-Prolog
\item YAP
\item GNU Prolog
\item SICStus Prolog
\item Visual Prolog
\item ...
\end{itemize}
\end{frame}
\begin{frame}{SWI-Prolog}
Używam SWI-Prolog.

Cechy:
\begin{itemize}
\item LGPL/GPL
\item CLP
\item XPCE
\item Serwer WWW
\item Doskonała dokumentacja
\item ...
\end{itemize}
\end{frame}
\begin{frame}[fragile]{Instalacja}
\begin{description}
\item[Arch Linux] posiada SWI-Prolog w AURze (np.~\verb+yaourt -S swi-prolog+)
\item[Debian] ma SWI-Prolog w repozytorium (np.~\verb+sudo apt-get install swi-prolog+)
\item[Inne GNU/Linuksy] paczka w repozytorium lub kompilacja ze~źródeł do pobrania ze strony \url{http://swi-prolog.org/}
\item[MacOS X] paczka jest do pobrania ze strony \url{http://swi-prolog.org/}
\item[Windows] paczka jest do pobrania ze strony \url{http://swi-prolog.org/}
\end{description}

W GNU/Linuksie i Mac OS X pojawia się wtedy polecenie \verb+swipl+. W Windowsie jest ikona sowy w menu Start.
\end{frame}
\subsection{Paradygmat logiczny}
\begin{frame}{Paradygmat logiczny}
\begin{description}
\item[Imperatywnie] wykonujemy instrukcje
\item[Funkcyjnie] obliczamy wartość funkcji
\item[Logicznie] pytamy o relacje
\end{description}
\end{frame}
\begin{frame}{Funkcja a relacja}
\begin{center}
\begin{tikzpicture}
\draw (1, 3) -- (4, 3);
\draw (1, 2) -- (4, 3);
\draw (1, 2) -- (4, 1);
\draw (1, 2) ellipse (1 and 2);
\draw (1, 3) node [fill=white] {a};
\draw (1, 2) node [fill=white] {b};
\draw (1, 1) node [fill=white] {c};
\draw (4, 2) ellipse (1 and 2);
\draw (4, 3) node [fill=white] {d};
\draw (4, 1) node [fill=white] {e};
\end{tikzpicture}
\end{center}
\uncover<2->{
Relacja $\rho$ to nie funkcja:
\begin{description}
\item<3->[$\rho(a) = d$] ok...
\item<4->[$\rho(b) = ?$] dwie wartości
\item<5->[$\rho(c) = ?$] brak wartości
\end{description}}
\end{frame}
\begin{frame}[fragile]{W Prologu}
\begin{lstlisting}
ro(a, d).
ro(b, d).
ro(b, e).
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{Czas na przykład z życia - sinus :)}
\lstinputlisting{zrodla/lubi.pl}
\end{frame}
\section{Podstawy}
\tytul{Podstawy}
\subsection{Składnia}
\begin{frame}[fragile]{Komentarze, atomy i zmienne}
\begin{description}
\item[Komentarz] zaczyna się od \%.
\item[Atom] zaczyna się z małej litery.
\item[Zmienna] zaczyna się z dużej litery.\
\end{description}
\begin{lstlisting}
%atomy
jan
kot
pies

%Zmienne
Lista
X
N1
ODP
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{Termy}
\begin{enumerate}
\item Atom to term
\item Liczba to term
\item Zmienna to term
\item Termem jest też nazwana krotka postaci:
\begin{lstlisting}
atom(term1, term2, term3, ...)
\end{lstlisting}
\end{enumerate}
\end{frame}
\begin{frame}[fragile]{Źródło to nie REPL}
\begin{columns}
\begin{column}{.5\linewidth}
Źródło to baza faktów!

\lstinputlisting{zrodla/lubi.pl}
\end{column}
\begin{column}{.5\linewidth}
REPL służy do zadawania pytań!

\begin{lstlisting}
lubi(jan, koty).
lubi(jan, Co).
lubi(X, Y).
\end{lstlisting}
\end{column}
\end{columns}
Zarówno fakty, jak i pytania kończymy kropką.
\end{frame}
\subsection{Zmienne}
\begin{frame}[fragile]{Zmienne}
Prolog ma zmienne jednokrotnego przypisania:
\begin{lstlisting}
?- X = a.
X = a.

?- X = a, X = b.
false.

?- f(X, X) = f(Y, Z).
X = Y, Y = Z.

?- f(X, g(X)) = f(g(Y), Y).
X = Y, Y = g(g(Y)).
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{Zmienne związane i wolne}
Jeśli zmienna ma wartość to jest związana (ang. grounded).

Zmienne mogące przyjąć różne wartości to zmienne wolne.
\begin{lstlisting}
?- X = 2, ground(X).
X = 2.

?- X = 2, ground(Y).
false.
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{Dopasowanie do wzorca}
Prolog wszędzie automatycznie dopasowuje się do wzorca.
\begin{lstlisting}
?- X = f(a, b).
X = f(a, b).

?- f(X, Y) = f(a, b).
X = a,
Y = b.

ksiazka(autor(jan, kowalski), wroclaw, 2013).
ksiazka(autor(stefan, nowak), warszawa, 1983).

?- ksiazka(_, _, Rok).
Rok = 2013 ;
Rok = 1983.
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{Zmienne a dane}
W Prologu zmienna może być częścią danej.
\begin{lstlisting}
?- f(a, X) = f(Y, b).
X = b,
Y = a.

%mozliwe termy cykliczne

?- X = f(Y), Y = g(X).
X = f(g(X)),
Y = g(X).
\end{lstlisting}
\end{frame}
\subsection{Liczby i wyrażenia}
\begin{frame}[fragile]{Operatory}
Prolog ma zdefiniowane operatory. Można dodać nowe: \verb+op/3+.
\begin{lstlisting}
?- X = '+'(A, B).
X = A+B.

?- nazwa(arg1, arg2, arg3) =.. L.
L = [nazwa, arg1, arg2, arg3].

?- (a, X) = (Y, b).
X = b,
Y = a.

?- (a, b, c) =.. L.
L = [',', a, (b, c)].
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{2+2 to nie 4}
Prolog nie dokonuje ewaluacji automatycznie.

2+2 to wyrażenie

4 to liczba

Wyrażenie nie jest liczbą.

Żeby coś policzyć, używamy is.

\begin{lstlisting}
?- X = 2+2.
X = 2+2.

?- X is 2+2.
X = 4.
\end{lstlisting}
\end{frame}
\subsection{Listy i reguły}
\begin{frame}[fragile]{Definicja listy}
\begin{enumerate}
\item Lista pusta \verb+[]+ to lista
\item Para złożona z elementu i listy to lista
\end{enumerate}

Jaki symbol ,,spina'' listę?

\uncover<2>{Podpowiedź: A jak jest w Lispie?}

\uncover<3>{Kropka}
\end{frame}
\begin{frame}[fragile]{Listy - przykłady}
\begin{lstlisting}
?- [a, b, c] = L, L = [X| Y], write_canonical(L).
'.'(a,'.'(b,'.'(c,[])))
L = [a, b, c],
X = a,
Y = [b, c].

?- X = .(a, .(b, [])).
X = [a, b].

?- length(X, 3).
X = [_G1106, _G1109, _G1112].

?- append([a, b, c], X, Y).
Y = [a, b, c | X].
\end{lstlisting}
\end{frame}
\begin{frame}[fragile]{Długość listy}
\begin{columns}
\begin{column}{.5\linewidth}
\only<1>{
\begin{block}{Myśl logicznie!}
Długość listy pustej to 0.

Długość listy niepustej to długość ogona + 1.
\begin{center}inaczej\end{center}
Długość niepustej listy to N + 1 wtedy, gdy długość ogona to N.
\end{block}
}
\only<2>{
\begin{block}{Składnia reguły}
wniosek :- warunki.

Warunki oddzielamy przecinkiem, który oznacza koniunkcję zdań (spójnik i).
\end{block}
}
\only<3-4>{
\begin{block}{Zagadka}
Co jest nie tak z tym kodem?

\uncover<4>{\alert<4>{Nie użyto rekursji ogonowej.}}
\end{block}
}
\end{column}
\begin{column}{.5\linewidth}
\begin{lstlisting}
dl([], 0).

dl([_|T], N1) :-
    dl(T, N),
    N1 is N+1.
\end{lstlisting}
\end{column}
\end{columns}
\end{frame}
\begin{frame}[fragile]{Wersja optymalna z rekursją ogonową}
\lstinputlisting{zrodla/dlugosc.pl}
\end{frame}
\begin{frame}[fragile]{Czas na coś ciekawego}
\lstinputlisting{zrodla/polacz.pl}
\begin{lstlisting}
?- polacz([a, b], [c, d], X).
X = [a, b, c, d].
\end{lstlisting}

Pytamy o relacje

A co Prolog na to?

\begin{lstlisting}
?- polacz(X, Y, [a,b,c]).
\end{lstlisting}
\end{frame}
\subsection{Rozwidlanie i odcięcie}
\begin{frame}[fragile]{Rozwidlanie}
W programach imperatywnych i funkcyjnych program ,,idzie'' jedną ścieżką.

W Prologu tworzone są równoległe ścieżki.

\uncover<2>{Na przykład polacz/3.}
\end{frame}
\begin{frame}[fragile]{Rozwidlanie - przykład}
\begin{lstlisting}
?- select(X, [a, b, c], L), select(Y, L, _),
	     write('Wynik: '), writeln(X+Y).
\end{lstlisting}
\begin{columns}
\begin{column}{.33\linewidth}
\begin{lstlisting}
Wynik: a+b
X = a,
L = [b, c],
Y = b ;
Wynik: a+c
X = a,
L = [b, c],
Y = c ;

\end{lstlisting}
\end{column}
\begin{column}{.33\linewidth}
\begin{lstlisting}
Wynik: b+a
X = b,
L = [a, c],
Y = a ;
Wynik: b+c
X = b,
L = [a, c],
Y = c ;

\end{lstlisting}
\end{column}
\begin{column}{.33\linewidth}
\begin{lstlisting}
Wynik: c+a
X = c,
L = [a, b],
Y = a ;
Wynik: c+b
X = c,
L = [a, b],
Y = b ;
false.
\end{lstlisting}
\end{column}
\end{columns}
\end{frame}
\begin{frame}{Rozwidlanie - schemat}
\begin{center}
\begin{tikzpicture}
\draw (4.5, 6) -- (1, 4);
\draw (4.5, 6) -- (4.5, 4);
\draw (4.5, 6) -- (8, 4);
\draw (0, 0) node [fill=white] {a+b} -- (0, 2) node [fill=white] {Y = b} -- (1, 4) node [fill= white] {X = a}
 -- (2, 2) node [fill=white] {Y = c} -- (2, 0) node [fill=white] {a+c};
\draw (3.5, 0) node [fill=white] {b+a} -- (3.5, 2) node [fill=white] {Y = a} -- (4.5, 4) node [fill= white] {X = b}
 -- (5.5, 2) node [fill=white] {Y = c} -- (5.5, 0) node [fill=white] {b+c};
\draw (7, 0) node [fill=white] {c+a} -- (7, 2) node [fill=white] {Y = a} -- (8, 4) node [fill= white] {X = c}
 -- (9, 2) node [fill=white] {Y = b} -- (9, 0) node [fill=white] {c+b};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}[fragile]{Odcięcie}
\begin{lstlisting}
?- select(X, [a, b, c], L), select(Y, L, _),
	     write('Wynik: '), Y = c, !, writeln(X+Y).
\end{lstlisting}
\end{frame}
\begin{frame}{Odcięcie - schemat}
\begin{center}
\begin{tikzpicture}
\draw (4.5, 6) -- (1, 4);
\draw (4.5, 6) -- (4.5, 4);
\draw (4.5, 6) -- (8, 4);
\draw (0, 0) node [fill=white] {fail} -- (0, 2) node [fill=white] {Y = b} -- (1, 4) node [fill= white] {X = a}
 -- (2, 2) node [fill=white] {Y = c} -- (2, 0) node [fill=white] {a+c sukces!};
\draw (4.5, 4) node [fill= white] {X = b};
\draw (8, 4) node [fill= white] {X = c};
\draw (4, 5) -- (9, 5) node [fill=white] {odcięcie};
\end{tikzpicture}
\end{center}
\end{frame}
\section{Ciekawe przykłady}
\tytul{Ciekawe przykłady}
\subsection{Listy różnicowe}
\tytulprz{Listy różnicowe}{}
\begin{frame}[fragile]{Definicja}
Lista różnicowa to lista z odjętym ogonem.
\begin{lstlisting}
[a, b, c, d] - [d]
[a, b, c | X] - X
\end{lstlisting}
\begin{enumerate}
\item Prolog nie ewaluuje, więc nie muszę definiować tego odejmowania
\item Mam daną listę [a, b, c], ale nie wiem, jaki ogon odejmę - zmienna częścią danej(!)
\item Te listy daje się (zwykle) łączyć w czasie stałym(!)
\end{enumerate}
\end{frame}
\begin{frame}[fragile]{Łączenie w czasie stałym}
Lista różnicowa to lista z odjętym ogonem.
\begin{lstlisting}
polacz(X-Y, Y-Z, X-Z).
\end{lstlisting}

Oto CAŁA implementacja.

Prolog cechuje bardzo zwięzły zapis.
\end{frame}
\subsection{Programy ,,samouczące się''}
\tytulprz{Programy ,,samouczące się''}{}
\begin{frame}{Ciąg Fibonacciego - z definicji}
\lstinputlisting{zrodla/fib1.pl}

\uncover<2>{Nieefektywne :(}
\end{frame}
\begin{frame}{Ciąg Fibonacciego - zapamiętajmy wynik}
\lstinputlisting{zrodla/fib.pl}
\end{frame}
\subsection{Zagadki}
\tytulprz{Zagadki}{}
\begin{frame}{Opis}
\textit{Zagadka pochodzi z ,,Jaki jest tytuł tej książki?'' autorstwa Raymonda Smullyana}

Wszyscy mieszkańcy pewnej wyspy są albo rycerzami (ludźmi, którzy nigdy nie kłamią) albo łotrami (ludźmi, którzy kłamią zawsze).

Wędrując po tej wyspie spotykamy trzech tubylców:

Zadaliśmy osobie A pytanie czy jest łotrem czy rycerzem ale ten odpowiedział niewyraźnie i nie zrozumieliśmy jego odpowiedzi.

Pytamy się osobę B co odpowiedział A. B odpowiada nam, że A powiedział o sobie, że jest łotrem.

Słysząc to C mówi: "Nie wierz B! To B jest łotrem!".

Kim są B i C?
\end{frame}
\begin{frame}{Kod}
\textit{Kod autorstwa dra Przemysława Kobylańskiego}
\lstinputlisting{zrodla/zagadka.pl}
\end{frame}
\begin{frame}[fragile]{Pytanie}
Pytamy się osobę B co odpowiedział A. B odpowiada nam, że A powiedział o sobie, że jest łotrem.

Słysząc to C mówi: "Nie wierz B! To B jest łotrem!".
\begin{lstlisting}
?- powiedzial(B, powiedzial(A, lotr(A))),
powiedzial(C, lotr(B)).

B = lotr,
C = rycerz.
\end{lstlisting}
\end{frame}
\subsection{Więzy}
\tytulprz{Więzy}{}
\begin{frame}{Czym są więzy}
Za pomocą więzów można zapisywać ograniczenia, np.
\begin{itemize}
\item A jest pomiędzy 0 i 9
\item A i B są różne
\end{itemize}

Przykłady podane za dokumentacją SWI-Prologu
\end{frame}
\tytulprz{Więzy}{SEND + MORE = MONEY}
\begin{frame}{SEND + MORE = MONEY}
\begin{center}
\begin{Huge}
\begin{tabular}{|p{20pt}ccccccp{20pt}|}
\hline
 & & & & & & & \\ 
 & & & S & E & N & D & \\ 
 & + &  & M & O & R & E & \\ 
\cline{2-7} 
 & & M & O & N & E & Y & \\ 
 & & & & & & & \\
\hline
\end{tabular}
\end{Huge} 
\end{center}
\end{frame}
\begin{frame}[fragile]{SEND + MORE = MONEY}
Pytanie:
\begin{lstlisting}
?- puzzle(X + Y = Z), label(X).
\end{lstlisting}
\lstinputlisting{zrodla/money.pl}
\end{frame}
\tytulprz{Więzy}{Sudoku}
\begin{frame}{Sudoku}
\lstinputlisting{zrodla/sudoku.pl}
\end{frame}
\begin{frame}{Sudoku - konkretna zagadka}
\lstinputlisting{zrodla/sudoku-def.pl}
\end{frame}
\begin{frame}[fragile]{Sudoku - rozwiązanie}
\begin{lstlisting}
?- problem(1, Rows), sudoku(Rows),
   maplist(writeln, Rows).
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[2, 4, 6, 1, 7, 3, 9, 8, 5]
[3, 5, 1, 9, 2, 8, 7, 4, 6]
[1, 2, 8, 5, 3, 7, 6, 9, 4]
[6, 3, 4, 8, 9, 2, 1, 5, 7]
[7, 9, 5, 4, 6, 1, 8, 3, 2]
[5, 1, 9, 2, 8, 6, 4, 7, 3]
[4, 7, 2, 3, 1, 9, 5, 6, 8]
[8, 6, 3, 7, 4, 5, 2, 1, 9]
Rows = [[9, 8, 7, 6, 5, 4, 3, 2|...], ... , [...|...]].
\end{lstlisting}
\end{frame}
\section{Surgunt}
\tytul{Surgunt}
\begin{frame}[fragile]{Funkcje anonimowe}
\begin{lstlisting}
F = (X -> Y -> do(Z is X+Y) -> Z)

subst([2,3], F, R)

subst([1], F, Incr)
%Incr = (Y -> do(Z is 1+Y) -> Z)
\end{lstlisting}
\end{frame}
\begin{frame}{Funkcje anonimowe - kod 1/2}
\lstinputlisting{zrodla/surgunt/anonFun1.pl}
\end{frame}
\begin{frame}{Funkcje anonimowe - kod 2/2}
\lstinputlisting{zrodla/surgunt/anonFun2.pl}
\end{frame}
\begin{frame}[fragile]{Predykaty anonimowe}
\begin{lstlisting}
%zamiast pisac
length_(X, L) :- length(L, X).
?- length(Rows, 3), maplist(length_(3), Rows).

%mozemy napisac:
%anonPred(kod, interfejs, argument)
anonPred(length(L, 3), [L], List)

maplist(anonPred(length(L, 3), [L]), Rows)

%zatem dla kazdego wiersza:
anonPred(length(L, 3), [L], Row)
\end{lstlisting}
\end{frame}
\begin{frame}{Predykaty anonimowe - kod}
\lstinputlisting{zrodla/surgunt/anonPred.pl}
\end{frame}
\begin{frame}[fragile]{Składanie}
\begin{lstlisting}
%zamiast pisac
p1(Input, X1),
p2(Arg, X1, X2),
p3(X2, Output)

%piszemy
compose(Input, [p1, p2(Arg), p3], Output)
\end{lstlisting}
\end{frame}
\begin{frame}{Składanie - kod}
\lstinputlisting{zrodla/surgunt/compose.pl}
\end{frame}
\begin{frame}
\frametitle{Więcej informacji}
\begin{itemize}
\item E. Gatnar, K. Stąpor, \textit{Prolog, język sztucznej inteligencji}, PLJ, Warszawa 1991, ISBN: 83-85190-63-5
\item W. F. Clocksin, C. S. Mellish, \textit{Prolog, programowanie}, Helion, Gliwice 2003, ISBN: 83-7197-918-5
\item Jan Wielemaker, \textit{SWI-Prolog Reference Manual 6.2.6}, \url{http://www.swi-prolog.org/download/stable/doc/SWI-Prolog-6.2.6.pdf}
\end{itemize}
\end{frame}
\begin{frame}
\begin{center}
\begin{Huge}
Dziękuję za uwagę.

Czas na pytania.

matma6 (tech. Michał Gabor)

matma6.net

matma6@matma6.net

\end{Huge}
\end{center}
\end{frame}
\end{document}