Informatyka MIMUW

Posłużymy się GhostScriptem jak kalkulatorem, by przećwiczyć postfiksowy zapis wyrażeń. Przy okazji przedstawimy też podzbiór Postscriptu umożliwiający użycie go jak "prawdziwego" języka programowania.

Prosimy o uruchomienie programu Ghostscript poleceniem gs. Otworzy się okno z graficznym podglądem strony, a na konsoli będziemy mogli wprowadzać polecenia. Kończąc pracę, wpiszemy quit.

Zaczniemy od:

0 0 moveto 595 842 lineto stroke

rysującego przekątną strony, by pokazać, że interpreter działa.

Po tym wprowadzimy polecenie:

0 842 595 0 moveto lineto stroke

które narysuje drugą przekątną. Wyjaśnijmy, co tu się stało.

Prosimy o wpisanie ciągu liczb:

9
7
5
3
1

Po wprowadzeniu każdej z nich, w tekście zachęty wyświetli się informacja o liczbie wartości na stosie. Po ostatniej liczbie wprowadzimy polecenie:

stack

które wyświetli aktualną zawartość stosu, nie zmieniając jej.

Następnie wpiszemy:

add sub mul div =

i ręcznie prześledzimy ciąg obliczeń. = zdejmuje i wyświetla wartość z czubka stosu a pozostałe polecenia wykonują odpowiednie operacje arytmetyczne.

Prosimy o przetłumaczenie jakiegoś przykładu wyrażenia w zapisie infiksowym (z nawiasami) na zapis posfiksowy i sprawdzenie w Ghostscripcie, czy wynik wychodzi zgodny z oczekiwaniami.

Następnie przechodzimy do prezentacji PostScriptu jako języka programowania. Zaczniemy od pętli for:

1 2 10 {=} for

Polecenie for ma cztery argumenty - wartość startową, krok, wartość końcową i kod treści pętli. Treść pętli jest wykonywana z wartościa "zmiennej sterującej" na czubku stosu. Powyższy przykład wypisze więc nieparzyste liczby od 1 to 10.

By to przećwiczyć, jeszcze jeden przykład, liczący silnię z 10:

1 2 1 10 {mul} for =

Pętle oczywiście można zagnieżdżać. Oto przykład rysujący odcinki między parami punktów na dolnej i górnej krawędzi strony:

0 35 595 {
  0 35 595 {0 moveto dup 842 lineto stroke} for
  pop
} for

Przed jego wykonaniem warto oczyścić okno podglądu strony poprzez showpage.

W przykładzie mamy dwa nowe polecenia: dup powielające wartość na czubku stosu i pop zdejmujące wartość z czubka stosu.

Kolejny przykład wypisuje tekstowo choinkę (bez pnia). Mamy tu prostszą formę pętli - "repeat":

0 1 20 {
  dup 20 exch sub {( ) print} repeat {(**) print} repeat (*\n) print
} for

repeat wykonuje podany na czubku stosu kod liczbę razy wskazaną wartością pod czubkiem stosu. Mamy tu też użycie polecenia exch zamieniającego miejscami dwie wartości z czubka stosu i print wypisującego napis.

W kolejnym przykładzie pokażemy, jak można definiować odpowiedniki Pascalowych procedur/funkcji:

/Pionowa {dup 0 moveto 842 lineto stroke} def

/Pionowa jest tu nazwą, którą wiążemy z podanym kodem za pomocą polecenia def. Dostajemy w ten sposób procedurę, w tym przypadku jednoparametrową, rysującą dla zadanej współrzędnej x pionową kreskę przez całą stronę. Możemy ją wywołać np. poleceniem:

100 Pionowa

albo:

200 5 400 {Pionowa} for

Kolejny przykład, tym razem z funkcją:

/Silnia {dup 1 gt {dup 1 sub Silnia mul} if} def

Jest tu polecenie gt sprawdzające, czy między dwiema wartościami zachodzi relacja >, oraz if dostające na czubku stosu kod i wykonujące go, jeśli pod czubkiem stosu jest wartość logiczna "prawda".

Przykład uruchomimy poleceniem:

5 Silnia =

Jeszcze jedna funkcja rekurencyjna:

/Fib {dup 1 gt {dup 1 sub Fib exch 2 sub Fib add} if} def

uruchamiana np. tak:

0 1 10 {Fib =} for

Żonglowanie wartościami na stosie bywa niewygodne i łatwo się pomylić. Alternatywą jest posłużenie się zmiennymi, którym nadajemy wartość znanym już polecenien def. Wpiszmy:

/NWD {
  /a exch def
  /b exch def
  {a b eq {exit} if a b sub dup 0 gt {/a} {/b} ifelse exch abs def} loop
  a
} def

i przetestujmy:

234 432 NWD =

W tym przykładzie jest kilka nowych poleceń - eq badające równość, ifelse wykonujące jeden z dwóch fragmentów kodu w zależności od prawdziwości warunku, abs liczące wartość bezwzględną, loop realizujące potencjalnie nieskończoną pętlę i exit przerywające pętlę.

Następny przykład rysuje odcinki od środka strony do punktów na okręgu:

/szerokosc 595 def
/wysokosc 842 def
/NaSrodek {szerokosc 2 div wysokosc 2 div moveto} def
0 5 360 {dup sin 250 mul exch cos 250 mul NaSrodek rlineto} for stroke

Tym razem za pomocą def zdefiniowaliśmy nie tylko pomocniczą procedurę, ale i dwie stałe. Korzystamy tu też z sin i cos.

W kolejnym przykładzie - implementacji sita Eratostenesa - posłużymy się tablicą:

/n 100 def
/t n 1 add array def
2 1 n sqrt {dup dup mul exch n {t exch 1 put} for} for
2 1 n {dup t exch get 1 ne {=} {pop} ifelse} for

array tworzy tablicę o rozmiarze podanym na czubku stosu. Tablice w PostScripcie są indeksowane od 0, a wartością początkową poszczególnych elementów jest null. Wartość z tablicy odczytujemy za pomocą get, które na czubku stosu dostaje indeks a pod nim tablicę. Zapis do tablicy realizuje put z trzema argumentami (w kolejności od czubka stosu): wartość, indeks i tablica.

Mamy tu też sqrt, czyli pierwiastek kwadratowy i ne sprawdzające, czy wartości są różne.

W ostatnim przykładzie skorzystamy z generatora liczb pseudolosowych i wprowadzimy do rysunku kolor:

/Losowa {rand 2 31 exp div} def
/LosowyPunkt {Losowa szerokosc mul Losowa wysokosc mul} def
10 setlinewidth
1000 {
  Losowa Losowa Losowa setrgbcolor
  LosowyPunkt moveto LosowyPunkt lineto stroke
} repeat

rand daje losową liczbę całkowitą od 0 do 2^31-1, exp to potęgowanie, setlinewidth ustala szerokość kreski w punktach (domyślnie jest 1) a setrgbcolor wskazuje aktualny kolor na podstawie trzech liczb rzeczywistych z przedziału [0 .. 1] określających składową czerwoną, zieloną i niebieską.

Przejdźmy do kolejnego programu przykładowego (cesaro.pas):

program cesaro;
 
const
    SZEROKOSC_STRONY = 595;
    WYSOKOSC_STRONY = 842;
    MARGINES = 5;
    DLUGOSC_BOKU = SZEROKOSC_STRONY - 2 * MARGINES;
    ZMIANA_KATA = PI / 2.1;
    PODZIAL_DLUGOSCI = 2 * (1 + cos(ZMIANA_KATA));
    N = 5;
 
procedure r(dlugosc, kat : Real; krok : Integer);
begin
    if krok = N then
        writeln(dlugosc * cos(kat), ' ', dlugosc * sin(kat), ' rlineto')
    else begin
        r(dlugosc / PODZIAL_DLUGOSCI, kat, krok + 1);
        r(dlugosc / PODZIAL_DLUGOSCI, kat + ZMIANA_KATA, krok + 1);
        r(dlugosc / PODZIAL_DLUGOSCI, kat - ZMIANA_KATA, krok + 1);
        r(dlugosc / PODZIAL_DLUGOSCI, kat, krok + 1)
    end
end;
 
begin
    writeln('%!PS');
    {writeln('[2] 0 setdash');}
    writeln(MARGINES, ' ', (WYSOKOSC_STRONY - DLUGOSC_BOKU) / 2, ' moveto');
    r(DLUGOSC_BOKU, 0, 0);
    r(DLUGOSC_BOKU, PI / 2, 0);
    r(DLUGOSC_BOKU, PI, 0);
    r(DLUGOSC_BOKU, 3 * PI / 2, 0);
    writeln('stroke showpage')
end.

Kompilujemy go i uruchamiamy, przekierowując wynik do pliku wynik.ps, a następnie otwieramy ten plik programem Ghostscriptem.

Program ten rysuje fraktal Cesaro. Zmieniając wartość stałej N na 0, 1, 2 itd. powinniśmy zrozumieć rekurencyjny proces budowy krzywej. Wartość stałej "ZMIANA_KATA" można modyfikować w zakresie [O, π / 2]. W szczególności, dla π / 3 dostaniemy "cztery-trzecie" płatka (a właściwie antypłatka) Kocha.

Przykład korzysta z polecenia rlineto ("r" od "relative"), które jest odpowiednikiem lineto, ale z argumentami wskazującymi wektor, a nie współrzędne docelowe. Do kompletu w Postscripcie jest też rmoveto.

Dodatkowo, korzystamy tu też z faktu, że w skład rysowanej "ścieżki" może wchodzić więcej niż jeden odcinek. Kolejne polecenia lineto czy rlineto rysują odcinki od miejsca, w którym zakończył się odcinek poprzedni.

Odkomentujmy instrukcję writeln('[2] 0 setdash'). Powoduje ona, że linia rysowania staje się przerywana. Pierwszy argument to tablica określająca cykliczną sekwencję kresek i przerw. W tym wypadku będzie kreska długości dwóch punktów, następnie dwa punkty przerwy itd. Drugi argument mówi, w którym miejscu tej sekwencji zaczynamy - 0 oznacza, że od początku.