Obsah
1. Chicken Scheme – další interpret a především překladač programovacího jazyka Scheme
2. Překlad a instalace projektu Chicken Scheme
3. Použití interpretru dodávaného současně s Chicken Scheme
4. Překlad skriptu naprogramovaného ve Scheme do nativního kódu
5. Možné problémy při překladu
6. Příprava jednoduchého benchmarku
7. Porovnání rychlosti interpretrů GNU Guile a Chicken Scheme
8. Rychlost benchmarku přeloženého do nativního kódu
9. Porovnání kvality překladače Chicken Scheme s alternativními implementacemi vytvořenými v C a Go
10. Typové informace a jejich vliv na výsledek benchmarku
11. Výsledky všech benchmarků v grafické podobě
12. Další vlastnosti programovacího jazyka implementovaného v rámci Chicken Scheme
16. FFI – rozhraní mezi Chicken Scheme a nativními jazyky (C apod.)
18. Repositář s demonstračními příklady
1. Chicken Scheme – další interpret a především překladač programovacího jazyka Scheme
V dnešní části seriálu o rozsáhlém a možná i poněkud chaotickém světě lispovských programovacích jazyků se seznámíme se základními vlastnostmi projektu nazvaného Chicken Scheme, který naleznete na adrese https://call-cc.org/. Podle názvu tohoto projektu je možné snadno uhodnout, že se jedná o další implementaci programovacího jazyka Scheme (plně podle R5RS a částečně i R7RS), takže se nám sbírka již popsaných implementací úspěšně rozrůstá (mimochodem: je zajímavé, že se Scheme stále drží v první padesátce seznamu nejcitovanějších programovacích jazyků, což je zvláštní, když si uvědomíme, že například na slavné MIT byl předmět založený na SICP nahrazen jinými předměty).
Jen pro připomenutí, s jakými variantami tohoto programovacího jazyka jsme se již setkali: především se jednalo o projekt nazvaný GNU Guile a taktéž o nástroj TinyScheme. Oba zmíněné projekty nabízí programátorům jak klasickou interaktivní smyčku REPL, tak i možnost vložit (embed) interpret či překladač jazyka Scheme do dalších nativních aplikací a tím do značné míry rozšířit jejich možnosti (skriptovatelné aplikace, aplikace s podporou pluginů získaných od třetích stran atd.). Zatímco projekt GNU Guile obsahuje jak interpret, tak i překladač (a to relativně dobrý), je TinyScheme v tomto ohledu mnohem jednodušší, protože se jedná o „pouhý“ interpret, ovšem pochopitelně doplněný o automatickou správu paměti a další pro Scheme naprosto nezbytné vlastnosti.
Obrázek 1: Logo projektu GNU Guile.
Z rozsáhlejších projektů jsme se zmínili o jazyku nazvaném Kawa, který je zajímavý a potenciálně užitečný hned z několika důvodů. Jedná se o implementaci jazyka Scheme naprogramovanou v Javě a běžící nad virtuálním strojem Javy (JVM). Ovšem současně se v žádném případě nejedná o pouhý primitivní interpret, ale o překladač jazyka Scheme do bajtkódu JVM. Z benchmarků je patrné, že výsledný kód vůbec není pomalý ale naopak dokáže více než zdárně konkurovat dalším programovacím jazykům, které v současnosti nad JVM existují.
Obrázek 2: Logo projektu Kawa.
A konečně jsme se ve třech článcích zabývali projektem nazvaným Racket, jehož původní jméno bylo PLT Scheme. Samotný programovací jazyk Racketu sice vychází z klasického Scheme, ale je poměrně snadno rozšiřitelný a modifikovatelný, takže vzniklo hned několik jeho variant. Kromě klasického dynamicky typovaného jazyka Scheme je tak možné použít jazyk s možností přesné deklarace datových typů, jazyk s infixovu notací zápisu aritmetických výrazů, dokonce i implementaci Algolu 60 atd.
Obrázek 3: Logo projektu Racket.
Přímými konkurenty Chicken Scheme jsou však odlišné implementace, s nimiž se ještě v tomto seriálu později podrobněji seznámíme:
- Gambit-C s pravděpodobně nejlepším překladačem do C
- Bigloo s překladačem do C, bajtkódu JVM a bajtkódu .NETu
- Scheme48 s překladačem do bajtkódu
Obrázek 4: Logo projektu Chicken Scheme.
2. Překlad a instalace projektu Chicken Scheme
Balíčky s projektem Chicken Scheme jsou sice většinou součástí standardních repositářů většiny rozšířených linuxových distribucí, ovšem mnohdy se setkáme se staršími verzemi tohoto jazyka. V době psaní tohoto článku je aktuální verze 5.1, ovšem například ve Fedoře 30 (což není tak stará distribuce) najdeme pouze Chicken Scheme ve verzi 4.12.0, o čemž se ostatně můžeme velmi snadno přesvědčit:
[schemer ~]$ cat /etc/redhat-release Fedora release 30 (Thirty) [schemer ~]$ chicken (c) 2008-2017, The CHICKEN Team (c) 2000-2007, Felix L. Winkelmann Version 4.12.0 linux-unix-gnu-x86-64 [ 64bit manyargs dload ptables ] compiled 2019-01-31 on buildvm-14.phx2.fedoraproject.org Enter `chicken -help' for information on how to use the compiler, or try `csc' for a more convenient interface. Run `csi' to start the interactive interpreter.
Aby bylo možné použít nejnovější stabilní verzi interpretru a překladače, je vhodnější provést překlad a instalaci Chicken Scheme přímo z dostupných zdrojových kódů. Potřebovat budeme standardní vývojové nástroje, zejména překladač programovacího jazyka C (výchozí je GCC, teoreticky je však možné využít i další překladače) a GNU Makefile. Nejprve je nutné stáhnout tarball se zdrojovými kódy stabilní verze Chicken Scheme. V tomto konkrétním příkladu se bude stahovat verze 5.1.0, ale pochopitelně můžete stáhnout i verzi starší či naopak novější:
[schemer ~]$ wget https://code.call-cc.org/releases/5.1.0/chicken-5.1.0.tar.gz --2019-11-14 19:20:27-- https://code.call-cc.org/releases/5.1.0/chicken-5.1.0.tar.gz Resolving code.call-cc.org (code.call-cc.org)... 78.47.93.131 Connecting to code.call-cc.org (code.call-cc.org)|78.47.93.131|:443... connected. HTTP request sent, awaiting response... 200 OK Length: 4071169 (3,9M) [application/x-gzip] Saving to: ‘chicken-5.1.0.tar.gz’ 100%[=====================================================================================================================>] 4 071 169 1,73MB/s in 2,2s
Následně je nutné stažený tarball rozbalit, a to běžným postupem:
[schemer ~]$ tar xvfz chicken-5.1.0.tar.gz
Dále přejít do adresáře vytvořeného při rozbalování tarballu se zdrojovými kódu:
[schemer ~]$ cd chicken-5.1.0
A provést vlastní překlad, který většinou trvá několik desítek sekund:
[schemer chicken-5.1.0]$ make PLATFORM=linux
Po překladu by se měly v aktuálním adresáři objevit minimálně tyto tři spustitelné soubory:
- chicken (základní tooling včetně interpretru)
- csi (interpret)
- csc (překladač)
Pro jistotu otestujeme, zda je možné spustit alespoň interpret (což by mělo být v každém případě možné):
[schemer chicken-5.1.0]$ ./csi CHICKEN (c) 2008-2019, The CHICKEN Team (c) 2000-2007, Felix L. Winkelmann Version 5.1.0 (rev 8e62f718) linux-unix-gnu-x86-64 [ 64bit dload ptables ]
3. Použití interpretru dodávaného současně s Chicken Scheme
Interpret dodávaný společně s projektem Chicken Scheme (resp. přesněji řečeno interpret, který jsme přeložili podle postupu z předchozí kapitoly) je kompatibilní s dalšími dialekty tohoto programovacího jazyka, a to minimálně na úrovni R5RS. Nejprve si vyzkoušíme naprogramovat a následně spustit funkci určenou pro výpočet faktoriálu, a to v její rekurzivní variantě (bez tail callů). Tato funkce bývá v oblasti LISPovských jazyků obdobou programu typu „Hello world“, který se používá v jazycích odvozených od Algolu (tato tradice začala už u céčka):
(define (println item)
(display item)
(newline))
(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)))))
(println (factorial 10))
Celý skript můžeme předat do interpretru, který je představován spustitelným souborem csi (Chicken Scheme Interpret):
[schemer ~]$ ./csi factorial.scm
Interpret by měl vypsat vypočtenou hodnotu faktoriálu a následně zůstat v interaktivní smyčce REPL:
[schemer ~]$ csi factorial.scm CHICKEN (c) 2008-2017, The CHICKEN Team (c) 2000-2007, Felix L. Winkelmann Version 4.12.0 linux-unix-gnu-x86-64 [ 64bit manyargs dload ptables ] compiled 2019-01-31 on buildvm-14.phx2.fedoraproject.org ; loading factorial.scm ... 3628800
Interpret musíme ukončit, a to například zavoláním funkce s názvem quit:
#;1> (quit)
Pokud je vyžadováno, aby se interpret ukončil ihned poté, co je dokončen běh vybraného skriptu, je nutné použít přepínač -q:
[schemer ~]$ ./csi -q factorial.scm
S tímto výsledkem:
[schemer ~]$ csi -q factorial.scm 3628800
4. Překlad skriptu naprogramovaného ve Scheme do nativního kódu
Existují dva hlavní důvody, proč by se vývojář vůbec měl zabývat projektem Chicken Scheme. Prvním důvodem je existence poměrně rozsáhlého ekosystému, který je okolo tohoto jazyka postaven (takzvané Eggs). A druhým důvodem je fakt, že je projekt Chicken Scheme vybaven překladačem, který dokáže transformovat skripty zapsané ve Scheme do nativního spustitelného kódu nebo do knihovny určené pro statické či dynamické slinkování s dalšími bloky nativního kódu. Ve výsledném kódu je kromě běžných runtime funkcí dostupný i plnohodnotný správce paměti (garbage collector), který je pro LISPovské jazyky prakticky nutností.
Samotný překlad je přitom proveden v několika krocích:
- Transpilace zdrojového kódu ze Scheme do jazyka C
- Překlad transpilovaného kódu překladačem jazyka C (například GCC)
- Slinkování do spustitelné podoby a/nebo knihovny
Důležité a potenciálně užitečné přitom je, že je umožněn takzvaný cross překlad pro jiné architektury, než s jakou právě vývojář pracuje. Je tak například možné na platformě x86–64 provést překlad aplikace pro procesory ARM, AArch64 atd.
Dnes si ovšem ukážeme „pouhý“ překlad do nativního kódu pro stejnou platformu a systém, na které je provozován vlastní Chicken Scheme. Samotný překlad je z pohledu uživatele-programátora až triviálně jednoduchý, protože postačuje použít nástroj csc neboli Chicken Scheme Compiler, kterému se v tom nejjednodušším případě předá jediný argument – jméno překládaného skriptu:
[schemer ~]$ csc factorial.scm
Po několika sekundách by se měl vytvořit spustitelný soubor, jehož jméno je odvozeno od jména původního skriptu (tedy v našem případě factorial). Jedná se o běžnou aplikaci, kterou lze přímo spustit:
[schemer ~]$ ./factorial 3628800
Zajímavé bude zjistit, jak je vlastně výsledný soubor velký a jaké má závislosti:
[schemer ~]$ ls -l factorial -rwxrwxr-x. 1 schemer schemer 51424 Dec 7 20:01 factorial
[schemer ~]$ ldd factorial
linux-vdso.so.1 (0x00007fff789ed000)
libchicken.so.8 => /lib64/libchicken.so.8 (0x00007f5c75db6000)
libm.so.6 => /lib64/libm.so.6 (0x00007f5c75c70000)
libdl.so.2 => /lib64/libdl.so.2 (0x00007f5c75c6a000)
libc.so.6 => /lib64/libc.so.6 (0x00007f5c75aa4000)
/lib64/ld-linux-x86-64.so.2 (0x00007f5c7623e000)
5. Možné problémy při překladu
Pokud jste nainstalovali Chicken Scheme ze standardního repositáře vaší linuxové distribuce, může se stát, že se překlad skriptu pro výpočet faktoriálu nezdaří a namísto vytvoření výsledného spustitelného souboru se pouze zobrazí chybové hlášení:
[schemer ~]$ csc factorial.scm sh: gcc: command not found Error: shell command terminated with non-zero exit status 32512: 'gcc' 'factorial.c' -o 'factorial.o' -c -fno-strict-aliasing -fwrapv -DHAVE_CHICKEN_CONFIG_H -DC_ENABLE_PTABLES -O2 -g -pipe -Werror=format-security -Wp– D_FORTIFY_SOURCE=2 -Wp– D_GLIBCXX_ASSERTIONS -fexceptions -fstack-protector-strong -grecord-gcc-switches -specs=/usr/lib/rpm/redhat/redhat-hardened-cc1 -specs=/usr/lib/rpm/redhat/redhat-annobin-cc1 -m64 -mtune=generic -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection -Wformat -Os -fomit-frame-pointer -I/usr/include/chicken
Napravení tohoto problému je snadné – postačuje nainstalovat gcc a vývojářskou verzi standardní céčkové knihovny.
6. Příprava jednoduchého benchmarku
Vzhledem k tomu, že je projekt Chicken Scheme vybaven plnohodnotným překladačem, bude užitečné zjistit, jak kvalitní kód tento překladač vlastně generuje. Připravíme si tedy jednoduchý benchmark, s nímž jsme se vlastně již seznámili v předchozích článcích. Jedná se o program určený pro iterativní výpočet konstanty π s využitím (velmi pomalu konvergujícího) Wallisova součinu (Wallis product, který je popsán například na stránce https://en.wikipedia.org/wiki/Wallis_product). Přepis tohoto algoritmu do Scheme může vypadat následovně:
(define (compute-pi n)
(let ((pi 4.0))
(do ((i 3 (+ i 2)))
((> i (+ n 2)))
(set! pi (* pi (/ (- i 1) i) (/ (+ i 1) i))))
pi))
(do ((n 1 (* n 2)))
((> n 10000000))
(display n)
(display " ")
(display (compute-pi n))
(newline))
7. Porovnání rychlosti interpretrů GNU Guile a Chicken Scheme
S projektem nazvaným GNU Guile jsme se již v tomto seriálu seznámili. Jedná se o interpret jazyka Scheme doplněný o JIT překladač, takže můžeme předpokládat, že by výpočetní výkon takto doplněného interpretru mohl být vyšší, než je tomu v případě jednoduchého interpretru dodávaného s projektem Chicken Scheme. Ostatně se o tomto předpokladu můžeme snadno přesvědčit, protože výše popsaný výpočet konstanty π je napsán takovým způsobem, že je kompatibilní jak s GNU Guile, tak i s Chicken Scheme.
Nejprve tedy výpočet spustíme v GNU Guile a budeme sledovat jak strojový čas strávený výpočtem, tak i celkový čas viditelný vnějším pozorovatelem (což je mnohdy důležitější ukazatel):
[schemer ~]$ time guile pi1.scm
Výsledky, na jejichž konci jsou zobrazeny i časové údaje:
1 3.5555555555555554 2 3.5555555555555554 4 3.4133333333333336 8 3.302393550012597 16 3.230036466411716 32 3.1881271694471383 64 3.1654820600347926 128 3.1536988490957967 256 3.147686899556418 512 3.1446501625172 1024 3.143124017028185 2048 3.142358989121772 4096 3.141975985005608 8192 3.1417843602347433 16384 3.1416885171495856 32768 3.1416405879293077 65536 3.1416166213993866 131072 3.1416046376544267 262144 3.1415986456618494 524288 3.141595649635512 1048576 3.141594151614876 2097152 3.141593402602468 4194304 3.1415930280955355 8388608 3.1415928408418403 real 0m4.858s user 0m5.212s sys 0m0.058s
Nyní si vyzkoušejme, jestli bude výpočet π podle stejného skriptu s využitím interpretru nástroje Chicken Scheme rychlejší nebo pomalejší. Použijeme přepínače -b a -q, které zajistí, že se interpret po dokončení výpočtů ihned ukončí a že se na začátku nebudou zobrazovat úvodní informace o projektu Chicken Scheme (což sice nevede k žádnému podstatnému urychlení, ale ke zpřesnění výsledných časů):
[schemer ~]$ time csi -b -q pi1.scm
Samotné výsledky výpočtu by měly být přibližně podobné, minimálně na prvních sedmi až osmi desetinných místech:
1 3.55555555555556 2 3.55555555555556 4 3.41333333333333 8 3.3023935500126 16 3.23003646641172 32 3.18812716944714 64 3.16548206003479 128 3.1536988490958 256 3.14768689955642 512 3.1446501625172 1024 3.14312401702818 2048 3.14235898912177 4096 3.14197598500561 8192 3.14178436023474 16384 3.14168851714959 32768 3.14164058792931 65536 3.14161662139939 131072 3.14160463765443 262144 3.14159864566185 524288 3.14159564963551 1048576 3.14159415161488 2097152 3.14159340260247 4194304 3.14159302809554 8388608 3.14159284084184 real 0m8.137s user 0m7.739s sys 0m0.318s
Čas celého výpočtu je v tomto případě výrazně delší, než tomu je v porovnání s projektem GNU Guile. Dále můžeme při porovnání všech tří časů předpokládat, že výpočet běžel pouze v jediném vláknu (což je ostatně pravda).
8. Rychlost benchmarku přeloženého do nativního kódu
Při porovnání předchozích časových údajů se může čtenář zajisté ptát, kde tedy spočívají přednosti Chicken Scheme oproti GNU Guile, když interpret je (alespoň v rámci jednoduchého a jednoúčelově zaměřeného benchmarku) pomalejší. Odpověď je zřejmá – tou je překladač. Budeme tedy muset benchmark nejdříve přeložit a otestovat, jak dlouho bude trvat výpočet provedený (přeloženým) nativním kódem.
Samotný překlad je jednoduchý a prakticky okamžitý:
[schemer ~]$ csc pi1.scm
Dále již budeme používat spustitelný soubor nazvaný „pi1“:
[schemer ~]$ time ./pi1
Se stejnými výsledky výpočtu, ovšem zcela odlišnými časy:
1 3.55555555555556 2 3.55555555555556 4 3.41333333333333 8 3.3023935500126 16 3.23003646641172 32 3.18812716944714 64 3.16548206003479 128 3.1536988490958 256 3.14768689955642 512 3.1446501625172 1024 3.14312401702818 2048 3.14235898912177 4096 3.14197598500561 8192 3.14178436023474 16384 3.14168851714959 32768 3.14164058792931 65536 3.14161662139939 131072 3.14160463765443 262144 3.14159864566185 524288 3.14159564963551 1048576 3.14159415161488 2097152 3.14159340260247 4194304 3.14159302809554 8388608 3.14159284084184 real 0m0.885s user 0m0.869s sys 0m0.011s
Nyní tedy celý výpočet trval pouze přibližně 0,89 sekundy, což je oproti interpretaci (více než 8 sekund) prakticky řádový rozdíl!
9. Porovnání kvality překladače Chicken Scheme s alternativními implementacemi vytvořenými v C a Go
Překladač Chicken Scheme tedy skutečně dokáže odvést poměrně velmi dobrou práci, minimálně v porovnání s klasickými interpretry popř. interpretry dovybavenými JIT překladačem. Ovšem jak dobrý či naopak špatný je tento překladač v porovnání s podobně naprogramovaným algoritmem v čistém céčku? Na tomto místě můžeme předpokládat, že Chicken Scheme bude produkovat horší kód (už jen kvůli neexistenci explicitního typového systému, resp. prozatím jsme tento systém nevyužili), ovšem musíme se o tomto předpokladu přesvědčit.
V céčku může obdobný výpočet konstanty π vypadat následovně (jedná se o prakticky doslovný přepis předchozího skriptu):
#include <stdio.h>
double compute_pi(int n) {
double pi = 4.0;
long i;
for (i = 3; i <= n + 2; i += 2) {
pi = pi * (i-1)/i * (i+1)/i;
}
return pi;
}
int main(void) {
long n;
for (n=1; n <= 10000000; n *= 2) {
printf("%ld %16.14f\n", n, compute_pi(n));
}
return 0;
}
Výsledky pro neoptimalizovaný kód:
[schemer ~]$ gcc -Wall -ansi pi.c [schemer ~]$ time ./a.out 1 3.55555555555556 2 3.55555555555556 4 3.41333333333333 8 3.30239355001260 16 3.23003646641172 32 3.18812716944714 64 3.16548206003480 128 3.15369884909580 256 3.14768689955642 512 3.14465016251721 1024 3.14312401702820 2048 3.14235898912179 4096 3.14197598500563 8192 3.14178436023478 16384 3.14168851714965 32768 3.14164058792947 65536 3.14161662139959 131072 3.14160463765471 262144 3.14159864566229 524288 3.14159564963532 1048576 3.14159415161453 2097152 3.14159340260678 4194304 3.14159302810327 8388608 3.14159284083911 real 0m0.157s user 0m0.154s sys 0m0.002s
Zde je urychlení cca 5,5násobné oproti výsledku překladače Chicken Scheme!
Překlad se základními optimalizacemi:
[schemer ~]$ gcc -Wall -ansi -O3 pi1.c [schemer ~]$ time ./a.out 1 3.55555555555556 2 3.55555555555556 4 3.41333333333333 8 3.30239355001260 16 3.23003646641172 32 3.18812716944714 64 3.16548206003480 128 3.15369884909580 256 3.14768689955642 512 3.14465016251721 1024 3.14312401702820 2048 3.14235898912179 4096 3.14197598500563 8192 3.14178436023478 16384 3.14168851714965 32768 3.14164058792947 65536 3.14161662139959 131072 3.14160463765471 262144 3.14159864566229 524288 3.14159564963532 1048576 3.14159415161453 2097152 3.14159340260678 4194304 3.14159302810327 8388608 3.14159284083911 real 0m0.128s user 0m0.126s sys 0m0.001s
Je patrné, že jsme dosáhli ještě dalšího urychlení, i když již nikoli několikanásobného, jako tomu bylo při přechodu na C.
Pro zajímavost si ještě vyzkoušejme podobný algoritmus napsaný v programovacím jazyku Go. Nejdříve použijeme naivní přístup pracující v jednom vláknu (tj. stejný přístup, jako ve Scheme a jazyku C):
package main
import "fmt"
func computePi(n int) float64 {
pi := 4.0
var i int
for i = 3; i <= n+2; i += 2 {
fi := float64(i)
pi = pi * (fi - 1) / fi * (fi + 1) / fi
}
return pi
}
func main() {
var n int
for n = 1; n <= 10000000; n *= 2 {
fmt.Printf("%d %16.14f\n", n, computePi(n))
}
}
S výsledky benchmarku:
[schemer ~]$ go build pi1.go [schemer ~]$ time ./pi1 1 3.55555555555556 2 3.55555555555556 4 3.41333333333333 8 3.30239355001260 16 3.23003646641172 32 3.18812716944714 64 3.16548206003480 128 3.15369884909580 256 3.14768689955642 512 3.14465016251721 1024 3.14312401702820 2048 3.14235898912179 4096 3.14197598500563 8192 3.14178436023478 16384 3.14168851714965 32768 3.14164058792947 65536 3.14161662139959 131072 3.14160463765471 262144 3.14159864566229 524288 3.14159564963532 1048576 3.14159415161453 2097152 3.14159340260678 4194304 3.14159302810327 8388608 3.14159284083911 real 0m0.143s user 0m0.136s sys 0m0.005s
Výkonnější by mohl být algoritmus převedený do takové podoby, kdy se konstanta π získaná ze zadaného počtu prvků nějaké řady vypočítá v samostatné gorutině:
package main
import "fmt"
func computePi(n int, results chan<- float64) {
pi := 4.0
var i int
for i = 3; i <= n+2; i += 2 {
fi := float64(i)
pi = pi * (fi - 1) / fi * (fi + 1) / fi
}
results <- pi
}
func main() {
var results [30]chan float64
// inicializace kanálů
for i := range results {
results[i] = make(chan float64)
}
// výpočet v gorutinách
for i, n := 0, 1; n <= 10000000; i, n = i+1, n*2 {
go computePi(n, results[i])
}
// čekání na dokončení gorutin
for i, n := 0, 1; n <= 10000000; i, n = i+1, n*2 {
fmt.Printf("%d %16.14f\n", n, <-results[i])
}
}
Nyní budou výsledky odlišné:
[schemer ~]$ go build pi2.go [schemer ~]$ time ./pi2 1 3.55555555555556 2 3.55555555555556 4 3.41333333333333 8 3.30239355001260 16 3.23003646641172 32 3.18812716944714 64 3.16548206003480 128 3.15369884909580 256 3.14768689955642 512 3.14465016251721 1024 3.14312401702820 2048 3.14235898912179 4096 3.14197598500563 8192 3.14178436023478 16384 3.14168851714965 32768 3.14164058792947 65536 3.14161662139959 131072 3.14160463765471 262144 3.14159864566229 524288 3.14159564963532 1048576 3.14159415161453 2097152 3.14159340260678 4194304 3.14159302810327 8388608 3.14159284083911 real 0m0.078s user 0m0.138s sys 0m0.008s
Tento výpočet z hlediska mikroprocesoru sice trval prakticky stejně dlouho, jako výpočet předchozí, ovšem z pohledu uživatele byl proveden v prakticky polovičním čase. To přesně odpovídá použití gorutin, kdy je celkový čas zdola omezen poslední gorutinou, která vlastně provádí více výpočtů, než všechny ostatní gorutiny dohromady.
10. Typové informace a jejich vliv na výsledek benchmarku
Dalšího vylepšení času výpočtu je možné dosáhnout přidáním typových informací do zdrojového kódu vytvořeného v jazyku Scheme. Chicken Scheme umožňuje specifikovat typ globálních symbolů tímto zápisem:
(: symbol typ)
V případě funkcí pak zápisem:
(: symbol (typy na vstupu -> typ návratové hodnoty)
Dále je možné explicitně zadat typ hodnoty přiřazené k lokálnímu symbolu, a to s využitím speciální formy the, které se předá datový typ a hodnota či výraz. Například:
(let ((pi (the float 4.0)))
...
...
...)
Předchozí výpočet tedy můžeme poněkud nešikovně přepsat takto:
(: compute-pi (fixnum -> float))
(define (compute-pi n)
(let ((pi (the float 4.0)))
(do ((i (the fixnum 3) (+ i 2)))
((> i (+ n 2)))
(set! pi (* pi (/ (- i 1) i) (/ (+ i 1) i))))
pi))
(do ((n 1 (* n 2)))
((> n 10000000))
(display n)
(display " ")
(display (compute-pi n))
(newline))
11. Výsledky všech benchmarků v grafické podobě
Výsledky předchozích benchmarků si můžeme zobrazit i v grafické podobě:
Obrázek 5: Výsledky benchmarků v grafické podobě.
Obrázek 6: Porovnání rychlostí výpočtu různých implementací jazyka Scheme..
12. Další vlastnosti programovacího jazyka implementovaného v rámci Chicken Scheme
Většina základních vlastností programovacího jazyka implementovaného v rámci Chicken Scheme je odvozena z R5RS a částečně i z novějších vydání RnRS. Týká se to především samotné sémantiky programovacího jazyka, ovšem s tím, že některé funkce, které jsou v ostatních implementacích Scheme běžně dostupné, je v Chicken Scheme zapotřebí explicitně importovat. Týká se to například i tak základních funkcí, jakými jsou funkce vyššího řádu map či filter. Ty jsou dostupné v balíčku nazvaném srfi-1 a před jejich použitím je nutné použít volání:
(use srfi-1)
popř.:
(import srfi-1)
Podobně jako je tomu i v dalších implementacích Scheme je i v Chicken Scheme základním strukturovaným datovým typem seznam (list) doplněný o základní funkce pro práci s ním. Z LISPu byly převzaty funkce car a cdr i jejich další varianty (cadr, cdar atd.):
; helper function
(define (println item)
(display item)
(newline))
(println '(1 2 3 4))
(println (list 1 2 3 4))
; create list and assign it to symbol
; (=variable)
(define a '(1 2 3 4))
; get the first item
(println (car a))
; get the rest of a list
(println (cdr a))
; combination of car+cdr
(println (cadr a))
; combination of cdr+cdr
(println (cddr a))
S výsledky:
(1 2 3 4) (1 2 3 4) 1 (2 3 4) 2 (3 4)
Interně jsou seznamy reprezentovány prvky, přičemž každý prvek je tvořen takzvanou tečka-dvojicí, kterou si můžeme představit jako strukturu obsahující dvě hodnoty – buď ukazatel na další tečka-dvojici nebo hodnotu (včetně prázdné hodnoty):
; helper function
(define (println item)
(display item)
(newline))
; simple dot-pair
(println '(1 . 2))
(println '(1 . ((2 . 3) . 4)))
(println '((1 . 2) . (3 . 4)))
; this is proper list in LISP, but not in Scheme!
(println '(1 . (2 . (3 . nil))))
; this is proper list
(println '(1 . (2 . (3 . ()))))
Výsledky získané spuštěním tohoto skriptu:
(1 . 2) (1 (2 . 3) . 4) ((1 . 2) 3 . 4) (1 2 3 . nil) (1 2 3)
Seznamy je možné konstruovat i s využitím funkce cons:
(define (print item)
(display item)
(newline))
(print (cons 1 2))
(print (cons 1 (cons 2 3)))
(print '((1 . 2) . (3 . 4)))
; this is proper list
(print (cons 1 (cons 2 (cons 3 '()))))
(define nil '())
; this is proper list
(print (cons 1 (cons 2 (cons 3 nil))))
S výsledky:
(1 . 2) (1 2 . 3) ((1 . 2) 3 . 4) (1 2 3) (1 2 3)
13. Funkce a speciální formy
Podobně jako u každého dialektu programovacího jazyka LISP, i v případě Scheme 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í speciální formy define, za níž v závorkách následuje jméno funkce. Každá funkce může mít libovolný počet parametrů, jejichž jména se uvádí v seznamu ihned za pojmenováním funkce. Poslední částí formy define je v tomto případě 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 s podobným významem):
; one-liner function (define (add x y) (+ x y)) ; function written on more lines (define (mul x y) (* x y))
; function written on more lines using lambda (define div (lambda (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:
(print (add 1 2)) (print (mul 6 7)) (print (div 10 3))
Kromě pojmenovaných funkcí, které jsme si již představili v předchozím textu, je možné ve Scheme použít i funkce anonymní, tj. funkce, které nejsou navázány na žádné jméno. Pro tento účel se používá přímo lambda výraz (bez define), podobně jako v každém ortodoxním Lispu (snad kromě PicoLispu):
; anonymous function is a value (lambda (x y) (+ x y)) ; call anonymous function (print (lambda (x y) (+ x y)))
Další důležitou vlastností jazyka implementovaného v Chicken Scheme, s níž se dnes (znovu) seznámíme, je použití takzvaných speciálních forem. Ze syntaktického hlediska jsou speciální formy zapisovány naprosto stejným způsobem jako běžné funkce, ovšem existuje zde jeden významný rozdíl – zatímco u funkcí jsou všechny jejich parametry nejdříve vyhodnoceny, u speciálních forem k tomuto vyhodnocení obecně nedochází, resp. jsou vyhodnoceny pouze některé parametry (které konkrétně, to závisí na tom, o jakou speciální formu se jedná). S některými speciálními formami jsme se již setkali, především s formou define či let, ovšem existují i formy další – cond, if, and, lambda, quote, do atd.
14. Koncová rekurze
V naprosté většině algoritmů se objevují bloky kódu, které se mají iterativně opakovat. Při programování s využitím funkcionálního paradigmatu se iterace vyjadřuje formou rekurze. Ta je samozřejmě ve Scheme podporována (mezi jediné známější jazyky, které rekurzi nepodporovaly, patřil původní FORTRAN a Basic), ovšem specifikace jazyka Scheme jde ještě dále, protože určuje, ve kterých případech je skutečná rekurze (při níž se parametry a návratové adresy musí ukládat na zásobník) nahrazena takzvanou koncovou rekurzí, což zjednodušeně řečeno znamená, že se namísto skutečného rekurzivního volání funkce interně provede obyčejný skok (koncový skok či koncové volání) bez nutnosti alokace místa na zásobníku pro parametry volané funkce a návratové adresy.
Koncová rekurze představuje při správném použití velmi silnou programovací techniku, protože umožňuje zapisovat mnoho algoritmů v mnohdy elegantní rekurzivní formě, ovšem skutečné zpracování takto zapsaných algoritmů je stejně efektivní jako provádění programové smyčky (každou koncovou rekurzi lze nahradit smyčkou a naopak).
Klasickým příkladem rozdílu mezi normální (plnou, skutečnou) rekurzí a koncovou rekurzí je výpočet faktoriálu. Ten můžeme zapsat mnoha způsoby, například (jak je to v matematice obvyklé), rekurzivně:
(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)))))
Z teoretického hlediska není na výše uvedené funkci nic nekorektního, ovšem při jejím praktickém používání brzy narazíme na limit způsobený omezenou velikostí zásobníku.
Výše uvedený rekurzivní výpočet lze relativně malou úpravou převést na výpočet který (alespoň v programovacím jazyce Scheme) vede na koncové volání, což mj. znamená, že paměťové (prostorové) nároky tohoto programu jsou konstantní:
; výpočet faktoriálu využívající koncového volání
(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í
)))
15. Lokální rozsah proměnných
Jazyk Scheme je, na rozdíl od původních LISPů, založen na lokálním rozsahu proměnných (local scope). Můžeme si to ukázat na následujícím demonstračním příkladu, v němž je uvnitř funkce add použit lokální rozsah, v rámci něhož je vyhodnocována proměnná x:
(define x 1)
(define y 2)
(define (add x y)
; rozsah (scope) je lokální!
(set! x (+ x y))
x)
(print (add x y))
(print (add x y))
(set! x 10)
(print (add x y))
(print (add x y))
Po spuštění tohoto příkladu se vypíše:
3 3 12 12
Příklad s globálními a lokálními proměnnými:
(define x 1)
(define y 2)
(define (add x y)
(+ x y))
(print (add x y))
(print
(let ((x 10)
(y 20))
(add x y)))
(set! x 10)
(print (add x y))
(print
(let ((x 10)
(y 20))
(add x y)))
(print
(let ((x 100))
(add x y)))
Po spuštění tohoto příkladu se vypíše:
3 30 12 30 102
(define (larger-than limit)
(lambda (value) (> value limit)))
(print ((larger-than 5) 0))
(print ((larger-than 5) 10))
(print (filter (larger-than 5) '(1 2 3 4 5 6 7 8 9 10)))
S těmito výsledky:
#f #t (6 7 8 9 10) (6 7 8 9 10)
Další, nepatrně složitější implementace uzávěrů:
(use srfi-1)
(define (print item)
(display item)
(newline))
(define counter
(let ((i -1))
(lambda ()
(set! i (+ i 1))
i)))
(print (counter))
(print (counter))
(print (counter))
S výsledky:
0 1 2
(use srfi-1)
(define (print item)
(display item)
(newline))
(define (get-counter)
(let ((i -1))
(lambda ()
(set! i (+ i 1))
i)))
(define counter1 (get-counter))
(define counter2 (get-counter))
(print (counter1))
(print (counter1))
(print (counter1))
(print (counter2))
(print (counter2))
(print (counter2))
(print (counter1))
(print (counter1))
(print (counter1))
Výsledky činnosti dvou čítačů:
0 1 2 0 1 2 3 4 5
16. FFI – rozhraní mezi Chicken Scheme a nativními jazyky (C apod.)
V ekosystému jazyka Chicken Scheme nalezneme hned několik implementací FFI neboli Foreign Function Interface. Jedno z těchto rozšíření se jmenuje přiléhavě – The „Easy“ Foreign Function Interface. Použití FFI, tedy zavolání nativní céčkové funkce, je s využitím tohoto rozšíření mnohdy velmi triviální. Pokud například potřebujeme zavolat standardní funkci getchar, jejíž deklaraci najdeme v hlavičkovém souboru stdio.h, stačí napsat:
(foreign-declare " #include <stdio.h> ") (foreign-parse "extern int getchar(void);")
Poté je možné tuto funkci zavolat, jakoby se jednalo o běžnou funkci či speciální formu deklarovanou přímo ve Scheme:
(print (getchar))
Podobné je to v případě funkce akceptující parametr nějakého (céčkového) typu:
(foreign-declare " #include <math.h> ") (foreign-parse "extern double fabs(double);") (print (fabs -10))
V případě, že se použijí funkce, které nejsou dostupné ve standardní knihovně, je nutné příslušnou externí knihovnu či objektový soubor správně slinkovat:
$ csc -X easyffi ffi-test.scm soubor.o
Především při použití nestandardních knihoven je někdy nutné předat další parametry překladači céčka a/nebo linkeru, typicky s cestou ke hlavičkovým souborům a cestou ke knihovně, která se má slinkovat s vygenerovaným kódem do výsledného spustitelného souboru:
$ csc -X easyffi ffi-test.scm soubor.o -C -Iinclude_directory -L "-llinovaná_knihovna"
17. Předchozí části seriálu
V této kapitole jsou uvedeny odkazy na všechny předchozí části seriálu o světě programovacích jazyků LISP a Scheme:
- Jemný úvod do rozsáhlého světa jazyků LISP a Scheme
https://www.root.cz/clanky/jemny-uvod-do-rozsahleho-sveta-jazyku-lisp-a-scheme/ - PicoLisp: minimalistický a přitom překvapivě výkonný interpret Lispu
https://www.root.cz/clanky/picolisp-minimalisticky-a-pritom-prekvapive-vykonny-interpret-lispu/ - PicoLisp: užitečné funkce a speciální formy používané při tvorbě aplikací
https://www.root.cz/clanky/picolisp-uzitecne-funkce-a-specialni-formy-pouzivane-pri-tvorbe-aplikaci/ - PicoLisp: dokončení popisu a několik praktických rad na závěr
https://www.root.cz/clanky/picolisp-dokonceni-popisu-a-nekolik-praktickych-rad-na-zaver/ - GNU Guile – interpret Scheme vestavitelný do nativních aplikací
https://www.root.cz/clanky/gnu-guile-interpret-scheme-vestavitelny-do-nativnich-aplikaci/ - TinyScheme aneb další interpret jazyka Scheme vestavitelný do dalších aplikací
https://www.root.cz/clanky/tinyscheme-aneb-dalsi-interpret-jazyka-scheme-vestavitelny-do-dalsich-aplikaci/ - Kawa: překvapivě silný a výkonný dialekt Scheme pro JVM
https://www.root.cz/clanky/kawa-prekvapive-silny-a-vykonny-dialekt-scheme-pro-jvm/ - Jazyk Kawa v ekosystému virtuálního stroje Javy
https://www.root.cz/clanky/jazyk-kawa-v-ekosystemu-virtualniho-stroje-javy/ - Zpracování vektorů, matic a N-rozměrných polí v programovacím jazyku Kawa
https://www.root.cz/clanky/zpracovani-vektoru-matic-a-n-rozmernych-poli-v-programovacim-jazyku-kawa/ - Racket: programovací jazyk a současně i platforma pro vývoj nových jazyků
https://www.root.cz/clanky/racket-programovaci-jazyk-a-soucasne-i-platforma-pro-vyvoj-novych-jazyku/ - Makra v Racketu i v dalších lispovských jazycích
https://www.root.cz/clanky/makra-v-racketu-i-v-dalsich-lispovskych-jazycich/ - Základní knihovna jazyka Racket
https://www.root.cz/clanky/zakladni-knihovna-jazyka-racket/ - Jazyk Joker: dialekt Clojure naprogramovaný v Go
https://www.root.cz/clanky/jazyk-joker-dialekt-clojure-naprogramovany-v-go/
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:
19. Literatura
Sbírka dnes již klasických knih o programovacích jazycích LISP a Scheme:
- Peter Seibel
„Practical Common Lisp“
2009 - Paul Graham
„ANSI Common Lisp“
1995 - Gerald Gazdar
„Natural Language Processing in Lisp: An Introduction to Computational Linguistics“
1989 - Peter Norvig
„Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp“
1991 - Alex Mileler et.al.
„Clojure Applied: From Practice to Practitioner“
2015 - „Living Clojure: An Introduction and Training Plan for Developers“
2015 - Dmitri Sotnikov
„Web Development with Clojure: Build Bulletproof Web Apps with Less Code“
2016 - McCarthy
„Recursive functions of symbolic expressions and their computation by machine, part I“
1960 - R. Kent Dybvig
„The Scheme Programming Language“
2009 - Max Hailperin
„Concrete Abstractions“
1998 - Guy L. Steele
„History of Scheme“
2006, Sun Microsystems Laboratories - Kolář J., Muller K.:
„Speciální programovací jazyky“
Praha 1981 - „AutoLISP Release 9, Programmer's reference“
Autodesk Ltd., October 1987 - „AutoLISP Release 10, Programmer's reference“
Autodesk Ltd., September 1988 - McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I.
„LISP 1.5 Programmer's Manual“
MIT Press. ISBN 0 262 130 1 1 4 - Carl Hewitt; Peter Bishop and Richard Steiger
„A Universal Modular Actor Formalism for Artificial Intelligence“
1973 - Feiman, J.
„The Gartner Programming Language Survey (October 2001)“
Gartner Advisory - 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) - Paul Graham
On Lisp
Prentice Hall, 1993
Dostupné online na stránce http://www.paulgraham.com/onlisptext.html - David S. Touretzky
Common LISP: A Gentle Introduction to Symbolic Computation (Dover Books on Engineering)
- Peter Norvig
Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp - Patrick Winston, Berthold Horn
Lisp (3rd Edition)
ISBN-13: 978–0201083194, ISBN-10: 0201083191 - 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 - Graham Hutton
A tutorial on the universality andexpressiveness of fold
http://www.cs.nott.ac.uk/~pszgmh/fold.pdf
20. Odkazy na Internetu
- Chicken Scheme
https://call-cc.org/ - Eggs Unlimited
http://wiki.call-cc.org/chicken-projects/egg-index-5.html - Chicken Scheme Wiki
https://wiki.call-cc.org/ - CHICKEN for Python programmers
https://wiki.call-cc.org/chicken-for-python-programmers - Programming for Performance
http://wiki.call-cc.org/programming-for-performance - Using the compiler
https://wiki.call-cc.org/man/4/Using%20the%20compiler - CHICKEN Scheme tutorials
https://wiki.call-cc.org/tutorials - Racket: programovací jazyk a současně i platforma pro vývoj nových jazyků
https://www.root.cz/clanky/racket-programovaci-jazyk-a-soucasne-i-platforma-pro-vyvoj-novych-jazyku/ - Makra v Racketu i v dalších lispovských jazycích
https://www.root.cz/clanky/makra-v-racketu-i-v-dalsich-lispovskych-jazycich/ - Základní knihovna jazyka Racket
https://www.root.cz/clanky/zakladni-knihovna-jazyka-racket/ - Grafický metaformát PostScript
https://www.root.cz/clanky/graficky-metaformat-postscript/ - Vektorový grafický formát SVG
https://www.root.cz/clanky/vektorovy-graficky-format-svg/ - The Racket Drawing Toolkit
https://docs.racket-lang.org/draw/index.html - Traditional Turtles
https://docs.racket-lang.org/turtles/Traditional_Turtles.html - [racket] How best to repeat a function call n times?
https://lists.racket-lang.org/users/archive/2014-September/064203.html - Racket: Macros
https://www.it.uu.se/edu/course/homepage/avfunpro/ht13/lectures/Racket-3-Macros.pdf - Beautiful Racket / explainers: Macros
https://beautifulracket.com/explainer/macros.html - Macros (dokumentace k Racketu)
https://docs.racket-lang.org/guide/macros.html - Model syntaxe jazyka Racket
https://docs.racket-lang.org/reference/syntax-model.html - Syntax Objects
https://docs.racket-lang.org/guide/stx-obj.html - Tech behind Tech: Clojure Macros Simplified
http://techbehindtech.com/2010/09/28/clojure-macros-simplified/ - Fatvat – Exploring functional programming: Clojure Macros
http://www.fatvat.co.uk/2009/02/clojure-macros.html - Beautiful Racket: an introduction to language-oriented programming using Racket
https://beautifulracket.com/ - Stránky projektu Racket
https://racket-lang.org/ - Dokumentace k projektu Racket
https://docs.racket-lang.org/index.html - Seznam dostupných balíčků pro Racket
https://pkgs.racket-lang.org/ - Racket na Wikipedii
https://en.wikipedia.org/wiki/Racket_(programming_language) - Blogy o Racketu a navazujících technologiích
https://blog.racket-lang.org/ - Prográmky psané v Racketu na RosettaCode
http://rosettacode.org/wiki/Category:Racket - Fear of Macros
https://www.greghendershott.com/fear-of-macros/ - Rackjure
https://github.com/greghendershott/rackjure - Matthew Flatt’s proposal to change Racket’s s-expressions based syntax to infix representation creates a stir in the community
https://hub.packtpub.com/matthew-flatts-proposal-to-change-rackets-s-expressions-based-syntax-to-infix-representation-creates-a-stir-in-the-community/ - Racket News
https://racket-news.com/ - Racket: Lisp for learning
https://lwn.net/Articles/795385/ - Future of Racket
https://www.greghendershott.com/2019/07/future-of-racket.html - Kawa: Compiling Scheme to Java
https://www.mit.edu/afs.new/sipb/project/kawa/doc/kawa-tour.html - Kawa in Languages shootout
http://per.bothner.com/blog/2010/Kawa-in-shootout/ - Kawa 2.0 Supports Scheme R7RS
https://developers.slashdot.org/story/14/12/13/2259225/kawa-20-supports-scheme-r7rs/ - Kawa — fast scripting on the Java platform
https://lwn.net/Articles/623349/ - Tail call (a její optimalizace)
https://en.wikipedia.org/wiki/Tail_call - SLIME (Wikipedia)
http://en.wikipedia.org/wiki/SLIME - slime.vim
http://s3.amazonaws.com/mps/slime.vim - What are the best scheme implementations?
https://www.slant.co/topics/5282/~scheme-implementations - Bigloo homepage
http://www-sop.inria.fr/mimosa/fp/Bigloo/ - FTP s tarbally Bigloo
ftp://ftp-sop.inria.fr/indes/fp/Bigloo - GOTO 2018 • Functional Programming in 40 Minutes • Russ Olsen
https://www.youtube.com/watch?v=0if71HOyVjY - TinyScheme (stránka na Sourceforge)
http://tinyscheme.sourceforge.net/home.html - Embedding Tiny Scheme in a Game
http://www.silicondelight.com/embedding-tiny-scheme-in-a-game/ - Embedding Scheme for a game mission scripting DSL
http://carloscarrasco.com/embedding-scheme-for-a-game-mission-scripting-dsl.html - Všechny verze TinyScheme na SourceForge
https://sourceforge.net/projects/tinyscheme/files/tinyscheme/ - Fork TinyScheme na GitHubu
https://github.com/yawnt/tinyscheme - Ackermannova funkce
https://cs.wikipedia.org/wiki/Ackermannova_funkce - Ackermann function na Rosetta Code
https://rosettacode.org/wiki/Ackermann_function#Scheme - Success Stories (lisp.org)
https://lisp-lang.org/success/ - Allegro Common Lisp Success Stories
https://franz.com/success/ - Clojure Success Stories
https://clojure.org/community/success_stories - Scheme Quick Reference
https://www.st.cs.uni-saarland.de/edu/config-ss04/scheme-quickref.pdf - Slajdy o Scheme (od slajdu číslo 15)
https://docs.google.com/presentation/d/1abmDnKjrq1tcjGvvRNAKhOiSTSE2lyagtcEPal07Gbo/edit - Scheme Cheat Sheet
https://github.com/smythp/scheme-cheat-sheet - Embedding Lua, embedding Guile
http://puntoblogspot.blogspot.com/2013/04/embedding-lua-embedding-guile.html - Lambda Papers
https://en.wikisource.org/wiki/Lambda_Papers - Revised7Report on the Algorithmic Language Scheme
https://small.r7rs.org/attachment/r7rs.pdf - 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/ - Why is Scheme my first language in university?
https://softwareengineering.stackexchange.com/questions/115252/why-is-scheme-my-first-language-in-university - The Perils of JavaSchools
https://www.joelonsoftware.com/2005/12/29/the-perils-of-javaschools-2/ - How to Design Programs, Second Edition
https://htdp.org/2019–02–24/index.html - LilyPond
http://lilypond.org/ - LilyPond — Extending (přes Scheme)
http://lilypond.org/doc/v2.18/Documentation/extending/scheme-tutorial - Scheme in LilyPond
http://lilypond.org/doc/v2.18/Documentation/extending/scheme-in-lilypond - GnuCash
http://www.gnucash.org/ - Custom Reports (in GNU Cash)
https://wiki.gnucash.org/wiki/Custom_Reports - Program by Design
https://programbydesign.org/ - SchemePy
https://pypi.org/project/SchemePy/ - 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 - femtolisp
https://github.com/JeffBezanson/femtolisp - (How to Write a (Lisp) Interpreter (in Python))
http://norvig.com/lispy.html - Repositář s Guile Emacsem
http://git.hcoop.net/?p=bpt/guile.git - Interacting with Guile Compound Data Types in C
http://www.lonelycactus.com/guilebook/x1555.html - Calling Guile functions from C
http://www.lonelycactus.com/guilebook/c1204.html#SECCALLGUILEFUNC - Arrays, and other compound data types
http://www.lonelycactus.com/guilebook/charrays.html - Interacting with Guile Compound Data Types in C
http://www.lonelycactus.com/guilebook/x1555.html - Guile Reference Manual
https://www.gnu.org/software/guile/manual/html_node/index.html - Scheme: Summary of Common Syntax
https://www.gnu.org/software/guile/manual/html_node/Syntax-Summary.html#Syntax-Summary - Scripting with Guile: Extension language enhances C and Scheme
https://www.ibm.com/developerworks/library/l-guile/index.html - Having fun with Guile: a tutorial
http://dustycloud.org/misc/guile-tutorial.html - Guile: Loading Readline Support
https://www.gnu.org/software/guile/manual/html_node/Loading-Readline-Support.html#Loading-Readline-Support - lispy
https://pypi.org/project/lispy/ - Lython
https://pypi.org/project/Lython/ - Lizpop
https://pypi.org/project/lizpop/ - Budoucnost programovacích jazyků
http://www.knesl.com/budoucnost-programovacich-jazyku - LISP Prolog and Evolution
http://blog.samibadawi.com/2013/05/lisp-prolog-and-evolution.html - List of Lisp-family programming languages
https://en.wikipedia.org/wiki/List_of_Lisp-family_programming_languages - clojure_py na indexu PyPi
https://pypi.python.org/pypi/clojure_py - PyClojure
https://github.com/eigenhombre/PyClojure - Hy na GitHubu
https://github.com/hylang/hy - Hy: The survival guide
https://notes.pault.ag/hy-survival-guide/ - Hy běžící na monitoru terminálu společnosti Symbolics
http://try-hy.appspot.com/ - Welcome to Hy’s documentation!
http://docs.hylang.org/en/stable/ - Hy na PyPi
https://pypi.org/project/hy/#description - Getting Hy on Python
https://lwn.net/Articles/596626/ - Programming Can Be Fun with Hy
https://opensourceforu.com/2014/02/programming-can-fun-hy/ - Přednáška o projektu Hy (pětiminutový lighttalk)
http://blog.pault.ag/day/2013/04/02 - Hy (Wikipedia)
https://en.wikipedia.org/wiki/Hy - GNU Emacs Lisp Reference Manual: Point
https://www.gnu.org/software/emacs/manual/html_node/elisp/Point.html - GNU Emacs Lisp Reference Manual: Narrowing
https://www.gnu.org/software/emacs/manual/html_node/elisp/Narrowing.html - GNU Emacs Lisp Reference Manual: Functions that Create Markers
https://www.gnu.org/software/emacs/manual/html_node/elisp/Creating-Markers.html - GNU Emacs Lisp Reference Manual: Motion
https://www.gnu.org/software/emacs/manual/html_node/elisp/Motion.html#Motion - GNU Emacs Lisp Reference Manual: Basic Char Syntax
https://www.gnu.org/software/emacs/manual/html_node/elisp/Basic-Char-Syntax.html - Elisp: Sequence: List, Array
http://ergoemacs.org/emacs/elisp_list_vs_vector.html - Elisp: Property List
http://ergoemacs.org/emacs/elisp_property_list.html - Elisp: Hash Table
http://ergoemacs.org/emacs/elisp_hash_table.html - Elisp: Association List
http://ergoemacs.org/emacs/elisp_association_list.html - The mapcar Function (An Introduction to Programming in Emacs Lisp)
https://www.gnu.org/software/emacs/manual/html_node/eintr/mapcar.html - Anaphoric macro
https://en.wikipedia.org/wiki/Anaphoric_macro - Some Common Lisp Loop Macro Examples
https://www.youtube.com/watch?v=3yl8o6r_omw - A Guided Tour of Emacs
https://www.gnu.org/software/emacs/tour/ - The Roots of Lisp
http://www.paulgraham.com/rootsoflisp.html - Evil (Emacs Wiki)
https://www.emacswiki.org/emacs/Evil - Evil (na GitHubu)
https://github.com/emacs-evil/evil - Evil (na stránkách repositáře MELPA)
https://melpa.org/#/evil - Evil Mode: How I Switched From VIM to Emacs
https://blog.jakuba.net/2014/06/23/evil-mode-how-to-switch-from-vim-to-emacs.html - GNU Emacs (home page)
https://www.gnu.org/software/emacs/ - GNU Emacs (texteditors.org)
http://texteditors.org/cgi-bin/wiki.pl?GnuEmacs - An Introduction To Using GDB Under Emacs
http://tedlab.mit.edu/~dr/gdbintro.html - An Introduction to Programming in Emacs Lisp
https://www.gnu.org/software/emacs/manual/html_node/eintr/index.html - 27.6 Running Debuggers Under Emacs
https://www.gnu.org/software/emacs/manual/html_node/emacs/Debuggers.html - GdbMode
http://www.emacswiki.org/emacs/GdbMode - Emacs (Wikipedia)
https://en.wikipedia.org/wiki/Emacs - Emacs timeline
http://www.jwz.org/doc/emacs-timeline.html - Emacs Text Editors Family
http://texteditors.org/cgi-bin/wiki.pl?EmacsFamily - Vrapper aneb spojení možností Vimu a Eclipse
https://mojefedora.cz/vrapper-aneb-spojeni-moznosti-vimu-a-eclipse/ - 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/ - Emacs/Evil-mode – A basic reference to using evil mode in Emacs
http://www.aakarshnair.com/posts/emacs-evil-mode-cheatsheet - From Vim to Emacs+Evil chaotic migration guide
https://juanjoalvarez.net/es/detail/2014/sep/19/vim-emacsevil-chaotic-migration-guide/ - Introduction to evil-mode {video)
https://www.youtube.com/watch?v=PeVQwYUxYEg - EINE (Emacs Wiki)
http://www.emacswiki.org/emacs/EINE - EINE (Texteditors.org)
http://texteditors.org/cgi-bin/wiki.pl?EINE - ZWEI (Emacs Wiki)
http://www.emacswiki.org/emacs/ZWEI - ZWEI (Texteditors.org)
http://texteditors.org/cgi-bin/wiki.pl?ZWEI - Zmacs (Wikipedia)
https://en.wikipedia.org/wiki/Zmacs - Zmacs (Texteditors.org)
http://texteditors.org/cgi-bin/wiki.pl?Zmacs - TecoEmacs (Emacs Wiki)
http://www.emacswiki.org/emacs/TecoEmacs - Micro Emacs
http://www.emacswiki.org/emacs/MicroEmacs - Micro Emacs (Wikipedia)
https://en.wikipedia.org/wiki/MicroEMACS - EmacsHistory
http://www.emacswiki.org/emacs/EmacsHistory - Seznam editorů s ovládáním podobným Emacsu či kompatibilních s příkazy Emacsu
http://www.finseth.com/emacs.html - evil-numbers
https://github.com/cofi/evil-numbers - Debuggery a jejich nadstavby v Linuxu (1.část)
http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu/ - Debuggery a jejich nadstavby v Linuxu (2.část)
http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-2-cast/ - Debuggery a jejich nadstavby v Linuxu (3): Nemiver
http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-3-nemiver/ - Debuggery a jejich nadstavby v Linuxu (4): KDbg
http://fedora.cz/debuggery-a-jejich-nadstavby-v-linuxu-4-kdbg/ - 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/ - Org mode
https://orgmode.org/ - The Org Manual
https://orgmode.org/manual/index.html - Kakoune (modální textový editor)
http://kakoune.org/ - Vim-style keybinding in Emacs/Evil-mode
https://gist.github.com/troyp/6b4c9e1c8670200c04c16036805773d8 - Emacs – jak začít
http://www.abclinuxu.cz/clanky/navody/emacs-jak-zacit - Programovací jazyk LISP a LISP machines
https://www.root.cz/clanky/programovaci-jazyk-lisp-a-lisp-machines/ - Evil-surround
https://github.com/emacs-evil/evil-surround - Spacemacs
http://spacemacs.org/ - Lisp: Common Lisp, Racket, Clojure, Emacs Lisp
http://hyperpolyglot.org/lisp - Common Lisp, Scheme, Clojure, And Elisp Compared
http://irreal.org/blog/?p=725 - Does Elisp Suck?
http://irreal.org/blog/?p=675 - Emacs pro mírně pokročilé (9): Elisp
https://www.root.cz/clanky/emacs-elisp/ - If I want to learn lisp, are emacs and elisp a good choice?
https://www.reddit.com/r/emacs/comments/2m141y/if_i_want_to_learn_lisp_are_emacs_and_elisp_a/ - Clojure(Script) Interactive Development Environment that Rocks!
https://github.com/clojure-emacs/cider - An Introduction to Emacs Lisp
https://harryrschwartz.com/2014/04/08/an-introduction-to-emacs-lisp.html - Emergency Elisp
http://steve-yegge.blogspot.com/2008/01/emergency-elisp.html - Lambda calculus
https://en.wikipedia.org/wiki/Lambda_calculus - John McCarthy's original LISP paper from 1959
https://www.reddit.com/r/programming/comments/17lpz4/john_mccarthys_original_lisp_paper_from_1959/ - Micro Manual LISP
https://www.scribd.com/document/54050141/Micro-Manual-LISP - How Lisp Became God's Own Programming Language
https://twobithistory.org/2018/10/14/lisp.html - History of Lisp
http://jmc.stanford.edu/articles/lisp/lisp.pdf - The Roots of Lisp
http://languagelog.ldc.upenn.edu/myl/llog/jmc.pdf - Racket
https://racket-lang.org/ - The Racket Manifesto
http://felleisen.org/matthias/manifesto/ - MIT replaces Scheme with Python
https://www.johndcook.com/blog/2009/03/26/mit-replaces-scheme-with-python/ - Adventures in Advanced Symbolic Programming
http://groups.csail.mit.edu/mac/users/gjs/6.945/ - Why MIT Switched from Scheme to Python (2009)
https://news.ycombinator.com/item?id=14167453 - Starodávná stránka XLispu
http://www.xlisp.org/ - AutoLISP
https://en.wikipedia.org/wiki/AutoLISP - Seriál PicoLisp: minimalistický a výkonný interpret Lispu
https://www.root.cz/serialy/picolisp-minimalisticky-a-vykonny-interpret-lispu/ - Common Lisp
https://common-lisp.net/ - Getting Going with Common Lisp
https://cliki.net/Getting%20Started - Online Tutorial (Common Lisp)
https://cliki.net/online%20tutorial - Guile Emacs
https://www.emacswiki.org/emacs/GuileEmacs - Guile Emacs History
https://www.emacswiki.org/emacs/GuileEmacsHistory - Guile is a programming language
https://www.gnu.org/software/guile/ - MIT Scheme
http://groups.csail.mit.edu/mac/projects/scheme/ - SIOD: Scheme in One Defun
http://people.delphiforums.com/gjc//siod.html - CommonLispForEmacs
https://www.emacswiki.org/emacs/CommonLispForEmacs - Elisp: print, princ, prin1, format, message
http://ergoemacs.org/emacs/elisp_printing.html - Special Forms in Lisp
http://www.nhplace.com/kent/Papers/Special-Forms.html - Basic Building Blocks in LISP
https://www.tutorialspoint.com/lisp/lisp_basic_syntax.htm - Introduction to LISP – University of Pittsburgh
https://people.cs.pitt.edu/~milos/courses/cs2740/Lectures/LispTutorial.pdf - Why don't people use LISP
https://forums.freebsd.org/threads/why-dont-people-use-lisp.24572/ - Structured program theorem
https://en.wikipedia.org/wiki/Structured_program_theorem - Clojure: API Documentation
https://clojure.org/api/api - Tutorial for the Common Lisp Loop Macro
http://www.ai.sri.com/pkarp/loop.html - Common Lisp's Loop Macro Examples for Beginners
http://www.unixuser.org/~euske/doc/cl/loop.html - A modern list api for Emacs. No 'cl required.
https://github.com/magnars/dash.el - The LOOP Facility
http://www.lispworks.com/documentation/HyperSpec/Body/06_a.htm - Clojure.org: Vars and the Global Environment
http://clojure.org/Vars - Clojure.org: Refs and Transactions
http://clojure.org/Refs - Clojure.org: Atoms
http://clojure.org/Atoms - Clojure.org: Agents as Asynchronous Actions
http://clojure.org/agents - Transient Data Structureshttp://clojure.org/transients
- Dynamic Languages Strike Back
http://steve-yegge.blogspot.cz/2008/05/dynamic-languages-strike-back.html - Scripting: Higher Level Programming for the 21st Century
http://www.tcl.tk/doc/scripting.html - Clojure (na Wikipedia EN)
http://en.wikipedia.org/wiki/Clojure - Clojure (na Wikipedia CS)
http://cs.wikipedia.org/wiki/Clojure - SICP (The Structure and Interpretation of Computer Programs)
http://mitpress.mit.edu/sicp/ - Pure function
http://en.wikipedia.org/wiki/Pure_function - Funkcionální programování
http://cs.wikipedia.org/wiki/Funkcionální_programování - 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/ - Pixie: lehký skriptovací jazyk s „kouzelnými“ schopnostmi
https://www.root.cz/clanky/pixie-lehky-skriptovaci-jazyk-s-kouzelnymi-schopnostmi/ - Programovací jazyk Pixie: funkce ze základní knihovny a použití FFI
https://www.root.cz/clanky/programovaci-jazyk-pixie-funkce-ze-zakladni-knihovny-a-pouziti-ffi/ - Stránka projektu Jython
http://www.jython.org/ - Jython (Wikipedia)
https://en.wikipedia.org/wiki/Jython - Scripting for the Java Platform (Wikipedia)
https://en.wikipedia.org/wiki/Scripting_for_the_Java_Platform - JSR 223: Scripting for the JavaTM Platform
https://jcp.org/en/jsr/detail?id=223 - List of JVM languages
https://en.wikipedia.org/wiki/List_of_JVM_languages - The JavaTM Virtual Machine Specification, Second Edition
http://java.sun.com/docs/books/jvms/second_edition/html/VMSpecTOC.doc.html - The class File Format
http://java.sun.com/docs/books/jvms/second_edition/html/ClassFile.doc.html - javap – The Java Class File Disassembler
http://docs.oracle.com/javase/1.4.2/docs/tooldocs/windows/javap.html - javap-java-1.6.0-openjdk(1) – Linux man page
http://linux.die.net/man/1/javap-java-1.6.0-openjdk - Using javap
http://www.idevelopment.info/data/Programming/java/miscellaneous_java/Using_javap.html - Examine class files with the javap command
http://www.techrepublic.com/article/examine-class-files-with-the-javap-command/5815354
ČLÁNKY DO MAILU