Programowanie w Brainf**ku

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

Pod warunkiem, że...

Dotychczas nie korzystaliśmy jeszcze z niczego, co przypominałoby tradycyjną konstrukcję warunkową if-then-else! Konstrukcja taka nie przypomina na pierwszy rzut oka k-krotnego powtórzenia, więc można mieć podejrzenia, że trzeba będzie się sporo namachać. Na szczęście nie jest aż tak źle.

Do kodowania wartości logicznych najprościej chyba użyć konwencji znanej między innymi z języka C: prawdę będziemy reprezentować wartością niezerową, zaś fałsz - zerem. Mając taką reprezentację, narzuca się następująca implementacja instrukcji if-then: [[-]then]. Jak widać, jest dość podobna do używanej przez nas wcześniej konstrukcji k-krotnego powtórzenia. Różnica polega na tym, że zerując k na początku pętli, wymuszamy tylko jednokrotne jej wykonanie. Z konstrukcji tej będziemy dość często korzystać.

Samo if-then to trochę mało, zapytacie się więc pewnie, jak zaimplementować instrukcję if-then-else? Jeśli się chwilę zastanowić, nie jest to bardzo trudne. Ponieważ w Brainf**ku wykonanie kodu może być warunkowane tylko obecnością niezerowej wartości w pewnej komórce pamięci, wystarczy zapewnić, aby w pewnej tymczasowej komórce była niezerowa wartość wtedy i tylko wtedy, gdy wartość, którą sprawdzamy, jest równa zeru. Zrobimy to, inkrementując na początku tę komórkę i dekrementując ją w gałęzi then. Instrukcja if-then-else wyglądać więc będzie tak: >+<[[-]>-then<]>[-else].

Ponieważ wartości logiczne w konwencji C mają tę wadę, że przy manipulacji łatwo je "przekręcić" (przypominam, że w Brainf**ku pojedyncza komórka przechowuje tylko jeden bajt!), często warto je skonwertować do postaci "0 albo 1". Używając wcześniej zdefiniowanej konstrukcji if-then wykonanie tego jest dość oczywiste - wystarczy zapisać do tymczasowej komórki 1, jeśli sprawdzana wartość to prawda, a potem przenieść zawartość komórki tymczasowej na oryginalne miejsce. Odpowiedni kod wygląda tak: [[-]>+<]>[-<+>]<.

Uzbrojeni w podstawowe instrukcje, możemy zacząć implementować ostatnie brakujące elementy: operatory logiczne i porównania. Zacznijmy od operacji lub. Załóżmy, że oba argumenty są już w postaci "0 lub 1". Użyjemy następującego podejścia: najpierw dodamy argumenty do siebie, a potem używając konstrukcji if-then zamienimy wynik z powrotem do postaci "0 lub 1". Kod: [->+<]>[[-]<+>]<.

Instrukcję negacji nie w zasadzie już napisaliśmy - jest zawarta w konstrukcji if-then-else. Wystarczy w gałęzi else przypisać jedynkę do komórki wynikowej. Kod: >+<[[-]>-<]>[-<+>]<.

Z trójki operacji logicznych najtrudniejsza jest operacja i. Najłatwiej jest ją chyba zapisać z użyciem operacji nie-i oraz negacji. Przypiszmy na początek 2 do komórki tymczasowej:

>>++

Następnie, używając odejmowania (zakładamy, że argumenty są w postaci "0 lub 1"), odejmujemy argumenty od komórki tymczasowej:

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

Teraz w komórce tymczasowej znajduje się 0, jeśli obydwa argumenty miały wartość 1; w przeciwnym wypadku znajduje się tam 1 lub 2. Używając konstrukcji negacji możemy więc obliczyć wynik:

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

Kompletny kod operacji i prezentuje się więc następująco:

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

Na koniec przedstawię, jak wykonywać porównania w Brainf**ku. Aby sprawdzić, czy k jest różne od l, wystarczy wykonać odejmowanie. Jeśli wynik odejmowania jest równy 0, testowane liczby były równe, w przeciwnym razie były różne. Aby sprawdzić, czy k jest równe l, wystarczy zanegować wynik.

Sprawdzenie nierówności jest nieco bardziej skomplikowane. Posłużymy się specjalnym rodzajem odejmowania, takim, który będzie zmniejszać o jeden oba argumenty, dopóki oba są niezerowe. W ten sposób, kiedy odejmowanie się zakończy, to, czy któryś z argumentów będzie niezerowy, powie nam, który z argumentów był początkowo większy.

Ponieważ chcemy powtarzać pętlę, dopóki obie wartości są niezerowe, obliczmy wartość logiczną, która będzie nam mówić, czy rzeczywiście tak jest. Na początek skopiujmy oba argumenty z pierwszej i drugiej komórki do trzeciej i czwartej:

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

Następnie użyjmy operacji i w wersji dla wartości logicznych w stylu C:

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

Jeśli wynik był pozytywny, odejmujemy jedynkę od parametrów:

[-<-<-

W tym momencie znów musimy sprawdzić, czy obie wartości są niezerowe, kopiujemy więc poprzedni kod:

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

Możemy tu zakończyć pętlę:

]

Powiedzmy, że interesuje nas, czy pierwsza liczba była większa, niż druga. Skasujmy więc drugi wynik, a głowicę ustawmy nad pierwszym:

<[-]<

A oto kompletny kod, najdłuższy do tej pory:

[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>]
++<<[[-]>>-<<]>[[-]>-<]<+>>[[-]<<->>]<<
[-<-<-
[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>]
++<<[[-]>>-<<]>[[-]>-<]<+>>[[-]<<->>]<<
]<[-]<
5
Twoja ocena: Brak Ocena: 5 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com