LPM and Concurrency

3 May 1996 00:03:19 -0400

          From comp.compilers

Related articles
LPM and Concurrency qjackson@direct.ca (1996-05-03)
| List of all articles for this month |

From: qjackson@direct.ca
Newsgroups: comp.compilers
Date: 3 May 1996 00:03:19 -0400
Organization: Parsepolis Software
Keywords: lex

[ This article is a modified repost of LPM_MISC-9604001. ]

You are encouraged to offer your views, tell of your experience, or
suggest any of the literature you feel may be of worth concerning the

When I first wrote Laleh's Pattern Matcher, it was implemented as a
static library intended to be run in a single-tasking environment, so
no intrinsic knowledge of concurrency on the part of the engine was

It immediately became apparent as I ported the engine to
cross-platform compatible C++, however, that LPM would have to
accommodate dynamically linked, multitasking environments such as
Microsoft Win dows. This new paradigm broke some original design

In particular, due to the fact that data that was both public and
global to a DLL is effectively global across the clients that access
the DLL, identifiers that were stored in global tables became a
problem. Consider the following LPM rule:

        [^ anchor
                [+'a-z'# any amount of a through z
        ['foobar'{NOW}^ cast into 'foobar' immediately
        <ws> any amount of whitespace
        ['foobar'! what we cast into foobar


Rule 1.0 casts a word into the class foobar immediately. If no class
"foobar" existed before, a new one is dynamically created. In a
single-tasking world, no problem exists. In a world where two o r
more clients are making use of one common LPM.DLL, however, it is
quite possible that another client subsequently might run the
following rule:

        ['quux'$ the literal 'quux"
        <ws> followed by any amount of whitespace
        ['foobar'! any member in the bag called "foobar"
        ['baz'$ the literal "baz"


with the local expectation that its foobar belongs to it alone. The
results are, at best, undefined. Rule 1.0 suffers particularly in a
preemptive environment, since, although it is intended to mat ch
patterns such as "a a", it may end up matching "a b" erroneously if
another application casts "b" into its own class "foobar" during its
tick. It is left to me, therefore, to design concurrency into LPM++ so
that the mechanism for concurrency is:

          A. Portable to other multitasking platforms,
          B. Graceful, so as to encourage programmers to
actually use it,
          C. Robust, so as to work should multitasking
paradigms change.

I will explain each of these in order.


If LPM were only meant to be compiled as a Windows DLL, several means
would be available to me to assure proper scoping, such that the
programmer could continue to use LPM as if he were programming i n a
single tasking environment.

For instance, the PowerBASIC DLL Compiler Reference Guide [PB96, page
91] suggests the following approach:

        The simplest way to do this would be to make applications call a
        one-time "check in" function, before using any of the DLL's
        services and "check out" prior to termination. When an
        application checks in, the DLL would register the application by
        adding it to the list of running applications. This would be a
        good time to allocate that application's memory and associate
        it with the application for future use. [Uniquely identifying
        each task] is easily accomplished by using the application's
        stack segment (SS) selector as its "handle", since each
        application or instance of such will have a unique stack segment
        selector. [...] Once the application's entry has been located,
        the DLL would then default to that applications data for any
        further data references.

The above approach, although GRACEFUL, in that it goes on behind the
back of the LPM programmer, is not portable, since it relies on the
Intel architecture's SS register.

Besides being non-portable, the above has its deficiencies where LPM
is concerned, since there are times when one may actually WISH to
share data across clients. Consider the case of a suite of prog rams
that all rely on LPM.DLL, but work as a team. One application may
scan incoming mail for keywords, another may then scan an ASCII
database against those keywords. If both applications in the s uite
could share a common 'keyword' class between their rules, the system
would work as a team, otherwise data files or DDE pipes would have to
be used to share this data.

To be portable, then, data should be guarded by standard C/C++
mechanisms, not by reliance on quirks of any machine's architecture.


I will define graceful as any method that does most of the work of
data hiding for the LPM programmer, relying on the programmer to
remember as little as possible, thereby freeing him to concentrate on
issues that are more pressing than identifier scope. I contend that
ungraceful solutions are often avoided and klujed around by what might
turn out to be untransportable solutions. (Well, at lea st that's how
I get around them when they hit me at 2 in the morning! ;-) LPM
programmers should be encouraged by a mechanism's gracefulness to
actually use that mechanism.


Robustness is portability's cousin. A concurrency scoping solution
that seems adequate today may be outdated by advances in hardware or
compiler semantics tomorrow. Even if the stack segment soluti on
discussed above were portable, it might not be compatible with future
advances to CPU register hardware.

Ideally, a robust mechanism will live as long as the system that
relies on it, or at least be designed in such a way as to allow easy
modification if the system that relies on it grows. (If anything can
go wrong, it already has.)

[The original message had a possible solution here, but the solution
has since been found to be inadequate.]


As it stands, LPM has no notion of concurrency scoping.

You are welcome -- invited! -- to comment on any of the above by
posting to this list. Should I adopt any of the ideas thrown around
here into the finalized LPM concurrency engine, those responsible will
be credited.


[PB96] -- _PowerBASIC DLL Compiler Reference Guide_, PowerBASIC Inc.,

Carmel, CA (1996).



        Parsepolis Software || Quinn Tyler Jackson
                "ParseCity" || qjackson@direct.ca

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.