Programozzunk C#-ban 8. rész
Ebben a részben egy komolyabb programot fogunk elkészíteni, ami egy Turing gép emulátor lesz, pontosabban a BrainFuck programozási nyelv egy implementációja.
A Turing gép a nevét Alan Turing angol matematikusról kapta. Ez egy matematikai modell a számítógépek egyszerűsített leírására. A modellt 1936-ban publikálta legelőször és ezzel forradalmasította a számítástechnikát, olyannyira, hogy minden számítógép lényegében egy Turing gép. Turing publikációja azért is zseniális, mivel ha van egy probléma és annak a megoldására kreálni tudunk egy algoritmust, akkor az algoritmus megoldásra építhető a Turing modellen alapuló gép.
A Turing gép működése
A működési leírás forrása a Wikipedia.
A gép négy fő egységből áll:
- Egy cellákra osztott végtelenített papírszalag formában létező memória (szalagmemória, szalagtár, társzalag); minden cellában a gép által megértett nyelv betűi, azaz a Tár-abc egy-egy betűje van írva.
- Egy vezérlőegységből, mely a gép programját tartalmazza; a vezérlőegység különböző időpillanatokban különféle belső állapotokban létezhet
- Egy író-olvasó fejből (I/O-fej), mely szimbólumokat ír vagy olvas a szalag celláira (ahogy a valóságos számítógépek betűket írnak ki a monitorra vagy a nyomtatóban lévő papírívre).
- Egy átmenettábla, ami vezérli a gép működését, megadva, hogy adott szimbólum beolvasásának hatására adott állapotban mit tegyen: hogyan mozogjon, milyen szimbólumot írjon a tárra, és milyen belső állapotba kerüljön.
A Turing gépnek minden időben van egy aktuális pozíciója a memóriaszalagon, amely pozíciónál az aktuális cella helyezkedik el. Minden időben van egy állapota, amely az aktuális állapot. Az aktuális állapotok definiálása része a gép programozásának.
A gép minden lépésben beolvas egy szimbólumot a társzalag aktuális cellájából, ezután a program attól függően, hogy az aktuális állapota milyen és a beolvasott szimbólum a gép ábécéjének melyik betűje, a következő három lehetőség közül az egyiket írja elő:
- Az aktuális cellába beír egy meghatározott szimbólumot.
- Az olvasófej a társzalagon balra vagy jobbra lép, esetleg helyben marad.
- A gép (vezérlőegysége) átvált az éppen aktuális állapotból (amelyben éppen van, abból) egy másikra (az új állapot persze lehet ugyanaz, mint az aktuális). Egy speciális állapot a „stop-állapot”, amely után a Turing-gép a programozása szerint megáll.
Az időbeli lefutást leírva a gép beolvas, változtat, mozog, és aztán ez a ciklus újra kezdődik: azon a cellán, amelyre mozgott, ismét beolvas, változtat, majd lép. Így megy ez, s eme folyamatnak a gép programozásától és az elvégzendő feladattól függően kétféle kimenetele lehet:
- Szabályos megállás (terminálás): a gép leálló belső állapotba („stop-állapot”) kerül;
- „Elszállás”: a gép végtelen ideig fut. A legegyszerűbb módon ez úgy lehet, hogy egy végtelen ciklusba kerül, de más módon is futhat végtelen ideig, mert egyszerűen sosem kerül „stop-állapotba”.
A BrainFuck programozási nyelv
A BrainFuck az egzotikus programozási nyelvek közé sorolható. A név arra utal, hogy nem a legkönnyebb programozási nyelv, viszont egy teljes Turing gép implementáció, így elméletileg bármilyen bonyolult program megírható benne.
A nyelv szerkezete és értelmezése egyszerű. Egy 30 000 byte-ból álló memóriaterületen tudunk műveleteket végezni. A memória szervezése byte alapú, tehát egy rekesz értéke 0 és 255 között változhat. Alapesetben a memória összes rekeszének értéke 0-ról indul. A memória címzéséhez egy változó van rendelve, ami indításkor a tömb elejére (0. elem) mutat.
A változót pointernek hívjuk. Az aktuálisan feldolgozott utasításhoz is tartozik egy pointer, amit utasítás pointernek nevezünk. A nyelv nyolc utasítását egy-egy karakter reprezentálja. Ezek:
- >
A pointer növelése eggyel - <
A pointer csökkentése eggyel - +
A pointer által mutatott memóriarekesz értékének növelése eggyel - –
A pointer által mutatott memóriarekesz értékének csökkentése eggyel - .
A pointer által mutatott memóriarész kiírása a képernyőre - ,
A pointer által mutatott memóriarészbe egy byte bekérése a billentyűzetről - [
Ha a pointer által mutatott memóriarekesz értéke 0, akkor ahelyett, hogy az utasítás mutató értékét növelnénk eggyel, addig növeljük, míg az aktuális [ jelhez tartozó ] jel utáni parancsot meg nem találtam. - ]
Ha a pointer által mutatott memóriarekesz értéke nem 0, akkor ahelyett, hogy az utasítás mutató értékét növelnénk eggyel, addig csökkentjük, míg az aktuális ] jelhez tartozó [ jel utáni parancsot meg nem találtuk.
Az implementáció
Az implementáció megvalósítható lenne két módon is: fordítóprogram segítségével és feldolgozóval. A feldolgozó program előnye, hogy jelen esetben könnyebb megírni, mivel a BrainFuck egy igen egyszerű állapotgép, valamint nem igen jellemző, hogy több millió soros programokat kreáljanak ezen a nyelven emberek, így az értelmező lassúsága nem igen jelent komoly problémát.
A készülő feldolgozónk egy konzol alkalmazás lesz, mivel a BrainFuck alapvetően egy parancssoros alkalmazás. Mivel egy konzol alkalmazás önmagában nem igen modern, ezért a megvalósításom azt az extra funkcionalitást tartalmazza, hogy képes programot betölteni a vágólapról vagy fájlból.
A fájl betöltése nem parancssorosan történik, hanem a Windows beépített fájl megnyitás ablakának segítségével.
Korábban nem volt még szó a grafikus felületekről. Alapvetően kétféle grafikus keretrendszer van a .NET-be beépítve: a Windows Forms és a Windows Presentation Foundation.
A Windows Forms kompatibilitási okokból van a rendszerben. Ennek az alapja a GDI, ami a Windows része 1995-ös megjelenése óta. Ezen könyvtár legnagyobb problémája, hogy szinte teljesen szoftveres a megjelenítés rajzolása. Tehát a képernyőre történő rajzolás leginkább a rendszer memóriát és a CPU-t fogja terhelni.
A WPF a modern grafikus alrendszer, ami a DirectX-re támaszkodik. Ebből adódóan a rajzolási folyamatot szinte teljes egészében a videovezérlő végzi.
Modern, komplex alkalmazás fejlesztéshez ma már leginkább a WPF ajánlott. A fájl megnyitás ablakunkat a programunk viszont a Windows Forms-ból fogja importálni. Ennek oka az, hogy ez kevesebb erőfeszítéssel jár, mivel csak egy extra szerelvény csomagot kell hozzáadni az alkalmazáshoz.
A szerelvény csomagok lefordított .NET kódot tartalmaznak binárisan. Lényegében a lefordított EXE fájlunk is egy szerelvény csomag. Azonban léteznek olyan szerelvények, amelyek önmagukban nem futtathatóak, viszont más futtatható szerelvények számára kódot tartalmaznak.
Ezek használatához nem kell semmi extra ismeret, csupán a szerelvényt referenciaként hozzá kell adni a projektünkhöz. Ezután a szerelvényben található névterek és azok publikus osztályai ugyanúgy használhatóak a kódunkból, mintha mi írtuk volna őket.
Visual Studio esetén a szerelvény hozzáadásnak két lépése van. Első lépésként ki kell nyitni a Solution Explorer-ben a projektünket, majd jobb gombbal kell kattintani a References mappán. A felugró menüben pedig az Add Reference… menüt kell választani.
Ennek hatására megnyílik a referencia választó ablak. Referenciát hozzáadhatunk külső (DLL) fájlból, a Solution-ből, vagy a keretrendszerből. Jelen esetben a keretrendszerből szeretnénk referenciát felvenni, ezért az ablak jobb oldalán található keresés mezőbe beírjuk a következőt: System.Windows.Forms
A keresési találatot ki kell jelölni, majd az előtte található dobozba egy pipát kell tenni,így az OK gombra kattintva fel is vettük a referenciánkat.
A kész programot két osztályra bontottam. A teljes értelmező a BrainFuck osztályban kapott helyet:
using System; using System.IO; using System.Windows.Forms; namespace _17_brainfuck { internal class BrainFuck { /// <summary> /// Adat memória /// </summary> private byte[] _memory; /// <summary> /// Brainfuck kód /// </summary> private string _code; /// <summary> /// Memória Limit /// </summary> private int _maxmemory; /// <summary> /// Memória mutató /// </summary> private int _MemPtr; /// <summary> /// Aktuális utasítás mutató /// </summary> private int _IPtr; public BrainFuck(int maxmemory = 4096) { _maxmemory = maxmemory; _memory = new byte[_maxmemory]; _MemPtr = 0; } /// <summary> /// Hibaüzenet megjelenítése /// </summary> /// <param name="hiba">Üzenet tárgya</param> private void Error(string hiba) { MessageBox.Show(hiba, "Hiba", MessageBoxButtons.OK, MessageBoxIcon.Error); } /// <summary> /// Kód betöltése a vágólapról /// </summary> public void LoadClipboard() { if (Clipboard.ContainsText()) _code = Clipboard.GetText(); else Error("A vágólapon nem szöveges infromáció található."); } /// <summary> /// Kód betöltése egy TXT fájlból /// </summary> public void LoadFromFile() { try { //megnyitás ablak létrehozása OpenFileDialog ofd = new OpenFileDialog(); //kiterjesztések beállítása ofd.Filter = "Szöveges fájlok | *.txt"; ofd.CheckFileExists = true; if (ofd.ShowDialog() == DialogResult.OK) { FileInfo fi = new FileInfo(ofd.FileName); if (fi.Length > _maxmemory) { Error("A betölteni kívánt fájl nagyobb, mint az értelmező memória korlátja!"); return; } //using direktíva az IDisposable interfész miatt using (TextReader tx = File.OpenText(ofd.FileName)) { //a fájl egész tartalmát beolvassuk a memóriába _code = tx.ReadToEnd(); } } } catch (Exception ex) { Error("Hiba történt a fájl mengyitása,beolvasása közben:\r\n" + ex.Message); } } /// <summary> /// Értelmező alapállapotba állítása /// </summary> public void Reset() { _code = null; _memory = null; //szemétgyüjtő kényszerített hívása. Első híváskor általában a destruktorokat hívja meg GC.Collect(); //megvárjuk a folyamatban lévő destruktor futást GC.WaitForPendingFinalizers(); //Szemétgyüjtő meghívása megint, tényleges memória felszabadítás GC.Collect(); _memory = new byte[_maxmemory]; _MemPtr = 0; _IPtr = 0; } /// <summary> /// Ciklus eleje /// </summary> private void LoopStart() { int bal = 1; if (_memory[_MemPtr] == '\0') { do { _IPtr++; if (_code[_IPtr] == '[') bal++; else if (_code[_IPtr] == ']') bal--; } while (bal != 0); } } /// <summary> /// Ciklus vége /// </summary> private void LoopEnd() { int bal = 0; do { if (_code[_IPtr] == '[') bal++; else if (_code[_IPtr] == ']') bal--; _IPtr--; } while (bal != 0); } /// <summary> /// Brainfuck program futtatása /// </summary> public void Run() { while (_IPtr < _code.Length) { switch (_code[_IPtr]) { case '>': ++_MemPtr; break; case '<': --_MemPtr; break; case '+': _memory[_MemPtr]++; break; case '-': _memory[_MemPtr]--; break; case '.': Console.Write((char)_memory[_MemPtr]); break; case ',': var key = Console.ReadKey(); _memory[_MemPtr] = (byte)key.KeyChar; break; case '[': LoopStart(); break; case ']': LoopEnd(); break; } ++_IPtr; if (_MemPtr > _maxmemory) throw new Exception("A memória pointer túlment a maximális memória határon"); if (_MemPtr < 0) throw new Exception("A memória pointer negatív memóriába mutatott"); } } } } |
Az esetleges hibák megjelenítéséért az Error függvény a felelős, ami a MessageBox típus Show metódusát hívja meg. A Show metódus első paramétere az ablakban megjelenő szöveg, második paramétere az ablak fejléc szövege. A harmadik paraméter az ablakban megjelenő gombok egy meghatározott kombinációja, míg az utolsó paraméter az ablakhoz tartozó ikon, ami szintén egy meghatározott listából kerülhet ki.
A megnyitás ablak típusa az OpenFileDialog. Ezen dialógus ablak egyik legfontosabb paramétere a Filter. Ez határozza ugyanis meg, hogy milyen kiterjesztésű fájlok nyithatóak meg. A filter szöveg minden esetben az alábbi felépítést kell, hogy kövesse: leírás|*.kiterjesztés1;*.kiterjesztés2
C# esetén a fájlkezelés Stream alapú. A fájlkezeléshez és egyéb be -és kimenetekhez kapcsolódó osztályok a System.IO névtérben kaptak helyet. Ezen névtérhez tartozó szerelvény alapértelmezetten bekerül a projektbe, így nem kell külön hozzáadni.
A FileInfo osztály a fájlokról képes információkat lekérdezni. Ezen információk közül a leghasznosabb jelen pillanatban a fájl mérete. Ha az nagyobb, mint a maximális program méret (jelen implementációban 4kb), akkor a betöltés sikertelen lesz.
A TextReader osztály kifejezetten szöveges fájlok beolvasására szolgál. A beolvasás egy using blokkban van megvalósítva. Using blokkban csak IDisposable felületet megvalósító osztályok szerepelhetnek. Az IDisposable felületet minden olyan objektumnak implementálnia kell, amely nem csak menedzselt memóriával és erőforrással dolgozik. A fájlok pedig tipikusan ilyenek, mivel ezek kezelését az operációs rendszer valósítja meg.
A using előnye, hogy a blokk végén automatikusan felszabadul a blokkban használt erőforrás, így véletlenül sem fordulhat elő az, hogy a fájlt elfelejtjük bezárni. A fájl bezárásának elmaradása azért problémás, mert az olvasás végeztével is zárolva marad a fájl és más program, a felhasználó nem tud addig hozzáférni annak a tartalmához.
A kód értelmezése a Run() függvényben van megvalósítva egyszerű switch-case szerkezettel. A ciklus kezeléshez tartozó megfelelő zárójel keresésről a LoopStart() és LoopEnd() metódusok gondoskodnak.
A főprogram:
using System; namespace _17_brainfuck { class Program { //statikus szál modell alkalmazása. //ha ez nincs itt akkor a vágólapot nem tudja elérni //a konzol alkalmazásunk [STAThread] static void Main(string[] args) { BrainFuck bf = new BrainFuck(); ConsoleKeyInfo key; while (true) { Console.Clear(); Console.WriteLine("BrainFuck#"); Console.WriteLine("1. Program futtatás vágólapról"); Console.WriteLine("2. Program futtatása fájlból"); Console.WriteLine("ESC Kilépés"); Console.WriteLine("---------------------------------------"); Console.Write("Válasz: "); key = Console.ReadKey(); //esc gombra kilépés if (key.Key == ConsoleKey.Escape) break; bf.Reset(); switch (key.KeyChar) { case '1': bf.LoadClipboard(); break; case '2': bf.LoadFromFile(); break; default: continue; } try { Console.WriteLine(); Console.WriteLine("A program kimenete:"); bf.Run(); } catch (Exception ex) { Console.WriteLine("Hiba történt a futtatásnál: " + ex.Message); } Console.WriteLine(); Console.WriteLine("---------------------------------------"); Console.WriteLine("A folytatáshoz nyomj egy gombot..."); Console.ReadKey(); } } } } |
A főprogram a BrainFuck osztályt veszi használatba, egyetlen újdonság benne a main előtt található attribútum. C# esetén az attribútumok segítségével lehet jelezni dolgokat a keretrendszernek. A most használt [STAThread] attribútum azt állítja be, hogy az attribútum által megjelölt rész szál modellje statikus, egy szálon futó legyen. Ez azért kell, mert máskülönben nem fog tudni a programunk kommunikálni a Windows többi részével üzenetek segítségével. Ez leginkább dialógus ablakok megjelenítéséhez kell, valamint jelen esetben leginkább a vágólap eléréshez, mivel a vágólap szintén Windows üzenetekkel kommunikál a többi alkalmazással.
Végszó
A kész feldolgozónkat érdemes tesztelnünk. A legegyszerűbb BrainFuck program szerintem az alábbi hat karakteres csoda, ami kiírja az ASCII kódtáblát a képernyőre:
.+[.+]
A Hello World kód némileg összetettebb:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.——.——–.>+.>.
Az alábbi kód pedig a program egy rövid névjegye, ami a C# BrainFuck feldolgozo – https://webmaster442.hu üzenetet jeleníti meg 🙂
++++[++++>—<]>.+[–>+<]>+.—.+[->++<]>.—[—–>+<]>-.+++[->+++<]>++.++++++++.+++++.-[->+++<]>-.[++>——-<]>.+[->+++<]>+.++++++++.-[++>—<]>+.++[->+++<]>.-.+++++++.——–.+++++++++++.—.—–.++++++++.-[—>+<]>.[->+++<]>+.[—>+<]>—–.–[–>+++<]>.[—>++<]>++.-[—>++<]>–.++++++++++++..—-.[–>+<]>++.———–..++[—>++<]>+.[->+++<]>.—.+++++++++++.————.–[—>+<]>–.+.+++[->+++<]>.+++++++++++++.[–>+<]>—–..–.—-.+[—>+<]>+++.[—>+<]>—.
A program forráskódja szokásosan a GitHub oldalon található meg.