PicoLisp: minimalistický a přitom překvapivě výkonný interpret Lispu

Obsah

1. PicoLisp: minimalistický a přitom překvapivě výkonný interpret Lispu

2. Interní datové struktury používané interpretrem PicoLispu

3. Typ ukládaných hodnot

4. Automatická správa paměti (garbage collector atd.)

5. Je interpret PicoLispu skutečně pojatý minimalisticky?

6. Základní vlastnosti PicoLispu – tečkové páry a seznamy

7. Další datové struktury postavené nad seznamy: zásobníky, fronty a cyklické seznamy

8. Funkce – základní stavební prvek programů

9. Funkce vyššího řádu

10. Programové smyčky

11. Anonymní funkce

12. Reprezentace numerických hodnot

13. Obsah druhé části článku

14. Příloha: stručná historie vývoje LISPu

15. Literatura

16. Odkazy na Internetu

1. PicoLisp: minimalistický a přitom překvapivě výkonný interpret Lispu

Programovací jazyk LISP za sebou má přibližně šedesátiletou historii, což mj. znamená, že se jedná o jednu z nejdéle existujících rodin programovacích jazyků vůbec (druhá podobná větev je tvořena různými verzemi Fortranu a třetí pak COBOLem). V průběhu oněch necelých šedesáti let vzniklo velké množství různých variant tohoto jazyka, přičemž některé varianty byly implementovány formou interpretru a jiné naopak byly vybaveny překladačem. Z rodiny LISPovských jazyků se vyvinuly i další podobně koncipované jazyky, především pak Scheme (v Linuxu zastupované především projektem Guile) a dnes stále více populární jazyk Clojure. Z „velkých“ LISPů je nutné jmenovat především dialekt Common Lisp. Kromě toho však vzniklo i mnoho minimalisticky pojatých interpretrů a překladačů Lispu. Patří sem například dnes již historický Xlisp, první (původně značně primitivní) AutoLISP a v neposlední řadě i PicoLisp, který si popíšeme dnes.

Interpret programovacího jazyka PicoLisp je – alespoň podle slov autorů tohoto projektu – pojat minimalisticky. To se ovšem týká především způsobu implementace interních datových struktur používaných samotným interpretrem a jeho správcem paměti (garbage collector). Naproti tomu vlastní programovací jazyk je až překvapivě vyspělý, což sice nemusí být na první pohled patrné, ale například při porovnání s podobnými minimalisticky pojatými programovacími jazyky (různými implementacemi Forthu) se ukazuje, že PicoLisp obsahuje jak rozsáhlou základní knihovnu, tak i možnost relativně snadného použití nativních (většinou céčkových) knihoven, které jsou v systému nainstalovány (dokonce existuje možnost propojení PicoLispu s běžící JVM, podle mě je to ale spíše technologické demo a nikoli řešení připravené pro použití v produkci).

Tento programovací jazyk je tedy v případě potřeby možné použít i ve funkci „lepidla“, v němž jsou implementovány pouze vysokoúrovňové části aplikace (tu lze navíc vytvářet a testovat interaktivně), zatímco části nízkoúrovňové mohou být vytvořeny v nějakém jazyku překládaném do nativního kódu. Na podobném předpokladu, tj. na myšlence současného použití vysokoúrovňového a nízkoúrovňového jazyka, byl ostatně postaven i dnes poněkud pozapomenutý jazyk TCL (viz též slavný článek od tvůrce tohoto jazyka, slova tohoto článku se už do značné míry vyplnila), ale i mnohem populárnější skriptovací jazyky (Python, Ruby, Perl, částečně i Lua).

2. Interní datové struktury používané interpretrem PicoLispu

Popisem možností programovacího jazyka PicoLisp se budeme poněkud podrobněji zabývat v navazujících kapitolách; nyní se pojďme alespoň ve stručnosti věnovat tomu, jakým způsobem je interně implementován vlastní interpret a jeho virtuální stroj. Interpretry LISPovských jazyků jsou většinou relativně jednoduché, zejména v porovnání s interpretry jiných programovacích jazyků se složitějšími syntaktickými pravidly. Je tomu tak z toho důvodu, že v LISPu se programy zapisují v notaci, která do značné míry koresponduje s AST (Abstract Syntax Tree), které si překladač či interpret prakticky jakéhokoli programovacího jazyka vytváří ve druhé fázi překladu. PicoLisp tedy parsuje zapsané formy a přímo z nich vytváří interní podobu programu, kterou ukládá do paměti a následně interpretuje.

To, že je interpret PicoLispu pojat minimalisticky, je způsobeno tím, že interně podporuje pouze několik jednoduchých datových typů a navíc jen jediný složený datový typ. Interně jsou totiž všechny hodnoty ukládány do takzvaných „tečkových párů“ (dot-pair, někdy se setkáme s překladem tečka-dvojice), což vlastně není nic jiného, než céčková datová struktura se dvěma prvky. První prvek se z historických důvodů jmenuje car, druhý pak cdr. Tyto prvky obsahují buď vlastní jednoduchou hodnotu (část celého čísla, hodnotu nil atd.) či ukazatel na další tečkový pár. Ve zdrojovém kódu PicoLispu vypadá deklarace tečkového páru (zde nazývaného buňka – cell) dosti nenápadně, ovšem síla plyne až ze způsobu použití:

typedef struct cell {
    struct cell *car;
    struct cell *cdr;
} cell, *any;

3. Typ ukládaných hodnot

Typ hodnoty uložené do car či cdr se snadno pozná z nejnižších tří bitů. Předpokládejme překlad na 32bitové platformě (příkladem může být Raspberry Pi apod.). V takovém případě je sizeof(cell) rovno 64bitům a každý z ukazatelů má následující strukturu:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx010 Číslo (resp. jeho část)
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx100 Symbol
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx000 Pár (ukazatel)

Poznámky:

1. PicoLisp pro čísla používá speciální formát umožňující reprezentovat prakticky jakoukoli hodnotu (omezeni jsme dostupnou kapacitou paměti). Pro malá čísla (do šedesáti bitů na 64bitové platformě) je hodnota přímo uložena v buňce (60 bitů hodnoty, bit pro znaménko následovaný již zmíněnou trojicí bitů 010), pro větší hodnoty pak v buňkách tvořících lineárně vázaný seznam.
2. Nejnižší bit je interně použit správcem paměti typu mark & sweep. Implicitně je nulový (jak je naznačeno před tímto odstavcem), ovšem při označování dostupných buněk je správcem paměti nastavován na jedničku.
3. To, že ukazatel na další pár má spodní tři bity (na 64bitových platformách čtyři bity) nulové, je zcela v pořádku, protože tečkové páry/buňky jsou vždy zarovnány na adresy dělitelné osmi (na 64bitových platformách šestnácti).
4. V celém virtuálním stroji existuje jedna speciální hodnota (vytvořená při inicializaci VM) nazvaná NIL. Ta má hned několik významů; pokud je použita v buňce (což je velmi často), tak se jedná o ukazatel na symbol (tj. druhý typ hodnoty).

4. Automatická správa paměti (garbage collector atd.)

Žádné další složitější či rozsáhlejší datové struktury, než jsou výše zmíněné tečkové páry alias buňky, v PicoLispu nenajdeme. Co to však znamená v praxi? Největší dopad má tato vlastnost na implementaci správce paměti (garbage collector), který má do značné míry ulehčenou práci – nikdy totiž nemusí provádět přeskupování bloků paměti jen proto, aby se v ní vytvořilo místo například pro rozsáhlejší pole či pro delší řetězec (to je naopak poměrně velký problém například pro správce paměti v Javě atd. – velké objekty jsou mnohdy spravovány speciálním způsobem). Celá paměť, přesněji řečeno halda (heap), se v případě PicoLispu alokuje ve větších blocích, které mohou mít velikost například jeden megabajt (to je výchozí hodnota, ale při překladu ji lze změnit předeklarováním konstanty CELLS v hlavičkovém souboru pico.h – lze tak sledovat chování správce paměti):

#define CELLS (1024*1024/sizeof(cell)) // Heap allocation unit 1MB
 
typedef struct heap {
    cell cells[CELLS];
    struct heap *next;
} heap;

Vidíme, že jednotlivé bloky tvoří lineárně vázaný seznam (další lineární seznam je použit pro svázání volných buněk v rámci bloků).

V těchto blocích je vytvořeno místo pro n tečkových párů (buněk), přičemž každé z míst může být buď skutečně obsazeno nebo je volné. Pokud je dané místo volné, obsahuje ukazatel na další volné místo. Všechna volná místa na haldě tak tvoří jediný lineárně vázaný seznam. Alokátor paměti tedy může jednoduše začít paměť přidělovat od začátku tohoto seznamu, pamatovat si ukazatel na první prvek seznamu a přesně od tohoto místa alokovat popř. hledat další volnou oblast paměti.

Správce paměti je typu mark & sweep. Ve fázi mark se označují dostupné tečkové páry (pro tento účel je vyhrazen nejnižší bit v každém slovu), ve fázi sweep se pak neoznačené tečkové páry zneplatňují a přidávají do seznamu volných buněk. Může dojít i k uvolnění celého bloku paměti (tj. jediným systémovým voláním se uvolní celý jeden megabajt). Mimochodem – celý správce paměti je implementován ve zdrojovém souboru o velikosti necelých čtyř kilobajtů a má jen 184 řádků, což skutečně je minimalistické pojetí (otázkou ovšem zůstává chování garbage collectoru u aplikací běžících například několik měsíců).

5. Je interpret PicoLispu skutečně pojatý minimalisticky?

Zdrojové kódy PicoLispu existují ve dvou variantách. Pro všechny 32bitové procesory (a pro architektury odlišné od x86_64) se používá varianta naprogramovaná v jazyce C, pro 64bitové procesory řady x86_64 pak varianta, v níž je část zdrojových kódů vytvořena v assembleru a je vůči céčkové variantě optimalizována. Podívejme se jen pro ilustraci na velikost výsledného binárního kódu interpretru a virtuálního stroje PicoLispu v porovnání s dalšími interpretry/VM.

Architektura x86_64, balíčky z Linux Mintu

Architektura ARM11, balíčky z Raspbiannu, PicoLisp přeložený autorem článku

Poznámky:

1. Nejedná se o příliš férové porovnání, protože například nebereme v úvahu množství zabudovaných funkcí dostupných programátorům atd. (například v případě jazyka Lua nemáme k dispozici knihovnu pro práci s regulárními výrazy atd.)
2. Raspbian nebyl zvolen náhodou, protože právě na Raspberry Pi má použití PicoLispu svůj význam. Na výkonnějších desktopech a serverech se vyplatí použít buď Common Lisp nebo rovnou Clojure.
3. Na Raspbiannu se musí nepatrně upravit Makefile tak, aby se nepoužíval přepínač -m32.
4. Na Raspbiannu jsem nejprve provedl překlad s výchozí volbou -O2 (optimalizace na výkon) a posléze i s volbou -Os (menší strojový kód).
5. Povšimněte si, že ostatní binární soubory jsou pro ARM11 (ARMv6) menší, což může být způsobeno použitím instrukční sady Thumb, popř. méně agresivními optimalizacemi (rozbalování programových smyček atd.)

6. Základní vlastnosti PicoLispu – tečkové páry a seznamy

Víme již, že základní interní strukturou PicoLispu je takzvaný tečkový pár (dotted-pair). Tečkový pár je možné v LISPovských programech zapisovat formou dvojice výrazů (takzvaných S-výrazů) oddělených tečkou (a většinou i mezerami, v případě čísel jsou mezery nutností), 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). V následujících ukázkách je vždy první řádek zapsán programátorem, druhý řádek je vyhodnocen interpretrem PicoLispu:

Základní způsob zápisu tečkového páru:

(1 . 2)
(1 . 2)

Musí se skutečně jednat o pár, což je hlídáno:

(1 . 2 . 3)
(1 . 2) -- Bad dotted pair

Složitější datová struktura tvořená rekurzivně zanořenými tečkovými páry:

(1 . ((2 . 3) . 4))
(1 (2 . 3) . 4)

Zde se opět pokoušíme o vytvoření trojice:

(1 . (2 . 3) . 4)
(1 2 . 3) -- Bad dotted pair

Někdy je nutné interpretru zakázat pokus o vyhodnocení zadáním apostrofu:

'((1 . 2) . (3 . 4))
((1 . 2) 3 . 4)

A nyní přichází na řadu velmi zajímavá vlastnost: rekurzivní tečkové páry zakončené dvojicí (atom . NIL) vytvoří seznam, resp. přesněji řečeno seznam je pouze syntaktickým cukrem pro takto vytvořenou datovou strukturu:

(1 . (2 . (3 . NIL)))
(1 2 3)

Dtto platí při použití prázdného seznamu jako ukončovacího prvku (prázdný seznam je při zpracování a vyhodnocování totožný s NIL):

(1 . (2 . (3 . ())))
(1 2 3)

V PicoLispu se seznam začínající číslem nijak nevyhodnocuje (což je praktické):

(1 2 3 4)
(1 2 3 4)

Seznam je možné uložit do proměnné, přesněji řečeno ho navázat na symbol a získat jeho první prvek funkcí car, ostatní prvky seznamu bez prvku prvního funkcí cdr, popř. použít některou z kombinací c[ad]+r

(setq a '(1 2 3))
(1 2 3)
 
(car a)
1
 
(cdr a)
(2 3)
 
(cadr a)
2
 
(cddr a)
(3)

Poznámka: povšimněte si rozdílu mezi (1 2 3 4) a (car a). V prvním případě se seznam nijak speciálně nevyhodnocuje, zatímco v případě druhém je první prvek chápán jako jméno funkce, která se má zavolat. Jinými slovy – v LISPu není velký rozdíl mezi daty a programovým kódem. Této důležité vlastnosti se říká homoikonicita.

7. Další datové struktury postavené nad seznamy: zásobníky, fronty a cyklické seznamy

Seznamy mohou být použity i pro implementaci dalších užitečných datových struktur. Příkladem může být zásobník (stack) se základními operacemi push a pop:

(push 'zasobnik 1)
1
 
(push 'zasobnik 2)
2
 
(push 'zasobnik 3)
3
 
zasobnik
(3 2 1)
 
(pop 'zasobnik)
3
 
(pop 'zasobnik)
2
 
(pop 'zasobnik)
1
 
(pop 'zasobnik)
NIL

Třetí často používanou datovou strukturou je fronta (queue)

(queue 'fronta 1)
1
 
(queue 'fronta 2)
2
 
(queue 'fronta 3)
3
 
fronta
(1 2 3)
 
(pop 'fronta)
1
 
fronta
(2 3)
 
(pop 'fronta)
2
 
(pop 'fronta)
3
 
(pop 'fronta)
NIL

Vytvoření fronty typu FIFO s využitím cyklického seznamu (poslední prvek seznamu ukazuje na prvek první):

(fifo 'X 1)
1
 
(fifo 'X 2 3)
3
 
X
(3 1 2 .)
; tečka před závorkou označuje cyklický seznam!
 
(fifo 'X)
1
 
(fifo 'X)
2
 
X
(3 .)
 
(fifo 'X)
3
 
(fifo 'X)
NIL

8. Funkce – základní stavební prvek programů

Podobně jako u každého dialektu programovacího jazyka LISP, i v případě PicoLispu se program skládá především z funkcí. Ty mohou být anonymní (nepojmenované) či naopak pojmenované. Nejprve se zabývejme pojmenovanými funkcemi, protože ty se chovají prakticky stejně, jako běžné funkce v jiných programovacích jazycích. Pojmenované funkce se definují pomocí de (zkratka od „define“), za nímž následuje jméno funkce. Každá funkce může mít libovolný počet parametrů, jejichž jména se uvádí v seznamu za pojmenováním funkce. Poslední částí formy de je tělo funkce, přičemž po zavolání funkce se vyhodnocená forma vrátí jako její výsledek (nikde se tedy nezapisuje slovo „return“ ani nic podobného):

(de add (x y) (+ x y))

Přehlednější je však zápis definice funkce na více řádků. První řádek obsahuje jméno, druhý pojmenované parametry, další řádky pak tělo funkce:

(de mul
    (x y)
    (* x y))

PicoLisp nedělá velké rozdíly mezi kulatými a hranatými závorkami, proto se můžeme přiblížit formátu známému z programovacího jazyka Clojure:

(de mul
    [x y]
    (* x y))

Zavolání funkce je jednoduché – používá se stále ten samý formát seznamu, na jehož prvním místě je jméno funkce a za ním následují parametry:

(mul 6 7)
42

Funkce bez parametrů, která vrací NIL:

(de nic () NIL)
 
(nic)
NIL

9. Funkce vyššího řádu

PicoLisp sice není, na rozdíl od Haskellu a částečně i Clojure, čistě funkcionální jazyk, nicméně i zde hrají při vývoji aplikací velkou roli funkce vyššího řádu, tj. funkce, které jako své parametry akceptují jiné funkce popř. dokonce vrací (nové) funkce jako svoji návratovou hodnotu. Mezi dvě základní funkce vyššího řádu, které nalezneme prakticky ve všech dialektech programovacího jazyka Lisp, patří funkce nazvané mapcar a taktéž apply. Funkce mapcar jako svůj první parametr akceptuje jinou funkci (s jedním parametrem) a druhým parametrem musí být seznam. mapcar postupně aplikuje předanou funkci na jednotlivé prvky seznamu a vytváří tak seznam nový (modifikovaný). Podívejme se na jednoduchý příklad – aplikace funkce pro zvýšení hodnoty o jedničku na seznam:

(de inc
    (x)
    (+ x 1))
 
(mapcar inc (1 2 3))
(2 3 4)

Funkce apply se chová poněkud odlišně – aplikuje totiž nějakou funkci (svůj první parametr) na předaný seznam. Typický „školní“ příklad s binární funkcí + (tj. funkcí se dvěma parametry) může vypadat následovně:

(apply + (1 2 3 4))
10

Pozor však – apply není reduce a ve výše uvedeném příkladu fungovala proto, že funkce + je variadická. Následující kód již správně nebude:

(de add
    (x y)
    (+ x y))
 
(apply add (1 2 3 4))
3

Můžeme zkusit i něco složitějšího. Funkcí range vygenerujeme seznam hodnot a posléze tyto hodnoty vynásobíme:

(range 1 10)
(1 2 3 4 5 6 7 8 9 10)
 
(apply * (range 1 6))
720

Ono vynásobení hodnot od 1 do n není vlastně nic jiného, než výpočet faktoriálu, takže:

(de factorial
    (n)
    (apply * (range 1 n)))

10. Programové smyčky

Vzhledem k tomu, že se PicoLisp nesnaží být (na rozdíl od Scheme) čistě funkcionálním jazykem, nalezneme v něm i programové smyčky, které se ovšem stále zapisují formou funkcí či speciálních forem. Nebudeme si ukazovat všechny typy programových smyček, ale jen naprosté základy:

Počítaná smyčka typu for:

(for n 10 (println n))
 
1
2
3
4
5
6
7
8
9
10

Počítaná smyčka typu while:

(while (num? (read)) (println 'cislo))
 
1
cislo
454
cislo
4254
cislo
konec

Počítaná smyčka typu repeat-until:

(until (=T (setq N (read)))
    (println 'vysledek (* N N)))
1
vysledek 1
4
vysledek 16
9
vysledek 81
10
vysledek 100

11. Anonymní funkce

Kromě pojmenovaných funkcí, které jsme si již představili v předchozích kapitolách, je možné v PicoLispu použít i funkce anonymní, tj. funkce, které nejsou navázány na žádné jméno. Zajímavé je, že zde nenalezneme žádnou obdobu speciální formy lambda ani nic podobného, ale lze použít formu quote, která se v PicoLispu chová poněkud odlišně, než v jiných dialektech LISPu. Podívejme se na typický příklad – budeme chtít ze vstupního seznamu vytvořit výstupní seznam s hodnotami o jedničku zvýšenými. Pro něco tak jednoduchého asi nemá smysl si vytvářet novou pojmenovanou funkci, ale použijeme přímo funkci anonymní:

(mapcar (quote (x) (+ x 1) ) (1 2 3 4))
 
(2 3 4 5)

Zajímá vás řada n²?:

(mapcar (quote (x) (* x x)) (range 1 10))
(1 4 9 16 25 36 49 64 81 100)

Nebo chcete získat seznam faktoriálů n od 1 do 10?:

(mapcar (quote (n) (apply * (range 1 n) )) (range 1 10))
 
(1 2 6 24 120 720 5040 40320 362880 3628800)

12. Reprezentace numerických hodnot

PicoLisp se od mnoha dalších dnes používaných programovacích jazyků odlišuje i tím, že pro reprezentaci numerických hodnot nepoužívá ani základní celočíselné datové typy (int, long int atd.) a dokonce ani dnes běžné formáty hodnot s plovoucí řádovou čárkou (float, double), které jsou definovány v normě IEEE 754. Namísto toho jsou podporována celá čísla se znaménkem, která mají neomezený rozsah. Interně jsou totiž číselné hodnoty reprezentovány speciálním typem seznamu, který vypadá následovně:

   Number
   |
   V
+-----+-----+
| DIG |  |  |
+-----+--+--+
         |
         V
      +-----+-----+
      | DIG |  |  |
      +-----+--+--+
               |
               V
            +-----+-----+
            | DIG |  /  |
            +-----+-----+

Tato datová struktura je v 64bitové variantě PicoLispu mírně odlišná, než je tomu v základní 32bitové verzi, nicméně původní myšlenka zůstává zachována: pro relativně malé hodnoty (jak kladné, tak i záporné) postačuje číslo reprezentovat jedinou buňkou (cell), zatímco u větších hodnot je nutné použít dvě či dokonce větší množství buněk propojených formou lineárního seznamu. Předností je (podle očekávání) neomezený rozsah a taktéž nezávislost na existenci matematického koprocesoru (či příslušné knihovny), nevýhodou pak obecně poněkud pomalejší výpočty, zejména u těch mikroprocesorových architektur, které mají plnohodnotné matematické koprocesory. Naopak u malých mikrořadičů může být výhodnější NEpoužít matematickou knihovnu pro reálná čísla a namísto toho se spokojit s řešením nabízeným PicoLispem. Díky možnosti specifikovat pevné umístění řádové tečky (čárky) se navíc (prakticky) neomezený rozsah spojuje s neomezenou přesností, což je téma, které si ukážeme příště.

Podívejme se nyní na to, jak výpočty s „neomezenými“ celočíselnými hodnotami probíhají v praxi. Opět si zvolme populární výpočet faktoriálu:

(de factorial
    [n]
    (apply * (range 1 n)))

Vlastní výpočet faktoriálu je omezen jen výkonem mikroprocesoru (ten je dostatečný i na původním modelu Raspberry Pi) a dostupnou operační pamětí. Začneme zlehka:

(for n 10 (println n (factorial n)))
 
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362880
10 3628800

Ovšem můžeme se například podívat na 1000!:

(factorial 1000)
 
402387260077093773543702433923003985719374864210714632543799
910429938512398629020592044208486969404800479988610197196058
631666872994808558901323829669944590997424504087073759918823
627727188732519779505950995276120874975462497043601418278094
646496291056393887437886487337119181045825783647849977012476
632889835955735432513185323958463075557409114262417474349347
553428646576611667797396668820291207379143853719588249808126
867838374559731746136085379534524221586593201928090878297308
431392844403281231558611036976801357304216168747609675871348
312025478589320767169132448426236131412508780208000261683151
027341827977704784635868170164365024153691398281264810213092
761244896359928705114964975419909342221566832572080821333186
116811553615836546984046708975602900950537616475847728421889
679646244945160765353408198901385442487984959953319101723355
556602139450399736280750137837615307127761926849034352625200
015888535147331611702103968175921510907788019393178114194545
257223865541461062892187960223838971476088506276862967146674
697562911234082439208160153780889893964518263243671616762179
168909779911903754031274622289988005195444414282012187361745
992642956581746628302955570299024324153181617210465832036786
906117260158783520751516284225540265170483304226143974286933
061690897968482590125458327168226458066526769958652682272807
075781391858178889652208164348344825993266043367660176999612
831860788386150279465955131156552036093988180612138558600301
435694527224206344631797460594682573103790084024432438465657
245014402821885252470935190620929023136493273497565513958720
559654228749774011413346962715422845862377387538230483865688
976461927383814900140767310446640259899490222221765904339901
886018566526485061799702356193897017860040811889729918311021
171229845901641921068884387121855646124960798722908519296819
372388642614839657382291123125024186649353143970137428531926
649875337218940694281434118520158014123344828015051399694290
153483077644569099073152433278288269864602789864321139083506
217095002597389863554277196742822248757586765752344220207573
630569498825087968928162753848863396909959826280956121450994
871701244516461260379029309120889086942028510640182154399457
156805941872748998094254742173582401063677404595741785160829
230135358081840096996372524230560855903700624271243416909004
153690105933983835777939410970027753472000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000

Tento výsledek by měl (alespoň doufejme) odpovídat výsledku z adresy http://justinwhite.com/big-calc/1000.html.

Další možnosti práce s numerickými hodnotami, především změnu pozice řádové tečky (čárky), si popíšeme ve druhé části tohoto článku.

13. Obsah druhé části článku

Ve druhé a současně i poslední části tohoto článku popis možností nabízených těm vývojářům, kteří se rozhodnou využít programovací jazyk PicoLisp, dokončíme. Zabývat se budeme jak funkcemi, které jsou součástí základních knihoven tohoto jazyka (včetně deklarací tříd či zpracování výjimek), tak i způsobem kooperace programů napsaných v PicoLispu s nativními knihovnami. Nezapomeneme ani na další zajímavou vlastnost PicoLispu – možnost volání metod objektů vytvořených v samostatně běžícím virtuálním stroji jazyka Java (JVM). Jak kooperace s nativními knihovnami, tak i volání metod v JVM jsou z hlediska praktické použitelnosti PicoLispu velmi důležité, protože nelze předpokládat (ani by to vlastně nebylo praktické), že pro tento dosti minoritní interpret s relativně malou komunitou vznikne větší množství knihoven a/nebo dokonce celých frameworků.

14. Příloha: stručná historie vývoje LISPu

Historie programovacího jazyka LISP je poměrně dlouhá a komplikovaná, neboť se jedná o jeden z nejstarších programovacích jazyků vůbec. Autorem teoretického návrhu LISPu 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, cloudy, virtualizace, popř. WEB 2.0, v padesátých a šedesátých letech minulého století se jednalo o umělou inteligenci a taktéž o expertní systémy). McCarthy navrhl, aby se fakta o okolním světě (která může AI při své činnosti použít) reprezentovala 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é.

Následně McCarthy ve svých teoretických pracech (vznikajících v průběhu let 1957 a 1958) ukázal, že je možné s využitím 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, obsahoval možnost vytváření rekurzivních funkcí (což byl významný rozdíl například oproti tehdejší verzi FORTRANU), funkce bylo možné použít jako argumenty jiných funkcí, byly zde popsány i podmíněné výrazy (jedna z variant speciální formy), funkce pro manipulaci se seznamy a v neposlední řadě také funkce eval.

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 – CLOS v případě Common Lispu), vznikl v minulosti i nový dialekt tohoto jazyka nazvaný Scheme (původně Schemer), jehož autory jsou dnes již zmíněný 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 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 (z tohoto období pochází také známá TCL War, která ukázala některé konceptuální rozdíly mezi aplikacemi založenými na LISPu/Scheme a modelem UNIXu založeného na používání textových proudů).

Jednou z moderních reinkarnací LISPu je jazyk Clojure, jemuž se na stránkách Roota věnujeme poměrně intenzivně.

15. 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 reference“
   Autodesk Ltd., October 1987
5. „AutoLISP Release 10, Programmer's reference“
   Autodesk Ltd., September 1988
6. 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
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

16. Odkazy na Internetu

1. PicoLisp
   http://picolisp.com/wiki/?home
2. A PicoLisp Tutorial
   http://software-lab.de/doc/tut.html
3. Pico Lisp Documentation
   http://picolisp.com/wiki/?Do­cumentation
4. The PicoLisp Machine
   http://software-lab.de/doc/ref.html#vm
5. Pico Lisp: A Case for Minimalist Interpreters?
   http://lambda-the-ultimate.org/node/2124
6. PicoLisp na Wikipedii
   https://en.wikipedia.org/wi­ki/PicoLisp
7. Programovací jazyk LISP a LISP machines
   http://www.root.cz/clanky/programovaci-jazyk-lisp-a-lisp-machines/
8. Programovací jazyk LISP (druhá část)
   http://www.root.cz/clanky/programovaci-jazyk-lisp-druha-cast/
9. Steel Bank Common Lisp
   http://www.sbcl.org/
10. CLISP (implementace Common Lispu)
    http://clisp.org/
11. PLEAC-PicoLisp
    http://pleac.sourceforge.net/ple­ac_picolisp/index.html#AEN4
12. Rosetta Code – Category:Lisp
    http://rosettacode.org/wi­ki/Category:Lisp
13. Emacs timeline
    http://www.jwz.org/doc/emacs-timeline.html
14. EINE (Emacs Wiki)
    http://www.emacswiki.org/emacs/EINE
15. EINE (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?EINE
16. ZWEI (Emacs Wiki)
    http://www.emacswiki.org/emacs/ZWEI
17. ZWEI (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?ZWEI
18. Zmacs (Wikipedia)
    https://en.wikipedia.org/wiki/Zmacs
19. Zmacs (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?Zmacs
20. TecoEmacs (Emacs Wiki)
    http://www.emacswiki.org/e­macs/TecoEmacs
21. Micro Emacs
    http://www.emacswiki.org/e­macs/MicroEmacs
22. Micro Emacs (Wikipedia)
    https://en.wikipedia.org/wi­ki/MicroEMACS
23. EmacsHistory
    http://www.emacswiki.org/e­macs/EmacsHistory
24. Seznam editorů s ovládáním podobným Emacsu či kompatibilních s příkazy Emacsu
    http://www.finseth.com/emacs.html