Re: Parsec parser library...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Mon, 27 Jul 2026 17:04:15 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_2B13F8E1-A992-44B3-A025-DDFBF54EC142 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 So yes, I expected the parser to operate independently on each number = submitted to the Lisp reader. After splitting out the fields of each = database line, I call upon READ-FROM-STRING to perform the conversion = from text to Lisp. So yes, there is no good reason for a parser on one object to pollute = the actions of the parser working on a completely different piece of = text.=20 And it turns out to be trivial to produce a thread-safe version of the = Parseq parser. You don=E2=80=99t even have to know about threads.=20 Thanks to the breakthrough efforts of Martin and Co. LW has consistently = been the supreme leader when it comes to Lisp in SMP. It has always been = thus, since I first found Harlequin Lisp in 1990. > On Jul 27, 2026, at 16:35, Michael Lenaghan <[email protected]> = wrote: >=20 > So you chop the table into four completely independent pieces, expect = shared-nothing parsing on each piece, and get shared-something? >=20 > Are you creating the parser in the main thread or letting each thread = create its own? >=20 > Again, just curious. >=20 > On Jul 27, 2026 at 7:23:13=E2=80=AFPM, David McClain = <[email protected] <mailto:[email protected]>> = wrote: >> 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. >>=20 >> 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. >>=20 >> 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 >>=20 >> - DM >>=20 >>> On Jul 27, 2026, at 16:03, Michael Lenaghan (as michaell at dazzit = dot com) <[email protected] <mailto:[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 >>=20 --Apple-Mail=_2B13F8E1-A992-44B3-A025-DDFBF54EC142 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;">So yes, I expected the parser to operate = independently on each number submitted to the Lisp reader. After = splitting out the fields of each database line, I call upon = READ-FROM-STRING to perform the conversion from text to = Lisp.<div><br></div><div>So yes, there is no good reason for a parser on = one object to pollute the actions of the parser working on a completely = different piece of text. </div><div><br></div><div>And it turns out = to be trivial to produce a thread-safe version of the Parseq parser. You = don=E2=80=99t even have to know about threads. </div><div>Thanks to = the breakthrough efforts of Martin and Co. LW has consistently been the = supreme leader when it comes to Lisp in SMP. It has always been thus, = since I first found Harlequin Lisp in 1990.</div><div><br></div><div><br = id=3D"lineBreakAtBeginningOfMessage"><div><br><blockquote = type=3D"cite"><div>On Jul 27, 2026, at 16:35, Michael Lenaghan = <[email protected]> wrote:</div><br = class=3D"Apple-interchange-newline"><div><div><div dir=3D"ltr"> So you chop the table into four completely independent pieces, = expect shared-nothing parsing on each piece, and get = shared-something?</div><div dir=3D"ltr"><br></div><div dir=3D"ltr">Are = you creating the parser in the main thread or letting each thread create = its own?</div><div dir=3D"ltr"><br></div><div dir=3D"ltr">Again, just = curious.</div> <br> <div class=3D"gmail_quote"> <div dir=3D"ltr" class=3D"gmail_attr">On Jul 27, 2026 at = 7:23:13=E2=80=AFPM, David McClain <<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"> <div aria-label=3D"message body"><div><meta = http-equiv=3D"content-type" content=3D"text/html; = charset=3Dutf-8"></div><div style=3D"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><d= iv>- 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) <<a = href=3D"mailto:[email protected]">[email protected]</a>> = 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></div></div> </blockquote> </div></div> </div></blockquote></div><br></div></body></html>= --Apple-Mail=_2B13F8E1-A992-44B3-A025-DDFBF54EC142-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html