Re: Parsec parser library...

I probably misspoke. 

Last-time stack could grow indefinitely - more than 1 deep. But every valid encounter of the non-terminal cleans up after itself. So the stack grows by 1 for each use of a non-terminal, and shrinks back toward zero depth on exit.

He uses an UNWIND-PROTECT to ensure that the elements get popped off the last-time stacks.



> On Jul 27, 2026, at 13:33, David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote:
> 
> 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


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