requirements gathering on mini transformation language

[Allison Randal]

I need a volunteer write up the requirements for a mini transformation
language to use in the compiler tools. You wouldn't have to write up the
specification for the language, just what features we need. This will
help us plan what it's going to take to get from here to there, and give
us a way to measure when the spec/implementation can be called "done".

It's essentially a matter of spending some time with me and Patrick on
the phone and solidifying the ideas on paper, together with any
perspectives or experience you add to the mix.

Allison

[Markus Triska]

Allison Randal writes:

> mini transformation language to use in the compiler tools.

For what purpose, roughly? I've some experience with rule-based
peep-hole optimisations. If it's in that area, I volunteer.

Best wishes,
Markus Triska

[Chromatic]

On Thursday 28 September 2006 14:51, Markus Triska wrote:

> Allison Randal writes:
> > mini transformation language to use in the compiler tools.
>
> For what purpose, roughly? I've some experience with rule-based
> peep-hole optimisations. If it's in that area, I volunteer.

That's part of it, but mostly it's for transforming one tree-based
representation of a program into another. See for example Pheme's lib/*.tg
files.

-- c

[Adriano Ferreira]

Among the features that cannot be missed in a transformation language
(and sorry if that's too obvious) I mention:
* a data structure pattern language
(something between patterns used in Prolog and some functional languages
and XPath)
* and rules that are selected via these patterns (with a certain number of
default behavior to make useful things easier).

For example, an identity transformation may look like

tr_rule id($obj ~~ Any) { tr_apply($kid) for $kid ($obj.children) }

and it could be changed to an almost identity by inserting
a rule that changed the string "foo" to "bar".

tr_rule quasi_id($obj ~~ Any) { tr_apply($kid) for $kid ($obj.children) }
tr_rule quasi_id($obj ~~ "foo") { "bar" }

More complex patterns should be able to give names to structure parts
which may be used in the body of the rule. Something similar to what
Prolog does.

tr_rule some_trans( $obj ~~ [ $a ~~ Hash, $b ~~ { 'k' => $vk } ] ) {
[ { 'y' => $vk, $a } ]
}

The rules must know how to walk each kind of structure: array, hash,
object, whatever and build new ones.

My 0.00000002 cents.

Adriano Ferreira.

[Aaron Sherman]

I'm confused. I thought that this is what TGE did. Is TGE going away, or
are we talking about something that extends TGE in some way?

[Chromatic]

On Wednesday 04 October 2006 07:13, Aaron Sherman wrote:

> chromatic wrote:

> > That's part of it, but mostly it's for transforming one tree-based
> > representation of a program into another. See for example Pheme's
> > lib/*.tg files.

> I'm confused. I thought that this is what TGE did. Is TGE going away, or
> are we talking about something that extends TGE in some way?

TGE needs an embedded language to say "You gave me a PGE tree. I want to turn
that into a PAST tree, by turning this node into that node, copying that
information, and adding this other information." Note that this language has
nothing to do with *finding* nodes (as in XPath). That's what TGE does.
This mini language is just the stuff in curly braces in the TGE Grammar
files:

transform result (empty_list) :language('PIR') {
.local pmc result
result = new 'PAST::Exp'

.local pmc cons
cons = new 'PAST::Op'
cons.'op'( '__make_empty_cons' )

result.'add_child'( cons )
.return( result )
}

It turns out that assembly language makes things like looping and declaring
complex data structures rather tedious.

-- c

[Allison Randal]

You've exactly got what's on my mind. But no one could know that, since
I haven't written it down yet. :)

We got several volunteers, so I'm going to spend some time talking with
them.

Allison

[Markus Triska]

chromatic writes:

> That's part of it

With his permission, I've put the relevant section of Stefan Kral's
master's thesis online at:

http://stud4.tuwien.ac.at/~e0225855/kral_optimizer.pdf

The chapter describes the implementation of a rule-based peep-hole
optimizer using Prolog DCGs. The rules start at page 55. They are all
quite concise, and I hope that the syntax is a useful starting point
for the language to be used in Parrot. If you have any questions about
it or the implementation of the rewrite system, please let me know.

Best wishes!
Markus Triska