Antoni Kreczmar

Antoni Kreczmar

Państwo działania	Polska
Data i miejsce urodzenia	1945 Warszawa
Data i miejsce śmierci	23 października 1996 Warszawa
doktor habilitowany nauk matematycznych
Specjalność: podstawy informatyki
Alma Mater	Uniwersytet Warszawski
Doktorat	1973
Habilitacja	1977
Nauczyciel akademicki
Uczelnia	Uniwersytet Warszawski
Odznaczenia

Antoni Kreczmar (ur. 1945 w Warszawie, zm. 23 października 1996 tamże) – polski informatyk i matematyk, doktor habilitowany, pracownik naukowy Instytutu Informatyki Uniwersytetu Warszawskiego.

Pochodził z rodziny Kreczmarów, nauczycieli od pokoleń, a później także ludzi teatru i filmu. Był synem Jerzego Kreczmara. W roku 1973 obronił rozprawę doktorską Effectivity problems of Algorithmic Logic, promowaną przez prof. Helenę Rasiową. W 1977 napisał pracę "Programmability in fields", przedstawioną później jako rozprawę habilitacyjną na Wydziale Matematyki UW. Spoczywa w grobowcu rodzinnym na cmentarzu Powązkowskim w Warszawie (kw. 190–V–24/25).

Grób Antoniego Kreczmara na warszawskim cmentarzu Powązkowskim

Osiągnięcia naukowe

W zakresie logiki algorytmicznej

• Jego pierwsze badania (rozprawa doktorska) dotyczyły oszacowania zbioru tautologii logiki algorytmicznej. Wykazał, że zbiór ten nie mieści się w żadnej klasie arytmetycznej hierarchii Kleene-Mostowskiego.[Kreczmar 1977a ↓ ]
• Udowodnił, że ciało liczb wymiernych jest scharakteryzowane z dokładnością do izomorfizmu przez aksjomaty ciała oraz własność stopu algorytmu Euklidesa [Kreczmar 1977b ↓ ]. Wynika stąd, że każda prawdziwa własność algorytmiczna dowolnego programu P działającego w jakimś ciele Euklidesowym może być wyprowadzona z aksjomatów uporządkowanego ciała Euklidesowego, tzn. z aksjomatów ciała wzbogaconych o następującą formułę:

$\color {blue}\qquad \forall _{x\geq 0}\forall _{y\geq 0}\left\{{\begin{array}{l}\mathbf {while} \ x\neq y\ \mathbf {do} \\\qquad \mathbf {if} \ x>y\ \mathbf {then} \ x:=x-y\ \mathbf {else} \ y:=y-x\ \mathbf {fi} \\\mathbf {od} \end{array}}\right\}x=y\color {black}$

(Euc)

którą należy czytać: dla każdych nieujemnych wartości x i y, program(algorytm) Euklidesa kończy obliczenia. A dokładniej, program ujęty w nawiasy {} kończy swoje obliczenia i jego wyniki spełniają formułę x=y następującą po nim. Jest to przykład formuły algorytmicznej. Zauważ, że formuła ta nie jest prawdziwa w dziedzinie liczb rzeczywistych, w dziedzinie odcinków na płaszczyźnie z odejmowaniem odcinków i porównywaniem ich długości, ani w dziedzinie liczb zespolonych.

• udowodnił, że zbiór własności algorytmicznych prawdziwych w dziedzinie liczb rzeczywistych to formuły dające się wyprowadzić ze schematu aksjomatów liczb formalnie rzeczywistych [Kreczmar 1977b ↓, s. 19].
• Jest współautorem pierwszej monografii na temat logiki algorytmicznej [Banachowski i in. 1977 ↓ ].

W zakresie złożoności obliczeniowej

• zmodyfikował algorytm Strassena mnożenia macierzy uzyskując znaczne zmniejszenie zapotrzebowania na dodatkowe komórki pamięci roboczej [Kreczmar 1976 ↓ ] z $\color {blue}{\frac {11}{3}}n^{2}\color {black}$ na $\color {blue}{\frac {2}{3}}n^{2}\color {black}$ (Jak zazwyczaj, przyjmuje się, że mówimy o mnożeniu macierzy o rozmiarach $n\times n$).

• po raz pierwszy w Polsce poprowadził wykład ze złożoności obliczeniowej,

• był współautorem polskiego tłumaczenia ważnej dla pokoleń informatyków książki Projektowanie i analiza programów komputerowych autorstwa A. Aho, J. Hopcrofta i J. Ullmana,

• jest współautorem trzech książek o analizie algorytmów
  • Elementy analizy algorytmów [Banachowski i Kreczmar 1989 ↓ ],
  • Analiza algorytmów i struktur danych [Banachowski, Kreczmar i Rytter 1987 ↓ ],
  • Analysis of Algorithms and Data Structures [Banachowski, Kreczmar i Rytter 1991 ↓ ]

W zakresie języków programowania obiektowego

• Jest współautorem języka programowania obiektowego Loglan'82 [Kreczmar 1982 ↓, s. 66, Bartol i in. 1984 ↓ ]

• Jest autorem running systemu (dzisiaj częściej używa się nazwy maszyna wirtualna) dla języka Loglan'82. Przy tej okazji rozwiązał wiele problemów:

1. Czy istnieje taki system zarządzania pamięcią obiektów, w którym można usuwać niepotrzebne obiekty w sposób bezpieczny (tzn. bez ryzyka powstania wiszących referencji) i w czasie stałym?
2. W jaki sposób należy odszukiwać wystąpienie deklarujące dany identyfikator używany w danym miejscu programu?
3. Czy można zaadaptować (zachować) mechanizm Display Vectora?
4. Jak ma działać system współprogramów?

• Opracował bezpieczny i efektywny system zarządzania pamięcią obiektów, [Kreczmar i Cioni 1984 ↓ , Cioni, Kreczmar i Vitale 1989 ↓ ], jest to system kompletny, oferujący operacje: tworzenia nowego obiektu i rezerwowania pamięci dla niego, kompresji kopca obiektów, odśmiecania kopca, tj. pamięci obiektowej i przede wszystkim operację kill bezpiecznego usuwania obiektu. Tutaj omówimy jego unikalną cechę wyrażającą się w postaci poniższego schematu:

Schemat aksjomatu instrukcji kill

Niech x₁, ... ,x_n będą zmiennymi, n>0, 1≤i≤n. Każda formuła o podanym poniżej schemacie jest twierdzeniem running systemu Kreczmara.

$\color {blue}(x_{1}=\dots =x_{n}\neq none)\Rightarrow [kill(x_{i})](x_{1}=\dots =x_{n}=none)\;\color {blue}$

co się czyta: jeżeli na pewien obiekt o wskazuje n zmiennych to po wykonaniu instrukcji kill(x_i) wspólną wartością tych zmiennych jest none (oznacza to, że sam obiekt o jest od tej pory niedostępny i może być przez tę samą instrukcję kill bez szkody usunięty). W konsekwencji:

• nie ma potrzeby powtarzania operacji kill(x₁),kill(x₂), ...
• nie występuje zjawisko wiszących referencji,
• każda próba odniesienia się do atrybutu obiektu, który wcześniej został usunięty zostanie wykryta i spowoduje zgłoszenie wyjątku „reference to none”.

Należy podkreślić, że koszt operacji kill jest stały, niezależny od liczby n wskaźników na usuwany obiekt.

Taki system zarządzania pamięcią obiektów zastosowano tylko raz, w implementacji języka Loglan'82.

System zarządzania obiektami jest pomyślany całościowo, dostarcza operacji:

• wspomagających powstanie obiektu – new,
• sprawdzających legalność operacji dostępu do atrybutów obiektu,
• usuwania obiektu na żądanie,
• defragmentacji i odśmiecania pamięci obiektowej.

Porównaj sposoby pozbywania się niepotrzebnych obiektów

	model A (Loglan'82)	Model B (C++ 1986)	Model C (Java 1995, Python)
Przed	Na pewien obiekt o wskazują zmienne x1,x2, ..., xn.
Instrukcja	kill(xi)	delete(xi)	x1=null;x2=null; ... xn=null; Po wykonaniu instrukcji gc() obiekt zostanie usunięty.
Po	Wszystkie zmienne przyjęły wartość none. Obiekt został usunięty.	Obiekt o został usunięty. x ma wartość null. Inne zmienne wskazują na zwolnione pole – jest to groźny błąd – wiszącej referencji.	Obiekt został usunięty, pod warunkiem, że nie zapomniano o żadnej zmiennej wskazującej na obiekt o.
Koszt	Stały (nieduży)	Stały (nieduży).	Znaczny, zależny od liczby zmiennych wskazujących na obiekt i od łącznego rozmiaru pamięci obiektowej (koszt operacji gc()).
Ryzyko	Brak(!). Próba dostępu do obiektu o podnosi wyjątek reference to none.	Duże prawdopodobieństwo (przy n>1) błędu wiszących referencji Duże prawdopodobieństwo błędu sprzecznych informacji.	Spore szanse na to, że programista zapomni usunąć, którąś referencję do niepotrzebnego obiektu.

• Opracował na nowo system zarządzania obiektami współprogramów (ang. coroutines)[Cioni i Kreczmar 1989 ↓, s. 297-308]. Usunął w ten sposób sprzeczności występujące w systemie współprogramów w języku Simula67.
• Rozwiązał razem z H. Langmaackiem, M. Krause i M. Warpechowskim problem adaptacji mechanizmu Display Vectora dla klasy języków z klasami zagnieżdżanymi i z dziedziczeniem [Kreczmar i in. 1986 ↓ , zobacz też Kreczmar i in. 1983 ↓ ].
• Podał prawidłowe rozwiązanie problemu statycznego wiązania aplikacyjnych wystąpień identyfikatorów z odpowiednią deklaracją [Kreczmar i in. 1983 ↓ ].
• Jest współautorem kolejnej (niezrealizowanej) wersji języka Loglan (zobacz Kreczmar, Salwicki i Warpechowski 1990 ↓ ]).
• Stworzył running system dla języka Loglan'88.

Inne

Wypromował 5 doktorantów. Dwóch z nich zostało profesorami.

Został wyróżniony nagrodą państwową 1. stopnia (zespołową) w dziedzinie nauki, za opracowanie i realizację języka programowania obiektowego Loglan'82, [nagroda w roku 1986].

Przyczynił się do rozwoju internetu w Polsce w latach 90. XX wieku.

W 1989 był współorganizatorem konferencji Mathematical Foundations of Computer Science w Porąbce [Kreczmar i Mirkowska 1989 ↓ ].

W latach 1994–1996 był dyrektorem departamentu Informatyki w Ministerstwie Finansów. Zmarł w trakcie pracy nad zadaniem zbudowania systemu POLTAX, informatycznego systemu podatkowego.

Odznaczony pośmiertnie Krzyżem Kawalerskim Orderu Odrodzenia Polski.

Wybrane publikacje

W jego dorobku publikacyjnym znajdują się m.in.:

1. [Kreczmar 1977a] Antoni Kreczmar. Effectivity problems of Algorithmic Logic. „Fundamenta Informaticae”, 1977. 
2. [Kreczmar 1977b] Antoni Kreczmar. Programmability in Fields. „Fundamenta Informaticae”, s. 195-230, 1977. 
3. [Kreczmar, Cioni 1984] Antoni Kreczmar, Gianna Cioni. Programmed deallocation without dangling reference. „Information Processing Letters”, s. 179-187, 1984. 
4. [Banachowski, Kreczmar 1989] Lech Banachowski, Antoni Kreczmar: Elementy Analizy Algorytmów. Warszawa: WNT, 1989, s. 197. ISBN 83-204-1147-5.Sprawdź autora:1.
5. [Banachowski, Kreczmar, Rytter 1987] Lech Banachowski, Antoni Kreczmar, Wojciech Rytter: Analiza Algorytmów i Struktur Danych. Warszawa: WNT, 1987, s. 217. ISBN 83-204-0717-6.
6. [Banachowski, Kreczmar, Rytter 1991] Lech Banachowski, Antoni Kreczmar, Wojciech Rytter: Analysis of Algorithms and Data Structures. New York: Addison-Wesley, 1991, s. 300. ISBN 0-201-41693-X.
7. [Loglan 82] W.M. Bartol i in.: Report on the Loglan'82 programming language. Warszawa-Łódź: PWN, 1984, s. 165.Sprawdź autora:1.
8. [Kreczmar 1976] Antoni Kreczmar: On Memory Requirements of Strassen’s Algorithm. T. Proc. MFCS'76. Berlin: Springer, 1976, s. 404-407, seria: LNCS. ISBN 3-540-07854-1.Sprawdź autora:1.
9. [Grabowski, Kreczmar 1978] Michał Grabowski, Antoni Kreczmar: Dynamic theories of real and complex numbers. T. Proc. MFCS'78. Berlin: Springer Vlg, 1978, s. 239-249, seria: LNCS 64. ISBN 0-387-08921-7.
10. [Kreczmar, Oktaba, Ratajczak, Litwiniuk 1983] Antoni Kreczmar, W.M. Bartol, H. Oktaba, A.I. Litwiniuk: Semantics and Implementation of Prefixing at Many Levels. T. proc. Logics of Programs and their Applications. Berlin: Springer Vlg, 1983, s. 45-80, seria: LNCS 148. ISBN 0-387-11981-7.
11. [Kreczmar i in 1984] Antoni Kreczmar, Manfred Krause, Hans Langmaack, Andrzej Salwicki: Specification and Implementation Problems of Programming Languages Proper for Hierarchical Data Types. T. Rep. 8410. Kiel: Institut fuer Informatik, University of Kiel, 1984.
12. [Kreczmar 1982] Antoni Kreczmar: The programming language Loglan'82 Basic constructs and facilities. Warszawa: Uniwersytet Warszawski, 1982, s. 66.
13. [Kreczmar i in. 1986] Antoni Kreczmar, Manfred Krause, Hans Langmaack, Marek Warpechowski: Concatenation of program modules an algebraic approach to the semantics and implementation problems. Berlin: Springer, 1986, s. 134-156, seria: LNCS 208.
14. [Kreczmar, Salwicki, Warpechowski 1990] Antoni Kreczmar, Andrzej Salwicki, Marek Warpechowski: Loglan'88 – Report on the Programming Language. Berlin: Springer Vlg, 1990, s. 133, seria: LNCS 414. ISBN 0-387-52325-1.
15. [Cioni,Kreczmar 1989] Gianna Cioni, Antoni Kreczmar: Modules in High Level Programming Languages. T. Advanced Programming Methodologies. London: Academic Press, 1989, s. 247-340. ISBN 0-12-174690-9.
16. [Cioni,Kreczmar, Vitale 1989] Gianna Cioni, Antoni Kreczmar, Ricardo Vitale: Storage Management. T. Advanced Programming Methodologies. London: Academic Press, 1989, s. 341-366. ISBN 0-12-174690-9.
17. [Kreczmar, Mirkowska 1989] Antoni Kreczmar, Grażyna Mirkowska: Mathematical Foundations of Computer Science. Berlin: Springer Vlg, 1989, s. 620, seria: LNCS. ISBN 978-3-540-51486-2.
18. [Kreczmar 1977] Antoni Kreczmar: On finite and infinite computations. T. Proc. FCT'77. Bonn: Springer Vlg, 1977, s. 441-446, seria: LNCS 56. ISBN 0-387-08442-8.
19. [Kreczmar 1977] Antoni Kreczmar. On infinite sets of polynomial relations. „Bull.Acad.Pol.Sci.Ser.Astr.Math.Phys.”. 25, 1977. PWN. brak numeru strony
20. [Kreczmar 1979] Antoni Kreczmar: Some historical remarks on algorithmic logic. T. Algorithms in Modern Mathematics and Computer Science. Berlin: Springer Vlg, 1979, s. 999-1000, seria: LNCS. ISBN 0-12-345678-9.
21. [Banachowski i in.] Lech Banachowski, Antoni Kreczmar, Grażyna Mirkowska, Helena Rasiowa, Andrzej Salwicki: An introduction to Algorithmic Logic – Metamathematical Investigations of Theory of Programs. T. 2: Banach Center Publications. Warszawa: PWN, 1977, s. 7-99, seria: Banach Center Publications. ISBN 123.

Zobacz też

• odśmiecanie pamięci

Linki zewnętrzne

• repozytorium Loglanu. 1996. [dostęp 2012-12-29].
• Antoni Kreczmar: Loglan'82 – basic constructs and facilities. 1982. [dostęp 2013-02-10].