Re: Parsec parser library...
"Michael Lenaghan (as michaell at dazzit dot com)" <[email protected]> Mon, 27 Jul 2026 16:03:21 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <CAHV0GgG-=E0ZcTqR+o4bCPZ+YFMCLELOEPkz2auVyrcNFA6uBg@mail.gmail.com> |
--000000000000a07e2b06579fba83 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Well I=E2=80=99ll ask the obvious question, because I=E2=80=99m curious. W= hy 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 pars= e > tree is popped off at terminal node exit, means that we could just as wel= l > 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. A= nd > you won=E2=80=99t need to use an UNWIND-PROTECT to pop it back off. > > 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. > > 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. > > - 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 level > > 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 som= e > 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 detec= t > 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 rar= e > 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 acces= sible > 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]= > > 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 happe= ns > in each of several parallel threads all trying to parse numbers. > > >> > > >> I can reliably parse literally millions of number strings with it, whe= n > 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 parse= r. > > >> > > >> 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 > --000000000000a07e2b06579fba83 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <html><body><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></body></html> --000000000000a07e2b06579fba83-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html