NézetNyomtat

AgyKacsa (Megoldás)
Címkék > Feladat

AgyKacsa

Bevezetés

Az AgyKacsa a világ egyik legegyszerűbb programozási nyelvének egy variánsa. Ennek a programozási nyelvnek mindösszesen nyolc utasítása van, és mindegyik pontosan egy karakter hosszú. A nyelv mégis Touring-teljes, tehát bármilyen algoritmikus probléma megoldható vele. Nyolcféle karakter használatával nem könnyű programozni, valószínűleg ezért is nevezték az eredeti nyelvet Brainfucknak. Unatkozó programozók körében ez egy nagyon népszerű programozási nyelv, egy keresőbe beírva rengeteg megírt példaprogramot találhatunk rá. Az eredeti nyelv egyetlen dologban tér el az AgyKacsától, mégpedig a nevében, hogy tekintettel legyünk kiskorú olvasóinkra. Tehát az interneten talált Brainfuck példaprogramok tökéletesen futtathatók lesznek AgyKacsában is.

a nyelv leírása

Alapmodell

Hogy az AgyKacsa programok működését megértsük, először el kell képzelni egy egyszerű számítógép-modellt. Ennek a számítógépnek:
  • van egy 30,000 cella méretű memóriája, melyben minden cella pontosan egy byte-ot tárol, és kezdetben mindegyik tartalma a nulla szám.
  • van egy mutatója is, ami mindig a memória egyik cellájára mutat, kezdetben a legelsőre. Ezt a kijelölt cellát aktuális cellának nevezzük.
A lehetséges utasítások:
KódLeírás
>Jobbra lépteti a mutatót eggyel
<Balra lépteti a mutatót eggyel
+Növeli az aktuális cellában lévő értéket eggyel
-Csökkenti az aktuális cellában lévő értéket eggyel
A memóriában lévő számok növelése és csökkentése esetén körberfordul az érték, 255 növelése esetén 0-ra, 0 csökkentése esetén 255-re. Példa:
++++++++++
++++++++++
++++++++++
++++++++++
++
>
+++
hihihi-hahaha
A fenti program utasításait sorban kell értelmezni. A nyelvben nem szereplő karaktereket figyelmen kívűl kell hagyni: például a szóközöket, sortöréseket, az angol ábécé betűit, stb. Ez a program beírja a 42 számot az első cellába, majd az 2 számot a másodikba. Miért nem a hármat? Mert az utolsó sorban van egy - parancs, ami visszacsökkenti a cella értékét kettőre. Az ismeretlen karakterek azért megengedettek a nyelvben, hogy könnyű legyen kommenteket írni.

Bemenet és kimenet

Az előbbi utasítások segítségével már sokféle programot lehet írni, de ezek a külvilággal még nem tudnak kommunikálni. Úgyhogy léteznek még a következő utasítások is:
KódLeírás
.Kiírja a mutatott cellában lévő értéket a képernyőre karakterként
,Beolvas egy karaktert a bemenetről és beírja a mutatott cellába
Látszólagos ellentmondás, hogy a memóriában bájtok vannak, kiírásnál és beolvasásnál pedig karakterekről beszélünk. Ennek a feloldása az, hogy minden karakterhez egy szám van hozzárendelve, és valójában ezt tárolja minden számítógép és ezt használja minden program. Csak mi, a képernyőn látjuk karaktereknek őket. Az angol ábécé betűihez és a gyakoribb írásjelekhez rendelt számokat az ASCII szabvány határozza meg, és bőven kisebbek 255-nél, tehát beférnek egy bájtba. Példa:
,>,
<
-.>+.
Beolvas két karaktert, az elsőnél kiírja az egyel kisebb kódú karaktert, a másodiknál pedig az egyel nagyob kódú karaktert. Például ha a bemenet:
35
Akkor a kimenet:
26
Ne feledjük, hogy itt karakterkódokról volt szó, tehát ha például a második karakter egy 9-es, akkor ennek kódja fog a memóriába beolvasódni, ami 57, és ezt egyel megnövelve 58-at kapunk, ami a kettőspont karakter kódja.

Feltételes szerkezet

Amíg nincs feltételes szerkezet - elágazás, ciklus vagy feltétes ugrás, stb. - egy programozási nyelvben, addig erősen korlátozott, hogy milyen programokat lehet benne írni.
KódLeírás
]Mindig párban áll egy [ utasítással. (Egy páron belül lehetnek további párok.) A végrehajtás az utasítás párján folytatódik.
[Ha az aktuális memóriacellában nulla van, akkor az ehhez az utasításhoz párosítható ] utasítás után következő utasításhoz ugrik, és onnan folytatja a program végrehajtását. Ha az érték nem nulla, akkor a következő utasításnál folytatódik a végrehajtás.
Példa:
[-]
Addig csökkenti az aktuális cella értékét, amíg az nem lesz nulla. Másszóval nullára állítja be. Ez akkor hasznos, ha nem tudjuk mi ez az érték, egyébként megfelelő számú minusz-jel is megfelelne.

feladat

Feladatunk készíteni egy AgyKacsa interpretert. Egy interpreter egy olyan program, ami végrehajt egy más nyelven írt programot. Lépések, amik után tesztelni érdemes:
  1. AgyKacsa programkód beolvasása egy fájlból egy stringbe. (teszt: String kiírása képernyőre.)
  2. Az alapmodell utasításainak megvalósítása. (teszt: Az ott látható példaprogram lefuttatása. A teszteléshez készítsünk egy dump() nevű segédfüggvényt, ami kiírja az első néhány memóriahelyen tárolt értéket szám és karakter formájában is.)
  3. A bemeneti és kimeneti utasítások megvalósítása. (Teszt: a példaprogram használata, beolvasott karakterek kiírása például "beolvasva: karakter szám" formában.)
  4. Részfeladat: nyitózárójel csukó párjának megkeresése egy stringben; csukózárójel nyitó párjának megkeresése stringben. (Ezeket külön függvénybe érdemes írni, és tesztelni őket egy külön programban.)
  5. A részfeladat megoldását felhasználva a feltételes utasítások megvalósítása. (teszt: az ott látható példa)
És most már lefuttathatjuk a hello worldöt [forrás]:
+++ +++ +++ +           initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++ +++ +             add  7 to cell #1
    > +++ +++ +++ +         add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<< < -                 decrement counter (cell #0)
]                   
>++ .                   print 'H'
>+.                     print 'e'
+++ +++ +.              print 'l'
.                       print 'l'
+++ .                   print 'o'
>++ .                   print ' '
<<+ +++ +++ +++ +++ ++. print 'W'
>.                      print 'o'
+++ .                   print 'r'
--- --- .               print 'l'
--- --- --.             print 'd'
>+.                     print '!'
>.                      print '\n'

további feladatok

programok próbálgatása

Próbáld ki ezeket a példákat: add.bf hello.bf bottles.bf Keress interneten más példákat.

programok írása

Ötletek:
  • Eratosztenész(FIXME) szitája
  • Fibancci számok kiírása
  • stb
A byte-nyi cellaméretet megnövelhetjük integernyire is, hogy könnyebb legyen nagy számokkal számolni. Sőt az adatkiírást is módosíthatjuk, hogy karakter helyett valódi számot írjon ki. Így egyes netes példák elromolhatnak. Miért is? Egyébkétn bájtalapú cellákkal is lehetne nagy számokkal számolni, csak ekkor kézzel meg kell csinálni a bájthatárokon a túlcsordulást.