--------------------------------------------- Paper: 3 Title: Partial Vectorisation of Haskell Programs -------------------- review 1 -------------------- OVERALL RATING: 1 (weak accept) REVIEWER'S CONFIDENCE: 2 (medium) ----------------------- REVIEW -------------------- This paper describes "partial vectorisation" of functional programs. Vectorisation is a very "intrusive" transformation that reorganizes entire data structures -- changing their types as well as the types of the (higher-order) functions that operate on them. According to the authors it has only ever been done on entire programs, which is problematic in practice since vectorized code must interact with unvectorized modules, external resources, etc. As a reviewer essentially unknowledgable with respect to vectorization (but reasonably familiar with the design and implementation of functional languages), I found this paper extremely topical to DAMP and tackling what seems like an important issue for making efficient parallel implementations practical. In the end, the transformation supporting selective vectorisation ends up seeming fairly straightforward/elegant, which I view as a strength since it clearly required distilling a difficult problem down to its essence to reach the transformation presented. My primary criticism is that the uninformed reader could really use another page of background on how full vectorisation works, at least in the monomorphic case. The paper really does too much "not the focus of the present paper" because it builds on so much of the authors' prior work [4,5,6,8,...]. I feel the present work would be better served with an exposition that took a very simple language, showed full vectorisation, then showed partial vectorisation, then explained for experts how the bells/whistles/issue of polymorphism, type families, partial application, etc. are orthogonal issues (i.e., partial vectorisation will work with a real language/compiler). In the end, this is interesting work the DAMP community would be interested in, so we should accept the paper. Here are a few details for the authors: * page 2: "at a concrete example" -> "with a concrete example" * page 6: Figure 3 confused me for a short moment until I realized that defined type constructors could be nullary * page 8: "informal types" -- I wasn't sure what you meant by "informal"; do you just mean "Haskell-ish types" or something? * page 10: When we get to Figure 4 -- the heart of the matter -- we see nothing particularly parallelism-specific. Probably because you're not focusing on vectorisation, but rather how to make it selective, I fail to see a single [::] in Figure 4. That does two things: 1. It makes the paper harder to understand. 2. It makese what you're doing look *vaguely* like other transformations, such as SML compilers that selectively flatten tuple arguments to functions. * page 11: I couldn't decide if the [[ in Just [[ let V_v ... ]] was the right brackets to use here. Isn't the argument to Just already fully translated in the example? * page 11-12: Section 3.5 was hard to follow because the first part was describing part of Figure 4 (the let case) but then it discussed recursion, which is not in Figure 4. It would help the reader to be clearer what is in the figure and what is not. -------------------- review 2 -------------------- OVERALL RATING: 1 (weak accept) REVIEWER'S CONFIDENCE: 3 (high) ----------------------- REVIEW -------------------- This paper extends earlier work of the authors on transforming nested data structures into flattened ones which better suit a data parallel execution. It is based on the observation that a practical applicability of that transformation requires the ability to mix code fragments which have been transformed with others that have not been transformed. The authors propose a transformation scheme which tries to flatten (vectorise) programs whenever possible but nevertheless is capable to properly embed non-vectorised sub expressions. Overall, it is a well-written paper about a rather technical problem that arose in the context of the DPH project. The solution does not appear to be earth-shaking, however, most elegant solutions share this property. It would have been nice if the authors would have discussed a bit more the potential for optimisation. In particular, i would have hoped to read about the potential amortisation or the lack thereof when frequent conversions are required. Do the authors intend to apply cost-modelling here? If so, what would be the kind of cost abstractions they consider useful? Also, I found some of the formalisations provided in the paper not overly satisfying. Some notation is used with very little explanation. When paired with unusual extensions such as you syntactic categories in Fig.3 and other oddities of it such as the introduction of $f$ and $v$ without further use, or the different notations for non-terminals, readability does suffer a lot. Another example is the formalisation of the key contribution itself, i.e., the partial vectorisation. It appears to be a bit ad-hoc. The naming of the schemes is less then intuitive and some of the textual as well as some of the formal omissions make it difficult to follow the details. I am sure that some more brushing on these parts would improve the readability of it a lot. Even though the contribution of the paper may not appear to be overly impressive, I think that it represents an important stepping stone for making DPH suitable for real world use. Therefore, I see the paper as a notable contribution at the core of the workshop's topics which deserves publication. -------------------- review 3 -------------------- OVERALL RATING: 2 (accept) REVIEWER'S CONFIDENCE: 3 (high) ----------------------- REVIEW -------------------- This paper is the latest report on the ongoing development of Data Parallel Haskell. The flattening transformation, a technique for compilation of nested data parallel programs, was originally presented by Blelloch and Sabot in conjunction with the implementation of NESL. The original flattening papers were informal. Previous DPH research has formalized flattening, also known as vectorization, and augmented the original transformation with important extensions, including, notably, the ability to handle algebraic data types, parametric polymorphism, and higher-order functions. The present work provides an account of an approach to compile a mixture of vectorizable code and intrinsically unvectorizable code, such as System.IO.print. In this context, some code is to be vectorized, and some not, while previous presentations have focused on full vectorization of the code at hand. The heart of the paper is the presentation of a trio of mutually recursive transformations of data parallel progams in a small core language. These transformations yield programs that have been vectorized where possible and otherwise either left alone or infused with suitable conversion code. (A question: do the authors believe this transformation vectorizes a program to some maximum possible extent? This question, and the necessary quantitative machinery for reasoning about it, do not seem to be part of the present study.) The presentation is accompanied by discussions of interesting cases, including recursive let bindings. The authors also discuss the use of GHC's interface files as a mechanism for gluing together vectorized and unvectorized code across module boundaries. The success of the authors' strategy cannot yet be seen in action, as the implementation of the present system is not yet released. The problem at hand is clearly of great practical interest, as the interaction between data parallel computations and the often sequential demands of the outer world must be managed in any realistic programming language. This reviewer recommends this paper for acceptance as a novel, well-written, sensible approach to a matter of considerable current interest. A note on the presentation: it was unclear to me what is meant by bare brackets surrounding terms and subterms (as opposed to the application of one of the transformations, say, SV). Perhaps the authors could make this clear in the text. (Also, ``workhorses'' is one word.)