From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
X-Received: by 10.107.18.138 with SMTP id 10mr450880ios.70.1523311753679;
        Mon, 09 Apr 2018 15:09:13 -0700 (PDT)
X-Received: by 2002:a9d:4c99:: with SMTP id
 m25-v6mr1104294otf.6.1523311753379;
 Mon, 09 Apr 2018 15:09:13 -0700 (PDT)
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!maths.tcd.ie!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!k65-v6no2235839ita.0!news-out.google.com!15-v6ni1234itg.0!nntp.google.com!e130-v6no369734itb.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.ada
Date: Mon, 9 Apr 2018 15:09:13 -0700 (PDT)
In-Reply-To: <fj23jkFfushU1@mid.individual.net>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com;
 posting-host=47.185.233.194;
 posting-account=zwxLlwoAAAChLBU7oraRzNDnqQYkYbpo
NNTP-Posting-Host: 47.185.233.194
References: <p9s890$mmt$1@franka.jacob-sparre.dk>
 <1b44444f-c1b3-414e-84fb-8798961487c3@googlegroups.com>
 <62ee0aac-49da-4925-b9aa-a16695b3fc45@googlegroups.com>
 <pa0vga$rbe$1@franka.jacob-sparre.dk>
 <9879872e-c18a-4667-afe5-41ce0f54559f@googlegroups.com>
 <pa3jmj$9n3$1@franka.jacob-sparre.dk>
 <pa4ip3$1ton$1@gioia.aioe.org> <pa67ci$t34$1@franka.jacob-sparre.dk>
 <pa77nc$1pu1$1@gioia.aioe.org> <pa9a6q$ii$1@franka.jacob-sparre.dk>
 <paa5gk$knn$1@gioia.aioe.org>
 <80db2d05-744f-4201-ba1b-4436f8040491@googlegroups.com>
 <paaptu$1pce$1@gioia.aioe.org>
 <59f9ab6d-d6ba-45ff-a6f0-c5699983d9e8@googlegroups.com>
 <pachc4$mkr$1@gioia.aioe.org>
 <1a390e22-f49f-4028-8e58-ca4d0f51e4b6@googlegroups.com>
 <fj1ho6Fbv06U1@mid.individual.net>
 <b1f76a33-a41b-46bf-a334-f8c8fbbbbb24@googlegroups.com>
 <fj23jkFfushU1@mid.individual.net>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <195739aa-2f32-4cba-80ac-e60591e94712@googlegroups.com>
Subject: Re: Interesting article on ARG work
From: "Dan'l Miller" <optikos@verizon.net>
Injection-Date: Mon, 09 Apr 2018 22:09:13 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Xref: reader02.eternal-september.org comp.lang.ada:51426
Date: 2018-04-09T15:09:13-07:00
List-Id: <comp.lang.ada>

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=
=20
> number of possible complete ASTs (which is what the later stages of an=20
> ordinary compiler would have to process) is exponential in the number of=
=20
> choice points (that is, "@" instances)

Trivially exponential:  at most 2=C2=B9 =3D 2 alternative AST subtrees as s=
ome points, because there is only one choice point:  an @-code-is-present o=
n the compiler's command-line versus an @-code-is-elided on the compiler's =
command line.  Each @-prefixed line is not isomorphic to yet another differ=
ently-named macro in the C preprocessor (or M4, p4, etc preprocessors).  Fo=
r p choicepoints on the compiler command-line, yes you are trivially correc=
t:  =E2=80=9Cexponential=E2=80=9D 2=E1=B5=96 but where p is not only consta=
nt, but merely p=3D1, hence GLR's O(pn) asymptotic rate of growth is O(1n) =
=3D O(n) and likewise for the at-most twice-as-big AST.  Not @ instances (a=
s counted by lines of code) but @ degrees of freedom on the compiler comman=
d-line.  You are not counting the correct things.