POLSKI SPOJ

Z całą pewnością Forth można uznać z jeden najoryginalniejszych języków programowania i dotyczy to dokładnie każdego aspektu. Dla jednych Forth jest najniższym z języków wysokiego poziomu, dla innych najwyższym z języków niskopoziomowych. Dla osób niewtajemniczonych składnia tego języka przypomina nocny koszmar przemęczonego programisty, a kompletne programy na pierwszy rzut oka wyglądają jak zupełnie przypadkowe zbitki dziwnych kombinacji znaków i cyfr. Kiedy dodamy do tego, że wynalazcą Fortha jest niejaki Charles Moore, z zawodu radioastronom, i że pierwszą wersję tego języka datuje się na połowę lat sześćdziesiątych, to poczujemy, że mamy do czynienia z tworem bardzo niecodziennym.

Program w języku Forth wykonuje się z wykorzystaniem stosu. Zapewne ta struktura danych nie jest dla ciebie nowością – wiesz, że stos, zachowuje się jak... stos – to, co położyłeś na nim jako pierwsze, zdejmiesz z niego jako ostatnie. I odwrotnie – to, co położyłeś jako ostatnie, zdejmiesz jako pierwsze.

I tu docieramy do pierwszej ciekawej cechy języka Forth. Jeśli w tekście programu pojawi się liczba, to ma ona podwójne znaczenie:

• po pierwsze, oznacza samą siebie

• po drugie, oznacza, że właśnie taką wartość należy położyć na stosie

Tu przyjmijmy nie do końca prawdziwe założenie, że zanim program w języku Forth zacznie się wykonywać, stos jest czyszczony, tzn. nie znajduje się na nim żadna liczba (stos jest pusty). Jeśli więc rozpatrzymy taki oto program (tak – w języku Forth to jest program!):

1 2 3 4 5

to należy się spodziewać, że w wyniku jego wykonania na stosie znajdzie się pięć liczb całkowitych, a sam stos wyglądać będzie tak:

Oczywiście, Forth ma bogaty zestaw operatorów – np. operator dodawania, którym jest znak '+' (plus). Jednak jego działanie może być nieco zaskakujące – otóż zdejmuje on ze stosu dwie liczby, dodaje je do siebie i sumę odkłada na stos. Wynika stąd, że po wykonaniu poniższego programu:

1 2 3 4 5 +

stos będzie wyglądał tak:

Mamy też operator mnożenia, którym jest gwiazdka ('*') - jak się zapewne sam domyślasz, zdejmuje on ze stosu dwie liczby, mnoży je i wynik tego mnożenia odkłada na stos. Program taki jak ten:

1 2 3 4 5 + *

 pozostawi stos w takim oto stanie:

Odejmowanie i dzielenie może budzić pewne wątpliwości – zacznijmy od odejmowania. Jego operatorem jest znak '-' (minus) i działa tak:

• zdejmuje ze stosu pierwszą liczbę (nazwijmy ją a)

• zdejmuje ze stosu drugą liczbę (nazwijmy ją b)

• kładzie na stosie wynik działania (a – b)

Podobnie ma się rzecz z dzieleniem, wyrażanym operatorem '/' (ukośnik) – powoduje on zdjęcie ze stosu liczb a i b (jak powyżej), a na stosie odłożony zostanie wynik działania (a / b). Tu dodajmy ważną uwagę – dzielenie w języku Forth jest całkowite – oznacza to, że program postaci:

1 2 3 4 5 + * /

pozostawi stos w stanie poniższym:

Jeśli to, o czym powiedzieliśmy do tej pory wywołuje w tobie nieodparte skojarzenia z Odwrotną Notacją Polską, to jesteś na właściwym tropie.

Kolejny ciekawy operator Fortha to kropka ('.'). Powoduje ona wykonanie następujących czynności:

• zdjęcie ze stosu jednej liczby

• wyprowadzenie wartości tej liczby na standardowe wyjście.

Poniższy program:

1 2 3 4 5 + * / .

pozostawi na stosie jedną liczbę (równą 1) i dodatkowo spowoduje, że na standardowym wyjściu pojawi się liczba 0.

Kolejne trzy operatory języka Forth omówimy lakonicznie:

• operator DUP zdejmuje ze stosu jedną liczbę, po czym odkłada ją na stos dwukrotnie

• operator DROP zdejmuje ze stosu jedną liczbę i niefrasobliwie ją gubi

• operator ROT czyni ze stosem sztuczkę następującą – jeśli przez jego użyciem stos wyglądał tak:

   

to po jego wykonaniu będzie wyglądał tak:

 Program takiej postaci:

 3 2 1 ROT . . .

 spowoduje pojawienie się na standardowym wyjściu takich oto wartości:

 3 1 2

 P.S.

Możesz zapytać, czy Forth dysponuje np. odpowiednikiem instrukcji if – tak, dysponuje. Ma instrukcje warunkowe, pętle, instrukcję wyboru i wywołania, czyli to wszystko, co powinien mieć szanujący się język programowania. Tyle, że na pierwszy rzut oka wygląd tych instrukcji jest co najmniej dziwny.

Polecenie: napisz program, będący uproszczonym interpreterem języka Forth, rozpoznającym opisane powyżej konstrukcje języka oraz wykonujący operacje arytmetyczne na danych o długości 32 bitów; rozmiar stosu twojego interpretera wynosi 1000.

Dane wejściowe: 1 wiersz tekstu, o nieznanej z góry długości, zawierający rozdzielone co najmniej jedną spacją nieujemne liczby całkowite z przedziału od 0 do 2³²-1 oraz operatory '+', '-', '*', '/', DUP, ROT i DROP w dowolnej kombinacji.

Dane wyjściowe: znaki, jakie wyprowadziłby na standardowe wyjście prawdziwy interpreter języka Forth przy następujących dodatkowych założeniach:

• po każdej wyprowadzonej liczbie należy wyprowadzić dokładnie jedną spację

• jeśli program próbuje wykonać dzielenie przez zero, interpreter powinien wyprowadzić na standardowe wyjście napis ERR i natychmiast zakończyć działanie

• jeśli liczba danych znajdujących się w pewnym momencie na stosie jest nieodpowiednia do wykonania żądanej operacji, interpreter powinien wyprowadzić na standardowe wyjście napis ERR i natychmiast zakończyć działanie

• jeśli na wejściu pojawi się ciąg znaków, którego nie jest ani operatorem, ani liczbą, interpreter powinien wyprowadzić na standardowe wyjście napis ERR i natychmiast zakończyć działanie

Przykład:

Wejście:

1 2 3 drop dup rot + . .

Wyjście:

3 2