Re: Parsec parser library...
"Michael Lenaghan (as michaell at dazzit dot com)" <[email protected]> Mon, 27 Jul 2026 16:35:58 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <CAHV0GgGxEQpFSk6yiF5LkTWA7T-GvZu-3wNv2e2pV78vT4CrEQ@mail.gmail.com> |
--000000000000406d5a0657a02f8a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable So you chop the table into four completely independent pieces, expect shared-nothing parsing on each piece, and get shared-something? Are you creating the parser in the main thread or letting each thread create its own? Again, just curious. On Jul 27, 2026 at 7:23:13=E2=80=AFPM, David McClain <dbm@refined-audiometr= ics.com> 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. > > But the other day, I was importing astronomical tables from the databases > at Strasbourg, and lo and behold, every time I finished parsing about 240= 0 > 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 th= e > 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: > > 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? > > On Jul 27, 2026 at 5:52:00=E2=80=AFPM, David McClain (as dbm at > refined-audiometrics dot com) <[email protected]> wrote: > >> You know=E2=80=A6 >> >> I think that Martin has a point here. >> >> 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 i= t back off. >> >> All of the LOL code is generated as part of a big (huge!!) macro. Instea= d >> of a LOL binding surrounding the generated lambda closure, we could avoi= d >> TLS altogether and just generate a DEFVAR inside a PROGN macro alongside >> the lambda function. >> >> I hate to suggest generating and using dozens of special vars, but it ha= s >> to be more streamlined than my coded hash-table access methods. >> >> - DM >> >> >> >> On Jul 27, 2026, at 12:01, Martin Simmons <[email protected]> wrote: >> >> >> Is having invocation history a bug or a feature? >> >> >> I would expect it to make the closure every time you invoke the top leve= l >> >> parser in most cases, but it sounds like it stores it forever. >> >> >> -- >> >> Martin Simmons >> >> LispWorks Ltd >> >> http://www.lispworks.com/ >> >> >> >> >> >>>>> 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 so= me >> 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 dete= ct >> 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, i= t >> only works in the face of single-threaded code. Those LET bindings are >> globally accessible and, if mutated, will cause race conditions, or wors= e, >> 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 wi= th >> locking to serialize mutation among threads. >> >> > >> >> > But just as often, you really don=E2=80=99t mean to have globally acce= ssible >> 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 o= f >> 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]= m> >> wrote: >> >> >> >> >> >> It looks like the Parsec library is not thread safe. >> >> >> >> >> >> I just ran into the most peculiar problem using it, wherein a formerl= y >> reliable number parsing system built with Parsec, claims to have detecte= d >> Left-Recursion after about 2500 numbers were thrown at it. And this happ= ens >> 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 al= l >> 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 pars= er. >> >> >> >> >> >> 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. >> >> >> >> >> >> >> >> > >> >> > >> >> >> >> _______________________________________________ >> Lisp Hug - the mailing list for LispWorks users >> [email protected] >> http://www.lispworks.com/support/lisp-hug.html >> > > --000000000000406d5a0657a02f8a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <html><body><div dir=3D"ltr"> So you chop the table into four completely independent pieces, expect s= hared-nothing parsing on each piece, and get shared-something?</div><div di= r=3D"ltr"><br></div><div dir=3D"ltr">Are you creating the parser in the mai= n 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]">db= [email protected]</a>> wrote:<br></div> <blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bor= der-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-t= ype" 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 PE= G Parser in Parseq, and have it do my work.<div><br></div><div>But the othe= r day, I was importing astronomical tables from the databases at Strasbourg= , and lo and behold, every time I finished parsing about 2400 numeric entri= es, 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 tr= ying to find out why this was happening. And then I realized - I have enorm= ous 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 j= ob=E2=80=A6</div><div><br></div><div>- DM<br id=3D"lineBreakAtBeginningOfMe= ssage"><div><br><blockquote type=3D"cite"><div>On Jul 27, 2026, at 16:03, M= ichael Lenaghan (as michaell at dazzit dot com) <<a href=3D"mailto:lisp-= [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;bor= der-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 D= EFRULE. 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 o= f a LOL binding surrounding the generated lambda closure, we could avoid TL= S 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 sp= ecial vars, but it has to be more streamlined than my coded hash-table acce= ss 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"c= ite"> <br></blockquote><blockquote type=3D"cite"> Is having invocation hist= ory a bug or a feature?<br></blockquote><blockquote type=3D"cite"> <br></bl= ockquote><blockquote type=3D"cite"> I would expect it to make the closure e= very 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></bloc= kquote><blockquote type=3D"cite"> <br></blockquote><blockquote type=3D"cite= "> -- <br></blockquote><blockquote type=3D"cite"> Martin Simmons<br></block= quote><blockquote type=3D"cite"> LispWorks Ltd<br></blockquote><blockquote = type=3D"cite"> <a href=3D"http://www.lispworks.com/">http://www.lispworks.c= om/</a><br></blockquote><blockquote type=3D"cite"> <br></blockquote><blockq= uote type=3D"cite"> <br></blockquote><blockquote type=3D"cite"> <br></block= quote><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 be= gs 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 ca= nnot 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 =C2=A0((STATE =E2=80=A6))= <br></blockquote><blockquote type=3D"cite">> =C2=A0=C2=A0=C2=A0(LAMBDA = =C2=A0(args=E2=80=A6)<br></blockquote><blockquote type=3D"cite">> <span = class=3D"Apple-tab-span" style=3D"white-space:pre"> </span>=E2=80=A6.))<= br></blockquote><blockquote type=3D"cite">> <br></blockquote><blockquote= type=3D"cite">> The LET bindings hold onto persistent state across invo= cations of the lambda closure. This is often a desirable thing to do. But a= s written, it only works in the face of single-threaded code. Those LET bin= dings 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><blockquo= te type=3D"cite">> So we need some kind of thread-local version of Let-O= ver-Lambda. In rare cases you might want the state to persist over all poss= ible invocations. And in that case, go ahead and use LET-OVER-LAMBDA along = with locking to serialize mutation among threads.<br></blockquote><blockquo= te type=3D"cite">> <br></blockquote><blockquote type=3D"cite">> But j= ust as often, you really don=E2=80=99t mean to have globally accessible sta= te shared between threads, but rather as a history tracking device within o= ne 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 libra= ry, the solution is to keep state for each named rule in a dynamically boun= d 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><block= quote type=3D"cite">> <br></blockquote><blockquote type=3D"cite">> We= need some kind of macrology to provide thread-safe LOL=E2=80=A6<br></block= quote><blockquote type=3D"cite">> <br></blockquote><blockquote type=3D"c= ite">> - DM <br></blockquote><blockquote type=3D"cite">> <br></blockq= uote><blockquote type=3D"cite">> <br></blockquote><blockquote type=3D"ci= te">>> 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><blockq= uote 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 proble= m using it, wherein a formerly reliable number parsing system built with Pa= rsec, claims to have detected Left-Recursion after about 2500 numbers were = thrown at it. And this happens in each of several parallel threads all tryi= ng to parse numbers.<br></blockquote><blockquote type=3D"cite">>> <br= ></blockquote><blockquote type=3D"cite">>> I can reliably parse liter= ally 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 h= appen when there are at least 4 parallel threads all doing the same kind of= work - taking tabular entries from an incoming database, splitting each li= ne at the delimiters, and then calling on READ-FROM-STRING to read the numb= ers contained in those strings.<br></blockquote><blockquote type=3D"cite">&= gt;> <br></blockquote><blockquote type=3D"cite">>> The numbers are= all just plain decimal numbers with fractions, like 310.1023344. Nothing u= nusual about them.<br></blockquote><blockquote type=3D"cite">>> <br><= /blockquote><blockquote type=3D"cite">>> If I surround the calls to R= EAD-FROM-STRING with a plain vanilla READTABLE, then no errors arise becaus= e it no longer uses my Parseq parser.<br></blockquote><blockquote type=3D"c= ite">>> <br></blockquote><blockquote type=3D"cite">>> If I have= just one thread using the Parseq parser, no problem. <br></blockquote><blo= ckquote type=3D"cite">>> <br></blockquote><blockquote type=3D"cite">&= gt;> So I am led to conclude that something in the Parseq library is not= thread-safe.<br></blockquote><blockquote type=3D"cite">>> <br></bloc= kquote><blockquote type=3D"cite">>> <br></blockquote><blockquote type= =3D"cite">> <br></blockquote><blockquote type=3D"cite">> <br></blockq= uote><br><br>_______________________________________________<br>Lisp Hug - = the mailing list for LispWorks users<br><a href=3D"mailto:lisp-hug@lispwork= s.com">[email protected]</a><br><a href=3D"http://www.lispworks.com/su= pport/lisp-hug.html">http://www.lispworks.com/support/lisp-hug.html</a><br> </div> </div> </blockquote> </div></div> </div></blockquote></div><br></div></div></div> </blockquote> </div></body></html> --000000000000406d5a0657a02f8a-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html