Transcript JTSx - UT Computer Science

The Jakarta Tool Suite
Don Batory
Department of Computer Sciences
University of Texas at Austin
1
Introduction
 Central
problems in Software Engineering
stem from one fact:
software is written by hand
 Complaints
about the lack of:
– quality, performance, reliability,
maintainability, evolvability
2
Quality of Software
 Function
of:
– basic design
» “build it several times to get it right”
» designs improved with experience
– programming staff
 How
can we do better?
– to exploit previous experiences?
– to improve quality of programmers?
3
Future of Software Engineering
 Automated
production of rote software
» major improvements in: performance, reliability,
quality…
 Domain-specific
component technologies
» engineering approach that standardizes:
designs (programming problems)
 implementations (programming solutions)

4
Generators
 Generators
are tools that:
– transform component compositions into code
– validate compositions automatically
– automatic customizations and optimizations
 Software
quality improved
– use good designs, expert programmers
– expect good performance & reliability,
easier maintenance, extensibility
5
What are Generators?
 Generators
are compilers for:
– domain-specific languages
– general-purpose programming languages with
domain-specific extensions
 Problem:
– generators are hard to build
– programming infrastructure is lacking
– 60% of effort focuses on infrastructure
6
The Jakarta Tool Suite (JTS)
– for building component technologies and
generators in Java
» based on experiences in building multiple generators
» compiler tools (POPART, Dialect, TXL), MS’s IP
– for language extensibility
» creates preprocessors for domain-specific languages
(DSLs) or embedded DSLs
– for architectural optimizations needed for selfadaptive software
7
Language Extensibility isn’t new...
– LISP macros & CLOS meta-object protocols
– Language extensibility of JTS based on different
packaging architectural extensibility
» same techniques used in avionics, network protocols,
database systems were applied to programming languages
» unit of extensibility is a “layer” or
“building block” of a family of programming languages
8
This Presentation...
– Jak Language
open, extensible version of Java
 its basic features

– Bali Generator
of customized dialects of Jak
 (product-line of dialects of Java)

– Adaptive Software

demo
– Status Report and Conclusions
9
The Jak Language
open, extensible superset of Java
examine “base” extension
10
Support for Metaprogramming
 Extends
Java with:
– AST constructors
» represent and manipulate programs as data
» adds LISP quote/unquote to Java
– AST traversals, manipulation
» arbitrary program transformations
– Generation scoping
» variant of hygienic macros
11
AST Constructors
 Added
constructors for code fragments of
different types (expression, statement, …)
» similar to LISP quote
AST_Exp
AST_Stm
e
s
=
=
e.unparse( );
s.unparse( );
exp{
stm{
7 + x*8 }exp;
if (y>4) return r; }stm;
// outputs “7 + x*8”
// outputs “if (y>4) return r;”
12
Parameterization and
Composition of Code Fragments
 Explicit
escapes
» LISP unquote
AST_Exp
e
=
exp{ 7 + x*8 }exp;
AST_Exp
s
=
stm{ if (($exp(e))>4)
return r;
}stm;
s.unparse( ):
// outputs:
“ if ((7+x*8)>4) return r; ”
13
AST Constructors (Continued)
 Focusing
on AST constructors for Java
(or extended Java)
 Add
–
–
–
–
AST constructors for other languages
CORBA IDL
Embedded SQL
(subsets of) C, C++
...
14
The Binding Problem
macro(x) {
int temp = 2*x;
… }
Macro Definition
int temp = 5;
macro(temp);
Application Code
int
int temp
temp =
=
{
{ int
int temp
temp
…
… }
}
Bogus Generated
Code
5;
5;
=
= 2*temp;
2*temp;
Hygienic, lexically scoped macros (HLSM)15
Generation Scoping
 Generalization
of HLSM for generators
» Y. Smaragdakis added to Microsoft’s IP
» validated with DiSTiL
» convenient solution to “binding problem”
 Different
than HLSM
» generators are not reflective, macro-based
» GS allows you to maintain the name-space of the
generated program
» generator language different than generated language
16
AST Traversals
 Package/classes
for depth-first searches,
manipulations
» support arbitrary program transformations
AstCursor
Ast_Node
c = new AstCursor( );
root = // root of AST to search
for (c.First(root); c.More( ); c.PlusPlus( ) )
if (c.node instanceof AstInterface)
c.Delete( );
17
How Jak Works
18
SSTs versus ASTs
 Surface
syntax tree (SST) is a syntactically
correct parse tree
» tree constructors, modifiers guarantee syntactic
correctness
» SSTs may not be semantically correct
 Abstract
syntax tree (AST) is a typechecked SST
» with annotations to symbol table
» invoked by typecheck( ) method to root of SST
19
Extensibility of SST/ASTs
 “Intentions”
– add AST nodes with domain-specific semantics
» P3 adds cursor, container types to Java
– at reduction time, intention nodes are replaced
with their Java (or host language)
implementations
» P3 replaces cursor, container AST nodes with their
20
concrete Java implementations
Jakarta Follows DSL Paradigm
domain
specific
program
Written in Jak
lexer
and
parser
AST
transform
program
Jak
Java
program
21
More Detail: Processing in Phases
Parser creates SST of
a domain-specific program
Jak type checks SST
to convert to AST
Jak replaces intentions
with SSTs
If necessary, SSTs can be
type checked to form ASTs
intentions
22
Big Picture
 JTS/Jak
is technology marriage of:
– Java
– metaprogramming concepts
» quote, unquote, generation scoping (HLSM)
– intention-based programming and
transformation systems
 Inherently
“open” compiler
23
How to...
 Produce
lexers and parsers?
 Produce
transform program?
 Where
does GenVoca fit in?
answers in remainder of talk...
24
Bali
GenVoca Generator of
Precompilers of Java Dialects
25
Family Languages
 Jak
is a family of related languages
» versions with/without constructors
» with/without P3 extensions
» with/without CORBA IDL extensions…
 Classic
library scalability problem
» n optional, largely orthogonal features
» 2n different possible combinations of features
» cannot build all 2n combinations by hand
» can generate them
26
Bali is a GenVoca Generator
 Bali
assembles variants of Jak from
components
 Components encapsulate primitive
extensions
» generation scoping
» domain-specific generators like P3
» CORBA IDL
»…
 Compositions
of components specifies
particular variant
27
Two Aspects
 Tool
for writing compilers for
Domain-Specific Languages (DSL)
– looks similar to other DSL-compiler tools
– specify syntax of DSL or language extension
– annotated, extended BNF grammars
 GenVoca
generator
– software component technology
– architectural, extensibility aspects
28
Domain-Specific Language
Compiler Tool
29
Bali Grammars
 Extended
BNF grammar
» extended to handle repetitions
» e.g., POPART
StatementList
: ( Statement )+
;
ArgumentList
: Argument ( ‘,’ Argument )*
;
30
Bali Grammars
 Annotated
» by class to instantiate when production is recognized
» POPART, DIALECT, common OO design techniques
SelectionStmt
: IF ‘(’ Expr ‘)’ Statement
| SWITCH ‘(’ Expr ‘)’ Block
;
:: IfStm
:: SwitchStm
constructors: IfStm( token, token, ASTexp, token, ASTstm )
SwitchStm( token, token, ASTexp, token, ASTblk31)
Inheritance Hierarchies
 is
deduced from DSL grammar
Rule1 :
|
;
pattern1
Rule2
Rule2 :
|
;
pattern2
pattern3
Rule1
:: C1
C1
:: C2
:: C3
Rule2
C2
C3
32
Bali Specifications
 Jak
– 170 tokens
– 400 productions
– 800 lines
// bali spec
lexical patterns
%%
grammar rules
grammar

Bali grammar
– 15 tokens
– 20 productions
– 73 lines
33
What can be generated...
 Lexical analyzer
» Jlex (java version of lex)
» Bernie Lofaso (Jakarta Team Member)
 Parser
» Java_Cup (java version of yacc)
» Scott Hudson@Georgia Tech
 Inheritance
Now moving
to JavaCC
hierarchy and AST classes
» constructors, unparsing, editing methods
34
What can’t be generated...
 Type
checking, reduction, optimization
methods
– AST node specific
– hand code as subclasses to Bali-generated class
AstNode
JTS kernel class
IfStm’
SwitchStm’
…
Bali-generated classes
IfStm
SwitchStm
…
Hand-coded subclasses
35
Big Picture
 Traditional
approach to building compilers
for domain-specific languages

clean model of proven technology
 Problem:
don’t want to hand-code and
hand-assemble each variant

too expensive
 Solution:
GenVoca component technology
components encapsulate primitive extensions
 compose components to form variants of Jak

36
GenVoca Generators
37
GenVoca
 Model
of parameterized programming
– addresses the architectural aspects of software
– building blocks of domains are refinements of
fundamental domain abstractions
– components are implementations of refinements
– components composed by parameter instantiation
 visualize
layers
component composition as stacking
38
Quick Tutorial
 Components
define algebraic operators
 Software system is type equation
System:
Z
System = Z[ Y [ X ] ]
Y
X
Question: what is relationship
of components to classes?
39
OO Realizations of Refinements
A
small-scale refinement adds new data
members, methods, and/or overrides
existing methods to a class
class
subclassing relationship
subclass
40
Large Scale Refinement
 Adds
new data members and methods
simultaneously to several classes
class
class
class
subclass
subclass
subclass
41
Relationship to GenVoca
 GenVoca
components are large scale
– consistent refinements of multiple classes
application classes
42
Relationship to JTS
AstNode
Guard
With
Java
Kernel
Application Classes
43
To Scale, Not to Scale...
AstNode
Guard
With
Java
Kernel
>500 classes
J1 = Guard[ With[ Java[ Kernel ] ] ];
44
Express Components as Mixin
Layers
– Mixins are classes whose superclass is
specified via a parameter
– Components are expressed as a mixin (whose
superclass is the “lower layer”)
» inner classes themselves are mixins
Component
x
y
z
w
45
Mixin-Layer Construction
Guard
With
Java
Kernel
Elegant model of component-based software construction
46
Big Picture
 Bali
is marriage of:
– DSL compiler technology
– GenVoca generator technology
 Bali
synthesizes versions of Jak thru
component composition
– automatic synthesis of lexer, parser, transform
engine
– can synthesize variants of other languages, too
47
Current Status
and Future Work
48
Current JTS Language
Component Definition
and Composition
Compose
LayerDef
Macros
Embedded DSL
GenVoca Generator
for Containers
P3
SymTab
Legend
Match
Metaprogramming
AST Constructors
Hygienic Macros
Base Language
GScope
AST
1998
1997
Java1.1
Java1.0
49
Current Status
 Jakarta
now supports:
» AST constructors and escapes
» generation scoping
» parameterized inheritance (mixin layers)
» P3 generator of container data structures
 Add
type checking to AST nodes
» needed for semantics-based transformations
 FSATS
» Fire Support Automated Test System
50
Self-Adaptive Software
– JTS represents applications as equations
S=
A
B
S = A[ B[ C ] ];
C
– Users need help:
» selecting components
» knowing combinations that satisfy requirements
express such knowledge as algebraic rewrite rules
51
Design Wizard
– Applies rewrite rules to optimize equations
– Space of all implementations = space of all
type equations
– Rank “goodness” of a Teqn by generating cost
functions that estimate performance
– Walk space (heuristically) to locate Teqn with
cheapest cost
52
Simple Application using P3
 Spelling
checker
» two containers, 1 for dictionary, another for document
» initially are simple lists, optimally are hash or rbtrees
with hash comparison optimizations
Cont = list[transient]
Code = rbtree[word, ... ]
53
Self-Adaptivity
 Let
application monitor
its workload
 Design
Wizard deduces
better implementation
 Jak
regenerates
application
Self-Adaptive Cycle
Design Wizard
regenerated
application
updated
requirements,
actual
workloads
Application
54
Self-Adaptivity
– Concept of rewriting type equations is domainindependent
– Interesting problem when there are lots of
components that implement the same
functionality in different ways

this is where optimization problems arise
– Matter of analyzing additional domains and
applying this technology
55
Conclusions
 JTS
integrates of different technologies:
» metaprogramming
» domain-specific language compiler tools
» architectural view: components/generators
 Yields
a powerful set of tools for creating
» component technologies and their generators
 Embody
useful advance
» generator infrastructure
» automating software development
56
The End
57
Timings
 How
Jak works -14min
 Bali - 4min
 up to GenVoca - 9 min
 up to current status - 10 min
 current status - 11 min
 Total:
48 min.
58