• O Zpravodaji
• Pro autory
• Pro čtenáře
• Statistiky

• Aktuální číslo
• Archivní čísla

• Autoři
• Články
• Seriály

• Vyhledávání

   

Průkopník vědy o programování (1)

Na jaře letošního roku rozhodla vědecká rada Masarykovy univerzity o udělení titulu doktor honoris causa v informatice profesoru Donaldu Erwinu Knuthovi, emeritnímu profesoru Stanfordovy univerzity v Kalifornii. V postavě Donalda Knutha je v jistém smyslu ztělesněno uvedení informatiky jako rovnocenného oboru mezi ostatní tradiční vědní obory pěstované v univerzitním či akademickém prostředí. Ve svých 58 letech se může pochlubit 19 čestnými doktoráty z univerzit po celém světě, řadou prestižních cen, mj. i IEEE Computer Pioneer Award za zásluhu na vydělení se informatiky jako vědní disciplíny. V jeho pracích a pracích jeho studentů nalezneme zásadní výsledky týkající se výstavby programovacích jazyků, analýzy technik programování a důležitých algoritmů používaných pro třídění, vyhledávání nebo zpracování numerických výpočtů, stejně jako hluboké matematické výsledky z algebry, teorie grafů a kombinatorických metod. Jeho opus magnum, dosud jen z části zpracovaná série monografii The Art of Computer Programming, představuje základní a dodnes svym rozsahem nepřekonané dílo věnované konstrukci a analýze efektivních algoritmů použitelných v praktických programech.

Mezi světovou vědeckou komunitou ho neméně než jeho 18 vydaných knih a dlouhá řada dalších prací proslavila jeho práce na rozsahlem a po stránce praktické použitelnosti nesmírně propracovaném systému programu pro počítačovou sazbu knih, zejména matematických. TeX a aplikace v něm vytvořené (napr. LaTeX) dnes tvoří de facto standard výměny vědeckých publikací v celé řade vědních disciplín, jeho prostředky jsou ukládany vědecké práce v rozsahlých databázích a algoritmy, které D. Knuth pro tento systém vyvinul a které věnoval k obecnému použití, nalezneme v řadě komerčních systémů používaných velkými i menšími nakladatelstvími. Na Masarykově univerzitě, stejně jako na dalších českých vysokých skolách, je TeX velmi významným nástrojem umožňujícím přípravu kvalitních publikací většího rozsahu.

Při tvorbě tohoto systému měl Donald Knuth za cíl nejen napsání velmi dokonalého programu, který je schopný efektivní práce na prakticky všech třídách počítačů - od nejmenších osobních až po velké superpočítače - ale, jak říká v předmluvě jedné ze svých knih, rovněž "napsání programu, na který by mohl být profesor informatiky pyšný i přes to, že splňuje praktická omezení a činí s tím související kompromisy". Pro automatickou konstrukci velmi dokonale dokumentovaného kódu, který může být knižně publikován bez jakýchkoli dalších úprav a je rovněž schopen kompilace a efektivního běhu na počítači, D. Knuth vytvořil metodologii gramotného programování (literate programming) - v původní podobě to byl na Pascalu založený WEB, který se dočkal úpravy na řadu dalších jazyků, zejména pak na C, resp. C++. Tato technologie programování se těší trvale rostoucímu zájmu programátorů v oblasti akademických aplikací i mimo ně, a řada odborniků ji považuje za vůbec nejdůležitejší koncept, který byl produktem více než patnáct let trvajícího projektu systému TeX.1

Před dvěma lety poskytl Donald Knuth interview pro Computer Literacy Bookshop, ve kterém dovoluje nahlédnout do pozadí svého stylu práce a přístupu k programování a informatice obecně.2 Soudíme, že pro čtenáře univerzitního Zpravodaje věnovaného uvahám o vypočetní technice nemusí být před březnovou návštěvou profesora Knutha na Masarykově univerzitě nezajímavé se s těmito úvahami seznámit. Uveřejňujeme proto překlad plné verze tohoto rozhovoru.

Rozhovor s Donaldem Knuthem pro Computer Literacy Bookshop

Donald E. Knuth patří podle mnohých do světové špičky v informatice. První tři svazky díla The Art of Computer Programming, které ani po 30 letech neztratily na významu, mu přinesly Turingovu cenu ACM v roce 1974 a národní medaili za vědu v roce 1979. Knuth také vyvinul převratné aplikace v počítačové sazbě (TeX a METAFONT) a vývoji softwaru (WEB) a má na svém kontě více než 100 publikací.

Nyní, kdy je emeritním profesorem Stanfordovy univezity, vrhl Knuth opět veškerou svou energii na psaní. Dan Doernberg se jej v tomto rozhovoru z prosince 1993 ptal na to, co v poslední době dělal a na co se můžeme těšit.

CLB: Právě jste publikoval knihy jak o systému CWEB, tak i o Stanford GraphBase, dvou oblastech vašeho vlastního výzkumu. Začněme CWEBem, který je spojením jazyka C a TeXu a slouží k dokumentování programů.

Knuth: Systém CWEB je nadstavbou C a je to zdaleka nejlepší na světě známá programovací metoda. Musím být prostě upřímný a říci, že je to senzační věc. Kniha CWEB System of Structured Documentation je definitivní uživatelskou příručkou a vysvětluje toho víc, než může kdokoliv potřebovat.

CLB: Řekl jste, že CWEB zvyšuje řádově produktivitu programátora - jak to?

Knuth: No, možná ne řádově, možná jen dvojnásobně. Lidé, kteří používali CWEB, zjistili, že píší lepší programy, které jsou přenositelnější, lze je snáze ladit, udržovat... a dají se také rychleji napsat.

CLB: Používá se CWEB jen ve Stanfordu, anebo také v průmyslu?

Knuth: Používá se na celém světě. Na řadě systémů jsme měli CWEB, původní verzi pro Pascal, a řada lidí, kteří se jím infikovali, se pak stále rozrůstala. TeX byl napsán ve CWEBu. Silvio Levy v roce 1987 provedl konverzi na CWEB. Ten byl dlouho experimentální, ale teď mohu říci: "Experiment vyšel!" CWEB je mnohem lepší než WEB, protože C je mnohem hezčí jazyk pro systémové programování a řadu jiných věcí. Nenapadá mne, proč by měl někdo, kdo se opravdu zajímá o programování, tímto pohrdnout ve prospěch jiného systému.

CLB: Snadno použitelné, rychlé, všechno bezvadné?

Knuth: Správně, a taky cítíte po napsání programu ohromné uspokojení!

CLB: I když napíšete špatný program?

Knuth: Skoro...no...jo! Zeptejte se Jill, jak párkrát za týden vyjdu ze své pracovny a říkám: "To programování v CWEBu je taková zábava!" Je to fakt, nemůžu se toho nabažit.

Duševní rozpoložení, v němž se ocitáte, když píšete program v CWEBu, je o hodně lepší než starý přístup. Představujete si, jako byste psal pro lidskou bytost, lidské bytosti vysvětloval, co by měl počítač udělat, a ne že jste jen v roli toho, kdo má počítači nějak sdělit, co má dělat. Máte-li to ale vysvětlit jiné osobě, tak si to musíte sám daleko lépe sesumírovat. Tento postup pomáhá i pro program, který za hodinu zahodíte. CWEB je prostředek, který doporučuji používat, i když třeba píšete program jen pro sebe, pro své oči.

CLB: CWEB se zdá být hodně blízko modelům strukturovaného programování v 70. letech...

Knuth: Správně, jde o další krok. U strukturovaného programování někteří radili vytvářet programy shora dolů, a jiní zase zdola nahoru. S WEBem nebo CWEBem můžete kus udělat zdola nahoru a kus shora dolů, podle toho, co vám přijde vhodné z hlediska programu nebo té části, v níž zrovna jste.

Metodologie strukturovaného programování byla vyborná... jenže k opravdovému pochopení ji nesmíte chápat jako kuchařku s předpisy, ale jako způsob porozumění vztahu mezi vyšší a nižší perspektivou pohledu na program. Na celý program musíte nahlížet jako na síť, spoustu malých kousků, které jsou samy jednoduché a mají jednoduchá propojení s jinými malými kousky. Schéma WEBu právě podporuje tento způsob chápání složitého celku pomocí jednoduchých malých částí a propojení mezi nimi.

Ty části můžete vytvářet v pořadí, které vám psychologicky nejvíce vyhovuje. Někdy je můžete udělat zdola nahoru. Zdola nahoru znamená, že nějak tušíte, že se asi bude pro něco hodit určitý podprogram, takže jej napíšete hned, když jste na to připraven nebo dokud máte náladu. Při tomto programování zdola nahoru se vaše tužka stává stránku od stránky mocnější, protože na straně devět vyvinete nástroje, které můžete použít na straně deset... vaše tužka je silnější.

Pokud jde o programování shora dolů, tam začnete zkraje a řeknete si: "Tohle napíšu napřed a pak toto, a potom toto...", ale později je na vás, abyste podrobně rozepsal, oč v každé části běží - může být, že po sto stránkách budete lapat po dechu, když konečně přijdete na to, jak to vlastně máte všechno udělat!

Na několika prvních stranách vypadá programování shora dolů obyčejně velmi pěkně, ale pak je čím dál těžší udržet všechny nitky v chodu. Programování zdola nahoru také často vypadá nějakou dobu pěkně, vaše tužka sílí, ale to právě zas svádí k různým trikům. Pokud oba přístupy nějak psychologicky vhodně zkombinujete, pak to funguje, dokonce i když končíte.

Takhle jsem to dělal s TeXem, což je hodně velký program: víc než 500 stran zdrojového kódu v knize. V celém tom programu, u každé jeho řádky byla vždy jen jediná věc, kterou jsem musel udělat jako příští. Neměl jsem žádný velký výběr; každý krok se zakládal na tom, co už jsem do té doby udělal. Žádná metodologie by mne nenaučila, jak psát software tohoto druhu, pokud bych se jí přísně držel. Ale když jsem si představil, že ten program vysvětluji dobrému, schopnému programátorovi, tedy všechno, co v něm je, našel jsem jen jednu přirozenou cestu, jak to udělat. Uspořádání, v němž se kód nachází v knize, odpovídá tomu, jak jsem jej psal.

CLB: Do jaké míry jste sledoval nebo sledujete ony "svaté války" - debaty o metodologiích softwarového inženýrství?

Knuth: Nesledoval jsem všechny nuance těchhle věcí, ale dominantních myšlenek jsem si všímal. Až za mnoho let po jiných lidech jsem vlastně zjistil, co jsou to nástroje CASE. Myslím si, že nebylo dobře dělat z toho takové náboženství. V oněch dobách se způsob programování řídil "politickou korektností".

Podobná věc se stala v matematickém společenství ve dvacátých letech, kdy se říkalo, že dobrý matematik musí dokazovat věty určitým způsobem. Nehodilo se používat jisté prostředky důkazu, o nichž někteří soudili, že vás mohou zavést do paradoxů. Bylo to něco jako pěstování matematiky s jednou rukou uvázanou za zády. Politicky korektní strukturované programování podobným způsobem překáželo lidem v napsání dobrých programů, i když přesně věděli, co dělají, a to jen proto, že jejich postup zrovna nezapadal do současného chápání správnosti. Informatika je jako každý jiný obor; postupuje v módních vlnách. Některé z trendů jsou dobré, jenže skoro s každou dobrou myšlenkou se tak nějak zachází jinak, než jak by se mělo.

Například si vezměte generátory náhodných čísel. Patnáct let jsme neměli žádnou teorii o tom, jak generovat náhodná čísla. Pak někdo dokázal takovou drobnost o jedné z metod: když se vzal průměr sériových korelací přes celou periodu čítající miliardu čísel, pak ten průměr byl nula, což bylo dobré. Z ničeho nic všichni všeho nechali, vyhodili své staré rutiny a přešli k této nové metodě, poněvadž to byla jediná metoda, k níž byla vůbec nějaká teorie. Ukázalo se, že to je hrozný generátor náhodných čísel; teorii ušlo, že průměr přes první polovinu oné periody je +1 a přes druhou polovinu -1 ! Vždy v celé historii si lidé vybírali metody a nedošla jim jejich omezení.

CLB: Co to bylo za metodu?

Knuth: No, ve většině knihoven podprogramů se jí říkalo RANDU. Touto dobou už by měla být dostatečně vymýcena; nicméně, jak někdo uvidí podprogram s názvem RANDU, pryč s ním!

CLB: Vedlo vás ke spojení WEBu s Céčkem to, že je dnes tolik programátorů používá, anebo se vám osobně C líbí a píšete v něm?

Knuth: Myslím si, že C má spoustu velmi důležitých vlastností. Například způsob, jímž C zachází se směrníky, byl znamenitou inovací; vyřešil řadu problémů se strukturováním dat, s nimiž jsme se dříve potýkali, a vylepšil také vzhled výsledných programů. C ovšem není dokonalý jazyk, nakonec dokonalý není žádný z existujících jazyků, ale má podle mého spoustu kladů, a když se vám něco nelíbí, tak se tomu můžete vyhnout. Takže C jako jazyk se mi určitě líbí, zvlášť protože je dobře sladěn s operačním systémem (pokud například používáte UNIX).

Po celý život si vždy vybírám ten jazyk, který je nejlépe sladěn s debuggerem a operačním systémem, které zrovna používám. Pokud bych měl pro nějaký jazyk X lepší debugger a X se dobře snášel s operačním systémem, používal bych tento jazyk.

Extrémní případ nastal, když jsem rok pracoval v laboratoři, kde operační systém navrhl Ned Irons. Byl to systém pro jednoho z raných Crayů a Irons také napsal kompilátor pro jazyk zvaný IMP. IMP měl řadu hrozných vlastností. Jednak to byl rozšiřitelný jazyk, a tak jej všichni neustále rozšiřovali. Program, který v pondělí fungoval, vám v úterý fungovat přestal, čili po zřícení programu se vždycky muselo napřed zkontrolovat, zda je v pořádku strojový kód programu. Zadruhé, IMP byl jazykem ohromně zhuštěným. Kupříkladu tam, kde v Pascalu píšete "if X>0 then ...", v IMP řeknete "X+=>". Jinými slovy, programy byly velmi krátké. Připadalo vám sice, že píšete elegantní programy, protože měly jen pár znaků, jenže druhý den už jste je nemohl vůbec přečíst! Cenou za úspornost tak bylo, že jste z té změti značek na stránce byl docela vedle...

CLB: V současné době zřejmě kladete důraz na "gramotné programování", ale přitahoval vás někdy APL jakožto matematicky orientovaný jazyk?

Knuth: To je něco jiného. APL je pro lidi, kteří mají problémy k řešení a nestarají se tolik o efektivitu; chtějí pěkně a elegantně zformulovat řešení svého problému, i když toto řešení nemusí být nutně snadnou záležitostí pro počítač. Je to jazyk pro specifikaci problémů, nikoliv jazyk pro systémové programování... APL-CWEB existuje.

Chtěl bych ale ještě něco říci k IMP. Třetí věcí proti němu bylo to, že v případě chyby se buď kompilátor dostal do nekonečné smyčky anebo se zastavil na první chybě, oznámil "ERROR ERROR ERROR" a skončil. Sám jste musel přijít na to, v čem je chyba. Žádný skvělý jazyk nebo kompilátor to tedy nebyl.

Nicméně... stejně jsem si tenhle jazyk zvolil, protože bezvadně zapadal do onoho operačního systému. Názvy polí se volily tak, že byly snadno vidět v debuggeru a mohl jste zjistit, jakým způsobem se přiděluje paměť, věděl jste, co se děje, a konec konců jste mohl program zvládnout tak, aby běžel spolehlivě, poněvadž IMP byl sladěn s operačním systémem. Mohl jste psát v lepším jazyku, ale odpovědi byste jen tak nezískal a celá práce by vám trvala o pár týdnů déle. Já jsem používal IMP.

CLB: Používal se IMP ve Stanfordu?

Knuth: Tohle bylo ve výzkumné laboratoři v Princetonu. Rok před mým příchodem do Stanfordu jsem tam dělal na výzkumném projektu klasifikované analýzy šifer.