Re: Interesting article on ARG work

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 18-04-10 01:09 , Dan'l Miller wrote:
> On Monday, April 9, 2018 at 4:17:42 PM UTC-5, Niklas Holsti wrote:
>> If there are 2 alternative AST subtrees at each choice point, the
>> total number of possible complete ASTs (which is what the later
>> stages of an ordinary compiler would have to process) is
>> exponential in the number of choice points (that is, "@"
>> instances)
>
> Trivially exponential:  at most 2¹ = 2 alternative AST subtrees as
> some points, because there is only one choice point:  an
> @-code-is-present on the compiler's command-line versus an
> @-code-is-elided on the compiler's command line.

I call a "choice point" a point in the input sentence where the parser 
has to fork into alternatives. For a GLR parser, this means every 
_occurrence_ of an "@" in the input sentence.

You are ignoring my explicitly stated assumption (which follows if one 
is using _just_ a GLR parser) that the choices of alternative at the 
various choice points are uncorrelated. This makes the number of 
combinations of choices, which is the number of alternative _entire_ 
ASTs (in the commonly accepted meaning of AST as _one_ parse of the 
input sentence) exponential in the number of choice points.

The paper to which you referred avoids that problem by associating 
choice points with conditions depending on preprocessor variables, which 
is a natural thing to do, but which also means passing beyond the 
abilities of _just_ GLR parsing.

> Each @-prefixed line is not isomorphic to yet another
> differently-named macro in the C preprocessor (or M4, p4, etc
> preprocessors).

In plain GLR parsing it is isomorphic, because a GLR parser does not 
create any correlations between the non-deterministic choices at 
different points in the sentence. That would be a context-dependent grammar.

> For p choicepoints on
> the compiler command-line, yes you are trivially correct:
> “exponential” 2ᵖ but where p is not only constant, but merely p=1,
> hence GLR's O(pn) asymptotic rate of growth is O(1n) = O(n) and
> likewise for the at-most twice-as-big AST.

That is true for the "Fork-Merge LR" (FMLR) parsing in the paper you 
referenced, but that is not GLR.

> Not @ instances (as counted by lines of code) but @ degrees of
> freedom on the compiler command-line.  You are not counting the
> correct things.

We are certainly counting different things.

You said that GLR parsing could be used to parse both "@ enabled" and "@ 
disabled" sentences at the same time. I maintain that _just_ a GLR 
parser is not suitable, because the uncorrelated choice of alternative 
parses at each choice point (each "@") does not match the meaning of the 
"@" symbol (enabled everywhere, or disabled everywhere).

The FMLR method, with alternatives correlated by logical conditions, 
works, at least if one fully believes the claims in the paper to which 
you referred (I am perhaps not quite convinced that the paper's 
"ifdef-hoisting" will work and remain relatively local in all cases).

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .