PAPER NUMBER 90 -- Feature-Oriented Programming with Object Algebras ARTIFACT GRADE met expectations REVIEW SUMMARY This artifact quite closely matched the reviewers' expectations from reading the paper. It was clear that the examples in the paper were represented by the artifact, and the artifact was straightforward to install and test. The reviewer most expert in Scala and FOP gained some useful insights from the artifact, while the other two could have benefited from more documentation and a clearer walkthrough of examples within the artifact itself. There was also some minor annoyance at the use of mere print statements for testing the artifact, when an assertion-based approach would have made it easier to understand the effects of modifying the artifact without relying on differences in console output. Overall, the artifact effectively backs up the claims in the paper, and is easy to install, run, and use (the reviewers were able to extend the examples with one of their own). The reviewers felt the artifact met expectations. ============================ REVIEWS =========================== PAPER NUMBER 90 ARTIFACT GRADE exceeded expectations PAPER SUMMARY AND CONTRIBUTIONS The paper demonstrates an encoding of object algebras in Scala based on intersection types and type-constructor polymorphism, supporting typed object and family self-references. Generic combinators are defined using type-constructor polymorphism and implemented either manually or using run-time reflection. ARTIFACT SUMMARY The artifact is a Scala code-base on Github containing the generic code described in the paper and some demonstration code for two example applications, concerning stacks and grammars. ARTIFACT PACKAGING The packaging was fine, no complaints here. I got everything to work in the Scala IDE with a small amount of work. Specifically, I find it perfect to put artifacts like this on Github. ARTIFACT IMPLEMENTATION AND USABILITY Some additional documentation in the code would have been helpful here and there and the authors regularly use Scala-isms that obscure the meaning of the code when there is no advantage to doing this. Because of both these issues, I sometimes needed quite some time to follow the code. Some specific remarks: * in oalg.algebra.core, AlgebraDefault.fcloseAlg and AlgebraDefault.fclose: could it be that you need to bound S to Object, so that you don't need to cast to Object using asInstanceOf? * To make your code a bit more accessible to a non-Scala audience, it could help to remove where possible some of the Scala-isms by more general OO code. For example, in oalg.algebra.paper.Self, you have // Closing trait CloseAlg[E] extends ExpAlg[E] { val alg : OExpAlg[E,E] def Lit(x : Int) : E = fix(alg.Lit(x)) def Add(e1 : E, e2 : E) : E = fix(alg.Add(e1,e2)) } def closeAlg[E](a : OExpAlg[E,E]) : ExpAlg[E] = new CloseAlg[E] { val alg = a } Unless you have a special reason to do so, I would consider it more standard OO code to write: class CloseAlg[E](alg : OExpAlg[E,E]) extends ExpAlg[E] { def Lit(x : Int) : E = fix(alg.Lit(x)) def Add(e1 : E, e2 : E) : E = fix(alg.Add(e1,e2)) } def closeAlg[E](a : OExpAlg[E,E]) : ExpAlg[E] = new CloseAlg[E](a) This code uses what seems to be a standard Scala pattern to work around the lack of constructor parameters for traits in Scala, but for readers that are not well-versed in Scala, this pattern is strange and makes the code harder to follow. There seems to be no reason to not use a class in this case. * Another Scala-ism that did not make it any easier for me to follow is the following in oalg.algebra.demo.Grammar.Grammar: class CircNullable extends (Nullable => Nullable) { import oalg.algebra.aspects.Circ type G = Map[String, Nullable] override def apply(n: Nullable): Nullable = { val sup = new Circ[Boolean, G](false, n.nullable _) new Nullable { def nullable(g: G) = sup(g) } } } Why not just the following: def circNullable(n : Nullable): Nullable = { import oalg.algebra.aspects.Circ type G = Map[String, Nullable] val sup = new Circ[Boolean, G](false, n.nullable _) return new Nullable { def nullable(g: G) = sup(g) } } ? * Some of the code in oalg.algebra.demo.grammar.Main had better been put oalg.algebra.demo.grammar.Grammars. I was expecting the former to only contain demo code for the latter, not code like the various Profile lifters. * It took me a while to understand what the GrammarProfile feature was doing in oalg.algebra.demo.Grammar.Grammar... I still don't understand why for example GrammarProfile.Terminal.profile returns a singleton map of self to 1 and not e.g. 0... OVERALL ASSESSMENT First, some major comments: * Regarding your stacks example. I've been thinking for a while about the precise meaning of your StackAlg and CounterAlg. They both look like a trivial or degenerate form of an algebra: trait StackAlg[In,Out] { def stack() : Out } trait CounterAlg[In,Out] { def counter() : Out } From their definition, they are clearly equivalent, and have nothing to do with stacks or counters. My understanding is that you are actually using a one-constructor object algebra (a class family with only one member), that I would call SimpleFactoryAlg: trait SimpleFactoryAlg[In,Out] { def produce() : Out } and that the link with stacks or counters only comes from the factory implementations that add specific functionality to the one-constructor object algebra. In this sense, this example seems more like a demonstration that you can recover normal inheritance from your model of family inheritance. If these insights are correct, I would have liked a discussion along these lines in the paper. After re-reading the description of this example in the paper, I have to say that I do not find it clear from the text that the example is such a simple base case of your technique as what I find it to be in the code. I therefore find the example disappointing. Why not mention that it is a simple base-case in the text? You have two more complicated examples (the expression problem and grammars), which is quite sufficient in my opinion. * On the other hand, I found the Grammar example very interesting and compelling. I have dealt with similar code in Haskell before and found the "First algorithm depends on Nullable"-problem very recognizable and your solution to the problem looks very nice. The same comment applies for the Circ aspect which is reused by different features. * Finally, I would be less distrusting of your use of reflection if it were compile-time reflection and not run-time. I understand that Scala offers both, so I am wondering if there is a reason you have not used it (apart from the fact that run-time reflection is rather easy here)? Similarly, have you attempted to avoid reflection altogether and use some form of generic programming instead? Nevertheless, you are quite clear about your use of run-time reflection in the paper, so this is just a remark. All in all, I find that the artefact delivers on what is promised in the paper: the implementation of object algebra's corresponds to what is described in the paper, and I did not notice any additional hard complications that were not mentioned in the text. The description of the demo applications in the paper text were short, so I found it very interesting to look at the two demo applications. I found the stacks example slightly disappointing (see above), and I found it hard to see the pattern there as more than a limited version of a single-object composition feature like traits. On the other hand, I found the grammars example rather compelling (having worked on similar libraries in Haskell before), and I find it provided a much stronger demonstration of what object algebra's are useful for. That being said, the code is just demo code for object algebra's, it is far from ready for use by a wide audience. Regarding quality, the code would have benefited from more documentation here and there, but it was still possible for me to understand it in a reasonable amount of time. Because the grammars example gave me a much better understanding of the technique described in the paper and because I found it a quite compelling demonstration of the technique, I find that the artefact exceeded my expectations. If there had been more documentation and less Scala-isms, and if the stacks example had not been slightly disappointing to me after reading the text (see above), I would have given the top score. SUGGESTIONS Slightly more documentation and cutting back on Scala-isms would be appreciated. ---------------------------------------------------------------------- PAPER NUMBER 90 ARTIFACT GRADE met expectations PAPER SUMMARY AND CONTRIBUTIONS This paper presents the use of object algebras to support a powerful and expressive form of FOP. Concretely, the authors implemented in Scala two type system features, 'intersection types' and 'type-constructor polymorphism' to provide object algebras with expressive and practical composition mechanisms. They also implemented a modular mechanism for self-references when delegation-based combinators are present. This paper has four contributions: FOP using object algebras, generic object algebra combinators, modular self-references and two case studies. ARTIFACT SUMMARY A set of source code artifacts with the implementation of the object algebras supporting FOP. The implementation is done in Scala and uses some Java facilities. These artifacts correspond to the generic object algebra (algebra.core), both case studies Stacks and Grammar to show the applicability of object algebra composition (algebra.demo), and the examples provided in the paper (algebra.paper). ARTIFACT PACKAGING The only inconvenient I had was when installing the Scala IDE. For the specified Eclipse Juno, the corresponding link for downloading Scala fails, as there are missing dependencies. In my MAC OS X 10.6.8, the following link worked instead: http://download.scala-ide.org/nightly-scala-ide-juno-210x ARTIFACT IMPLEMENTATION AND USABILITY OVERALL ASSESSMENT The contributions of the paper are shown by the source code artifacts and they met my initial expectations. Even though, the paper itself illustrates considerable portions of code, it is very important to be able to load and explore the whole code, and execute the case studies. The demos were very useful to see your approach working, and this was complemented with the examples included in the paper package. However, being a non Scala user, I cannot comment on the quality and efficiency of the implementation proposed. SUGGESTIONS ---------------------------------------------------------------------- PAPER NUMBER 90 ARTIFACT GRADE met expectations PAPER SUMMARY AND CONTRIBUTIONS The paper describes a trait and mixin pattern for feature-oriented programming, and an implementation of it in Scala. The pattern is similar to related work in Mixin Layers, various extensible visitor patterns, and other solutions from the feature-oriented programming literature. Object algebras are distinguished by being implemented in pure Scala, which is an already existing and popular language not designed explicitly for FOP. ARTIFACT SUMMARY The artifact is a Scala IDE project for Eclipse. It contains definitions for all the boilerplate and mixing patterns described in the paper in a library package, and the two extended examples described in the case studies section of the paper, which use the library module. These both run out of the box, and both print their test results to the console. Finally, there are other examples from the paper in a separate package. ARTIFACT PACKAGING I performed this review on a Thinkpad x230i running 64bit Ubuntu 12.04 Overall, the installation instructions were great. Thank you for including instructions/packages for the (necessary) Scala 2.10! Ubuntu's repositories only have Scala 2.9 on my release. Minor annoyances (not the authors' fault, just worth noting for future READMEs and users): - I had to install the EGit plugin even though I'm under Indigo, and the instructions suggested that I would only have to do so under Juno. I changed the path for software updates to say "indigo" at the end instead of "juno", and that seems to have worked. - I got an error about swt interfaces when I tried restarting Eclipse after installing Git and ScalaIDE, but it was easily fixed by the top answer from this StackOverflow post: http://stackoverflow.com/questions/10165693/eclipse-cannot-load-swt-libraries ARTIFACT IMPLEMENTATION AND USABILITY The code in oalg.algebra.core is great; it's nice that the core constructs take only ~110 LOC to express. I tried to define an extension to grammars that would provide a reverse method, which would return a new grammar that accepted the reverse of the strings in the original. I didn't figure out how to mix this in with the others. I think it's just a parameterization problem, but I'm not sure. In the interests of getting my review in on time I stopped fiddling with it, but here's the definition I added to Grammar.scala: trait Reverse[S] { def reverse(g: Map[String, S]): S } trait GrammarReverse[S <: Reverse[S]] extends GrammarDesugarAlg[S, Reverse[S]] { type G = Map[String, S] def Alt(lhs: S, rhs: S) = self => new Reverse[S] { def reverse(g: G) = fself.Alt(lhs.reverse(g), rhs.reverse(g)) } def Seq(leftNowOnRight: S, rightNowOnLeft: S) = self => new Reverse[S] { def reverse(g: G) = fself.Seq(rightNowOnLeft.reverse(g), leftNowOnRight.reverse(g)) } def Terminal(word: String) = self => new Reverse[S] { def reverse(g: G) = fself.Terminal(word.reverse) } def NonTerminal(name: String) = self => new Reverse[S] { def reverse(g: G) = fself.NonTerminal(name) } def Empty() = self => new Reverse[S] { def reverse(g: G) = fself.Empty } } def grammarReverse[S <: Reverse[S]] : OpenGrammarAlg[S, Reverse[S]] = s => new GrammarReverse[S] { lazy val fself = s } And then in Main.scala, I tried adding: // near the top trait PNR extends Parse with Nullable with Reverse[PNR] // further down val f2 = fclose( combine[Parse, Nullable with Reverse[PNR], PNR]( decorate(grammarParse[PNR], new Memo), combine[Nullable, Reverse[PNR], PNR]( decorate(grammarNullable[PNR], new CircNullable), grammarReverse[PNR] ).asInstanceOf[OpenGrammarAlg[PNR,PNR]])) But this yields really long type errors about mismatches between Parse with Nullable with Reverse[PNR] and PNR, and I'm not sure how to bootstrap this. I may also need to define a CircReverse, but that's really tricky because there isn't an obvious base case to start from (the other examples use Set() and false, but I want the equivalent of fself.Empty(), which isn't available there). Maybe I'm missing an example of a use of object algebrae to construct new values of homogeneous type from within an operation. This feels like it should be doable and I'm just missing something. For tweaking the implementation of algebras, I would prefer better tests. The tests in the artifact are all based on printing, making it a little tricky to tell, if I changed something in the implementation, if things broke. I'd prefer unit tests or assert statements, or something that clearly gives a message when it breaks. OVERALL ASSESSMENT Great packaging, implementation is complex but concise and very clearly matches the paper and is in pure Scala, which is cool. I was expecting an example of the thing I was trying and didn't find one (but maybe something in Stacks.scala does it better, I spent most of my time trying to understand Grammars.scala). From the paper, this artifact was exactly what I expected, and not a whole lot more. The examples work to help understand what's going on, and definitely reflect the paper, but more of a tutorial style in the artifact, with, for example, "fill in the blanks" examples, would have gone above and beyond what the artifact needs to do to back up the paper. SUGGESTIONS OTHER After chatting with the committee, we fixed the silly parenthesis bug in my example program. Here's the updated instantiation with a few test cases: val f2 = fclose( combine[Parse, Nullable with Reverse[PNR], PNR]( decorate(grammarParse[PNR], new Memo), combine[Nullable, Reverse[PNR], PNR]( decorate(grammarNullable[PNR], new CircNullable), grammarReverse[PNR] )).asInstanceOf[OpenGrammarAlg[PNR,PNR]]) // A ::= | "ac" "b" A val toReverse = Map("A" -> f2.Alt(f2.Empty,f2.Seq(f2.Terminal("ac"), f2.Seq(f2.Terminal("b"), f2.NonTerminal("A"))))) val gram = toReverse("A") gram.parse(toReverse, Seq("ac", "b"), x => println(x)) gram.reverse(toReverse).parse(toReverse, Seq("b", "ca"), x => println(x)) gram.reverse(toReverse).parse(toReverse, Seq("ac", "b"), x => println(x)) gram.reverse(toReverse).reverse(toReverse).parse(toReverse, Seq("ac", "b"), x => println(x)) println(gram.nullable(toReverse)) ----------------------------------------------------------------------