-------------- Reviews on submission 104 -------------

-------------------- review 1 --------------------

PAPER: 104

TITLE: Parsing with derivatives

OVERALL RATING: 4 (OK paper, but I will not champion it.)

REVIEWER'S CONFIDENCE: 2 (medium)

----------------------- REVIEW --------------------

MAIN PART

The paper describes an original approach to the derivation of parsers from grammars. The approach is based on the observation that context-free grammars are closed under Brzozowski derivatives, and such derivatives can be easily computed. The parser described hence parses a string by lazily computing the derivatives of the grammar for each character met. Quite surprisingly, such a parser seems very easy to encode, especially in a language that supports streams and lazy computations, can parse every grammar, and is quite efficient.

I found the paper very interesting. The studied problem is very important, and is surprising to meet original results in a field that has been explored so much. I enjoyed the first pages of the paper very much, they are extremely crisp and clear. Unfortunately, around page 8, the paper starts getting more and more obscure; chapter 7 end abruptly, and chapter 8, which is probably the most important one, is quite obscure. At the end I still think that the paper should be accepted, but I really hope that the authors will be able to beef section 8 up to the point of making it readable for me.

Detailed remarks for the authors only

Example 1: the parse tree is: => the pasre tree of ' () ' is;

In general: you should write <B||B->\epsilon> rather then <B|B->\epsilon> (this is not quantum theory, after all...)

The non-deterministic state machine: the language in \Sigma is a language over A', not over A, right? You should say that explicitly.

In the rules for bra's and ket's, the consequences should look like

   (L,w) =>^{\bra{n}} (D_{\bra{n}}(L),w)

I think you forgot the derivative, right?

The parse-string machine pushed a bra when it meets it, but never pops it. You can easily adjust the last rule of section 7 to pop it, but the real question is: why do you push it?

The end of section 7 is too abrupt. You have described a nice pair of abstract machines, but now you should tell me something a bit more concrete about the amount of nondetermins involved, how much would that hurt me in practice...

Page 10: the monotonicity for parser combinators should look like:

  forall p in \tau_X(w) exists p' in \tau_X(w') such that first p prefix of first p'

Section 8 is obscure. It is too terse. The equations look right and look convincing, but I was totally unable to create a mental picture about how this machinery actually work. I understand that such a combination of non-determinism and lazyness creates code that tends to work in a mysterious way, but still the section is extremely unsatisfactory, especially.

Section 9: a bit unreadable, at least for a non-scala programmer.

PROS AND CONS

+ interesting solution for an interesting problem

+ elegant

+ innovative

+ first 8 pages are a pleasure to read

- crucial sections are almost unreadable

REBUTTAL

-------------------- review 2 --------------------

PAPER: 104

TITLE: Parsing with derivatives

OVERALL RATING: 2 (Weak paper, though I will not fight strongly against it.)

REVIEWER'S CONFIDENCE: 4 (expert)

----------------------- REVIEW --------------------

MAIN PART

The authors describe how one can use Brzozowski-style derivatives to

implement parser combinators. They claim that their technique leads to

simple implementations, and this seems to be the case. They also claim

that their implementation is efficient, but give no solid evidence for

this (they added a special combinator to get decent numbers from their

single reported experiment). Another claim is that their parser

combinators can handle left recursion, but they give no evidence for

this.

The authors seem to be unaware that Danielsson presented essentially

the same technique at TYPES 2009 ("Mixing Induction and Coinduction").

However, Danielsson's draft paper does not try to sell the technique,

only using it as a vehicle to implement provably total parser

combinators, and he does not address efficiency of parsing, so there

could be a place for both papers.

The authors seem to claim that their implementation is a lot more

efficient than other parser combinator libraries:

 "[...] they are easy to implement, and easy to implement as

 libraries (like top-down parsers), yet they are efficient and

 expressive (like bottom-up parsers)."

However, they have not made any head-to-head comparisons, and they

have not cited a single paper discussing efficient parser combinators.

Generally there is a serious lack of references to related work on

parser combinators.

Section 7 discusses another parsing technique (also based on

derivatives). However, I found this section to be poorly written and

hard to follow. I suggest that it should be removed.

If the claims about efficiency had been followed up with substantial

evidence, then I would have recommended that the paper should be

published. As it stands I do not make such a recommendation.

Detailed comments:

Section 2:

"This technique was lost to the “sands of time” until [paper from

2009]" A quick web search will tell you that a large number of papers

published before 2009 have used Brzozowski derivatives (or

generalisations), so this comment is incorrect. See for instance the

work of Rutten, including "Automata and Coinduction; an exercise in

coalgebra" and "Automata, Power Series, and Coinduction: Taking Input

Derivatives Seriously".

Section 6:

The expansion of D_x(List) would be easier to follow if you added a

step between the second and third lines.

"the null string terminal" and "the empty nonterminal" may not exist

in N, so they may have to be added to N'.

One could be led to believe that the last "and:" only applies when

m = 0.

"The empty nonterminal arises frequently with derivatives, and if this

reduction is applied aggressively, the grammar will remain a

manageable size." You give no proper motivation for this statement. In

fact, your discussion of the "special closure construct" in Section 9

seems to imply that this statement is false. I suggest that you remove

this statement.

Section 7:

The machine in this section does not make sense to me. First of all

you do not state what the machine should accomplish; my guess is that

you intend

 ((L, s), <>) ->* ((L', <>), <t>)

to hold iff t is a parse tree which witnesses the membership of s in

L. Furthermore you give no reason (such as a proof) to believe that

the machine satisfies this specification. For instance, you push

nonterminals onto the stack, but you never remove them (I suspect that

the last rule should remove a nonterminal), and it seems strange that

the state is unchanged in the rules involving "first".

I think the paper would be better if Section 7, which is not central

to the paper, was omitted.

"This approach is not well suited to typed languages, since a literal

implementation of the parsing machine must use a generic parse-tree

type, or else violate type-safety with casts for reductions." I

suspect that you could do better with a dependently typed language, so

I suggest that you remove this sentence.

Example 1: "the parse tree is:" I think you mean "one parse tree is:".

"The parsing machine demonstrates that, even without reduction rules

associated with the grammar, we can use derivatives to construct a

concrete syntax tree." I do not follow this sentence. What kind of

reduction rules are you referring to?

Section 8:

The parser combinators that you give seem quite outdated to me. The

functional programming community moved away from this set of

combinators more than a decade ago, in favour of combinators based on

monads or applicative functors. Please motivate this choice.

You state two properties that parser combinators must satisfy, but you

never really make any use of these properties. Are these properties

necessary for your development? Is your definition of a parser

combinator a function which satisfies these properties?

"A parser combinator is monotonic iff..." I assume that the second

instance of \sqsubseteq should be read pointwise.

"the meaning of an input expression w <- A^∗ is contained within

tau_N(w)" In fact it is the one and only (complete) result, right?

"D_c(c) = eps -> \w.{(c, w)}" This does not make sense, the second

argument of -> is not a parser.

Section 9:

Your parsers accept infinite streams as input. However, parseFull

clearly fails to terminate for infinite input. Why do you not restrict

the input to finite lists?

Your parsers return potentially infinite streams of results. However,

your parse function uses "append", which (essentially) throws away its

second argument if the first is infinite. Wouldn't it be better to

return a fair interleaving of the two streams?

In internalDerive you seem to have renamed a and b to first and

second, respectively.

"the longest possible parse first" Why is this relevant for

performance? If you return all possible parses, then the order in

which they are returned should not matter, and for unambiguous parsers

at most one result is returned anyway. I can imagine that your

optimisation matters in the (atypical?) case of an ambiguous parse, if

you are not interested in inspecting all the results, but only want to

see that there is more than one.

The sentence before the table seems to be unfinished.

I assume that "43 m" should be "43 ms".

"These results suggest that derivative-based parser combinators scale

well enough to be useful in practice." To me this result suggests that

I may have to repeatedly add new special-case combinators (like your

closure operation) to ensure decent performance.

Section 10:

"derivative-based parsing defies the classical taxonomies", "Top-down

methods", "back-tracking"... Are you not aware of parser combinator

libraries which use breadth-first techniques (which your combinators

also do)? See, for instance, Claessen's "Parallel Parsing Processes".

"these methods have not been able to handle left-recursive grammars"

You should check out Lickman's MSc thesis "Parsing With Fixed Points"

and "Parser Combinators for Ambiguous Left-Recursive Grammars" by

Frost et al.

"Philosophically, neither derivative-based method “feels” like a

top-down parsing method." To me your combinator implementation does

feel like a (breadth-first) top-down method.

You claim (implicitly) that your parser combinators can handle left

recursive grammars. However, I doubt that you can handle grammars of

the form "n ::= n". If you can handle such grammars, please explain

how you do it. Otherwise it would be interesting to know exactly what

kind of left recursion you support.

"they are efficient and expressive (like bottom-up parsers)" This

seems to imply that there is a language which can be parsed using

bottom-up techniques, but not using top-down techniques. Can you

verify this claim?

You may want to cite Frost and Szydlowski, who claim worst-case cubic

time for parsing ("Memoizing purely functional top-down backtracking

language processors"). Swierstra's work on efficient parser

combinators is also relevant (many papers).

References:

Improve formatting.

PROS AND CONS

+ Simple technique for implementing parser combinators.

- The technique has been presented before.

- No substantial evidence for claims of efficiency.

- Section 7 does not make sense to me (but could be removed).

REBUTTAL

-------------------- review 3 --------------------

PAPER: 104

TITLE: Parsing with derivatives

OVERALL RATING: 2 (Weak paper, though I will not fight strongly against it.)

REVIEWER'S CONFIDENCE: 2 (medium)

----------------------- REVIEW --------------------

MAIN PART

The paper proposes a new parsing technique based on "derivatives",

inspired by the derivatives of regular expressions and extended to the

derivatives of context free grammars.

Because context free grammars may be ambiguous, they propose to compute the

set of all parse trees but using lazy evaluation to share and delay the

computation. They present their framework and an implementation in Scala.

They claim that their technique is efficient in practice.

EVALUATION

Parsing techniques are old and well-established, although the current status

of the theory is still unsatisfactory: grammars are still a burden to write

and any advance of this topic is welcomed.  However, the topic must be

addressed very seriously.

Given this, this work is potentially interesting as a possible way to

improve the state of the art situation, but not in its current

presentation, as the paper should not just _claim_ that using derivatives

for parsing is feasible, but _demonstrate_ that writing grammars with

combinators is at least both as convenient and as efficient as using

existing technology.

The first aspect is not discussed at all in the paper.  As for efficiency,

which is claimed, the benchmarks are really small, and perhaps probably

representative of existing grammars, and the results are not compared with

other parsing techniques.

Other questions arise: what happens when the grammar is largely ambiguous?

Do you intend to reject those, or pick the meaning of the things that you

are parsing at random?

The overall structure of the paper is not very clear either. You should

gives us a road map at the beginning and make it clear how the different

sections fits together.

OTHER COMMENTS

Section 7 and 8 are the key sections of the paper to understand your

proposal. However, I have problems with both.

I don't understand while your parsing is decomposed into production of an

intermediate parsing string that is then consumed by the machine that

produces a syntax tree. Since the parsing string is a linear representation

of the parsing tree, why can't you work with the parsing tree itself, which

is more structured than the parsing string? Why can't you directly extract

a syntax tree from the parsing tree? Could you run the algorithm in Section

7 on an example?

In section 8, you compute the derivatives of parser combinators, but you

could instead compute the grammar defined by the parser combinator and

compute its derivative in one step. What is this bad/worse than computing it

directly?

- One line above section 2: "could [to<-] modify"

- Section 2, Line 10: "derivative---[they<-??] critical property"

- One line above Section 7: "remain [<-of] a manageable size.

- Computation of the derivative, above theorem 1:

 You could explain the derivatives, especially for rules n-> s1..sn

 and perhaps give an example.

- Last two lines above section 8: "The parsing machine demonstrates...

 a concrete syntax tree".

 I don't really understand what you (intend to) mean.

- Section 8.1, Line 1: "ability [the<-to] combine them"

- End of section 8.1:

 you should say and comment on the fact that these definitions are

 recursive.

- First line of section 8.4: "to be able [<-to] parse"

- Section 8.4: How do you use these inequations? Why do you give this list of

 formulas without any comment?

- Section 8.5: what are the lambda-terms on the right of --> ?

-------------------- review 4 --------------------

PAPER: 104

TITLE: Parsing with derivatives

OVERALL RATING: 1 (Serious problems. I will argue to reject this paper.)

REVIEWER'S CONFIDENCE: 3 (high)

----------------------- REVIEW --------------------

MAIN PART

SUMMARY

The paper proposes a basic algorithm for determining whether a sentence s is a

member of a context-free language L: (i) if the sentence is empty, determine

whether L contains the empty string (a decidable problem); (ii) if the

sentence is of the form c.s, determine whether the suffix s is a member of the

derivative c^{-1}.L. Because the derivative of a context-free language can be

effectively constructed, this is an algorithm.

The contribution of the paper is in generalizing this basic algorithm in two

ways: (i) instead of just determining membership, the parsing algorithm can be

made to return a concrete syntax tree, or a semantic value; (ii) instead of

viewing the derivative as an operation that accepts a monolithic grammar and

produces a monolithic grammar, one can view it as an operation that accepts a

parser combinator and produces a parser combinator; this means that the

parsing algorithm is amenable to a modular, combinator-based implementation.

EVALUATION

The introduction of the paper is somewhat irritating, for two reasons. First,

it promises a lot ("simplicity, feasibility, and ubiquity"), which the paper

does not clearly deliver. Second, it criticizes the most popular parsing

methods (LL and LR) on the grounds that the constraints that they impose, in

order to rule out ambiguous grammars, are difficult to grasp. I can accept

this criticism. But the authors do not offer any solution to the ambiguity

problem: their algorithm produces a parse forest. This leaves the programmer

faced with the task of writing and debugging disambiguation filters, an error

prone task. At least, an LR parser generator is able (in principle, and some

implementations actually do this) to accurately explain why the grammar seems

ambiguous. It can produce a sentence that is a prefix of the fringes of two

distinct, valid parse trees.

The first claimed contribution of the paper is the remark that the derivative

of a context free language can be effectively constructed. (A proof appears in

section 6.) This is in fact not a contribution. This property of context free

languages is well-known, at least in the formal language community (perhaps

not in the programming language community). The derivative of a formal language

is also known as its left quotient, and written c^{-1}L. See, for instance, the

following paper, which exploits this property intensively:

 Jean Berstel and Luc Boasson. Towards an algebraic theory of context-free

 languages. Fundamentae Informaticae, 25(3):217-239, 1996.

The remainder of the paper contains two distinct developments. In section 7, a

version of the derivative-based parsing algorithm is developed, which produces

concrete syntax trees. Then, in sections 8 and 9, another version is developed,

which produces programmer-defined semantic values, and is combinator-based.

It is not clear to me why these two distinct developments co-exist. In my eyes,

the approach of sections 8 and 9 seems superior, because it is more flexible

(it is not limited to producing concrete syntax trees) and modular.

The idea that the notion of a derivative can be generalized to parser

combinators is interesting, and worthy of thought. To some extent, section 8.2

is where the paper really begins! Section 8 provides a mathematical view of

the problem, while section 9 describes part of a Scala implementation.

This material is interesting, but can be criticized on several grounds:

1. The complexity analysis of the algorithm is absent. The algorithm seems

very expensive in the worst case: indeed, the effective construction of a

derivative in section 6 causes a quadratic blow up of the size of the grammar,

and this operation is iterated at every character of the input stream! In

fact, section 9.1 mentions that a naive implementation of the algorithm is

unusable (exponentially slow), and that special support for the Kleene star

had to be added. However, there is no argument that this patch is sufficient

for the algorithm to become useable. A worst-case analysis of the space and

time complexity is needed, and, if this worst-case complexity is bad (say,

exponential), then a formal or semi-formal argument is needed why the behavior

of the algorithm remains tolerable in practice. In light of the efficiency

claim found in the introduction, this is indispensable!

2. The description of the implementation could be improved. In particular,

memoization and sharing seem to play a crucial role. It seems that two

attempts to compute the derivative of a parser combinator should return the

same object. This includes the particular case where the second attempt is in

fact nested within the first one (i.e., it is a recursive call). For instance,

if the grammar contains the single production L -> LM, a call to L.derive(t)

will (indirectly) cause another call to L.derive(t). What happens then? By

which mechanism is non-termination avoided? This is not clearly described.

The paper contains four lines of text that seem to concern this topic (p.15,

"It is important to note [...] immediately suspended."), but I find them

obscure. I note that there seems to be a distinction between derive and

internalDerive, which is not explained in the paper; my guess is that the

former may be a memoizing version of the latter, using a table indexed by

tokens. Is this the case?

3. The introduction claims "ubiquity", that is, if I understand correctly, it

claims that the method is very easy to implement as a library. This may be

true, but the paper lacks a convincing argument why this is so. In particular,

how is this approach superior to the other parsing combinator libraries in

existence? The paper lacks a good comparison with other combinator-based

parsing techniques.

It seems that there might be a connection between the technique presented in

the paper and intersection parsing (see e.g. chapter 13 of the excellent book

"Parsing techniques", by Grune and Jacobs). Computing the derivative of a

context free language with respect to a terminal symbol c is closely related

to computing its intersection with the regular language c(.*). Intersection

parsing, as described by Grune and Jacobs, computes the intersection of the

grammar with the input (which is a string, so a regular language!) and

simplifies the resulting grammar, which can then be viewed as a parse

tree. Could one view the approach presented in the paper as an incremental

(and modular) way of doing intersection parsing?

In conclusion, although the paper contains an interesting idea, its

investigation is not sufficiently thorough, and a clear case in favor

of this parsing technique is missing.

DETAILED COMMENTS

The authors state in section 7 that "a literal implementation [...] must use a

generic parse-tree type, or else violate type safety with casts for

reductions". Strictly speaking, this depends on which type system one has in

mind. If the type system is ML, for instance, the claim is probably true. If

the type system has GADTs, however, it is quite possible that the discipline

of the parsing machine can be encoded in the types. This has been done, for an

LR parsing machine, and for an arbitrary but fixed grammar, in the following

paper:

 François Pottier and Yann Régis-Gianas. Towards efficient, typed LR parsers.

 In ACM Workshop on ML, volume 148(2) of Electronic Notes in Theoretical Computer

 Science, pages 155-180, 2006.

To the best of my knowledge, both Haskell and Scala have GADTs, so the authors

might wish to check this out.

p.5, "for any class of decidable languages closed under the derivative,

derivatives may be used to determine membership". I am not sure what is meant

by "decidable" here. If it is meant that membership in the language is

decidable, then this is a tautology. Perhaps one should understand that

membership *of the empty word* in the language is decidable, since effectively

that is all that is needed?

p.5, "the derivative is closed under regular operations": unclear formulation.

p.7, before theorem 1: please indicate the interval over which the index i

ranges. My guess is 0 \geq i < m. The particular case where m = 0 seems

redundant: when m = 0, there is no suitable index i, so no production is

generated, which means D_c(n) is empty. In fact, the notation \emptyset

in the right-hand side of a production does not make sense, since the

right-hand side of a production is supposed to be a sequence of symbols.

p.7, "the empty nonterminal": this has not been defined. I assume this

explains the use of \emptyset above. Define it.

p.8, example 1: "for the grammar [...] of balanced parentheses [...] the parse

tree is": I assume this should be: "the parse tree for the string '()'".

p.8, "A parse string is [...] containing both nonterminal markers and

reduction markers"." Please indicate at this point that a parse string also

contains elements of the alphabet A. In fact, the definition of the alphabet

A' should be moved to this point.

p.8, "we construct a new grammar [...] over parse strings": please change

this to "a new grammar over the alphabet A'".

p.8, the definition of \Sigma mentions \mathbb{L}: I guess this should be

\mathbb{L}_{A'}.

p.9, "a second rule for producing bras": is the rule correct? In the

right-hand side of the conclusion, instead of L, I would have expected the

derivative of L with respect to <n|. (The rule, as it stands, clearly causes

an infinite stream of <n|'s to be produced! Similarly for the third rule.

p.9, "the parsing machine reduces": one might wish to state the invariant

of the parsing machine which guarantees that reduction can never fail (by

lack of material on the stack).

p.9, "popular as of late": please provide citation(s).

p.10, the statement of the monotonicity condition is somewhat unclear: the

assertion \tau_X(w) \sqsubseteq \tau_X(w') compares two sets of pairs. An

ordering over pairs is defined, but an ordering over sets of pairs is not

defined.

p.11, the authors might want to spend more space explaining the definition of

the derivative of a parser combinator -- why is the right definition? and how

does it relate with the definition of the derivative of a formal language?

Can one recover the latter as a degenerate case of the former?

p.12, section 8.3: the parser combinator \epsilon is used, but has not been

defined. What is its type? In particular, what semantic value does it produce?

(A unit value?) What is the meaning of the notation \lambda\epsilon. ...

p.12, equation (3): the elegance afforded by the use of \delta in the

definition of the derivative of a concatenation (p.5) seems to have been lost

here.

p.13, "in practice, the cost [...] as they are derived". I don't know what

this means. Please be more precise and include a formal complexity claim.

p.14, "parse trees of type A" should really be referred to as "semantic

values", since they may not be trees at all -- they are programmer-defined.

p.14, "its implementation follows eq.2": actually, eq.2 corresponds only

to the "else" clause of the code, so the text is badly worded. Same problem

with eq.1 a few lines later.

p.15, the distinction between "derive" and "internalDerive" is not explained.

p.15, the derivative of union "short-circuits if it finds either arm is

empty": is this important, say, to ensure termination? or is it just a minor

optimization?

p.16, the fact that a naïve treatment of the Kleene star required exponential

time, and the fact that right recursion is significantly more efficient than

left recursion, are worrisome. These problems are perhaps partially masked by

the introduction of "the special closure construct", but how do we know that

they are gone?

p.16, the test suite consists of just one grammar and a set of randomly

generated inputs. This seems far from representative of actual usage...

p.17, "the cost of that compilation is amortized across the entire parsing

process". I don't know what is meant by "compilation" here, nor do I know

why its cost is amortized. Please explain.

p.18, "these combinators are slowly transforming and unfolding the grammar

itself into a parse tree": this seems to be an interesting intuition. Why

not try to make it more formal?

TYPOS

p.2, "could to modify"

p.2, "they critical"

p.6, "attempt interpret"

p.10, "Operations or combinators"

p.10, "the remainders of the input"

p.12, "is base case"

p.13, "able parse"

p.15, "short-circuiting if the first element is nullable": should this be: "is

not nullable"?

p.16, "43 m" -> "43 ms"

p.16, "surpising"

p.17, "they extent"

PROS AND CONS

+ interesting and possibly novel idea

- no time/space complexity analysis

- implementation not clearly described

- case in favor of the idea not clearly made

- comparison with related work should be more thorough

REBUTTAL

No specific questions.