Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:miw:miw08_rbs_back [2008/07/11 14:16] gjn |
pl:miw:miw08_rbs_back [2008/07/14 09:58] miw |
====== Opis ====== | |
__**Projekt zakończony**__ | |
| |
Dawid, Zwoźniak, <david_z@poczta.fm> | |
| |
RBS_Back | |
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 ===== | |
| |
| |
? | |
| |
===== 080626 ===== | |
? | |
| |
| |
====== 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ń. | |
| |
W systemach ekspertowych wykorzystuje się 3 rodzaje wnioskowania: | |
- w przód | |
- wstecz | |
- mieszane | |
| |
Wnioskowanie wstecz przebiega w odwrotną stronę niż wnioskowanie w przód. Ogólnie polega ono na wykazaniu prawdziwości hipotezy głównej na postawie prawdziwości przesłanek. Jeśli nie wiemy, czy jakaś przesłanka jest prawdziwa, to traktujemy tę przesłankę jako nową hipotezę i próbujemy ją wykazać. Jeżeli w wyniku takiego postępowania zostanie wreszcie znaleziona reguła, której wszy¬stkie przesłanki są prawdziwe, to konkluzja tej reguły jest prawdziwa. Na pod¬stawie tej konkluzji dowodzi się następną regułę, której przesłanka nie była po¬przednio znana itd. Postawiona hipoteza jest prawdziwa, jeśli wszystkie rozważa¬ne przesłanki dadzą się wykazać. | |
| |
Cel -> reguły -> fakty | |
| |
Wnioskowanie wstecz różni się od wnioskowania w przód m.in. tym, że generuje mniejszą liczbę nowych faktów oraz uniemożliwia równoczesne dowodzenie kilku hipotez. Ogólnie w typowych zastosowaniach wnioskowanie wstecz jest efektywniejsze i bardziej rozpowszechnione. Istotne jest także to, że przy wnioskowaniu wstecz czas oczekiwania na osiągnięcie rozwiązania postawionej hipotezy jest w wielu przypadkach dużo krótszy niż przy wnioskowaniu w przód. | |
| |
| |
Wnioskowanie wstecz zostało zastosowane, między innymi, w interpreterach PROLOG-u. | |
| |
| |
======== SOFTWARE VISUALIZATION ======= | |
| |
Celem projektu było zbadanie metodologii reprezentacji wiedzy w systemach regułowych z wnioskowaniem wstecz, a konkretnie o sposób wizualizacji wiedzy. | |
| |
W projekcie skupiono się na odszukaniu projektów wizualizaji reprezentacji wiedzy w PROLOG-u. | |
| |
Znaleziono następujące programy: | |
* PPVL (Prolog Program Visualization Laboratory) | |
* TPM (Transparent Prolog Machine) | |
* Tools for Software Visualization – SVT (Semantic Visualization Tools) and Vmax | |
* VPP (Visual Programming in Prolog) | |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
======= 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 ====== | |
| |
| |
====== 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}} | |