Neprocedurální pohádka

Tuhle pohádku jsem napsal během absolvování předmětu Neprocedurální programování v roce 2003. Pokud jste si jím prošli také, tak si to (doufám) užijete.

O Karlíčkovi a Logince

Bylo-nebylo, (haskelloví jazykové tvrdí, že Maybe Bylo,) za osmi streamy a čtyřiašedesáti mounty žili tatínek Prolog a maminka Ada se svými dvěma dětmi -- robotem Karlem a želvičkou Logo, kterým však doma neřekli jinak než Karlíčku a Loginko. Byla to dítka hodná, avšak rozpustilá až běda, takže jich byl plný hard disk, jak už to tak bývá. Rodinka žila šťastně a spokojeně v malém sektoru, až kdesi na kraji paměťového prostoru. Tatínek Prolog byl data-minerem a den co den se brzy, brzičko ráno vydával do nedalekého lesa kácet adresářové stromy.

Jednoho dne si maminka Ada musela nepodmíněně skočit do CPU něco zpracovat a tak nezbylo tatínku Prologovi, než využít polymorfismu a vzít své potomky s sebou do lesa. V lese se dal Prolog jako obvykle do své nelehké práce: strom nejprve oddělil od kořene, povalil na zem a pak se jal odřezávat jednotlivé větve, někdy červeným, raději však zeleným řezem, až se mu konečně podařilo strom unifikovat s nařezaným dřevem, zapřaženým za bujného trojského koníka a redo from start.

Dětem se v lese líbilo, honily se mezi stromy, Karlíček poskakoval, tu zkoušel krátký, tu zase dlouhý skok, Loginka zase pobíhala po komplikovaných trajektoriích a opisovala ty nejroztodivnější iterativní křivky a obrazce. Když se unavili, čapli si na bobek, rozhrnovali jemné listy zelených fraktálních kapradin a pozorovali housenky a drobné obratlovce, kterými se to v lese jen hemžilo; jindy zase zaklonili hlavu a pokoušeli se zahlédnout povykosy, kteří povykovali někde nahoře ve vysokých hladinách stromů. Když ale začali induktivně trhat listy malého stromku, musel je tatínek okřiknout.

Jenže jak procesorové cykly ubíhaly, zabral se Prolog do práce. Zrovna rozřezával jeden strom tak dlouho, že se začal obávat cyklu nebo chybě v procedurální sémantice podprogramu, když se Karlíček s Loginkou zatoulali hluboko do lesa. Marně ho volali, na blízké volání neodpovídal a pro vzdálené jim chyběla adresa segmentu. Hledali ho, ale hledání vždy skončilo nula nalezenými soubory. Už padala tma a děti dostaly strach. "Kdybych býval nechával za sebou značky, mohli jsme cestu domů backtrackovat" mrzelo robota. "Karlíčku, vylez na strom a podívej se, jestli neuvidíš někde světýlko," napadlo Loginku. Karel se ušklíbl její dětské syntaxi a jal se šplhat na nejbližší strom metodou DFS. Když konečně dosáhl k-té hladiny, rozhlédl se a skutečně uviděl v dálce něco emitovat. Rychle sešplhal dolů a povídá: "Támhle v dáli jsem viděl únik dat, určitě tam žije Pascal nebo nějaký jiný milý procedurální jazyk." Vydali se tím směrem a nakonec skutečně objevili paseku, kde jako izolovaný bod v množině hromadných bodů stála opuštěná eulerovská jednotažka. Loginka si to už mířila ke dveřím chaloupky a chystala se hledat kliku velikosti n, když v tom Karlíček povídá: "Loginko, ta střecha je ze syntaktického cukru!" Loginka vyvolala přerušení aktuálního programu a odsekla "Jsi iracionální jak přepona čtverce." Ale robot se nenechal odradit, uloupl několik bajtů ze střechy, ukousl několik nibblů a rotoval je v akumulátoru.

V tom se však dveře chaloupky rozlétly, vyrazila z nich ošklivá, rozezlená rekurze a zaskuhrala "porušili jste ochranu mé chaloupky. Teď jsem bezbraná proti těm zpropadeným hackerům, Rainovi a Snowovi." Popadla Karlíčka s Loginkou za uživatelské interfejsy a pushla je do temného zásobníku. "Okamžitě nás popněte, nebo vyvolám výjimku!" zkoušel to Karlíček, ale rekurze na ně vycenila Master theorem: "Ale děti, já se o vás přece budu dobře starat, dostanete tolik syntaktického cukru, kolik jen budete chtít!" Děti smutně refreshovaly v zásobníku, zatímco babice pilně pobíhala po jednotažce a ladila lexikální analyzátor. Ani Karlíček, natožpak mladší Loginka, netušil že zlá rekurze je nejen karložrout, ale ráda si smlsne i na lecjakém neprocedurálním jazyku.

Když už byl lexikální analyzátor řádně odladěný, jeho výstup dobře táhl rourou do komína a teplo z řeřavých lexémů příjemně sálalo, popla rekurze děti ze zásobníku a povídá: "Ty, želvičko, podržíš rukojeť socketu, a ty, robote, si sedneš na datagram a vyprofiluješ analyzátor, jestli všechny jeho moduly pracují optimálně. Karlíček si sedl na datagram a hned zase spadl. "Promiňte, babičko, ale nevím, jak se na datagramu sedí. Preorder, inorder, nebo postorder?" Rekurze se rozesmála na celou složitost: "Ach ta dnešní mládež, to je samá ochrana (paměti) a neumí to ani základní síťové operace. Nastav si na mě watches, ukážu ti to!" Rekurze se obratně usadila na datagram: "Tak co, už jste to odladili?" Ale Karlíček s Loginkou na nic nečekali, popadli rukojeť, pushli rekurzi do analyzátoru a zavřeli socket.

Zevnitř se ozval příšerný řev, to jak líné vyhodnocování lexikálního analyzátoru redukovalo rekurzi a pak postupně i celou eulerovskou jednotažku na hodnotu Bottom. Děti však na nic nečekaly a utíkaly, jako by jim za patama formátoval.

Doma zatím Prolog s Adou ztráceli poslední bit naděje, že se jejich potomkům ve vícenásobné dědičnosti podaří provést instrukci return. Na nebi už vycházel Sun, Prolog zrovna vysypával staré termy do garbage collectoru, když v tom vidí, že se k jejich efektivní adrese blíží Karlíček s Loginkou. Maminka Ada nechala stát strýčka Sama v předsíni, vyběhla ze zadních dvířek a vyrazila dětem naproti jako zásobník proti haldě. To bylo handshaků a checksumování! To byla šťastná kolize!

Reference

Aneb co je potřeba k dokonalému pochopení.

• absolvovat předmět PRG005 Neprocedurální programování

• přečíst skvělou knihu Markéty Synovcové Martina si hraje s počítačem /107 programů pro robota Karla/ Albatros 1989

• vědět co je to programovací jazyk Logo ("želví grafika", programujete želvu, která chodí po obrazovce a zanechává za sebou stopu, tím kreslí různé obrázky)

• znát něco málo z BASICu, objektového programování, TCP/IP, near/far pointery, x86 assembler...

• vědět, jak vzniknul programovací jazyk Ada

• Master Theorem (Kuchařka) z předmětu Složitost I
• eulerovské jednotažky (Diskrétní matematika)
• průchod stromem do hloubky (Programování I)
• předmět Základy operačních systémů a překladačů
• BSD sockets (třeba Úvod do UNIXu, Rodina protokolů TCP/IP)

Autor a poznámky

• Jiří Svoboda (chip(at)matfyz.cz)
• vzhledem k tomu, že asi málokdo četl všechno z výše uvedeného seznamu, napíšu možná vysvětlivky, kde některé věci vysvětlím :)
• některé narážky jsem zvýraznil kurzívou, hlavně ty, které nejsou příliš okaté
• jestli se někomu nelíbí, že jsem si sem dal vlastní dílko, tak si poslužte a vymažte ho, ale aspoň tu na něj nechte odkaz (http://chip.matfyz.cz/h_zabava/b_pohadka/index.html)