728 x 90

Janus – czyli programy odwracalne, cz. 1

Janus – czyli programy odwracalne, cz. 1

Słowem wstępu

W dniach 28 – 31 sierpnia 2017 na Wydziale Matematyki i Informatyki Uniwersytetu Mikołaja Kopernika w Toruniu odbyła się międzynarodowa szkoła letnia „International Training School on Reversible Computation” poświęcona, jak nazwa wskazuje, tematowi obliczeń odwracalnych. O samej szkole możecie przeczytać w innym artykule jej poświęconym, ja natomiast skupię się na bardziej technicznym i praktycznym jej aspekcie. Na jednym z wielu ciekawych warsztatów przedstawiony został ciekawy język programowania o nazwie Janus. Z wyglądu, składni i działania język ten przypomina znany powszechnej społeczności C++. Nie jest on jednak tak bogaty, można wręcz powiedzieć, że stanowi niewielki wycinek tego pięknego języka. To co jednak charakteryzuje Janus i wyróżnia go na tle sztandarowych języków, to nie jego ogólne możliwości, a odwracalność. Każdy program napisany w języku Janus, o zostanie poprawnie wykonany, jest odwracalny. Oznacza to, że możemy nie tylko wywołać funkcję, ale także odwrócić jej działanie. Ale o tym za chwilę.

O języku słów kilka

Janus powstał w 1986 roku. Został zaprojektowany przez dwie osoby: Christopher’a Lutz oraz Howard’a Derby. Uznawany jest za pierwszy w historii odwracalny język programowania. W swojej pierwszej, oryginalnej wersji, Janus był językiem wspierającym proste, odwracalne aktualizacje, instrukcje warunkowe i pętle. Jego składnia różni się od rozwijanej obecnie. Wciąż można jednak używać pierwotnej wersji języka, nazywanej Janus86.

W późniejszych latach język ten został odkryty ponownie i stał się ważnym tematem naukowym w grupie PIRC (Program Inversion and Reversible Computation), zajmującej się właśnie szeroko pojętą odwracalnością programów i obliczeniami odwracalnymi. Obecnie Janus jest dalej badany i rozwijany, co daje nam możliwość korzystania z jego nowego, wciąż rozwijanego interpretatora.

Czym jest ta cała odwracalność

W dużym skrócie odwracalność pozwala nam odwrócić działanie jakiegoś obliczenia, funkcji, programu. Można to porównać na przykład do zakupów w sklepie. Kupujemy jakiś towar, powiedzmy nowy laptop. Jak to przebiega? Dajemy pieniądze w odpowiedniej ilości i w zamian dostajemy nasz sprzęt. Jeżeli chcielibyśmy odwrócić to działanie, czyli zwrócić sprzęt, to wykonujemy akcję, która zamienia naszego świeżo kupionego laptopa na pieniądze, w tej samej ilości, w jakiej je wydaliśmy. Podobnie sytuacja wygląda do odwracania funkcji. Wywołując ją przekazujemy odpowiednie parametry, a w odpowiedzi dostajemy wynik. Gdy chcemy odwrócić jej działanie, to przekazujemy wynik i otrzymujemy parametry wejściowe. To tylko ogólny schemat,  w praktyce nie jest to jednak aż takie proste, o czym zaraz się przekonamy.

Odwracalne programy w języku Janus

Zanim zaczniemy naszą przygodę z programowaniem w Janusie, przyda nam się sposób na uruchomienie napisanych programów. Do tego celu najlepiej wykorzystać intepreter online, dostępny tutaj: http://topps.diku.dk/pirc/?id=janusP

Wyposażeni w środowisko programistyczne, możemy przystąpić do napisania naszego pierwszego, odwracalnego programu. Będzie to prosty program zwiększający wartość zmiennej x o 2.

procedure inc2(int x)
    x += 2
procedure main()
    int x
    x += 8
    call inc2(x)

Wklejamy powyższy kod do interpretera i uruchamiamy przyciskiem „Run”. Naszym oczom w oknie konsoli na dole strony ukaże się wynik działania programu: „x = 10”. Przyjrzyjmy się teraz dokładniej temu, co napisaliśmy.

Program składa się z dwóch procedur: inc2 oraz main. Zadaniem pierwszej jest zwiększenie zmiennej x, podanej jako parametr, o wartość 2. Druga z kolei powinna nam się wydać znajoma, stanowi bowiem trzon naszego programu, czyli główną procedurę uruchamianą na samym początku.

Przyjrzyjmy się dokładniej naszym dwóm metodom. Zaczniemy od procedury inc2. Chociaż jej ciało składa się tylko z jednej linijki, wymaga pewnego komentarza. Po pierwsze warto zwrócić uwagę na fakt, że inc2 nie zwraca żadnej wartości. Z tego też powodu nie jest to funkcja, a właśnie procedura. Jednak jak możemy zauważyć w wyniku działania naszego programu wartość zmiennej x, która początkowo ustalona jest na 8, zwiększona zostaje o 2. Dzieje się tak dlatego, że w języku Janus wszystkie parametry przekazywane są przez referencję. Co za tym idzie nie jest tworzona ich kopia, a operacje przeprowadzone są na tym samym fragmencie pamięci.
Drugą rzeczą, której powinniśmy się przyjrzeć, jest sposób zmiany wartości zmiennej x. Część z Was może rozpoznawać zapis “x += 2” jako skróconą wersję operacji “x = x + 2”. Gdy jednak spróbujemy użyć takiej formy zapisu, to dostaniemy błąd wykonania programu. Nie oznacza to, że w Janusie nie ma klasycznej arytmetyki. Gdy jednak chcemy zmieniać wartość zmiennej, ograniczeni jesteśmy do operacji “+=” oraz “-=”. Wszystko na rzecz odwracalności.

Spójrzmy teraz na procedurę main. Na początku deklarujemy zmienną x typu integer, czyli całkowitoliczbowego. Warto tutaj nadmienić, że jest to jedyny dostępny typ. Zgadza się, w Janusie na próżno nam szukać typów takich jak float czy char, chociaż mamy do dyspozycji tablice. Po deklaracji naszej zmiennej możemy zmienić jej wartość. I tutaj jesteśmy także ograniczeni do dodania lub odjęcia jakiejś wartości. Operacja przypisania ograniczona jest do zmiennych lokalnych, o których opowiem innym razem. Na początku każda zadeklarowana zmienna ma wartość równą 0. Tak więc, aby uzyskać zmienną x o wartości 8 musimy do niej dodać właśnie tę wartość.
W ostatniej linijce naszej procedury widzimy wywołanie metody inc2, poprzedzone tajemniczym słówkiem call. To słowo kluczowe jest bardzo ważne, ponieważ wskazuje nam, którą wersję procedury chcemy wykonać. Jak wspomniałem wcześniej, programy napisane w Janus są odwracalne. Żeby być dokładnym należałoby jednak powiedzieć, że nie tyle programy są odwracalne, co same procedury. Każda procedura napisana w Janusie może być wywołana na dwa sposoby: w tradycyjnej wersji lub w swoim odwróconym wydaniu. Tak więc call odpowiada za wywołanie standardowej wersji procedury, natomiast uncall za wywołanie jej odwróconej wersji.

Zanim przystąpimy do odwracania, należy w tym miejscu zwrócić uwagę na jeszcze jedną rzecz. Po uruchomieniu programu zobaczyliśmy w konsoli wypisany komunikat “x = 10”, chociaż nigdzie nie zawarliśmy instrukcji wypisania komunikatu takiego komunikatu. Dzieje się tak dlatego, że po zakończeniu działania programu wypisywane są aktualne wartości wszystkich zmiennych zadeklarowanych w procedurze main.

Bogatsi o tą wiedzę możemy przystąpić do odwrócenia działania naszej procedury. Na końcu naszego programu dodajmy wywołanie “uncall inc2(x)”:

procedure inc2(int x)
 x += 2
procedure main()
 int x
 x += 8
 call inc2(x)
 uncall inc2(x)

Uruchamiamy program i widzimy wynik “x = 8”. Co się wydarzyło? Najpierw wywołaliśmy standardową wersję procedury inc2 w wyniku której wartość zmiennej x została zwiększona o 2. Następnie użyliśmy polecenia uncall aby wywołać odwróconą wersję inc2, w efekcie czego wartość zmiennej x wróciła do początkowej wartości!

No dobrze, ale co tak naprawdę się dzieje, gdy wykonujemy polecenie uncall inc2(x)? Tak jak wspomniałem wcześniej, wywoływana jest odwrócona wersja naszej procedury inc2. Jak jednak ona wygląda? Interpreter języka Janus wyposażony jest w funkcjonalność pozwalającą nam dokonać odwrócenia naszych procedur, wszystkich poza main. Żeby zobaczyć, jak wygląda odwrócona wersja procedury inc2, użyjmy przycisku Invert. Naszym oczom ukaże się następujący program:

procedure inc2(int x)
    x -= 2
procedure main()
    int x
    x += 8
    call inc2(x)
    uncall inc2(x)

Jak widać, w odwróconej wersji, procedura inc2 zamiast dodawać, to odejmuje wartość 2 od zmiennej x. Nie było ciężko się tego domyślić, teraz jednak dokładnie wiemy, jaka procedura jest wywoływana, gdy w naszym oryginalnym kodzie użyjemy polecenia uncall inc2(x).

Podsumowanie

W pierwszej części artykułu dowiedzieliśmy się czym jest odwracalność i na czym polegają obliczenia odwracalne. Poznaliśmy prawdopodobnie pierwszy w historii odwracalny język programowania Janus oraz napisaliśmy naszą własną, odwracalną procedurę. W kolejnej części dowiemy się, jak można odwracać instrukcje warunkowe, pętle, czym są zmienne lokalne i jak je wykorzystać przy pisaniu odwracalnej procedury konwertującej liczby dziesiętne na system binarny.

Źródło obrazu tytułowego: freeimages.com

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

Inne artykuły