The Shape of Kotlin

At Kotlin Day 2019 in London, I share how I stumbled on to AST parsing, debunk the Kotlin compiler, and share how 47 Degrees is taking advantage of AST parsing to elevate the power of Kotlin metaprogramming.

1. 47deg.com The Shape of Kotlin AST Parsing and its role in the Kotlin compiler Amanda Hinchman-Dominguez
2. 47deg.com The Shape of Kotlin • How I stumbled on to AST parsing • Debunk the black box that is the Kotlin Compiler • How 47 Degrees is leveraging AST parsing in Arrow-meta elevate the power of Kotlin metaprogramming 2 Amanda Hinchman-Dominguez
3. 47deg.com 3
4. 47deg.com 4 Detecting UI inputs Amanda Hinchman-Dominguez • Abstract Syntax Tree Parsing (AST) • Program Structure Interface (PSI)
5. 47deg.com 5
6. 47 Degrees is a global consulting firm and certified LightBend and Databricks Partner 47deg.com Specializing in 6
7. We love Open Source! contributors stars repositories languages 656 3217 93 18 47deg.github.io
8. 47deg.com 8 The Kotlin compiler is scary!
9. 47deg.com 9 By studying AST, we can learn a lot of about the Kotlin compiler.
10. 47deg.com 10 What is an Abstract Syntax Tree (AST)?
11. 47deg.com • AST is a form of abstracted representation that is generated and used in several roles within the compiler • AST is a tree made of nodes that have direct mapping to the text ranges in the underlying document 11 Bottom-most nodes of an AST matches individual tokens Higher nodes matches multiple-token fragments
12. 47deg.com What does AST parsing tell us? Amanda Hinchman-Dominguez • AST parsing tells us how code has been written by the end user • AST parsing gives all but punctuation in the analyzed text range including tokens 12
13. 47deg.com Amanda Hinchman-Dominguez 13 Element.BINARY_EXPRESSION Element.INTEGER_CONSTANT Element.INTEGER_CONSTANT Token.PLUS Token.INTEGER_LITE RAL Token.INTEGER_LITE RAL 2 + 3
14. 47deg.com Amanda Hinchman-Dominguez 14 Element.INTEGER_CONSTANT Element.CALL_EXPRESSION Element.DOT_QUALIFIED_EXPLANATION Token.DOT Token.NUMBER Token.IDENTIFIER 2.plus(3) Element.REFERENCE_ EXPRESSION Element.VALUE_ARGUMENT_LIST Token.LPAR Token.RPAR Element.VALUE_ARGUMENT 14 Element.INTEGER_CONSTANT Token.INTEGER_LITERAL
15. 47deg.com 15 The Kotlin Compiler
16. 47deg.com Amanda Hinchman-Dominguez Parsing Phase • Builds the AST tree • Analyzes the tree and augments with complete information
17. 47deg.com Amanda Hinchman-Dominguez • The basis for any compiler optimization • Transforms the input program into unoptimized intermediate representation • Generates Program Structure Interface (PSI) Analysis Phase
18. 47deg.com Amanda Hinchman-Dominguez • Generates 2 symbol tables: ◦ One to accompany AST ◦ Another for the associating generated IR model • PSI enhanced with descriptors which have been typed-checked • Optimizations performed on IR to improve quality and performance of machine code Resolution Phase
19. 47deg.com Amanda Hinchman-Dominguez • Transforms IR into the native machine language Codegen
20. 47deg.com 20 What role(s) does AST play in the Kotlin compiler?
21. 47deg.com Amanda Hinchman-Dominguez • Lexer breaks code text into a sequence of lexical token • Lexer may break code into multiple fragments while scanning or into lexemes Lexer
22. 47deg.com Amanda Hinchman-Dominguez Builds the AST tree. The parse tree is often: • Analyzed • Augmented • Transformed In later phases of the compiler Syntax Analyzer
23. 47deg.com Amanda Hinchman-Dominguez • Compiler checks the AST tree for type checking and semantic analysis • Generates symbol table & IR Semantic Analyzer
24. 47deg.com Amanda Hinchman-Dominguez • Outputs unoptimized intermediate representation (IR) • Analysis performed on IR ◦ Control flow ◦ Call stacks Intermediate Code Generator
25. 47deg.com Amanda Hinchman-Dominguez • Machine-dependent optimizations on IR • Improves performance & quality of produced machine code • Resource & storage decisions Intermediate Code Optimizer
26. 47deg.com 26 How does AST relate to PSI?
27. 47deg.com Amanda Hinchman-Dominguez 27 Element.BINARY_EXP RESSION Element.INTEGER_LITERAL Element.INTEGER_LITERAL Element.FILE Token.PLUS Token.NUMBER INTEGER_LITERAL AST Tree 2 + 3
28. 47deg.com Amanda Hinchman-Dominguez 28 KtBinaryExpression KtConstantExpression KtConstantExpression KtFile PSI Tree 2 + 3
29. 47deg.com 29 PsiViewer Plugin
30. 47deg.com 30 AST/PSI vs. Descriptors vs. IR?
31. 47deg.com Amanda Hinchman-Dominguez • IR is generated as another form of abstracted representation for CPU-level architecture • PSI and IR each have symbol tables mapping their nodes to descriptors PSI Descriptor IR
32. 47deg.com A sneak peek into Arrow-meta Run Wild, Run Free! 32
33. 47deg.com Arrow-meta intercepts AST & its resulting models • AST allows us to alter the surface level of language without changing the rest of the compiler (although we can and usually do) 33
34. 47deg.com 34
35. 47deg.com 35
36. 47deg.com 36
37. 47deg.com 37
38. 47deg.com 38
39. 47deg.com 39
40. 47deg.com 40
41. 47deg.com 41
42. 47deg.com 42
43. 47deg.com 43
44. 47deg.com KEEP Insisting! - KotlinConf 2019
45. Thank you! 47deg.com
46. 47deg.com 46 • Arrow-meta: https://github.com/arrow-kt/arrow-meta • Kotlin compiler crash course: https://github.com/ahinchman1/Kotlin-Compiler-Crash-Course Sources Cited