February 2004 - template-haskell

RE: [Template-haskell] Hygienic macros and lexical-scoping
by Simon Peyton-Jones 26 Feb '04

26 Feb '04

| > | using x val body = [| do { (var x) <- val; body; (var x).Dispose () } | > |] | > | // x is of type string | > | | > | [| \y -> do { $(using "x" [| x |]); f y |] | > | | > | wouldn't work, and one would have to use gensym by his own to get | > | > expected | > | > | sematics. | > | > I'm sorry, I didn't understand this at all. What is 'using x val body'? | > What is .Dispose()? Not Template Haskell certainly. | | Well, it supposed to be a function, which takes 'x' (of type string), 'val' | and 'body' (being expressions) and creates code which does: | - define local variable of name 'x' initialized with 'val' | - execute 'body' (it is assumed to have occurrences of 'x' inside, which | should be captured by local 'x' | - disposes 'x' (it has method 'Dispose', so I think its Haskell counterpart | would be calling function 'Dispose' on 'x') Ah. I thought 'using' was a keyword! OK, so it's like this: foo :: String -> Q Exp -> Q Exp -> Q Exp foo x val body = [| do { $(mkName x) <- $val; $body; dispose $(dyn x) } |] Here, mkName :: String -> Name dyn :: String -> Q Exp dyn s = return (Var (mkName s)) and I'm assuming an as-yet-unimplemented feature of TH which lets you splice a Name into a binding position (thus ($n <- ...) or (\$n -> ...)). The binding $(mkName x) certainly captures the occurrence $(dyn x). But you also want to capture some occurrences of 'x' in 'body'. Thus, consider foo "wug" [| 77 |] [| wug > 2 |] does the 'wug' in 'wug > 2' get captured by the (mkName "wug") binding? No, not in TH. The above call is statically rejected unless wug is already in scope. For example let wug = 88 in foo "wug" [| 77 |] [| wug > 2 |] And in this case, the 'wug > 2' is indissoubly bound to the 'wug = 88' binding. What if you *want* the 'wug > 2' to be bound un-hygienically to the (mkName "wug") binding? Then use 'dyn' thus let wug = 88 in foo "wug" [| 77 |] [| $(dyn "wug") > 2 |] Now, plainly, the wug=88 binding plays no role. | This can be implemented in TH with (dyn "x") which you mentioned, but if | 'body' is itself passed from another context and 'x' is introduced in | | f body = [| using "x" Foo $( [| do { dosomething x; body } |] ) |] | | then some external 'x' in original 'body' might get catched by dynamic | binding, which is not hygienic behavior. | | I'm aware that this can be workaround with manually creating 'x' with newName | and using this Name. Our decision to bind variables after macros expansion | makes it possible to handle such cases in other way. There are opposite | design goals, and I clearly see advantage of TH's one - bind to what you can | see, before any expansion. Nevertheless we will try another approach and | experiment with such system. I hope the above makes it clear that you can express either behaviour in TH. To be sure, the references to dynamically scoped things are inconvenient, as we see in $(dyn "wug") > 2, but at least there's a simple story to tell. | see, before any expansion. Nevertheless we will try another approach and | experiment with such system. Indeed -- this is a rather complex design space, so it's great to explore new parts of it. Simon

1 0

RE: [Template-haskell] Hygienic macros and lexical-scoping
by Simon Peyton-Jones 25 Feb '04

25 Feb '04

Kamil Thanks for your email. | My question is: when binding of variables is resolved? Is it during | translation of quotation, or maybe during expansion of $(...) where the above | code is used? Answer 1: Binding is resolved before any expansion or translation. So in \x -> $(f [| x |]) the occurrence of 'x' is bound indissolubly to the binding '\x', and you can tell that by looking at the source code, before expansion. So if 'f' was defined like this f :: Q Exp -> Q Exp f e = [| \x -> $e |] Then the expression \x -> $(f [| x |]) means the same as \x1 -> \x -> x1 Answer 2: In an extension that is implemented but not described in a published paper (but is described here http://research.microsoft.com/~simonpj/tmp/notes2.ps) we also support a sort of dynamic binding: \x -> $(f (dyn "x")) Here 'dyn' is a function with type dyn :: String -> Q Exp (dyn "x") is a variable that will bind to whatever "x" is in scope where that expression is spliced in. So the expression \x -> $(f (dyn "x")) means the same as \x1 -> \x -> x Notice that this dynamic binding always explicitly involves a string, like "x". You wouldn't expect (dyn "x") to bind indissolubly to the enclosing '\x'. | After reading the paper, I'm convinced that it's former case. But let's | consider: | using x val body = [| do { (var x) <- val; body; (var x).Dispose () } |] | // x is of type string | | [| \y -> do { $(using "x" [| x |]); f y |] | | wouldn't work, and one would have to use gensym by his own to get expected | sematics. I'm sorry, I didn't understand this at all. What is 'using x val body'? What is .Dispose()? Not Template Haskell certainly. | In our system we are shifting binding of variables from quotation translation | to macro expansion phase, so [| x |] can be "catched" inside 'using' | meta-function. Resolving of scoping is done after all executions of macros | are done. It involves quite complex algorithm to tag variables with place | where they come from - we are adapting Dybvig's algorithm into our system, so | we could use most flexible convention introduced by Scheme community. As I say above, TH supports both pre-expansion binding (via plain mentions of a variable), and post-expansion biding (via "dyn"). Whatever you choose to do, let me encourage you to give it a formal description. | As we discussed our design, there was some confusion if macros should | introduce new definitions into program. I noticed, that in Haskell it is done | by special keyword 'splice', and it's forbidden inside quotations. As we | decided to resolve names in late phase, we could introduce definitions in | arbitrary place. Yes, that's right. We discuss this in Section 8 of the above note. (But nested declaration splicing isn't yet implemented.) Some questions arise in that case: | Let's consider following macros (in Nemerle syntax, as I'm more used to it) | | using Foo; /// it introduces functions 'blah' and 'bar' variables | macro m() { <[ def bar() { 1 } ]> } | macro m'() { <[ m(); blah() + bar() ]> } | | does m'() generate | def bar_43 = 1; Foo.blah() + Foo.bar() | or | def bar_43 () { 1 }; Foo.blah() + bar_43() The most systematic story in TH would be that you get the former -- that's lexical scoping. You could get the latter by using (dyn "bar"). But, for top-level declarations, it's very inconvenient to use all the dyn stuff. So in TH we compromise: top level splices lexically shadow previous stuff, so you get the latter definition. We explicitly call this a hack (see section 8.2). Simon

2 1

Hygienic macros and lexical-scoping
by Kamil Skalski 24 Feb '04

24 Feb '04

Hello! I'm developer of meta-programming system in a new language Nemerle. As we are coming near to implementation of lexical scoping and alpha-renaming in our system, I would like to share some ideas and ask few questions about Haskell Templates' approach to these problems. As I read in 'Template meta-programming in Haskell', the implementation translates [| \x -> $(f [| x |]) |] to do { x <- gensym "x"; lam [Pvar x] (app f (var x) } (I'm not familiar with Haskell, so I may have mistaken some syntax) My question is: when binding of variables is resolved? Is it during translation of quotation, or maybe during expansion of $(...) where the above code is used? After reading the paper, I'm convinced that it's former case. But let's consider: using x val body = [| do { (var x) <- val; body; (var x).Dispose () } |] // x is of type string [| \y -> do { $(using "x" [| x |]); f y |] wouldn't work, and one would have to use gensym by his own to get expected sematics. In our system we are shifting binding of variables from quotation translation to macro expansion phase, so [| x |] can be "catched" inside 'using' meta-function. Resolving of scoping is done after all executions of macros are done. It involves quite complex algorithm to tag variables with place where they come from - we are adapting Dybvig's algorithm into our system, so we could use most flexible convention introduced by Scheme community. Assuming I'm not wrong by now, I also have question, was the other option considered during design of Template Haskell? As we discussed our design, there was some confusion if macros should introduce new definitions into program. I noticed, that in Haskell it is done by special keyword 'splice', and it's forbidden inside quotations. As we decided to resolve names in late phase, we could introduce definitions in arbitrary place. Some questions arise in that case: Let's consider following macros (in Nemerle syntax, as I'm more used to it) using Foo; /// it introduces functions 'blah' and 'bar' variables macro m() { <[ def bar() { 1 } ]> } macro m'() { <[ m(); blah() + bar() ]> } does m'() generate def bar_43 = 1; Foo.blah() + Foo.bar() or def bar_43 () { 1 }; Foo.blah() + bar_43() lexical scoping should theoretically mean the former case, but if we consider function MacroUseSymbol (x : string) - that generates symbol, which will behave as one introduced in macro use site, then latter case is valid. The same function might be used to implement 'using' macro, I've mentioned: macro using (x : string, val, body) { def x = MacroUseSymbol (x); <[ def $(x : var) = $val; $body; $(x : var).Dispose () ]> } My last question is if this approach was considered and what are opinions about introducing this kind of lexial scoping into languages with explicit quoasi-quotations. I can describe our algorithm if anyone is interested (as it is still under discussions). Kamil Skalski Nemerle developer - http://nemerle.org

1 0

Re: [Template-haskell] On reifing functions and partial evaluation
by Duncan Coutts 17 Feb '04

17 Feb '04

On Tue, 2004-02-17 at 09:05, Alastair Reid wrote: > > First the sensational headline: > > ghc beats gcc by 57% on Ackerman benchmark, improved to 290% using > > Template Haskell. > > Any thoughts on how it would compare with a C++ template-based version of ack? > Off the top of my head, I'd say performance ought to drop back to nearer the > 57% better mark but it'd be (mildly) interesting to confirm this. Ok, so to be fair to C/C++ (!) we should really compare like with like in which case we should compare our template-unrolled version with a C++ template unrolled version. As you thought, the performance drops back, but we still win. :-) 75 sec for g++-3.3.2 -O3 -fomit-frame-pointer 40 sec for genex_ack_4 with ghc -O So the percent improvement that the marketing folk would put in their adds would be 87%. So actually we're winning by a greater margin than before. If you're really keen we can get the time down even further: 88 sec for ack_4 with ghc -O2 -fvia-C -optc-O2 (vs 100sec for ghc -O) 32 sec for genex_ack_4 with ghc -O2 -fvia-C -optc-O2 (vs 40sec for ghc -O) Duncan Here's the C++ code: template<int m> class foo { public: static int ack(int n) { if (n==0) return foo<m-1>::ack(1); else return foo<m-1>::ack(ack(n-1)); } }; template<> class foo<0> { public: static int ack(int n) { return n+1; } }; int main (int argc, char *argv[]) { int n = ((argc == 2) ? atoi(argv[1]) : 1); printf("ack 4 %d = %d\n", n, foo<4>::ack(n)); return 0; }

1 0

On reifing functions and partial evaluation
by Duncan Coutts 17 Feb '04

17 Feb '04

All, So I'd like to persuade people of the desirability of being able to reify values/functions. :-) I've now got two ways of potentially doing partial evaluation using Template Haskell, they correspond to two different types for our specialisation function mix. To describe the types, I'm going to pretend that TH is typed. Just erase the phantom type to get real TH (ie Exp a --> ExpQ). mix1 :: Exp (a -> b) -> Exp a -> Exp b eg mix1 [| isJust |] [| Nothing |] This is where we do abstract interpretation of the function on its static argument. Unless the function is a textually a lambda abstraction we can't look at its definition to to the interpretation. The other way that might work has this type: mix2 :: Exp (a -> b) -> a -> Exp b eg mix2 [| isJust |] Nothing Here, the static argument is a value rather than a syntax tree representing a value. It would be desirable to have mix with this type because it avoids the heavy double encoding that we get with mix1 when we apply it to itself. With mix1 we would do cogen = $( mix1 [| mix1 |] [|[| mix1 |]|] ) where as with mix2 we can do cogen = $( mix2 [| mix2 |] [| mix2 |] ) To implement mix with this type, what we do is construct the generating extension of the function we are specialising, apply it to its static argument and splice in the resulting code. For example for isJust, we need to do the following transformation: isJust = \m -> case m of Nothing -> False Just _ -> True --> genex-isJust = \m -> case m of Nothing -> [| False |] Just _ -> [| True |] Now, genex-isJust Nothing = ConE GHC.Base.False (ignoring the Q monad) We could define genex simply as genex f = (\e -> [| e |]) . f But then it would only work for liftable values - ie not functions. Of course with partial evaluation it is functions that are particularly interesting. We typically specialise functions of several arguments on just one or two static arguments - the remaining arguments are accepted at runtime. So, instead of just composing with wrap = (\e -> [| e |]) :: a -> Exp a we'll need genex :: Exp (a -> b) -> Exp (a -> Exp b) and it will have to inspect the definitions of functions/values. Another example: foo s d = case s of Nothing -> False Just _ -> case d of Nothing -> False Just _ -> True --> genex-foo s d = case s of Nothing -> [| False |] Just _ -> [| case d of Nothing -> False Just _ -> True |] The bits in the quasi-quote brackets [| |] are the fragments of the computation that will be deferred to runtime because they depend on an argument to the function that is not known (static) at compile time. We can also get nested $() and [| |] if there are static subexpressions inside a dynamic expression. bar s d = case d of Nothing -> False Just _ -> case d of Nothing -> False Just _ -> True --> genex-bar s d = [| case d of Nothing -> False Just _ -> $( case s of Nothing -> [| False |] Just _ -> [| True |] ) |] This is an example where Ian's idea of adding QQuot and Splice as Exp constructors would make things easier, but it's not essential so long as encodings are possible. On a related issue, I recall Simon PJ wondered about the best way of reifying values in patterns, like: let (a,b) = e reify "a" = ??? What about just applying the appropriate projection reify "a" = [| (\(x,_)->x) e |] I guess there's a danger of people duplicating computations by carelessly manipulating such expressions. ie inadvertently doing the following transformation: let (a,b) = e --> let a = fst e b = snd e Duncan

2 1

[Template-haskell] Second CFP: GPCE'04 -- Generative Programming and Component Engineering
by Eelco Visser 11 Feb '04

11 Feb '04

[Papers about Template Haskell would fit very well in this conference.] SECOND CALL FOR PAPERS ---------------------------------------------------------------------- Third International Conference on Generative Programming and Component Engineering (GPCE'04) Vancouver, October 24-28, 2004 co-located with OOPSLA 2004 and ISMM 2004 http://gpce04.gpce.org ---------------------------------------------------------------------- ------------------------------------ Important Dates ------------------------------------ * Pre-submission: March 12, 2004 * Submission: March 19, 2004 ------------------------------------ Scope ------------------------------------ Generative and component approaches have the potential to revolutionize software development in a similar way as automation and components revolutionized manufacturing. Generative Programming (developing programs that synthesize other programs), Component Engineering (raising the level of modularization and analysis in application design), and Domain-Specific Languages (elevating program specifications to compact domain-specific notations that are easier to write and maintain) are key technologies for automating program development. GPCE arose as a joint conference, merging the prior conference on Generative and Component-Based Software Engineering (GCSE) and the Workshop on Semantics, Applications, and Implementation of Program Generation (SAIG). The goal of GPCE is to provide a meeting place for researchers and practitioners interested in cutting edge approaches to software development. We aim to foster further cross-fertilization between the software engineering research community on the one hand, and the programming languages community on the other, in addition to supporting the original research goals of both the GCSE and the SAIG communities. We seek papers both in software engineering and in programming languages, and especially those that bridge the gap and are accessible to both communities at the same time. ------------------------------------ Topics of Interest ------------------------------------ The conference solicits submissions related (but not limited) to: * Generative programming o Reuse, meta-programming, partial evaluation, multi-stage and multi-level languages, step-wise refinement o Semantics, type systems, symbolic computation, linking and explicit substitution, in-lining and macros, templates, program transformation o Runtime code generation, compilation, active libraries, synthesis from specifications, development methods, generation of non-code artifacts, formal methods, reflection * Generative techniques for o Product lines and architectures o Embedded systems o Model-driven architecture * Component-based software engineering o Reuse, distributed platforms, distributed systems, evolution, analysis and design patterns, development methods, formal methods * Integration of generative and component-based approaches * Domain engineering and domain analysis o Domain-specific languages (DSLs) including visual and UML-based DSLs * Separation of concerns o Aspect-oriented programming, feature-oriented programming, o Intentional programming, and multi-dimensional separation of concerns * Industrial applications Reports on applications of these techniques to real-world problems are especially encouraged, as are submissions that relate ideas and concepts from several of these topics, or bridge the gap between theory and practice. The program committee is happy to advise on the appropriateness of a particular subject. ------------------------------------ Paper Submission ------------------------------------ Authors are invited to submit a title and abstract by March 12, 2004, and a full paper by March 19, 2004. These deadlines are firm. Simultaneous submission to other venues and submission of previously published material are not allowed. Electronic submission will be required, except by special arrangement with the program chairs. Authors will be notified of acceptance by May 17, 2004. Final versions of accepted papers must be submitted by July 25, 2004. Accepted papers will appear in the conference proceedings published in the Springer-Verlag Lecture Notes in Computer Science (LNCS) series http://www.springer.de/comp/lncs/index.html. Submissions must be in PDF, must conform to the LNCS style, and be no longer than 15 pages. For the formatting details see http://www.springer.de/comp/lncs/authors.html. ------------------------------------ Other Contributions ------------------------------------ Work related to generative programming and component engineering can also be presented in other forms than papers. GPCE has separate days for tutorials and workshops. During the conference there are sessions for tool demonstrations and practitioner reports. If you want to organize a workshop, present a tutorial, or demonstration, see the information on the conference website for details about format and submission. Contact the relevant chair for more information. ------------------------------------ Important Dates ------------------------------------ Technical papers * Pre-submission: March 12, 2004 * Submission: March 19, 2004 * Notification: May 17, 2004 * Final version: July 25, 2004 Submissions of proposals * Workshops: March 19, 2004 * Practitioners: April 30, 2004 * Tutorials: April 30, 2004 * Demonstrations: July 2, 2004 Conference * Tutorials: October 24, 2004 * Workshops: October 25, 2004 * Papers: October 26-28, 2004 ------------------------------------ Organization ------------------------------------ General chair * Tim Sheard (OGI School of Science & Engineering at OHSU) Program committee chairs * Gabor Karsai (Vanderbilt University) * Eelco Visser (Utrecht University) Program committee * Uwe Assmann (Linkopings Universitet) * Don Batory (University of Texas) * Jan Bosch (Universiteit Groningen) * Jean Bezivin (Universit� de Nantes) * Jim Cordy (Queen's University) * Krzysztof Czarnecki (University of Waterloo) * Mathew Flatt (University of Utah) * Robert Gl�ck (University of Copenhagen) * George Heineman (Worcester Polytechnic Institute) * Michael Leuschel (University of Southampton) * Karl Lieberherr (Northeastern University) * Simon Peyton Jones (Microsoft Research) * Douglas R. Smith (Kestrel Institute) * Gabriele Taentzer (Technical University of Berlin) * Todd Veldhuizen (Indiana University) * Kris de Volder (University of Britisch Columbia) * Dave Wile (Teknowledge Corp.) * Alexander Wolf (University of Colorado at Boulder) Workshop Chair * Zino Benaissa (Intel) Tutorial Chair * Jeff Gray (University of Alabama at Birmingham) Demonstrations Chair * Simon Helsen (University of Waterloo) Contact * gpce-chairs(a)cs.uu.nl

1 0

RE: Documentation fix for TH example
by Simon Peyton-Jones 03 Feb '04

03 Feb '04

All true! Good suggestions. Are you getting on all right with TH now. The mailing list has been rather quiet recently. Simon | -----Original Message----- | From: glasgow-haskell-bugs-bounces(a)haskell.org [mailto:glasgow-haskell-bugs- | bounces(a)haskell.org] On Behalf Of Gregory Wright | Sent: 29 January 2004 22:04 | To: glasgow-haskell-bugs(a)haskell.org | Subject: Documentation fix for TH example | | | Hi, | | The GHC 6.2 User's Guide has some misleading information w.r.t. | template haskell. | | It still uses Expr instead of ExpQ. It refers to Tim Sheard's notes, | but doesn't have the link | | http://research.microsoft.com/~simonpj/tmp/notes2.ps | | It should also warn that not all of the features discussed in the above | notes are implemented. | In particular, the way to get TH is still to import | Language.Haskell.THSyntax, not Language.Haskell.TH. | | The example doesn't compile under 6.2. The attachment corrects this. | | A note that TH is rapidly evolving and that the API is likely to change | incompatibly between | compiler releases might not be out of place either. (I know that such | warnings are present | in the literature and in some places on the mailing list, but language | users who are not | part of the FP community look to the documentation first.) | | Best Wishes, | | Greg | | Gregory Wright | Antiope Associate LLC | 18 Clay Street | Fair Haven, New Jersey 07704 | | gwright(a)antiope.com |

3 3