----------------------- REVIEW 1 --------------------- PAPER: 23 TITLE: Merging Idiomatic Haskell with Attribute Grammars AUTHORS: Arie Middelkoop, Jeroen Bransen, Atze Dijkstra and Doaitse Swierstra OVERALL RATING: -1 (weak reject) REVIEWER'S CONFIDENCE: 3 (high) The paper gives an overview of the UUAG attribute grammar system and describes a series of extensions that tackle various issues that arise when integrating attribute grammars in Haskell code. In particular, the paper introduces eager rules (for eager evaluation of certain attributes), and custom attribute evaluator hooks. The subject of the paper is quite interesting for the Haskell Symposium and the integration of a full fledged attribute grammar system with Haskell is a powerful combination. Unfortunately, I found the paper difficult to read where it is often quite unclear about the details. Also, some parts are very nice and can be fully understood in terms of the AG language, while other parts depend intricately on particular implementation details. (which makes it hard to generalize the solutions to other systems) Section 2: the paper tries to talk about attribute grammars abstractly even when introducing a very particular system and syntax. It would be good to introduce UUAG as the particular system and language, and stress that it can be downloaded and used, and that it executes all the examples in the paper. (which I assume it does?) On copy rules: the rules are explained abstractly, but why not give a concrete example directly? Also, since copy rules are so important to all the other examples later in the paper, perhaps try to explain it really well here in Section 2 and then just use it everywhere. Section 3: As a reader, it is strange to start reading about how the code is generated for an AG: usually, when using a programming language it is not important to know how code is generated in a paper on language features. Perhaps this section should be removed completely. The reasons for having this section are stated but perhaps false. In particular, to understand the semantics it would be much better to explain the semantics in terms of an AG itself instead of the generated code. One can also refer to the literature on AG's. Section 4: Higher order attributes are important but perhaps not widely known to a Haskell audience. The section would be improved by starting with some concrete examples (as in figure 4 & 5) and explaining how it works; only then give a formal definition (which in itself is hard to understand if the reader has not first seen some concrete example) Section 4.4: Please state more clearly that Proxy is not an extension but just a pattern that relies heavily on copy rules. Moreover, give again a concrete example here: explaining it abstractly (in terms of P, N, n, etc) is just not helpful without having seen an instance. Currently it is only forward referenced. Section 4.4: the grammar extension: this is introduced as a 'transparent approach' but it seems a terribly fragile and implementation dependent approach. In particular, - Proxy is not defined in the example: what is it? (I guess the earlier presented example: data Proxy | P n : N) - The "n" field has type "N" in Root but is then 'overridden' (?) as the inst.n attribute of type "Proxy" ? - Somehow, the user is supposed to rely on very intricate details of the code generation of the AG system; it is like an __asm directive in C++ (or worse). * The user needs to know that the type Proxy will become a function from something to something * and that "sem_P" is some function that does P semantics and that its result is somehow a type correct replacement of a "N" typed evaluation... All in all, not in the spirit of an AG at all which has nice declarative semantics. I find it a problem that the paper is not more explicit about these issues. Also, it is unclear how this approach could be reused in other AG systems with its strong reliance on a particular compilation strategy. Section 6: I do not understand how the eager rule transformation can be both sound and complete: if I annotate everything as eager, the repmin AG will now diverge instead of terminate with an answer? Section 7: It is remarked that the nice solution with a type class constraint is undesirable because "it requires a language specific extension".. and right after that a less elegant solution is presented that relies on: - a GHC specific extension to Haskell - the property that the generated code must have the dictionary unpacked in scope but the AG system does not guarantee this (ie. it may well generate wrong code that does not type check). The fix is to annotate all of these unpacking functions as eager rules which will implicitly have code generator generate correct code. All in all, a very fragile approach in my opinion and the paper fails to discuss this clearly. The whole dependence on how the code is generated gets even worse in Section 10 with the expl attributes. It surely fixes the particular problem but it is unclear if these solutions can be reused in other contexts. ----------------------- REVIEW 2 --------------------- PAPER: 23 TITLE: Merging Idiomatic Haskell with Attribute Grammars AUTHORS: Arie Middelkoop, Jeroen Bransen, Atze Dijkstra and Doaitse Swierstra OVERALL RATING: 1 (weak accept) REVIEWER'S CONFIDENCE: 3 (high) The paper presents a collection of programming idioms and extensions to attribute grammars in an attempt to achieve better integration with Haskell programs. The paper is well written, but it presents numerous small ideas and I found it a bit hard to put them together to form an overall picture. (Also, some of the typos in the examples has me confused for a while, but that should be easily fixable, I listed the ones that I noticed bellow.). I found that that most compelling extension proposed is the idea of "eager rules", which help to avoid some memory leaks, by computing their results as soon as their dependencies are ready. I had a somewhat mixed reaction to the extensions/idioms for working with polymorphic data: things seemed simple and natural for computations data are independent of the type parameters (e.g., the "length" example), however anything beyond that seemed to require fairly heavy-weight encoding. For example, using overloading (i.e., Haskell classes) is done using explicit dictionary passing, which essentially side-steps the class system. Also, type parameters are treated as terminals, so if we want to instantiate them with other structured data with attributes, we have to resort to a complex-looking encoding that uses higher-order attributes, and passes type-equality evidence explicitly. Finally, I found it a bit odd that polymorphic datatypes need to provide two sets of type parameters, ordinary ones, and another set used only by the evaluator, to support fairly simple functions such as "map". To support monadic computation, the paper proposes some syntax for writing monadic attributes. However, programmers have to use explicit data-dependencies to specify the order in which monadic computations will be sequenced which, while flexible, also seems somewhat error prone. Finally, the paper proposes a mechanism for hooking into the attribute grammar evaluator itself, so that programmers can use arbitrary Haskell code to control the computation of attributes. While very expressive, I was not convinced by the stream-processor example presented in the paper, and I can't help but wonder if using an attribute grammar is the right tool for solving this particular task. Typos: p1, 2nd paragrap of Introduction: "to be expressed as a an ..." --> "to be expressed as a ..." p2, paragraph "Example" "synthesized attribute 'res' ..." --> "synthesized attribute 'repl' ..." p2, paragraph "Advantages" "Atribute grammers offers ..." --> "Attribute grammers offer ..." p2, Figure 1: In the attributes of `Tree`: Shouldn't the attribute "lmin" be synthesized? In the semantics of `Bin`, last line: "left.gmin = @lhs.gmin" --> "right.gmin = @lhs.gmin" p5, 3rd paragraph of "Definitons" "statical analysis" --> "static analysis" p6, Figure 7: Shouldn't 'lmin' be synthesized? p6, code in paragraph "Example" Shouldn't 'lmin' be synthesized? p7, end of 1st paragraph, of Section 8: "multiple of such children" --> "multiple such children" p7, 1st line of 2nd paragraph: "[1999b] deals nonterminals ..." --> "[1999b] deals with nonterminals..." p7, code example at the top of RHS: attr Info inh eqExpr :: t Expr syn repExpr :: InfoExpr --> attr Info inh eqExpr :: t :=: Expr syn repExpr :: InfoExpr p10, 2nd paragraph of part "Example": "earlier section has the processor Proc only one ..." --> "earlier section the processor Proc has ony one ..." ----------------------- REVIEW 3 --------------------- PAPER: 23 TITLE: Merging Idiomatic Haskell with Attribute Grammars AUTHORS: Arie Middelkoop, Jeroen Bransen, Atze Dijkstra and Doaitse Swierstra OVERALL RATING: 1 (weak accept) REVIEWER'S CONFIDENCE: 4 (expert) I think the work is original. The weakest part for me was the motivation, but it's difficult to fit much in a relatively short paper. In particular, the line seems to be "Haskell programmers like to use these features" so we need to support them in our AGs. I can buy that for type polymorphism and type classes, but it's less convincing for the monad features. As the authors note, the idea of AGs is quite opposed to things like side-effecting computations since the whole idea is that the order of evaluation is implicit. Just saying that Haskell programmers want to use such monads in their computations is not enough for me to require development of more hooks to influence the evaluation scheme. It seems cleaner to keep things like state monads out of the AG world and integrate at a higher level. The comparison with related work was much too brief I think, mostly being a bit of history of development relating it to functional languages. There is essentially no analysis of how the features they have introduced compare to approaches to similar issues in other AG systems. In summary, for the Haskell workshop this paper is more acceptable than it would be in a more general language engineering conference. In the latter the lack of proper comparison to other AG systems is a severe weakness. For the workshop the focus would more likely be on the Haskell technical details rather than on AGs per se, so it's on stronger ground there. But it's still hard for a reader to place this work in context than it should be. ----------------------- REVIEW 4 --------------------- PAPER: 23 TITLE: Merging Idiomatic Haskell with Attribute Grammars AUTHORS: Arie Middelkoop, Jeroen Bransen, Atze Dijkstra and Doaitse Swierstra OVERALL RATING: 1 (weak accept) REVIEWER'S CONFIDENCE: 1 (low) This is a non-expert review. I haven't used attribute grammar systems before, but as the paper has a specific "Attribute Grammar Tutorial" section I decided to have a go at it. Sections 2-3 give a crash course in attribute grammar systems and common extensions. This was good for me because I didn't know much about them before reading this paper, but I suspect people more familiar with AGs would become impatient. The author's contributions don't start until Page 5. I suggest trying to reorganise the material to cover some of the new stuff earlier, or at least motivate it and give more hints about what is coming. Even as an AG novice I started itching to hear about the new material after page 3. The authors first extend their AG system with parametric polymorphism and eager rules. This sounds totally reasonable. Indeed, I was surprised that standard AG systems didn't already support polymorphism. The addition of eager rules also seems reasonable, for the same reason we want strictness annotations in plain Haskell. The way type classes have been added seems like a necessary hack. I can appreciate that if polymorphism is new in the AG world then we need at least a stop-gap solution for type classes. However, I imagine that plumbing explicit dictionaries like this will quickly become painful in real code. It looks like we have to explicitly unpack dictionaries in every rule that uses them. This suggests that we really want a proper analysis that inserts them. I appreciate that authors are probably trying to implement their AG syntax via a simple desugaring onto Haskell, but for future work, the current type class implementation makes me think we really want to do type inference over the AG code first. I could follow the motivation for S8 "Abstraction over Nonterminals" section, but had problems with the AG syntax. On p7 we've got: sem Stmt | If inst.guard : ExprProxy inst.guard = Proxy Back in S4.3 the declaration part "inst.c : M" was attached to the "data" declaration, but now it's in the "sem" rule. Why the change? This might just be displaying my lack of knowledge about AG systems, but then I see on page 9 a line "inst.run = @oper.value" without the child definition "inst.run : ..." anywhere. It would be nice to have a grammar for their attribute grammar system. After the middle of page 9 I can't trick myself into believing I understand how the code works anymore. I'd need to spend some time with a real AG system and learn it properly. In any case, for the section on integrating monads I really don't see the point of the stream processor example. The text mentions some sort of web-service as an example application. Has this actually been tried? The other suggestion was to use monads to write a "streaming compiler", but I don't know any real examples of those either. Just-in-time compilers: yes, but streaming compilers: no. At the end of page 9 it says that whether we want to enforce a sequential order on monadic code depends on the application. It suggests that there are applications where we may want to permit "change [in] the order in which responses are written to the output channel." I can see why we want this for a stream processor, but not a compiler. I don't know why we were talking about stream processors to begin with. In Section 10 on "Inversion of control", I drowned. The introduction motivates this material with 'spreading environments, computing fixpoints, computing transformed trees and collecting error messages'. Then we're back to stream processors and I don't see the point. The section describes the syntax and operation of the inversion of control feature, but it doesn't say "we want to use inversion of control in our stream processor because of *good reason*". That said, the paper does seem to be pushing the boundaries of what can be done with attribute grammar systems. Maybe the good reasons have to come afterwards. I'd be fine with that. *** Notes on the text *** p1. "expressed as a an embedded domain" p1. Figure 1. Surely "lmin" is synthetic? p1. Figure 1. missing "right.gmin = ..." p3. Is parallel evaluation of attribute grammar systems helpful in practice? It seems like the grain size for the parallel computations would be very low. p3. "if the rules do so too". Awkward phrasing. p3. "In the figure, left' and right' ... " Break up sentence. Too many "and"s p3. "Rules may refer to ... when defined by a rule". Confusing double use of "rule". Rephrase. p4. "as [an] inherited attribute" p4. "larger arguments" => "later discussion". "arguments" makes me think of functions here. p4. "A common pattern..." Text doesn't flow from the "pattern" mentioned in the previous paragraph. p5. I would rewrite to use "repl" instead of "r" to match Figure 1. You also switch between "r" and "repl" in other figures. p5. The approach is sound... I don't see why you're mentioning soundness. It seems plain as day that changing scheduling constraints won't crash the program. p6. "The attributes are polymorphic..." Break up very long sentence. p6. "specify the used dictionaries" => "specify the dictionaries used" p6. "In a context ... needed ... not needed..." Confusing double use of 'needed'. Rephrase. p6. "With a GHC extension" Name it! p7. Point out that "Refl" is refers to "reflexivity" for the equality constraint. People without solid formal training might not get this. p7. "deals [with] nonterminals parameterised..." p7. "or because the attributes are independent of it?" Independent of what? I don't understand this sentence. p7. State what you mean by "pure" monads. Some people would say IO is pure because of the thread-the-world thing. p7. The example at the end of this page isn't very convincing. I'd like to see examples closer to the problem domain -- stuff from real compilers. p7. The integer "fld head". I can't find a "fld" function. p8. Passed on to the tail as "tl.c" what is "tl.c" ? p8. "that it obtains as [the] inherited attribute expr ..." p8. "@loc.m" what ".m" ? I don't see it defined. p9. "a <- code". Don't write meta-syntactic variables like 'code' with the same font as real code. It's very confusing. p9. "the st attributes determines influences" p10. "left argument is proved to be" => "left argument is proven to be" p11. "exponential in the amount of attributes" => "exponential in the number of attributes." We can't say "amount of attributes" because attributes have individual identity. correct: "number of cars" "number of grains" "amount of milk" "amount of rice" incorrect: "amount of cars" "amount of grains" "number of milk" "number of rice"