Programovací jazyk LISP a LISP machines

Pavel Tišnovský 25. 3. 2010

V dnešní části seriálu o historii počítačů se opět budeme zabývat problematikou jazyka LISP. Oproti předchozím článkům si na chvíli odpočineme od popisu syntaxe a především sémantiky jazyka. Namísto toho se seznámíme s počítačovými architekturami, které byly optimalizovány pro běh programů napsaných v LISPu.

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

5. Connection Machine 1 a 2

6. Connection Machine 5

7. Obsah následující části seriálu

8. Literatura

9. Odkazy na Internetu

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.

ibm07

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.

23_lisp3

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é.

23_lisp3

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.

23_lisp3

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.

23_lisp3

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.

23_lisp3

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.

23_lisp3

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.).

23_lisp3

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.

23_lisp3

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áctidimen­zioná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).

23_lisp3

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.

23_lisp3

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

  1. 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.
  2. Lewis W. Tucker, George G. Robertson,
    „Architecture and Applications of the Connection Machine“
    Computer, vol. 21, no. 8, pp. 26–38, August, 1988.
  3. 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.
  4. 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)
  5. Cliff Lasser, Jeff Mincy, J.P. Massar
    „The Essential *LISP Manual“
    Thinking Machines Corporation, 1986.
  6. Anonymous
    „Getting Started in *Lisp, Version 6.1“
    Thinking Machines Corporation, Cambridge, Massachusetts, June 1991.
  7. Anonymous
    „*Lisp Dictionary“
    Thinking Machines Corporation, Cambridge, Massachusetts.
  8. Anonymous
    „*Lisp Timesharing User's Guide“
    Online at CMU AI Repository
  9. Zdzislaw Meglicki
    „The CM5 *Lisp Course“
    Centre for Information Science Research, The Australian National University, 1994
  10. McCarthy
    „Recursive functions of symbolic expressions and their computation by machine, part I“
    1960
  11. Guy L. Steele
    „History of Scheme“
    2006, Sun Microsystems Laboratories
  12. Kolář J., Muller K.:
    „Speciální programovací jazyky“
    Praha 1981
  13. „AutoLISP Release 9, Programmer's re­ference“
    Autodesk Ltd., October 1987
  14. „AutoLISP Release 10, Programmer's re­ference“
    Autodesk Ltd., September 1988
  15. McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I.
    „LISP 1.5 Programmer's Ma­nual“
    MIT Press. ISBN 0 262 130 1 1 4
  16. Carl Hewitt; Peter Bishop and Richard Steiger
    „A Universal Modular Actor Formalism for Artificial Intelligence“
    1973
  17. Feiman, J.
    „The Gartner Programming Language Survey (October 2001)“
    Gartner Advisory

9. Odkazy na Internetu

  1. *Lisp
    http://en.wiki­pedia.org/wiki/*Lisp
  2. Lisp machine
    http://en.wiki­pedia.org/wiki/Lis­p_machine
  3. MIT CADR Lisp Machine FAQ
    http://www.un­lambda.com/ca­dr/cadr_faq.html
  4. Symbolics LISP Machines
    http://www.fro­benius.com/sym­bolics.htm
  5. UNIVAC
    http://en.wiki­pedia.org/wiki/U­nivac
  6. UNIVAC 1100/2200 series
    http://en.wiki­pedia.org/wiki/U­NIVAC_1100/220­0_series#UNIVAC_1100_se­ries
  7. Allegro CL Examples and Utilities
    http://examples­.franz.com/in­dex.html
  8. LISP 1.5 for the Univac 1100 Mainframe
    http://www.fro­benius.com/uni­vac.htm
  9. STARSIM: Thinking Machines' *Lisp Simulator
    http://www-2.cs.cmu.edu/af­s/cs/project/ai-repository/ai/lan­g/lisp/impl/star­lisp/0.html
  10. Connection Machine
    http://en.wiki­pedia.org/wiki/Con­nection_Machi­ne
  11. Connection Machine –1–2–5
    http://ed-thelen.org/comp-hist/vs-cm-1–2–5.html
  12. Richard Feynman and The Connection Machine
    http://www.lon­gnow.org/essa­ys/richard-feynman-connection-machine/
  13. Sheryl Handler
    http://en.wiki­pedia.org/wiki/She­ryl_Handler
  14. W. Daniel Hillis
    http://en.wiki­pedia.org/wiki/Dan­ny_Hillis
  15. The Rise and Fall of Thinking Machines
    http://www.in­c.com/magazine/19950915/­2622.html
  16. Lisp (programming language)
    http://en.wiki­pedia.org/wiki/Lis­p_(programmin­g_language)
  17. On Lisp
    http://paulgra­ham.com/onlis­ptext.html?as­df
  18. Lambda calculus
    http://en.wiki­pedia.org/wiki/Lam­bda_calculus
  19. A Short Introduction to the Lambda Calculus
    http://www.cs­.bham.ac.uk/~ax­j/pub/papers/lam­bda-calculus.pdf
  20. A Tutorial Introduction to the Lambda Calculus
    http://www.inf.fu-berlin.de/leh­re/WS03/alpi/lam­bda.pdf
  21. Scheme (programming language)
    http://en.wiki­pedia.org/wiki/Sche­me_(programmin­g_language)
  22. An Introduction to Scheme and its Implementation
    ftp://ftp.cs.u­texas.edu/pub/gar­bage/cs345/sch­intro-v14/schintro_toc­.html
  23. The latest version of the Scheme standard: R6RS
    http://www.r6rs­.org/
  24. Humor on Computers, Systems and Programming
    http://www-crypto.htw-saarland.de/we­ber/misc/program­ming.html
  25. Teach Yourself Scheme in Fixnum Days
    http://www.ccs­.neu.edu/home/do­rai/t-y-scheme/t-y-scheme.html
  26. AutoLISP
    http://en.wiki­pedia.org/wiki/Au­toLISP
  27. Rosetta Code – Category:Lisp
    http://rosetta­code.org/wiki/Ca­tegory:Lisp
  28. Retrocomputing – MIT CADR Lisp Machines
    http://www.un­lambda.com/ca­dr/index.html

Ohodnoťte jako ve škole:

Průměrná známka 1,23

Našli jste v článku chybu?
Zasílat nově přidané názory e-mailem
Vitalia.cz: Proč máme prasklý chléb nejraději?

Proč máme prasklý chléb nejraději?

DigiZone.cz: Druhá anglická liga pro Digi TV

Druhá anglická liga pro Digi TV

Root.cz: DDoS útoky aneb když vám zahltí dráty

DDoS útoky aneb když vám zahltí dráty

Lupa.cz: Jak EET vidí ajťák aneb Drahá vražda UX

Jak EET vidí ajťák aneb Drahá vražda UX

120na80.cz: Tady se vaří padělané léky

Tady se vaří padělané léky

DigiZone.cz: Změní se veřejnoprávní status ČT?

Změní se veřejnoprávní status ČT?

120na80.cz: Velký přehled: 7 očkování proti exotickým nemocem

Velký přehled: 7 očkování proti exotickým nemocem

Vitalia.cz: Před, nebo po snídani? Kdy je lepší čistit si zuby

Před, nebo po snídani? Kdy je lepší čistit si zuby

Root.cz: Zákon o hazardu je v rozporu s ústavou

Zákon o hazardu je v rozporu s ústavou

Lupa.cz: Válka e-shopů. Alza končí s Heurekou

Válka e-shopů. Alza končí s Heurekou

DigiZone.cz: Šlágr TV: pokuta 100 tisíc za on-line

Šlágr TV: pokuta 100 tisíc za on-line

Vitalia.cz: 7 nemocí očí, které musíte léčit včas

7 nemocí očí, které musíte léčit včas

Podnikatel.cz: Šizený guláš na pultě. Jako Lidl to nedělejte

Šizený guláš na pultě. Jako Lidl to nedělejte

Podnikatel.cz: Rošáda v živnostech. Týká se vás?

Rošáda v živnostech. Týká se vás?

120na80.cz: 10 dezinfekcí: Vede „starý dobrý“ peroxid

10 dezinfekcí: Vede „starý dobrý“ peroxid

Lupa.cz: Kam si doma dáte internet věcí? Na polici?

Kam si doma dáte internet věcí? Na polici?

Lupa.cz: Nová podoba Instagramu? Katastrofa

Nová podoba Instagramu? Katastrofa

Vitalia.cz: Mražené ryby z Makra byly falšované

Mražené ryby z Makra byly falšované

Vitalia.cz: SÚKL: vakcíny jsou bezpečné a s autismem nesouvisí

SÚKL: vakcíny jsou bezpečné a s autismem nesouvisí

120na80.cz: Jak si udržet zdravou vaginu

Jak si udržet zdravou vaginu