During on of our chats on current affairs, Martin mentioned that Lennart Kats
had proposed to introduce global variables in Stratego. My first reaction was
of course outrage. My second reaction was to immediately add it
to the compiler. The proposal was not to add some sort of C-style global variables,
but rather to provide better syntax for a programming pattern that was already
well established (although considered somewhat improper, at least by me).
Dynamic rewrite rules are Stratego's feature for maintaining
state, albeit in a
scoped way. A dynamic rule is a rewrite rule
defined at run-time. The following is the paradigmatic example of dynamic rules:
define-inline =
?Function(f, xs, e)
; rules( Inline : Call(f, es) -> Let(xs, es, e)
This strategy definition matches a function definition for a function f with formal
parameters xs and body e, and then defines a dynamic rule Inline that rewrites
a call to function f to an instantiation of the body of the function. What distinghuishes
this definition from a static rewrite rule
Inline2 : Call(f, es) -> Let(xs, es, e)
is that the variables f, xs, and e in the rule are inherited from the definition context (think
of it as a closure if that helps you). Indeed the rule Inline2 is not valid, since its right-hand
side uses the variables xs and e, which are not bound by the left-hand side.
So dynamic rules provide a way to dynamically construct a mapping from term (patterns)
to terms and use this mapping when convenient. Now it happens often in programming
that we just want to record a single value, which we want to access later. If we don't want
pass the value around using a variable, we need a global variable. This can be achieved
in Stratego using the following pattern:
x := <compute>
; rules( Foo : _ -> x )
Here the value that 'compute' returns is bound to the variable x. Then the dynamic rule
Foo is defined to rewrite anything (underscore is wildcard and matches anything) to the
value of x. The value can later on be retrieved by an application <Foo>. This pattern
is not so nice since it has quite a bit of syntactic noise. What we would like is just write
Foo := <compute>
However, this binds Foo as a local variable in the current strategy definition. And we also
don't want to introduce C-style global variables.
Comes in the idea of Lennart, which is quite obvious in retrospect, as are all good ideas.
Still use the dynamic rule pattern above as implementation, but provide better syntax for
it. Still use the := operator, but in the context of a rules() interpret it as a dynamic global
variable assignment, so that we can now write the following for the pattern above:
rules( Foo := <compute> )
I thought this was a great idea. Rather than putting this on the issue list, which is
always an ominous sine for a feature request ;-), I boasted to Martin to implement
this in five minutes. So we sat down defined the syntax for the rule and its implementation,
which is the addition of the following desugaring rule to the Stratego compiler's front-end:
Desugar :
|[ rules( dr := t ) ]| -> |[ where({y : !t; ?y; rules( dr : _ -> y )}) ]|
where y := <newname> "globvar"
The rule would compile the assignment above to
where({x : x := <compute>; rules( Foo : _ -> x )})
introducing x as a fresh local variable. This took us 12 minutes from start
to the commit, including an informative commit message! Of course it
turned out that, while correct, the build didn't immediately succeed. To
add new syntax to Stratego, one first needs to create a new baseline
with the new syntax, before it can be used in the compiler. And Martin
added a nice test set.
While we were at it, we also included the following variant:
Desugar :
|[ rules( dr :+= t ) ]| -> |[ where({y : !t; ?y; rules( dr :+ _ -> y )}) ]|
where y := <newname> "globvar"
Exercise to the reader to figure out what this one does.
Another exercise to the reader is to explain why these global variables are
not the same as C-style global variables.
There is also some room for critique. There are now two forms of the operator
:= in Stratego, one as a strategy x := t and one in the context of a dynamic
rules definition rules( x := t ). There is a subtle difference between these two;
can you spot it? (No, it is not eagerness, both versions first evaluate t before
assigning it to x.)
Another issue is the cost in terms of time and space, at least compared to a
simple C assignment, and with the current implementation of dynamic rules.
The plans for a new implementation scheme for dynamic rules would improve
at least the storage cost.
There you have it, challenging questions for the knowing. An opportunity for
comments to this blog?
