Re: Parsec parser library...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Mon, 27 Jul 2026 16:23:13 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_7BEB13FC-AE75-4712-AC28-DB496B8F57EB Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 I use a lot of extended number formats, like 12:23:32.14, and = 2027/07/27T01:00:00U-7, 1.3+2.7j, and many others. And it takes a bit of = work to ferret out what is and is not a valid number. So I wrote the PEG = Parser in Parseq, and have it do my work. But the other day, I was importing astronomical tables from the = databases at Strasbourg, and lo and behold, every time I finished = parsing about 2400 numeric entries, the computer would blurt out that it = =E2=80=9CDetected Left-Recursion=E2=80=9D in my Parseq parser. It drove me nuts trying to find out why this was happening. And then I = realized - I have enormous tables to parse. Essentially large CSV format = tables. So I inhale about 10,000 lines fom Strasbourg, and then I chop = the table into 4 sections and fire off parallel tasks, charged with = splitting out the individual numeric entries, and parsing them down to = numbers. A Parallel Concurrent Parsing job=E2=80=A6 - DM > On Jul 27, 2026, at 16:03, Michael Lenaghan (as michaell at dazzit dot = com) <[email protected]> wrote: >=20 > Well I=E2=80=99ll ask the obvious question, because I=E2=80=99m = curious. Why do you need a multi-threaded parser in the first place? >=20 > On Jul 27, 2026 at 5:52:00=E2=80=AFPM, David McClain (as dbm at = refined-audiometrics dot com) <[email protected] = <mailto:[email protected]>> wrote: >> You know=E2=80=A6 >>=20 >> I think that Martin has a point here.=20 >>=20 >> The fact that the LOL vars are being used as a stack, and the pushed = parse tree is popped off at terminal node exit, means that we could just = as well have used a special binding, one such binding for each named = non-terminal DEFRULE. Just CONS a new element to the special binding for = every push. And you won=E2=80=99t need to use an UNWIND-PROTECT to pop = it back off. >>=20 >> All of the LOL code is generated as part of a big (huge!!) macro. = Instead of a LOL binding surrounding the generated lambda closure, we = could avoid TLS altogether and just generate a DEFVAR inside a PROGN = macro alongside the lambda function. >>=20 >> I hate to suggest generating and using dozens of special vars, but it = has to be more streamlined than my coded hash-table access methods. >>=20 >> - DM >>=20 >>=20 >>=20 >>> On Jul 27, 2026, at 12:01, Martin Simmons <[email protected] = <mailto:[email protected]>> wrote: >>>=20 >>> Is having invocation history a bug or a feature? >>>=20 >>> I would expect it to make the closure every time you invoke the top = level >>> parser in most cases, but it sounds like it stores it forever. >>>=20 >>> -- >>> Martin Simmons >>> LispWorks Ltd >>> http://www.lispworks.com/ >>>=20 >>>=20 >>>=20 >>> >>>>> On Sun, 26 Jul 2026 22:45:52 -0700, David McClain (as dbm at = refined-audiometrics dot com) said: >>> > >>> > I tracked down the programming style that led to thread-unsafe = conditions. It is a very common programming idiom in Lisp and it begs = some questions=E2=80=A6 >>> > >>> > The Parseq library compiles PEG grammar rules into Let-Over-Lambda = closures, where the LET var is used to track invocation history and = detect the use of Left-Recursion. Parseq cannot do left recursion. >>> > >>> > And there are good reasons for wanting Let-Over-Lambda: >>> > >>> > (LET ((STATE =E2=80=A6)) >>> > (LAMBDA (args=E2=80=A6) >>> > =E2=80=A6.)) >>> > >>> > The LET bindings hold onto persistent state across invocations of = the lambda closure. This is often a desirable thing to do. But as = written, it only works in the face of single-threaded code. Those LET = bindings are globally accessible and, if mutated, will cause race = conditions, or worse, between multiple threads attempting to alter the = persistent state. >>> > >>> > So we need some kind of thread-local version of Let-Over-Lambda. = In rare cases you might want the state to persist over all possible = invocations. And in that case, go ahead and use LET-OVER-LAMBDA along = with locking to serialize mutation among threads. >>> > >>> > But just as often, you really don=E2=80=99t mean to have globally = accessible state shared between threads, but rather as a history = tracking device within one thread=E2=80=99s execution. And for that, = LET-OVER-LAMBDA is a disaster in multi-threaded code. >>> > >>> > In the case of the Parseq library, the solution is to keep state = for each named rule in a dynamically bound hash-table, indexed by the = name of the state. Each thread, on entry just rebinds a special var with = a new hash-table for its own use. But this does not have the simple = appearance of a LET-OVER-LAMBDA. >>> > >>> > We need some kind of macrology to provide thread-safe LOL=E2=80=A6 >>> > >>> > - DM >>> > >>> > >>> >> On Jul 25, 2026, at 14:51, David McClain = <[email protected] <mailto:[email protected]>> = wrote: >>> >> >>> >> It looks like the Parsec library is not thread safe. >>> >> >>> >> I just ran into the most peculiar problem using it, wherein a = formerly reliable number parsing system built with Parsec, claims to = have detected Left-Recursion after about 2500 numbers were thrown at it. = And this happens in each of several parallel threads all trying to parse = numbers. >>> >> >>> >> I can reliably parse literally millions of number strings with = it, when executed from a single thread (the Editor, or the REPL). >>> >> >>> >> But I see erorrs happen when there are at least 4 parallel = threads all doing the same kind of work - taking tabular entries from an = incoming database, splitting each line at the delimiters, and then = calling on READ-FROM-STRING to read the numbers contained in those = strings. >>> >> >>> >> The numbers are all just plain decimal numbers with fractions, = like 310.1023344. Nothing unusual about them. >>> >> >>> >> If I surround the calls to READ-FROM-STRING with a plain vanilla = READTABLE, then no errors arise because it no longer uses my Parseq = parser. >>> >> >>> >> If I have just one thread using the Parseq parser, no problem. >>> >> >>> >> So I am led to conclude that something in the Parseq library is = not thread-safe. >>> >> >>> >> >>> > >>> > >>=20 >>=20 >> _______________________________________________ >> Lisp Hug - the mailing list for LispWorks users >> [email protected] <mailto:[email protected]> >> http://www.lispworks.com/support/lisp-hug.html --Apple-Mail=_7BEB13FC-AE75-4712-AC28-DB496B8F57EB Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8 <html aria-label=3D"message body"><head><meta http-equiv=3D"content-type" = content=3D"text/html; charset=3Dutf-8"></head><body = style=3D"overflow-wrap: break-word; -webkit-nbsp-mode: space; = line-break: after-white-space;">I use a lot of extended number formats, = like 12:23:32.14, and 2027/07/27T01:00:00U-7, 1.3+2.7j, and many others. = And it takes a bit of work to ferret out what is and is not a valid = number. So I wrote the PEG Parser in Parseq, and have it do my = work.<div><br></div><div>But the other day, I was importing astronomical = tables from the databases at Strasbourg, and lo and behold, every time I = finished parsing about 2400 numeric entries, the computer would blurt = out that it =E2=80=9CDetected Left-Recursion=E2=80=9D in my Parseq = parser.</div><div><br></div><div>It drove me nuts trying to find out why = this was happening. And then I realized - I have enormous tables to = parse. Essentially large CSV format tables. So I inhale about 10,000 = lines fom Strasbourg, and then I chop the table into 4 sections and fire = off parallel tasks, charged with splitting out the individual numeric = entries, and parsing them down to numbers. A Parallel Concurrent Parsing = job=E2=80=A6</div><div><br></div><div>- DM<br = id=3D"lineBreakAtBeginningOfMessage"><div><br><blockquote = type=3D"cite"><div>On Jul 27, 2026, at 16:03, Michael Lenaghan (as = michaell at dazzit dot com) <[email protected]> = wrote:</div><br class=3D"Apple-interchange-newline"><div><div><div = dir=3D"ltr"> Well I=E2=80=99ll ask the obvious question, because I=E2=80=99m = curious. Why do you need a multi-threaded parser in the first = place?</div> <br> <div class=3D"gmail_quote"> <div dir=3D"ltr" class=3D"gmail_attr">On Jul 27, 2026 at = 5:52:00=E2=80=AFPM, David McClain (as dbm at refined-audiometrics dot = com) <<a = href=3D"mailto:[email protected]">[email protected]</a>> = wrote:<br></div> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px = 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" = type=3D"cite"> =20 <div> <div> You know=E2=80=A6<br><br>I think that Martin has a point here. = <br><br>The fact that the LOL vars are being used as a stack, and the = pushed parse tree is popped off at terminal node exit, means that we = could just as well have used a special binding, one such binding for = each named non-terminal DEFRULE. Just CONS a new element to the special = binding for every push. And you won=E2=80=99t need to use an = UNWIND-PROTECT to pop it back off.<br><br>All of the LOL code is = generated as part of a big (huge!!) macro. Instead of a LOL binding = surrounding the generated lambda closure, we could avoid TLS altogether = and just generate a DEFVAR inside a PROGN macro alongside the lambda = function.<br><br>I hate to suggest generating and using dozens of = special vars, but it has to be more streamlined than my coded hash-table = access methods.<br><br>- DM<br><br><br><br><blockquote type=3D"cite"> On = Jul 27, 2026, at 12:01, Martin Simmons <<a = href=3D"mailto:[email protected]">[email protected]</a>> = wrote:<br></blockquote><blockquote type=3D"cite"> = <br></blockquote><blockquote type=3D"cite"> Is having invocation history = a bug or a feature?<br></blockquote><blockquote type=3D"cite"> = <br></blockquote><blockquote type=3D"cite"> I would expect it to make = the closure every time you invoke the top = level<br></blockquote><blockquote type=3D"cite"> parser in most cases, = but it sounds like it stores it forever.<br></blockquote><blockquote = type=3D"cite"> <br></blockquote><blockquote type=3D"cite"> -- = <br></blockquote><blockquote type=3D"cite"> Martin = Simmons<br></blockquote><blockquote type=3D"cite"> LispWorks = Ltd<br></blockquote><blockquote type=3D"cite"> <a = href=3D"http://www.lispworks.com/">http://www.lispworks.com/</a><br></bloc= kquote><blockquote type=3D"cite"> <br></blockquote><blockquote = type=3D"cite"> <br></blockquote><blockquote type=3D"cite"> = <br></blockquote><blockquote type=3D"cite">>>>>> On Sun, = 26 Jul 2026 22:45:52 -0700, David McClain (as dbm at = refined-audiometrics dot com) said:<br></blockquote><blockquote = type=3D"cite">> <br></blockquote><blockquote type=3D"cite">> I = tracked down the programming style that led to thread-unsafe conditions. = It is a very common programming idiom in Lisp and it begs some = questions=E2=80=A6<br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> The Parseq library = compiles PEG grammar rules into Let-Over-Lambda closures, where the LET = var is used to track invocation history and detect the use of = Left-Recursion. Parseq cannot do left = recursion.<br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> And there are good = reasons for wanting Let-Over-Lambda:<br></blockquote><blockquote = type=3D"cite">> <br></blockquote><blockquote type=3D"cite">> (LET = ((STATE =E2=80=A6))<br></blockquote><blockquote type=3D"cite">> = (LAMBDA (args=E2=80=A6)<br></blockquote><blockquot= e type=3D"cite">> <span class=3D"Apple-tab-span" = style=3D"white-space:pre"> </span>=E2=80=A6.))<br></blockquote><blockqu= ote type=3D"cite">> <br></blockquote><blockquote type=3D"cite">> = The LET bindings hold onto persistent state across invocations of the = lambda closure. This is often a desirable thing to do. But as written, = it only works in the face of single-threaded code. Those LET bindings = are globally accessible and, if mutated, will cause race conditions, or = worse, between multiple threads attempting to alter the persistent = state.<br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> So we need some kind of = thread-local version of Let-Over-Lambda. In rare cases you might want = the state to persist over all possible invocations. And in that case, go = ahead and use LET-OVER-LAMBDA along with locking to serialize mutation = among threads.<br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> But just as often, you = really don=E2=80=99t mean to have globally accessible state shared = between threads, but rather as a history tracking device within one = thread=E2=80=99s execution. And for that, LET-OVER-LAMBDA is a disaster = in multi-threaded code.<br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> In the case of the = Parseq library, the solution is to keep state for each named rule in a = dynamically bound hash-table, indexed by the name of the state. Each = thread, on entry just rebinds a special var with a new hash-table for = its own use. But this does not have the simple appearance of a = LET-OVER-LAMBDA.<br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> We need some kind of = macrology to provide thread-safe LOL=E2=80=A6<br></blockquote><blockquote = type=3D"cite">> <br></blockquote><blockquote type=3D"cite">> - DM = <br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">>> On Jul 25, 2026, at = 14:51, David McClain <<a = href=3D"mailto:[email protected]">[email protected]<= /a>> wrote:<br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">>> It looks like the = Parsec library is not thread safe. <br></blockquote><blockquote = type=3D"cite">>> <br></blockquote><blockquote type=3D"cite">>>= I just ran into the most peculiar problem using it, wherein a formerly = reliable number parsing system built with Parsec, claims to have = detected Left-Recursion after about 2500 numbers were thrown at it. And = this happens in each of several parallel threads all trying to parse = numbers.<br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">>> I can reliably parse = literally millions of number strings with it, when executed from a = single thread (the Editor, or the REPL). <br></blockquote><blockquote = type=3D"cite">>> <br></blockquote><blockquote type=3D"cite">>>= But I see erorrs happen when there are at least 4 parallel threads all = doing the same kind of work - taking tabular entries from an incoming = database, splitting each line at the delimiters, and then calling on = READ-FROM-STRING to read the numbers contained in those = strings.<br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">>> The numbers are all = just plain decimal numbers with fractions, like 310.1023344. Nothing = unusual about them.<br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">>> If I surround the = calls to READ-FROM-STRING with a plain vanilla READTABLE, then no errors = arise because it no longer uses my Parseq = parser.<br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">>> If I have just one = thread using the Parseq parser, no problem. <br></blockquote><blockquote = type=3D"cite">>> <br></blockquote><blockquote type=3D"cite">>>= So I am led to conclude that something in the Parseq library is not = thread-safe.<br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">>> = <br></blockquote><blockquote type=3D"cite">> = <br></blockquote><blockquote type=3D"cite">> = <br></blockquote><br><br>_______________________________________________<b= r>Lisp Hug - the mailing list for LispWorks users<br><a = href=3D"mailto:[email protected]">[email protected]</a><br><a = href=3D"http://www.lispworks.com/support/lisp-hug.html">http://www.lispwor= ks.com/support/lisp-hug.html</a><br> </div> </div> </blockquote> </div></div> </div></blockquote></div><br></div></body></html>= --Apple-Mail=_7BEB13FC-AE75-4712-AC28-DB496B8F57EB-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html