Laboratorium 7: Praca nad zadaniem zaliczeniowym 1. Postscript, rekursja

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:

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.