Brainfu**

Started by Thorinbur, May 30, 2010, 12:12:04 PM

Previous topic - Next topic

0 Members and 1 Guest are viewing this topic.

Thorinbur

Dla tych co nie wiedzą co to Brainf***:

Jest to ezoteryczny język programowania, który jest banalny do nauczenia, ponieważ składa się z oośmiu (vol) instrukcji: + - , . < > [ ]

Lecz te 8 instrukcji wystarcza by napisać dowolny program. Zatem czemu jeszcze nie ma translatora: C to Brainf*** (Brainf*** to C jest banalny do napisania)

Otóż nie było jescze wariata który by się za pisanie takowego zabrał. Do dziś...

Najtrudniejszy krok mam już za sobą czyli wymyślenie i skuteczna implementacja operacji wskaźnikowych w brainf***u. (Tak, wskaźniki w brainf***u) a to jest przepustką do dzoałającego translatora, ponieważ w BFie brakuje takich konstrukcji jak stos, sterta, zmienne, instrukcje warunkowe, rejestry procesora, lecz mając działające wskaźniki i pewną wiedzę na temat działania wymienionych elementów nic nie stoi na przeszkodzie by je zaimplmentować w translatorze i móc z nich korzystać tak jak w dowolnym innym języku programowania...

Czemu wogóle to piszę? Ponieważ narzekacie że nic się nie dzieje. Teraz już wiecie co (między innym chodzi po głowie obecnie moderatorowi). Jak ktoś sie chcę przyłączyć do pisania traslatora, to jestem skłonny podzielić się tajemnicą moich wskaźników (choć przyznaję że nie chetnie, bo jeszccze nigdzie do tej pory nie widziałem impementacji tychże w BFie)

A dla tych co nie znają Brainf***a to jego nauczenie sie jest banalnie proste:

Brainf*** operuje na w zaożeniu nieskończonej tablicy (ciągu) zmiennych (wartości), z których każda początkowo ma zero. My możemy swobodnie poruszać się po tej tablicy i dodawać lub odejować wartości. Możemy też wczytywać wartość z klawiatury i wypisywać ją na ekran.

A oto znaczenie wszystkich ośmiu instrukcji.

> przesunięcie się w pamięci o jedna wartość(index) w prawo
< przesuniećie się w pamięci o jedna wartość(index) w lewo
+ dodanie do aktualnie wskazywanej (aktywnej) komórki pamięci 1
- odjęcie od aktualnie wskazywanej (aktywnej) komórki pamięci 1
,  wczytanie kodu ASCII znaku wprowadzonego z klawiatury do aktualnie wskazywanej komórki pamięci
. wypisanie znaku ktorego kod ASCII znajduj się w aktualnie wskazywanej komórce pamięci
[ nawias oznaczający blok instrukcji wykonywanych warunkowo instrukcje za tym znakiem beda wykonywane pod warunkiem, ze wartosc w aktualnie wskazywanej komórce pamięci jest != (różna) od 0 i będa wykonywane aż do momentu dotarcia do znaku:
] który to kończy pętlę rozpoczynaną przez [. Gdy program dochodzi do tego znaku to ponownie sprawdza warunek (aktualna komórka != 0) i program albo wraca do znaku [ albo idzie dalej. Możliwe jest że pętla nie wykona się ani razu w momencie gdy warunek ak != 0 nie będzie spełniony już przy pierwszym sprawdzeniu warunku. Wtedy proram skacze od razu do odpowiedniego ] omijajac wszystkie instrukcje wewnątrz pętli. Co ciekawe w brainf***u przy każdym sprawdzeniu warunku zienna sterująca może być inna, co jest niemożliwe w innych językach programowania (trzeba by tam użyć wskaźników)

Mój pomysł na translatora polega na prostym zastępowaniu fragmentów w C na fragmenty w Brainf***u, przynajmniej początkowo, gdyż ewentualna ostateczna wersja przypominała by kompilator, gdyż bF jest nawet prostrzy od assemblera. Aktualnie próbuję znajleźc BFowe odpowiedniki wszystkich funkcji warunkowych oraz sposób implementacji konstrucji if, else, które natywnie nie występują w BFie.

Największym problemem wydaje się być sprawdzanie znaku liczby. Innym problemem jest także zapis liczb. Część implementacji BF'a zaklada że w pojedyńczej komórce można zpisywać wartości od 0 do 255, co by oznaczało ze pojedyńcze wartości są jedno bajtowe. Wtedy rozwiązanie problemu parzystości było by zaps w systemie U2. Wymaga to jednak też sporo roboty przy zwykłym odawaniu, ale hej.. to jest Brainf***. To nie ma  być proste! to ma być ciekawe!


Małe podsumowanie najbardziej podstawowych elementów języka C które powinny zostać przeniesione jako pierwsze:

Typy:
char
short
int
long
float
double
long double

operatory arytmetyczne:
+
-
*
/
%

operatory relacji:
==
!=
<
>
<=
>=

Kolejne istotne elementy to:
wskaźniki i tablice

instrukcje sterujące:
if, switch, main

jako że BF ma "wbudowaną obsługę wejścia i wyjścia" do listy dodajmy jeszcze instrukcję cin i cout (strumienie) by móc przetwarzać większość prostych programów.

A więc zacznijmy (nawet jak nikt tego nie czyta, albo czyta tylko z ciekawości to będe pisał dalej, bo równie dobrze mogę pisać to dla siebie w notatniku, albo tu, gdzie komuś może się to spodobać i może sie przyłączyć (ilośc kodu do napisania jest naprawdę duża)

Reprezentacja i typy
Język programowania bez zmiennych nie ma prawa istnienia. Każdy program musi przyjmować jakieś dane i coś z nimi robić. Taka jest definicja programu (mniej więcej) W brainfu**u operujemy gołą pamięcią dlatego typy zmiennych i ich rerezentacja oraz kontrola to zadanie dla programisty oraz kompilatora. Jako że w brainfu**u to nie istnieje więc rozróżnianie, pamiętanie, kontrola i reprezentacja to zadanie dla translatora.

Dlatego najlepiej będzie przyjąć jakąś stałą reprezentację jako że słowo ma 4 bajty(32 bity, nie bawimy się w 64 bity), to niech pamięć będzie podzielona na kawałki po 8 zmiennych (4 na wartość i 4 pomocnicze, wierzcie mi, przydadzą się i to bardzo, a w zalożeniu pamięć mamy nieskończenie długą, poza tym to zmniejszenie efektywnej wielkości pamięci tylko o połowe). Zatem jak już podzieliliśmy pamięć to kolejne fragmenty będziemy oznaczać jako 0x00000000, 0x00000001, 0x00000002 itd, natomiast kolejne bajty (po osiem w każdej zmiennej jako :0, :1, :2 itd, zatem pełen adres do konkretnego bajtu to na przykład 0x00000009:6. Jest to bardzo istotne by mieć dobrze określony i przemyślany sposób adresowania, gdyż w brainfu**u STRASZNIE dużo skacze się po pamięci i trzeba cały czas dokładnie kontrolować gdzie się jest, bo tutaj operuje się na gołej pamięci i jakakolwiek pomyłka będzie mieć straszne konsekwencje!

Typy:

char
Tak jak w rzeczywistości stracimy tutaj trochę pamięci gdyż bajty :1 :2 i :3 nie będą wykorzystywane. Jedynie bajty :0 i :4, :5, :6 i :7

short
int
long (brak long long)
Te typy dla uproszczenia wszystkie będziemy zastępować przez typ long (aktualnie zazwyczaj long = int) i będą to liczby całkowite w zapisie U2 (uzupełnieniowym do 2)

float
zapis dokładnie jak we współczesnych komputerach:
http://en.wikipedia.org/wiki/Single_precision

double podobnie jak single tylko zajmuje 2 zmienne (16 brainfu**o-bajtów)
double


Operatory:

Tutaj zaczyna się prawdziwa zabawa! Szczególnie przy tej dość nietypowej reprezentacji liczb.
Przed wykonaniem samej operacji dodawania należy przede wszystkim rozpoznać typy dodawanych zmiennych, więc mamy aż 6! typów zmiennych co daje razem 36 wersji operatora, (25, bo long i int zachowują się tak samo).
W procesorze operacjami arytmetycznymi zajmuje się akumulator i operuje na samych słowach. My niestety możemy dodawać tylko o jeden. Największym problemem dodawania jest przenoszenie do kolejnych bajtów. Trzeba wiedzieć kiedy wartość w bajcie osiągnęła 255 i należy dokonać takiego przeniesienia. Najprostszym sposobem było by porównanie po prostu wartości w bajcie z liczbą 255. Niestety takie porównanie nie jest w brainf***u ani proste, ani szybkie. Dodatkowo samo w sobie wymaga użycia operacji, lecz jako, że działanie Brainf***a w przypadku przepełnienia nie zostało sprecyzowane, to mamy tu pewną dowolność i możemy,  (przynajmniej początkowo) założyć, że przeniesienie takie będzie następować automatycznie w przypadku przepełnienia zmiennej do komórki sąsiedniej. W takim przypadku dodawanie bez obsługi przepełnien było by dość proste przy typach takich jak char, int short i long, ponieważ wymagały by jedynie wywołania odpoweidniej ilości plusów na zmiennej docelowej. Wynik dodawania obliczany jest zazwyczaj i zapamiętywany do rejestru procesora, dopiero potem może okazać się że należy go przypisać do jednej ze zmiennych będących argumentem, zapisać do innej zmiennej, użyć do dalszych obliczeń czy jako argument, zatem i my musimy tak zrobić. W tym celu musimy wydzielić pewną ilość zmiennych na potrzeby symulacji rejestrów procesora. Jest to bardzo istotne, gdyż w rejestrach zazwyczaj znajdują się krytyczne zmienne, adresy szczytu stosu itp. Narazie trudno mi powiedzieć ile takich rejestrów będzie faktycznie potrzebnych, dlatego nie posługuję się konkretymi adresami. Co do dodawania zmiennej z pod konkretnego adresu do zmiennej pod innym adresem, mam to zapisane w notatniku i na razie nie chcę się dzielić moim rozwiązaniem dot wskaźników jestem z niego taki dumny! XD

Co do operacji dzielenia i mnożenia. Mnożenie można łatwo zrealizować za pomocą wielokrotnego dodawania, natomiast dzielenie, chyba najłatwiej będzie poprzez odejmowanie i zliczanie, tak więc mając dodawania oraz operację odwracania możemy już wykonywać dowolne operacje arytmetyczne. Na właściwe kawałki kodu przyjdzie jeszcze czas.

Zajmijmy się tym co faktycznie nie jest takie oczywiste, czyli instrukcjami warunkowymi, które nie istnieją w BFie:

Instrukcje sterujące:
Jedyną instrukcją sterującą w BFie jest instrukcja while( *akt != 0){ };
Co znaczy mniej więcej dopóki wartość wskazywana w momencie sprawdzania warunku jest różna od 0; Trzymając liczby w zapisie U2, łatwo sprawdzimy też ich znak, czyli łatwo to przerobić a while( *akt <0) lub while( *akt >= 0) gdyż sprowadzają się one do prawdzenia czy 4 bajt jest mniejszy czy większy od 127. Jeśli większy to liczba jest ujemna, ale jak zrobić instrukcję if? Ponieważ wiemy, że wartości w pamięci są dodatnie wystarzczy sprawdzić czy uda nam się odjąć od niej 128 razy nie spadając poniżej zera, W C++ wyglądało by to mniej więcej tak:

Powiedzmy że chcemy sprawdzić wartość pod adresem 0x00000032
Więc udajemy się pod ten adres



bool wieksza=1;
int pomocnicza = 128;
While(*akt != 0){ //czyli posdstawowa pętla w brainf***u
 while(pomocnicza != 0 && *akt!=0){
   akt--;
   if(*akt==0)
     wieksza=0; //jeśli osiągneliśmy 0 zanim pomocnicza spadła do 0 to znaczy ze akt była mniejsza.
  }
}


Mimo że występują tu instrukcje if oraz while to wszędzie porównujemy z zerem i łatwo je przetłumaczyć na wersje w BFie.
Można też łatwo ten fragment kodu uogólnić, by porównywać z dowolną wartością z zakresu 0-255.
wystarczy pożadaną wartość wstawić zamiast 128 do zmiennej pomocnicza, a zatem tak wyglądała by organizacja pamięci:


0x00000032  
:0 wartosc porownywana
:1 reszta bajtow warotości
:2       -        ||        -
:3       -        ||        -
:4  zmienna pomocnicza (wartość porównywana)
:5  inna zmienna pomocnicza (pomoże nam w wychodzeniu z pętli)
:6  inna zmienna pomocnicza (nie używana)
:7  odpowiedź, po zakończeniu działania funkcji jeśli = 1 to znaczy ze wartość zmiennej była większa.


każdy fragment kodu zaczynam w :0
tak więc jesteśmy pod 0x00000032:0

Listing 01, porównywanie wartości
bool wieksza = 1
>>>>>>>+
int pomocnicza = 128
<<<
0x00000032:4 (porównywana)
                                                          teraz moglbym wpisac 127 plusów, ale w BFie zazwyczaj korzysta sie z sąsiedniej zmiennej (a w tym przypadku to zmienna pomocnicza = 0 i chwilowo nie uzywana) by skrócić zapis
>++++++++++++(12)[<++++++++++(10)>-]<++++++++(8)
                                                          po tej operacji w 0x32:4 jest wartość 128 wartosc w 5 nie zmieniła się

....... To be continued



oel kame futa oel kekame ke'u

rodrygo

hmmm

No to jak zdefiniować zmienną? np. liczbową, rzeczywistą


Thorinbur

W oryginalym Brainfu**u nie da się. Masz po prostu pamięć. W C, C++ typ, potem nazwa (int nazwa_zmiennej;). W brainfucku zazwyczaj zapisujesz gdzieś sobie na boku, lub nawet komentarzem w samym programie, ze po takim to a takim adresem jest zmienna taka to a taka. Więc w tym przypadku bedzie to zadanie translatora, zapamiętywanie i spamiętywanie nazw i typów zmiennych.
oel kame futa oel kekame ke'u

Kxortelung

Ja tam programuję w QuickBasicu. Może i jest to trochę przestarzała technologia, bo współpracuje jedynie z DOSem, ale za to jest niezwylke prosty i skuteczny.
Piszę w tym momencie opisowy symulator lotów kosmicznych. Będzie można dolecieć nawet na Pandorę.  ;)

Thorinbur

Czemu nie piszesz w C/C++. Nie musisz przecież kożystać z jakichś pokręconych elementów. A jest powód dla którego obiektowość jest tak popularna. Taki opisowy sumulator to nic innego jak zmienne, stringi tablice i couty XD w C++ również nie skomplikowane. A w chwili obecnej uczę się jescze jednego języka: Unreal Script
oel kame futa oel kekame ke'u

Kxortelung

Quote from: Thorinbur on May 31, 2010, 12:59:14 PM
Czemu nie piszesz w C/C++. Nie musisz przecież kożystać z jakichś pokręconych elementów. A jest powód dla którego obiektowość jest tak popularna. Taki opisowy sumulator to nic innego jak zmienne, stringi tablice i couty XD w C++ również nie skomplikowane. A w chwili obecnej uczę się jescze jednego języka: Unreal Script

Takie mam hobby ;D Nie ma to jak DOS  ;) Symulator jest stylizowany na science-fiction lat 70-tych (zielony ekran, rozkazy z PRL na starcie  :)). Poza tym QuickBacic jest bardzo przejrzysty. Czytałem o C++, i prawdę mówiąc przeraziłem się. Za dużo znaków "<,+,=", za mało opisów. Na dłuższa metę być może jest to pomocne, ale ja przecież nie programuję zawodowo. Dużo bardziej wolę zwyczajne polecenia typu PRINT, INPUT, SELECT CASE i numerację listy  :). Jedyna wada to potrzeba DOSboxa na Windowsie 7.

Thorinbur

W c++ masz to wszystko. Tak jak mówiłem. To tak jak hmm... otwieranie piwa nożem i scyzorykiem. Niby nożem się da i nie jest to takie trudne. Ale w scyzoryku masz otwieracz i masę innych rzeczy. Nikt ci nie każe z nich korzystać. Mimo wszystko warto je miec.
oel kame futa oel kekame ke'u

Kxortelung

Quote from: Thorinbur on June 02, 2010, 07:02:43 AM
W c++ masz to wszystko. Tak jak mówiłem. To tak jak hmm... otwieranie piwa nożem i scyzorykiem. Niby nożem się da i nie jest to takie trudne. Ale w scyzoryku masz otwieracz i masę innych rzeczy. Nikt ci nie każe z nich korzystać. Mimo wszystko warto je miec.
Tyle, że ja programuję dla samej przyjemności programowania w DOSie, a nie dla funkcjonalności (Wiem - dziwny jestem  :)) Wszystkie BASIC-i, czy to w Commodore 64, czy w Amidze są oparte na tej samej zasadzie i tych samych poleceniach.

rodrygo

ja też lubię różne basic-ki :-)
Jak zaczynałem się uczyć komputera to były jeszcze 8-bitowe procesory.

basic zastępował tam system operacyjny i było fajnie.

obecnie już nie nadążam za nowosciami...

wiecie może
czy są jeswzcze w użyciu takie twory jak basic, pascal, fortran?  bo C++ jest, jak pisze nasz mod  ;)

Thorinbur

basic, bardziej w wersji visual basic w tej chwili. pascal, jest funkcjonuje, nawet jak na studiach uczyli mnie programowania proceduralnego to właśnie na Pascalu (n szczęście w 2gim semestrze przeszli na C++, po drodze zachaczając o Javę) Fortran, nie. Fortran to już przeszłość, może jeszcze ew jakieś specjalistyczne maszyny programuje się w fortranie, bo z tego co kojarzę to bardzo matematyczny język.
oel kame futa oel kekame ke'u