Hlavní navigace

Programovací jazyky používané (nejen) v SSSR (část 3 – LISP)

11. 3. 2010
Doba čtení: 14 minut

Sdílet

V dnešním článku o historii výpočetní techniky dokončíme popis programovacího jazyka SNOBOL a poté se zaměříme na programovací jazyk, který spolu s programovacím jazykem C snad nejvíce ovlivnil celou informatiku, a to jak v teoretické, tak i praktické rovině. Jedná se o jazyk LISP, navržený už v roce 1958.

Obsah

1. SNOBOL: vyhledávání vzorů v řetězcích

2. Historie vzniku programovacího jazyka LISP

3. Dialekty jazyka LISP

4. Základní datové typy LISPu – atomy a seznamy

5. Tečka-dvojice: základ pro tvorbu složitějších datových struktur

6. Vliv architektury mainframu IBM 704 na strukturu programovacího jazyka LISP

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

8. Literatura

9. Odkazy na Internetu

1. SNOBOL: vyhledávání vzorů v řetězcích

V předchozí části seriálu o historii výpočetní techniky jsme si popsali základy programování v jazyce SNOBOL (StriNg Oriented SymBOlic Language), který byl vyvinut a implementován v průběhu šedesátých let minulého století v Bellových laboratořích Davidem J. Farberem, Ralphem E. Griswoldem a Ivanem P. Polonskym. První verze tohoto jazyka byla vytvořena na sálovém počítači IBM 7090, později však vznikly implementace pro mnoho dalších počítačových architektur: mainframů, minipočítačů a posléze i minipočítačů (některé z implementací tohoto jazyka vznikly i v zemích RVHP). Taktéž jsme si řekli, že tento jazyk byl určený především pro zpracování textových dat (rozpoznávání vzorů atd.), čemuž je podřízena i jeho syntaxe a sémantika. Každý programový řádek může být složen z pěti bloků (oddělených od sebe buď mezerami nebo speciálními znaky), přičemž žádný z těchto bloků není povinný. Jedná se o následující blo­ky:

  1. náveští (label)
  2. subjekt (subject)
  3. vzor (pattern)
  4. objekt (object)
  5. odkaz(y) na jiné příkazy (goto)

Všechny demonstrační příklady uvedené v předchozí části tohoto seriálu však na svých programových řádcích obsahovaly jen některé bloky, především návěští, objekt (výraz či příkaz) a popř. odkazy (skoky) na jiné programové řádky – veškeré podmíněné příkazy i smyčky jsou totiž v jazyce SNOBOL realizovány právě pomocí podmíněných či nepodmíněných skoků. Nyní si pojďme říci, jakým způsobem se používají zbývající dva bloky, ze kterých se může skládat každý programový řádek ve SNOBOLu. Blok nazvaný vzor (pattern) lze využít pro vyhledávání podřetězce v řetězci. Pokud je vzor v řetězci nalezen, je vrácen jako výsledek výrazu, čehož lze využít při rozeskoku (prázdný řetězec vrácený v případě, že vzor nebyl nalezen, odpovídá při rozeskocích pravdivostní hodnotě false, všechny ostatní řetězce jsou ekvivalentní hodnotě true). Vyhledávaný vzor sice nemůže být zapsán pomocí plnohodnotných regulárních výrazů (ty v době návrhu jazyka SNOBOL neexistovaly), ale je možné použít jejich podmnožinu (včetně rekurzivní definice), jak je patrné z následujících demonstračních příkladů:

Načtení řádku ze standardního vstupu a zjištění, zda zadaný řetězec obsahuje zapsaný vzor:

ADRESA = INPUT
ADRESA 'www.root.cz'

Vyhledávaný vzor samozřejmě může být uložen v proměnné:

ROOT = 'www.root.cz'
ADRESA = INPUT
ADRESA ROOT

Vzor pro vyhledání kombinací dvou slov popisujících typ celočíselné proměnné či konstanty v céčku:

PREFIX = 'signed' | 'unsigned' | ''
WIDTH = 'short' | 'long' | 'long long' | ''
TYPE = 'int' | ''
DEFINITION = PREFIX WIDTH TYPE

Ve vyhledávaných vzorech lze použít i závorky pro úpravu priority. Konkatenace dvou vzorů má vyšší prioritu než zápis více alternativ pomocí znaku |, z čehož vyplývá, že vzory PATTERN1 a PATTERN2 jsou identické:

P = 'BE' | 'BEA' | 'BEAR'
Q = 'RO' | 'ROO' | 'ROOS'
R = 'DS' | 'D'
S = 'TS' | 'T'
PATTERN1 = P R | Q S
PATTERN2 = (P R) | (Q S)
PATTERN3 = P (R | Q ) S

SNOBOL4 podporuje i rekurzivní definici vzoru:

P = *P 'Z' | 'Y'
PO = P . OUTPUT
'Y' PO       (vytiskne Y)
'YZZZ' PO    (vytiskne YZZZ)
'XYZ' PO     (vytiskne YZ)
'YZZX' PO    (vytiskne YZZ)
'AYZZZZB' PO (vytiskne YZZZZ)

Následující program načítá jednotlivé řádky ze standardního vstupu a odstraňuje z nich komentáře (které jsou reprezentovány řádky začínajícími znakem #). Jedná se tedy o velmi jednoduchý filtr, jakýsi primitivní grep. Nastavením speciální proměnné &ANCHOR na jedničku se scanner jazyka SNOBOL nastaví do režimu, že vyhledává vzor pouze na začátku řetězce:

      &ANCHOR = 1
BEGIN LINE = INPUT   :F(END)
      LINE '#'       :S(BEGIN)
      OUTPUT = LINE  :(BEGIN)
END

2. Historie vzniku programovacího jazyka LISP

Syntaxe jazyka LISP je již po 50 let zdrojem inspirace pro autory vtipů

Historie programovacího jazyka LISP je velmi dlouhá, neboť se jedná o jeden z nejstarších programovacích jazyků vůbec. Autorem teoretického návrhu tohoto jazyka je John McCarthy, který se již v roce 1956 připojil k týmu, jehož úkolem bylo navrhnout algebraický programovací jazyk umožňující zpracování seznamů, jenž by byl vhodný pro vývoj systémů umělé inteligence – AI (zatímco dnes jsou „v kurzu“ enterprise systémy popř. WEB 2.0, v padesátých a šedesátých letech minulého století se jednalo o umělou inteligenci a expertní systémy). McCarthy navrhl, aby se fakta o okolním světě (která může AI při své činnosti použít) lze reprezentovat formou vět ve vhodně strukturovaném formálním jazyce. Posléze se ukázalo, že je výhodné reprezentovat jednotlivé věty formou seznamů. McCarthy myšlenku jazyka vhodného pro AI rozpracoval dále – odklonil se například od infixové notace zápisu algebraických výrazů, protože naprogramování některých manipulací s těmito výrazy (derivace, integrace, zjednodušení výrazů, logická dedukce) bylo zbytečně složité.

lisp01

Obrázek 1: Na tomto grafu evoluce programovacích jazyků můžeme vidět některé jazyky, které jsme si již v tomto seriálu popsali (Fortran, Cobol, SNOBOL, Algol, APL) nebo popíšeme (LISP, Basic).

Následně McCarthy ve svých teoretických pracích (vznikajících v průběhu let 1957 a 1958) ukázal, že je možné pomocí několika poměrně jednoduchých operací (a notací pro zápis funkcí) vytvořit programovací jazyk, který je Turingovsky kompletní (tj. jeho výpočetní mocnost je ekvivalentní Turingovu stroji), ale zápis algoritmů v tomto jazyce je mnohem jednodušší než zápis pravidel pro Turingův stroj. Tento jazyk, jenž byl z velké části založen na Lambda kalkulu (viz následující část tohoto seriálu), obsahoval možnost vytváření rekurzivních funkcí (což byl významný rozdíl například oproti tehdejší verzi FORTRANU), funkce jako argumenty jiných funkcí, podmíněné výrazy (jedna z variant speciální formy), funkce pro manipulaci se seznamy a v neposlední řadě také funkci eval. Na McCarthovu teoretickou práci navázal S. R. Russell, který si uvědomil, že samotná funkce eval, pokud by byla implementována na nějakém počítači, může sloužit jako základ plnohodnotného interpretru jazyka LISP (interpretr LISPu se někdy též označuje zkratkou REPL: Read-Eval-Print-Loop, tj. interpretr ve smyčce načítá jednotlivé výrazy, vyhodnocuje je a následně tiskne jejich výslednou hodnotu). Russell skutečně celou smyčku REPL implementoval – tímto způsobem se zrodila první verze LISPu.

3. Dialekty jazyka LISP

V průběhu dalších více než pěti desetiletí vzniklo mnoho dialektů tohoto programovacího jazyka, například MacLISP, InterLISP, ZetaLISP, XLisp, AutoLISP (původně odvozený z XLispu), Emacs LISP nebo slavný Common LISP. Kromě těchto implementací jazyka LISP, které se od sebe v několika ohledech odlišují (například existencí či neexistencí maker či objektového systému), vznikl v minulosti i nový dialekt tohoto jazyka nazvaný Scheme (původně Schemer), jehož autory jsou Guy L. Steele a Gerald Jay Sussman. Tento dialekt je implementačně jednodušší a také se ho lze naučit rychleji, než mnohé další varianty jazyka LISP. Právě z těchto důvodů se Scheme využívá či využívalo jak při výuce programování, tak i v mnoha open-source projektech, například v textovém editoru Emacs či v grafickém editoru GIMP jako jeden z podporovaných skriptovacích jazyků. Richard Stallman si dokonce přál, aby se Scheme stalo standardním skriptovacím jazykem většiny GNU aplikací, což je idea, která se – především po vzniku dalších vysokoúrovňových programovacích jazyků (Perl, Python, TCL) – nakonec neuskutečnila. Některé rozdíly mezi „klasickým“ LISPem a programovacím jazykem Scheme si popíšeme v dalších dílech tohoto seriálu.

4. Základní datové typy LISPu – atomy a seznamy

Je Matrix napsaný v LISPu nebo Perlu?

Základními datovými typy, se kterými se v LISPu pracuje, jsou atomy a seznamy. Atomy jsou z hlediska tohoto programovacího jazyka základními objekty, které není možné dále dělit, ale je je možné ukládat do seznamů. Atomy mohou být několika typů: jedná se především o symboly (například ABC), čísla (42, 3.1415 atd. – některé interpretry jazyka LISP rozlišují celá čísla, čísla reálná, čísla komplexní a někdy též zlomky, tj. čísla racionální), řetězce („pokus“, „velmi dlouhý řetězec“), vestavěné funkce atd. V reálných programech se atomy ukládají do seznamů, přičemž pro označení začátku a konce seznamu se používají kulaté závorky – levá závorka samozřejmě označuje začátek seznamu a pravá závorka jeho konec. Prvky/elementy seznamu jsou od sebe odděleny alespoň jednou mezerou nebo koncem řádku, což mj. znamená, že seznam může být rozepsán na více řádcích (to je velmi důležité ve chvíli, kdy se pomocí seznamů reprezentují funkce).

Zvláštním a v mnoha ohledech důležitým typem seznamu je prázdný seznam, jenž neobsahuje žádné prvky (elementy) a proto je zapisován buď levou závorkou, za níž ihned následuje závorka pravá (mezi závorkami se tedy nenachází žádný atom ani další seznam, mohou se zde nacházet pouze mezery nebo konce řádků), nebo lze pro jeho zápis alternativně použít symbol nil, který je ekvivalentní prázdnému seznamu (současně se tímto symbolem označuje logická hodnota nepravda, tj. prázdný seznam se v logických výrazech vyhodnocuje na hodnotu false). Seznam může jako své prvky (elementy) obsahovat jak atomy, tak i další vnořené seznamy, což znamená, že se jedná o rekurzivní datovou strukturu, pomocí níž je možné popsat i mnohé další složitější datové struktury, například n-dimenzionální pole, stromy, hierarchické mřížky atd. Pod tímto odstavcem je uvedeno několik příkladů seznamů akceptovaných interpretrem jazyka LISP. Povšimněte si především důsledného vyvážení pravých a levých závorek, především v případě, že seznam obsahuje jako své prvky/elementy další podseznamy:

; komentáře jsou uvozené znakem středník, jak je to demonstrováno na tomto programovém řádku

; prázdný seznam
()

; prázdný seznam - alternativní zápis
nil

; seznam obsahující čtyři atomy (konkrétně se jedná o trojici symbolů a jedno číslo)
(SEZNAM OBSAHUJICI 4 ATOMY)

; seznam obsahující trojici čísel
(42 3.14159 6502)

; dvouprvkový seznam obsahující dva podseznamy, z nichž každý obsahuje dva atomy
((A B) (C D))

; dvouprvkový seznam obsahující dva prázdné podseznamy
(() ())

; jednoprvkový seznam obsahující taktéž jednoprvkový podseznam obsahující prázdný podseznam :-)
((()))

; tříprvkový seznam obsahující jeden symbol a dvě čísla
(+ 1 2)

; tříprvkový seznam obsahující jeden symbol a dvojici podseznamů
(* (+ 1 2) (- 1 2))

Poslední dva seznamy mají zvláštní význam, protože jejich první element představuje symbol reprezentující primitivní (základní) funkci. Programovací jazyk LISP by tento seznam zpracoval tak, že by funkci zavolal s tím, že jí jako parametry předá všechny další prvky seznamu (případné podseznamy se nejdříve rekurzivně vyhodnotí naprosto stejným způsobem). Podrobnosti definování i volání funkcí si uvedeme v následující části tohoto seriálu, kde se mj. seznámíme i s takzvanými speciálními formami.

5. Tečka-dvojice: základ pro tvorbu složitějších datových struktur

předchozí kapitole jsme si řekli, že programovací jazyk LISP je založen na zpracování seznamů. Jak jsou však seznamy uloženy v operační paměti počítače a jak s nimi interpretry tohoto jazyka pracují? Základní interní strukturou, která je však dostupná i programátorům aplikací v jazyce LISP, je takzvaná tečka-dvojice (dotted-pair). Tuto strukturu si můžeme představit jako dvojici ukazatelů, přičemž každý z těchto ukazatelů může obsahovat adresu atomu, adresu další tečka-dvojice nebo speciální hodnotu nil odpovídající v céčku hodnotě NULL či v Javě hodnotě null, tj. jedná se o speciální hodnotu, která interpretru říká, že daný ukazatel neobsahuje žádný odkaz. Tečka-dvojici lze v LISPovských programech zapisovat formou dvojice výrazů (takzvaných S-výrazů) oddělených tečkou, které jsou uzavřeny do kulatých závorek (i když je pravda, že se s tečka-dvojicemi v reálných programech příliš často nesetkáme, především z důvodu nepřehledného zápisu s velkým množstvím závorek):

(1.2)
(1.nil)
(A.(B.C))
(A.(B.nil))
((A.B).C)
((A.B).(C.D))
(ABC.DEF)
((ABC.(DEF.UVW)).XYZ)

Pro přístup k informaci (atomu či další tečka dvojici), na kterou odkazuje první ukazatel tečka dvojice, se používá primitivní funkce CAR, a pro přístup k informaci, na níž se odkazuje druhý ukazatel, lze použít funkci CDR (proč jsou názvy těchto funkcí takto zvláštní, se dozvíme v následující kapitole). Pomocí tečka-dvojic je možné vytvořit klasický seznam následujícím způsobem: první ukazatel každé n-té tečka-dvojice odkazuje na n-tý prvek seznamu (například atom), druhý ukazatel se odkazuje na další (n plus první) tečka-dvojici. Speciálním případem je poslední tečka-dvojice, jejíž druhý ukazatel obsahuje výše uvedenou speciální hodnotu nil. Z následujícího příkladu (obsahujícího ekvivalentní datové struktury) je patrné, že použití syntaxe pro zápis seznamů je přehlednější a současně i kratší, než explicitní zápis tečka-dvojic; ovšem právě znalost vnitřní reprezentace seznamů pomocí tečka-dvojic nám umožňuje pochopit, jak pracují některé základní funkce, včetně již zmíněných funkcí CAR a CDR:

; seznam zapsaný pomocí tečka-dvojic
(1.(2.(3.(4.(5.nil)))))

; běžný způsob zápisu seznamu
(1 2 3 4 5)

; interní struktura seznamu v paměti
;         .
;        / \
;       1   .
;          / \
;         2   .
;            / \
;           3   .
;              / \
;             4   .
;                / \
;               5   nil

Poznamenejme, že další struktury vytvořené pomocí rekurzivně zanořených tečka-dvojic není možné převést na běžné seznamy. Například jednoduchý binární strom se třemi úrovněmi a čtyřmi listy lze reprezentovat buď pomocí tečka-dvojic (v paměti se vytvoří skutečná obdoba binárního stromu), popř. je možné tuto datovou strukturu „simulovat“ pomocí seznamů (ovšem v tomto případě bude paměťová náročnost vyšší kvůli nutnosti ukončení všech podseznamů tečka dvojicí obsahující ve svém druhém ukazateli hodnotu nil):

; binární strom se třemi úrovněmi a čtyřmi listy vytvořený pomocí tečka dvojic
((A.B).(C.D))
; interní podoba této struktury v operační paměti:
;     .
;    / \
;   .   .
;  / \ / \
;  A B C D

; binární strom vytvořený pomocí LISPovských seznamů
((A B) (C D))
; interní podoba této struktury v operační paměti:
;         .
;        / \
;       /   \
;      /     \
;     /       \
;    .         .
;   / \       / \
;   A  .     .  nil
;     / \   / \
;     B nil C  .
;             / \
;             D nil

6. Vliv architektury mainframu IBM 704 na strukturu programovacího jazyka LISP

První implementace programovacího jazyka LISP vznikla na sálovém počítači IBM 704, který byl založený na technologii elektronek a feritových pamětí. Tento počítač, přesněji řečeno jeho aritmeticko-logická jednotka, dokázal zpracovávat numerické či znakové hodnoty uložené ve slovech, jejichž šířka byla rovna 36 bitům (jednalo se buď o celá čísla se znaménkem, čísla uložená ve formátu plovoucí řádové čárky či šestici znaků, z nichž každý byl uložen v šesti bitech). Operační paměť počítače IBM 704 byla z hlediska zpracování dat organizována po slovech o šířce 36 bitů (viz předchozí text), přičemž celkový počet těchto slov uložených v paměti mohl nabývat hodnot 4096, 8192 či 32768, což odpovídá postupně 18 kB, 36 kB a 144 kB (pro představu – v posledním případě musela feritová paměť obsahovat přes jeden milion feritových jadérek a několik desítek tisíc vodičů). Právě 36bitová šířka zpracovávaných slov měla velký vliv na způsob uložení datových struktur LISPu v operační paměti, jak si ostatně řekneme v navazujícím odstavci.

ibm07

Obrázek 2: Sálový počítač IBM-704.

V předchozí kapitole jsme si řekli, že seznamy jsou v LISPu zkonstruovány pomocí tečka-dvojic. Tento způsob konstrukce seznamů vychází přímo z architektury počítače IBM 704, který používal 15bitové adresy, čemuž odpovídá v předchozím odstavci zmíněný maximální počet 32768 adresova­telných slov. V každém 36bitovém slově bylo možné uložit dvě 15bitové adresy nazvané podle svého významu address a decrement. Počítač IBM 704 obsahoval instrukce, pomocí nichž bylo možné jednu z částí address či decrement z 36bitového slova získat a uložit ji do index registru, jenž se používal při adresování operandů strojových instrukcí. Tvůrci první implementace jazyka LISP tuto možnost využili – ukládali tečka-dvojice do 36bitového slova rozděleného na čtyři části: prefix (3 bity), address (15 bitů), decrement (15 bitů) a tag (3 bity). Původně v LISPu existovaly čtyři funkce, pomocí nichž bylo možné získat jednu ze čtyř částí 36bitového slova představujícího tečka dvojici:

Primitivní funkce Význam
CAR Contents of the Address part of Register
CDR Contents of the Decrement part of Register
CPR Contents of the Prefix part of Register
CTR Contents of the Tag part of Register

Z těchto funkcí nakonec ve finální verzi LISPu zůstaly pouze funkce CAR a CDR, které můžeme nalézt v prakticky každém dialektu tohoto jazyka. Druhou oblastí, v níž se projevila architektura počítače IBM 704, byl způsob správy paměti. Původně chtěli tvůrci LISPu použít metodu počítání referencí na objekty (reference counting), ovšem to bylo poměrně problematické – v každém 36bitovém slově zbylo pouhých šest bitů (prefix a tag), navíc rozmístěných takovým způsobem, že jejich sloučení bylo poměrně obtížné. Použití čítačů referencí by tedy vedlo k nutnosti změny významu všech bitů v 36bitovém slově, do čehož se autorům LISPu evidentně nechtělo :-) Proto namísto čítače referencí implementovali automatickou správu paměti pomocí plnohodnotného garbage collectoru, který dokázal pracovat korektně i v případech, kdy se vytvořila datová struktura obsahující cyklus (viz též následující části tohoto seriálu). Pravděpodobně se jednalo o první využití garbage collectoru v široce používaném obecném programovacím jazyce.

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

V následující části seriálu o historii výpočetní techniky si popíšeme některé základní (primitivní) funkce, které jsou dostupné v prakticky každém interpretru programovacího jazyka LISP. Taktéž se seznámíme s takzvanými speciálními formami i způsobem jejich použití při tvorbě rozhodovacích konstrukcí (obdoba podmíněných příkazů). Na závěr si řekneme, jak lze v jazyce LISP použít lambda výrazy, vytvořit (nadefinovat) uživatelské funkce a použít rekurzi namísto programových smyček. „Klasické“ implementace tohoto jazyka totiž neobsahují žádnou programovou konstrukci, pomocí níž by bylo možné programové smyčky zapsat, protože z teoretického hlediska je možné každou programovou smyčku nahradit rekurzí; ovšem některé novější implementace jazyka LISP (například AutoLISP) buď programové smyčky přímo podporují (jedná se o speciální formu, nikoli běžnou primitivní funkci) nebo uživatelům nabízí systém maker (Common Lisp), pomocí nichž lze smyčky poměrně přímočarým způsobem vytvořit.

root_podpora

8. Literatura

  1. McCarthy
    „Recursive functions of symbolic expressions and their computation by machine, part I“
    1960
  2. Guy L. Steele
    „History of Scheme“
    2006, Sun Microsystems Laboratories
  3. Kolář J., Muller K.:
    „Speciální programovací jazyky“
    Praha 1981
  4. „AutoLISP Release 9, Programmer's re­ference“
    Autodesk Ltd., October 1987
  5. „AutoLISP Release 10, Programmer's re­ference“
    Autodesk Ltd., September 1988
  6. 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
  7. Carl Hewitt; Peter Bishop and Richard Steiger
    „A Universal Modular Actor Formalism for Artificial Intelligence“
    1973
  8. Feiman, J.
    „The Gartner Programming Language Survey (October 2001)“
    Gartner Advisory
  9. Griswold R. E., Poage J. F., Polonsky I. P.:
    „The SNOBOL4 Programming Language“
    second edition, Bell Telephone Laboratories, 1968, 1971

9. Odkazy na Internetu

  1. SNOBOL4 and SPITBOL Information
    http://www.sno­bol4.com/
  2. Vanilla Snobol4 Reference Manual
    http://burks.bton­.ac.uk/burks/lan­guage/snobol/cat­spaw/manual/con­tents.htm
  3. SNOBOL4.ORG – SNOBOL4 Resources
    http://www.sno­bol4.org/
  4. Snobol3 – Snobol 3 Interpreter Implemented in Java
    http://serl.cs­.colorado.edu/~den­nis/software/s3­.html
  5. Exploring Beautiful Languages – A guick look at SNOBOL
    http://langex­plr.blogspot.com/2007/12­/quick-look-at-snobol.html
  6. Rosetta Code: Roman_numerals
    http://rosetta­code.org/wiki/Ro­man_numerals
  7. Category:SNOBOL4
    http://rosetta­code.org/wiki/Ca­tegory:SNOBOL4
  8. An introduction to SNOBOL by James Ford
    http://drofmij­.awardspace.com/sno­bol/
  9. Humor on Computers, Systems and Programming
    http://www-crypto.htw-saarland.de/we­ber/misc/program­ming.html
  10. Rosetta Code – Category:Lisp
    http://rosetta­code.org/wiki/Ca­tegory:Lisp

Byl pro vás článek přínosný?

Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.