Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:miw:miw08_rbs_back [2008/05/20 15:41] gjn |
pl:miw:miw08_rbs_back [2019/06/27 15:50] (aktualna) |
====== Opis ====== | ====== Opis ====== |
| __**Projekt zakończony**__ |
| |
Dawid, Zwoźniak, <david_z@poczta.fm> | Dawid, Zwoźniak, <david_z@poczta.fm> |
| |
Przegląd metodologii reprezentacji reguł dla wnioskowania w tył (wstecz). Należy szczególnie uwzględnić reprezentacje graficzne oraz zwrócić uwagę na: przejrzystość reguł, gęstość reprezentowanej informacji. | Przegląd metodologii reprezentacji reguł dla wnioskowania w tył (wstecz). Należy szczególnie uwzględnić reprezentacje graficzne oraz zwrócić uwagę na: przejrzystość reguł, gęstość reprezentowanej informacji. |
| |
| |
====== Spotkania ====== | |
===== 080304 ===== | |
przydzielenie projektu | |
| |
===== 080311 ===== | |
planowane konsultacje | |
| |
| |
===== 080318 ===== | |
? | |
| |
===== 080527 ===== | |
| |
====== Projekt ====== | ====== Projekt ====== |
| |
| |
| ====== WSTĘP ====== |
Ekspertowy system regułowy składa się z bazy danych, zawierającej pewne ustalone fakty i reguły służące do wywnioskowywania nowych faktów oraz interpetera reguł, sterującego procesem wnioskowań. | Ekspertowy system regułowy składa się z bazy danych, zawierającej pewne ustalone fakty i reguły służące do wywnioskowywania nowych faktów oraz interpetera reguł, sterującego procesem wnioskowań. |
| |
Wnioskowanie wstecz zostało zastosowane, między innymi, w interpreterach PROLOG-u. | Wnioskowanie wstecz zostało zastosowane, między innymi, w interpreterach PROLOG-u. |
| |
Reprezentacja wiedzy: | |
| |
1.Reguły decyzyjne (Decision Rules) | ======== SOFTWARE VISUALIZATION ======= |
najbardziej podstawowa forma przedstawiania reguł to: | |
reguła: fakt1 ^ fakt2 ^ ... ^ faktn → konkluzja | |
bardziej rozbudowana forma może mieć postać: | |
reguła: fakt1 ^ fakt2 ^ ... ^ faktn → konkluzja1 ^ konkluzja2 ^ ... ^ konkluzjan | |
| |
2.Tabele decyzyjne (Decision Tables) | Celem projektu było zbadanie metodologii reprezentacji wiedzy w systemach regułowych z wnioskowaniem wstecz, a konkretnie o sposób wizualizacji wiedzy. |
tabele decyzyjne mają postać: | |
| |
http://student.uci.agh.edu.pl/~zwozniak/rbs/tabela.jpg | |
| |
zaletą tabeli jest ich prostota i łatwość ich interpretacji, wadą natomiast jest to, | W projekcie skupiono się na odszukaniu projektów wizualizaji reprezentacji wiedzy w PROLOG-u. |
że klasyczne tabele są ograniczone do binarnej logiki. | |
| |
3.Drzewa decyzyjne (Decision Trees) | Znaleziono następujące programy: |
Reprezentacja wiedzy przy pomocy drzewa jest czytelna, łatwa do użycia i zrozumienia. | * PPVL (Prolog Program Visualization Laboratory) |
Reprezentacja przy pomocy drzewa wygląda następująco: | * TPM (Transparent Prolog Machine) |
| * Tools for Software Visualization – SVT (Semantic Visualization Tools) and Vmax |
| * VPP (Visual Programming in Prolog) |
| |
http://student.uci.agh.edu.pl/~zwozniak/rbs/tree.jpg | |
| |
Korzeń drzewa jest węzłem wejściowym. Do każdego węzła dołączone są gałęzie. | |
Koła reprezentują akcje. | |
Prostokąty reprezentują atrybuty. | |
Równoległoboki reprezentują relacje i wartości | |
| |
| |
4.Grafy (Graphs) | |
Używana w sztucznej inteligencji teoria grafów, opisująca pewien rodzaj abstrakcyjnych danych. Graf składa się z węzłów, które są zwykle opisane oraz krawędzi. Tak utworzona sieć jest grafem skierowanym z numerycznymi wartościami przypisanymi do krawędzi. | |
| |
5.Grafy koncepcyjne (Conceptual Graph) | |
W grafie koncepcyjnym węzły są koncepcyjnymi zależnościami. Każda koncepcja jest szczególną instancją koncepcyjnego typu. Każdy graf reprezentuje pojedynczą formułę. | |
| |
6.Ramki (Frames) | |
7.Model obiektowo-zorientowany (Object-oriented model) | |
8.Sieci symantyczne (Semantics Network) | |
| |
| ======= PPVL (Prolog Program Visualization Laboratory) ========= |
| |
| PPVL jest projektem który służy do wizualizacji wiedzy Prolog-u. Łączy w sobie kilka programów do wizualizacji - SV. |
| Są to: |
| * Spy (Byrd, 1980) |
| * PTP (Prolog Trace Package) |
| * TPM (Transparent Prolog Machine) |
| * TTT (Textual Tree Tracer) |
| |
| W środowisku PPVL każdy wymieniony wyżej SV system ma podobny interfejs i nawigacje. |
| |
| Środowisko zostało stworzone w Macprolog wersji 4.5 i uruchamiane na Macintosh system 7.1 |
| |
| Spy, PTP i TTT zostały w pełni zaimplementowane. Natomiast TPM zostało zaimportowane i później zmodyfikowane aby umożliwić integracje z PPVL (nawigacje i zapisywanie). |
| PPVL posiada wiele zalet nad zaimplementowanymi systemami osobno, między innymi zapewnia identyczny interfejs dla wszystkich systemów. |
| |
| == Spy (Byrd, 1980) == |
| |
| Spy jest krokowym, liniowym i tekstowym systemem śledzenia wykonywania programu, który używa Byrd Box model do uruchamiania programu. Model używa proceduralnej interpretacji logiki. |
| |
| Początek klauzuli jest klasyfikowany jako procedura, natomiast koniec klauzuli jedną lub więcej sub procedur. |
| Każda procedura lub sub procedura może mieć jeden z czterech stanów: |
| * call |
| * exit |
| * fail |
| * redo |
| |
| Wywołanie procedury jest klasyfikowane jako call, jeśli jest zakończone sukcesem jest kończone exit, jeśli nie to fail. Procedura ponownego próbowania lub wstecznego śledzenia jest pokazywana jako redo. |
| |
| Przykładowy program: |
| |
| ''p(X) :- q(X), r(X).'' |
| |
| ''q(a).'' |
| |
| ''q(b).'' |
| |
| ''r(b).'' |
| |
| '':- p(What).'' |
| |
| |
| Spy - śledzenie wykonywania przykładowego programu: |
| |
| ''call p(_1)'' |
| |
| ''UNIFY 1 []'' |
| |
| ''call q(_1)'' |
| |
| ''UNIFY 1'' |
| |
| ''exit q(a)'' |
| |
| ''call r(a)'' |
| |
| ''fail r(a)'' |
| |
| ''redo q(a)'' |
| |
| ''UNIFY 2'' |
| |
| ''exit q(b)'' |
| |
| ''call r(b)'' |
| |
| ''UNIFY 1'' |
| |
| ''exit r(b)'' |
| |
| ''exit p(b)'' |
| |
| |
| == PTP (Prolog Trace Package) == |
| |
| PTP został stworzony przez Eisenstadt (1984) w celu zapewnienia większej ilości detali i bardziej czytelnego przeglądanie uruchamiania programów Prologu, niż w Spy. |
| PTP obsługuje 19 różnych stanów uruchamiania (Spy tylko 4). Również wyróżnia osiągnięcie celu i klauzuli w programie, które były wykorzystywane do osiągnięcia tego celu, poprzez używanie różnych symboli dla wchodzenia i wychodzenia z klauzuli i osiągniętego celu. |
| |
| |
| PTP - reprezentacja przykładowego programu: |
| ''1: ? p(_1) |
| |
| 2: > p(_1) [1] |
| |
| 3: ? q(_1) |
| |
| 4: +*q(a) [1] |
| |
| 5: ? r(a) |
| |
| 6: -~r(a) |
| |
| 7: ^ q(a) |
| |
| 8: < q(a) [1] |
| |
| 9: +*q(b) [2] |
| |
| 10: ? r(b) |
| |
| 11: +*r(b) [1] |
| |
| 12: + p(b) [1]'' |
| |
| |
| == TPM (Transparent Prolog Machine) == |
| |
| TPM wykorzystuje AND/OR model drzewa dla wykonywania programu Prologu. Został stworzony przez Eisenstadt and Brayshaw, 1988; Brayshaw and Eisenstadt, 1991. |
| Opis TPM jest przedstawiony jako osobne narzędzie do wizualizacji. |
| |
| == TTT (Textual Tree Tracer)== |
| |
| TTT ma zasadniczo podobny model jak TPM, jednak używa tekstowej reprezentacji drzewa prez co dostarcza pojedynczego widoku uruchamiania programu. |
| Został stworzony przez Taylor et al, 1991. |
| |
| W przeciwieństwie do liniowych tekstowych programów śledzących wykonywanie programu takich jak Spy i PTP, bieżąca informacja określająca związek z poprzednio osiągniętym celem jest wyświetlana z lub nad poprzednią informacją. To utrzymuje wszystkie powiązane informacje poszczególnych celów w jednym miejscu. |
| |
| Siedem symboli relacji klauzul jest zaimplementowanych. Zmienne powiązane z historią celu są wyświetlane bezpośrednio pod nim. |
| |
| |
| TTT- reprezentacja przykładowego programu: |
| |
| ''>>>1: p(What) 1S |
| |
| |1 What = b |
| |
| ***2: q(What) 1SF/2S |
| |
| |1 What ≠ a |
| |
| |2 What = b |
| |
| ***3: r(a) Fm |
| |
| ***4: r(b) 1S'' |
| |
| |
| |
| |
| |
| |
| ====== ISVL (The Internet Software Visualization Laboratory) ======== |
| |
| ISVL jest projektem, który miał na celu pomoc studentom w rozumieniu uruchamianych programów napisanych w Prolog-u, poprzez internet. |
| Projekt ten wywiązał się jakby z PPVL, jednak zaimplementowano w nim jedynie TPM. |
| |
| Demonstracje działania ISVL można zobaczyc na stronie: |
| |
| [[http://www-jime.open.ac.uk/97/1/java/isvl-09.html|http://www-jime.open.ac.uk/97/1/java/isvl-09.html]] |
| |
| |
| ======= TPM (Transparent Prolog Machine) =============== |
| |
| TPM jest narzędziem do wizualizacji i animacji uruchamianych programów napisanych w Prologu. Stworzony zarówno dla początkujących jak i zaawansowanych programistów Prologu, zapewnia wierną reprezentację (w zwolnionym tempie) działania wewnętrznego interpretera Prologu, jak również umożliwia wysokiej prędkości wizualny podgląd uruchamianego programu. |
| |
| Bieżące wersje umożliwiają używanie: textbook diagrams, animacji video oraz implementacji graficznych stacji roboczych. |
| |
| System dodatkowo umożliwia tworzenie użytkownikowi widoków śledzonych programów . |
| |
| Model: |
| |
| {{:pl:miw:miw08_rbs_back:tpm_model.jpg|:pl:miw:miw08_rbs_back:tpm_model.jpg}} |
| |
| Akcja: |
| |
| {{:pl:miw:miw08_rbs_back:tpm_action.jpg|:pl:miw:miw08_rbs_back:tpm_action.jpg}} |
| |
| Granulacja danych: |
| |
| {{:pl:miw:miw08_rbs_back:tpm_gran.jpg|:pl:miw:miw08_rbs_back:tpm_gran.jpg}} |
| |
| |
| Podgląd ogólny widoku uruchamiania programu Prologu. |
| |
| {{:pl:miw:miw08_rbs_back:tpm_1.jpg|:pl:miw:miw08_rbs_back:tpm_1.jpg}} |
| |
| Ten sam widok z bliska |
| |
| {{:pl:miw:miw08_rbs_back:tpm_2.jpg|:pl:miw:miw08_rbs_back:tpm_2.jpg}} |
| |
| |
| Projekt powstawal w latach 1983-1988 w Open University and Expert Systems Ltd. |
| TPM jest dostepny jako komercyjny produkt (Expert Systems Ltd.) uruchamiany na graficznych stacjach roboczych systemu UNIX. |
| Powstała również wersja uczelniana na platforme Mac. |
| |
| |
| |
| |
| ======= Tools for Software Visualization – SVT (Semantic Visualization Tools) and Vmax ========= |
| |
| System SVT dostarcza strukturę dla SV (Software Visualization) nazywana Vmax. Kod źródłowy i uruchamiane dane są analizowane w tym systemie poprzez język Prolog, co zapewnia dostęp do informacji o strukturze programu i uruchomionych w nim danych w szerokim zakresie połączonych widoków. Środowisko SVT oraz widok programu użytkownika został napisany w Javie. |
| |
| SVT jest potężnym narzędziem który umożliwia wizualizację programów napisanych w różnych językach oraz wszelkiego typu diagramów. |
| |
| Skupiono się jednak na możliwościach SVT do wizualizaji wiedzy i programów w Prolog-u. |
| |
| Vmax może wyświetlać i edytować programy Prolog-u jako wizualne języki (visual languages). To pokazuje potencjalne możliwości SVT dla visual programming. |
| |
| Klauzula Prologu w SVT wygląda następująco: |
| ''user_clause(ClauseId, Clause)'' |
| |
| gdzie ClauseId jest niepowtarzalnym identyfikatorem klauzuli, a Clause jest struktura klauzuli. |
| |
| Aktualnie nie ma zewnętrznej tekstowej reprezentacji Prologu. |
| |
| Klauzule które zdefiniuje użytkownik mogą być przeglądane. |
| |
| Przykładowy ekran widoku predykatów: |
| |
| {{:pl:miw:miw08_rbs_back:vmax1.jpg|:pl:miw:miw08_rbs_back:vmax1.jpg}} |
| |
| Przykładowy ekran widoku klauzuli: |
| |
| {{:pl:miw:miw08_rbs_back:vmax2.jpg|:pl:miw:miw08_rbs_back:vmax2.jpg}} |
| |
| Struktura klauzuli może być vizualizowana na różne sposoby. Przedstawia to rysunek poniżej: |
| |
| {{:pl:miw:miw08_rbs_back:vmax3.jpg|:pl:miw:miw08_rbs_back:vmax3.jpg}} |
| |
| Vmax umożliwia również wizualizacji klauzul bardzo podobnie do TPM, co można zobaczyć na rysunku: |
| |
| {{:pl:miw:miw08_rbs_back:vmax4.jpg|:pl:miw:miw08_rbs_back:vmax4.jpg}} |
| |
| Vmax daje możliwość edycji klauzul na różne sposoby zarówno tekstowo jak i graficznie. Jednak zmiany w trybie graficznym nie są zapisywane do kodu źródłowego, dlatego jest to mało użyteczne. Lepszym rozwiązaniem w tym przypadku jest edycja kodu źródła programu. |
| |
| |
| |
| |
| ======== VPP (Visual Programming in Prolog) i VPE (Visual Program Execution)================== |
| |
| Komputerowe środowisko jakim jest VPP zostało stworzone aby wspomagać programowanie w Prolog-u przy wykorzystaniu graficznego interfejsu, który jest czytelniejszy dla początkujących programistów. |
| |
| Visual Programming to dwie różne eksperymentalne implementacje: |
| - Visual Programming (VPP) |
| - wizualizacja uruchamiania (VPE) |
| |
| W źródłach do jakich można dotrzeć VPE jest opisywane jeszcze w fazie konstrukcji. Działa na podobnej zasadzie jak TPM, jednak w przeciwieństwie do TPM ma dopełniający system VPP (który używa w zasadzie tych samych formalizmów) w celu zapewnienia pełną funkcjonalność dla visual programming. Zależności są bardziej wyeksponowane w VPE niż w TPM. |
| |
| Wyidealizowany widok środowiska VPP dla visual programming przedstawia rysunek poniżej: |
| |
| {{:pl:miw:miw08_rbs_back:vpp1.jpg|:pl:miw:miw08_rbs_back:vpp1.jpg}} |
| |
| Relacja w VPP jest przedstawiana następująco: |
| |
| {{:pl:miw:miw08_rbs_back:vpp2.jpg|:pl:miw:miw08_rbs_back:vpp2.jpg}} |
| |
| Klauzula w następujący sposób: |
| |
| {{:pl:miw:miw08_rbs_back:vpp3.jpg|:pl:miw:miw08_rbs_back:vpp3.jpg}} |
| |
| Reguła następująco: |
| |
| {{:pl:miw:miw08_rbs_back:vpp4.jpg|:pl:miw:miw08_rbs_back:vpp4.jpg}} |
| |
| |
| Natomiast rysunek poniżej przedstawia kompletny ślad uruchamiania prostego programu w VPE: |
| |
| {{:pl:miw:miw08_rbs_back:vpp5.jpg|:pl:miw:miw08_rbs_back:vpp5.jpg}} |
| |
| Poniższy rysunek pokazuje jeden ze sposobów reprezentowania list relacji w VPP i VPE: |
| |
| {{:pl:miw:miw08_rbs_back:vpp6.jpg|:pl:miw:miw08_rbs_back:vpp6.jpg}} |
| |
| Aktualnie są dwie prototypowe implementacje VPP: |
| * Philip |
| * Treglow |
| |
| |
| |
| ====== Podsumowanie ====== |
| |
| Próby wizualizacji programów napisanych w Prologu były tworzone juz na początku lat 80-tych. |
| Powstało kilka projektów/systemów, które dają możliwość wizualizacji i śledzenia wykonywania programów Prologu, jednak nie można żadnego z nich zdobyć. |
| Są to albo wersje komercyjne (TPM na UNIX-a, SVT i Vmax) lub akademickie na system MAC (TPM, PPVL, ale tez nie udało się ich odnaleźć na sieci). |
| |
| Większość z tych systemów podczas graficznej wizualizacji korzysta ciągle z tego samego, czyli TPM, a nie udało się odnaleźć bardziej szczegółowego opisu działania. |
| Wydana została książka o TPM (koszt 150$ + przesyłka) a wszystkie inne informacje na sieci są bardzo pobieżne i piszą ciągle o tym samym (w skrócie jak to ladnie sobie można robić wizualizacje śledzenia programów w Prolog-u przy pomocy TPM). |
| |
| Projekt niestety nie jest oparty na własnych próbach wykonywania programów z powodu braku dostępu do systemów SV dla Prologu. Zatem zostały opisane i przetłumaczone informacje jakie udało mi się odnaleźć w sieci. |
| |
| Opisanie tych programów było bardzo trudne. Ciężko pisać o czymś czego nie można wypróbować opierając sie tylko na bardzo ogólnych opisach. |
| |
====== Sprawozdanie ====== | ====== Sprawozdanie ====== |
| |
| |
| |
====== Materiały ====== | ====== Materiały ====== |
| |
| {{:pl:miw:miw08_rbs_back:005.pdf|:pl:miw:miw08_rbs_back:005.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:declarative-debugging-with-the.pdf|:pl:miw:miw08_rbs_back:declarative-debugging-with-the.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:domingue-97-1.pdf|:pl:miw:miw08_rbs_back:domingue-97-1.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:iee_20vis_20prolog_2091.pdf|:pl:miw:miw08_rbs_back:iee_20vis_20prolog_2091.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:mulholland97incorporating.pdf|:pl:miw:miw08_rbs_back:mulholland97incorporating.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:ppigvisprologfixed.pdf|:pl:miw:miw08_rbs_back:ppigvisprologfixed.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:tbpa91.pdf|:pl:miw:miw08_rbs_back:tbpa91.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:ucam-cl-tr-511.pdf|:pl:miw:miw08_rbs_back:ucam-cl-tr-511.pdf}} |
| |
| {{:pl:miw:miw08_rbs_back:visandor-iclp93.pdf|:pl:miw:miw08_rbs_back:visandor-iclp93.pdf}} |
| |
| |
| |
| [[http://citeseer.ist.psu.edu/cache/papers/cs/20963/http:zSzzSzkmi.open.ac.ukzSzmarczSzpaperszSzIJMMS-91.pdf/brayshaw91practical.pdf|http://citeseer.ist.psu.edu/cache/papers/cs/20963/http:zSzzSzkmi.open.ac.ukzSzmarczSzpaperszSzIJMMS-91.pdf/brayshaw91practical.pdf]] |
| |
| [[http://kmi.open.ac.uk/kmi-misc/tpm/tpm.html|http://kmi.open.ac.uk/kmi-misc/tpm/tpm.html]] |
| |
| [[http://www.amazon.com/Transparent-Prolog-Machine-Visualizing-Programs/dp/0792314476|http://www.amazon.com/Transparent-Prolog-Machine-Visualizing-Programs/dp/0792314476]] |
| |
| [[http://www.cc.gatech.edu/classes/cs7390_98_winter/talks/logic/topic3.html|http://www.cc.gatech.edu/classes/cs7390_98_winter/talks/logic/topic3.html]] |
| |
| [[http://citeseer.ist.psu.edu/cache/papers/cs/6324/http:zSzzSzwww.cs.usask.cazSzprojectszSzenvlopzSzWLPEzSz8WLPEzSzproceedingszSzmulholland.pdf/mulholland97incorporating.pdf|http://citeseer.ist.psu.edu/cache/papers/cs/6324/http:zSzzSzwww.cs.usask.cazSzprojectszSzenvlopzSzWLPEzSz8WLPEzSzproceedingszSzmulholland.pdf/mulholland97incorporating.pdf]] |
| |
| [[http://citeseer.ist.psu.edu/cache/papers/cs/150/ftp:zSzzSzfrost.open.ac.ukzSzpubzSzpaulmzSzMul-HCRL107.pdf/mulholland93evaluating.pdf|http://citeseer.ist.psu.edu/cache/papers/cs/150/ftp:zSzzSzfrost.open.ac.ukzSzpubzSzpaulmzSzMul-HCRL107.pdf/mulholland93evaluating.pdf]] |
| |
| [[http://books.google.pl/books?id=ATqiSr7QE24C&dq=Transparent+Prolog+Machine&pg=PP1&ots=-V8A0bzMyv&sig=9x21p9xwmyNquvVrCXlOcsBzQmA&hl=pl&sa=X&oi=book_result&resnum=1&ct=result#PPP1,M1|http://books.google.pl/books?id=ATqiSr7QE24C&dq=Transparent+Prolog+Machine&pg=PP1&ots=-V8A0bzMyv&sig=9x21p9xwmyNquvVrCXlOcsBzQmA&hl=pl&sa=X&oi=book_result&resnum=1&ct=result#PPP1,M1]] |
| |
| [[http://citeseer.ist.psu.edu/cache/papers/cs/27638/http:zSzzSzwww.cl.cam.ac.ukzSzTechReportszSzUCAM-CL-TR-511.pdf/grant99software.pdf|http://citeseer.ist.psu.edu/cache/papers/cs/27638/http:zSzzSzwww.cl.cam.ac.ukzSzTechReportszSzUCAM-CL-TR-511.pdf/grant99software.pdf]] |
| |
| [[http://www-jime.open.ac.uk/97/1/isvl-01.html|http://www-jime.open.ac.uk/97/1/isvl-01.html]] |
| |
| |
| |