Re: Parsec parser library...

Well, not my own code… But from what I can understand of it, he uses a Let-Over-Lambda to hold the last invocation of a parser non-terminal, and then checks on every next entry to see whether the current parse tree matches what he pushed on the stack the last time. 

But that “last-time” entry is pushed on, at the first entry, and popped off after completing the parse for that non-terminal. Hence, the last-time LOL value should always have a resting value of NIL, and never grow more than 1 element deep. And from what I see when I look at the new Thread-local hash-table, all the resting entries are NIL.

So this is being used to detect whether or not a Left-Recursion condition is happening. The error condition is checked before pushing the current parse tree onto the LOL var.

The closures themselves are pre-compiled lambda closures inside that LOL structure, and stored away in another hash-table called RULES-TABLE. There appears to be no need to reconstruct them every time you reenter the parser.

The Parseq system operates in two phases. Phase I constructs all the precompiled non-terminal rules closures from DEFRULE definitions. Then Phase II is actual use of these rules by calling on PARSEQ itself. That is the one that needs TLS protection.

- 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 some questions…
>> 
>> 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 …))
>>    (LAMBDA  (args…)
>> 	….))
>> 
>> 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’t mean to have globally accessible state shared between threads, but rather as a history tracking device within one thread’s 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…
>> 
>> - 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 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.
>>> 
>>> 
>> 
>> 


_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html