Badania podstawowe

Z Lem
Skocz do: nawigacji, wyszukiwania

Podczas prac w projekcie Loglan'82 napotkano wiele problemów. Zanim podjęto decyzję w konkretnej sprawie, formułowaliśmy problem dbając o precyzję i staraliśmy się znaleźć jego rozwiązanie.

Przykład. Zarządzanie pamięcią obiektów nie jest sprawą trywialną. Jeśli system zarządzania obiektami nie umożliwi usuwania obiektów już niepotrzebnych, to może to doprowadzić do wycieku pamieci. Zjawisko takie jest nie tylko niepożądane, lecz niebezpieczne. Z drugiej strony zezwolenie na usuwanie obiektu może prowadzić do bardzo groźnych i trudnych do wykrycia błędów tzw. wiszących referencji. Błąd taki powstaje gdy obiekt jest wartościa dwu zmiennych x i y . Polecenie: delete(y) (w jezyku C++, free(y) w Pascalu) spowoduje, że obiekt zostanie usunięty, zmienna y przyjmie wartość nil. Zmienna x utrzymuje swą poprzednią wartość sugerując, że wskazuje ona na jakiś obiekt. Po chwili może powstać jakiś nowy obiekt innego typu i pewna zmienna z może wskazywac na ten obiekt. Taka sytuacja to błąd sprzecznych informacji. Zmienna x mówi tu jest obiekt typu T, zmienna z mówi tu jest obiekt typu U. Zamieszanie powiększa się gdy twórca języka uważa, ze problem zostanie rozwiazany przez wprowadzenie odśmiecacza (ang. garbage collector). W r. 1995 powstał język Java. Jego twórcy w artykule white paper tłumaczyli: nie wolno wprowadzac do języka instrukcji delete bo w ten sposób moga pojawic się błedy wiszacych referencji. A poniewaz Java jest wyposażona w odśmiecacz, to wywołując go poleceniem gc() zawsze będziesz mógł usunąć niepotrzebne obiekty. Juz w dwa lat apóźniej w 1997 okazało się, że odśmiecacz nie może usunąć obiektu o, dla którego wcześniej starannie nie usunieto wszystkich wskazujących nań referencji. Okazało się, że zadanie takie jest nierealne. Programista chcący się pozbyc niepotrzebnego obiektu musiałby pamietac o wszystkich wskaźnikach na taki obiekt, również tych, które postały automatycznie poprzez zarządzanie strukturami danych takimijak kolejki, stosy czy drzewa. Wprowadzono więc w Javie referencje mocne i słabe. Podobnie jest w Pytonie. Nadal jednak pozostaje problem: niewielu programistów w Javie zdaje sobie sprawę z tego , że istnieja słabe referencje i jak z nich korzystać. Profesor Antoni Kreczmar sformułował problem inaczej: czy istnieje taka struktura danych, która pozwala przechowywać obiekty, wskażniki do nich i usuwać w sposób bezpieczny i efektywne obiekty wskazane przez programistę. Powyższe sformułowanie jest tylko szkicem pełnej specyfikacji wymagań. Szczegółową implementację systemu Kreczmara można znaleźć w [Kreczmar i Cioni 1984 ↓, Cioni, Kreczmar i Vitale 1989 ↓]. Analizę wymagań przeprowadziła Hanna Oktaba w rozprawie doktorskiej, zob.[] .

Nie twierdzimy, że wszyscy powinni zacząć programować w Loglanie. Dziwi jednak, że od ponad 30 lat od ukazania się publikacji G. Cioni i A. Kreczmara, żaden z nowych języków, lub nowej wersji języka już istniejącego, nie zauważył, że istnieje tanie i bezpieczne rozwiązanie problemu programowalnej dealokacji obiektów.

A oto lista problemów wraz z informacjami o znalezionych rozwiązaniach.

  • Problem programowanej, bezpiecznej dealokacji obiektów. Omówiony powyżej, zob[]
  • Problem wyznaczania klas bazowych. Klasa A może rozszerzać klasę B (inaczej, klasa A dziedziczy z klasy B). Jeśli język programowania taki jak Loglan, Java etc. dopuszcza zagnieżżanie klas, to w jednym programie może znaleźć sie wiele klas o nazwie B. Która z tych klas jest tą rozszerzaną? Problem nie jest taki trudny w Simuli'67. Nieco trudniejszy w Loglanie'82. Problem wyznaczania klasy bazowej jest dość skomplikowany w Javie, poczynając od wersji Java 1.2. Rozwiązanie problemu zawarliśy w publikacjach []. Zwracamy uwagę, że opis zawarty w Java Language Specification jest rozproszony po wielu stronach tej książki i niepełny.
  • Problem statyczne, dynamiczne, inne ... wiązanie aplikacyjnego wystąpienia identyfikatora z odpowiednią deklaracją tego indeyfikatora.
  • Problem Display Vector'a. Dostęp kodu procedury do wielkości nielokalnych nasuwa pytania jak należy obliczać adres wielkości nielokalnej? Poniewaz procedury i funkcje mogą opisywc obliczenia rekurencyjne nie mozna wyznaczyć adrsu wielkości nielokalnej przed rozpoczęciem wykonywania programu (podczas kompilacji). Eleganckie rozwiązanie podał E.W. Dijkstra [] proponując strukturę danych nazwaną Display Vector. Wiele implementacji języków Algol60, Pascal i Simula67 stosuje ten mechanizm. Jeśli jednak język programowania zezwala na zagnieżdżanie klas i dziedziczenie bardziej swobodne niż to dozwolone w Simuli, to sprawa się komplikuje.

Pierwsze rozwiązanie jakie znaleźliśmy umożliwiło stosowanie mechanizmu Display Vectora, ale za pewną cenę. Okazało sie, że semantyka języka nie była w pełni statyczna. Błąd ten znalazł i wskazał prof. Hans Langmaack z Uniwersytetu w Kilonii. We współpracy z nim znaleziono poprawne rozwiązanie problemu, które pozwala zachowac mechanizm Display Vectora.

Bibliografia

  1. [Kreczmar, Cioni 1984] Antoni Kreczmar, Gianna Cioni. Programmed deallocation without dangling reference. „Information Processing Letters”, s. 179-187, 1984. 
  2. [Cioni,Kreczmar, Vitale 1989] Gianna Cioni, Antoni Kreczmar, Ricardo Vitale: Storage Management. T. Advanced Programming Methodologies. London: Academic Press, 1989, s. 341-366. ISBN 0121746909.
  3. [Kreczmar, Oktaba, Ratajczak, Litwiniuk 1983] {{cytuj książkę | odn=tak|nazwisko = Kreczmar | imię = Antoni | tytuł= Semantics and Implementation of Prefixing at Many Levels | tytuł tomu = proc. Logics of Programs and their Applications | wydawca = Springer Vlg | miejsce = Berlin | data = 1983 | seria = LNCS 148 | strony = 45-80 | nazwisko2 = Bartol | imię2 = W.M. | nazwisko3 = Oktaba | imię3 = H. | nazwisko4 = Litwiniuk | imię4 = A.I.|isbn=0387119817 }