.. Copyright 2022 NWChemEx-Project .. .. Licensed under the Apache License, Version 2.0 (the "License"); .. you may not use this file except in compliance with the License. .. You may obtain a copy of the License at .. .. http://www.apache.org/licenses/LICENSE-2.0 .. .. Unless required by applicable law or agreed to in writing, software .. distributed under the License is distributed on an "AS IS" BASIS, .. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. .. See the License for the specific language governing permissions and .. limitations under the License. .. _call_graph_design: ################################## Designing the Call Graph Component ################################## Stemming from the discussions in :ref:`pp_architecture` and :ref:`module_manager_design` PluginPlay needs a call graph component. This section describes the overall design of that component. ********************* What is a call graph? ********************* .. note:: To make contact with typical computer science terminology the use of static and dynamic call graphs differ somewhat in this section than in other places of the manual. Call graphs are graphs (in the mathematical sense) that represent the control flow of a program. Each node in a call graph represents one function in the program. Edges between nodes are directed from the calling function to the called function. Given the complexity of most programs, call graph representations are typically determined by running the program and recording the control flow. The resulting call graph is only representative of the run used to generate it. Such call graphs are typically known as "dynamic" call graphs, since they are generated dynamically. In theory, there also exists a "static" call graph which shows all possible control flow paths through the program; however, for most programs this call graph is far too complicated to be useful and determining it has undecidable complexity. In the PluginPlay call graph component we define "call graph" slightly differently than the computer science definition just given. In particular, in PluginPlay's call graph component, the nodes are user-provided :ref:`module` objects, not individual function calls. Similarly, the edges go from the calling :ref:`module` object to the callee :ref:`module` object, not between individual function calls. The net result is that PluginPlay's call graph component is a coarse-grained representation of the actual call graph. ************************* Call Graph Considerations ************************* Sections :ref:`pp_architecture` and :ref:`module_manager_design` passed a number of considerations to the call graph component which we list here: #. Inspect and modify the call graph - Need to be able to add/remove nodes at runtime - Must be able to "rewire" the call graph #. Leverage cache component for memoization, saving/loading, and checkpoint/restart #. Dynamically determine interface for calling a module - Modules may be callable in different ways, similar to overloads in C++ #. Remain domain agnostic - Need to be compatible with a domain's native types - Realize that the set of types in a domain may expand over time - Avoid directly coupling one domain to another #. Support a Python :ref:`api` - Using pure Python, there is no way to instantiate a class template (or function template) at runtime, meaning all interfaces must be known at compile time. *N.B.*, Cppyy :cite:`cppyy` is a notable exception. ***************** Call Graph Design ***************** .. note:: PluginPlay was designed before considering Cppyy and this discussion assumes that only pure Python bindings are being considered. Node Design =========== As established the nodes of the call graph will be PluginPlay :ref:`module` objects and will need to be function-like. We propose the ``Module`` class to describe the modules. Users will create ``Module`` instances which contain their algorithms and any state the algorithm needs. Then the ``Module`` object can be run by providing it any inputs it needs. We do not want to use the constructor for running the module, as the constructor is more naturally used to initialize any state the ``Module`` may have. Thus we require the ``Module`` class to have a ``run`` method. The ``run`` method will take a series of inputs and return zero or more results. Since the ``run`` method will be written in C++ we now have to decide on the types of the inputs/results. The consideration to remain domain agnostic immediately suggests a templated solution and we suggest that ``run`` looks like: .. code-block:: c++ template std::tuple run(Inputs&&...); While a perfectly acceptable C++ solution, this :ref:`api` can not be exposed to Python without instantiating every possible function template, *i.e.*, to expose this to Python we need to know every possible choice for the ``Results`` and ``Inputs`` parameter packs. In turn, PluginPlay would need to either know domain information (which we don't want it to know) or we would have to restrict the allowable types to some set (which could have serious performance consequences). A common C++ technique for passing arbitrary types, in a non-templated type-safe manner is "type erasure.". For now we ignore the details of how type erasure works and simply note that it requires us to define a class to act as, more or less, a common base class for every type we may want to wrap. We thus establish the ``AnyField`` class for type erasing inputs/results. We also note that templating is only required to create the ``AnyField`` object and to unwrap it, the actual class is not templated. In terms of ``AnyField`` we can write the ``run`` :ref:`api` as: .. code-block:: c++ std::vector run(std::vector inputs); Where we switched to ``std::vector`` to avoid needing to know the number of fields at compile time. .. note:: Python actually uses a similar trick to interface with the C code underlying it. By ensuring that we can convert ``AnyField`` objects to/from Python handles, we are able to expose this interface to Python seamlessly. Modules written in Python get inputs that are Python objects and the returned Python objects are automatically converted to ``AnyField`` objects. Similarly, when an ``AnyField`` object containing a Python object is unwrapped in C++ we know the C++ type we want and under the hood we simply cast the Python object to that type before returning it to the C++. We could stop here, but actually using the ``run`` members is quite clunky. The problem is that at compile time every module is now interchangeable with every other module because they all have literally the same :ref:`api`. However, type erasure is still type-safe, it just defers the type check to runtime. Thus it should be noted that at runtime they are **NOT** all compatible. This is because inside the run function you'll have to do something like: .. code-block:: c++ std::vector run(std::vector inputs){ // Our function expects two arguments assert(inputs.size() == 2); // Argument 0 should be of type T T arg0 = inputs[0].unwrap(); // Argument 1 should be a double double arg1 = inputs[1].unwrap(); // Rest of function... } While this will always compile, it will raise runtime errors if the number of inputs is not two, the first argument is convertible to type ``T``, or if the second argument is not convertible to a ``double``. Having to wait until runtime (and possibly very far into a session) to find out if the call graph is wired correctly is undesirable. Another problem is say that we have two modules whose ``run`` APIs essentially are: .. code-block:: c++ double run(double); after we unwrap the ``AnyField`` objects. These modules are :ref:`api` compatible at both compile time and run time. The problem is these modules may do very different things despite having the same :ref:`api`. To address the problems of: runtime type-checking and discerning callbacks we introduce the "Property Type" component. The name "property type" comes from the fact that most of the original use cases focused on using property types to discern among modules which compute different properties, but have the same :ref:`api`. PluginPlay only includes infrastructure for registering property types, not the actual property types. This is because property types are necessarily domain-specific and should be defined downstream of PluginPlay. Each :ref:`module` internally must set the property types that it satisfies. By stating that a module ``M`` satisfies property type ``A`` the module developer of ``M`` is saying that anytime anyone needs a module capable of computing ``A``, they may use ``M``. In this sense, PluginPlay uses each :ref:`property_type` as a :ref:`strong_type`, helping avoid accidentally using a module in the wrong place. To address the runtime type-checking problem each property type also includes the types of the inputs and the results. Data Flow in to/out of a Module =============================== The previous sections introduced the components of the call graph. With these pieces it is now possible to describe how nodes will actually call one another. .. _fig_data_flow: .. figure:: assets/data_flow.png :align: center Left how typed information traverses the user's code into the module developer's code and right how typed information leaves the module developer's code and enters the user's code. Note that all data traverses the code boundary in type-erased form. To try and make the design from the last section more intuitive consider :numref:`fig_data_flow`. The left side shows the process of passing data into a :ref:`module`. This can be passing data into the first :ref:`module` in the call graph or from one :ref:`module` in the call graph to another. The first step is to type-erase the data. This is done by feeding the data through the :ref:`property_type` resulting in ``AnyField`` objects. The ``AnyField`` objects then cross the code boundary into PluginPlay, where cacheing and memoization may occur, before being forwarded to the :ref:`module`. Inside the :ref:`module` the same :ref:`property_type` is used to unpack the ``AnyField`` objects. Returning data simply reverses the process. There are several points to note about this design: #. User and module developers need to agree on a set of property types. This simply amounts to standardization, *i.e.*, the field has to agree on what it means to compute a specific property, including the classes. - *N.B.* with good class design it is possible to avoid coupling the identity of the class to the data layout of the class, *e.g.*, by using :ref:`pimpl`. #. The user code never directly touches the module developer's code, nor does the module developer's code every directly touch the user's code. - This places onus on PluginPlay to maintain its APIs, but avoids the user and module developer's codes from every having to know about one another. - This facilitates extending the call graph later since new code only needs to know about PluginPlay (and the property types) #. Type-erasure is **NOT** serialization - Serialization often has a large performance-penalty - Type-erasure is a pointer cast and extremely cheap on the scale of most scientific simulations. Assembling the Call Graph ========================= With a design in place to wrap algorithms in modules, and a design for how to call the modules, the last piece of the call graph component is literally assembling the call graph. As a first pass we have adopted a simple solution depicted in :numref:`fig_assemble_call_graph`. .. _fig_assemble_call_graph: .. figure:: assets/making_callgraph.png :align: center Each module must register with PluginPlay the number of callback points it exposes, and the property types which will be used at those points. PluginPlay chooses (with a lot of help from the user) the modules for each callback point and gives them to the module at run time. Rather than create a literal call graph object to represent the call graph we have taken a linked list approach. When a module developer writes a module they register with PluginPlay all of their callback points. In :numref:`fig_assemble_call_graph` the developer has registered three callback points. To distinguish callback points within the module, each callback point is assigned a unique name (unique within the scope of the module). Here these names are ``"Callback A"``, *etc.*. In addition to the name of the callback point, PluginPlay also needs to know what :ref:`property_type` will be used for the callback. Module developers register the domain-specific property type they will use. As noted in :numref:`fig_assemble_call_graph` the property types need not be different. These steps are written as part of developing the module (although they will actually get executed at run time). When it comes time to assemble a call graph, PluginPlay will look at the first module to call, retrieve its list of callback points, and determine which module, from the module pool, will be called at which call back location. Once the callbacks are determined, the module is linked to them and the process is repeated recursively inside each callback module. Summary ======= The current design addresses the above considerations by: #. Inspect and modify the call graph - The call graph is made up of components which have run time state. - Run time state of call graph can be inspected and modified - Able to swap modules out. #. Leverage cache component for memoization, saving/loading, and checkpoint/restart - PluginPlay is invoked before and after each module call. - This allows PluginPlay to do cacheing, memoization, and saving. - Memoization falls to the module component. #. Dynamically determine interface for calling a module - All modules have the same, type-erased base :ref:`api`. - It is up to the user and module developer to determine the property type to use. While the list of property types can not evolve at run time, it is possible to use logic to determine which property type to use at runtime. #. Remain domain agnostic - Type-erasure preserves the domain's native types, but uses pointer trickery to avoid exposing them. - Type-erasure only needs to know type of object at creation and unwrapping so more types can be wrapped later - All calls go through PluginPlay, which avoids directly coupling domains #. Support a Python :ref:`api` - PluginPlay exposes type-erased APIs which can easily interoperate with Python's object handles and duck typing - Python object handles can be cast to C++ types under the hood of the type-erased objects This design has also mandated the creation of several components and design criteria for those components. #. Module Component - Users of PluginPlay write algorithms in ``Module`` objects - ``Module`` constructor is reserved for initialization - ``Module`` must expose ``run`` member for running the object given a set of type-erased inputs, and must return a set of type-erased outputs - Store a list of callback points, and a list of callbacks for those points #. Any Component - ``AnyField`` class for type-erasing inputs and results to modules - Need to be compatible with Python object handles #. Property Type Component - Used to restore compile time type checks - Facilitates wrapping/unwrapping type-erased objects - Establishes domain-specific properties a module can compute - Downstream users register property types - PluginPlay infrastructure must be agnostic to API codified by property type, **************** Additional Notes **************** #. For simplicity we assumed that each module object stores a list of the modules it will call, and PluginPlay manipulates this list. We could create a full fledged graph object at a later point. This would facilitate searching the graph.