Języki ezoteryczne

28.12.2009 - Marek Materzok
TrudnośćTrudność

Befunge: pętle wzięte zbyt dosłownie

We wszystkich znanych językach programowania, w tym w dotychczas omówionych językach ezoterycznych, program jest opisany za pomocą jakiegoś ciągu znaków. A może by tak zapisywać program na płaszczyźnie? Językiem, który pozwala to zrealizować, jest Befunge.

Program w języku Befunge jest dwuwymiarową tablicą znaków dowolnych wymiarów. Instrukcje, podobnie jak w języku Brainf**k, składają się z pojedynczych znaków. Pierwsza instrukcja w programie znajduje się w lewym górnym rogu, kolejna instrukcja do wykonania znajduje się po prawej stronie. Kierunek biegu programu można zmienić, używając instrukcji ^, v, < i > - powodują one, że po ich napotkaniu kolejne instrukcje do wykonania znajduje się odpowiednio powyżej, poniżej, po lewej lub po prawej od aktualnie wykonywanej. W związku z tym w kodzie programu pętle faktycznie wyglądają jak pętle, na przykład nieskończoną pętlę można zapisać tak:

>   v

^   <

Istotną cechą programów w Befunge jest to, że po wyjściu poza tablicę następuje "zapętlenie" - kolejną instrukcja do wykonania jest instrukcja po przeciwnej stronie tablicy! (Można też powiedzieć, że program w Befunge jest zapisany na torusie - "obwarzanku".) Wykorzystując ten fakt, nieskończoną pętlę można zapisać też tak:

^>
<v

Program w języku Befunge jako pamięć wykorzystuje stos. Instrukcja będąca cyfrą od   do 9 umieszcza swoją wartość na szczycie stosu, a operacje arytmetyczne *, -, * i / zdejmują ze szczytu stosu dwie wartości, wykonują działanie na nich i odkładają na stos wynik. Widać więc, że wykonywanie obliczeń w języku Befunge jest dużo łatwiejsze, niż w INTERCALu i Brainf**ku - obliczane wyrażenie wystarczy zapisać w postaci postfiksowej, znanej też jako odwrotna notacja polska. Dla przykładu, aby obliczyć wartość wyrażenia 2+2*2 w Befunge, można użyć następującego ciągu instrukcji:

222*+

Dostępne są też instrukcje modyfikujące stos: instrukcja $ usuwa wartość na szczycie stosu, : tworzy kopię wartości na szczycie stosu, a \ zamienia dwie najwyżej położone na stosie wartości ze sobą.

Na szczęście łatwość wykonywania obliczeń nie czyni języka Befunge nudnym - jego konstrukcje sterujące są bardzo interesujące! Weźmy chociażby instrukcję warunkową, zapisywaną w Befunge | lub _. Instrukcja ta zdejmuje wartość ze stosu; jeśli było to zero, zmieniamy kierunek wykonywania na dół (prawo), w przeciwnym wypadku kontynuujemy wykonywanie w górę (lewo). Instrukcje te mogą tworzyć wyjścia z pętli - tak jak na przykład w poniższym programie, obliczającym silnię:

0&v  _$v* <
  :  : >\:|
  >1-^    >.@

Program ten najpierw zapisuje na stosie kolejne liczby od 1 do wczytanej wartości n, po czym mnoży je, dopóki nie napotka na zostawione na początku programu zero. (Instrukcja & oznacza wprowadzenie liczby, . wypisanie liczby, a @ kończy działanie programu.

Dla ułatwienia pisania skomplikowanych programów istnieje instrukcja # - "trampolina", oznaczająca pominięcie następnej instrukcji. Za jej pomocą można swobodnie przecinać różne ścieżki wykonania programu bez konieczności umieszczania spacji na "skrzyżowaniach".

Programy w języku Befunge mają jeszcze jedną ciekawą cechę - mogą modyfikować swój własny kod! Instrukcja g zdejmuje ze stosu parę liczb - współrzędne komórki, po czym zapisuje wartość tej komórki na stosie. Analogicznie, instrukcja p zdejmuje ze stosu współrzędne komórki, następnie zdejmuje ze stosu nową wartość komórki i zapisuje ją w tablicy programu. Możliwość samomodyfikacji powoduje, że napisanie kompilatora języka Befunge jest trudne.

Oto program Hello World w Befunge:

>              v
v ,,,,,"Hello"<
>48*,          v
v,,,,,,"World!"<
>25*,@

Program używa specjalnej instrukcji " do zapisania napisu na stosie, który potem jest wypisywany na ekran znak po znaku.

Unlambda - funkcyjnie bez zmiennych

Niektóre języki programowania są szczególnie dobrze przystosowane do operowania funkcjami - między innymi pozwalają na przekazywanie funkcji jako parametr do innych funkcji, zwracanie funkcji jako wartość innej funkcji oraz łatwe definiowanie nowych funkcji. Języki takie nazywamy funkcyjnymi. Można posunąć się z tym do ekstremum i uniemożliwić tworzenie niczego za wyjątkiem funkcji. Taki ograniczony język nadal może być kompletny obliczeniowo - można z pomocą funkcji zakodować liczby, operacje arytmetyczne i logiczne. Okazuje się, że można posunąć się jeszcze dalej i zrezygnować z istnienia zmiennych! Nie można wtedy nawet definiować funkcji przez zależność wyniku od argumentu (f(x) = t), gdyż argument funkcji również jest zmienną. Jedynym sposobem na definiowanie nowych funkcji staje się aplikowanie do siebie funkcji już wbudowanych w język. Na takiej idei oparty jest język programowania Unlambda.

Ciekawostka: podstawą teoretyczną języków funkcyjnych jest rachunek lambda - prosty język programowania, w którym występują tylko trzy rodzaje wyrażeń: odczytanie zmiennej, zdefiniowanie funkcji i zastosowanie funkcji do argumentu. Język opracował Alonzo Church w roku 1930 - choć jego celem nie było stworzenie języka programowania, a opracowanie alternatywnej podstawy matematyki do teorii zbiorów. Ten język również jest kompletny obliczeniowo!

Funkcje w języku Unlambda, podobnie jak w popularnych językach funkcjonalnych, są jednoargumentowe. Funkcje wielu argumentów "symuluje się" w taki sposób, że funkcja po przyjęciu pierwszego argumentu zwraca nową funkcję, która przyjmuje drugi parametr, i tak dalej - aż zostanie przyjęty argument ostatni, kiedy to wreszcie zwracany jest wynik funkcji. Innymi słowy, zamiast definiować funkcję f(x,y) = t, definiujemy f(x)(y) = t. Technikę ta nazywa się currying i jest powszechnie stosowana w językach funkcyjnych.

Dwie najważniejsze funkcje wbudowane w języku Unlambda to s oraz k.

Funkcja k bierze dwa parametry (w zgodzie z poprzednim akapitem) i zwraca pierwszy - czyli k(x)(y) = x. Funkcja s jest bardziej skomplikowana. Bierze ona trzy parametry i składa je według wzoru: s(x)(y)(z) = x(z)(y(z)). Dla wygody istnieje też funkcja identycznościowa i o działaniu i(x) = x, jednakże można ją zdefiniować jako s(k)(k): s(k)(k)(x) = k(x)(k(x)) = x = i(x).

Język Unlambda posiada bardzo uproszczoną notację dla aplikacji argumentu do funkcji. Jest to notacja prefiksowa, i jest bardzo podobna do odwrotnej notacji polskiej - różnica polega na tym, że zamiast pisać najpierw argumenty, a potem operację, piszemy odwrotnie: najpierw operację, a potem jej argumenty. Zgodnie z tą notacją, zamiast f(x) piszemy `fx. W związku z tym możemy wbudowane funkcje opisać inaczej - mianowicie, że wyrażenia postaci ``kXY przepisywane są do x, zaś ```sXYZ do ``XZ`YZ.

Opisany powyżej język już jest kompletny obliczeniowo (choć nie bardzo widać, jak w nim można programować!), jednak brakuje mu sposobu na wypisywanie informacji. W tym celu stosuje się funkcję zapisywaną .X, gdzie X jest dowolnym znakiem. Funkcja ta działa tak samo, jak i, jednak przy okazji wypisuje na ekran znak X.

Oto program "Hello World" w języku Unlambda:

`````````````.H.e.l.l.o.,. .w.o.r.l.d.!k

Program ten wywołuje po kolei funkcje wypisujące kolejne litery.

5
Twoja ocena: Brak Ocena: 5 (1 ocena)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com