Hlavní navigace

Jazyk Kawa v ekosystému virtuálního stroje Javy

Pavel Tišnovský

Ve druhém článku o nástroji Kawa, který nabízí interpret a současně i překladač jazyka Scheme běžícího v ekosystému JVM, si ukážeme, jakým způsobem dokáže překladač Kawa generovat výsledný bajtkód JVM.

Doba čtení: 43 minut

Sdílet

11. Optimalizace výpočtu faktoriálu přidáním typových informací

12. Výpočet faktoriálu používající numerické hodnoty typu long

13. Optimalizace výpočtu faktoriálu s využitím tail rekurze

14. Plně optimalizovaná varianta výpočtu faktoriálu

15. Obsah další části seriálu

16. Soubor Makefile určený pro překlad demonstračních skriptů do bajtkódu a pro jejich disassembling

17. Příloha: vybrané instrukce bajtkódu JVM

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

19. Literatura

20. Odkazy na Internetu

1. Kawa: interpret a současně i překladač programovacího jazyka Scheme do bajtkódu JVM

V předchozí části seriálu o lispovských programovacích jazycích jsme se seznámili s projektem nazvaným Kawa. Připomeňme si, že se jedná o interpret a současně i překladač programovacího jazyka Scheme určený pro ekosystém postavený okolo virtuálního stroje Javy (JVM – Java Virtual Machine). V současnosti neslouží JVM zdaleka pouze pro běh aplikací naprogramovaných přímo v Javě, protože pro JVM vzniklo i množství dalších programovacích jazyků a jejich dialektů. O těch nejdůležitějších a nejpoužívanějších jsme se zmínili minule na konci článku.

Mezi programovací jazyky používané pro běh nad virtuálním strojem Javy patří – což asi není příliš překvapující – i různé dialekty jazyků LISP a Scheme; pochopitelně ovšem nesmíme zapomenout na jeden z nejpopulárnějších lispovských jazyků současnosti – na jazyk Clojure. A mezi lispovské jazyky určené pro běh nad JVM patří i projekt Kawa. Dnes si řekneme, jakým způsobem je prováděn překlad skriptů psaných v dialektu Scheme do bajtkódu JVM. Přitom si ve stručnosti vysvětlíme princip bajtkódu i použité instrukce (samotné instrukce bajtkódu jsou velmi stabilní a kromě několika nových instrukcí typu invokedynamic zůstaly od dob Javy 1.0 prakticky nezměněny).

Poznámka: v dalším textu budeme často používat slovní spojení „spuštění bajtkódu“. Bajtkód určený pro virtuální stroj Javy pochopitelně nelze spustit přímo na mikroprocesoru, takže se „spuštěním bajtkódu“ v kontextu tohoto článku myslí inicializace běhového prostředí Javy (JRE – Java Runtime Environment), načtení bajtkódu z příslušného binárního souboru s koncovkou .class, nalezení bajtkódu statické metody main a začátek interpretace a/nebo JITování bajtkódu této metody (kromě toho se interně provádí i další operace, například kontrola sémantiky bajtkódu atd.).

2. Přímá interpretace versus okamžitý překlad do bajtkódu

Předchozí článek byl věnován především popisu některých význačných vlastností programovacího jazyka Scheme, resp. přesněji řečeno jeho dialektu implementovaného nástrojem Kawa. Mj. jsme si řekli, že přímo ve skriptech lze vytvářet instance javovských tříd, volat metody tímto způsobem zkonstruovaných objektů, vytvářet a používat rozhraní (interface) a pochopitelně taktéž pracovat s kolekcemi.

Jak je ovšem implementováno propojení jazyka Scheme s ekosystémem programovacího jazyka Java? Projekt Kawa nám sice nabízí klasickou interaktivní smyčku REPL (Read-Eval-Print-Loop), ovšem interpretace zapsaných výrazů (přesněji řečeno forem) není prováděna přímo. Namísto toho je daný výraz přeložen do bajtkódu JVM a teprve poté je tento bajtkód spuštěn ve virtuálním stroji Javy. Pokud se jedná o krátký bajtkód spouštěný jen několikrát (nebo dokonce jen jedinkrát), bude interpretován, při opakovaném spuštění pak „JITován“, tj. přeložen do optimalizovaného strojového kódu, jakoby se jednalo o běžný bajtkód vytvořený přímo překladačem javac.

Kromě výše zmíněného přímého překladu do bajtkódu, který je v Kawě nedílnou součástí interaktivní smyčky REPL (v jednoduchosti lze říci, že samotný překlad leží mezi operacemi read a eval), je však možné použít nástroj Kawa pro plnohodnotný překlad skriptů do bajtkódu JVM, přičemž výsledkem budou standardní soubory s koncovkou .class, které běžně vznikají překladačem javac, popř. jsou výsledkem činnosti dalších překladačů jiných programovacích jazyků určených pro JVM. S těmito soubory se pak zachází naprosto stejným způsobem, tj. lze je například zabalit do Java archivů, použit v projektech spravovaných Mavenem apod. My tyto soubory dnes využijeme dvojím způsobem – budeme je spouštět (v rámci JVM) a analyzovat standardním nástrojem javap.

3. Překlad skriptu typu „Hello world“ do bajtkódu s jeho následným spuštěním

Ukažme si nyní, jakým způsobem lze překlad do bajtkódu provést. Nejdříve si napíšeme ten nejjednodušší funkční skript, který je variantou na klasický céčkovský příklad „Hello world!“. Ve skriptu pouze voláme funkci display a předáváme jí řetězec, který se má vytisknout na standardní výstup:

(display "Hello world!")
Poznámka: povšimněte si, že tento skript neobsahuje žádnou deklaraci uživatelské funkce, pouze přímé volání standardní funkce display. Tento příklad vlastně nemá v Javě ekvivalentní obdobu, což mj. znamená, že výsledný bajtkód bude muset ve skutečnosti obsahovat mnohem větší množství bloků, než pouhé zobrazení řetězce na standardním výstupu. Dále stojí za povšimnutí samotný název skriptu, který je schválně zvolen takovým způsobem, aby odpovídal jmenným konvencím Javy – jsou použita velká písmena na začátku názvů a taktéž se používá pojmenování typu CamelCase namísto lispem-inspirovaného-pojmenování-s-pomlčkami a už vůbec ne pojmenování_s_podtržítky.

Pokud je výše uvedený skript naprogramovaný ve Scheme uložen do souboru pojmenovaného „Hello.scm“, můžeme jeho překlad do bajtkódu JVM provést tímto příkazem:

$ ./kawa -C HelloWorld.scm 
Poznámka: předchozí příkaz předpokládá, že se spustitelný soubor kawa nachází v aktivním adresáři. Pokud tomu tak není, můžete vynechat úvodní „./“, ovšem cestu k nástroji kawa je nutné přidat do PATH. Taktéž si povšimněte, že překlad do bajtkódu se zapíná přepínačem -C, i když se na několika místech v dokumentaci píše o přepínači -c.

Následně se můžeme pokusit o spuštění, jakoby se jednalo o běžnou přeloženou javovskou třídu:

$ java HelloWorld

Ovšem výsledek pravděpodobně nebude odpovídat našemu očekávání, protože namísto zobrazení řetězce „Hello world“ se na chybovém výstupu zobrazí hlášení o chybě:

Exception in thread "main" java.lang.NoClassDefFoundError: gnu/expr/RunnableModule
        at java.lang.ClassLoader.defineClass1(Native Method)
        at java.lang.ClassLoader.defineClass(ClassLoader.java:800)
        at java.security.SecureClassLoader.defineClass(SecureClassLoader.java:142)
        at java.net.URLClassLoader.defineClass(URLClassLoader.java:449)
        at java.net.URLClassLoader.access$100(URLClassLoader.java:71)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:361)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:425)
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:358)
        at sun.launcher.LauncherHelper.checkAndLoadMain(LauncherHelper.java:482)
Caused by: java.lang.ClassNotFoundException: gnu.expr.RunnableModule
        at java.net.URLClassLoader$1.run(URLClassLoader.java:366)
        at java.net.URLClassLoader$1.run(URLClassLoader.java:355)
        at java.security.AccessController.doPrivileged(Native Method)
        at java.net.URLClassLoader.findClass(URLClassLoader.java:354)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:425)
        at sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:308)
        at java.lang.ClassLoader.loadClass(ClassLoader.java:358)
Poznámka: konkrétní stack trace může být ve skutečnosti nepatrně odlišný, ovšem důvod chyby je stále stejný.

4. Přidání cesty k runtime knihovně a vygenerování bajtkódu pro funkci main

Vidíme, že se spuštění nepodařilo. Je tomu tak z toho důvodu, že i ty nejjednodušší skripty napsané ve Scheme pro své spuštění vyžadují i runtime knihovnu s podpůrnými datovými typy, implementací základních funkcí Scheme atd. Tato knihovna je uložena v Java archivu pojmenovaném kawart.jar. V případě, že se soubor kawart.jar při překladu a instalaci nástroje Kawa uložil do adresáře ~/lib, bude muset spuštění našeho příkladu vypadat následovně:

$ java -cp /home/tester/lib/kawart.jar:. HelloWorld

Ve skutečnosti nebude spuštění ani v tomto případě úspěšné, a to z toho důvodu, že námi přeložená třída neobsahuje obdobu Javovské metody public void main(String args[]), která tvoří jeden ze vstupních bodů aplikace:

Error: Main method not found in class HelloWorld, please define the main method as:
   public static void main(String[] args)

Ostatně obsah souboru „Hello.class“ si můžeme vypsat standardním nástrojem javap, což je disassembler pro standardní soubory .class, který je dodáván přímo v JDK (Java Development Kit):

$ javap HelloWorld
 
Compiled from "HelloWorld.scm"
public class HelloWorld extends gnu.expr.ModuleBody implements java.lang.Runnable,gnu.expr.RunnableModule {
  static final gnu.lists.IString Lit0;
  public static HelloWorld $instance;
  public final void run(gnu.mapping.CallContext);
  public static {};
  public HelloWorld();
}
Poznámka: ve skutečnosti lze další přímo spustitelné příkazy uložit do bloku static, takže minimálně pro starší JRE není existence metody main striktně vyžadována.

V případě, že budeme chtít vytvořit soubor .class, který bude spustitelný, musíme překlad provést nepatrně odlišným způsobem, a to konkrétně takto (přidáním přepínače –main, který musí být uveden před přepínačem -C):

$ ./kawa --main -C HelloWorld.scm

Spuštění nyní proběhne naprosto bez problémů:

$ java -cp /home/tester/lib/kawart.jar:. HelloWorld
 
Hello world!

Pro úplnost se podívejme, jak vypadá dekódovaný obsah souboru „Hello.class“ v případě, že byl překlad proveden s přepínačem –main:

$ javap HelloWorld
 
Compiled from "HelloWorld.scm"
public class HelloWorld extends gnu.expr.ModuleBody implements java.lang.Runnable,gnu.expr.RunnableModule {
  static final gnu.lists.IString Lit0;
  public static HelloWorld $instance;
  public final void run(gnu.mapping.CallContext);
  public static {};
  public HelloWorld();
  public static void main(java.lang.String[]);
}

Můžeme vidět, že oproti předchozí variantě došlo k přidání výše zmíněné funkce main tvořící vstupní bod aplikace.

5. Skript typu „Hello world“ s uživatelsky definovanou funkcí

Nyní se pokusme původní skript „Hello.scm“ upravit takovým způsobem, aby obsahoval uživatelsky definovanou funkci, kterou ve skriptu následně zavoláme. Taková úprava je pochopitelně velmi snadná a může vypadat například takto:

(define (hello)
  (display "Hello world!"))
 
(hello)

I tento skript je bez problémů přeložitelný do bajtkódu JVM:

$ ./kawa -C HelloWorld2.scm 

Výsledek ovšem v této chvíli bude odlišný, o čemž se opět snadno přesvědčíme standardním nástrojem javap. Ve výpisu interních bloků bajtkódu si povšimněte existence statické metody nazvané hello. Pochopitelně se jedná o námi implementovanou funkci hello přeloženou ze Scheme:

$ javap HelloWorld2
 
public class HelloWorld2 extends gnu.expr.ModuleBody implements java.lang.Runnable,gnu.expr.RunnableModule {
  public static final gnu.expr.CompiledProc hello;
  static final gnu.lists.IString Lit0;
  public static HelloWorld2 $instance;
  static final gnu.mapping.SimpleSymbol Lit1;
  public final void run(gnu.mapping.CallContext);
  public static void hello();
  public static java.lang.Object hello$check(gnu.mapping.Procedure, gnu.mapping.CallContext);
  public static {};
  public HelloWorld2();
}

Povšimněte si, že uživatelská funkce hello byla přeložena do statické metody pojmenované taktéž hello:

  public static void hello();
    Code:
       0: getstatic     #12    // Field Lit0:Lgnu/lists/IString;
       3: invokestatic  #18    // Method kawa/lib/ports.display:(Ljava/lang/Object;)V
       6: return

Pro otestování funkčnosti příkladu musíme dodat (automaticky generovanou) metodu main, a to nám již dobře známým způsobem – použitím přepínače –main:

$ ./kawa --main -C HelloWorld2.scm 
 

Takto vytvořený soubor nazvaný „HelloWorld2.class“ již bude možné spustit v rámci běhového prostředí Javy (JRE), podobně jako běžnou přeloženou javovskou třídu:

$ java -cp /home/tester/lib/kawart.jar:. HelloWorld2
 
Hello world!

6. Překlad funkcí s parametry a návratovou hodnotou: problematika statického typového systému JVM

V předchozí kapitole jsme mohli vidět, že se funkce vytvořené v programovacím jazyku Scheme překládají do bajtkódu takovým způsobem, že se z funkcí stanou běžné statické metody. Tyto metody jsou volatelné z běžných metod napsaných v programovacím jazyku Java či v libovolném jiném jazyku postaveném nad JVM. Ovšem je zde jeden dosti zásadní háček, který spočívá v tom, že se snažíme propojit dynamicky typovaný jazyk Scheme s ekosystémem postaveným okolo staticky typovaného programovacího jazyka Java. Od vlastností Javy se do značné míry odvíjí i vlastnosti bajtkódu JVM, což v tomto případě znamená, že instrukce bajtkódu vždy pracují s operandy konkrétních typů. Neexistuje například instrukce add, která by pracovala jak s celými čísly, tak i s čísly typu float či double.

Rozdíly mezi Scheme a Javou si můžeme ilustrovat na velmi jednoduché funkci sloužící pro součet dvou hodnot. Taková funkce se ve Scheme naprogramuje naprosto triviálním způsobem:

(define (add x y)
  (+ x y))

Samozřejmě si vyzkoušíme překlad této funkce do bajtkódu:

$ ./kawa -C Add1.scm

Soubor „Add1.class“, který překladem vznikl, můžeme analyzovat, a to pochopitelně opět nástrojem javap. Tentokrát ovšem použijeme i přepínač -c, kterým si vynutíme výpis instrukcí bajtkódu, které tvoří těla jednotlivých metod a bloků static. Z celého bajtkódu zde uvedu pouze výpis přeložené funkce add, protože nás jeho další součásti prozatím nebudou zajímat:

public static java.lang.Object add(java.lang.Object, java.lang.Object);
  Code:
     0: iconst_1
     1: aload_0
     2: aload_1
     3: invokestatic  #16                 // Method gnu/kawa/functions/AddOp.apply2:(ILjava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
     6: areturn

Výsledný bajtkód není ani krátký a dokonce ani příliš efektivní a rychlý, protože se v něm volá další metoda apply z runtime třídy AddOp, tedy interní implementace součtu ve Scheme. Toto řešení má pochopitelně svůj význam, protože ve Scheme můžeme sčítat všechny číselné hodnoty, nezávisle na tom, kam spadají v typovém systému „numerické věže“ tohoto jazyka. Jen pro připomenutí – volání funkce + (skutečně se jedná o validní jméno funkce) lze aplikovat na libovolný počet hodnot tohoto typu (ty je ve Scheme vázán k hodnotě, nikoli km proměnné!):

Typ Význam
number libovolná obecná čísla
quantity numerická hodnota i s uvedenou jednotkou (viz další text)
quaternion kvaterniony
complex komplexní čísla
real reálná čísla
rational zlomky (racionální čísla)
integer celá čísla

To příliš neodpovídá numerické věži jazyka Java, která je odlišná (navíc se nejedná o věž, ale o dvě větve – celá čísla, čísla s plovoucí řádovou čárkou).

7. Přidání informací o typech parametrů uživatelsky definované funkce

V případě, že budeme chtít v programovacím jazyce Scheme naprogramovat efektivněji prováděnou funkci pro součet dvou hodnot, budeme muset přistoupit k tomu, že explicitně určíme typ parametrů funkce a případně i typ návratové hodnoty. Typ je v systému Kawa nepovinnou metainformací připojenou ke jménu parametru a oddělenou od jména dvojtečkou (navíc můžeme použít i nepovinné mezery okolo dvojtečky). Definice funkce add akceptující jako své parametry dvě celá 32bitová čísla typu int tedy bude vypadat následovně:

(define (add x :: int y :: int)
  (+ x y))

Oproti tomu původní funkce vypadala pouze takto:

(define (add x y)
  (+ x y))

Po překladu prvního skriptu (s typovými informacemi) do bajtkódu se můžeme podívat na to, jak byl součet implementován po přidání typových informací:

public static int add(int, int);
  Code:
     0: iload_0        // načtení prvního parametru metody s jeho uložením na zásobník operandů
     1: iload_1        // načtení třetího parametru metody s jeho uložením na zásobník operandů
     2: iadd           // provedení součtu
     3: ireturn        // návrat z metody, použití hodnoty z vrcholu zásobníku pro přenos výsledku metody

Výsledek je nyní efektivní a přímočarý – dokonce ho ani lépe napsat nelze!

Ostatně nebude na škodu si ověřit, do jakého bajtkódu se přeloží obdobná metoda, tentokrát naprogramovaná v Javě:

class Test {
    // provedení součtu dvou celých čísel
    static int add(int a, int b) {
        int c=a+b;
        return c;
    }
 
    // zavolá metodu pro provedení součtu dvou čísel
    // a uloží návratovou hodnotu do své lokální proměnné
    static void callAdd() {
        int result = add(1234,5678);
    }
}

Přeložený bajtkód první z těchto metod (tedy metody add) je následující. Všechny poznámky jsou samozřejmě dopsány ručně:

// v metodě add je zásobník operandů použit pouze pro provedení operace součtu
static int add(int, int);
  Code:
   0:   iload_0        // uložení prvního parametru metody na zásobník operandů
   1:   iload_1        // uložení druhého parametru metody na zásobník operandů
   2:   iadd           // provedení operace součtu s odstraněním obou operandů
   3:   istore_2       // vyzvednutí výsledku součtu a uložení do lokální proměnné
   4:   iload_2        // opětovné uložení obsahu lokální proměnné na zásobník
   5:   ireturn        // při operaci ireturn se využije hodnota z vrcholu zásobníku
Poznámka: povšimněte si, že v tomto případě je vlastně bajtkód nepatrně složitější, než v předchozím příkladu. Je tomu tak z toho důvodu, že výsledek součtu nejdříve uložíme do lokální proměnné c, která je uložena na zásobníkovém rámci a teprve poté je výsledek přenesen zpět na zásobník, aby mohl být vrácen instrukcí ireturn. Pokud se ptáte, proč je to řešeno tak komplikovaně – jde o podporu ladění a krokování aplikace, protože potřebujeme, aby bylo možné běh programu zastavit na přiřazení do proměnné c. V reálném provozu instrukce provedené navíc nebudou příliš vadit, protože se při JITování optimalizují a odstraní.

8. Základní principy, na kterých je postaven bajtkód a interpret JVM

V této kapitole se ve stručnosti seznámíme se základními principy, na kterých je postaven bajtkód virtuálního stroje Javy i interpret, který je v JVM taktéž implementován (JIT je pochopitelně mnohem složitější, ovšem vychází z jednoduššího interpretru, jehož činnost vlastně musí napodobit generovaným strojovým kódem).

Většina instrukcí virtuálního stroje Javy pracuje s operandy uloženými na takzvaném zásobníku operandů (operand stack). Zásobník operandů (v tomto případě se jedná o skutečný zásobník typu LIFO – Last In, First Out) je vytvářen v čase běhu aplikace pro každou zavolanou metodu, což mj. znamená, že je při spuštění metody vždy prázdný (zásobník operandů je podle specifikace součástí zásobníkového rámce, jeho konkrétní umístění však je libovolné). Již v čase překladu zdrojového kódu je pro každou metodu zjištěno, jak velká oblast paměti má být pro zásobník operandů vyhrazena a samozřejmě je prováděna kontrola, zda se v době běhu aplikace tato velikost nepřekročí (to by se nemělo u validního bajtkódu stát).

Virtuální stroj Javy kontroluje typy operandů uložených na zásobník operandů a zajišťuje, že se nad těmito operandy budou provádět pouze typově bezpečné operace. V praxi to například znamená, že není možné na zásobník uložit dvě hodnoty typu float a následně provést instrukci iadd, protože tato instrukce vyžaduje, aby na zásobníku byly uloženy dvě hodnoty typu int (i když floatint mají shodnou bitovou šířku).

Poznámka: tato vlastnost virtuálního stroje Javy je zcela odlišná od zdánlivě podobného virtuálního stroje, tentokrát VM Pythonu. Tento virtuální stroj má vlastní bajtkód, ovšem instrukce odpovídající součtu je plně polymorfní, protože bude vykonávat odlišné operace podle toho, jakého datového typu budou její operandy. Pochopitelně se může jednat i o uživatelské datové typy.

Vraťme se však k virtuálnímu stroji Javy. Ten dokáže pracovat s celkem deseti datovými typy, které jsou všechny vypsány v následující tabulce. Prvních osm datových typů odpovídá primitivním datovým typům známým všem programátorům v Javě, devátý typ odpovídá objektovému datovému typu (reference na libovolnou instanci), ovšem desátý typ není přímo z Javy přístupný. Operand s tímto typem obsahuje ukazatel na instrukční kód, tj. může se například jednat o skutečnou adresu v adresovém prostoru procesoru s JVM, offset platný v rámci prostoru haldy atd.

# Typ v Javě Použitý typ v JVM
1 boolean int
2 byte int
3 char int
4 short int
5 int int
6 long long
7 float float
8 double double
9 reference reference
10 není dostupný returnAddress

Instrukce pracující s typem int začínají písmenem „i“, instrukce pro typ long písmenem „l“ atd.

9. Překlad funkcí s parametry s typem odlišným od typu int

Nic nám pochopitelně nebrání naprogramovat si další variantu funkce pro součet dvou čísel, ovšem tentokrát budou oba operandy typu float a nikoli typu int:

(define (add x :: float y :: float)
  (+ x y))

Pravděpodobně váš příliš nepřekvapí, že i instrukce v generovaném bajtkódu budou odlišné. Vzhledem k tomu, že float je v Javě primitivním datovým typem (viz též předchozí kapitolu), navíc plně podporovaným a uzavřeným vůči všem základním operacím (což u jiných datových typů ne vždy platí!), bude výsledný bajtkód obsahovat instrukce pro operaci s hodnotami typu float:

public static float add(float, float);
  Code:
     0: fload_0        // uložení prvního parametru metody na zásobník operandů
     1: fload_1        // uložení druhého parametru metody na zásobník operandů
     2: fadd           // provedení operace součtu s odstraněním obou operandů
     3: freturn        // při operaci freturn se využije hodnota z vrcholu zásobníku

Otestovat můžeme i funkci, která akceptuje první parametr typu int a druhý parametr typu float:

(define (add x :: int y :: float)
  (+ x y))

Zajisté již tušíte, že vygenerovaný bajtkód bude v tomto případě složitější, protože bude nutné provést konverzi obou operandů na společný typ (víme již, že nelze použít iadd pro jiné operandy, než typu int). V Javě je definována konverze intfloat:

public static float add(int, float);
  Code:
     0: iload_0        // uložení prvního parametru metody na zásobník operandů
     1: i2f            // převod celého čísla typu int na typ float
     2: fload_1        // uložení druhého parametru metody na zásobník operandů
     3: fadd           // provedení operace součtu s odstraněním obou operandů
     4: freturn        // při operaci freturn se využije hodnota z vrcholu zásobníku
Poznámka: jen na okraj – při konverzi hodnoty typu int na hodnotu typu float může dojít ke ztrátě přesnosti, protože jak typ int, tak i typ float jsou podle specifikace 32bitové, ovšem zatímco u typu int jsou všechny bity rezervovány pro uložení celočíselné hodnoty ve tvaru dvojkového doplňku, u typu float je nutné několik bitů z 32bitového slova rezervovat pro uložení exponentu, viz též Norma IEEE 754 a příbuzní: formáty plovoucí řádové tečky.

10. Bajtkód funkce pro výpočet faktoriálu s přímou rekurzí

Nyní se podívejme na poněkud složitější demonstrační příklady naprogramované ve Scheme a na způsob jejich překladu do bajtkódu virtuálního stroje Javy. Začneme běžnou implementací faktoriálu, konkrétně s využitím algoritmu, v němž se používá přímá rekurze. Jedná se o jeden z typických „školních“ příkladů, na němž se ovšem kromě jeho jednoduchosti dá ukázat mnoho vlastností programovacích jazyků a jejich interpretrů i překladačů:

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

V definici funkce pro výpočet faktoriálu jsme nepoužili žádné typové informace, takže překlad bude proveden takovým způsobem, aby byl výpočet použitelný pro všechny numerické datové typy jazyka Scheme. Tomu bude odpovídat o poměrně komplikovaný bajtkód:

public static java.lang.Object factorial(java.lang.Object);
  Code:
     0: aload_0
     1: getstatic     #14     // Field Lit0:Lgnu/math/IntNum;
     4: invokestatic  #20     // Method gnu/kawa/functions/NumberCompare.$Eq:(Ljava/lang/Object;Ljava/lang/Object;)Z
     7: ifeq          16
    10: getstatic     #23     // Field Lit1:Lgnu/math/IntNum;
    13: goto          34
    16: getstatic     #29     // Field gnu/kawa/functions/MultiplyOp.TIMES:Lgnu/kawa/functions/MultiplyOp;
    19: aload_0
    20: iconst_m1
    21: aload_0
    22: getstatic     #23     // Field Lit1:Lgnu/math/IntNum;
    25: invokestatic  #35     // Method gnu/kawa/functions/AddOp.apply2:(ILjava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
    28: invokestatic  #39     // Method factorial:(Ljava/lang/Object;)Ljava/lang/Object;
    31: invokevirtual #44     // Method gnu/mapping/Procedure.apply2:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
    34: areturn

Výpočet nebude příliš rychlý, ovšem bude pracovat pro libovolné vstupní n (pokud se pochopitelně bude jednat o celé kladné číslo).

11. Optimalizace výpočtu faktoriálu přidáním typových informací

Nic nám ovšem nebrání vylepšit a urychlit výpočet faktoriálu takovým způsobem, že do původního skriptu přidáme potřebné typové informace. První pokus o optimalizaci může vypadat následovně (informace o typech jsou opět zvýrazněny tučným fontem):

(define (factorial n :: int)
  (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 :: int 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))

Zajímavé je, že dodané typové informace o parametru funkce factorial ve skutečnosti nejsou dostačující pro vygenerování optimálního bajtkódu, což je jasně patrné z disassemblovaného bajtkódu:

public static java.lang.Object factorial(int);
  Code:
     0: iload_0
     1: ifne          10
     4: getstatic     #12     // Field Lit0:Lgnu/math/IntNum;
     7: goto          26
    10: getstatic     #18     // Field gnu/kawa/functions/MultiplyOp.TIMES:Lgnu/kawa/functions/MultiplyOp;
    13: iload_0
    14: invokestatic  #24     // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
    17: iload_0
    18: iconst_1
    19: isub
    20: invokestatic  #28     // Method factorial:(I)Ljava/lang/Object;
    23: invokevirtual #34     // Method gnu/mapping/Procedure.apply2:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
    26: areturn
Poznámka: povšimněte si především volání funkcí určených pro konverzi numerických hodnot, pro implementaci „univerzálních“ aritmetických operací atd. U výpočtu faktoriálu nad datovým typem int ovšem žádné volání dalších metod nebudeme potřebovat – pochopitelně kromě přímé rekurze.

Ovšem na tomto místě si pravděpodobně položíte otázku „Proč tomu tak je“? Ve funkci je implementován výpočet, do kterého sice vstupuje hodnota typu int, ovšem není specifikován návratový typ funkce. I to ovšem lze v Kawě provést, a to uvedením typu ještě před samotné tělo funkce. Náš skript se tedy nepatrně změní:

(define (factorial n :: int) :: int
  (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 :: int 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))

Nyní je již bajtkód optimální – obsahuje podmínku ifne se skokem goto a přímou rekurzí realizovanou instrukcí invokestatic:

public static int factorial(int);
  Code:
     0: iload_0
     1: ifne          8      // porovnání parametru s nulou
     4: iconst_1             // pokud je vstup roven 0, vrátíme jedničku
     5: goto          16
     8: iload_0              // n na zásobník operandů
     9: iload_0
    10: iconst_1
    11: isub                 // výpočet n-1
    12: invokestatic  #12    // Method factorial:(I)I
    15: imul                 // výpočet nového mezivýsledku
    16: ireturn              // předání výsledku výpočtu volající funkci/metodě

12. Výpočet faktoriálu používající numerické hodnoty typu long

Jen pro zajímavost se podívejme na to, jak se změní funkce pro výpočet faktoriálu ve chvíli, kdy všechny výpočty budou probíhat nad datovým typem long. Samotné tělo definované funkce bude stejné, jako v předchozím příkladu, ovšem změní se určení typu parametru i typu návratové hodnoty:

(define (factorial n :: long) :: long
  (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 :: long 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))

Výsledný bajtkód se vlastně příliš neliší od bajtkódu předchozího příkladu, samozřejmě s tím rozdílem, že se zde použijí instrukce pro práci s celočíselnými operandy typu long a nikoli int (tyto instrukce začínají znakem „l“, u typu int začínají znakem „i“):

public static long factorial(long);
  Code:
     0: lload_0
     1: lconst_0
     2: lcmp
     3: ifne          10      // porovnání parametru s nulou
     6: lconst_1              // pokud je vstup roven 0, vrátíme jedničku
     7: goto          18
    10: lload_0               // n na zásobník operandů
    11: lload_0
    12: lconst_1
    13: lsub                  // výpočet n-1
    14: invokestatic  #12     // Method factorial:(J)J
    17: lmul                  // výpočet nového mezivýsledku
    18: lreturn               // předání výsledku výpočtu volající funkci/metodě

13. Optimalizace výpočtu faktoriálu s využitím tail rekurze

Nástroj Kawa při generování bajtkódu plně podporuje tail rekurzi a její optimalizaci, tedy náhradu rekurze za programovou smyčku popř. v bajtkódu za kombinaci podmínky a skoku (instrukce goto). Zkusme tedy náš výpočet faktoriálu upravit takovým způsobem, aby se tail rekurze a její optimalizace (TCO) mohla provést. První varianta upraveného skriptu může vypadat například následovně:

(define (factorial n :: int) :: int
  (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 :: int 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))
Poznámka: všimněte si, že volání fact-iter je provedeno v takzvané tail pozici.

Po překladu do bajtkódu virtuálního stroje Javy je (opět) patrné, že námi zavedené typové informace nejsou dostačující, protože v bajtkódu můžeme vidět volání funkcí s implementací aritmetických operací a konverzí pro všechny numerické datové typy jazyka Scheme:

public static int factorial(int);
  Code:
     0: iload_0
     1: invokestatic  #14                 // Method gnu/math/IntNum.make:(I)Lgnu/math/IntNum;
     4: getstatic     #18                 // Field Lit0:Lgnu/math/IntNum;
     7: astore_2
     8: astore_1
     9: aload_1
    10: lconst_0
    11: invokestatic  #22                 // Method gnu/math/IntNum.compare:(Lgnu/math/IntNum;J)I
    14: ifne          24
    17: aload_2
    18: invokevirtual #28                 // Method java/lang/Number.intValue:()I
    21: goto          37
    24: aload_1
    25: iconst_m1
    26: invokestatic  #32                 // Method gnu/math/IntNum.add:(Lgnu/math/IntNum;I)Lgnu/math/IntNum;
    29: aload_1
    30: aload_2
    31: invokestatic  #36                 // Method gnu/math/IntNum.times:(Lgnu/math/IntNum;Lgnu/math/IntNum;)Lgnu/math/IntNum;
    34: goto          7
    37: ireturn

14. Plně optimalizovaná varianta výpočtu faktoriálu

Plně optimalizovanou variantu výpočtu faktoriálu získáme tak, že typové informace použijeme i u vnitřní pomocné funkce použité pro tail call rekurzi. Skript se sice změní jen nepatrně, ovšem důsledek pro generovaný bajtkód je obrovský:

(define (factorial n :: int) :: int
  (let fact-iter (                     ; pomocná vnitřní funkce
              (n :: int n )            ; počitadlo iterací
              (result :: int 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 :: int 0)
 
(do ()
  ((>= n 30))
  (display (factorial n))
  (newline)
  (set! n (+ n 1)))

Výsledný bajtkód již obsahuje pouze základní numerické operace s operandy typu int, podmíněné skoky (implementace podmínky) a skok nepodmíněný (implementace smyčky)

public static int factorial(int);
  Code:
     0: iload_0
     1: iconst_1               // příprava výsledku (akumulátoru)
     2: istore_2
     3: istore_1
     4: iload_1                // začátek programové smyčky (viz goto na offsetu 19)
     5: ifne          12       // test, zda se má výpočet (smyčka) ukončit či nikoli
     8: iload_2
     9: goto          22
    12: iload_1
    13: iload_2
    14: imul                   // provedení jedné iterace výpočtu faktoriálu
    15: istore_2
    16: iinc          1, -1    // snížení hodnoty n
    19: goto          4        // a provedení další iterace
    22: ireturn                // ukončení běhu funkce, hodnota z vrcholu zásobníku je návratovou hodnotou

15. Obsah další části seriálu

V navazující části seriálu o rozsáhlém světě lispovských programovacích jazyků dokončíme popis možností nabízených programovacím jazykem Kawa. Především se zaměříme na podporu dalších typů kolekcí, protože Kawa umožňuje kromě běžných seznamů (list) velmi efektivně pracovat i s vektory a poli. Na tomto poli se přibližuje možnostem specializovaných jazyků.

16. Soubor Makefile určený pro překlad demonstračních skriptů do bajtkódu a pro jejich disassembling

Pro úplnost si ještě ukažme, jak by mohl vypadat pomocný soubor Makefile sloužící pro překlad dnešních demonstračních příkladu do bajtkódu JVM a pro jejich následný disassembling:

KAWA=./kawa
JAVA_DISASSEMBLER=javap
 
.PRECIOUS: %.class
 
all:    Add1.asm Add2.asm Add3.asm Add4.asm HelloWorld.asm HelloWorld2.scm \
        Factorial1.asm Factorial2.asm Factorial3.asm \
        Factorial4.asm Factorial5.asm Factorial6.asm
 
clean:
        rm -f *.class
        rm -f *.asm
 
%.asm:  %.class
        $(JAVA_DISASSEMBLER) -c $< > $@
 
%.class:        %.scm
        $(KAWA) -C $<
Poznámka: tento soubor naleznete na adrese https://github.com/tisnik/lisp-families/blob/master/kawa/Makefile.

17. Příloha: vybrané instrukce bajtkódu JVM

Na závěr si popíšeme aritmetické instrukce bajtkódu JVM, které jsou velmi jednoduché. Jedná se většinou o instrukce pracující s dvojicí operandů uložených na zásobníku operandů, Tyto instrukce slouží pro implementaci pěti základních (binárních) aritmetických operací – součtu, rozdílu, součinu, podílu a výpočtu zbytku po dělení. Vzhledem k tomu, že každá tato operace existuje ve čtyřech variantách pro datové typy int, long, float a double, jsou binární aritmetické operace implementovány dvaceti instrukcemi.

Další čtyři instrukce – změna znaménka – však pracují pouze s jedním operandem. Virtuální stroj Javy v čase běhu aplikace nebo v čase verifikace bajtkódu testuje, zda se všechny aritmetické operace provádí se správným typem operandů. Povšimněte si, že instrukční soubor JVM neobsahuje žádné aritmetické operace pro operandy typu byte, short či char – operandy těchto typů jsou vždy převedeny na int. Navíc se u celočíselných operací netestuje přetečení, což je možná u vysokoúrovňového jazyka poněkud překvapující (ono je ostatně při poněkud jednostranném pohledu překvapující i to, že Java má primitivní datové typy :-):

# Instrukce Opkód Operand 1 Operand 2 Operace Poznámka
1 iadd 0×60 int int součet oba původní operandy jsou ze zásobníku operandů odstraněny
2 ladd 0×61 long long součet -//-
3 fadd 0×62 float float součet -//-
4 dadd 0×63 double double součet -//-
5 isub 0×64 int int rozdíl -//-
6 lsub 0×65 long long rozdíl -//-
7 fsub 0×66 float float rozdíl -//-
8 dsub 0×67 double double rozdíl -//-
9 imul 0×68 int int součin -//-
10 lmul 0×69 long long součin -//-
11 fmul 0×6A float float součin -//-
12 dmul 0×6B double double součin -//-
13 idiv 0×6C int int podíl -//-
14 ldiv 0×6D long long podíl -//-
15 fdiv 0×6E float float podíl -//-
16 ddiv 0×6F double double podíl -//-
17 irem 0×70 int int zbytek po dělení -//-
18 lrem 0×71 long long zbytek po dělení -//-
19 frem 0×72 float float zbytek po dělení -//-
20 drem 0×73 double double zbytek po dělení -//-
21 ineg 0×74 int   změna znaménka původní operand je ze zásobníku operandů odstraněn
22 lneg 0×75 long   změna znaménka původní operand je ze zásobníku operandů odstraněn
23 fneg 0×76 float   změna znaménka původní operand je ze zásobníku operandů odstraněn
24 dneg 0×77 double   změna znaménka původní operand je ze zásobníku operandů odstraněn

Další důležitou skupinou instrukcí virtuálního stroje jazyka Java, s níž se dnes ve stručnosti seznámíme, jsou instrukce sloužící pro konverzi dat. Programovací jazyk Java sice patří mezi jazyky silně typované, ale konverze mezi některými datovými typy jsou prováděny automaticky (byte-→int) a jiné lze explicitně zapsat. Navíc se konverzní instrukce objevují v bajtkódu například při vytváření návratové hodnoty metody v případě, že tato hodnota nemá typ int, long, float či double. Ovšem ne všechny kombinace konverzí datových typů jsou v instrukční sadě přítomny, takže některé konverze je ve skutečnosti nutné provádět pomocí dvojice instrukcí (například se může jednat o konverzi z float na short a podobně). Podívejme se ostatně na tabulku obsahující všechny konverzní instrukce. V prvním sloupci je uveden datový typ, z něhož je konverze prováděna a v prvním řádku naopak výsledný datový typ:

# z/na-> char byte short int long float double
1 char              
2 byte              
3 short              
4 int i2c i2b i2s   i2l i2f i2d
5 long       l2i   l2f l2d
6 float       f2i f2l   f2d
7 double       d2i d2l d2f  

Naproti tomu však některé další instrukce obsahují přímo ve svém operačním kódu (tj. v onom jednom bajtu) krátkou celočíselnou konstantu, která se využívá buď jako index do oblasti lokálních proměnných nebo jako skutečná číselná konstanta. Tato technika je použita z toho důvodu, aby byl bajtkód co možná nejkratší, proto se také nejvíce místa v instrukční sadě „obětovalo“ na instrukce sloužící pro uložení konstanty typu int. V následující tabulce jsou vypsány všechny instrukce sloužící pro uložení číselné konstanty na zásobník. Ve sloupci „Instrukce“ se nachází symbolické jméno instrukce, sloupec „Opkód“ obsahuje bajtovou hodnotu uloženou přímo v bajtkódu (tedy operační kód instrukce), ve sloupcích „Data 1“ a „Data 2“ jsou vypsány bajty, které jsou případně uloženy ihned za operačním kódem a ve sloupci „Typ“ je uveden datový typ skutečně uložený na zásobník operandů:

# Instrukce Opkód Data 1 Data 2 Typ na zásobníku Popis
01 aconst_null 0×01     ref. uložení reference „null“ na zásobník
02 iconst_m1 0×02     int uložení konstanty –1 na zásobník
03 iconst0 0×03     int uložení konstanty 0 na zásobník
04 iconst1 0×04     int uložení konstanty 1 na zásobník
05 iconst2 0×05     int uložení konstanty 2 na zásobník
06 iconst3 0×06     int uložení konstanty 3 na zásobník
07 iconst4 0×07     int uložení konstanty 4 na zásobník
08 iconst5 0×08     int uložení konstanty 5 na zásobník
09 lconst0 0×09     long uložení konstanty 0L na zásobník
10 lconst1 0×0a     long uložení konstanty 1L na zásobník
11 fconst0 0×0b     float uložení konstanty 0.0f na zásobník
12 fconst1 0×0c     float uložení konstanty 1.0f na zásobník
13 fconst2 0×0d     float uložení konstanty 2.0f na zásobník
14 dconst0 0×0e     double uložení konstanty 0.0 na zásobník
15 dconst1 0×0f     double uložení konstanty 1.0 na zásobník
16 bipush 0×10 byteconst   int uložení „byteconst“ na zásobník s konverzí na int
17 sipush 0×11 hi-byte lowbyte int uložení slova hibyte-lowbyte na zásobník s konverzí na int
18 ldc 0×12 index   string/ref/int/float načte konstantu z constant poolu (může se jednat i o referenci)
19 ldc_w 0×13 hi-byte lowbyte string/ref/int/float načte konstantu z constant poolu (index je šestnáctibitový)
20 ldc2_w 0×14 hi-byte lowbyte long/double totéž co předchozí instrukce, ale pro typy long a double (ty mají v constant poolu vyhrazeny dvě položky)

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 HelloWorld.scm přímé volání funkce display https://github.com/tisnik/lisp-families/blob/master/kawa/He­lloWorld.scm
2 HelloWorld2.scm implementace funkce Hello https://github.com/tisnik/lisp-families/blob/master/kawa/He­lloWorld2.scm
3 Add1.scm součet dvou numerických hodnot libovolného typu https://github.com/tisnik/lisp-families/blob/master/kawa/Add1.scm
4 Add2.scm součet dvou numerických hodnot typu int https://github.com/tisnik/lisp-families/blob/master/kawa/Add2.scm
5 Add3.scm součet dvou numerických hodnot typu float https://github.com/tisnik/lisp-families/blob/master/kawa/Add3.scm
6 Add4.scm součet dvou numerických hodnot typu int a float https://github.com/tisnik/lisp-families/blob/master/kawa/Add4.scm
7 Factorial1.scm klasický rekurzivní výpočet faktoriálu https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial1.scm
8 Factorial2.scm přidání typových informací o parametru funkce https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial2.scm
9 Factorial3.scm přidání typové informace o výsledku funkce https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial3.scm
10 Factorial4.scm výpočet faktoriálu nad typem long https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial4.scm
11 Factorial5.scm výpočet faktoriálu s tail call rekurzí https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial5.scm
12 Factorial6.scm přidání typových informací a plná optimalizace výpočtu https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial6.scm

Nesmíme zapomenout ani na vygenerované a disassemblované soubory typu .class:

# Příklad Popis příkladu Cesta
1 HelloWorld.asm přímé volání funkce display https://github.com/tisnik/lisp-families/blob/master/kawa/He­lloWorld.asm
2 HelloWorld2.asm implementace funkce Hello https://github.com/tisnik/lisp-families/blob/master/kawa/He­lloWorld2.asm
3 Add1.asm součet dvou numerických hodnot libovolného typu https://github.com/tisnik/lisp-families/blob/master/kawa/Add1.asm
4 Add2.asm součet dvou numerických hodnot typu int https://github.com/tisnik/lisp-families/blob/master/kawa/Add2.asm
5 Add3.asm součet dvou numerických hodnot typu float https://github.com/tisnik/lisp-families/blob/master/kawa/Add3.asm
6 Add4.asm součet dvou numerických hodnot typu int a float https://github.com/tisnik/lisp-families/blob/master/kawa/Add4.asm
7 Factorial1.asm klasický rekurzivní výpočet faktoriálu https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial1.asm
8 Factorial2.asm přidání typových informací o parametru funkce https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial2.asm
9 Factorial3.asm přidání typové informace o výsledku funkce https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial3.asm
10 Factorial4.asm výpočet faktoriálu nad typem long https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial4.asm
11 Factorial5.asm výpočet faktoriálu s tail call rekurzí https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial5.asm
12 Factorial6.asm přidání typových informací a plná optimalizace výpočtu https://github.com/tisnik/lisp-families/blob/master/kawa/Fac­torial6.asm

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