Obsah
1. Programovací jazyk LISP a LISP machines
2. LISP na mainframech Univac 1100
3. Architektura počítačů CONS a CADR
4. Společnost Thinking Machines a architektura Connection Machine
7. Obsah následující části seriálu
1. Programovací jazyk LISP a LISP machines
Programovací jazyk LISP, s jehož základy jsme se seznámili v předcházejících dvou částech tohoto seriálu, se prakticky ihned po vzniku jeho první implementace na mainframech firmy IBM začal používat pro výzkum i tvorbu aplikací z oblasti umělé inteligence (AI – Artificial Intelligence). Nejedná se přitom o žádnou náhodu, protože tvůrcem LISPu je John McCarthy, který se vývojem systémů umělé inteligence zabýval a dokonce tento termín v roce 1956 (tj. dva roky před vznikem samotného LISPu) použil v názvu nově vzniklé konference – Dartmouth Summer Research Conference on Artificial Intelligence. Programovací jazyk LISP skutečně měl (a doposud má) některé vlastnosti, které jsou z hlediska tvorby AI výhodné. Jedná se například o možnost jednoduché práce se symboly (například při zpracování přirozeného jazyka, analýze sítí či manipulaci s výrazy – jejich symbolické derivaci, zjednodušování atd.). Symboly jsou, jak jsme si již řekli v předchozích dvou částech seriálu, považovány za atomický datový typ.
Obrázek 1: Sálový počítač IBM-704, jehož architektura byla (i když neúmyslně) hned z několika hledisek vhodná pro implementaci LISPu. Jednalo se o mainframe, v jehož slovech bylo možné uložit vždy celou tečka-dvojici (cons) a poměrně snadno z této struktury získat obě její části – CAR a CDR.
Dále lze v LISPu velmi snadno pracovat se seznamy i s dalšími komplikovanějšími datovými strukturami, například se stromy či obecnějšími grafy (v mnoha implementacích tohoto jazyka taktéž s asociativními poli) a současně LISP díky dynamickému typovému systému a existenci automatického správce paměti (garbage collector) nezatěžuje vývojáře mnohdy zbytečnými „nízkoúrovňovými“ problémy. LISP se postupně rozšířil z mainframů firmy IBM i na další superpočítače, minipočítače a později i na mikropočítače. Ovšem současně se zvýšeným zájmem o umělou inteligenci, vyvolaným představou, že inteligentní systémy se podaří vytvořit poměrně rychle (nejpozději na začátku 21. století), začaly vznikat počítače, které byly specializované na spouštění LISPovských aplikací, tj. programů, v nichž se manipuluje především se symboly uloženými v seznamech a ne s numerickými údaji uloženými většinou v polích (zde dominovaly klasické superpočítače a programovací jazyky typu Fortran, částečně APL a později i Céčko). V následujících kapitolách si některé z počítačů uzpůsobených pro běh LISPovských programů popíšeme.
Obrázek 2: Mainframe IBM-709, na němž byl provozován LISP 1.5, tedy první „skutečný“ LISP v podobě, jak ho známe doposud.
2. LISP na mainframech Univac 1100
Jedním z prvních mainframů, na kterých byl programovací LISP implementován, byly mainframy UNIVAC řady 1100. Jednalo se o počítače, které se v některých ohledech podobaly strojům firmy IBM. Taktéž se jednalo o mainframy, jejichž aritmeticko-logické jednotky zpracovávaly 36bitové operandy a i struktura jejich pamětí byla navržena takovým způsobem, aby se mohla načítat i zapisovat přímo 36bitová slova. Počítače UNIVAC dokázaly zpracovávat celočíselné údaje o šířce 36 bitů, osmnáctibitová čísla (ty byly uloženy ve dvojicích v každém slově), dvanáctibitová čísla (tři v jednom slově), devítibitová čísla (čtyři v každém slově) a konečně současně šestici šestibitových čísel. Pro implementaci seznamů používaných v programovacím jazyku LISP jak pro uložení dat, tak i pro reprezentaci vlastních programů, bylo nejvýhodnější použít osmnáctibitové číselné údaje uložené v jednom slově v operační paměti. Vzhledem k tomu, že typická kapacita operační paměti byla rovna 32768, popř. 65536 slovům, bylo použití 18bitových ukazatelů více než dostatečné.
Obrázek 3: Část počítače UNIVAC 1107.
I instrukční sada těchto mainframů byla upravena takovým způsobem, aby většina instrukcí měla šířku 36bitů. Do takto širokých slov bylo možné kromě samotného operačního kódu instrukce (rozeznávalo se celkem 114 instrukcí) a adres operandů uložit i šestnáctibitovou adresu. Původní UNIVACy nesoucí čísla 1101 až 1105 (které však navzdory svému číslování nejsou součástí „série 1100“) měly aritmeticko-logickou jednotku i řadič vytvořeny s pomocí elektronek, další typy (1107 až 1110) již používaly tranzistory a posléze i první generaci integrovaných obvodů. Taktéž konstrukce pamětí se změnila z původních pamětí feritových na paměti polovodičové. První strojem ze série 1100, na kterém byl s poměrně velkým úspěchem provozován jazyk LISP, nesl označení UNIVAC 1107 a začal být prodáván již v roce 1962. Využíval feritovou paměť o kapacitě v rozsahu 16384 slov až 65536 slov (každé slovo mělo šířku 36bitů). Paměť byla rozdělena do dvou banků – jeden bank byl rezervován pro program (instrukce), druhý pro data, což zdvojnásobilo průměrnou rychlost přístupu do paměti z původních čtyř mikrosekund na pouhé dvě mikrosekundy. Jedná se vlastně o určitý ústupek z von Neumannovy architektury, který způsoboval problémy i při implementaci LISPu, ovšem tvůrci jeho interpretru nakonec tento problém vyřešili úpravou celého systému.
Obrázek 4: Součásti počítače UNIVAC 1107. Za pozornost stojí především menší zařízení v popředí (napravo). Jedná se o čtečku děrných štítků nazývanou místo „card reader“ termínem „card eater“. Povšimněte si velkého tlačítka na tomto zařízení. Pokud začala čtečka děrné štítky opravdu kousat, mohla se tímto tlačítkem ihned vypnout a zachránit tak alespoň zbytek programu nebo dat.
3. Architektura počítačů CONS a CADR
Počítače nazvané CONS a CADR vznikly na slavné Massachusettské universitě (MIT) v laboratoři umělé inteligence (AI lab), v níž mj. pracoval i Richard Stallman. Tyto počítače byly přímo optimalizovány pro běh interpretru jazyka LISP. Zatímco počítač nazvaný CONS (což je, jak již víme z předchozí části tohoto seriálu, současně i jméno konstruktoru tečka-dvojice, tj. jedné z nejzákladnějších operací) byl spíše prototypem, počítač CADR byl již vyroben v malé sérii cca třiceti kusů. Název tohoto počítače (druhého v pořadí) je také příhodný, protože LISPovská funkce CADR vrací druhý prvek seznamu. Někteří členové AI lab v pozdějších letech založili společnost Symbolics Corp., která taktéž vyráběla počítače specializované na programovací jazyk LISP. Prvním výrobkem této firmy byl počítač LM-2 (nazývaný také kvůli jeho rychlosti „the dog“), jehož architektura byla založena právě na počítači CADR.
Obrázek 5: Štítek s logem počítače CADR.
Protože se počítače CADR staly mezi výzkumníky v oblasti AI poměrně populární a vznikla pro ně celá řada zajímavých aplikací, objevila se po nástupu výkonných osobních počítačů snaha o záchranu těchto aplikací. Dnes již existuje emulátor počítače CADR a dokonce byly nalezeny (po cca 35 letech!) i magnetické pásky obsahující původní programové vybavení, které je z velké části převedeno a upraveno tak, aby bylo možné tyto programy úspěšně spustit v emulátoru, což může být pro čtenáře zajímající se o LISP zajímavé, neboť některé programy jsou skutečně složité a rozsáhlé – prý se jedná o jedny z nejrozsáhlejších LISPovských programů vůbec.
Obrázek 6: Program určený původně pro počítač CADR spuštěný v emulátoru.
4. Společnost Thinking Machines a architektura Connection Machine
Další zajímavou architekturu počítačů, která je prakticky nerozlučně spjata s LISPem, představují superpočítače Connection Machine, které jsou v mnoha ohledech odlišné od výstavby většiny ostatních typů superpočítačů. Pravděpodobně největší podíl na vzniku architektury Connection Machine má Danny Hillis (a nepřímo též známý Marvin Minsky), který spolu s dalším společníkem Sheryl Handlerovou v roce 1983 založil společnost nazvanou poněkud nadneseně Thinking Machines Corporation. Tato společnost po třech letech vývoje představila zcela nový typ superpočítače nazvaného Connection Machine 1, známého též pod zkráceným názvem CM-1. Snahou (nebo možná spíše vizí) Dannyho Hillise bylo vytvoření počítače, který by skutečně myslel. V polovině osmdesátých let minulého století totiž prakticky všechny superpočítače sice měly poměrně velký výpočetní výkon (měřený většinou v jednotkách MIPS nebo MFLOPS), ale jejich schopnosti v oblasti umělé inteligence byly naprosto nedostatečné – neuměly například rozeznat lidské obličeje, zpracovat jazyk pětiletého dítěte, dokázat indukcí nějaké jednodušší tvrzení atd.
Obrázek 7: Superpočítač Connection Machine 1.
Hillis se domníval, že hlavní překážkou v dalším vývoji počítačů s umělou inteligencí není hrubý výpočetní výkon, ale jejich samotná architektura, protože stávající stroje byly vybaveny pouze několika výkonnými procesory (podobně jako dnes běžné pracovní počítače). Naproti tomu lidský mozek obsahuje relativně málo výkonné neurony, které jsou však zapojeny do rozsáhlé „propojovací sítě“, přičemž právě tato propojovací síť je pro činnost mozku (pravděpodobně) mnohem důležitější než schopnosti či rychlost samotných neuronů. Podobný princip se Hillis snažil aplikovat i při návrhu superpočítačů, které měly být složeny z velkého množství poměrně málo výkonných procesorů, ovšem celkový počet procesorů by měl dosahovat minimálně řádů tisíců. Výsledkem jeho snah byla právě architektura Connection Machine, pro níž byl jako hlavní programovací jazyk zvolen dialekt LISPu nazvaný *LIST (StarLisp), jenž obsahoval speciální formy umožňující provádět některé výpočty paralelně (nastavení všech prvků seznamu na určitou hodnotu v konstantním čase, hledání v neseřazené posloupnosti v logaritmickém čase atd.).
Obrázek 8: Část superpočítače Connection Machine 5.
5. Connection Machine 1 a 2
Počítače Connection Machine 1 a Connection Machine 2 jsou si v mnohém podobné, takže si je popíšeme společně. Jedná se o počítače vybavené několika stovkami až několika tisíci mikroprocesorů (maximální počet je roven 65536 procesorům), z nichž je každému přidělena relativně malá operační paměť o kapacitě 4 kb. Každý mikroprocesor dokáže v daný okamžik zpracovat pouze jediný bit informace (program je pro všechny procesory stejný), ovšem všechny procesory pracují současně (paralelně), takže při použití vhodně zvoleného algoritmu lze říci, že počítač s například 8192 procesory zpracuje vektor 8192 bitů v jednom kroku (cyklu), což je zajisté mnohem více, než můžeme očekávat od současných 32bitových či 64bitových procesorů. Nejdůležitější částí CM-1 a CM-2 však nejsou jednotlivé procesory a jejich paměti, ale propojovací síť, protože právě její struktura určuje, zda všechny procesory budou skutečně pracovat paralelně či zda na sebe budou čekat.
Obrázek 9: Konfigurace a vzájemné propojení procesorů a matematického koprocesoru u počítače Conection Machine 2.
Procesory jsou vzájemně propojeny sítí, jejichž topologie odpovídá dvanáctidimenzionální kostce, což znamená, že každý procesor se může spojit s jedenácti sousedními procesory. Díky tomu je průměrná vzdálenost mezi dvěma procesory velmi malá – dvanáct sousedních procesorů je od sebe vzdáleno jeden „skok“, 144 procesorů dva skoky a 1728 procesorů tři skoky (pro jednoduchost můžeme říci, že čím větší počet skoků, tím více času je nutné obětovat pro přenos dat). Aby se počítače Connection Machine mohly používat i v aplikacích, v nichž se provádí i složitější výpočty, byl počítač CM-2 navíc vybaven i matematickými koprocesory Weitek 3132. Ovšem tyto koprocesory nebyly přidány ke každému mikroprocesoru, protože by se jednalo o značné plýtvání a nevyváženou architekturu. Namísto toho byl numerický koprocesor používán 32 jednobitovými procesory, které společně tvořily základní modul počítače, jichž mohlo být nainstalováno i několik tisíc (viz též devátý obrázek). Celkově mohl počítač CM-2 obsahovat až 512 MB RAM a pole RAID s kapacitou 25 GB, což jsou na dobu jeho vzniku (1987) úctyhodná čísla. V kontextu tohoto článku je důležitá i informace, že většina programů pro tyto počítače byla napsána v již zmiňovaném *LISPu.
6. Connection Machine 5
Dalším superpočítačem, který firma Thinking Machines navrhla a s poměrně velkým úspěchem i prodávala, byl počítač Connection Machine 5 (CM-5). Architektura tohoto počítače se hned v několika ohledech odlišovala od jeho předchůdců. Zatímco všechny procesory v CM-1 i CM-2 zpracovávaly stejné instrukce, tj. jednalo se o architekturu SIMD (Single Instruction, Multiple Data), je v případě CM-5 použita architektura MIMD, což znamená, že každý procesor nejenže zpracovává různá data, ale může provádět i jiný program (Multiple Instructions, Multiple Data). Taktéž došlo ke změně parametrů vlastních procesorů, protože se namísto jednoduchých jednobitových mikroprocesorů používají v CM-5 plnohodnotné procesory SPARC umístěných v uzlech, jejichž počet se může pohybovat od šestnácti do šestnácti tisíc (přesněji 16384).
Obrázek 10: Design počítače Connection Machine 5 se skutečně povedl, jedná se pravděpodobně o nejelegantnější superpočítač, který byl kdy vyroben.
Výpočetní výkon Connection Machine 5 se oproti CM-1 a CM-2 samozřejmě zvýšil, ovšem rozdělování práce mezi jednotlivé procesory je kvůli architektuře MIMD složitější. Taktéž se změnila topologie propojovací sítě, protože se namísto hyperkostky používá topologie „tlustého“ stromu (fat tree), konkrétně jedna z variant čtyřstromu (quad tree). Podrobnosti o programování CM-5 si řekneme v následující části tohoto seriálu.
Obrázek 11: Další pohled na Connection Machine 5. Červené diody jsou rozsvěcovány podle stavu jednotlivých mikroprocesorů, ale kromě toho mají svůj nezanedbatelný vizuální účinek. Pokud skutečně existuje Matrix, pak pravděpodobně (po)běží na další generaci CM-5 :-)
7. Obsah následující části seriálu
V následující části seriálu o historii počítačů dokončíme problematiku programovacího jazyka LISP. Ukážeme si například práci s lambda výrazy, které jsou základem pro většinu dalších jazykových konstrukcí, použití konstrukcí typu apply, map či reduce i základy tvorby maker v Common Lispu.
8. Literatura
- Hillis, D.
„New Computer Architectures and Their Relationship to Physics or Why CS is No Good“
Int J. Theoretical Physics 21 (3/4) 255–262. - Lewis W. Tucker, George G. Robertson,
„Architecture and Applications of the Connection Machine“
Computer, vol. 21, no. 8, pp. 26–38, August, 1988. - Arthur Trew and Greg Wilson (eds.) (1991)
„Past, Present, Parallel: A Survey of Available Parallel Computing Systems“
New York: Springer-Verlag. ISBN 0–387–19664–1. - W. Daniel Hillis and Lewis W. Tucker
„The CM-5 Connection Machine: A Scalable Supercomputer“
In Communications of the ACM, Vol. 36, No. 11 (November 1993) - Cliff Lasser, Jeff Mincy, J.P. Massar
„The Essential *LISP Manual“
Thinking Machines Corporation, 1986. - Anonymous
„Getting Started in *Lisp, Version 6.1“
Thinking Machines Corporation, Cambridge, Massachusetts, June 1991. - Anonymous
„*Lisp Dictionary“
Thinking Machines Corporation, Cambridge, Massachusetts. - Anonymous
„*Lisp Timesharing User's Guide“
Online at CMU AI Repository - Zdzislaw Meglicki
„The CM5 *Lisp Course“
Centre for Information Science Research, The Australian National University, 1994 - McCarthy
„Recursive functions of symbolic expressions and their computation by machine, part I“
1960 - Guy L. Steele
„History of Scheme“
2006, Sun Microsystems Laboratories - Kolář J., Muller K.:
„Speciální programovací jazyky“
Praha 1981 - „AutoLISP Release 9, Programmer's reference“
Autodesk Ltd., October 1987 - „AutoLISP Release 10, Programmer's reference“
Autodesk Ltd., September 1988 - McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I.
„LISP 1.5 Programmer's Manual“
MIT Press. ISBN 0 262 130 1 1 4 - Carl Hewitt; Peter Bishop and Richard Steiger
„A Universal Modular Actor Formalism for Artificial Intelligence“
1973 - Feiman, J.
„The Gartner Programming Language Survey (October 2001)“
Gartner Advisory
9. Odkazy na Internetu
- *Lisp
http://en.wikipedia.org/wiki/*Lisp - Lisp machine
http://en.wikipedia.org/wiki/Lisp_machine - MIT CADR Lisp Machine FAQ
http://www.unlambda.com/cadr/cadr_faq.html - Symbolics LISP Machines
http://www.frobenius.com/symbolics.htm - UNIVAC
http://en.wikipedia.org/wiki/Univac - UNIVAC 1100/2200 series
http://en.wikipedia.org/wiki/UNIVAC_1100/2200_series#UNIVAC_1100_series - Allegro CL Examples and Utilities
http://examples.franz.com/index.html - LISP 1.5 for the Univac 1100 Mainframe
http://www.frobenius.com/univac.htm - STARSIM: Thinking Machines' *Lisp Simulator
http://www-2.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/lisp/impl/starlisp/0.html - Connection Machine
http://en.wikipedia.org/wiki/Connection_Machine - Connection Machine –1–2–5
http://ed-thelen.org/comp-hist/vs-cm-1–2–5.html - Richard Feynman and The Connection Machine
http://www.longnow.org/essays/richard-feynman-connection-machine/ - Sheryl Handler
http://en.wikipedia.org/wiki/Sheryl_Handler - W. Daniel Hillis
http://en.wikipedia.org/wiki/Danny_Hillis - The Rise and Fall of Thinking Machines
http://www.inc.com/magazine/19950915/2622.html - Lisp (programming language)
http://en.wikipedia.org/wiki/Lisp_(programming_language) - On Lisp
http://paulgraham.com/onlisptext.html?asdf - Lambda calculus
http://en.wikipedia.org/wiki/Lambda_calculus - A Short Introduction to the Lambda Calculus
http://www.cs.bham.ac.uk/~axj/pub/papers/lambda-calculus.pdf - A Tutorial Introduction to the Lambda Calculus
http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf - Scheme (programming language)
http://en.wikipedia.org/wiki/Scheme_(programming_language) - An Introduction to Scheme and its Implementation
ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html - The latest version of the Scheme standard: R6RS
http://www.r6rs.org/ - Humor on Computers, Systems and Programming
http://www-crypto.htw-saarland.de/weber/misc/programming.html - Teach Yourself Scheme in Fixnum Days
http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html - AutoLISP
http://en.wikipedia.org/wiki/AutoLISP - Rosetta Code – Category:Lisp
http://rosettacode.org/wiki/Category:Lisp - Retrocomputing – MIT CADR Lisp Machines
http://www.unlambda.com/cadr/index.html
