THIS MODULE IS EXPERIMENTAL

Until further noted, this module subject to extreme fluxuations in interfaces and implied approaches. The hardest part about this will be managing all the cool and bright ideas stemming from it.

NAME

Sub::Genius - Manage concurrent Perl semantics in the uniprocess execution model of perl.

In Other Words

Sub::Genius generates a correctly ordered, sequential series of subroutine calls from a declarative plan that may be parallel or concurrent in nature. This allows a concurrency plan to be serialized or linearized properly for execution in a uniprocess (or single CPU) environment.

Sub::Genius introduces all the joys and pains of multi-threaded, shared memory programming to the uniprocess environment that is perl.

After all, if we're going to fake the funk out of coroutines [4], let's do it correctly. :)

SYNOPSIS

    # D E F I N E  T H E  P L A N
    my $preplan = q{( A B )  &   ( C D )      (Z)};
    #                 \ /          \ /         |
    #>>>>>>>>>>>     (L1) <shuff>  (L2) <cat>  L3
     
    # C O N V E R T  T H E  P L A N  T O  D F A 
    my $sq = Sub::Genius->new(preplan => $preplan);

    # I N I T  T H E  P L A N
    $sq->init_plan;
     
    # R U N  T H E  P L A N
    $sq->run_once;
    print qq{\n};
    
    # NOTE: sub declaration order has no bearing on anything
     
    sub A { print qq{A}  } #-\
    sub B { print qq{B}  } #--- Language 1
     
    sub C { print qq{C}  } #-\
    sub D { print qq{D}  } #--- Language 2
     
    sub Z { print qq{\n} } #--- Language 3

The following expecity execution of the defined subroutines are all valid according to the PRE description above:

    # valid execution order 1
      A(); B(); C(); D(); Z();
    
    # valid execution order 2
      A(); C(); B(); D(); Z();
    
    # valid execution order 3
      A(); C(); D(); B(); Z();
    
    # valid execution order 4
      C(); A(); D(); B(); Z();
    
    # valid execution order 5
      C(); D(); A(); B(); Z();

In the example above, using a PRE to describe the relationship among subroutine names (these are just multicharacter symbols); we are expressing the following constraints:

sub A: must run before sub B
sub C: must run before sub D
sub Z: is always called last

Meaningful Subroutine Names `FLAT` allows single character symbols to be expressed with out any decorations;

    my $preplan = q{ s ( A (a b) C & ( D E F ) ) f };  # define plan
    my $sq = Sub::Genius->new(preplan => $preplan);    # convert plan

The concatentation of single symbols is implied, and spaces between symbols doesn't even matter. The following is equivalent to the PRE above,

    my $preplan = q{s(A(ab)C&(DEF))f};                 # define plan
    my $sq = Sub::Genius->new(preplan => $preplan);    # convert plan

It's important to note immediately after the above example, that the PRE may contain symbols that are made up of more than one character.

But this is a mess, so we can use longer subroutine names as symbols and break it up in a more readable way:

    # define plan
    my $preplan = q{
      start
        (
          sub_A
          (
            sub_a
            sub_b
          )
          sub_C
        &
         (
          sub_D
          sub_E
          sub_F
         )
        )
      fin
    };
     
    # convert plan
    my $sq = Sub::Genius->new(preplan => $preplan);

This is much nicer and starting to look like a more natural expression of concurrent semantics, and allows the expression of subroutines as meaningful symbols.

Inline Comments

A final convenience provided during the preprocessing of PREs (which can be turned off with preprocess => 0 passed to new), is the support of inline comments and empty lines.

For example,

    # define plan
    my $preplan = q{
      start         # Language 1 (L1) always runs first
        (
          sub_A     # Language 2 (L2) 
          ( 
            sub_a   # L2
            sub_b   # L2
          )
          sub_C     # L2
        &           #<~ shuffle's L2 and L3
         (
          sub_D     # L3
          sub_E     # L3
          sub_F     # L3
         )
        )
      fin           # Language 4 (L4) always runs last
    };
    
    # convert plan
    my $sq = Sub::Genius->new(preplan => $preplan);

DESCRIPTION

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

Totally ordered means, subroutine B must follow subroutine A.

   my $preplan = q{ A   B };

Partially ordered means, subroutine A may lead or lag subroutine B, both must be executed.

   my $preplan = q{ A & B };

Using this concept, Sub::Genius can generate a valid sequential ordering of subroutine calls from a declarative plan that may directly express concurrency.

`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 perl is. This has necessarily restricted the expressive semantics that can very easily be extended to DWIM in a concurrent execution model. The problem is that perl has been 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 does perl not have real threads or admit real concurrency and semantics. Accepting the truth of the uniprocess model makes it clear and brings to it a lot of freedom. This module is meant to facilitate shared memory, multi-process reasoning to perl's fixed uniprocess reality.

The uniprocess model ease of reasoning, particularly in the case of shared memory programming semantics and consistency thereof. See [3] for more background on this.

Atomics and Barriers

When speaking of concurrent semantics in Perl, the topic of atomic primatives often comes up, because in a truly multi-process execution environment, they are very important to coordinating the competitive access of 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 any of these things. Singular lines of execution need no coordination because there is no competition for any resource (e.g., a file, memory, network port, etc).

The Expressive Power of Regular Languages

This module is firmly grounded on the power afforded in expressiveness by using Regular Language properties to express concurrency. Expansion into more powerful languages such as context sensitive or context free is not part of the goal. For anyone interested in this topic, it's a relevant to consider that since symbols in the PRE are mapped to subroutine names; it does add computational power when a subroutine is given a state variable, effectively turning them into coroutines. Memory is power; it doesn't provide unlimited power, but it is the thing that makes Context Sensitive Languages more power than Regular Languages, etc.

Given the paragraph above, Sub::Genius may also be described as a way to explore more or more valid execution orderings which have been derived from a graph that contains all valid orderings. This graph (the DFA) described precisely by the PRE.

Use of Well Known Regular Language Properties

Sub::Genius uses FLAT's ability to tranform a Regular Expression, of the Regular Language variety (not a Perl regex!) into a Deterministic Finite Automata (DFA); once this has been achieved, the DFA is minimized and depth-first enumeration of the valid "strings" accepted by the original Regular Expression may be considered sequentially consistent. The parallel semantics of the Regular Expression are achieved by the addition of the 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 means that it preserves the total ordering required by regular languages u and v, but admits the partial ordering - or shuffling - of the languages of both. This ultimately means that a valid string resulting from this combination is necessarily sequentially consistent. Which, 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.

And it is the shuffle operator that provides the concurrent semantics to be expressed rather naturally, and in a way the human mind can understand. This, above all, is absolultely critical for bridging the gap between the concurrent semantics people clamor for in Perl and the inherent uniprocess environment presented in the perl runtime.

Regular Language Operators

The following operator are available via FLAT:

concatentation - there is no character for this, it is implied when two symbols are directly next to one another. E.g., a b c d, which can also be expressed as abcd or even [a][b][c][d].

examples,

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

| - union - represented as a pipe, |.

If it looks like an or, that is because it is. E.g., a|b|c|d means a valid string is, 'a' or 'b' or 'c' or 'd'.

examples,

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

& - shuffle - represented by the ampersand, &.

It is the addition of this operator, which is closed under Regular Languages, that allows concurrency to be expressed. It is also generates a Parallel Finite Automata, which is an e-NFA with an additional special transition, represented by lambda. It's still closed under RLs, it's just a way to express a constraint on the NFA that preserves the total and partial ordering among shuffled languages. It is this property that leads to guaranteeing sequential consistency.

E.g.,

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

* - Kleene Star - Sub::Genius currently will die if one attempts to use this, but it is supported just fine by FLAT. It's not supported in this module because it admits an infinite language. That's not to say it's not useful for towards the aims of this module; but it's not currently understood by the merely sub-genius module author(s) how to leverage this operator.

E.g.,

      my $preplan = q{    a     &     b*     &   c};  # single char symbol
      my $preplan = q{symbol1 & symbol2* & symbol3};  # multi-car symbol

Note: the above PRE is not supported in Sub::Genius, but may be in the future. One may tell Sub::Genius to not die when an infinite language is detected by passing the infinite flag in the constructor; but currently the behavior exhibited by this module is considered undefined:

E.g.,

      my $preplan = q{    a     &     b*     &   c      };                    # single char symbol
      my $sq = Sub::Genius->new(preplan => $preplan, 'allow-infinite' => 1);  # without 'allow-infinite'=>1, C<new> will fail here

Precedence

(, )

Parenthesis are supported as a way to group constituent languages, provide nexting, and exlicitly express precendence. Many examples in this document use parenthesis liberally for clarity.

      my $preplan = q{ s ( A (a b) C & ( D E F ) ) f };

For example, the following preplan takes advantage of parentheses effectively to isolate six (6) distinct Regular Languages (init, L1-4, fin) and declare their total and partial ordering constraints that must be obeyed when serialized. The example is also nicely illustrative of the making a plan more readable using comments (not to suggest an idiom :)).

    # define plan
    my $preplan = q{
      ##########################################################
      # Plan Summary:                                          #
      #  'init' is called first, then 4 out of 8 subroutines   #
      #   are called based on the union ('|', "or") of each    #
      #   sub Regular Language. 'fin' is always called last    #
      ##########################################################
    
      init # always first
      (
        (alpha   | charlie) &   # L1  - 'alpha'   or 'charlie'
        (whiskey | delta)   &   # L2  - 'whiskey' or 'delta'
        (bravo   | tango)   &   # L3  - 'bravo'   or 'tango'
        (foxtrot | zulu)        # L4  - 'foxtrot' or 'zulu'
        # note: no '&'    ^^^^^ since it's last in the chain
      )
      fin  # always last
    };

RUNTIME METHODS

A minimal set of methods is provided, more so to not suggest the right way to use this module.

new

Required parameter:

preplan => $preplan

Constructor, requires a single scalar string argument that is a valid PRE accepted by FLAT.

    my $preplan = q{
      start
        (
          subA
          (
            subB_a subB_b
          )
          subC
        &
          subD subE subF
        )
      finish
    };

    my $sq = Sub::Genius->new(preplan => $preplan);

Optional pramameter:

cachedir => $dir

Sets default cache directory, which by default is $(pwd)/_Sub::Genius.

If set to undef, caching is disabled.

preprocess => undef|0

Disables the current preprocessing, which strips comments and adds brackets to all words in the PRE.

q{allow-infinite} => 1

Default is undef (off).

Note: due to the need to explore the advantages of supporting infinite languages, i.e., PREs that contain a Kleene star; init_plan will die after it compiles the PRE into a min DFA. It checks this using the FLAT::DFA::is_finite subroutine, which simply checks for the presence of cycles. Once this is understood more clearly, this restriction may be lifted. This module is all about correctness, and only finite languages are being considered at this time.

The reference, if captured by a scalar, can be wholly reset using the same parameters as new but calling the plan_nein methods. It's a minor convenience, but one all the same.

cachedir

Accessor for obtaining the value of the cache directory, either the default value or as set via new.

checksum

Accessor for obtaining the MD5 checksum of the PRE, specified by using the preplan parameter via new.

cachefile

Acessor for getting the full path of the cache file associated with the PRE; this file may or may not exist.

init_plan

This takes the PRE provided in the new constructure, and runs through the conversion process provded by FLAT to an equivalent mininimzed DFA. It's this DFA that is then used to generate the (currently) finite set of strings, or plans that are acceptible for the algorithm or steps being implemented.

    my $preplan = q{
      start
        (
          subA
          (
            subB_a subB_b
          )
          subC
        &
          subD subE subF
        )
      finish
    };
    
    my $sq = Sub::Genius->new(preplan => $preplan);
    
    $sq->init_plan;

Note: Caching

It is during this call that the DFA associated with the preplan PRE is compiled into a DFA. That also means, this is where cached DFAs are read in; or if not yet cached, are saved after the process to convert the PRE to a DFA.

As is mentioned several times, caching may be disabled by passing the parameter, cachedir => undef in the new constructor.

run_once

Returns scope as affected by the assorted subroutines.

Accepts two parameters, both are optional:

ns => q{My::Sequentially::Consistent::Methods}

Defaults to main::, allows one to specify a namespace that points to a library of subroutines that are specially crafted to run in a sequentialized environment. Usually, this points to some sort of willful obliviousness, but might prove to be useful nonetheless.

scope => {}

Allows one to initiate the execution scoped memory, and may be used to manage a data flow pipeline. Useful and consistent only in the context of a single plan execution. If not provided, scope is initialized as an empty anonymous hash reference:

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

verbose => 1|0

Default is falsy, or off. When enabled, outputs arguably useless diagnostic information.

Runs the execution plan once, returns whatever the last subroutine executed returns:

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

next

FLAT provides some utility methods to pump FAs for valid strings; effectively, its the enumeration of paths that exist from an initial state to a final state. There is nothing magical here. The underlying method used to do this actually creates an interator.

When next is called the first time, an interator is created, and the first string is returned. There is currently no way to specify which string (or plan) is returned first, which is why it is important that the concurrent semantics declared in the PRE are done in such a way that any valid string presented is considered to be sequentially consistent with the memory model used in the implementation of the subroutines. Perl provides the access to these memories by use of their lexical variable scoping (my, local) and the convenient way it allows one to make a subroutine maintain persistent memory (i.e., make it a coroutine) using the state keyword. See more about PERL's UNIPROCESS MEMORY MODEL AND ITS EXECUTION ENVIRONMENT in the section above of the same name.

An example of iterating over all valid strings in a loop follows:

    while (my $preplan = $sq->next_plan()) {
      print qq{Plan: $preplan\n};
      $sq->run_once;
    }

Note, in the above example, the concept of pipelining is violated since the loop is running each plan ( with no guaranteed ordering ) in turn. $scope is only meaningful within each execution context. Dealing with multiple returned final scopes is not part of this module, but can be captured during each iteration for future processessing:

    my @all_final_scopes = ();
    while (my $preplan = $sq->next_plan()) {
      print qq{Plan: $preplan\n};
      my $final_scope = $sq->run_once;
      push @all_final_scopes, { $preplan => $final_scope };
    }
    # now do something with all the final scopes collected
    # by @all_final_scopes

At this time Sub::Genius only permits finite languages, therefore there is always a finite list of accepted strings. The list may be long, but it's finite.

As an example, the following admits a large number of orderings in a realtively compact DFA, in fact there are 26! (factorial) such valid orderings:

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

Thus, the following will take long time to complete; but it will complete:

    my $ans; # global to all subroutines executed
    while ($my $preplan = $sq->next_plan()) {
      $sq->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 42 is left as an excercise for the reader.

run_any

For convenience, this wraps up the steps of plan, init_plan, next, and run_once. It presents a simple one line interfaces:

    my $preplan = q{
      start
        (
          subA
          (
            subB_a subB_b
          )
          subC
        &
          subD subE subF
        )
      finish
    };
    
    Sub::Genius->new(preplan => $preplan)->run_any();

plan_nein

Using an existing reference instantiation of Sub::Genius, resets everything about the instance. It's effectively link calling new on the instance without having to recapture it.

DEBUGGING AND TOOLS

stubby

This module installs a tool called stubby into your local $PATH. For the time being it is located in the ./bin directory of the distribution and on Github. It will help anyone interested in getting an idea of what programming using this model is like.

fash

This tool is just a bash script that makes it easier to called FLAT powered perl one-liners more efficiently.

Using this tool, one may explore the details of the PRE they are wishing to use. It allows one to also leverage external tools, such as graphviz, JFLAP[6], and image programs for seeing the underlying automata structures implied by the PRE being used. Debugging programs written using the model provided for by Sub::Genius is certainly going to require some time debugging. fash is just one way to do it.

This is a shell wrapper around FLAT that provides nice things, like the ability to dump PFAs generated from a PRE in graphviz format. It can also dump interesting things like the AST resulting from the parsing of the PRE (done so by RecDescent::Parser).

Note: with fash, multi character symbols must be encased in square backets. This is because it calls FLAT routines directly.

Example dump of the Parallel Finite Automata that is described by the PRE in the fash command below, in GraphViz dot format:

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

Then open up my-pfa.png and see a nice image of your pet Finite Automate (which may surprise you).

To see all of the useful commands one may use to explore the PRE when determining how to describe the semantics being expressed when using Sub::Genius.

    $ fash help

PERFORMANCE LIMITATIONS

FLAT is very useful for fairly complex semantics, but the number of FA states grows extremely large as it moves from the non-deterministic realm to to the deterministic.

What that means in most cases, is that the more non-deterministic the PRE (e.g., the more shuffles or &'s), the longer it will take for the final DFA to be created. It would not be hard to overwhelm a system's memory with a PRE like the one suggested above,

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

This suggests all 26 letter combinations of all of the lower case letters of the alphabet (26! such combinations, as noted above) must be accounted for in the final minimized DFA, which is really just a large graph.

The algorithms inplemented in FLAT to convert from a PRE to a PFA (equivalent to a PetriNet) to a NFA to a DFA, and finally to a minimized DFA are the basic' ones discussed in any basic CS text book on automata, e.g., [5].

CACHING

The practicality of converting the PRE to a DFA suitable for generating valid execution orders is reached relatively quickly as more shuffles are added. For this reason, init_plan looks for a cache file. If available, it's loaded saving potentally long start up times.

How Caching Works in `Sub::Genius`

Caching of the PRE is done after it has been compiled into a DFA, which is called most directly via init_plan. Unless the constructor has been created specifically turning it off via cachedir=undef>, Storable's store method is used to save it to the cachedir. Internally, a md5 checksum is generated using Digest::MD5's md5_hex method on the PRE after it's been preprocessed. If the constructor is passed the flag to disable preprocessing, the checksum is generated in consideration of the PRE as specified using the preplan parameter of new.

The lifecycle of caching, assuming default behavior is:

constructor used to create instance with preplan specified
preplan is preprocessed to strip comments, blank spaces, and put square braces around all words
a checksum is generated using the value of post-preprocessed preplan field
calling init_plan first looks for a cached file representing the DFA's checksum; if found it retrieves this file and this is the DFA moving forward
if no such cached DFA exists, then internally the FLAT enabled process to convert a PRE to a DFA is invoked; this is the step that has the potential for taking an inordinate amount of time
once the DFA is generated, it is saved in cachedir with the file name that matches the value of checksum.

Final Notes on Caching

Caching for compiled things, in lieu of better performance for necessarily complext algorithms, seems an acceptible cheat. Well known examples of this included Inline (e.g., the _Inline default directory) and the caching of rendered template by Template Toolkit.

This could be couched as a benefit, but the truth is that it would be better if caching DFAs was not necessary. In the case for very complex or highly shuffled PREs, it is necessary to precompile - and maybe even on much more performant machines than the one the code using them will run on. It may just be the nature of taming this beast.

This also suggests best practices if this module, or the approach it purports, ever reaches some degree of interesting. It is reasonable to imagine the rendering of frozen DFAs (the compiled form of PREs used to generate valid execution plans) is like a compilation step, just like building XS modules necessarily requires the compiling of code during module installation. It could also be, that assuming store'd files are platform independent, that a repository of these can be mainted somewhere like in a git repo for distribution. Indeed, there could be entire modules on CPAN that provide libraries to DFAs that ensure sequential consistency for a large variety of applications.

Until this is proven in the wild, it's just speculation. For now, it's sufficient to state that caching is a necessary part of this approach and may be for some time. The best we can do is provide a convenient way to handle it, and it's taking a hint from modules like Inline that we start off on the right footing.

As a final note, caching can be disabled in the constructure,

    my $sq = Sub::Genius->new( preplan => $preplan, cachedir => undef );

COPYRIGHT AND LICENSE

Same terms as perl itself.

AUTHOR

OODLER 577 <oodler@cpan.org>

ACKNOWLEDGEMENTS

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, most of the "Async" modules out there are actually fakin' the funk with coroutines.. See https://troglodyne.net/video/1615853053 for a fun, fresh, and informative video on the subject.

To install Sub::Genius, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Sub::Genius

CPAN shell

perl -MCPAN -e shell
install Sub::Genius

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

THIS MODULE IS EXPERIMENTAL

NAME

In Other Words

SYNOPSIS

Meaningful Subroutine Names `FLAT` allows single character symbols to be expressed with out any decorations;

Inline Comments

DESCRIPTION

`perl`'s Uniprocess Memory Model and Its Execution Environment

Atomics and Barriers

The Expressive Power of Regular Languages

Use of Well Known Regular Language Properties

Regular Language Operators

Precedence

RUNTIME METHODS

DEBUGGING AND TOOLS

See Also

PERFORMANCE LIMITATIONS

CACHING

How Caching Works in `Sub::Genius`

Final Notes on Caching

SEE ALSO

Good Reads

COPYRIGHT AND LICENSE

AUTHOR

ACKNOWLEDGEMENTS

THIS MODULE IS EXPERIMENTAL

NAME

In Other Words

SYNOPSIS

Meaningful Subroutine Names FLAT allows single character symbols to be expressed with out any decorations;

Inline Comments

DESCRIPTION

perl's Uniprocess Memory Model and Its Execution Environment

Atomics and Barriers

The Expressive Power of Regular Languages

Use of Well Known Regular Language Properties

Regular Language Operators

Precedence

RUNTIME METHODS

DEBUGGING AND TOOLS

See Also

PERFORMANCE LIMITATIONS

CACHING

How Caching Works in Sub::Genius

Final Notes on Caching

SEE ALSO

Good Reads

COPYRIGHT AND LICENSE

AUTHOR

ACKNOWLEDGEMENTS

Module Install Instructions

Meaningful Subroutine Names `FLAT` allows single character symbols to be expressed with out any decorations;

`perl`'s Uniprocess Memory Model and Its Execution Environment

How Caching Works in `Sub::Genius`