Hlavní navigace

TinyScheme aneb další interpret jazyka Scheme vestavitelný do dalších aplikací

Pavel Tišnovský

Na článek o GNU Guile dnes navážeme, protože si popíšeme další implementaci Scheme, která se jmenuje příznačně TinyScheme. Opět se jedná o interpret, který je možné v případě potřeby vestavět do dalších aplikací.

Doba čtení: 39 minut

Sdílet

11. Překlad prvního příkladu

12. Načtení skriptu z externího souboru

13. Úplný zdrojový kód druhého příkladu

14. Zpracování numerických hodnot předaných do nativní funkce ze Scheme

15. Úplný zdrojový kód třetího příkladu

16. Zavolání funkce s větším počtem parametrů

17. Jaký interpret použít pro implementaci DSL?

18. Repositář s demonstračními příklady

19. Literatura

20. Odkazy na Internetu

1. TinyScheme aneb další interpret jazyka Scheme vestavitelný do dalších aplikací

Ve druhé části miniseriálu o různých interpretrech a překladačích programovacích jazyků LISP a Scheme jsme si ukázali některé možnosti nabízené projektem GNU Guile. Připomeňme si ve stručnosti, že se jedná o interpret kombinovaný s překladačem programovacího jazyka Scheme, který lze využít jak samostatně (příkazem guile se spustí interaktivní smyčka REPL) nebo je možné GNU Guile vložit do dalších aplikací a použít tak Scheme jako skriptovací jazyk rozšiřující možnosti vybrané aplikace a umožňující například tvorbu pluginů (ze známých aplikací je tato idea asi nejvíce dotažena ve slavném Emacsu, který se rozšiřuje skripty psanými v Emacs Lispu a i velká část samotného Emacsu je psána v tomtéž programovacím jazyce).

Podobným způsobem je koncipován i projekt TinyScheme, s nímž se seznámíme dnes. Název TinyScheme je poměrně přiléhavý, protože samotný interpret (pochopitelně i s automatickým správcem paměti) je možné přeložit do spustitelného souboru, který má po odstranění ladicích symbolů velikost pouhých 66 kilobajtů, což je méně než u programovacího jazyka Lua, jehož interpret má na stejné architektuře velikost přes 150 kilobajtů (ovšem toto porovnání není úplně férové, protože by bylo nutné porovnat i všechny funkce ze základních knihoven). Navíc je možné TinyScheme vložit přímo do vyvíjené aplikace, přičemž je umožněno podle požadavků vývojářů využít statickou knihovnu (ta se slinkuje přímo do vyvíjené aplikace) či knihovnu dynamickou (bude se načítat až po spuštění a inicializaci aplikace). Při překladu TinyScheme lze navíc zvolit, které vlastnosti má výsledný interpret mít; například lze zcela odstranit práci s hodnotami typu double a zjednodušit tak nasazení na architekturách bez matematického koprocesoru.

2. Základní vlastnosti TinyScheme

O projektu TinyScheme jsme si v úvodní kapitole řekli, že se jedná o jednu z mnoha implementací programovacího jazyka Scheme. Ovšem co je tím myšleno v kontextu LISPovského jazyka? Již víme, že LISP (a tím pádem i jeho derivát Scheme) je dobré chápat spíše jako koncept, než jako konkrétní specifikaci, i když například existuje ANSI norma LISPu (Common Lisp). V případě některé implementace jazyka Scheme se tedy musíme spíše dívat na to, které konkrétní vlastnosti specifikované (mnohdy ovšem poměrně vágně) v RnRS jsou implementovány a které naopak nikoli; samozřejmě s tím důležitým dodatkem, že mnohé vlastnosti lze relativně snadno do již existujícího interpretru dodat dalšími funkcemi a makry (což je konkrétně příklad speciální formy do, která je v TinyScheme implementována jako makro v souboru init.scm).

Mezi základní datové typy podporované interpretrem TinyScheme patří především:

# Typ Poznámka
1 Number celá čísla jsou podporována vždy, podpora reálných čísel při USE_MATH=1
2 Symbol podpora pro převod na řetězec i naopak
3 Pair (tečka.dvojice)
4 String může obsahovat i konec řádků (ukončení řetězce na dalším řádku)
5 Character včetně řídicích znaků #\newline, #\tab atd.
6 Port podle R5RS, bude podrobněji vysvětleno příště
7 Eof podle R5RS, bude podrobněji vysvětleno příště
8 Environment
9 List vytvářen běžným způsobem – rekurzivní sekvence tečka-dvojic
10 Vector včetně všech základních podpůrných funkcí
Poznámka: ve skutečnosti nejsme omezeni pouze na řetězce používající kódování ASCII. Pokud je korektně nastaven terminál, lze využít i plnohodnotné UTF-8, protože interně TinyScheme s řetězci zachází jako s céčkovými stringy a základní funkce tedy dokážou pracovat i s UTF-8.

Při zápisu jednotlivých znaků je možné použít buď přímo ASCII hodnotu znaku nebo symbol, který reprezentuje ty znaky z ASCII kódu, které nemají přímo tisknutelnou podobu. Jedná se o prvních třicet jedna znaků a navíc taktéž o znak DEL(ETE) s kódem 127:

ASCII Symbol ASCII Symbol
0 #\nul 17 #\dc1
1 #\soh 18 #\dc2
2 #\stx 19 #\dc3
3 #\etx 20 #\dc4
4 #\eot 21 #\nak
5 #\enq 22 #\syn
6 #\ack 23 #\etv
7 #\bel 24 #\can
8 #\bs 25 #\em
9 #\ht 26 #\sub
10 #\lf 27 #\esc
11 #\vt 28 #\fs
12 #\ff 29 #\gs
13 #\cr 30 #\rs
14 #\so 31 #\us
15 #\si  
16 #\dle 127 #\del

TinyScheme se ovšem v některých ohledech odlišuje například od GNU Guile nebo od MIT Scheme. Příkladem chybějící vlastnosti, na kterou lze narazit i u relativně malých skriptů, je neexistující podpora pro komplexní čísla a především pak pro zlomky. Ukažme si nyní příklad rozdílného chování mezi GNU Guile, kterým jsme se zabývali minule, a TinyScheme při práci se zlomky.

Chování GNU Guile:

scheme@(guile-user)> 1/3
$1 = 1/3
scheme@(guile-user)> (* 1/2 1/3)
$2 = 1/6

Chování TinyScheme:

ts> 1/3
Error: eval: unbound variable: 1/3
 
ts> (* 1/2 1/3)
Error: eval: unbound variable: 1/2

Při výpočtech je taktéž nutné si dát pozor na to, že rozsah celých čísel je omezen nativním typem long, na rozdíl od klasického Scheme, kde toto omezení neexistuje. Podívejme se na typický příklad – rekurzivní výpočet faktoriálu:

(define (factorial n)
  (if (= n 0)     ; podmínka pro ukončení rekurzivního zanořování
    1             ; faktoriál nuly je definitoricky roven jedné
    (* n (factorial (- n 1)))
  )
)
 
 
(define n 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))

Po spuštění zjistíme, že dochází k přetečení výsledků, což je samozřejmě nekorektní:

1
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
-4249290049419214848
-1250660718674968576
8128291617894825984
-7835185981329244160
7034535277573963776
-1569523520172457984
-5483646897237262336
-5968160532966932480
-7055958792655077376

V tomto případě nám pochopitelně nepomůže ani převod programu na tail-call rekurzi:

(define (factorial n)
  (let fact-iter (                       ; pomocná vnitřní funkce
                (n n)                    ; počitadlo iterací
                (result 1))              ; průběžný výsledek
      (if (= n 0)                        ; po dosažení koncového stavu
        result                           ; se vrátí průběžný výsledek
        (fact-iter (- n 1) (* n result)) ; koncové volání
      )))
 
 
(define n 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))

S výsledky:

1
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
-4249290049419214848
-1250660718674968576
8128291617894825984
-7835185981329244160
7034535277573963776
-1569523520172457984
-5483646897237262336
-5968160532966932480
-7055958792655077376

Naproti tomu GNU Guile s tímto příkladem žádné zásadní problémy nemá:

1
1
2
6
24
120
720
5040
40320
362880
3628800
39916800
479001600
6227020800
87178291200
1307674368000
20922789888000
355687428096000
6402373705728000
121645100408832000
2432902008176640000
51090942171709440000
1124000727777607680000
25852016738884976640000
620448401733239439360000
15511210043330985984000000
403291461126605635584000000
10888869450418352160768000000
304888344611713860501504000000
8841761993739701954543616000000

Dále chybí podpora pro hygienická makra, což je docela škoda, protože se – alespoň podle mého názoru – jedná o jednu z těch velmi dobrých vlastností jazyka Scheme, kterou v naprosté většině mainstreamových jazyků nenalezneme.

Poslední problém, se kterým se setkáme (ovšem na který narazíme u prakticky všech interpretrů Scheme) je omezená práce paměti pro zásobník. V následujícím příkladu je použita Ackermannova funkce, která je rekurzivní, ovšem současně není primitivně rekurzivní. Navíc tato funkce i pro malé vstupní hodnoty vyžaduje mnoho rekurzivních zanoření:

(define (A m n)
  (cond
    ((= m 0) (+ n 1))
    ((= n 0) (A (- m 1) 1))
    (else (A (- m 1) (A m (- n 1))))))

Tuto funkci si můžeme otestovat pro malé hodnoty m a n:

(define m 0)
(define n 0)
 
(do ()
  ((>= m 4))
  (set! n 0)
  (do ()
    ((>= n 5))
    (display (A m n))
    (display "\t")
    (set! n (+ n 1)))
  (newline)
  (set! m (+ m 1)))

S výsledky:

1       2       3       4       5
2       3       4       5       6
3       5       7       9       11
5       13      29      61      125

Pro větší hodnoty, konkrétně pro m=5 a n=0 se již ovšem Ackermannovu funkci nepodaří vyhodnotit:

(display (A 5 0))

V tomto případě interpret pouze lakonicky oznámí:

No memory!

3. Získání zdrojových kódů a překlad TinyScheme

TinyScheme pravděpodobně nebude k dispozici přímo ve formě balíčku pro vaši Linuxovou distribuci, což však nemusí vadit, protože samotná kompilace interpretru i knihoven TinyScheme je velmi snadná i rychlá a vyžaduje pouze překladač jazyka C s jeho základními knihovnami a standardními nástroji typu ld, ar atd. (v případě GNU Guile je překlad nepatrně složitější, protože je vyžadováno větší množství knihoven, které nebývají standardně nainstalovány).

Nejprve je samozřejmě nutné získat repositář se zdrojovými kódy TinyScheme. Starší verze existuje ve formě forku přímo na GitHubu, konkrétně na adrese https://github.com/yawnt/tinyscheme, pokud ovšem budete vyžadovat jinou verzi (ideálně poslední stabilní verzi 1.41), je nutné zdrojové kódy získat ze SourceForge, konkrétně z adresy https://sourceforge.net/pro­jects/tinyscheme/files/ti­nyscheme/. Poslední stabilní verze 1.41 je dostupná ve formě tarballu na adrese https://sourceforge.net/pro­jects/tinyscheme/files/ti­nyscheme/tinyscheme-1.41/tinyscheme-1.41.tar.gz/download (stáhnout lze pochopitelně i ZIP archiv se stejným obsahem).

Samotná instalace se skládá jen ze dvou kroků.

Nejprve získaný tarball rozbalíme:

$ tar cvfz tinyscheme-1.41.tar.gz

Překlad a slinkování se provede klasicky nástrojem make. V případě překladu na Linuxu není nutné soubor makefile nijak upravovat, ovšem například při překladu pro operační systémy Microsoft Windows, Solaris atd. se podívejte do makefile (v tomto projektu je skutečně použit s malým písmenem na začátku názvu), které části se musí zakomentovat a které naopak odkomentovat:

$ cd tinyscheme-1.41
 
$ make
 
gcc -fpic -pedantic -I. -c -g -Wno-char-subscripts -O -DSUN_DL=1 -DUSE_DL=1 -DUSE_MATH=1 -DUSE_ASCII_NAMES=0  scheme.c
gcc -fpic -pedantic -I. -c -g -Wno-char-subscripts -O -DSUN_DL=1 -DUSE_DL=1 -DUSE_MATH=1 -DUSE_ASCII_NAMES=0  dynload.c
dynload.c:24:0: warning: "SUN_DL" redefined [enabled by default]
 #define SUN_DL
 ^
<command-line>:0:0: note: this is the location of the previous definition
dynload.c: In function ‘dl_proc’:
dynload.c:77:14: warning: ISO C forbids conversion of object pointer to function pointer type [-Wpedantic]
   FARPROC fp=(FARPROC)dlsym(mo,proc);
              ^
gcc -shared -o libtinyscheme.so scheme.o dynload.o -ldl -lm
ar crs libtinyscheme.a scheme.o dynload.o
gcc -fpic -pedantic -o scheme -g -Wno-char-subscripts -O scheme.o dynload.o -ldl -lm
Poznámka: výše zobrazená varování hlášená překladačem jsou tak trošku ostuda (navíc se jedná o jednoduše opravitelné problémy), ovšem snad ji autorovi odpustíme :-)

Po zadání předchozího příkladu by měly vzniknout zejména tyto tři soubory:

# Soubor Velikost (Linux, x86–64) Velikost (Linux, i686) Stručný popis
1 scheme 208779 142735 interpret jazyka Scheme
2 libtinyscheme.so 225070 150038 knihovna pro dynamické linkování
3 libtinyscheme.a 332922 175540 knihovna pro statické linkování
Poznámka: zajímavé je, jak výrazně rozdílné jsou velikosti výsledných souborů určených pro 32bitovou a pro 64bitovou architekturu.

4. Překlad bez podpory datového typu double

Ve svém výchozím nastavení se TinyScheme překládá s volbou USE_MATH=1. Při tomto nastavení se do vytvářeného interpretru vloží podpora pro následující numerické funkce volatelné z libovolného skriptu naprogramovaného ve Scheme:

# Funkce
1 exp
2 log
3 sin
4 cos
5 tan
6 asin
7 acos
8 atan
9 floor
10 ceiling
11 trunc
12 round
13 sqrt
14 expt
Poznámka: tyto funkce interně pracují s hodnotami typu double, což na většině dnes podporovaných mikroprocesorových architektur znamená numerické hodnoty s dvojitou přesností podle normy IEEE 754.

Pokud se ovšem volba USE_MATH=1 nepoužije, znamená to, že ani jedna z výše uvedených funkcí nebude k dispozici. Navíc se díky tomu, že se nebude linkovat knihovna math, nepatrně zmenší velikost výsledných binárních souborů s interpretrem i knihovnou s implementací TinyScheme. Rozdíly ve velikosti pro architekturu x86–64 můžeme vidět v následující tabulce:

# Soubor Velikost při USE_MATH=1 Velikost při USE_MATH=0
1 scheme 208779 199569
2 libtinyscheme.so 225070 215860
3 libtinyscheme.a 332922 320666
Poznámka: překlad pro počítače, které mají mikroprocesor s 32bitovou architekturou i686, byl proveden na netbooku Asus EEE 1000 s mikroprocesorem Atom.

Velikost vytvořených binárních souborů se sice zmenšila, ovšem dosti nepatrně (alespoň v kontextu velikostí dnešních aplikací). Jaký má tedy význam použití volby USE_MATH=0 v praxi? Použijeme ji například ve chvíli, kdy budeme potřebovat použít interpret programovacího jazyka Scheme na těch architekturách, které neobsahují matematický koprocesor. Kromě klasických osmibitových a šestnáctibitových mikrořadičů (TinyScheme by mělo jíž provozovat například na MSP430) se jedná o 32bitové mikrořadiče ARM. Zde bude úspora kódu mnohem větší, protože pokud se vůbec nepoužije datový typ double, nebude se ani linkovat knihovna se softwarovou implementací numerických operací.

Další matematické funkce jsou k dispozici vždy:

# Funkce
1 quotient
2 remainder
3 modulo
4 gcd
5 lcm

Následující predikáty jsou dostupné jen z knihovny init.scm:

# Funkce
1 exact?
2 inexact?
3 odd?
4 even?
5 zero?
6 positive?
7 negative?

5. Soubor init.scm

Kromě třech výše popsaných souborů vzniklých překladem (interpret, statická knihovna, dynamická knihovna) je pro uživatele důležitý i soubor nazvaný init.scm. Tento soubor obsahuje mnoho užitečných funkcí a maker, které zjednodušují tvorbu nových programů a navíc do jisté míry zaručují i kompatibilitu s R5RS a částečně i s R6RS. Tento soubor je automaticky načítán interpretrem představovaným spustitelným souborem scheme, ovšem v případě, že budeme provádět embedding interpretru TinyScheme do vlastních aplikací, bude nutné načtení init.scm provést ručně (to si ukážeme v navazujících kapitolách).

Spuštění interpretru ve chvíli, kdy init.scm existuje, se obejde bez chybových hlášení a všechny funkce a makra jsou automaticky načtena:

$ ./scheme
 
TinyScheme 1.41
ts> cadr
#<CLOSURE>
ts>
ts> (zero? 0)
#t
ts> (negative? 0)
#f

Ve chvíli, kdy soubor init.scm není možné najít či načíst, se chování změní:

$ ./scheme
 
Could not open file init.scm
TinyScheme 1.41
ts> cadr
Error: eval: unbound variable: cadr
 
ts>
ts> (zero? 0)
Error: eval: unbound variable: zero?
 
ts> (negative? 0)
Error: eval: unbound variable: negative?
 

Z rozšiřujících funkcí, které nalezneme v souboru init.scm se jedná například o různé kombinace standardních funkcí car a cdr:

ts> (cadr '(1 2 3 4))
2
ts> (caddr '(1 2 3 4))
3
ts> (caar '('(1 2) '(3 4)))
quote
ts> (caar '((1 2) (3 4)))
1
ts> (cadr '((1 2) (3 4)))
(3 4)

Dále pak například makro s implementací programové smyčky do, které se používá velmi snadno (viz též sedmou kapitolu):

(define i 0)
 
(do ()
  ((>= i 10))
  (display i)
  (newline)
  (set! i (+ i 1)))
 
0
1
2
3
4
5
6
7
8
9

O některých dalších funkcích, například numericky orientovaných predikátech, jsme se již zmínili v předchozí kapitole.

6. Rekurze

V úvodní části našeho povídání o programovacích jazycích LISPScheme jsme si mj. řekli, že iteraci, tj. opakování vybrané části kódu (většinou s různými parametry), lze vyjádřit buď pomocí rekurze nebo s využitím explicitně či implicitně zapsaných programových smyček. Použití rekurze je ve světě LISPu doporučovaná možnost, protože se nejvíce blíží funkcionálnímu stylu programování a v mnoha případech taktéž vychází rekurzivní zápis přímo z algoritmu, který se v jazyce LISP nebo Scheme implementuje. Následuje příklad několika jednoduchých funkcí zapsaných rekurzivně (jedná se o typické „školní“ příklady). Povšimněte si především toho, že se v těchto rekurzivních funkcích nevyskytují žádné pomocné lokální proměnné, jejichž použití bychom se nemohli vyhnout v případě zápisu obdobných výpočtů v nerekurzivní podobě.

Výpočet faktoriálu pro kladné parametry:

; rekurzivní zápis výpočtu faktoriálu
(define (factorial n)
    (if (<= n 1)
        1
        (* n (factorial (- n 1)))))

Rekurzivně zapsaný výpočet n-tého prvku Fibonacciho posloupnosti:

; rekurzivní výpočet Fibonacciho posloupnosti
(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1)) (fib (- n 2))))))

Výpočet Ackermannovy funkce pro zadané vstupní parametru m a n:

; rekurzivní výpočet Ackermannovy funkce
(define (A x y)
    (cond ((= y 0) 0)
          ((= x 0) (* 2 y))
          ((= y 1) 2)
          (else (A (- x 1) (A x (- y 1))))))

Výpočet největšího společného dělitele:

(define (gcd a b)
    (if (null? a)
        0
        (if (= b 0)
            a
            (gcd b (remainder a b)))))

Výpočet nejmenšího společného násobku:

(define (lcm a b)
    (if (null? a)
         1
         (if (or (= a 0) (= b 0))
             0
             (abs (* (quotient a (gcd a b)) b)))))

7. Programová smyčka typu do

Ovšem v některých případech může být vhodnější nahradit rekurzivní zápis algoritmu zápisem, v němž jsou použity programové smyčky. Pro tyto účely obsahuje jazyk Scheme universální smyčku představovanou speciální formou do. Tuto programovou smyčku lze použít například pro tvorbu cyklu, v němž se postupně mění hodnota řídicí proměnné (či řídicích proměnných), cyklu procházejícího přes prvky seznamu či cyklu, v němž se postupně načítají a zpracovávají data uložená v externím souboru. Při zápisu formy do je možné specifikovat seznam lokálních proměnných platných v těle smyčky (tyto proměnné mohou být použity například jako počitadla), výraz, pomocí kterého se hodnota těchto proměnných změní na konci těla smyčky, podmínka pro ukončení smyčky a samozřejmě též tělo smyčky, tj. příkazy prováděné v každé iteraci. Následuje jednoduchý příklad použití speciální formy do, pomocí něhož je vytvořena klasická počítaná smyčka:

(do ((i 1 (+ i 1)))  ; počáteční hodnota počitadla a iterační výraz provedený na konci smyčky
    ((= i 10))       ; podmínka vyhodnocovaná pro ukončení smyčky
        (display i)  ; tělo smyčky
        (newline)
)
 
1
2
3
4
5
6
7
8
9

Při zápisu speciální formy do lze vytvořit i větší množství lokálních proměnných platných v rámci těla smyčky, viz následující příklad s trojicí proměnných, z nichž každá se na konci smyčky (před začátkem další iterace) modifikuje na základě vyhodnocení různých výrazů:

(do (
        (x 1 (* x 2))    ; počáteční hodnota proměnné a iterační výraz provedený na konci smyčky
        (y 1000 (- y 1)) ; dtto
        (z 0 (* x y))    ; dtto
    )
    ((< y x))         ; podmínka vyhodnocovaná pro ukončení smyčky
        (display (list x y z)) ; tělo smyčky
        (newline)
)
 
(1 1000 0)
(2 999 1000)
(4 998 1998)
(8 997 3992)
(16 996 7976)
(32 995 15936)
(64 994 31840)
(128 993 63616)
(256 992 127104)
(512 991 253952)

V dalším příkladu je ukázáno postupné zpracování prvků uložených v seznamu (ovšem tento příklad by ve skutečnosti bylo možné napsat mnohem lépe a jednodušeji):

(do ((x '(1 2 3 4 5 6) (cdr x))) ; počáteční hodnota proměnné a iterační výraz provedený na konci smyčky
    ((null? x))                  ; podmínka vyhodnocovaná pro ukončení smyčky
        (display (car x))        ; vlastní tělo smyčky
        (newline))
 
1
2
3
4
5
6

Následuje poněkud složitější příklad, ve kterém je ukázáno použití vnořených počítaných smyček při výpočtu podílu všech kombinací dvou celých čísel ležících v rozsahu 1 až 10 (připomeňme, že výsledkem podílu dvou celých čísel je ve standardním Scheme hodnota typu rational tj. racionální číslo, ovšem v TinyScheme se jedná o reálné číslo). Na tomto příkladu je patrné, že pro zápis složitějších programových struktur je vhodné používat pomocné funkce, což je ostatně zásada, kterou je vhodné dodržovat i v dalších programovacích jazycích:

(do ((y 1 (+ y 1)))    ; počáteční hodnota počitadla a iterační příkaz
  ((> y 10))           ; podmínka pro ukončení smyčky
  (do ((x 1 (+ x 1)))  ; vnitřní smyčka
    ((> x 10))         ; podmínka pro ukončení vnitřní smyčky
    (display (/ x y))  ; tisk výsledku
    (display "\t")     ; přechod na další tabelační zarážku 
  )
  (newline)            ; přechod na další řádek
)

Většinou se však používá poněkud odlišný zápis bez zavíracích závorek umisťovaných na samostatné řádky:

(do ((y 1 (+ y 1)))    ; počáteční hodnota počitadla a iterační příkaz
  ((> y 10))           ; podmínka pro ukončení smyčky
  (do ((x 1 (+ x 1)))  ; vnitřní smyčka
    ((> x 10))         ; podmínka pro ukončení vnitřní smyčky
    (display (/ x y))  ; tisk výsledku
    (display "\t"))    ; přechod na další tabelační zarážku 
  (newline))           ; přechod na další řádek
Poznámka: sice poněkud předbíháme, ale ukažme si, jak je vlastně speciální forma do definována v TinyScheme. Ve skutečnosti se jedná o makro, které se chová jako speciální forma:
(macro do
  (lambda (do-macro)
    (apply (lambda (do vars endtest . body)
             (let ((do-loop (gensym)))
               `(letrec ((,do-loop
                           (lambda ,(map (lambda (x)
                                           (if (pair? x) (car x) x))
                                      `,vars)
                             (if ,(car endtest)
                               (begin ,@(cdr endtest))
                               (begin
                                 ,@body
                                 (,do-loop
                                   ,@(map (lambda (x)
                                            (cond
                                              ((not (pair? x)) x)
                                              ((< (length x) 3) (car x))
                                              (else (car (cdr (cdr x))))))
                                       `,vars)))))))
                  (,do-loop
                    ,@(map (lambda (x)
                             (if (and (pair? x) (cdr x))
                               (car (cdr x))
                               '()))
                        `,vars)))))
      do-macro)))
Poznámka: nejedná se vlastně o nijak dlouhý kód a přitom sémantiku jazyka dosti výrazným způsobem rozšiřuje. Zde je možná patrná elegance homoikonického jazyka.

8. Rozhraní mezi TinyScheme a nativními aplikacemi

Ve druhé části dnešního článku si ukážeme, jakým způsobem je možné vložit interpret programovacího jazyka Scheme do nativních aplikací vytvořených v jazyku C. Samozřejmě lze použít i jiný kompilovaný jazyk (nejbližší je C++), ovšem rozhraní mezi Scheme (resp. přesněji řečeno TinyScheme) a C je nejjednodušeji použitelné. Pro překlad, slinkování a spuštění dále popsaných příkladů budete potřebovat překladač C (gcc apod.) se základními knihovnami i základními nástroji (ld, ar, nm…). Soubory Makefile jsou zpracovávány utilitou make. Žádné další nástroje ani knihovny již v systému nejsou zapotřebí.

9. Inicializace interpretru Scheme a spuštění skriptu

V prvním příkladu je ukázáno, jakým způsobem je možné spustit skript naprogramovaný v jazyce Scheme přímo z céčka. Interpret Scheme lze mít spuštěn ve více instancích, přičemž ke každé instanci se dostaneme přes její kontext. Nejedná se přitom o globální proměnnou a jednotlivé kontexty mezi sebou přímo nesdílí data. Co to znamená v praxi? Můžeme vytvořit více na sobě nezávislých kontextů, použít tyto kontexty v různých vláknech atd. – zde programátorovi nejsou kladeny žádné závažnější překážky, což je jedna z výhod TinyScheme.

Nový kontext se vytvoří zavoláním funkce scheme_init_new:

scheme *sc;
 
sc = scheme_init_new();

Ve chvíli, kdy budeme chtít kontext zrušit (například při ukončení vlákna), musíme zavolat opačnou funkci nazvanou scheme_deinit:

scheme_deinit(sc);

Dále můžeme vytvořit jednoduchý skript volající funkci display. Tento skript uložíme do běžného céčkového řetězce:

const char *script="(display \"Hello world!\")";

Načtení a vyhodnocení skriptu se provede funkcí scheme_load_string:

scheme_load_string(sc, script);
Poznámka: v předchozí větě jsem použil slovo vyhodnocení. To znamená, že se každá forma zapsaná ve skriptu skutečně zpracuje interpretrem, konkrétně funkcí eval. Pokud se jedná o definici nového jména (proměnné, funkce, …), bude jméno vytvořeno v daném prostředí; ovšem pokud se jedná o volání funkce, bude funkce vyhodnocena, tj. zavolána.

Aby se po spuštění příkladu něco skutečně stalo, budeme muset vytvořit i céčkovskou variantu funkce display. Ta může vypadat následovně:

pointer display(scheme *sc, pointer args) {
    if (args!=sc->NIL) {
        if (sc->vptr->is_string(sc->vptr->pair_car(args)))  {
            char *str = sc->vptr->string_value(sc->vptr->pair_car(args));
            printf("%s", str);
        }
    }
    return sc->NIL;
}

Tato funkce sice může na první pohled vypadat složitě, ale ve skutečnosti celá její složitost spočívá v tom, že kontrolujeme, zda je jí předán parametr a zda je tento parametr typu string. Pokud tomu tak je, tak pomocí funkce string_value (přístupné přes ukazatel) získáme céčkovský řetězec a ten posléze vytiskneme.

Novou funkci musíme zaregistrovat (pod vhodným jménem), aby ji interpret jazyka Scheme mohl zavolat:

sc->vptr->scheme_define(
    sc,
    sc->global_env,
    sc->vptr->mk_symbol(sc, "display"),
    sc->vptr->mk_foreign_func(sc, display));
Poznámka: povšimněte si, jakým způsobem se volají funkce přes ukazatel získaný z tabulky vptr z aktuálního kontextu. Globální prostor proměnných a funkcí tím vůbec není ovlivněn.

10. Úplný zdrojový kód prvního příkladu

Podívejme se nyní na úplný zdrojový kód prvního příkladu popsaného v předchozí kapitole:

#include <stdio.h>
 
#define USE_INTERFACE 1
 
#include "scheme.h"
#include "scheme-private.h"
 
pointer display(scheme *sc, pointer args) {
    if (args!=sc->NIL) {
        if (sc->vptr->is_string(sc->vptr->pair_car(args)))  {
            char *str = sc->vptr->string_value(sc->vptr->pair_car(args));
            printf("%s", str);
        }
    }
    return sc->NIL;
}
 
int main(void)
{
    scheme *sc;
 
    sc = scheme_init_new();
 
    sc->vptr->scheme_define(
        sc,
        sc->global_env,
        sc->vptr->mk_symbol(sc, "display"),
        sc->vptr->mk_foreign_func(sc, display));
 
    const char *script="(display \"Hello world!\")";
 
    scheme_load_string(sc, script);
 
    scheme_deinit(sc);
    return 0;
}
Poznámka: povšimněte si především řádku #define USE_INTERFACE 1. Ten je nutné použít ještě před načtením hlavičkových souborů TinyScheme. V opačném případě nebude dostupná tabulka vptr s ukazateli funkcí.

11. Překlad prvního příkladu

Pro jednoduchost budeme první demonstrační příklad překládat ve stejném adresáři, v němž se nachází samotný projekt TinyScheme. Při překladu musíme určit, že se hlavičkové soubory scheme.h a scheme-private.h nachází v aktuálním adresáři. Pro tento účel slouží přepínač -I. Dále je nutné říci linkeru, kde nalezne knihovnu tinyscheme, která je na Linuxu představována soubory libtinyscheme.so a libtinyscheme.a. Pro tento účel použijeme přepínač -L. Překladač i linker (přesněji řečeno preprocesor, překladač i linker) lze spustit jediným příkazem, a to konkrétně takto:

gcc -I . -L . embed1.c -o embed1 -l tinyscheme

Lepší je však použít soubor Makefile, který ve své nejjednodušší podobě může vypadat následovně:

CC=gcc
 
CFLAGS=-Wall -std=c99 -pedantic -I.
 
LIBS=-L . -l tinyscheme
 
EXENAME=embed1
 
all:    ${EXENAME}
 
run:
        LD_LIBRARY_PATH=. ./${EXENAME}
 
clean:
        rm -f embed1.o
        rm -f ${EXENAME}
 
${EXENAME}:     embed1.o
        ${CC} $< ${LIBS} -o $@
 
embed1.o:       embed1.c
        ${CC} -c $< ${CFLAGS}
Poznámka: pokud se soubory projektu TinyScheme budou nabízet v odlišném adresáři, je úprava souboru Makefile snadná – postačí upravit třetí a pátý řádek, popř. do souboru přidat další proměnnou TINY_SCHEME_DIR apod.

12. Načtení skriptu z externího souboru

Ve druhém demonstračním příkladu je ukázáno, jak lze načíst skript (naprogramovaný ve Scheme) z externího souboru. Nejdříve si ukážeme načtení standardního souboru init.scm, o němž jsme se zmínili v páté kapitole. Prvním krokem je inicializace kontextu interpretru jazyka Scheme, což již dobře známe:

scheme *sc;
 
sc = scheme_init_new();

Dále otevřeme soubor init.scm pro čtení a načteme ho funkcí scheme_load_file:

FILE *finit = fopen("init.scm", "r");
scheme_load_file(sc, finit);
fclose(finit);
Poznámka: v praxi by samozřejmě bylo nutné zkontrolovat, zda se soubor podařilo otevřít, zavřít atd.

V následujícím kroku je nutné definovat funkci display, což již známe, takže jen krátce:

sc->vptr->scheme_define(
    sc,
    sc->global_env,
    sc->vptr->mk_symbol(sc, "display"),
    sc->vptr->mk_foreign_func(sc, display));

Dále se pokusíme načíst skript nazvaný script2.scm, který obsahuje definici nové funkce a současně i její volání:

(define (say-hello)
  (display "Hello world!")
  (newline))
 
(say-hello)

Tento skript načteme zcela stejným způsobem jako výše zmíněný standardní skript init.scm:

FILE *f = fopen("script2.scm", "r");
scheme_load_file(sc, f);
fclose(f);

Pochopitelně nesmíme zapomenout ani na „úklid“ všech otevřených a inicializovaných prostředků:

scheme_deinit(sc);

13. Úplný zdrojový kód druhého příkladu

Pro úplnost si ukažme úplný zdrojový kód dnešního druhého příkladu:

#include <stdio.h>
 
#define USE_INTERFACE 1
 
#include "scheme.h"
#include "scheme-private.h"
 
pointer display(scheme *sc, pointer args) {
    if (args!=sc->NIL) {
        if (sc->vptr->is_string(sc->vptr->pair_car(args)))  {
            char *str = sc->vptr->string_value(sc->vptr->pair_car(args));
            printf("%s", str);
        }
    }
    return sc->NIL;
}
 
int main(void)
{
    scheme *sc;
 
    sc = scheme_init_new();
 
    FILE *finit = fopen("init.scm", "r");
    scheme_load_file(sc, finit);
    fclose(finit);
 
    sc->vptr->scheme_define(
        sc,
        sc->global_env,
        sc->vptr->mk_symbol(sc, "display"),
        sc->vptr->mk_foreign_func(sc, display));
 
    FILE *f = fopen("script2.scm", "r");
    scheme_load_file(sc, f);
    fclose(f);
 
    scheme_deinit(sc);
    return 0;
}

14. Zpracování numerických hodnot předaných do nativní funkce ze Scheme

Ve třetím demonstračním příkladu je ukázáno, jak lze zpracovat numerické hodnoty (resp. zde jedinou numerickou hodnotu) předanou do nativní funkce z jazyka Scheme. Příkladem může být funkce, která vrátí zadanou hodnotu, ovšem s opačným znaménkem. Poměrně naivní implementace takové funkce může vypadat následovně:

pointer negate(scheme *sc, pointer args) {
      if (args!=sc->NIL) {
          if (sc->vptr->is_number(sc->vptr->pair_car(args))) {
              double v=sc->vptr->rvalue(sc->vptr->pair_car(args));
              return sc->vptr->mk_real(sc, -v);
          }
      }
      return sc->NIL;
}

Registrace této funkce:

sc->vptr->scheme_define(
    sc,
    sc->global_env,
    sc->vptr->mk_symbol(sc, "negate"),
    sc->vptr->mk_foreign_func(sc, negate));

Funkci otestujeme tímto skriptem naprogramovaných ve Scheme:

(define (test-negate)
  (display "test-negate")
  (display (negate 0))
  (display (negate 1))
  (display (negate -1))
  (display (negate "foobar"))
  (display "done"))
 
(test-negate)

Upravit budeme muset i naši implementaci funkce display, a to z toho důvodu, aby dokázala pracovat s numerickými hodnotami, nejenom s řetězci:

pointer display(scheme *sc, pointer args) {
    if (args!=sc->NIL) {
        if (sc->vptr->is_string(sc->vptr->pair_car(args)))  {
            char *str = sc->vptr->string_value(sc->vptr->pair_car(args));
            printf("%s\n", str);
        }
        else if (sc->vptr->is_number(sc->vptr->pair_car(args))) {
            double v=sc->vptr->rvalue(sc->vptr->pair_car(args));
            printf("%f\n", v);
        }
    }
    return sc->NIL;
}

15. Úplný zdrojový kód třetího příkladu

Jak se již stalo zvykem, uvedeme si úplný zdrojový kód upraveného demonstračního příkladu:

#include <stdio.h>
 
#define USE_INTERFACE 1
 
#include "scheme.h"
#include "scheme-private.h"
 
pointer display(scheme *sc, pointer args) {
    if (args!=sc->NIL) {
        if (sc->vptr->is_string(sc->vptr->pair_car(args)))  {
            char *str = sc->vptr->string_value(sc->vptr->pair_car(args));
            printf("%s\n", str);
        }
        else if (sc->vptr->is_number(sc->vptr->pair_car(args))) {
            double v=sc->vptr->rvalue(sc->vptr->pair_car(args));
            printf("%f\n", v);
        }
    }
    return sc->NIL;
}
 
pointer negate(scheme *sc, pointer args) {
      if (args!=sc->NIL) {
          if (sc->vptr->is_number(sc->vptr->pair_car(args))) {
              double v=sc->vptr->rvalue(sc->vptr->pair_car(args));
              return sc->vptr->mk_real(sc, -v);
          }
      }
      return sc->NIL;
}
 
int main(void)
{
    scheme *sc;
 
    sc = scheme_init_new();
 
    FILE *finit = fopen("init.scm", "r");
    scheme_load_file(sc, finit);
    fclose(finit);
 
    sc->vptr->scheme_define(
        sc,
        sc->global_env,
        sc->vptr->mk_symbol(sc, "display"),
        sc->vptr->mk_foreign_func(sc, display));
 
    sc->vptr->scheme_define(
        sc,
        sc->global_env,
        sc->vptr->mk_symbol(sc, "negate"),
        sc->vptr->mk_foreign_func(sc, negate));
 
    FILE *f = fopen("script3.scm", "r");
    scheme_load_file(sc, f);
    fclose(f);
 
    scheme_deinit(sc);
    return 0;
}

16. Zavolání funkce s větším počtem parametrů

Funkci s větším počtem parametrů je předáván seznam, což je interně rekurzivně vázaná sekvence tečka dvojic. Z tohoto důvodu je získání jednotlivých parametrů poněkud složitější a využijeme zde varianty funkcí car a cdr. Příkladem může být funkce pro vynásobení dvou předaných hodnot:

pointer multiply(scheme *sc, pointer args) {
      if (args!=sc->NIL) {
          if (sc->vptr->is_number(sc->vptr->pair_car(args)) &&
              sc->vptr->is_number(sc->vptr->pair_car(sc->vptr->pair_cdr(args)))) {
              double v1=sc->vptr->rvalue(sc->vptr->pair_car(args));
              double v2=sc->vptr->rvalue(sc->vptr->pair_car(sc->vptr->pair_cdr(args)));
              return sc->vptr->mk_real(sc, v1 * v2);
          }
      }
      return sc->NIL;
}

Samotné otestování takové funkce je snadné:

(define (test-multiply)
  (display "test-multiply")
  (display (multiply 6 7))
  (display "done"))
 
(test-multiply)
Poznámka: alternativně lze k parametrům přistupovat skutečně jako k vektoru.

17. Jaký interpret použít pro implementaci DSL?

Na tomto místě se možná někteří čtenáři mohou zeptat, jakou implementaci LISPu či Scheme je vlastně nejvýhodnější použít v případě, že potřebujeme přidat vlastní DSL (doménově specifický jazyk) do nějaké aplikace. Z prozatím zmíněných řešení se nabízí:

  1. PicoLisp
  2. GNU Guile
  3. TinyScheme

Předností PicoLispu jsou jeho nepatrné nároky na výpočetní výkon CPU i na velikost dostupné operační paměti, takže je možné interpret tohoto programovacího jazyka provozovat i na šestnáctibitových a pochopitelně i na výkonnějších 32bitových mikrořadičích. Ovšem musíme se přitom smířit s tím, že se jedná o v některých ohledech nestandardní implementaci LISPu, s níž nebudou uživatelé dobře seznámeni.

Implementace GNU Guile naproti tomu odpovídá RnRS, což samozřejmě zlepšuje pozici této implementace, neboť je k dispozici značné množství dokumentace o Scheme, knihy, tutoriály, záznamy z přednášek atd. GNU Guile taktéž podporuje překlad, multithreading, hygienická makra, práci s komplexními čísly, se zlomky atd. atd. Ovšem za existenci všech těchto vlastností zaplatíme většími nároky na systémové zdroje, což by mohlo v některých implementacích vadit.

A konečně dnes popisovaná implementace TinyScheme leží zhruba na půli cesty mezi minimalistickým, ovšem nestandardním PicoLispem na straně jedné a GNU Guile na straně druhé. Mezi jeho přednosti patří relativně dobrá podpora vlastností specifikovaných v R5RS (starší, ale stále platná specifikace), malé nároky na systémové zdroje, možnost vytvoření několika na sobě nezávislých kontextů apod. Nevýhodou ovšem je, že není podporována úplná „numerická věž“ Scheme; zejména může citelně chybět práce se zlomky (což jsme již viděli na několika příkladech). Taktéž nejsou plně podporována hygienická makra (chybí i makro while, to je však možné doprogramovat).

Poznámka: v dalších částech tohoto miniseriálu ovšem uvidíme, že existuje ještě větší množství implementací LISPu a Scheme, jejichž interpretry či dokonce překladače je možné v případě potřeby vložit do nativních aplikací a vytvořit tak pro ně vhodný DSL. Některé z těchto implementací nabízí plnohodnotný překladač, další jsou zase určeny pro minimalistická prostředí s omezenými výpočetními prostředky.

18. Repositář s demonstračními příklady

Zdrojové kódy všech dnes použitých demonstračních příkladů byly uloženy do Git repositáře, který je dostupný na adrese https://github.com/tisnik/lisp-families.git (stále na GitHubu :-). V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý), můžete namísto toho použít odkazy na jednotlivé příklady, které naleznete v následující tabulce:

# Příklad Popis příkladu Cesta
1 ackermann.scm Ackermannova funkce https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/ackermann.scm
2 closure1.scm vytvoření a použití uzávěru, první příklad https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/closure1.scm
3 closure2.scm vytvoření a použití uzávěrů, druhý příklad https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/closure2.scm
4 do_loop.scm první varianta smyčky do https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/do_loop.scm
5 do_loop2.scm druhá varianta smyčky do https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/do_loop2.scm
6 do_loop3.scm třetí varianta smyčky do https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/do_loop3.scm
7 factorial1.scm výpočet faktoriálu, rekurzivní varianta https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/factorial.scm
8 factorial2.scm výpočet faktoriálu, rekurzivní varianta https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/factorial.scm
9 factorial3.scm výpočet faktoriálu, tail-call varianta https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/factorial.scm
10 fibonacci.scm výpočet n-tého prvku Fibonacciho posloupnosti https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/fibonacci.scm
11 nested_loops1.scm vnořené smyčky, první varianta https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/nested_loop­s1.scm
12 nested_loops2.scm vnořené smyčky, druhá varianta https://github.com/tisnik/lisp-families/blob/master/tinys­cheme/examples/nested_loop­s2.scm

Projekty ukazující rozhraní mezi TinyScheme a céčkem:

# Příklad Popis příkladu Cesta
1 embed1 inicializace interpretru Scheme a spuštění skriptu https://github.com/tisnik/lisp-families/tree/master/tinyscheme/c-interface/embed1
2 embed2 načtení skriptu z externího souboru https://github.com/tisnik/lisp-families/tree/master/tinyscheme/c-interface/embed2
3 embed3 zpracování numerických hodnot předaných do nativní funkce ze Scheme https://github.com/tisnik/lisp-families/tree/master/tinyscheme/c-interface/embed3
4 embed4 zavolání funkce s větším počtem parametrů https://github.com/tisnik/lisp-families/tree/master/tinyscheme/c-interface/embed4

19. Literatura

  1. Peter Seibel
    „Practical Common Lisp“
    2009
  2. Paul Graham
    „ANSI Common Lisp“
    1995
  3. Gerald Gazdar
    „Natural Language Processing in Lisp: An Introduction to Computational Linguistics“
    1989
  4. Peter Norvig
    „Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp“
    1991
  5. Alex Mileler et.al.
    „Clojure Applied: From Practice to Practitioner“
    2015
  6. „Living Clojure: An Introduction and Training Plan for Developers“
    2015
  7. Dmitri Sotnikov
    „Web Development with Clojure: Build Bulletproof Web Apps with Less Code“
    2016
  8. McCarthy
    „Recursive functions of symbolic expressions and their computation by machine, part I“
    1960
  9. R. Kent Dybvig
    „The Scheme Programming Language“
    2009
  10. Max Hailperin
    „Concrete Abstractions“
    1998
  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 reference“
    Autodesk Ltd., October 1987
  14. „AutoLISP Release 10, Programmer's reference“
    Autodesk Ltd., September 1988
  15. 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
  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
  18. Harold Abelson, Gerald Jay Sussman, Julie Sussman:
    Structure and Interpretation of Computer Programs
    MIT Press. 1985, 1996 (a možná vyšel i další přetisk)
  19. Paul Graham
    On Lisp
    Prentice Hall, 1993
    Dostupné online na stránce http://www.paulgraham.com/on­lisptext.html
  20. David S. Touretzky
    Common LISP: A Gentle Introduction to Symbolic Computation (Dover Books on Engineering)
  21. Peter Norvig
    Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp
  22. Patrick Winston, Berthold Horn
    Lisp (3rd Edition)
    ISBN-13: 978–0201083194, ISBN-10: 0201083191
  23. Matthias Felleisen, David Van Horn, Dr. Conrad Barski
    Realm of Racket: Learn to Program, One Game at a Time!
    ISBN-13: 978–1593274917, ISBN-10: 1593274912

20. Odkazy na Internetu

  1. GOTO 2018 • Functional Programming in 40 Minutes • Russ Olsen
    https://www.youtube.com/wat­ch?v=0if71HOyVjY
  2. TinyScheme (stránka na Sourceforge)
    http://tinyscheme.sourcefor­ge.net/home.html
  3. Embedding Tiny Scheme in a Game
    http://www.silicondelight­.com/embedding-tiny-scheme-in-a-game/
  4. Embedding Scheme for a game mission scripting DSL
    http://carloscarrasco.com/embedding-scheme-for-a-game-mission-scripting-dsl.html
  5. Všechny verze TinyScheme na SourceForge
    https://sourceforge.net/pro­jects/tinyscheme/files/ti­nyscheme/
  6. Fork TinyScheme na GitHubu
    https://github.com/yawnt/tinyscheme
  7. Ackermannova funkce
    https://cs.wikipedia.org/wi­ki/Ackermannova_funkce
  8. Ackermann function na Rosetta Code
    https://rosettacode.org/wi­ki/Ackermann_function#Sche­me
  9. Scheme Quick Reference
    https://www.st.cs.uni-saarland.de/edu/config-ss04/scheme-quickref.pdf
  10. Slajdy o Scheme (od slajdu číslo 15)
    https://docs.google.com/pre­sentation/d/1abmDnKjrq1tcjGvvRNAK­hOiSTSE2lyagtcEPal07Gbo/e­dit
  11. Scheme Cheat Sheet
    https://github.com/smythp/scheme-cheat-sheet
  12. Embedding Lua, embedding Guile
    http://puntoblogspot.blog­spot.com/2013/04/embedding-lua-embedding-guile.html
  13. Lambda Papers
    https://en.wikisource.org/wi­ki/Lambda_Papers
  14. Revised7Report on the Algorithmic Language Scheme
    https://small.r7rs.org/at­tachment/r7rs.pdf
  15. Video Lectures (MIT, SICP 2005)
    https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6–001-structure-and-interpretation-of-computer-programs-spring-2005/video-lectures/
  16. Why is Scheme my first language in university?
    https://softwareengineerin­g.stackexchange.com/questi­ons/115252/why-is-scheme-my-first-language-in-university
  17. The Perils of JavaSchools
    https://www.joelonsoftware­.com/2005/12/29/the-perils-of-javaschools-2/
  18. How to Design Programs, Second Edition
    https://htdp.org/2019–02–24/index.html
  19. LilyPond
    http://lilypond.org/
  20. LilyPond — Extending (přes Scheme)
    http://lilypond.org/doc/v2­.18/Documentation/extendin­g/scheme-tutorial
  21. Scheme in LilyPond
    http://lilypond.org/doc/v2­.18/Documentation/extendin­g/scheme-in-lilypond
  22. GnuCash
    http://www.gnucash.org/
  23. Custom Reports (in GNU Cash)
    https://wiki.gnucash.org/wi­ki/Custom_Reports
  24. Program by Design
    https://programbydesign.org/
  25. SchemePy
    https://pypi.org/project/SchemePy/
  26. LISP FQA: Section – [1–5] What is the „minimal“ set of primitives needed for a Lisp interpreter?
    http://www.faqs.org/faqs/lisp-faq/part1/section-6.html
  27. femtolisp
    https://github.com/JeffBe­zanson/femtolisp
  28. (How to Write a (Lisp) Interpreter (in Python))
    http://norvig.com/lispy.html
  29. Repositář s Guile Emacsem
    http://git.hcoop.net/?p=bpt/guile.git
  30. Interacting with Guile Compound Data Types in C
    http://www.lonelycactus.com/gu­ilebook/x1555.html
  31. Calling Guile functions from C
    http://www.lonelycactus.com/gu­ilebook/c1204.html#SECCAL­LGUILEFUNC
  32. Arrays, and other compound data types
    http://www.lonelycactus.com/gu­ilebook/charrays.html
  33. Interacting with Guile Compound Data Types in C
    http://www.lonelycactus.com/gu­ilebook/x1555.html
  34. Guile Reference Manual
    https://www.gnu.org/softwa­re/guile/manual/html_node/in­dex.html
  35. Scheme: Summary of Common Syntax
    https://www.gnu.org/softwa­re/guile/manual/html_node/Syn­tax-Summary.html#Syntax-Summary
  36. Scripting with Guile: Extension language enhances C and Scheme
    https://www.ibm.com/develo­perworks/library/l-guile/index.html
  37. Having fun with Guile: a tutorial
    http://dustycloud.org/misc/guile-tutorial.html
  38. Guile: Loading Readline Support
    https://www.gnu.org/softwa­re/guile/manual/html_node/Lo­ading-Readline-Support.html#Loading-Readline-Support
  39. lispy
    https://pypi.org/project/lispy/
  40. Lython
    https://pypi.org/project/Lython/
  41. Lizpop
    https://pypi.org/project/lizpop/
  42. Budoucnost programovacích jazyků
    http://www.knesl.com/budoucnost-programovacich-jazyku
  43. LISP Prolog and Evolution
    http://blog.samibadawi.com/2013/05/lisp-prolog-and-evolution.html
  44. List of Lisp-family programming languages
    https://en.wikipedia.org/wi­ki/List_of_Lisp-family_programming_languages
  45. clojure_py na indexu PyPi
    https://pypi.python.org/py­pi/clojure_py
  46. PyClojure
    https://github.com/eigenhom­bre/PyClojure
  47. Hy na GitHubu
    https://github.com/hylang/hy
  48. Hy: The survival guide
    https://notes.pault.ag/hy-survival-guide/
  49. Hy běžící na monitoru terminálu společnosti Symbolics
    http://try-hy.appspot.com/
  50. Welcome to Hy’s documentation!
    http://docs.hylang.org/en/stable/
  51. Hy na PyPi
    https://pypi.org/project/hy/#des­cription
  52. Getting Hy on Python
    https://lwn.net/Articles/596626/
  53. Programming Can Be Fun with Hy
    https://opensourceforu.com/2014/02/pro­gramming-can-fun-hy/
  54. Přednáška o projektu Hy (pětiminutový lighttalk)
    http://blog.pault.ag/day/2013/04/02
  55. Hy (Wikipedia)
    https://en.wikipedia.org/wiki/Hy
  56. GNU Emacs Lisp Reference Manual: Point
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­lisp/Point.html
  57. GNU Emacs Lisp Reference Manual: Narrowing
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­lisp/Narrowing.html
  58. GNU Emacs Lisp Reference Manual: Functions that Create Markers
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­lisp/Creating-Markers.html
  59. GNU Emacs Lisp Reference Manual: Motion
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­lisp/Motion.html#Motion
  60. GNU Emacs Lisp Reference Manual: Basic Char Syntax
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­lisp/Basic-Char-Syntax.html
  61. Elisp: Sequence: List, Array
    http://ergoemacs.org/emac­s/elisp_list_vs_vector.html
  62. Elisp: Property List
    http://ergoemacs.org/emac­s/elisp_property_list.html
  63. Elisp: Hash Table
    http://ergoemacs.org/emac­s/elisp_hash_table.html
  64. Elisp: Association List
    http://ergoemacs.org/emac­s/elisp_association_list.html
  65. The mapcar Function (An Introduction to Programming in Emacs Lisp)
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­intr/mapcar.html
  66. Anaphoric macro
    https://en.wikipedia.org/wi­ki/Anaphoric_macro
  67. Some Common Lisp Loop Macro Examples
    https://www.youtube.com/wat­ch?v=3yl8o6r_omw
  68. A Guided Tour of Emacs
    https://www.gnu.org/softwa­re/emacs/tour/
  69. The Roots of Lisp
    http://www.paulgraham.com/ro­otsoflisp.html
  70. Evil (Emacs Wiki)
    https://www.emacswiki.org/emacs/Evil
  71. Evil (na GitHubu)
    https://github.com/emacs-evil/evil
  72. Evil (na stránkách repositáře MELPA)
    https://melpa.org/#/evil
  73. Evil Mode: How I Switched From VIM to Emacs
    https://blog.jakuba.net/2014/06/23/e­vil-mode-how-to-switch-from-vim-to-emacs.html
  74. GNU Emacs (home page)
    https://www.gnu.org/software/emacs/
  75. GNU Emacs (texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?GnuEmacs
  76. An Introduction To Using GDB Under Emacs
    http://tedlab.mit.edu/~dr/gdbin­tro.html
  77. An Introduction to Programming in Emacs Lisp
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­intr/index.html
  78. 27.6 Running Debuggers Under Emacs
    https://www.gnu.org/softwa­re/emacs/manual/html_node/e­macs/Debuggers.html
  79. GdbMode
    http://www.emacswiki.org/e­macs/GdbMode
  80. Emacs (Wikipedia)
    https://en.wikipedia.org/wiki/Emacs
  81. Emacs timeline
    http://www.jwz.org/doc/emacs-timeline.html
  82. Emacs Text Editors Family
    http://texteditors.org/cgi-bin/wiki.pl?EmacsFamily
  83. Vrapper aneb spojení možností Vimu a Eclipse
    https://mojefedora.cz/vrapper-aneb-spojeni-moznosti-vimu-a-eclipse/
  84. Vrapper aneb spojení možností Vimu a Eclipse (část 2: vyhledávání a nahrazování textu)
    https://mojefedora.cz/vrapper-aneb-spojeni-moznosti-vimu-a-eclipse-cast-2-vyhledavani-a-nahrazovani-textu/
  85. Emacs/Evil-mode – A basic reference to using evil mode in Emacs
    http://www.aakarshnair.com/posts/emacs-evil-mode-cheatsheet
  86. From Vim to Emacs+Evil chaotic migration guide
    https://juanjoalvarez.net/es/de­tail/2014/sep/19/vim-emacsevil-chaotic-migration-guide/
  87. Introduction to evil-mode {video)
    https://www.youtube.com/wat­ch?v=PeVQwYUxYEg
  88. EINE (Emacs Wiki)
    http://www.emacswiki.org/emacs/EINE
  89. EINE (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?EINE
  90. ZWEI (Emacs Wiki)
    http://www.emacswiki.org/emacs/ZWEI
  91. ZWEI (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?ZWEI
  92. Zmacs (Wikipedia)
    https://en.wikipedia.org/wiki/Zmacs
  93. Zmacs (Texteditors.org)
    http://texteditors.org/cgi-bin/wiki.pl?Zmacs
  94. TecoEmacs (Emacs Wiki)
    http://www.emacswiki.org/e­macs/TecoEmacs
  95. Micro Emacs
    http://www.emacswiki.org/e­macs/MicroEmacs
  96. Micro Emacs (Wikipedia)
    https://en.wikipedia.org/wi­ki/MicroEMACS
  97. EmacsHistory
    http://www.emacswiki.org/e­macs/EmacsHistory
  98. Seznam editorů s ovládáním podobným Emacsu či kompatibilních s příkazy Emacsu
    http://www.finseth.com/emacs.html
  99. evil-numbers
    https://github.com/cofi/evil-numbers
  100. Debuggery a jejich nadstavby v Linuxu (1.část)
    http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu/
  101. Debuggery a jejich nadstavby v Linuxu (2.část)
    http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-2-cast/
  102. Debuggery a jejich nadstavby v Linuxu (3): Nemiver
    http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-3-nemiver/
  103. Debuggery a jejich nadstavby v Linuxu (4): KDbg
    http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-4-kdbg/
  104. Debuggery a jejich nadstavby v Linuxu (5): ladění aplikací v editorech Emacs a Vim
    https://mojefedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-5-ladeni-aplikaci-v-editorech-emacs-a-vim/
  105. Org mode
    https://orgmode.org/
  106. The Org Manual
    https://orgmode.org/manual/index.html
  107. Kakoune (modální textový editor)
    http://kakoune.org/
  108. Vim-style keybinding in Emacs/Evil-mode
    https://gist.github.com/tro­yp/6b4c9e1c8670200c04c16036805773d8
  109. Emacs – jak začít
    http://www.abclinuxu.cz/clan­ky/navody/emacs-jak-zacit
  110. Programovací jazyk LISP a LISP machines
    https://www.root.cz/clanky/pro­gramovaci-jazyk-lisp-a-lisp-machines/
  111. Evil-surround
    https://github.com/emacs-evil/evil-surround
  112. Spacemacs
    http://spacemacs.org/
  113. Lisp: Common Lisp, Racket, Clojure, Emacs Lisp
    http://hyperpolyglot.org/lisp
  114. Common Lisp, Scheme, Clojure, And Elisp Compared
    http://irreal.org/blog/?p=725
  115. Does Elisp Suck?
    http://irreal.org/blog/?p=675
  116. Emacs pro mírně pokročilé (9): Elisp
    https://www.root.cz/clanky/emacs-elisp/
  117. If I want to learn lisp, are emacs and elisp a good choice?
    https://www.reddit.com/r/e­macs/comments/2m141y/if_i_wan­t_to_learn_lisp_are_emacs_an­d_elisp_a/
  118. Clojure(Script) Interactive Development Environment that Rocks!
    https://github.com/clojure-emacs/cider
  119. An Introduction to Emacs Lisp
    https://harryrschwartz.com/2014/04/08/an-introduction-to-emacs-lisp.html
  120. Emergency Elisp
    http://steve-yegge.blogspot.com/2008/01/emergency-elisp.html
  121. Lambda calculus
    https://en.wikipedia.org/wi­ki/Lambda_calculus
  122. John McCarthy's original LISP paper from 1959
    https://www.reddit.com/r/pro­gramming/comments/17lpz4/joh­n_mccarthys_original_lisp_pa­per_from_1959/
  123. Micro Manual LISP
    https://www.scribd.com/do­cument/54050141/Micro-Manual-LISP
  124. How Lisp Became God's Own Programming Language
    https://twobithistory.org/2018/10/14/lis­p.html
  125. History of Lisp
    http://jmc.stanford.edu/ar­ticles/lisp/lisp.pdf
  126. The Roots of Lisp
    http://languagelog.ldc.upen­n.edu/myl/llog/jmc.pdf
  127. Racket
    https://racket-lang.org/
  128. The Racket Manifesto
    http://felleisen.org/matthi­as/manifesto/
  129. MIT replaces Scheme with Python
    https://www.johndcook.com/blog/2009/03/26/mit-replaces-scheme-with-python/
  130. Adventures in Advanced Symbolic Programming
    http://groups.csail.mit.e­du/mac/users/gjs/6.945/
  131. Why MIT Switched from Scheme to Python (2009)
    https://news.ycombinator.com/i­tem?id=14167453
  132. Starodávná stránka XLispu
    http://www.xlisp.org/
  133. AutoLISP
    https://en.wikipedia.org/wi­ki/AutoLISP
  134. Seriál PicoLisp: minimalistický a výkonný interpret Lispu
    https://www.root.cz/serialy/picolisp-minimalisticky-a-vykonny-interpret-lispu/
  135. Common Lisp
    https://common-lisp.net/
  136. Getting Going with Common Lisp
    https://cliki.net/Getting%20Started
  137. Online Tutorial (Common Lisp)
    https://cliki.net/online%20tutorial
  138. Guile Emacs
    https://www.emacswiki.org/e­macs/GuileEmacs
  139. Guile Emacs History
    https://www.emacswiki.org/e­macs/GuileEmacsHistory
  140. Guile is a programming language
    https://www.gnu.org/software/guile/
  141. MIT Scheme
    http://groups.csail.mit.e­du/mac/projects/scheme/
  142. SIOD: Scheme in One Defun
    http://people.delphiforum­s.com/gjc//siod.html
  143. CommonLispForEmacs
    https://www.emacswiki.org/e­macs/CommonLispForEmacs
  144. Elisp: print, princ, prin1, format, message
    http://ergoemacs.org/emac­s/elisp_printing.html
  145. Special Forms in Lisp
    http://www.nhplace.com/ken­t/Papers/Special-Forms.html
  146. Basic Building Blocks in LISP
    https://www.tutorialspoin­t.com/lisp/lisp_basic_syn­tax.htm
  147. Introduction to LISP – University of Pittsburgh
    https://people.cs.pitt.edu/~mi­los/courses/cs2740/Lectures/Lis­pTutorial.pdf
  148. Why don't people use LISP
    https://forums.freebsd.org/threads/why-dont-people-use-lisp.24572/
  149. Structured program theorem
    https://en.wikipedia.org/wi­ki/Structured_program_the­orem
  150. Clojure: API Documentation
    https://clojure.org/api/api
  151. Tutorial for the Common Lisp Loop Macro
    http://www.ai.sri.com/pkarp/loop.html
  152. Common Lisp's Loop Macro Examples for Beginners
    http://www.unixuser.org/~e­uske/doc/cl/loop.html
  153. A modern list api for Emacs. No 'cl required.
    https://github.com/magnars/dash.el
  154. The LOOP Facility
    http://www.lispworks.com/do­cumentation/HyperSpec/Body/06_a­.htm
  155. Clojure.org: Vars and the Global Environment
    http://clojure.org/Vars
  156. Clojure.org: Refs and Transactions
    http://clojure.org/Refs
  157. Clojure.org: Atoms
    http://clojure.org/Atoms
  158. Clojure.org: Agents as Asynchronous Actions
    http://clojure.org/agents
  159. Transient Data Structureshttp://clojure.or­g/transients
  160. Dynamic Languages Strike Back
    http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html
  161. Scripting: Higher Level Programming for the 21st Century
    http://www.tcl.tk/doc/scripting.html
  162. Clojure (na Wikipedia EN)
    http://en.wikipedia.org/wiki/Clojure
  163. Clojure (na Wikipedia CS)
    http://cs.wikipedia.org/wiki/Clojure
  164. SICP (The Structure and Interpretation of Computer Programs)
    http://mitpress.mit.edu/sicp/
  165. Pure function
    http://en.wikipedia.org/wi­ki/Pure_function
  166. Funkcionální programování
    http://cs.wikipedia.org/wi­ki/Funkcionální_programová­ní
  167. Jazyky Hy a Clojure-py: moderní dialekty LISPu určené pro Python VM
    https://www.root.cz/clanky/jazyky-hy-a-clojure-py-moderni-dialekty-lispu-urcene-pro-python-vm/
  168. Pixie: lehký skriptovací jazyk s „kouzelnými“ schopnostmi
    https://www.root.cz/clanky/pixie-lehky-skriptovaci-jazyk-s-kouzelnymi-schopnostmi/
  169. Programovací jazyk Pixie: funkce ze základní knihovny a použití FFI
    https://www.root.cz/clanky/pro­gramovaci-jazyk-pixie-funkce-ze-zakladni-knihovny-a-pouziti-ffi/