A Brief Stratego XT Tutorial

Karl Trygve Kalleberg Eelco Visser

Description

A Brief Stratego/XT TutorialKarl Trygve KallebergEelco VisserDagstuhl Workshop: Beyond Program Slicing, 7.-11. Nov 2005Plan of AttackI Explain the basics of StrategoI Terms, signatures, rewrite rules, strategies, concrete syntax,dynamic rulesI Motivate with a small case-studyI Constant propagationI Give a tiny tool demoI Take questionsOutline1 Motivation2 Terms and Signatures3 Transformation Rules4 Transfo Strategies5 Dynamic RulesPart IMotivationfor i := 1 to n dofor j := 1 to n doc[i,j] := let var d := 0in for k := 1 to n dod := d + a[i,k] * b[k,j];dendlet var din for i := 1 to n dofor j := 1 to n do(d := 0;for k := 1 to n do d := d + a[i,k] * b[k,j];c[i,j] := d)endExample: Desugaringfor i := 1 to n dofor j := 1 to n doc[i,j] := sum k = 1 to n (a[i,k] * b[k,j])let var din for i := 1 to n dofor j := 1 to n do(d := 0;for k := 1 to n do d := d + a[i,k] * b[k,j];c[i,j] := d)endExample: Desugaringfor i := 1 to n dofor j := 1 to n doc[i,j] := sum k = 1 to n (a[i,k] * b[k,j])for i := 1 to n dofor j := 1 to n doc[i,j] := let var d := 0in for k := 1 to n dod := d + a[i,k] * b[k,j];dendExample: Desugaringfor i := 1 to n dofor j := 1 to n doc[i,j] := sum k = 1 to n (a[i,k] * b[k,j])for i := 1 to n dofor j := 1 to n doc[i,j] := let var d := 0in for k := 1 to n dod := d + a[i,k] * b[k,j];dendlet var din for i := 1 to n dofor j := 1 to n do(d := 0;for k := 1 to n do d := d + a[i,k] * b[k,j];c[i,j] := d)endThe ...

Informations

• Publié par: Onfue
• Nombre de lectures: 20
• Langue: English

Extrait

Dagstuhl

A

Brief Stratego/XT Tutorial

Karl Trygve Kalleberg Eelco Visser

Workshop: Beyond Program Slicing, 7.-11.

Nov

2005

Plano

I

I

I

I

fAttack

Explain the basics of Stratego I Terms,signatures,rewrite rules,strategies,concrete syntax, dynamic rules Motivate with a small case-study I Constant propagation

Give a tiny tool demo

Take questions

uOlti

1

2

3

4

5

ne

Motivation

Terms and Signatures

Transformation

Transformation

Dynamic Rules

Rules

Strategies

Part

I

Motivation

xaElempes:Dragugni f j:or o f ndto=1i:or +d=:,i[a ot1= d odn d e ]; le nd *bk],j[k i[j,:]l= 1=otdn c o 0 infork: etvard:= +d[ado=:b*k[,i]k ; for d:=0 tondk:=1 :jrof odn ( odnot1= nf d i artv to=1i:or

for i := 1 for j := c[i,j]

to n do 1 to n do :=sum k =

d

(a[i,k]

n

to

1

b[k,j])

*

];,j i,c[:=j] en d)

0; fo (d:= ondo:=1t d=a+od:dt1nokr=: [i ; c j]k,b[]*,k[i

(a[i,k] * b[k,j])

n

1 to

for i := 1 for j := c[i,j]

to n do 1 to n do :=sum k =

dne )d=:]j, vaet in rdl odno jrof iroft1=:

end

to n do 1 to n do :=let var in for d d

d := k := := d

for i := 1 for j := c[i,j]

to n do a[i,k] *

0 1 +

b[k,j];

ngrigasuDee:plamxE

Example:Dseguaring

for i := 1 to n do for j := 1 to n do c[i,j] :=sum k = 1 to n (a[i,k] * b[k,j])

for i := 1 to n do for j := 1 to n do c[i,j] :=let var d := 0 in for k := 1 to n do d := d + a[i,k] * b[k,j]; d end

let var d infor i := 1 to n do for j := 1 to n do (d := 0; for k := 1 to n do d := d + a[i,k] * b[k,j]; c[i,j] :=d)

end

TheBigPicture

A Simple Pipeline

1

2

3

4

5

Source code isparsedinto astructuredrepresentation, a concrete syntax tree(CST).

The CST is pruned for non-essential information, to yield abstract syntax tree(AST).

Additional information is added, e.g. type information.

One or multipletransformationsare applied to the AST.

The result is serialized back to file.

an

hTeSmalliPtcuer

Thesyntax definitiondeclares programs we transform and is stages.

thestructureof the used in constructing

language for the most pipeline

Terms

Part

and

I

I

Signatures

Tersm

I Terms are astructured representationof programs. I Their structure is often derived from the syntax definition of the language. I The syntax definition gives rules for the structural validation of terms.

Terms are primarily used to encodeabstract syntax trees.