.so tmac.ppt
.de X1
.br
.ne 2.5i
.mk
.P1
.ps 20
.vs 22
..
.de X2
.P2
.rt
.P1
.in +3i
.ps 20
.vs 22
..
.de X3
.P2
..
.TL
.sp -2
\f(CWrscc\fP: an extensible compiler
.AU
.nf
Russ Cox
Frans Kaashoek
Eddie Kohler
.sp 2
.ft R
PDOS Group Meeting
.br
January 24, 2006
.sp 2
.CW http://swtch.com/~rsc/talks/
...
.SL "Problem (big picture)
Programs are buggy.
Because programming languages don't work for you.
You work for them.
How do you resolve mismatch between
programming task and language?
.SL "Outline
Problem \- 5 slides
Specific Extensions \- 10 slides
How to Implement \f(CWrscc\fP \- 10 slides
\- parser
\- internal representation
Please interrupt with questions.
.SL "Good Languages?
.nf
Some languages make some bugs easier to avoid / find.
\- good abstractions
\- type systems
Never good enough.
People extend languages any way they can.
\- C preprocessor (easy, but rarely good)
\- custom preprocessors (good, but rarely easy)
\- custom checkers
.SL "Useful Preprocessors
.nf
Click (Kohler)
\- language to describe module properties, router configs
Tame (Krohn)
\- more convenient syntax for libasync
\- (Even \f2I\fP can write tame programs!)
Ace (Gosling)
\- syntax-based preprocessor, used for bitblt
QT Rewriter
- used for simpler event syntax in QT library
.SL "Useful Checkers
.nf
Magik (Engler)
\- checking of flow-sensitive conditions, using xgcc
\- more recent work about guessing things to check
Uno (Holzmann)
\- another static checker, actually available.
Sparse (Torvalds)
\- add annotations to Linux source for lock/unlock pairing,
kernel/user address spaces
.SL "Implementation Techniques
.nf
Start from scratch
\- lots and lots of work, requires knowing about compilers
Edit an existing compiler
\- lots of work, requires knowing about compilers,
requires \fIknowing\fP that particular compiler
.SL "Problem (recap)
.nf
Programs are buggy.
Because languages aren't good for programming.
Lots of good can come from tailoring the language.
But it's far too much work for most programmers.
How can we lower the bar?
.SL "Solution: Extensible Compiler
.nf
Extensible compiler
\- let programmers add extensions (\f(CW.so\fP files)
to the compiler during compilation.
\- extensions are separate from programs that use them
(think media-player codecs)
\- extensions add new language features, new checking
\- make it easy to write these extensions
\- hide compiler when possible
\- make compiler easy to understand
.SL "Solution: Extensible compiler
.PE
Extensible compiler, without extensions:
.PS
X1: box wid 1.5 ht 0.35 "\f(CWrscc\fP"
SRC: box invis wid 2 "C program" with .e at X1.w-(1,0)
OBJ: box invis wid 2 "executable" with .w at X1.e+(1,0)
arrow from SRC.e to X1.w-(.2,0)
arrow from X1.e+(.2,0) to OBJ.w
SRC2: box invis wid 2 "" "" with .n at SRC-(1,0)
.PE
Extensible compiler, with one extension:
.sp
.PS
X1: box wid 1.5 ht 0.35 "\f(CWrscc\fP"
SRC: box invis wid 2 "program" "using" "extension" with .e at X1.w-(1,0)
OBJ: box invis wid 2 "executable" with .w at X1.e+(1,0)
arrow from SRC.e to X1.w-(.2,0)
arrow from X1.e+(.2,0) to OBJ.w
SRC2: box invis wid 2 "extension" "source" with .n at SRC.s-(1,1)
X2: box wid 1.5 ht 0.35 "\f(CWrscc\fP" with .w at SRC2.e+(1,0)
OBJ2: box fill 0.9 wid 1.5 ht 0.35 "\f(CWext.so\fP" at X1.se-(.25,.1)
arrow from SRC2.e to X2.w-(.2,0)
spline -> from X2.e+(.2,0) to OBJ2.s-(0,1) then to OBJ2.s
.PE
.SL "Expected Uses
.nf
Extensions are usually small (and can start small).
Programmers write compiler extensions
while writing the programs that use them.
Project leaders write compiler extensions
to make big project easier for others.
Net work should be less than not using extensions.
Make possible the language changes mentioned earlier.
.SL "Example Extension: Alef
.LP
.X1
.in 0
.in -0.5i
void
primetask(chan(int) c)
{
chan(int) nc;
int i, p;
p = <-c;
print("%d\en", p);
alloc nc;
task primetask(nc);
for(;;){
i = <-c;
if(i%p)
nc <-= i;
}
}
Alef original
.X2
.in -4i
void
primethread(void *arg)
{
Channel *c, *nc;
int i, p;
c = arg;
p = recvul(c);
print("%d\en", p);
nc = chancreate(sizeof(ulong), 0);
threadcreate(primethread, nc, 1024);
for(;;){
i = recvul(c);
if(i%p)
sendul(nc, i);
}
}
C transliteration
.X3
.SL "Example Extension: Alef
.X1
Alef
chan(int) nc;
alloc nc;
task primetask(nc);
nc <-= i;
.X2
C + libthread
Channel *nc;
nc = chancreate(sizeof(ulong), 0);
threadcreate(primethread, nc, 1024);
sendul(nc, i);
.X3
Benefits of Alef:
\- more concise, more readable.
\- type-checked channels.
\- good thread creation syntax.
\- good communication syntax (\f(CWalt\fP)
Alef is dead.
\- compiler author moved on.
\- those left behind switched to C.
gave up the benefits for ease of maintenance
.SL "Example Extension: Tame
.X1
.ta +2n +2n +2n
TAME(static void
try_connect(str h,
int port))
{
VARS { int fd; }
BLOCK{ tcpconnect(h,
port, @(fd)); }
if(fd < 0)
warn << h << "\en";
exit(0);
}
Tame TCP client.
.X2
static void cb1(str, int);
static void try_connect(str h,
int port)
{
tcpconnect(h, port,
wrap(cb1, h));
}
static void cb1(str h, int fd)
{
if(fd < 0)
warn << h << "\en";
exit(0);
}
Equivalent libasync
.X3
.SL "Example Extension: Tame
.X1
.ta +2n +2n +2n
TAME(static void
try_connect(str h,
int port))
{
VARS { int fd; }
BLOCK{ tcpconnect(h,
port, @(fd)); }
if(fd < 0)
warn << h << "\en";
exit(0);
}
Tame TCP client.
.X2
static void cb1(str h, int fd)
{
if(fd < 0)
warn << h << "\en";
exit(0);
}
static void try_connect(str h,
int port)
{
tcpconnect(h, port,
wrap(cb1, h));
}
Libasync in the wild.
.X3
.SL "Example Extension: Tame
.X1
VARS { int fd; }
BLOCK{ tcpconnect(h,
port, @(fd)); }
exit(fd);
.X2
static void cb1(void) {exit(fd);}
tcpconnect(port, wrap(cb1));
.X3
Benefits of Tame:
\- more concise, more readable
\- does not encourage upside-down programming
\- easy to handle multiple parallel threads-of-control
\- can write structured programs again (\f(CWif\fP, \f(CWfor\fP, ...)
.SL "Example Extension: Plan 9 Kernel Checker
.nf
Plan 9 kernel has many conventions to remember:
(So does any large program.)
\- lock/unlock pairing
\- no sleeping in interrupt handlers
\- interrupt handlers must use ilocks
\- exception stack for error handling
\- kernel/user pointers
\- no dereferencing user pointers in interrupt handlers
\- ...
Many are checked at run-time.
No fundamental reason not to check at compile time.
.SL "Example Extension: Plan 9 Kernel Checker
.nf
Add attributes to document and enforce conventions.
.P1
.ps 20
.vs 22
void *ialloc(int) attribute(nosleep);
void *malloc(int) attribute(nosleep);
void print(char*, ...);
void*
ialloc(int n)
{
void *v;
v = malloc(n);
return v;
}
.P2
.SL "Example Extension: Plan 9 Kernel Checker
.nf
Add attributes to document and enforce conventions.
.P1
.ps 20
.vs 22
void *ialloc(int) attribute(nosleep);
void *malloc(int) attribute(nosleep);
void print(char*, ...);
void*
ialloc(int n)
{
void *v;
v = malloc(n);
.RGB 0.75 0 0
if(v == nil)
print("ialloc returning nil\en");
.CO black
return v;
}
.P2
.ps
.L1
Compiler can tell programmer he made a mistake.
.SL "\f(CWrscc\fP overview
.nf
Front end only
\- compile to low-level C and invoke \f(CWgcc\fP
Written using itself
Extensible LR(1) parser
Extensible grammar notation
Destructuring syntax
Restructuring syntax
Other extensions as convenient
.SL "Extensible LR(1) parser
.nf
Shift-reduce parsers run an NFA on input.
\- NFA says shift or reduce at each step
Parse \f(CWx * x + x
x * x + x shift
x * x + x shift
x * x + x reduce x => x*x
x + x shift
x + x shift
x + x reduce x => x+x
x
.ft
.SL "Extensible LR(1) parser
.nf
Shift-reduce parsers run an NFA on input.
\- NFA says shift or reduce at each step
\- NFA corresponds exactly to grammar rules
\f(CWYacc\fP precomputes, hard-codes equivalent DFA.
New parser for rscc:
\- run determinization on the fly, caching result.
\- if grammar changes, throw away DFA built so far.
\- normal C library interface
.P1
yynewsym(g, "\e"**\e"", 0);
yylexnewsym(g, "\e"**\e"");
yyrulestr(g, yyaction, "expr", "expr", "\e"**\e"", "expr", 0);
.P2
.SL "Grammar Syntax
.nf
Use an extension to present a better parser interface.
.P1
yacc {
yaccsym right "**" %prec "*";
expr: expr "**" expr;
}
.P2
.L1
Compiles into appropriate function calls.
Provides default \f(CWyyaction\fP rule
that builds an abstract syntax tree node.
.SL "Destructuring Syntax
.nf
Need to make abstract syntax tree nodes accessible.
Don't want extension writer to need to know internal representation.
Provide matching operator \f(CW~\fP for destructuring syntax.
.P1
Node *a, *b, n;
if(n ~ `expr{ \ea**\eb })
warn("using **: base=%N exponent=%N", a, b);
.P2
.SL "Restructuring Syntax
.nf
Same syntax as destructuring, but used as expression
instead of next to \f(CW~\fP.
.P1
Node *n, *a, *b;
if(n ~ `expr{ \ea**\eb })
n = `expr{ pow(\ea, \eb) };
.P2
.L1
The \f(CWa\fP and \f(CWb\fP are substituted as units,
not as token streams.
.P1
int x;
Node *n, *nn;
x = 2;
n = `expr{ 1+\ex };
nn = `expr{ \en*3 };
.P2
.SL "Extensible Functions
Linked list of function pointers implementing a function.
Each function can handle a call itself,
with or without invoking next function in the list.
Syntax codifies the idiom.
.P1
extend
Node*
compile(Node *n)
{
Node *a, *b;
if(n ~ `expr{ \ea**\eb })
return compile(`expr{ pow(\ea, \eb) });
return default;
}
.P2
.SL "Extensible data structures
Same idea as functions; not sure of implementation.
.P1
extend
struct Node
{
int extra;
int other;
int field;
};
.P2
.SL "Other extensions: iterators
.P1
static int start(State *z, Rule *r);
static int next(State *z, Sym **s);
static int end(State*);
iterator(start, next, end);
Rule *r;
Sym *s;
for(s in r)
something(s);
.P2
.SL "Related Work
.nf
Lots of macro systems
\- can't write checkers with those.
\- often run into scoping problems
Other extensible languages/compilers
\- require programmers to know too much about internals
\- not easy enough to write extensions
.SL "Status
\f(CWRscc\fP exists.
\- uses extensible grammar, yacc syntax
\- provides its own grammar action functions
\- uses restructuring, not destructuring
\- uses extensible functions heavily
\- no extensible data structures yet
\- uses iterators heavily
\- know how to switch over to implicit
actions and destructuring
\- need to find ways to hide other aspects
of compiler internals (types, flow control, ...)
\- submit to OSDI
\- always looking for more target uses
|
