Re: Parsec parser library...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Sun, 26 Jul 2026 22:45:52 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_BEBDDCA9-4F5A-4A19-8698-14E8878813EC
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
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=20
> On Jul 25, 2026, at 14:51, David McClain =
<[email protected]> wrote:
>=20
> It looks like the Parsec library is not thread safe.=20
>=20
> 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.
>=20
> I can reliably parse literally millions of number strings with it, =
when executed from a single thread (the Editor, or the REPL).=20
>=20
> 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.
>=20
> The numbers are all just plain decimal numbers with fractions, like =
310.1023344. Nothing unusual about them.
>=20
> 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.
>=20
> If I have just one thread using the Parseq parser, no problem.=20
>=20
> So I am led to conclude that something in the Parseq library is not =
thread-safe.
>=20
>=20
--Apple-Mail=_BEBDDCA9-4F5A-4A19-8698-14E8878813EC
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 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<div><br></div><div>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.</div><div><br></div><div>And there are good reasons for =
wanting Let-Over-Lambda:</div><div><br></div><div><font =
face=3D"Monaco">(LET ((STATE =E2=80=A6))</font></div><div><font =
face=3D"Monaco"> (LAMBDA =
(args=E2=80=A6)</font></div><div><font face=3D"Monaco"><span =
class=3D"Apple-tab-span" style=3D"white-space:pre"> =
</span>=E2=80=A6.))</font></div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>But just as often, you really don=E2=80=99=
t 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.</div><div><br></div><div>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.</div><div><br></div><div>We need some kind of macrology =
to provide thread-safe LOL=E2=80=A6</div><div><br></div><div>- =
DM </div><div><br></div><div><div><br><blockquote =
type=3D"cite"><div>On Jul 25, 2026, at 14:51, David McClain =
<[email protected]> wrote:</div><br =
class=3D"Apple-interchange-newline"><div><div>It looks like the Parsec =
library is not thread safe. <br><br>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><br>I can reliably =
parse literally millions of number strings with it, when executed from a =
single thread (the Editor, or the REPL). <br><br>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><br>The numbers are all just =
plain decimal numbers with fractions, like 310.1023344. Nothing unusual =
about them.<br><br>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><br>If I have just one thread using the Parseq =
parser, no problem. <br><br>So I am led to conclude that something in =
the Parseq library is not =
thread-safe.<br><br><br></div></div></blockquote></div><br></div></body></=
html>=
--Apple-Mail=_BEBDDCA9-4F5A-4A19-8698-14E8878813EC--
_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html