Obsah
1. Pohled pod kapotu JVM – složené datové typy a programová smyčka typu for-each v Lua VM
2. Programová smyčka typu „for-each“ v programovacím jazyku Lua
3. Demonstrační příklad Test23.lua – tabulky použité ve funkci pole
4. Okomentovaný bajtkód funkce printArray()
5. Okomentovaný bajtkód funkce sum()
6. Demonstrační příklad Test24.lua – tabulky použité ve funkci asociativního pole
7. Okomentovaný bajtkód funkce printTable()
8. Okomentovaný bajtkód funkce sum()
9. Porovnání implementace programové smyčky typu „for-each“ v JVM a Lua VM
10. Repositář se zdrojovými kódy obou dnešních demonstračních příkladů
1. Pohled pod kapotu JVM – složené datové typy a programová smyčka typu for-each v Lua VM
V předchozí části seriálu o programovacím jazyku Java i o virtuálním stroji tohoto jazyka jsme si ukázali, jakým způsobem se v Javě využívá programová smyčka typu „for-each“ i způsob překladu této programové smyčky do bajtkódu JVM. Připomeňme si, že tento typ programové smyčky lze v Javě použít pro průchod polem popř. jakoukoli kolekcí (resp. přesněji řečeno jakoukoli datovou strukturou, pro niž lze zkonstruovat iterátor). Zajímavé přitom je, že i když byla konstrukce smyčky „for-each“ zavedena až v Javě 5.0, nebylo ve skutečnosti nutné provést žádné zásahy do struktury bajtkódu ani do repertoáru instrukcí zpracovávaných virtuálním strojem jazyka Java. Průchod polem je v bajtkódu implementován s využitím počitadla, průchod kolekcemi opětovným voláním iterátoru (což vlastně odpovídá smyčce typu „while“). Dnes si ukážeme, jak je smyčka „for-each“ implementována v bajtkódech programovacích jazyků Lua a Python.
2. Programová smyčka typu „for-each“ v programovacím jazyku Lua
Nejprve si řekněme, jak se programová smyčka typu „for-each“ používá v programovacím jazyku Lua. Zde je jediným složeným datovým typem takzvaná tabulka, kterou je možné použít buď ve funkci pole (s indexy od 1 do délky pole) nebo alternativně ve funkci asociativního pole/slovníku. Ve skutečnosti lze oba způsoby zkombinovat, i když se v praxi většinou s jedinou datovou strukturou, v níž jsou nějaké prvky indexovány celými čísly a jiné prvky určeny klíči jiného typu (řetězec atd.) příliš často nesetkáme (s výjimkou řídkých matic atd.). V případě, že se tabulka používá ve funkci pole, lze pro průchod takovým polem použít programovou smyčku for s iterátorem získaným funkcí ipairs() (pracuje se s dvojicemi index-hodnota prvku):
function test(table) for i, item in ipairs(table) do ... ... ... end end
Pokud je tabulka používána ve funkci asociativního pole/slovníku, je nutné namísto funkce ipairs() volat funkci pairs() (potom se pracuje s dvojicemi klíč-hodnota, bez zaručení pořadí zpracování těchto dvojic):
function test(table) for key, value in pairs(table) do ... ... ... end end
3. Demonstrační příklad Test23.lua – tabulky použité ve funkci pole
Způsob využití tabulek ve funkci polí (s prvky indexovanými od jedničky) je ukázán v dnešním prvním demonstračním příkladu, jehož jméno je Test23.lua. V tomto příkladu jsou deklarovány dvě funkce. První funkce se jmenuje printArray() a slouží k výpisu obsahu celého pole na standardní výstup. Druhá funkce, jejíž jméno je sum(), sečte hodnotu všech prvků pole a vrátí výsledek (součet) jako návratovou hodnotu této funkce. Následuje výpis zdrojového kódu tohoto demonstračního příkladu:
-- -- Demonstracni priklad cislo 23. -- -- Tabulky vyuzite jako pole a programova smycka typu for-each. -- -- -- Vypis vsech prvku tabulky vyuzitych ve funkci pole. -- function printArray(array) for i, item in ipairs(array) do print(i, item) end end -- -- Vypocet souctu vsech prvku tabulky vyuzitych ve funkci pole. -- function sum(array) local sum = 0 for i, item in ipairs(array) do sum = sum + item end return sum end -- -- Test. -- function main() local array = {1, 2, 3, 4} printArray(array) print("Sum = " .. sum(array)) end main()
4. Okomentovaný bajtkód funkce printArray()
Podívejme se nyní na způsob překladu funkce printArray() do bajtkódu virtuálního stroje programovacího jazyka Lua. V bajtkódu můžeme vidět některé typické rysy, jakými se programová smyčka typu „for-each“ překládá. Prvním rysem je skok (JMP) před konec smyčky, konkrétně na místo, kde se volá iterátor a testuje se, zda se má běh smyčky ukončit. Dále můžeme v bajtkódu vidět dvojici instrukcí TFORCALL a TFORLOOP. Instrukce TFORCALL je podobná instrukci CALL, ovšem s tím rozdílem, že se registry obsahující argumenty volané funkce specifikují odlišným způsobem (indexy jsou o dvojku nižší) a předpokládá se, že volaná funkce vrátí jen dvě hodnoty (což platí pro všechny iterátory). Instrukce TFORLOOP provádí podmíněný relativní skok na základě hodnoty uložené ve specifikovaném registru. Pokud je hodnota tohoto registru nil, skok se neprovede, v opačném případě se skok provede na adresu vypočtenou z adresy instrukce TFORLOOP a (záporného) indexu uloženého v instrukčním slovu:
function <Test23.lua:12,16> (11 instructions at 0x9a38c88) 1 param, 9 slots, 1 upvalue, 6 locals, 2 constants, 0 functions 1 [13] GETTABUP 1 0 -1 ; příprava na volání funkce ipairs() [registr číslo 1] 2 [13] MOVE 2 0 ; tabulku/pole uložit do registru číslo 2 3 [13] CALL 1 2 4 ; zavoláni funkce ipairs() [reference uložena v registru číslo 1] 4 [13] JMP 0 4 ; skok těsně před konec programové smyčky [instrukce číslo 9] 5 [14] GETTABUP 6 0 -2 ; příprava na volání funkce print() 6 [14] MOVE 7 4 ; funkce print() vypíše obsah registrů číslo 7 a 8 7 [14] MOVE 8 5 ; -//- 8 [14] CALL 6 3 1 ; zavolání funkce print() s parametry v registrech číslo 7 a 8 9 [13] TFORCALL 1 2 ; volání funkce uložené v registru číslo 1 [ipairs()] ; s parametry R(2) [tabulka] a R(3) ; výsledek volání ulož do R(4) [index] a R(5) [hodnota] 10 [13] TFORLOOP 3 -6 ; pokud platí R(4) ~= nil, proveď relativní skok na instrukci číslo 5 11 [16] RETURN 0 1 ; standardní ukončení funkce
5. Okomentovaný bajtkód funkce sum()
Podobným způsobem, jaký byl popsán v předchozí kapitole, je do bajtkódu Lua VM přeložena i funkce sum(), v níž ovšem došlo ke změně těla programové smyčky „for-each“. Až na tento rozdíl zde můžeme vidět stejnou strukturu bajtkódu, tj. počáteční skok na konec smyčky pomocí instrukce JMP a implementaci iterace s testem s využitím dvojice instrukcí TFORCALL a TFORLOOP:
function <Test23.lua:23,29> (10 instructions at 0x9a39228) 1 param, 8 slots, 1 upvalue, 7 locals, 2 constants, 0 functions 1 [24] LOADK 1 -1 ; načtení konstanty 0 do lokální proměnné sum [registr číslo 1] 2 [25] GETTABUP 2 0 -2 ; příprava na volání funkce ipairs() [registr číslo 2] 3 [25] MOVE 3 0 ; tabulku/pole uložit do registru číslo 3 4 [25] CALL 2 2 4 ; zavolání funkce ipairs() [reference uložena v registru číslo 2] 5 [25] JMP 0 1 ; skok těsně před konec programové smyčky [instrukce číslo 7] 6 [26] ADD 1 1 6 ; přičtení obsahu registru číslo 6 k sumě [registr číslo 1] 7 [25] TFORCALL 2 2 ; volání funkce uložené v registru číslo 2 [ipairs()] ; s parametry R(3) [tabulka] a R(4) ; výsledek volání ulož do R(5) [index] a R(6) [hodnota] 8 [25] TFORLOOP 4 -3 ; pokud platí R(5) ~= nil, proveď relativní skok na instrukci číslo 6 9 [28] RETURN 1 2 ; ukončení funkce s návratovou hodnotou 10 [29] RETURN 0 1 ; standardní ukončení funkce
6. Demonstrační příklad Test24.lua – tabulky použité ve funkci asociativního pole
Dnešní druhý demonstrační příklad, jehož název je Test24.lua, se do značné míry podobá příkladu předchozímu, ovšem s tím rozdílem, že se zde tabulky nevyužívají ve formě polí, ale jako asociativní pole/slovníky, v nichž je každý prvek uložen ve formě dvojice klíč-hodnota, kde klíč je v rámci jedné datové struktury jedinečný. V obou implementovaných funkcích printTable() a sum() se pro průchod polem již nepoužívá funkce ipairs(), ale funkce pairs(). Pořadí prvků získaných v programových smyčkách je náhodné (resp. přesněji řečeno není zaručené, že prvky budou vypsány v takovém pořadí, v jakém byly do tabulky zapsány):
-- -- Demonstracni priklad cislo 24. -- -- Tabulky a programova smycka typu for-each. -- -- -- Vypis vsech prvku tabulky vyuzitych ve funkci pole. -- function printTable(tbl) for i, item in pairs(tbl) do print(i, item) end end -- -- Vypocet souctu vsech prvku tabulky. -- function sum(tbl) local sum = 0 for key, value in pairs(tbl) do sum = sum + value end return sum end -- -- Test. -- function main() local tbl = {first=1, second=2, third=3, fourth=4} printTable(tbl); print("Sum = " .. sum(tbl)) end main()
7. Okomentovaný bajtkód funkce printTable()
Při pohledu na bajtkód funkce printTable() můžeme vidět až nápadnou podobnost s bajtkódem funkce printArray(), která byla použita v předchozím demonstračním příkladu. Jediným podstatným rozdílem je použití pairs() namísto ipairs() pro iterátor, zbylé instrukce bajtkódu jsou totožné, a to díky univerzalitě programové smyčky typu „for-each“ v jazyku Lua:
function <Test24.lua:12,16> (11 instructions at 0x8ec7c88) 1 param, 9 slots, 1 upvalue, 6 locals, 2 constants, 0 functions 1 [13] GETTABUP 1 0 -1 ; příprava na volání funkce pairs() [registr číslo 1] 2 [13] MOVE 2 0 ; tabulku/pole uložit do registru číslo 2 3 [13] CALL 1 2 4 ; zavoláni funkce pairs() [reference uložena v registru číslo 1] 4 [13] JMP 0 4 ; skok těsně před konec programové smyčky [instrukce číslo 9] 5 [14] GETTABUP 6 0 -2 ; příprava na volání funkce print() 6 [14] MOVE 7 4 ; funkce print() vypíše obsah registrů číslo 7 a 8 7 [14] MOVE 8 5 ; -//- 8 [14] CALL 6 3 1 ; zavolání funkce print() s parametry v registrech číslo 7 a 8 9 [13] TFORCALL 1 2 ; volání funkce uložené v registru číslo 1 [pairs()] ; s parametry R(2) [tabulka] a R(3) ; výsledek volání ulož do R(4) [index] a R(5) [hodnota] 10 [13] TFORLOOP 3 -6 ; pokud platí R(4) ~= nil, proveď relativní skok na instrukci číslo 5 11 [16] RETURN 0 1 ; standardní ukončení funkce
8. Okomentovaný bajtkód funkce sum()
Tatáž poznámka, která byla uvedena v předchozí kapitole pro funkci printTable() platí i pro funkci sum() při porovnání s totožně pojmenovanou funkci z předchozího demonstračního příkladu:
function <Test24.lua:23,29> (10 instructions at 0x8ec8228) 1 param, 8 slots, 1 upvalue, 7 locals, 2 constants, 0 functions 1 [24] LOADK 1 -1 ; načtení konstanty 0 do lokální proměnné sum [registr číslo 1] 2 [25] GETTABUP 2 0 -2 ; příprava na volání funkce pairs() [registr číslo 2] 3 [25] MOVE 3 0 ; tabulku/pole uložit do registru číslo 3 4 [25] CALL 2 2 4 ; zavolání funkce pairs() [reference uložena v registru číslo 2] 5 [25] JMP 0 1 ; skok těsně před konec programové smyčky [instrukce číslo 7] 6 [26] ADD 1 1 6 ; přičtení obsahu registru číslo 6 k sumě [registr číslo 1] 7 [25] TFORCALL 2 2 ; volání funkce uložené v registru číslo 2 [pairs()] ; s parametry R(3) [tabulka] a R(4) ; výsledek volání ulož do R(5) [index] a R(6) [hodnota] 8 [25] TFORLOOP 4 -3 ; pokud platí R(5) ~= nil, proveď relativní skok na instrukci číslo 6 9 [28] RETURN 1 2 ; ukončení funkce s návratovou hodnotou 10 [29] RETURN 0 1 ; standardní ukončení funkce
9. Porovnání implementace programové smyčky typu „for-each“ v JVM a Lua VM
Nyní již máme dostatek informací proto, aby bylo možné porovnat implementaci programové smyčky typu „for-each“ ve virtuálním stroji jazyka Java a virtuálním stroji jazyka Lua:
# | Vlastnost | Java a JVM | Lua a Lua VM |
---|---|---|---|
1 | smyčka „for-each“ pro: | pole, kolekce (množina, seznam, mapa) | tabulky |
2 | vlastní implementace iterátoru: | podporována | podporována |
3 | průchod polem: |
for (type variable : array) { tělo smyčky } |
for i, item in ipairs(array) do tělo smyčky end |
4 | průchod polem-dostupný index: | ne | ano |
5 | průchod polem-posloupnost prvků: | zachována | zachována |
6 | průchod polem-indexování prvků: | od 0 do n-1 | od 1 do n |
7 | průchod seznamem: |
for (type variable : list) { tělo smyčky } |
for i, item in ipairs(array) do tělo smyčky end |
8 | průchod seznamem-dostupný index: | ne | ano |
9 | průchod seznamem-posloupnost prvků: | zachována | zachována |
10 | průchod seznamem-indexování prvků: | od 0 do n-1 | od 1 do n |
11 | průchod asoc.polem/mapou: |
for (Map.Entry<typ,typ> item : map.entrySet()) { tělo smyčky } |
for key, value in pairs(map) do tělo smyčky end |
12 | průchod mapou-dostupný index: | ne | ne |
13 | průchod mapou-posloupnost prvků: | „náhodná“ | „náhodná“ |
14 | typ klíče: | reference (kromě null) | cokoli kromě nil |
15 | typ hodnoty: | reference | cokoli včetně nil (=odstraněný prvek) |
16 | for-each pro pole: | bajtkód stejný jako pro počítanou smyčku for | využití instrukcí TFORCALL a TFORLOOP (+funkce ipairs) |
17 | for-each pro seznamy: | bajtkód stejný jako pro smyčku while s iterátorem | využití instrukcí TFORCALL a TFORLOOP (+funkce ipairs) |
18 | for-each pro mapy: | bajtkód stejný jako pro smyčku while s iterátorem | využití instrukcí TFORCALL a TFORLOOP (+funkce pairs) |
10. Repositář se zdrojovými kódy obou dnešních demonstračních příkladů
Dvojice dnes použitých demonstračních příkladů byla uložena do Mercurial repositáře umístěného na adrese http://icedtea.classpath.org/people/ptisnovs/jvm-tools/. Odkazy na prozatím poslední verze těchto příkladů naleznete v tabulce pod tímto odstavcem:
# | Zdrojový kód | Umístění |
---|---|---|
1 | Test23.lua | http://icedtea.classpath.org/people/ptisnovs/jvm-tools/file/e8a8fcf7257f/bytecode/Lua/Test23.lua |
2 | Test24.lua | http://icedtea.classpath.org/people/ptisnovs/jvm-tools/file/e8a8fcf7257f/bytecode/Lua/Test24.lua |
11. Odkazy na Internetu
- For-each Loop in Java
http://www.leepoint.net/notes-java/flow/loops/foreach.html - Programming in Lua (first edition)
http://www.lua.org/pil/contents.html - Programming in Lua: Numeric for
http://www.lua.org/pil/4.3.4.html - Programming in Lua: break and return
http://www.lua.org/pil/4.4.html - Programming in Lua: Tables
http://www.lua.org/pil/2.5.html - Programming in Lua: Table Constructors
http://www.lua.org/pil/3.6.html - Programovací jazyk Lua
http://palmknihy.cz/web/kniha/programovaci-jazyk-lua-12651.htm - Lua: Tables Tutorial
http://lua-users.org/wiki/TablesTutorial - Python 2.x: funkce range()
https://docs.python.org/2/library/functions.html#range - Python 2.x: typ iterátor
https://docs.python.org/2/library/stdtypes.html#iterator-types - Lua: Control Structure Tutorial
http://lua-users.org/wiki/ControlStructureTutorial - Lua Types Tutorial
http://lua-users.org/wiki/LuaTypesTutorial - Goto Statement in Lua
http://lua-users.org/wiki/GotoStatement - Python break, continue and pass Statements
http://www.tutorialspoint.com/python/python_loop_control.htm - For Loop (Wikipedia)
http://en.wikipedia.org/wiki/For_loop - Heinz Rutishauser
http://en.wikipedia.org/wiki/Heinz_Rutishauser - Parrot
http://www.parrot.org/ - Parrot languages
http://www.parrot.org/languages - Parrot Primer
http://docs.parrot.org/parrot/latest/html/docs/intro.pod.html - Parrot Opcodes
http://docs.parrot.org/parrot/latest/html/ops.html - Parrot VM
http://en.wikibooks.org/wiki/Parrot_Virtual_Machine - Parrot Assembly Language
http://www.perl6.org/archive/pdd/pdd06_pasm.html - Parrot Reference: Chapter 11 – Perl 6 and Parrot Essentials
http://oreilly.com/perl/excerpts/perl-6-and-parrot-essentials/parrot-reference.html - Python Bytecode: Fun With Dis
http://akaptur.github.io/blog/2013/08/14/python-bytecode-fun-with-dis/ - Python's Innards: Hello, ceval.c!
http://tech.blog.aknin.name/category/my-projects/pythons-innards/ - Byterun
https://github.com/nedbat/byterun - Python Byte Code Instructions
http://document.ihg.uni-duisburg.de/Documentation/Python/lib/node56.html - Python Byte Code Instructions
https://docs.python.org/3.2/library/dis.html#python-bytecode-instructions - Lua 5.2 sources
http://www.lua.org/source/5.2/ - Lua 5.2 sources – lopcodes.h
http://www.lua.org/source/5.2/lopcodes.h.html - Lua 5.2 sources – lopcodes.c
http://www.lua.org/source/5.2/lopcodes.c.html - dis – Python module
https://docs.python.org/2/library/dis.html - Comparison of Python virtual machines
http://polishlinux.org/apps/cli/comparison-of-python-virtual-machines/ - O-code
http://en.wikipedia.org/wiki/O-code_machine - Java quick guide: JVM Instruction Set (tabulka všech instrukcí JVM)
http://www.mobilefish.com/tutorials/java/java_quickguide_jvm_instruction_set.html - The JVM Instruction Set
http://mpdeboer.home.xs4all.nl/scriptie/node14.html - GC safe-point (or safepoint) and safe-region
http://xiao-feng.blogspot.cz/2008/01/gc-safe-point-and-safe-region.html - Safepoints in HotSpot JVM
http://blog.ragozin.info/2012/10/safepoints-in-hotspot-jvm.html - Java theory and practice: Synchronization optimizations in Mustang
http://www.ibm.com/developerworks/java/library/j-jtp10185/ - How to build hsdis
http://hg.openjdk.java.net/jdk7/hotspot/hotspot/file/tip/src/share/tools/hsdis/README - Java SE 6 Performance White Paper
http://www.oracle.com/technetwork/java/6-performance-137236.html - Lukas Stadler's Blog
http://classparser.blogspot.cz/2010/03/hsdis-i386dll.html - How to build hsdis-amd64.dll and hsdis-i386.dll on Windows
http://dropzone.nfshost.com/hsdis.htm - PrintAssembly
https://wikis.oracle.com/display/HotSpotInternals/PrintAssembly - The Java Virtual Machine Specification: 3.14. Synchronization
http://docs.oracle.com/javase/specs/jvms/se7/html/jvms-3.html#jvms-3.14 - The Java Virtual Machine Specification: 8.3.1.4. volatile Fields
http://docs.oracle.com/javase/specs/jls/se7/html/jls-8.html#jls-8.3.1.4 - The Java Virtual Machine Specification: 17.4. Memory Model
http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4 - The Java Virtual Machine Specification: 17.7. Non-atomic Treatment of double and long
http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.7 - Open Source ByteCode Libraries in Java
http://java-source.net/open-source/bytecode-libraries - ASM Home page
http://asm.ow2.org/ - Seznam nástrojů využívajících projekt ASM
http://asm.ow2.org/users.html - ObjectWeb ASM (Wikipedia)
http://en.wikipedia.org/wiki/ObjectWeb_ASM - Java Bytecode BCEL vs ASM
http://james.onegoodcookie.com/2005/10/26/java-bytecode-bcel-vs-asm/ - BCEL Home page
http://commons.apache.org/bcel/ - Byte Code Engineering Library (před verzí 5.0)
http://bcel.sourceforge.net/ - Byte Code Engineering Library (verze >= 5.0)
http://commons.apache.org/proper/commons-bcel/ - BCEL Manual
http://commons.apache.org/bcel/manual.html - Byte Code Engineering Library (Wikipedia)
http://en.wikipedia.org/wiki/BCEL - BCEL Tutorial
http://www.smfsupport.com/support/java/bcel-tutorial!/ - Bytecode Engineering
http://book.chinaunix.net/special/ebook/Core_Java2_Volume2AF/0131118269/ch13lev1sec6.html - Bytecode Outline plugin for Eclipse (screenshoty + info)
http://asm.ow2.org/eclipse/index.html - Javassist
http://www.jboss.org/javassist/ - Byteman
http://www.jboss.org/byteman - Java programming dynamics, Part 7: Bytecode engineering with BCEL
http://www.ibm.com/developerworks/java/library/j-dyn0414/ - 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 - aspectj (Eclipse)
http://www.eclipse.org/aspectj/ - Aspect-oriented programming (Wikipedia)
http://en.wikipedia.org/wiki/Aspect_oriented_programming - AspectJ (Wikipedia)
http://en.wikipedia.org/wiki/AspectJ - EMMA: a free Java code coverage tool
http://emma.sourceforge.net/ - Cobertura
http://cobertura.sourceforge.net/ - jclasslib bytecode viewer
http://www.ej-technologies.com/products/jclasslib/overview.html