Logické programování v malém

12.10.2018 13:22 | Přečteno: 3509× |

V dobách osmibitových počítačů byla laťka pro vysokoúrovňové jazyky nastavena o poznání níže než dnes, takže k nim bylo tenkrát řazeno i Céčko. Bylo pro ně ovšem k dispozici i pár jazyků, o jejichž vysokoúrovňovosti nikdo nepochybuje ani dnes. Tentokrát se podíváme na jeden z nich - micro-PROLOG pro ZX Spectrum.

Výběr programovacích jazyků dostupných pro ZX Spectrum byl docela rozmanitý. Většina programů se sice psala s pomocí BASICu a jazyka strojových isntrukcí, ale krom nich měli majitelé (nejen) těchto strojů ještě k dispozici širokou škálu alternativ. Pro výuku algoritmizace tu bylo Logo či Karel, algolovské strukturované jazyky reprezentoval Pascal a C. Samozřejmě nechyběl ani Forth a Lisp. Existovalo i několik prostředí specializovaných na vývoj určitého typu her, ale kvalit pozdějšího AGD ještě nedosahovaly.

I logické programování mělo na Spectru svého plnohodnotného zástupce. Byl jím micro-PROLOG firmy LPA. Protože tento program měl to štěstí a nepohltila ho digitální nicota jako některé jeho současníky, můžeme si jej stále vyzkoušet. Od méně šťastných kolegů se odlišuje ještě jednou podstatnou vlastností. Je k němu k dispozici učebnice čítající asi tři sta stran, která má i po 35 letech stále co nabídnout.

Micro-Prolog pro ZX Spectrum byl vydán na konci roku 1983. Za kazetu s učebnicí jste museli sáhnout do kapsy pro cca 25 liber, což byl byl přibližně pětinásobek ceny áčkového herního titulu, ale podobné programy tenkrát většinou nebývaly levnější (HiSoft C i Pascal stály ostatně stejně) a přibalená kniha a kvalita titulu cenu ospravedlňovala.

Historie samotného micro-PROLOGu sahá do roku 1979, kdy byly jeho první verze vytvořeny na Královské univerzitě v Londýně. Následně komercializován firmou LPA Ltd (Logic Programming Associates Limited). Byl k dispozici pro několik systému včetně CP/M verze pro procesor Z80, takže jeho port pro ZX Spectrum byl přirozený krok.

Samotný micro-PROLOG je jazyk, který se od dnešního Prologu vhledem výrazně liší. Je postavený na syntaxi, která je silně inspirována Lispem. Jako příklad si vezměme klauzule pro spojení dvou seznamů. V běžném Prologu vypadá jejich zápis nějak takto:

append([], L, L). 
append([H|T], L2, [H|L3]) :- append(T, L2, L3).

Nativní syntaxe micro-PROLOGu svůj lispovský původ a snahu o snadné strojové zpracování rozhodně nezapře.

((APPEND () X X))
((APPEND (X|Y) Z (X|x))
  (APPEND Y Z x))

Ovšem tuto syntaxi se alespoň před začátečníky snaží micro-PROLOG skrýt seč může. Jakmile totiž nahrajete do paměti samotný micro-PROLOG, předpokládá se, že si hned nahrajete program jménem SIMPLE. Ten je už napsaný přímo v Prologu a poskytuje uživateli rozhraní, které programy překládá do uživatelský přívětivější syntaxe. Ta vypadá takto:

append(() y y) 
append((x|X) y (x|Z)) if append(X y Z) 

Jak je vidět, stále se od dnešního Prologu liší. Používá například jiný zápis seznamů či odlišné vyjádření implikace a řezů. Je to dáno tím, že vychází z původní Marseilleské syntaxe vytvořené s ohledem na to, že Prolog budou používat počítačově nepříliš zdatní lingvisté. Postupně ale vyhrála alternativní syntaxe použitá v Edinburghské implementaci, což je možná škoda, protože tento tento druh zápisu je docela čitelný. Dovoluje i infixovou notaci.

x grandfather-of y if
        x father-of z and
        z parent-of y

Co se proměnných týče, jejich jména jsou omezena na X, Y, Z, x, y, z, X1, Y1, Z1, x1, y1, z1, X2 atd. Můžete použít libovolná z uvedeného rozsahu, ale kvůli šetření pamětí se jejich pořadí stejně přeskládá na uvedené, protože interně je uložen jen index proměnné a původní název se zapomene. Micro-PROLOG nemá anonymní proměnné (_).

Co se možností samotného jazyka týče, jedná se v podstatě o plnohodnotnou implementaci Prologu poskytující i základní reflektivní vlastnosti, které dovolují programování vyššího řádu (sic), tedy psát pravidla jako maplist či modifikovat programy, což dokazuje samotný program SIMPLE. Navíc micro-PROLOG poskytuje mocný systém modulů, které dokáží zakrývat svou implementační část.

Použitelný je i editor, i když se nedá označit za komfortní. Programy se needitují jako zdrojový text, pracuje se s databází pravidel a faktů. K ovládání této databáze má programátor k dispozici imperativní příkazy jako add, list, edit, delete. Takže pokud chcete třeba změnit druhou klauzuli u pravidla append a posunout ji na první místo, napíšete příkaz edit append 2 a v editačním řádku upravíte pravidlo, na jehož začátku je pořadové číslo, které můžete přepsat. Původní formátování se neuchovává, ale ve výpisu pravidel se provádí rozumné automatické přeformátování, takže programy jsou bez potíží čitelné.

Pro dotazy slouží příkazy jako is, which, all a one. U příkazu which či ekvivalentního all se na začátku dotazu uvádí vzor odpovědi oddělený dvojtečkou odkazující na proměnné.

which(x y : append(x y (2 3 4)))

Vzor odpovědi umožňující mezi proměnné vkládat další libovolný text.

which(result is x and y : append(x y (2 3 4))) 
result is () and (2 3 4)
result is (2) and (3 4)
result is (2 3) and (4)
result is (2 3 4) and ()
No (more) answers 

Tomuto systému editace programů a komunikace s micro-PROLOGem bych vytknul především to, že si nepamatuje alespoň poslední zapsaný příkaz a to ani v případě, že obsahoval syntaktickou chybu. Takže si programátor své klávesnice užije dosytosti. V emulovaném prostředí je výhodné používat rychlý snapshot.

K ladění programů se používá program SIMTRACE, který je také napsán v PROLOGu a je potřeba ho stejně jako SIMPLE dodatečně nahrát z kazety. Ten dovoluje nahlížet na postup backtrackingu při vyhodnocování pravidel a zjišťovat tak, proč se vaše klauzule nechovají tak, jak očekáváte.

No space left

Micro-PROLOG pro Spectrum vás uvítá velice “optimistickou” zprávou 24153 Bytes Free. Programátor má tedy pro svoje potřeby k dispozici asi 23,5 kB paměti. Z ní si ale část ještě ukousne SIMPLE, případně SIMTRACE či další utility. S hlášením o nedostatku paměti se tedy setkáte častěji, než by bylo milé. Když jsem si například psal solver na zmenšené sudoku, měl jsem ověřeno, že všechny mé klauzule na validaci řádků, sloupců a bloků fungují podle mých požadavků, ale při jejich spojení do jednoho pravidla solve došla při pokusu o řešení každého sudoku paměť. Nezbývalo tedy než se pokusit pravidla přepsat tak, aby pracovala méně nenažraně.

Na brutální omezenou paměť se dá nahlížet i pozitivně. Nutí programátora k psaní efektivnějších programů. Také 3,5 MHz procesor tepající v útrobách vašeho počítače spolehlivě upozorní na každý pomalý algoritmus. Ve skutečnosti je problém s pamětí ještě o něco horší. Protože samotné SIMPLE je napsáno v Prologu a je limitováno úplně stejně, může se vám snadno stát, že při použití mnoha zbytečně dlouhých klauzulí mu při překladu do zjednodušené syntaxe dojde dech a vám se tak nepodaří váš odporný paskvil ani vypsat, za což si zaslouží jen poděkování.

Jistě se ptáte, má-li vůbec cenu se v dnes mučit tímto desítky let starým programem. Osobně mohu říct, že se jedná o velice zábavné a podnětné trýznění. Přeci jen je to už dlouhá doba, kdy jsem s Prologem přišel do styku naposledy a je prospěšné si opět po čase obrátit mozek naruby a přepnout se na deklarativní způsob myšlení. Používat Prolog jako univerzální jazyk sice osobně nepovažuji za vhodné, ale nic vám nebrání ho používat jako solver či si ve svém oblíbeném programovacím jazyce najít nějakou jeho obdobu. Pro řady reálných problémů se jedná o ideální nástroj a trápit se s micro-PROLOGem nebo nějakou moderní implementací vám pomůže tyto problémy snáze identifikovat a následně řešit pomocí vhodných nástrojů.

Čímž se dostáváme k otázce, k čemu praktickému na Spectru micro-PROLOG byl? Samotná učebnice je z velké části postavena na typických didaktických příkladech s rodinnými vztahy, což zájemce o programování tenkrát asi příliš neuspokojilo. Na řešení aritmetických problémů se micro-PROLOG nehodil prakticky vůbec. Navíc, tím, že se při interaktivní práci s ním používal relativně náročný překlad syntaxe, i na odpověď na jednoduchý aritmetický součet dvou celých čísel si člověk počkal o několik řádů déle než u pomalého BASICu.

V tomto ohledu micro-PROLOG na Spectru působí jako zjevení z jiného světa. Světa, který se nezabývá podružnými problémy, jako je vypsání Hello world, ale kde se lidé snaží o parsování přirozeného jazyka a podobné problémy expertních systémů a umělé inteligence, ať už odborníci pod tímto termínem viděli něco jiného, než si představovali začínající počítačoví nadšenci. Ve své době se jednalo nepochybně o velké lákadlo, které vyvolávalo očekávání, jež micro-PROLOG na Spectru jednoduše nemohl naplnit.

U každého programovacího jazyka platí, že to, co jej dělá skutečně použitelným, jsou knihovny. Prolog na tom není jinak. I řešení problémů pro něj vyloženě vhodných, jako je zmíněné sudoku, není jednoduché, pokud máte jen syrový systém bez tak základních funkcí, jako je zjištění, zda je daný prvek v seznamu, transpozice matic atd. A micro-PROLOG takové knihovny nenabízel ani přiložené. Programátor si je musel napsat sám nebo se poohlédnout v odborné literatuře.

V učebnici micro-PROLOGu chybí popis kooperace Prologovských programů s BASICem nebo strojovým kódem, což jeho reálnou použitelnost ještě dále limituje. Vůbec bych se nedivil, pokud by pro řadu lidí micro-PROLOG pro Spectrum skončil někde zaprášený na poličce a každý pohled na něj doprovázel pocit, že si místo něj měl koupit raději několik her. Samotná učebnice je psána hlavně ze začátku velice přístupně, později se však v řadě pasáží jedná o hodně hutné a náročné čtení a nemyslím si, že by její cílová skupina byli žáci základní školy. I z dnešního pohledu se však jedná o učebnici PROLOGu, která stojí za přečtení.

S časovým odstupem nezbývá než micro-PROLOG hodnotit vyloženě kladně. Jako úvod do světa logického programování se jednalo o výborný počin s profesionálním zpracováním a jeho omezení a problematická praktická využitelnost plynula především z nedostatečnosti dobového hardwaru. Nabízel solidní nástin, jak bude vypadat programování v budoucnu, kdy počítače budou mít tehdy ještě nepředstavitelné množství paměti, extrémně rychlá vysokokapacitní úložná média a nespočet úžasně rychlých procesorů. Budoucnost, která se naplnila, ale přesto vypadá úplně jinak.

Samotný micro-PROLOG se nedochoval kompletní. Všechny dostupné obrazy kazet obsahují pouze stranu A, takže chybí některé důležité utility, například nástroje pro vytváření modulů. Naštěstí se mi podařilo sehnat a zakoupit originální kazetu a až se mi konečně dostane do rukou, při troše štěstí se tento nedostatek napraví a tento klenot se budoucím generacím zachová celý. K micro-PROLOGu vyšla ještě další oficiální kniha, referenční manuál. Ten bohužel není nikde k dohledání. Přístupné jsou však referenční manuály k verzím pro CP/M. Informace v nich jsou do jisté míry platné i pro pro Spectrum. Snad se i tato informační díra podaří časem kompletně zacelit.

Interní implementace micro-PROLOGu historicky předchází Warren Abstract Machine a podobné techniky, takže z dnešního pohledu bude již archaická. Na krátkou návštěvu minulé budoucnosti programování ale poslouží více než dobře.

       

Obrázky

Komentáře

[Mirek]

pěkný, díky.

[dumblob]

Zajímavé. Také jsem netušil, že existovata "čitelnější" syntaxe než "dnešní" Prolog a Datalog.

[Andrej]

prolog nedavam, ale ta linka na AGD tutorial je skvela!

[pushkin]

Prolog nedávám, ale citát:

Na brutální omezenou paměť se dá nahlížet i pozitivně. Nutí programátora k psaní efektivnějších programů.

by chtělo tesat do kamene. Když dnes člověk vidí, jaké kraviny jsou neskutečně pomalé a nenažrané, možná by to ty lidi naučilo opravdu programovat.*

Jinak na doby ZX Spektra/Atari 800 rád vzpomínám. Vyučen BASICem na číslování řádků a GOTO a GOSUB jsem se dlouho blbě přeučoval na vyšší jazyky.

*) Ne, že bych byl jiný případ. To, jak blbě programuju mi ukázalo, když jsem se pokoušel analyzovat data ze čtyřkanálového osciloskopu a vyžral jsem s tím 6 GiB RAM, načež počítač začal swapovat (OK, 5GS/s a šlo o dvě periody 50 Hz signálu). Pak teprve jsem si uvědomil, jak je důležité po každém kroku mazat z paměti mezivýsledky

[carol]

Programming is too typical and hard for those who have no interest in it but Some students have their programming course in their syllabus so they had to study it but booking app development is not that hard you can make it or you can order it on our site.