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
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?