Sub-Genius

 view release on metacpan or  search on metacpan

lib/Sub/Genius/Extended.pod  view on Meta::CPAN

This allows a concurrency plan to be I<serialized> or I<linearized> properly for
execution in a uniprocess (or single CPU) environment.

It does this by marrying L<FLAT>'s ability to generate a valid string based on a
Parallel Regular Expression with the concept of that string I<correctly>
describing a I<sequentially consistent> ordering of Perl subroutine calls. This
approach allows one to declare a I<concurrent execution plan> that contains both
I<total> ordering and I<partial> ordering constraints among subroutine calls.

Totally ordered means: I<subroutine B must follow subroutine A>.

   my $plan = q{ A   B };

Partially ordered means: I<subroutine A may lead or lag subroutine B; both must
be executed>.

   my $plan = q{ A & B };

Using this concept, C<Sub::Genius> can generate a valid sequential ordering of
subroutine calls from a declarative plan that expresses concurrency.

=head2 perl's Uniprocess Memory Model and Its Execution Environment

While the language Perl is not necessarily constrained by a uniprocess execution
model, the runtime provided by C<perl> is. This has necessarily restricted the
expressive semantics that could be extended to DWIM in a concurrent execution
model.

The problem is that C<perl> has organically grown over the years to run as a
single process. It is not immediately obvious to many (even seasoned Perl
programmers) why after all of these years C<perl> does not have “real” threads or
admit “real” concurrency semantics.

Accepting the truth of the uniprocess model makes it clear, and brings with it a
lot of freedom. This module is meant to facilitate shared-memory, multi-process
reasoning within Perl’s fixed uniprocess reality.

The uniprocess model eases reasoning, particularly for shared-memory programming
semantics and consistency thereof. See [3] for more background on this.

=head2 Atomics and Barriers

When speaking of concurrent semantics in Perl, the topic of atomic primitives
often comes up, because in a truly multi-process execution environment they are
important to coordinate competitive access to resources such as files and shared
memory.

Since this execution model necessarily serializes parallel semantics in a
sequentially consistent way, there is no need for these mechanisms. Singular
lines of execution need no coordination because there is no competition for any
resource (e.g., a file, memory, network port, etc).

=head2 The Expressive Power of Regular Languages

This module is grounded in the expressive power afforded by regular language
properties to express concurrency. Expansion into more powerful languages such as
context-sensitive or context-free is not part of the goal.

Since symbols in the PRE are mapped to subroutine names, computational power can
also be increased by giving a subroutine a C<state> variable, effectively turning
it into a coroutine. Memory is power. It does not provide unlimited power, but it
is what makes context-sensitive languages more powerful than regular languages.

Given the paragraph above, C<Sub::Genius> may also be described as a way to
explore more and more valid execution orderings derived from a graph containing
all valid orderings. This graph (the DFA) is described precisely by the PRE.

=head2 Use of Well Known Regular Language Properties

C<Sub::Genius> uses C<FLAT>'s ability to transform a regular expression (of the
regular-language variety, not a Perl regex!) into a deterministic finite automaton
(DFA). Once achieved, the DFA is minimized and depth-first enumeration of the
valid strings accepted by the original expression may be considered sequentially
consistent.

The parallel semantics are achieved by the addition of shuffle of two or more
regular languages. The result is also a regular language.

From [1]:

    A shuffle w of u and v can be loosely defined as a word that is obtained
    by first decomposing u and v into individual pieces, and then combining
    (by concatenation) the pieces to form w, in a way that the order of
    the pieces in each of u and v is preserved.

This preserves the total ordering required by regular languages u and v, but
admits the partial ordering (shuffling) of both. A valid string resulting from
this combination is necessarily sequentially consistent.

From [2]:

    ... the result of any execution is the same as if the operations of
    all the processors were executed in some sequential order, and the
    operations of each individual processor appear in this sequence in
    the order specified by its program.

The shuffle operator provides the concurrent semantics in a way the human mind
can understand. This is critical for bridging the gap between the concurrent
semantics people clamor for in Perl and the inherent uniprocess environment of
the perl runtime.

=head2 Regular Language Operators

The following operators are available via C<FLAT>:

=over 4

=item Concatenation: C<L1 L2>

There is no character for this; it is implied when two symbols are next to one
another. E.g. C<a b c d>, which can also be expressed as C<abcd> or even
C<[a][b][c][d]>.

Examples:

      my $plan = q{  a        b        c   };       # single char symbol
      my $plan = q{symbol1 symbol2 symbol3 };       # multi-char symbol

=item C<|> - Union: C<L1 | L2>

If it looks like an “or”, that is because it is. E.g. C<a|b|c|d> means a valid

lib/Sub/Genius/Extended.pod  view on Meta::CPAN

=item C<< scope => {} >>

Initial execution-scoped memory (a data-flow pipeline). If not provided, scope is
initialized as an empty hashref:

    my $final_scope = $sg->run_once(scope => {}, verbose => undef);

=item C<< verbose => 1|0 >>

Default is off. When enabled, prints diagnostic output.

=back

Runs the execution plan once and returns whatever the last subroutine returns:

    my $plan = join(q{&}, (a..z));
    my $sg   = Sub::Genius->new(preplan => $plan);
    $sg->init_plan;
    my $final_scope = $sg->run_once;

=item C<next>

C<run_once> calls C<next> if it has not been run after C<init_plan>. It will
continue to call C<next> if C<run_once> is called again, meaning the preplan
remains in place until C<next> is called again.

Iterating over all valid strings:

    while (my $plan = $sg->next) {
      print qq{Plan: $plan\n};
      $sg->run_once;
    }

Once the iterator has generated all valid strings, the loop concludes.

Note: pipelining is violated in the above example since the loop runs each plan
with no guaranteed ordering. C<$scope> is only meaningful within each execution
context.

Final scopes can be captured for later processing:

    my @all_final_scopes;
    while (my $plan = $sg->next_plan()) {
      print qq{Plan: $plan\n};
      my $final_scope = $sg->run_once;
      push @all_final_scopes, { $plan => $final_scope };
    }

There are no deterministic guarantees of the ordering of valid strings (i.e.,
sequentially consistent execution plans).

L<FLAT> provides utilities to enumerate accepted strings. The underlying method
creates an iterator.

When C<next> is called the first time, an iterator is created and the first
string is returned. There is currently no way to specify which plan is returned
first, which is why concurrent semantics should be declared so that any valid
string is sequentially consistent with the implementation’s memory model.

Perl provides access to these memories via lexical scoping (C<my>, C<local>) and
persistent subroutine memory (coroutines) via C<state>.

At this time, C<Sub::Genius> only permits finite languages by default, therefore
there is always a finite list of accepted strings.

As an example, the following admits a large number of orderings: 26! such plans:

    my $plan = join(q{&}, (a..z));
    my $final_scope = Sub::Genius->new(preplan => $plan)->run_once;

Thus, the following will take a long time, but will complete:

    my $ans; # global to all subroutines executed
    while (my $plan = $sg->next_plan()) {
      $sg->run_once;
    }
    print qq{ans: $ans\n};

Done right, the output after 26! iterations may very well be:

    ans: 42

A formulation of 26 subroutines operating over shared memory in which all
cooperative execution of all 26! orderings reduces to C<42> is left as an
exercise for the reader.

=item C<run_any>

Convenience wrapper around C<new>, C<init_plan>, C<next>, and C<run_once>:

    Sub::Genius->new(preplan => $plan)->run_any();

=item C<plan_nein>

I<DEPRECATED> - this was not a well thought out idea and will be removed in the
near term, if it does not remove itself first. C<< >:E >>

Resets an existing instance, effectively like calling C<new> again on it without
recapturing the reference.

=back

=head1 PERFORMANCE CONSIDERATIONS

L<FLAT> is useful for complex semantics, but FA state growth can be extreme as it
moves from the nondeterministic realm to the deterministic.

In most cases, the more nondeterministic the PRE (e.g., more shuffles / C<&>), the
longer it takes for the final DFA to be created. A PRE like:

    my $plan = join(q{&}, (a..z));

can overwhelm memory and time on typical systems.

The algorithms in L<FLAT> are classic conversions: PRE → PFA → NFA → DFA → min DFA,
as discussed in standard automata texts (e.g., [5]).

Two approaches mitigate performance issues:

=over 4

lib/Sub/Genius/Extended.pod  view on Meta::CPAN

=head2 fash

C<fash> is a bash script wrapper around L<FLAT> to make exploration of PREs easier.
It can help leverage external tools such as graphviz, JFLAP, and image viewers for
visualizing underlying automata.

B<Note>: With C<fash>, multi-character symbols must be encased in square brackets
because it calls L<FLAT> directly.

Example: dump a PFA as GraphViz dot and render to PNG:

    $ fash pfa2gv "[abc]&[def]" | dot -Tpng > my-pfa.png

Then open C<my-pfa.png>.

To see available commands:

    $ fash help

=head2 See Also

L<stubby> and L<fash>.

=head1 SEE ALSO

L<Pipeworks>, L<Sub::Pipeline>, L<Process::Pipeline>, L<FLAT>, L<Graph::PetriNet>

=head2 Good Reads

=over 4

=item * 1. L<https://www.planetmath.org/shuffleoflanguages>

=item * 2. Leslie Lamport, "How to Make a Multiprocessor Computer That Correctly
Executes Multiprocess Programs", IEEE Trans. Comput. C-28,9 (Sept. 1979), 690-691.

=item * 3. L<https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf>

=item * 4. L<https://troglodyne.net/video/1615853053>

=item * 5. Introduction to Automata Theory, Languages, and Computation; Hopcroft, Motwani,
Ullman. Any year.

=item * 6. L<https://chapel-lang.org/docs/language/spec/memory-consistency-model.html#sequential-consistency-for-data-race-free-programs>

=back

=head1 COPYRIGHT AND LICENSE

Same terms as Perl itself.

=head1 AUTHOR

OODLER 577 E<lt>oodler@cpan.orgE<gt>

=head1 ACKNOWLEDGEMENTS

I<TEODESIAN> (@cpan) is acknowledged for his support and interest in this project,
in particular his work lifting the veil off of what passes for concurrency these
days; namely, I<most of the "Async" modules out there are actually fakin' the funk
with coroutines.> See L<https://troglodyne.net/video/1615853053> for a fun, fresh,
and informative video on the subject.