Programátoři z pekel zde za šat a stravu programují čipová pseuda.

Programujeme v BASICu: Seriózní programy (4)

Slyšel jsem, že máte rádi interprety. Tak jsem naprogramoval interpret v interpretu, abyste mohli interpretovat, zatím co interpretujete!

Když jsem před třemi roky začínal sérii o seriózních programech, vážně jsem myslel, že budou seriózní. Nejsou. Jsou to programy, které píšu abych si něco zkusil, něco ověřil, něco se naučil. Jednou takhle cestou do práce jsem pojal chuť zkusit si napsat interpret esoterického programovacího jazyka Brainfuck. V assembleru to na ZX Spectru už napsalo nenulové množství lidí, ale v BASICu si to žádný netroufl. Proč asi?
Brainfuck combines the speed of BASIC with the ease of INTERCAL and the readability of an IOCCC entry!

Toto zajímavé dílo amigisty Urbana Müllera má pouze osm příkazů/instrukcí/elementů:

  •  <    Posune datový ukazatel o jednu adresu dolů.
  •  >    Posune datový ukazatel o jednu adresu nahoru.
  •  +    Zvýší o jedna hodnotu na adrese dané paměťovým ukazatelem.
  •  -    Sníží o jedna hodnotu na adrese dané paměťovým ukazatelem.
  •  .    Vypíše hodnotu na adrese dané paměťovým ukazatelem na výstup.
  •  ,    Uloží hodnotu ze vstupu na adresu danou paměťovým ukazatelem.
  •  [    Pokud je hodnota na adrese dané paměťovým ukazatelem rovna nule, posune programový ukazatel dopředu za párovou ].
  •  ]    Pokud je hodnota na adrese dané paměťovým ukazatelem různá od nuly, posune programový ukazatel zpět za párovou [.
Ač se to může zdát k nevíře, tak těchto osm instrukcí stačí k vyřešení jakéhokoliv řešitelného problému, neb jazyk je turingovsky kompletní. Oč složitější je v Brainfucku programovat, o to jednodušší je vytvořit interpret.
  10 CLEAR 27999: LOAD ""CODE : LOAD ""CODE
  20 LET dbeg=28000: LET dsize=30000: LET pbeg=dbeg+dsize
  30 LET ptr=dbeg: LET pc=pbeg
 100 REM Main Cycle
 110 LET i=PEEK pc
 120 IF i=CODE ("+") THEN GO SUB 500
 130 IF i=CODE ("-") THEN GO SUB 550
 140 IF i=CODE (">") THEN GO SUB 600
 150 IF i=CODE ("<") THEN GO SUB 650
 160 IF i=CODE (".") THEN GO SUB 700
 170 IF i=CODE (",") THEN GO SUB 750
 180 IF i=CODE ("[") THEN GO SUB 800: GO TO 200
 190 IF i=CODE ("]") THEN GO SUB 900
 200 LET pc=pc+1: GO TO 100
 500 REM INC(ptr)
 510 LET x=(PEEK ptr)+1
 520 IF x>255 THEN LET x=0
 530 POKE ptr,x
 540 RETURN
 550 REM DEC(ptr)
 560 LET x=(PEEK ptr)-1
 570 IF x<0 THEN LET x=255
 580 POKE ptr,x
 590 RETURN
 600 REM INC ptr
 610 LET ptr=ptr+1
 620 IF ptr=pbeg THEN LET ptr=dbeg
 630 RETURN
 650 REM DEC ptr
 660 LET ptr=ptr-1
 670 IF ptr=dbeg-1 THEN LET ptr=pbeg-1
 680 RETURN
 700 REM PRINT (ptr)
 710 PRINT CHR$ PEEK ptr;: RETURN
 750 REM INPUT (ptr)
 760 PAUSE 0: POKE ptr,CODE INKEY$: RETURN
 800 REM loop start
 810 IF PEEK ptr<>0 THEN RETURN
 820 LET c=0
 830 LET pc=pc+1
 840 IF CHR$ PEEK pc="[" THEN LET c=c+1
 850 IF CHR$ PEEK pc="]" AND c=0 THEN RETURN
 860 IF CHR$ PEEK pc="]" THEN LET c=c-1
 870 GO TO 830
 900 REM loop end
 910 IF PEEK ptr=0 THEN RETURN
 920 LET c=0
 930 LET pc=pc-1
 940 IF CHR$ PEEK pc="]" THEN LET c=c+1
 950 IF CHR$ PEEK pc="[" AND c=0 THEN RETURN
 960 IF CHR$ PEEK pc="[" THEN LET c=c-1
 970 GO TO 930
Standardem mezi interprety je, že datová oblast má alespoň 30000 bajtů, do 48kB paměti ZX Spectra se tak vejde i s dalšími šesti kilobajty místa pro samotný brainfuckový program. Jelikož mají všechny datové buňky mít na počátku hodnotu 0 a nulování skoro třiceti kilobajtů paměti BASICem je čiré utrpení, předpokládá můj interpret nahrání dvou souborů:
  • 30000 B dlouhý soubor plný nul od adresy 28000
  • brainfuckový zdroják od adresy 58000
Fungování samotného programu asi nevyžaduje žádného detailního komentáře. Hlavní cyklus načítá instrukce a skáče na příslušné podprogramy, které instrukce vykonávají přesně podle definice v úvodu článku. Zkoušel jsem to hned na několika stažených ukázkových zdrojácích a funguje to.

Funguje to ale dost pomalu. Pěkně je to vidět na poněkud komplexnějším programu 99 Bottles of Beer, který vypisuje anglickou pivní říkanku:
99 Bottles of beer on the wall 99 Bottles of beer Take one down and pass it around 98 Bottles of beer on the wall 98 Bottles of beer on the wall 98 Bottles of beer Take one down and pass it around 97 Bottles of beer on the wall
Emulátor FUSE na mém Lenovu T400 běží maximálně na 72-násobku rychlosti originálu ZX Spectra. Pokud v něm pustím tento program, pak generování a výpis jednoho čtyřverší trvá přesně 45 sekund. Při devětadevadesáti čtyřverších se dostáváme na 74 minut a 15 sekund. Na reálném stroji by to bylo ještě 72x více, čímž se dostáváme na 5346 minut, tedy 89 hodin a 6 minut, neboli tři a tři čtvrti dne.

Na modelování celoplanetárního počasí je tedy Brainfuck interpretovaný Sinclair BASICem, který je interpretovaný procesorem Z80 celkem nevhodný. Jako ukázka toho, že to jde, je ale docela dostačující.