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:

1. 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.
2. 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
3. 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).
4. 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ő:

1. Az aktuális cellába beír egy meghatározott szimbólumot.
2. Az olvasófej a társzalagon balra vagy jobbra lép, esetleg helyben marad.
3. 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:

1. Szabályos megállás (terminálás): a gép leálló belső állapotba („stop-állapot”) kerül;
2. „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.