printf. The experience with printf, however,
has not been pleasant: even keeping the generated code syntactically
correct has been a struggle -- let alone figuring out
what went wrong when that code fails to compile.
Staged programming languages ensure by design not only
that the generated code is syntactically well-formed, but also that
all its variables are bound -- to their intended binders. When
the object language is typed, staged systems also statically guarantee that a
well-typed generator produces only well-typed code. Providing such
assurances, well-scopedness in particular, is not easy:
Lisp-like quasiquotation alone does not suffice. Practical staging
systems also offer code-generating facilities beside code
templates, such as cross-stage persistence and code movement (e.g.,
let-insertion).
Our framework is not a an experimental language with a new syntax and uncertain future. Rather, it is a regular, not a bleeding edge, library in mature Haskell. It is modular and extensible: one can add to the target language more features and constants or change it to be typed or untyped, first- or higher-order. Polymorphism over generated environments makes generators composable. The higher-order abstract syntax used in the library makes target functions and variables human-readable. Our library may be regarded as `staged Haskell'.
There are many code generation frameworks with one or the other of the features. Ours has all of them. Template Haskell, among other systems, falls short, assuring -- dynamically rather than statically -- the well-typedness of only the final code. Furthermore, although the generated code, after a type-check, is well-typed, it may still be ill-scoped.
The static types of our generator expressions not only ensure that a well-typed generator produces well-typed and well-scoped code. They also express the lexical scopes of generated binders and prevent mixing up variables with different scopes. For the first time we demonstrate, in an embedded domain-specific language, statically safe and well-scoped loop interchange and constant factoring from arbitrarily nested loops.
Joint work with Yukiyoshi Kameyama and Chung-chieh Shan.
beyond-talk.pdf [193K]
The annotated slides of the talk presented at PEPM 14
on January 20, 2014 in San Diego, CA, USA
Region Memory Management
for Free Variables:
Type- and Scope-Safe Code Generation with Mutable Cells
The formalization of one part of the combinator library,
as the calculus <NJ>
TSCore.hs [29K]
The core of the code generation library
TSCPST.hs [17K]
Code generation with control effects reaching beyond the
closest binder. Far-reaching let-insertion.
The implementation of the CPSA applicative hierarchy.
Examples and Sample code
The original Template Haskell (Haskell Workshop, 2002) is essentially untyped, with no guarantees that the generated code is any good, or even well-typed. Writing code generators was akin to programming in `dynamically typed' languages: although we can easily tell that the fully generated program is untypable (because it cannot be compiled), we cannot easily point out which part of the generator was to blame. The dissonance with the type discipline of Haskell is jarring. On the other hand, Template Haskell is very expressive: it generates not only expressions but also definitions, type declarations, classes and instances, etc. -- all sort of things that may appear in Haskell code. Designing a type system for such broad code generation was, and still is, a great challenge.
Against this background, Typed Template Haskell was introduced. It produces code only for expressions (and not for declarations, etc.). On the other hand, we can finally write typed generators. Typed Template Haskell is quite similar to the lambda-circle calculus or MetaOCaml, but restricted to two levels. Here is the sample typed generator.
t1 :: Q (TExp Int)
t1 = do
c1 <- [|| (1::Int) + 2 ||]
c2 <- [|| 3 + $$(return c1) ||]
return c2
As in MetaOCaml, the type of code values TExp
is indexed by the type of the expression to be generated.
[|| ... ||] is the typed antiquotation, corresponding
to the brackets .< ... >. of MetaOCaml.
The brackets enclose, or quote, the code to generate, which must be
a well-typed expression. The unquotation, or typed splice, is
$$( ... ). The splice is evaluated and must produce
(a possibly open) code, which is then spliced into the enclosing typed
quotation. If the splice appears outside a quotation, it is called
top-level. In that case, the splice must produce a closed
expression, which is inserted into the code being compiled.
The sample generator t1 produces the following code:
3 GHC.Num.+ ((1 :: GHC.Types.Int) GHC.Num.+ 2)or, hiding the module qualifications,
3 + (1 + 2).
The problematic example is very short:
t2 :: Q (TExp Int)
t2 = do
r <- runIO $ newIORef undefined
c1 <- [|| \x -> (1::Int) +
$$(do
xv <- [||x||]
runIO $ writeIORef r xv
return xv) ||]
runIO $ readIORef r
It generates x_0: just the single, unbound variable. It is clearly
not typable. Such code cannot
be compiled or spliced-in at the top level. The culprit is runIO,
which runs IO computations from within typed splices.
It is highly desirable, for error handling and many other reasons.
It is also responsible for breaking type soundness.
Once again we see the tension between safety and expressiveness. Without effects, we cannot generate all the code we want and cannot handle errors well. With side effects, maintaining type safety is a challenge. Fortunately, the challenge has recently been met, outside GHC and Typed Template Haskell.
The problem sprang to attention during the lecture by Simon Peyton
Jones at the First Metaprogramming Summer School in Cambridge, UK in
August 2016 -- when runIO was mentioned.
Tagless-Staged: Combinators for Impure yet Hygienic Code Generation
Type sound code generation with arbitrary side-effects
MetaOCaml resolves the tension between expressiveness and safety in a different, easy to implement way
Here is a sample MetaOCaml code and its Scheme translation
# let eta = fun f -> .<fun x -> .~(f .<x>.)>.
in .<fun x -> .~(eta (fun y -> .<x + .~y>.))>.
- : (int -> int -> int) code = .<fun x_1 -> fun x_2 -> (x_1 + x_2)>.
(let ((eta (lambda (f) (bracket (lambda (x) (escape (f (bracket x))))))))
(bracket (lambda (x) (escape (eta (lambda (y) (bracket (+ x (escape y)))))))))
Translating MetaOCaml code into Scheme seems trivial: code values
are like S-expressions, MetaOCaml's bracket is like quasiquote, escape
is like unquote, and `run' is eval. If we indeed replace bracket with
the quasiquote and escape with the unquote in the above Scheme code and then
evaluate it, we get the S-expression
(lambda (x) (lambda (x) (+ x x))),
which is a wrong result, quite different from the code
expression .<fun x_1 -> fun x_2 -> (x_1 + x_2)>.
produced by MetaOCaml. The latter is the code of the curried function that
adds two integers. The S-expression produced by the naive Scheme translation
represents the curried function that disregards the first argument and doubles
the second. This demonstrates that the often mentioned `similarity' between
the bracket and the quasiquote is flawed. MetaOCaml's bracket respects
alpha-equivalence; in contrast, Scheme's quasiquotation, being the general
form for constructing arbitrary S-expressions (not necessarily
representing any code), is oblivious to the binding structure.
Our implementation still uses S-expressions for code values
(so we can print them and eval-uate them) and treats
escape as unquote. To maintain the hygiene, we need to make sure
that every run-time evaluation of a bracket form such as
(bracket (lambda (x) x)) gives
'(lambda (x_new) x_new)
with the unique bound variable x_new.
Two examples in the source code demonstrate why the static renaming
of manifestly bound identifiers is not sufficient.
We implement the very clever suggestion by Chung-chieh Shan
and represent a staged expression such as
.<(fun x -> x + 1) 3>. by the sexp-generating expression
`(,(let ((x (gensym))) `(lambda (,x) (+ ,x 1))) 3)
which evaluates to the S-expression
((lambda (x_1) (+ x_1 1)) 3).
Thus bracket is a complex macro that transforms its body
to the sexp-generating expression, keeping track
of the levels of brackets and escapes. The macro
bracket is implemented
as a CEK machine with the defunctionalized continuation. In our
implementation, the Scheme translation of the eta-example yields
the S-expression
(lambda (g6) (lambda (g8) (+ g6 g8))).
Just as in MetaOCaml, the result represents the curried addition.
CSP poses another implementation problem. In MetaScheme we can write
the MetaOCaml expression .<fun x -> x + 1>. as
(bracket (lambda (x) (+ x 1))),
which yields the S-expression (lambda (g1) (+ g1 1)).
When we pass this code to eval, the identifier +
will be looked up in the environment of eval, which is generally
different from the environment that was in effect when the original
bracket form was evaluated. That might not look like much of a difference
since + is probably bound to the same procedure
for adding numbers in either environment. This is no longer the case
if we take the following MetaOCaml code and its putative MetaScheme
translation:
let test = let id u = u in
.<fun x -> id x>.
(define test (let ((id (lambda (u) u)))
(bracket (lambda (x) (id x)))))
The latter definition binds test to the S-expression
(lambda (x) (id x)) that contains the free identifier
id, unlikely to be bound in the environment of eval.
Our code values therefore should be `closures', being able to include
values that are (possibly locally) bound in the environment when the
code value was created. Incidentally, the problem of code closures
closed over the environment of the generator also appears in syntax-case
macros. R6RS editors made a choice to prohibit the occurrence of
locally-bound identifiers in the output of a syntax-case transformer.
MetaOCaml among other staged systems does permit the inclusion of values from the generator stage in the generated code. Such values are called CSP; they are evident in the output of the MetaOCaml interpreter for the above test:
val test : ('a -> 'a) code =
.<fun x_1 -> (((* cross-stage persistent value (as id: id) *)) x_1)>.
In MetaScheme, we have to write CSP explicitly:
(% e), which is often called `lift'.
(define test
(let ((id (lambda (u) u)))
(bracket (lambda (x) ((% id) x)))))
One may think that such a lifting is already available in Scheme:
(define (lift x) (list 'quote x)).
Although this works in the simple cases of x
being a number, a string, etc., it is neither universal nor
portable: attempting this way to lift a closure or an output-port
could be an error. According to R5RS, the argument of a quotation is an
external representation of a Scheme datum. Closures,
for example, are not guaranteed to have an external representation.
For portability, we implement CSP via a reference in a global array,
taking advantage of the fact that both the index (a number) and
the name of the array (an identifier) have external representations
and hence are trivially liftable by quotation. This is precisely
the mechanism once used by MetaOCaml.
The source code contains many more examples of the translation of MetaOCaml code into MetaScheme -- including the examples with many stages and CSP.
Joint work with Chung-chieh Shan.