Programowanie w Brainf**ku

28.12.2009 - Marek Materzok
TrudnośćTrudnośćTrudność

Czyli jak napisać sensowny program w ekstremalnie uproszczonym języku programowania.

Krótko o Brainf**ku

Brainf**k jest jednym z najbardziej znanych ezoterycznych języków programowania - czyli takich, które nie służą do praktycznego programowania. Język ten wyróżnia niezwykła prostota zarówno sposobu zapisu, jak i dostępnych komend. Program w Brainf**ku posiada pamięć (taśmę) złożoną z bajtów, na jeden z nich wskazuje głowica. Można przyjąć, że taśma jest z prawej strony nieograniczona - to znaczy, jakkolwiek daleko głowica zawędruje na prawo, taśmy nie zabraknie. (Naturalnie, ilość pamięci komputera w praktyce ogranicza długość taśmy, ale nie będziemy się tym przejmować.) Komendy w Brainf**ku mają długość jednego znaku i decydują o ruchach głowicy oraz zmianach na taśmie. Owe komendy to:

  • + - zwiększa wartość pod głowicą o jeden (inkrementacja)
  • - - zmniejsza wartość pod głowicą o jeden (dekrementacja)
  • < - przesuwa głowicę jeden bajt w lewo
  • < - przesuwa głowicę jeden bajt w prawo
  • [ - rozpocznij pętlę, jeśli pod głowicą jest wartość inna niż 0, w przeciwnym razie pomiń wszystkie instrukcje aż do pasującego ]
  • ] - jeśli pod głowicą jest wartość inna niż 0, powtórz pętlę, w przeciwnym wypadku nie rób nic
  • , - wczytaj znak z wejścia i zapisz pod głowicą
  • . - odczytaj znak pod głowicą i wypisz na wyjście

Komendy [ i ] muszą być dopasowane do siebie, jak nawiasy. Każdy znak, który nie jest komendą, jest ignorowany.

Być może trudno to sobie wyobrazić, ale przedstawiony powyżej język pozwala na wyrażenie każdego algorytmu, jaki można zapisać w innych, bardziej codziennych językach! Nie znaczy to oczywiście, że programy w Brainf**ku będą tak samo szybkie - myślę, że dość łatwo sobie wyobrazić, że będą dużo, dużo wolniejsze. Programując w Brainf**ku należy chwilowo zapomnieć o efektywności; zrobienie czegokolwiek poprawnie jest wystarczająco kłopotliwe!

Jak to ugryźć?

Programowanie w Brainf**ku może wydawać się bardzo trudnym zadaniem, jednak nie taki diabeł straszny, jak go malują. Aby umożliwić sobie swobodne pisanie programów w tym języku, wystarczy odtworzyć w nim elementy, które dobrze znamy z innych, bardziej praktycznych języków.

Zacznijmy od czegoś prostego - od dodawania. Pamiętając o tym, że jedyne, co potrafimy zrobić w Brainf**ku, to dodawać i odejmować jedynki, możemy powiedzieć, że dodanie liczby k i l polega na k-krotnym dodaniu jedynki do l. Zakładając, że k jest pod głowicą, a l jeden bajt na prawo od niej, kod wykonujący dodawanie to [->+<]. A oto ilustracja jego działania dla przykładu k=2, l=3:

W analogiczny sposób można zaimplementować odejmowanie.

Powyższy program dodający ma jedną istotną cechę, która może być zarówno zaletą, jak i wadą - mianowicie, bajt zawierający jedną z dodawanych liczb jest zerowany. W Brainf**ku jest to zjawisko nie do uniknięcia, gdyż jest konsekwencją sposobu działania pętli. Druga dodawana wartość również zniknęła z pamięci, została zastąpiona wynikiem. Jeśli wartości użyte w działaniu będą nam potrzebne później w programie, niezbędne jest skopiowanie ich w inne miejsce w pamięci.

Program kopiujący wygląda bardzo podobnie do przedstawionego wcześniej programu dodającego. Jedyna różnica polega na tym, że wewnątrz pętli inkrementujemy więcej niż jeden bajt na taśmie. Przykładowy kod duplikujący: [->+>+<<] - a oto, jak działa:

Jak widać, bajt pamięci zawierający duplikowaną wartość został w wyniku operacji wyzerowany, tak, jak ostatnio. Jeśli jest to dla nas z jakiegoś powodu niepożądane, możemy przywrócić porządek dodatkową operacją dodawania. Nie da się niestety uniknąć przejściowego użycia dodatkowej komórki pamięci. W Brainf**ku jest to często występująca sytuacja. Gotowy kod kopiujący z komórką tymczasową: [->+>+<<]>>[-<<+>>].

Ponieważ mnożenie jest wielokrotnie powtórzonym dodawaniem, skorzystanie z przygotowanych powyżej kawałków kodu powinno nam ułatwić jego implementację. Przyjmijmy, że pierwszy czynnik (k) jest pod głowicą, drugi (l) komórkę na prawo, zaś wynik chcemy zapisać dwie komórki na prawo. Ponieważ chcemy powtórzyć k-krotnie pewne operacje, zacznijmy, tak jak poprzednio:

[-

Pamiętając, że operacja dodawania wyzeruje pierwszy argument, musimy go przy okazji skopiować, używając tymczasowo dodatkowej komórki.

>[->+>+<<]>>[-<<+>>]

Teraz drugi czynnik jest nienaruszony, ponadto został dodany do wyniku. Tymczasowa komórka pamięci została już wyzerowana, zostaje więc już tylko przenieść głowicę na pozycję wyjściową:

<<<]

Poniżej kod mnożenia w całości oraz przykład działania.

[->[->+>+<<]>>[-<<+>>]<<<]

Zaimplementowanie dzielenia w Brainf**ku jest wprawdzie jak najbardziej możliwe, jednak jest skomplikowane, w związku z czym nie zaprezentuję tu kodu dzielenia.

5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com