System and method for cellular network computing and communications6085233
Abstract
A cell-based system for computation and communication. A cell is a well-defined structure that associates executable code and data into a basic computational module. A processor can traverse a cell and execute the instructions therein. Cells are arranged into a network with each cell linked to other cells by forward branches or other paths. A processor branches to a cell by loading its program counter with the address of the cell or by sending a packet of data across a communications network to activate remote processing in a cell. Cells have a path selection section for evaluating conditional branches and causing branches to be followed. Multiple branches may be followed in parallel from any cell. A tree-like organization is superimposed on the network by distinguishing one branch to each cell as a superbranch incorporating a return path (called "recession path"). A cell also has a convergence section that handles processors and threads of execution that return to that cell by this path (called "recession"). The convergence section implements rules that control which, if any, processors or threads continue to execute upon recession as well as rules for handling any resulting values associated with the processors or threads. The cellular computational module controls highly parallel and distributed processing and supports dynamic self-modification of the system. Information is acquired within the system not only through the acquisition of data and the modification of executable code within the cells, but also through the encoding of information and behavior into the structure of links that connect the cells.
Claims
What is claimed is:
1. A cell-based computation and communications system comprising:
a memory system;
a cell network defined within the memory system, the cell network including a plurality of cells, each cell being associated with instructions defining the behavior of the cell;
the cell network including a plurality of linking cells defining structural links within the cell network, each linking cell having a plurality of forward link references to respective forward linked cells and a recession link reference to a respective recession linked cell; and
a processing system to process instructions within the cell network which is capable of selectively processing instructions associated with different cells in parallel;
wherein the cell network includes instructions for engendering parallel processing in conjunction with following at least some of the forward link references and instructions for controlling convergence of parallel processing in conjunction with following at least some of the recession link references; and
wherein each of the recession link references is defined as part of the structure of the cell network and is established separately from following the forward link references.
2. The system of claim 1 wherein a plurality of respective cells within the cell network are capable of being activated through following forward link references by both (i) an evocation wherein a recession link reference associated with the respective cell is followed upon completion of the activities directed by the respective cell; and (ii) an invocation wherein a return address is provided in connection with activating the respective cell and the return address is followed upon completion of the activities directed by the respective cell.
3. The system of claim 1 wherein the plurality of forward link references in at least some of the linking cells include conditional forward link references which are followed only when an associated condition is satisfied; and
wherein the conditional forward link references in at least some of the linking cells include both (i) a non-exclusive conditional forward link reference which is capable of being followed in parallel with other forward link references in the same cell; and (ii) an exclusive conditional forward link reference which, when followed, is followed to the exclusion of following other forward link references in the same cell in parallel.
4. The system of claim 2 wherein the plurality of forward link references in at least some of the linking cells include conditional forward link references which are followed only when an associated condition is satisfied; and
wherein the conditional forward link references in at least some of the linking cells include both (i) a non-exclusive conditional forward link reference which is capable of being followed in parallel with other forward link references in the same cell; and (ii) an exclusive conditional forward link reference which, when followed, is followed to the exclusion of following other forward link references in the same cell in parallel.
5. A cell-based computation and communications system comprising:
a memory system;
a cell network defined within the memory system, the cell network including a plurality of cells, each cell being associated with instructions defining the behavior of the cell;
the cell network including a plurality of linking cells defining links within the cell network, each linking cell having a plurality of forward link references to respective forward linked cells and a recession link reference to a respective recession linked cell; and
a processing system to process instructions within the cell network which is capable of selectively processing instructions associated with different cells in parallel;
wherein the cell network includes instructions for engendering parallel processing in conjunction with following at least some of the forward link references and instructions for controlling convergence of the parallel processing in conjunction with following at least some of the recession link references;
wherein a plurality of respective cells within the cell network are capable of being activated through following forward link references by both (i) an evocation wherein a recession link reference associated with the respective cell is followed upon completion of the activities directed by the respective cell; and (ii) an invocation wherein a return address is provided in connection with activating the respective cell and the return address is followed upon completion of the activities directed by the respective cell.
6. The system of claim 5 wherein the plurality of forward link references in at least some of the linking cells include conditional forward link references which are followed only when an associated condition is satisfied; and
wherein the conditional forward link references in at least some of the linking cells include both (i) a non-exclusive conditional forward link reference which is capable of being followed in parallel with other forward link references in the same cell; and (ii) an exclusive conditional forward link reference which, when followed, is followed to the exclusion of following other forward link references in the same cell in parallel.
7. A cell-based computation and communications system comprising:
a memory system;
a cell network defined within the memory system, the cell network including a plurality of cells, each cell being associated with instructions defining the behavior of the cell;
the cell network including a plurality of linking cells defining links within the cell network, each linking cell having a plurality of forward link references to respective forward linked cells; and
a processing system to process instructions within the cell network which is capable of selectively processing instructions associated with different cells in parallel;
wherein the cell network includes instructions for engendering parallel processing in conjunction with following at least some of the forward link references;
wherein the plurality of forward link references in at least some of the linking cells include conditional forward link references which are followed only when an associated condition is satisfied; and
wherein the conditional forward link references in at least some of the linking cells include both (i) a non-exclusive conditional forward link reference which is capable of being followed in parallel with other forward link references in the same cell; and (ii) an exclusive conditional forward link reference which, when followed, is followed to the exclusion of following other forward link references in the same cell in parallel.
8. A method for controlling parallel processing in a cell-based computation and communications system, wherein the system includes a network of cells, each cell being associated with instructions defining the behavior of the cell, the network of cells including a plurality of linking cells defining structural links within the cell network, each linking cell having a plurality of forward link references to respective forward linked cells in the network and a recession link reference to a respective recession linked cell in the network, the method comprising the steps of:
following at least some of the forward link references and at least some of the recession link references in the network of cells;
executing at least some of the instructions associated with the cells referenced by the forward link references and the recession link references which are followed;
engendering parallel processing in conjunction with following at least some of the forward link references in the linking cells;
controlling convergence of the parallel processing in conjunction with following at least some of the recession link references in the linking cells; and
establishing the recession link references independently from following the forward link references.
9. The method of claim 8 further comprising the steps of:
providing a plurality of respective cells within the cell network which are capable of being activated through following forward link references by both (i) an evocation wherein a recession link reference associated with the respective cell is followed upon completion of the activities directed by the respective cell; and (ii) an invocation wherein a return address is provided in connection with activating the respective cell and the return address is followed upon completion of the activities directed by the respective cell;
following at least some of the forward link references in the network by evocation; and
following at least some of the forward link references in the network by invocation.
10. The method of claim 8 further comprising the steps of:
associating conditions with at least some of the forward link references such that an associated forward link reference is followed only when the corresponding condition is satisfied, wherein the conditions include both exclusive conditions and non-exclusive conditions;
selectively following a forward link reference associated with an exclusive condition to the exclusion of following other forward link references in the same cell in parallel; and
selectively following a forward link reference associated with a non-exclusive condition while allowing other forward link references in the same cell to be followed in parallel.
11. The method of claim 9 further comprising the steps of:
associating conditions with at least some of the forward link references such that an associated forward link reference is followed only when the corresponding condition is satisfied, wherein the conditions include both exclusive conditions and non-exclusive conditions;
selectively following a forward link reference associated with an exclusive condition to the exclusion of following other forward link references in the same cell in parallel; and
selectively following a forward link reference associated with a non-exclusive condition while allowing other forward link references in the same cell to be followed in parallel.
12. A method for controlling parallel processing in a cell-based computation and communications system, wherein the system includes a network of cells, each cell being associated with instructions defining the behavior of the cell, the network of cells including a plurality of linking cells defining links within the cell network, each linking cell having a plurality of forward link references to respective forward linked cells in the network and a recession link reference to a respective recession linked cell in the network, the method comprising the steps of:
following at least some of the forward link references and at least some of the recession link references in the network of cells;
executing at least some of the instructions associated with the cells referenced by the forward link references and the recession link references which are followed;
providing a plurality of respective cells within the cell network which are capable of being activated through following forward link references by both (i) an evocation wherein a recession link reference associated with the respective cell is followed upon completion of the activities directed by the respective cell; and (ii) an invocation wherein a return address is provided in connection with activating the respective cell and the return address is followed upon completion of the activities directed by the respective cell;
following at least some of the forward link references in the network by evocation;
following at least some of the forward link references in the network by invocation;
engendering parallel processing in conjunction with following at least some of the forward link references; and
controlling convergence of the parallel processing in conjunction with following at least some of the recession link references.
13. The method of claim 12 further comprising the steps of:
associating conditions with at least some of the forward link references such that an associated forward link reference is followed only when the corresponding condition is satisfied, wherein the conditions include both exclusive conditions and non-exclusive conditions;
selectively following a forward link reference associated with an exclusive condition to the exclusion of following other forward link references in the same cell in parallel; and
selectively following a forward link reference associated with a non-exclusive condition while allowing other forward link references in the same cell to be followed in parallel.
14. A method for controlling parallel processing in a cell-based computation and communications system, wherein the system includes a network of cells, each cell being associated with instructions defining the behavior of the cell, the network of cells including a plurality of linking cells defining links within the cell network, each linking cell having a plurality of forward link references to respective forward linked cells in the network, the method comprising the steps of:
following at least some of the forward link references in the network of cells;
executing at least some of the instructions associated with the cells referenced by the forward link references which are followed;
engendering parallel processing in conjunction with following at least some of the forward link references in the linking cells;
associating conditions with at least some of the forward link references such that an associated forward link reference is followed only when the corresponding condition is satisfied, wherein the conditions include both exclusive conditions and non-exclusive conditions;
selectively following a forward link reference associated with an exclusive condition to the exclusion of following other forward link references in the same cell in parallel; and
selectively following a forward link reference associated with a non-exclusive condition while allowing other forward link references in the same cell to be followed in parallel.
Description
BACKGROUND OF THE INVENTION
1. Copyright Authorization
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by any one of the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
2. Field of the Invention
The field of the present invention relates in general to a system and method for structured computing and communications. More particularly, the field of the invention relates to structured computational cells linked together to form a highly flexible, dynamic computing and communications environment.
3. Background
Traditional notions of computer programming focus upon computer languages which are compiled to form executable code. These languages abstract away from the underlying machine language complexities, and allow a programmer to specify behavior in a more general manner. A compiler translates the program into a detailed machine specific implementation in the form of object code. In conventional procedural programming, the data and behavior of the program (i.e. the executable instructions) are distinct. In addition, these programs typically consist of sequential procedures or modes. As such these programs have a well-defined beginning, middle, and end, with little or no flexibility for the user to vary this predetermined sequence.
Procedural programming has been found inadequate in many respects. First, it does not provide a programmer with a paradigm for modeling real world objects and behavior. In particular, procedural programming is not readily adapted for sharing behavior among different computational units or objects. Second, the behavior of a procedural program at run time is typically determined by its data inputs. Since in the procedural model the data is distinct from the executable instructions, the level to which a user may interact with and modify the behavior of a program is limited. While it is possible to use procedural languages to write programs that are self-modifying, the complexity of the program may become unmanageable.
More recently, Object Oriented Programming (OOP) systems have been developed to overcome some of the limitations of procedural programming. OOP systems are based around objects that contain both data (the object's attributes) and executable code (the object's methods). While procedural languages tend to separate data from the processes that operate on it, OOP systems encapsulate the data that defines an object's attributes along with the methods that define the object's behavior. An object's methods may be accessed by sending a message to the object. For instance, a programmer may define a "Clock" object containing an attribute called "Current Time" (which is simply a variable containing the current time) and a method for displaying the time (which may be executable code that draws a clock on the screen showing the current time). The method might be activated by sending a "Display Time" message to the Clock. Once the Clock object is defined, the programmer may abstract away from its implementation. Rather than remembering how to calculate the current time and draw a clock on the screen, the programmer only needs to send a "Display Time" message to the Clock object.
OOP systems also provide a programmer with another method of abstraction called inheritance. A programmer may define a general class of objects having common attributes and methods. Subclasses may also be defined which inherit the attributes and methods from the parent class, but also add or modify attributes and methods. Thus, complex class hierarchies can be developed to define objects that share common attributes and behavior. To use an object from a particular class or subclass, the programmer simply instantiates an "instance" of the object. For example, a class may be defined called "Clock" with a method for calculating and displaying the current time. Subclasses of "Digital Clock" and "Analog Clock" may be defined that behave just like a Clock object, but display the current time differently--either in digital or analog form respectively. The programmer may use both digital and analog clocks in his program by declaring instances of each. Importantly, inheritance allows a programmer to add additional types of clocks without redefining how the current time is calculated. That ability may be inherited from the parent class--only additional or modified attributes and behavior need to be defined in the subclass.
Another aspect of many OOP systems, particularly OOP graphical user interfaces (GUIs), is that they support a "modeless" model, that is, one not tied to any particular predefined sequence of modes or procedures. These systems introduce the notion of "events." An event is any activity of interest, such as the press of a key on a keyboard or movement of a pointing device. The system responds to an event by sending a message to the currently executing application or object. This allows the sequence of events to be determined dynamically by a user's actions at run time.
While the OOP methodology provides for useful abstraction during development and more dynamic interaction at run time, current OOP systems have several limitations. First, application development in an object-oriented programming language, such as C++, brings with it a host of new complexities which the application developer must somehow manage. For instance, a C++ program of even modest complexities requires the creation and maintenance of immense class hierarchies--sophisticated data structures with complex interdependencies. Thus, while a programmer may encapsulate the complexities of an application in an object-oriented framework, the complexities of the framework itself must be managed. As object hierarchies grow, their own complexity obscures the simplicity of the OOP development model.
Second, the OOP model, while often adhered to during development, is rarely adhered to at run time. The attributes and methods of an object are spread across a number of classes and subclasses, and are not encapsulated at a single location in memory as the conceptual model would suggest. This limits the extent to which objects may be modified and restructured at run time. While OOP abstraction allows a programmer to readily define new objects during development, it is much more difficult for a user to do so at run time. This limitation on the ability to modify, add., and restructure objects at run time means that typical OOP systems cannot capture information and modify behavior based on a pattern of linkages and communicative interrelationships between objects. That is, the structure of the system cannot readily adapt and modify itself in response to interaction with a user or environment.
Neural network models suggest that this may be a major drawback to conventional OOP systems. Neural network models demonstrate that an immense amount of information and behavior may be defined based upon the way that neurons, or other simple computational units, are linked together into patterns of communicative interrelationships. Neural network models, however, tend to be primitive in nature and have failed to develop into a useful program development paradigm such as OOP.
What is needed is a development and computing system that is based upon structured, encapsulated computational units similar in some aspects to objects. Preferably, however, the system should provide the advantages of OOP systems without necessitating the creation and maintenance of complex class hierarchies. Further, such a system should preferably maintain its structure and encapsulation at run time, so that the system may be seamlessly modified based on interaction with a user or environment. The system should support dynamic modification of the internal behavior of the computational units, as well as the linkages and relationships among the units. The computational units should provide a basic structure that allows the system to be incrementally scaled to encompass different levels of complexity. Furthermore, it is preferred that the linkages among the basic computational units readily support massively parallel and distributed processing.
It is also desirable that such a computing system map across telecommunications networks. Generally, telecommunications systems of any sophistication are implemented as combinations of computers and interconnecting transmission lines. By design such networks are content-neutral--that is they do not discriminate based on the content of the messages they transport, provided the messages are supplied within defined constraints. Transmission lines are designed to be as nondistorting to the messages as possible, and nodes in the network are treated as "black boxes" whose internal operations--however diverse--are treated as irrelevant to the message traffic being handled by the network.
Intended to be content neutral, communications networks have accrued their own overwhelming complexities, quite apart from the arbitrary features of the messages passing through the system. Similar to procedural programming models, the data is isolated from the processes handling it. What is desired is a computing and communications system that allows the operation of a network and its components to be described in the same form as the content contained in the nodes and transported across the transmission lines of the network. In the ideal expansion of this concept, the entire telecommunications network assumes the capabilities of a general-purpose programmable computer serving its many users; although more limited expressions of the concept may provide for a mix of content-neutral transport of messages and programming of the network. What is desired is a computing and communications system that provides for the programming of the entire communications network in the same terms as the programming of individual computers (which may comprise nodes of the network).
Therefore, what is needed is the seamless integration of data, communications and procedure into a structured computing and communications environment. The behavior of such a system should not only account for data and procedures, but also the linkages and communicative relationships in the environment. Preferably, the system should be incrementally scalable, reuse tested atomic units of computation that are encapsulated and relocatable within the system, support highly parallel and distributed processing, and allow dynamic self-modification. In addition, the system should preferably support the dynamic acquisition of information not only through the acquisition of data and the modification of procedural code, but also through the encoding of information and behavior into the structure of the computing environment.
SUMMARY OF THE INVENTION
Aspects of the present invention provide a cell-based system for computation and communication. A cell associates executable code and data into a basic computational unit. A processor can traverse a cell and execute the instructions therein. Cells may be arranged in a network with each cell linked to other cells by paths or branches. In an exemplary embodiment, a processor branches to a cell by loading its program counter with the address of the cell. In other embodiments, a processor may send a packet of data across a communications network to activate remote processing in a cell. Various implementation technologies may be integrated into heterogeneous systems. Each cell may have a path selection section for evaluating conditional branches and causing branches to be followed. In an exemplary embodiment, multiple branches may be followed in parallel by initiating additional threads of execution on a single processor, or by causing additional processors to follow parallel branches. Each cell may also have a convergence section that handles processors and threads of execution that flow back to the original cell (called "recession"). The convergence section implements rules that control which, if any, processors or threads continue to execute upon recession as well as rules for handling any resulting values associated with the processors or threads. It is an advantage of the above aspects of the present invention that a basic atomic computational unit may be used to control multiprocessing. Both the linkages between the cells and the content of the cells determine the overall operation of the system.
Another aspect of the present invention provides for dynamic modification of a network of cells. The well-defined structure of a cell in the exemplary embodiment allows new cells to be constructed and added to the network by building a cell and adding a branch that leads to the new cell in the path selection section of an existing cell. In addition, cells may add executable code and/or data to other cells. In an exemplary embodiment, each cell is stored in a continuous portion of the virtual memory address space of a computer system. If the cells exceed the continuous address space available (i.e., such that if the cell expands it will overwrite a neighboring cell), the cell may be moved to another area in memory. Preferably, each cell keeps a list of the other cells that it references (referred to as forward links) as well as a list of the other cells that reference it (referred to as backward links). Preferably, these lists have a standard order and structure within the cells. These lists allow cell references to be dynamically modified and updated when cells are added, moved or deleted. If a cell should be required to move and has references to and/or from another cell, the cell may still be moved without disrupting continuity by leaving a reference to the new location at the old address (referred to as a "cell husk"). Once all the cells referencing the husk have been updated to reference the new cell location, the cell husk may be removed.
A system of locks regulates potentially conflicting references to a cell. There are several types of locks but all fall into three basic classes: 1) locks for execution, 2) locks for modification, and 3) locks for passive reference. In cases where a cell is being executed or modified by one or more threads of execution, updating of the cell is delayed (lock not granted) until all active references are completed. In cases where a cell has only passive references to it, updating the cell is allowed. Any updating may lead to a cell moving, which causes husking (the old cell is left in place and serves as a gateway to the new, moved cell). Husking is a mechanism whereby a cell's public address remains constant and in turn provides a lock-stepped gateway to a moveable operational cell (trueCell) so that processionists can always locate both the husk and the trueCell under all operational conditions.
Another aspect of the present invention imposes a hierarchical structure on a network of cells using a special branch called a "superbranch." In an exemplary embodiment, each cell may be referenced by a single superbranch from a "superspace" cell linked to the cell in a parent/child relationship. The cell being accessed is referred to as being in the immediate subspace of the superspace cell. The immediate subspace may also include other cells which have a sibling relationship to one another. The general subspace of a cell includes cells in its immediate subspace as well as the subspaces (if any) of those cells. A superbranch establishes a branch from the superspace cell to an immediate subspace cell, as well as a recession path back from the immediate subspace cell to the superspace cell. When a processor or thread of execution reaches the end of a cell without branching elsewhere, it normally recesses back to the superspace cell (i.e. it jumps to the convergence section of the superspace cell).
At each cell, multiple processors or threads of execution may diverge, following parallel superbranches to subspace cells. As execution in subspaces is completed, the processors or threads of execution may recess back up the cell hierarchy. Each cell may have a convergence section for receiving recessing processors and threads of execution. The convergence section determines which processors and threads of execution (as well as which results from computation in the subspace) may recess further up the cell hierarchy. The above described cell hierarchy provides for structured multiprocessing by linking basic computational modules.
In general, cells may include branches that do not have a corresponding recession path (simple branches) to any cell in the cell network. Thus, for example, a cell may branch to a cell in the subspace of a different cell. When that subspace cell completes execution, the processor or thread of execution will follow the recession path to the corresponding superspace cell and generally will not return to the cell from which it branched. Thus, a cell may activate other networks of cells as well as its own subspace. The other network of cells may be activated even though the current cell does not control divergence and convergence of processing within that cell network.
It is an advantage of the above aspects of the present invention that computation and communication may be controlled by linking modular structures. These computational modules may be activated in parallel over branches. Branching may entail any variety of methods for activating cells and includes causing a processor or thread of execution to jump to a specific address in the memory of a computer system or sending a signal or packet of data over a communications network to activate a remote cell. Such a system is readily adapted for highly parallel and distributed processing and dynamic self-modification. Information may be acquired within the system not only through the acquisition of data and the modification of executable code within the cells, but also through the encoding of information and behavior into the structure of links (i.e. branches and recession paths) that connect cells in the computing environment.
BRIEF DESCRIPTION OF THE DRAWINGS
These and other features and advantages of the present invention will become more apparent to those skilled in the art from the following detailed description in conjunction with the appended drawings in which:
FIG. 1 is a simplified block diagram illustrating a computer system which may be used in conjunction with a first embodiment of the present invention;
FIG. 2 is a simplified block diagram illustrating a computer network which may be used in conjunction with the first embodiment of the present invention;
FIG. 3 is a simplified block diagram showing the basic structure of a cell according to the first embodiment of the present invention;
FIGS. 4A-4E are simplified block diagrams illustrating evocation branching between cells according to the first embodiment;
FIGS. 5A-5B are simplified block diagrams illustrating invocation branching between cells according to the first embodiment;
FIGS. 6A-6B are simplified block diagrams illustrating coupling links between cells according to the first embodiment;
FIG. 7 illustrates symbols used to indicate different types of links used in the first embodiment including branches;
FIG. 8 is a simplified block diagram illustrating an exemplary assembly of cells (a "cell net") according to the first embodiment, having a hierarchical organization;
FIGS. 9A and 9B are block diagrams illustrating the structure of a cell according to the first embodiment;
FIGS. 10A and 10B are flow charts illustrating the process of branching into the entry zone of a cell according to the first embodiment;
FIG. 11 is a block diagram illustrating the relationship of a processionist, a processionist's current value and a cell according to the first embodiment;
FIGS. 12A-12B illustrate equivalent representations for an assembly of cells according to the first embodiment;
FIGS. 13A-13E are flow charts illustrating the operation of a branch evaluator according to the first embodiment;
FIG. 14 is a block diagram illustrating an exemplary network of cells using encore repetition units;
FIG. 15 is a graphical user interface of a cell builder utility showing the contents of one of the cells shown in FIG. 14;
FIG. 16 is a block diagram illustrating an exemplary network of cells according to the first embodiment; and
FIG. 17 is a block diagram illustrating clump frames according to the first embodiment.
DESCRIPTION
One aspect of the present invention provides a computing and communications system and method. The following description is presented to enable any person skilled in the art to make and use the invention. Descriptions of specific applications are provided only as examples. Various modifications to the preferred embodiment will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the invention. Thus, the present invention is not intended to be limited to the embodiment shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.
This description is presented in the following order:
I. Overview
1. Exemplary Computer and Network System
2. Computational Model (Cells, Paths, Processionists)
3. Basic Cell Structure (Header, Name Section, Entry Zone, Output Behavioral Section, Path Selection Section, Convergence Section, Exit Zone, Additional Components)
4. Cell Linkages (Evocation, Invocation, Coupling)
5. Current Value
6. Basic Multiprocessing Techniques (Locking, CellFrame, Stated Processionists)
7. Exemplary Cell Network: Dynamic Filing Tree
II. Detailed Cell Structure
1. Entry Zone and Activation Conditions
2. Output Behavioral Section and the Current Value (Evaluation Space, Current Value, Current Value in Progress, Lineal Code, Data Units)
3. Path Selection Section and Branch Evaluator
3.1 Overview of Branch Evaluator
3.2 Branch Evaluator Algorithm
3.3 Serialization/One Shot Jump (OSJ) Operation
4. Convergence and Result Forwarding Rules
4.1 Convergence/Recession Rules
4.2 Result Forwarding Rules
4.3 Combining Convergence and Forwarding Rules
5. Exit Zone and Repetition
5.1 Return from Invocation
5.2 Repetition Modules
5.3 Exemplary Cell Network: Encore Repetition Tree
5.4 Coupling
5.5 Exemplary Cell Network: Remote Agent
III. Specific Operation
1. Cell Building and Linking
2. Creating and Maintaining Network Continuity
3. Concurrent Cell Builders and Linkers & Network Self-Modification
4. Cell Locking
4.1 Protecting Cell State in a Multi-Threaded Environment
4.2 Locking and Unlocking Cells, Wait-Queuing and Dequeuing Lock Requests
4.3 Shareable and Unshareable Evoke and Invoke Locks
4.4 Additional Discussion of Convergence Locks
4.5 Lockable Cell Sections
5. Evaluation Space, Forwarding Handling, and I/O Model
5.1 Terminology: Forwarded Value Is Identical to Current Value (CV)
5.2 Terminology: Evaluation Space (ES)==CV and CVIP
5.3 Current Value (CV), Current Value In Progress (CVIP) and Evaluation Space (ES)
5.4 ES (CV and CVIP) Handling Rules
5.5 Discussion on Processionist's Frame for a Cell (cellFrame)
5.6 Convergence Rules and Their Role in CV Handling
5.7 Some Notes on Branch Evaluator Interaction with CV and One Shot Jump (OSJ)
5.8 Consumption of a CV and Resulting Resource Releasing
5.9 Additional Protracted Reference Discussion Regarding PROTRACT.sub.-- REF Locks, Storage Operations, and Resultant Husking, and Possible Ghosting
5.10 Considering ES In-Cell References Relative to Potential Husking, True Cell Creation, and Ghosting
5.11 Protracted References to Cells and Their Role in ES's
5.12 Input/Output Model As Related to CV and Output Section Elements
6. Partial Redundancy
7. Under-Specification & Deferred Resolution
8. Cloning and Inheritance
9. Exemplary Network Utilities
IV. Appendix A: Lineal Code and Lineal Translation Rules
V. Appendix B: The Cell Finder
VI. Appendix C: Notes on Implementation and Lineal Code of Branch Evaluator
I. Overview
1. Exemplary Computer and Network System
The first embodiment of the present invention provides a computing and communications system and method that may be used both in a computer system and across a communications network. FIG. 1 is a simplified block diagram illustrating a general purpose programmable computer system, generally indicated at 100, which may be used in conjunction with a first embodiment of the present invention. In the presently preferred embodiment, a Next.TM. computer containing a Motorola 68040 microprocessor, and running the NextStep operating system is used. Of course, a wide variety of computer systems may be used, and it should be understood that it is an advantage of the present invention that it may be used across different computer architectures. Examples of such computer systems include without limitation workstations or servers running Unix versions such as BSD 4.3 (or later) or System V Release 4.3 (or later), or other operating systems such as SunOS 4.1, DEC OSF/1, Open VMS, or Microsoft NT, and IBM compatible personal computers running Windows NT, O/S2 or Plan 9. FIG. 1 shows one of several common architectures for such a system. Referring to FIG. 1, such computer systems may include a central processing unit (CPU) 102 for executing instructions and performing calculations, a bus bridge 104 coupled to the CPU 102 by a local bus 106, a memory 108 for storing data and instructions coupled to the bus bridge 104 by memory bus 110, a high speed input/output (I/O) bus 112 coupled to the bus bridge 104, and I/O devices 114 coupled to the high speed I/O bus 112. As is known in the art, the various buses provide for communication among system components. The I/O devices 114 preferably include a manually operated keyboard and a mouse or other pointing device, sound recording devices, voice (with touch-tones) and data telephony for input, a CRT or other computer display monitor, speakers, head phones, voice (with touch-tones) and data telephony for output and a disk drive or other storage device for nonvolatile storage of data and program instructions. In addition, a local area network (LAN) adapter 116 is connected to the high speed I/O bus 112. The LAN adapter 116 allows computer system 100 to communicate with other devices over a LAN 118. Of course, other networking and communications connections may be supported through other adapters, modems, and the like.
The operating system typically controls the above identified components and provides a user interface. The user interface is preferably a graphical user interface which includes windows and menus that may be controlled by the keyboard or pointing device, plus voice sound and music recording and playback devices. Of course, as will be readily apparent to one of ordinary skill in the art, other computer systems and architectures are readily adapted for use with embodiments of the present invention.
FIG. 2 is a simplified block diagram illustrating a computer network, generally indicated at 200, which may be used in conjunction with a first embodiment of the present invention. For illustrative purposes, aspects of the first embodiment will be discussed within the context of LAN segments connected by a bridge or router. However, it should be understood that aspects of the present invention may find application in a virtually limitless number of networking arrangements and that it is an advantage of the present invention that it may be applied across different network architectures and protocols. Examples of networking configurations include without limitation Ethernet LANS, token ring LANS, wide area networks, and the internet. FIG. 2 illustrates an exemplary computer network which includes two Ethernet LAN segments 202a and 202b. The LAN segments 202a and 202b are connected to one another by bridge 204. Connected to each LAN segment are network nodes including workstations 206, 208 and 210, shared database servers 212 and 214, and laser printers 216. As is known in the art, other network nodes and other network segments may be added as well. The various network nodes 204-216 may communicate with each other across LAN segments 202 using the Ethernet protocol. Network nodes connected to LAN segment 202a may communicate with network nodes connected to LAN segment 202b across bridge 204 as is known in the art.
2. Computational Model (Cells, Paths, Processionists)
The exemplary computer system of FIG. 1 and the exemplary computer network of FIG. 2 will be used to illustrate the system and method of controlling computation and communication according to the first embodiment of the present invention. In order to appreciate aspects of the first embodiment, it is useful to approach the process of computation and communication from the perspective of process flow through a logical network of computational nodes rather than as a collection of objects or procedures. In order to understand embodiments of the present invention, it is desirable to describe a conceptual model that allows computation and communication of a wide variety of types using consistent terminology. Based upon this model, embodiments of the present invention are able to provide useful structures for the seamless integration of data, communications, and procedural computation. Computation and communication are based upon three components: cells, paths, and processionists. Cells are the basic structural elements of the system according to a first embodiment. In the first embodiment, cells may be implemented each as a contiguous area in the memory 108 of computer system 100 or as network nodes in computer network 200. One cell is connected to another cell by a path. A path may be a pointer or other reference from one cell to another in memory 108 of computer system. In a network such as that shown in FIG. 2 paths may be defined between different nodes in the network. If a node is designed to act as a single cell, a LAN address may be used to define a path to the node. If the node is a computer system whose memory hosts a network of cells, each cell may be referenced from another node using a path comprising a LAN address (to the node) and a symbolic reference (to the particular cell). A processionist is something capable of traversing a path. As processionists encounter cells, they are redirected to other paths or removed from the system. In addition, processionists may execute instructions in a cell, and carry values between cells.
Processionists may come in a variety of types. Processionists may be categorized based upon whether they can carry values between cells and/or execute instructions found in cells. The following are types of processionists that may be applicable in specific embodiments of the present invention:
1. A "Bare Processionist" is a processionist that merely moves from one cell to another without carrying a useful value. It simply causes the next cells along the path to be entered and activated. An example of a bare processionist would include a pulse on a LAN segment 202.
2. A "Simple Processionist" is a processionist that carries a useful value between cells. An example of a simple processionist would include signals on LAN segment 202 that represent binary data.
3. An "Operating Processionist" is a processionist capable of following or executing instructions it finds in a cell. An operating processionist may carry a value between cells.
4. A "Virtual Processionist" is a processionist that references different positions along a path or within cells, rather than physically moving along a path. A virtual processionist may use an offset counter or pointer to a position. As the counter or pointer is updated, the virtual processionist is said to traverse the path.
5. A "Virtual Operating Processionist" is a virtual processionist capable of following or executing instructions it finds in a cell. An example of a virtual operating processionist is CPU 102. In a multiprocessing system, multiple paths may be followed by different "threads" executed by CPU 102. In that case, each thread may be thought of as a virtual operating processionist. In a multiprocessing system with multiple CPUs, each CPU (or each thread for each CPU) may be a separate virtual operating processionist.
It should be noted that at a given cell, multiple paths may diverge from the cell. Therefore, a processionist must be able to create or recruit additional processionists. In a multiprocessing system, this means for instance that a single thread (acting as a virtual operating processionist) may create additional threads to follow additional paths from the cell. In addition, the type of path leading to a cell may be different from the type of path leading away from a cell. For instance, the path leading into a cell may be represented by a pointer in memory, while the path leading away from the cell may be a LAN address for a remote node in a network. Thus, processionists may have to transform as they pass between cells. For instance, a CPU (acting as a virtual operating processionist) may enter a cell, but the path leaving the cell to go to another cell may indicate a connection over a LAN segment. Therefore transduction must occur (at an appropriate adaptor) from one form of progression to another. Nevertheless, they can be regarded as a single processionist following a path among cells. It should be noted that with appropriate adaptors for transduction, biological or chemical signals, light or other physical signals may be included as part of a path between cells and may provide an interface between cells implemented in heterogenous technologies.
In computer system 100, the processionist is the CPU which traverses pointers in memory and executes code in the various cells (a virtual operating processionist). In computer network 200, the processionist may be a simple signal on the transmission lines, a packet of data, or a network agent capable of executing instructions at each node.
While it is possible to enumerate processionists, nodes and paths in many conventional systems, conventional systems are not designed based on these categorizations and therefore do not provide a consistent structure for describing and programming such a system. If computation and communication are modeled as processionists traversing paths from cell to cell, it can be seen that a consistent structure for cells provides the basis for a seamlessly integrated computing and communications environment. Further, by structuring the internal memory of a computer in a manner consistent with physical computer networks (that is by encapsulating cells in contiguous memory locations and connecting them by paths) parallel and distributed processing become seamless whether occurring within the computer system or across a physical transmission line in a computer network. In addition, information and behavior can be encoded in the pattern of paths connecting cells as well as within the cells themselves.
3. Basic Cell Structure (Header, Name Section, Entry Zone, Output Behavioral Section, Path Selection Section, Convergence Section, Exit Zone, Additional Components)
FIG. 3 is a simplified block diagram showing the basic structure of a cell, generally indicated at 300, according to embodiment, a cell is a present invention. In the first embodiment, a cell is a preferably contiguous block of memory in the virtual address space of computer system 100. As shown in FIG. 3, the cell of the first embodiment contains a plurality of cell segments including: a header 301, a name section 302, entry zone 304, output behavioral section 306, path selection section 308, convergence section 310, exit zone 312, and additional components 314. Each of these cell segments in the first embodiment comprises a block of virtual memory address space. Each of these sections will be described briefly below followed by a discussion of the various ways that cells may be linked to one another. The structure of the cell will then be described in greater detail.
The header 301 contains offsets or pointers to the other sections of the cell, plus a lock table and other state information. The name section 302 is used to store a name for the cell. The name is a piece of text that provides a default output or return value for a cell as well as a local identifier. In the first embodiment, names are not required to be unique, since identification ultimately relies on location in memory and the linkages between cells.
A cell is typically accessed by a branch from another cell. While branches may exist between any two cells, there is a special "superbranch" that creates a hierarchical structure among cells. Each cell has one superbranch leading to its entry zone from a "superspace" cell linked to the cell in a parent/child relationship. The cell 300 being referenced by the superbranch is referred to as being in the "subspace" of the superspace cell. The subspace may also include other cells which have a sibling relationship to one another as well as the subspaces of those cells. The immediate subspace of a cell contains only the direct children of the superspace cell, while the subspace generally also includes the children's subspaces. In addition to super branches, regular branches may be used to branch between any two cells. A cell may branch to: (1) a cell in its immediate subspace using a regular branch even though a superbranch also exists between the two cells (this is an example of an "inner branch" meaning it is a branch into the subspace); (2) a cell in its indirect subspace (this is also an example of an "inner branch"); (3) any other cell; or (4) the current cell itself in which case the processionist jumps back to the entry zone of the current cell. (3 and 4 are "outer branches" meaning it is a branch to a cell outside of the subspace.) The arrangement and linking of cells will be described further below.
A cell 300 is accessed when another cell sends a processionist along a path to entry zone 304. First the cell's lock is consulted which may result in waiting. The processionist then enters the cell at entry zone 304. In the first embodiment, this means that the preceding cell will load the program counter of CPU 102 with the address of entry zone 304 through a branch instruction. CPU 102 will then start executing instructions for the cell 300 at the first address of entry zone 304. The entry zone 304 contains conditions that may be tested regarding activation of the cell 300. These conditions may include modulators of the cell, activation rules, and inhibitory indications. Each of these conditions will be discussed further below.
In the first embodiment, after the code in the entry zone 304 is executed, the processionist (which is a thread of execution for CPU 102) then moves on to the output behavioral section 306. The output behavioral section 306 contains executable code for outputting values from the cell and performing other operations. The output behavioral section 306 may be blank for cells without output or it may include extensive code for generating complex output. By isolating output related code from other sections, the behavior of a cell may be modified at run time ("on the fly") simply by overwriting this section with new instructions and contents. The output behavioral section 306 also generates and/or modifies a data value carried by the processionist (referred to as the "current value") as it passes through the cell. See Section I.5 below. The current value may be returned with the processionist when it exits the cell.
After the output behavioral section has been completed, the processionist executes instructions in the path selection section 308. The path selection section 308 contains executable code and conditions for determining which paths emanating from cell 300 should be followed by the processionist. As will be described further below, there may be paths leading to cells in the immediate subspace via a special path called a superbranch. This superbranch establishes the parent/child relationship between the cells. Other types of branches may exist between cells whether or not the cells have a superspace/subspace relationship. A special module of code called the branch evaluator is used to determine which paths to follow from among the extant set of super and simple branches. (The branch evaluator may be reentrant code shared by many cells within the same address space.) The branch evaluator implements a branch selection rule that regulates whether processionists move from one cell to another within the system. The actual conditions that are evaluated and addresses for each referenced cell are contained in a branch table 309 within the cell. The branch table 309 makes up part of the cell's link table 311 which contains the addresses of all the other cells referenced by the current cell (forward links) and the addresses of all the other cells that reference the current cell (backward links). Forward links are used when a processionist branches from the current cell and backward links are used for memory management (e.g. updating the addresses used by other cells to reference the current cell in the event the current cell moves or is deleted). The addresses in the link table 311 may be virtual memory addresses for cells in the same address space or network addresses for cells on other nodes in a network or symbolic references.
The path selection section 308 contains a mechanism for dispatching processionists on the appropriate paths. In the first embodiment, this may be accomplished by requesting new threads of execution from CPU 102 to follow additional paths (the existing thread would follow one of the paths itself). The appropriate address for the branch may be loaded into the program counter of CPU 102 for the appropriate thread. For cells on other nodes in a network, the paths may be followed by sending a packet or other signal to the appropriate network address for the cell. In this way, cells branched to by cell 300 are activated in parallel using multiprocessing techniques. For systems that do not support multiprocessing, the selected paths can in some circumstances be taken up serially, with the order preferably determined based on the order of entries in forward branch table 309.
After processionists are dispatched along the selected paths from cell 300, the cell becomes dormant (that is, none of the executable code in the cell 300 is executed) until another processionist enters the cell or a processionist returns ("recesses") from the subspace to convergence section 310 (if no dispatching occurs then the processionist jumps directly to the exit zone 312, retaining its current value). The convergence section 310 contains rules for handling values returned from the various paths traversed in the subspace of cell 300. Based on conditions stored within the convergence section 310, some, all or none of the values returned by the paths may be forwarded by cell 310 back to its superspace cell. Locking mechanisms described in detail below may be used to prevent other processionists from entering the cell or specific sections of the cell as necessary to provide for controlled convergence of processionists from the subspace, and generally to preserve state to the extent a cell may not be fully reentrant.
When the conditions in the convergence section 310 are met, exit zone 312 is activated. The exit zone 312 contains code that should be executed and other conditions that should be evaluated before the processionist exits the cell. Among other things, the exit zone 312 may contain repetition control which causes the output behavioral section 306 (and what follows) to be repeated under a certain condition or a certain number of times before the processionist is allowed to leave the cell. Repetition is accomplished by sending a processionist back to the start of the output behavioral section 306. This may be accomplished in the first embodiment by using a conditional branch statement in exit zone 312. When the exit zone is entered by the processionist, a current value has already been set by the output behavioral section as modified and/or replaced by the subspace and any subsequent convergence and the exit zone performs no further modification.
The address of the superspace cell may be located in link table 311. While the address of the superspace cell's convergence section could be stored directly in the link table, preferably cells are referenced consistently by using the starting address of the cell. Offsets and/or pointers to specific sections may be retrieved from a standard location at the beginning of the cell and used to access a desired section of the cell. Indirect addressing, which is supported by standard programming languages such as "C" and "C++," may be used for this purpose. Thus, to send a processionist to the convergence section of the superspace cell, the cell address ("starting address") of the superspace cell is retrieved from the link table 311. A request is then made to lock the cell for convergence using a "lockCellFor" convergence function. In certain circumstances when a cell has been moved, the starting address of the cell as stored in link table 311 will not reflect the address of the cell contents (the "trueCell" address). Rather a "cell husk" remains in the previous location and references the trueCell address. The trueCell address is returned by the cell or cell husk in response to the "lockCellFor" function. An appropriate offset is then retrieved from a table 301 in the header of the superspace cell. The offset is then added to the trueCell address to provide the address of the superspace cell's convergence section
The additional components 314 provides storage for various tables, conditions, and data used by the sections described above. This may include, among other things, the link table 311 used by path selection section 308 and exit zone 312, storage for conditional parameters, and the actual output contents of the output behavioral section 306, plus pre-allocated extra space for the cell to grow.
It should be noted that excepting the cell header, the actual physical ordering of each section is irrelevant, whereas the execution order of active sections is crucial. Any physical ordering of sections will work so long as the sequential section-to-section execution transitions (jumps or branches) are properly constructed. For instance, in the first embodiment, the output behavioral section 306 is actually located just prior to the free storage area 318 in contiguous memory. This allows the output behavioral section 306 and free storage area 318 to be allocated and deallocated together for certain memory management techniques discussed below. See Section III.2 on husking and dehusking.
The detailed structure and implementation of a cell will be described further below. It will be noted, however, that a cell is structured such that instructions and conditions affecting entry, output behavior, branching, convergence, and exit are grouped into separate sections. The behavior of a cell may be modified simply by changing the executable code or conditions in the appropriate section. The cell structure also allows cells to be linked together through the path selection section 308 linking to the entry zone 304 of a subspace cell (via a superbranch) or of any cell (via an ordinary branch), and linking the exit zone 312 (via a recession path) to the convergence section 310 of the superspace cell or (via a coupling link) to the entry zone 304 of a co-spatial cell (i.e, one that is a subspace of the same superspace cell as the current cell). This provides a consistent structure for computation and communication and allows behavior to be controlled by the executable code and conditions in the cells as well as the linkages between cells.
4. Cell Linkages (Evocation, Invocation, Coupling)
In the first embodiment, cells may be linked using a variety of mechanisms. These cell linkages allow the paths available for process flow to be dynamically altered in a structured manner which provides a significant advantage over typical conventional systems. The first embodiment uses two major distinct methods for linking cells. The first method, linkage for "evocation" creates explicit branches that are defined between cells based on entries in the branch table 309 contained within link table 311 FIG. 4A illustrates cells 402 and 404 which have an explicit branch between the cells (here a "superbranch"). When a processionist reaches the path selection section 408 of cell 400, the entries in the branch table are evaluated. One of these branch entries contains the address of cell 420. If any conditions that may be imposed for this branch are met, cell 400 will send a processionist to entry zone 424 of cell 420 and thereby "evoke" cell 420 as indicated by arrow 416 in FIG. 4A. This is accomplished in the first embodiment by locking the cell (a husk or singular cell) for evoking, receiving its trueCell or singular cell address back, and then loading the program counter of CPU 102 with the address of entry zone 424 of cell 420. Unlike conventional procedure calls (such as that implemented by a conventional "JSR" assembly language instruction), the evocation branches in the first embodiment are stackless. This means that the address of cell 400 is not stored when the branch is made, and cell 420 has no record of which cell is responsible for evoking it among all those cells which may have branches to it potentially capable of evocation. For paths that cross communications networks, the address stored in forward branch table 409 is a network address, and/or symbolic link and the target cell is evoked by sending a packet or signal to the appropriate network address.
Cell 420 will also contain a corresponding link from the exit zone 432 of cell 420 to the convergence section 410 of cell 400. This link is called a "recession path." Once a processionist crosses the exit zone 432 of cell 420, it will look up the address of superspace cell 400 in the link table 431 by locking the superspace cell (a husk or singular cell) for convergence, receiving its trueCell or singular cell address back, and then recess to convergence section 410.
Forward links are links leading away from the current cell that may be followed by a processionist. Backward links are merely addresses of cells that reference the current cell and are used for maintaining continuity if the current cell is moved or deleted. As discussed previously, the address of cell 400 (which is retrieved from link table 431) is used to indirectly retrieve via cell-locking an offset or pointer from the header 401 of cell 400 to determine the address of the convergence section 410 of cell 400. The processionist will then jump to the convergence section 410 by loading the program counter of CPU 102 with the appropriate address as indicated by arrow 436 in FIG. 4A.
If such a corresponding recession path exists, the combination of the branch 416 and recession path 436 is referred to as a "superbranch", which shall be designated herein using a bidirectional arrow 440 connecting cells in opposing directions as shown in FIG. 4B with a solid arrowhead pointing at the evoked cell, and a hollow arrowhead pointing at the evoking cell (to represent the corresponding recession path). The system of the first embodiment is preferably structured such that exactly one superspace branch leads to the entry zone of a given cell (with a single corresponding recession path), although multiple superspace branches may emanate from the path selection section of a cell (to those cells called its subspaces).
Evoking branches do not, however, require a corresponding recession path in the first embodiment. Where an evoking branch links two cells without a corresponding recession path, a single arrow with a dot on either side 450 will be used to designate the link as shown in FIG. 4C. This will be referred to as a "simple branch". In this case, the evoked cell will execute, but when the exit zone of the evoked cell is reached, it will not recess to the evoking cell, but may recess to another cell through a recession path (which is part of a different superbranch). While only one super branch leads to the entry zone of a cell in the first embodiment (and only one recession path leads away from the exit zone), multiple simple branches may lead to the entry zone of a cell.
FIGS. 4D and 4E illustrate the processes of branching and convergence in additional detail. FIG. 4D shows the steps involved in following a branch (such as branch 416) in the first embodiment. As shown at step 452, the processionist first requests a cell lock for evocation from the subspace cell 420. The subspace cell 420 (or cell husk at that location) then returns the trueCell address--the actual address of the cell contents (step 454). The processionist then retrieves an offset from header 421 that indicates the offset to the entry zone (step 456). This offset is added to the trueCell address and loaded into the processionist's program counter, thus causing the processionist to jump to the entry zone 424 of the subspace cell 420 (step 458).
FIG. 4E shows the steps involved in converging back to a cell (such as along recession path 436). As shown at step 460, the processionist first requests a cell lock for convergence from the superspace cell 400. The superspace cell 400 (or cell husk at that location) then returns the trueCell address--the actual address of the cell contents (step 462). The processionist then retrieves an offset from header 401 that indicates the offset to the convergence section (step 464). This offset is added to the trueCell address and loaded into the processionist's program counter, thus causing the processionist to jump to the convergence section 410 of the superspace cell 400.
Cells may also be linked in the first embodiment through implicit links, which subsequently may be followed to "invoke" another cell. FIG. 5A shows an invoking cell 500 and an invoked cell 520. The implicit invocation link 516 is used in the output behavioral section 506 of the invoking cell 500 when it is desirable to use the behavior or output of the invoked cell 520. This is similar to a procedure call in conventional programming. Through invocation, a cell can use the functionality of other cells as part of its behavior, can effectively retrieve their contents, or can store into them or their subspace. The invoking cell can invoke any number of cells, and may invoke the same cell more than once in different parts of the output behavioral section. Unlike evocation, a return address is saved. Certain state information (such as the values of registers for CPU 102) may also be preserved (preferably in the processionist stack). The return address and related state information may be stored on a system stack using a push operation as with conventional procedure calls or it may be stored in the storage section 534 of the invoked cell 520 (as indicated at 535). Once the invoked cell 520 completes execution, the return address is popped off the system stack and used to return to the output behavioral section 506 of the invoking cell 500 (as indicated by arrow 536). Execution resumes at the next address in the output behavioral section 506 of the invoking cell 500. Like an evoked cell, the invoked cell 520 executes its entry zone 414 (although certain access control is skipped), output behavioral section 526, path selection section 528 (and contingent on subsequent events), convergence section 530, and exit zone 532. This may in turn involve further evocations and invocations of other cells. However invoked cells have their last output suppressed. All calculations are performed, so a proper value can be returned to the invoking cell. However, the output of a cell's value is suppressed, so an invoking cell 500 can use the invoked cell's functionality or contents without causing its output as well. When a cell invokes another cell, it will be designated herein using an arrow with two lines 540 as shown in FIG. 5B with a large arrowhead pointing at the invoked cell, and a small arrowhead pointing at the invoking cell (which represents the return path to the invoking cell).
Yet another type of link used in the first embodiment of the present invention is referred to as "coupling". Coupling allows for sibling cells in a subspace to be executed serially rather than in parallel. As shown in FIG. 6, a superspace cell 600 may evoke multiple subspace cells 620, 640 and 660. These subspace cells are said to have a sibling relationship. Ordinarily each subspace cell 620, 640 and 660 may be executed by a separate thread or processing unit in parallel. Alternatively coupling may be used to designate a serial order for executing the cells. The subspace cells are ordered according to the way they are listed in the branch table of superspace cell 600. Only after the first subspace cell 620 completes execution is the processionist sent to the second subspace cell 640. This process will continue for subsequent coupled cells (640 and 660) until all of the coupled subspace cells have been executed. The exit zone 672 of the last subspace cell 660 will then return to the convergence section 610 of superspace cell 600. Alternatively, only the first two cells 620 and 640 may be coupled. A processionist would not be sent to cell 640 until cell 620 had completed executing. The third cell 660 might be executed in parallel. This process of coupling can thus be used to serialize execution of sibling cells when a certain deterministic order of execution is required (or when multiprocessing is unavailable).
Coupling shall be designated herein using a double lined branch with one or two dots on either side as shown at 680 and 685 in FIG. 6B. A coupling branch with single dots 680 will represent tightly coupled cells. Tightly coupled cells are cells that are specified to remain coupled at all times. The principle purpose of tight coupling is to direct a recessing processionist to a sibling cell rather than having it recess directly to the superspace cell. A coupling branch with two dots on either side 685 represents loosely coupled cells. Cells are loosely coupled if the coupling may be temporarily uncoupled such that the coupled cells may be evoked concurrently rather than serially when extra processors, threads, or other processionists are available. Loose coupling is used primarily for operations that may be processed either serially or in parallel without a significant difference in the results obtained.
A number of basic computational cells may be linked together as described above. A group of cells linked together is referred to as a cell network. When a processionist moves through a cell network, it may arrive at a path selection section of a cell, from which multiple processionists are dispatched in parallel to execute multiple subspace cells, or more generally, multiple cells, some of which may be subspace cells. This process is called "divergence." When a processionist reaches the end of a path (there are no branches to pursue in a cell's branch table), the processionist proceeds to the exit zone and recesses to the convergence section of its superspace cell (assuming no coupling). Some forms of the convergence section of a cell only allows certain processionists to pass through to the next superspace cell (hierarchically "above"). When one or more processionists recess to a convergence section, the process is referred to as "convergence". (More generally, the idea of convergence encompasses also what is referred to as "uncontrolled convergence" which is the arrival of multiple processionists at a node in the cellular network, which is the entry zone of a particular cell.) Typically, processionists diverge (essentially fanning out) through a cell network causing parallel computation to occur in subspace cells. Where the computation is step-dependent, coupling may be used for serialization. As execution in subspaces is completed, the processionists then recess and converge back up the hierarchy. While processionists often converge at the initiating superspace cell (where a desired result is typically compiled), processionists are not required, and are not guaranteed, to recess and converge at the initiating superspace cell. This result depends on design of the network and conditions.
As described above, a cell may include simple branches to any cells including those outside of the immediate subspace of the cell. Unlike superbranches these simple branches do not include a corresponding recession path between the linked cells. A processionist following a simple branch may not recess to the evoking cell. When a simple branch is not expected to lead to recession to the cell where the evoking processionist originated, it is referred to as a wild branch. It may be difficult to determine whether a simple branch will lead to such recession, so a simple branch is presumed to be wild unless eventual recession is apparent. The default type for a simple branch is wild unless a programmer or software tool performing network analysis determines otherwise. Wild branches shall be designated with an arrow with a single line (like a simple branch), but with two pairs of dots on either side instead of a single pair (see 704 in FIG. 7). In addition, super branches that lead to cells having wild branches shall be designated stray super branches, since there may be no recession to the evoking cell if the wild branch is followed thence by a processionist. A stray super branch shall be designated using a super branch bidirectional arrow with a diamond in the middle (see 708 in FIG. 7). The cell to which it points is called a "stray subspace cell."
FIG. 7 summarizes the graphical symbols which will be used to represent the various types of branches for the first embodiment. These graphical symbols include simple branches 702, wild (simple) branches 704, super branches 706, stray super branches 708, invocation branches 710, tight coupling links 712, and loose coupling links 714.
The various branches described above allow the cells of the first embodiment to be linked together to perform computation. The superspace/subspace relationship among evoked cells in a network provides a convenient facility for controlling multiprocessing through divergence and convergence of processionists. To a large extent, the behavior of the system of the first embodiment is determined by the arrangement of cells within the above described network of cells as well as the particular types of branches linking the cells. These techniques allow the behavior of the system to be programmed into the system based on the interconnection of cells as well as the executable code contained within the cells.
5. Current Value
The behavior of the system of the first embodiment is also determined by the contents of the output behavioral section of individual cells and the effect it has upon values carried by a processionist through a cell. In the first embodiment, processionists may carry values between cells. Each processionist may be associated with a pointer to a location in memory which holds a processionist's data value. In the first embodiment, for each thread of execution (which is a virtual operating processionist) an address register may be designated for holding a pointer to the processionist's data value.
The value that is carried by a processionist as it passes through the output behavioral section of a cell is called the current value. The processionist enters the output behavioral section with an associated pointer to its current value, which is forwarded along with the processionist from the cell that evoked or invoked the current cell. As the processionist passes through the output behavioral section, the current value may be modified or replaced. At specific points, the current value may also be copied to other memory locations or output devices.
As will be discussed in further detail below, the output behavioral section may include any variety of functional instructions such as invocations of other cells, explicit executable instructions, lineal code to variably build or modify other cells based on run-time information, or references to executable programs of any scope. In this way, the cell structure can be used to encapsulate and organize conventional computational modules in a new way. Such executable code may be stored within the output behavioral section of a single cell, or it may be distributed across several cells in cases where additional advantages can be realized from the cell-based computational system of the first embodiment.
After the current value has been modified or retained by the output behavioral section, it will be forwarded along any branches that are selected by the path selection section. The evocation branches to be considered by the path selection section are listed in the branch table along with conditions that determine when the paths should be followed. The branch table is part of the link table and contains a subset of the forward links in the link table. Invocation and coupling links are not contained in the branch table, but are contained in the link table. Where multiple paths are followed, additional processionists (threads of execution in the first embodiment) must be generated along with copies of the current value (or in cases where the size of the current value exceeds a tuneable threshold, a pointer to the current value). These values are then forwarded along the paths emanating from a cell.
Similarly, values are forwarded back from subspace cells to the convergence section. The convergence section evaluates convergence rules (discussed further below) to determine which, if any, values returned from subspace cells should be forwarded back through the exit zone of the current cell. The selected value(s) is then forwarded back to the superspace cell along the recession path linking the current cell to its superspace cell.
6. Basic Multiprocessing Techniques
As multiple processionists (multiple threads of execution) traverse the network of cells through evocation and invocation, locking techniques must be used to prevent conflicting references to a cell. A system of locks is used to regulate cell references. When a processionist references a cell, it requests a lock for the specific activity it will be performing. There are three classes of locks in the first embodiment: 1. locks for execution (e.g., when a processionist is evoking, invoking or converging to a cell); 2. locks for modification (e.g, when a processionist wishes to store or modify information in a cell); and 3. locks for passive references (e.g, when a processionist reads data from a cell without modifying it). A lock table in the header 301 of the cell keeps track of which locks are in place and which locks can be granted.
Generally a cell can be shared by multiple processionists for evocation. Evocation is stackless and preferably allows cells to be shared to the extent possible. However, some state information may be maintained for the cell and accessible by a processionist that recesses back to the cell. This state information is stored in a "cellFrame" associated with the cell, and can be accessed by any processionists that are part of the same session (in the same "processionist group"). Processionists from other sessions (e.g, generated by another user who is concurrently using the same cell network) would maintain separate cellFrames and are not considered to be in the same processionist group. By maintaining a shared cellFrame with state information, any processionist in the same group that converges back from the subspace can continue executing the cell using the state information stored in the cellFrame. Essentially processionists can drop off cellFrames in a group resource linked list when they leave a cell and pick them up for continued execution when they recess to a cell if necessary. Alternately, the cellFrames can be associated with specific processionists. In such cases, however, the cellFrame is not available to other processionists converging back to the cell. Therefore, the cell has to wait for the specific processionist with the cellFrame to converge before execution could continue.
In contrast to evocation, invocation causes state information to be preserved on a system stack associated with a particular processionist. Each processionist maintains a variable that keeps track of the invocation level (i.e, the number of times state information has been pushed on the stack). When the invocation level is greater than zero (i.e, at least one invocation has been performed), the processionists is referred to as a "stated processionist." This means that the specific stated processionist must be returned from the invocation so the state can be restored from the stack. When a cell is invoked, multiple processionists may be initiated and caused to branch from the cell. Multiple processionists may then converge back to the cell. However, the invocation cannot be completed until the stated processionist converges. The stated processionist must be the processionist that is returned from the invoked cell, so state can be restored from its stack. For this reason, a stated processionist will not be sent on a wild branch (because by definition, it would not be expected to converge back from the wild branch).
In addition to the above techniques, processionist-specific information is maintained by a context block that is associated with each processionist in memory (e.g. via a dedicated address register). Among the processionist-specific information stored in the context block is: 1) a pointer to the current cellFrame being used by the processionist; 2) references to the current value and related data; and 3) routing information for input and output devices.
7. Exemplary Cell Network: Dynamic Filing Tree
FIG. 8 illustrates a cell network according to the system of the first embodiment. The cell network, indicated generally at 800, implements a dynamic filing tree. This dynamic filing tree is a simple network of cells used to sort and store strings in itself based on the first letter of the string. While this is a relatively straightforward example, it illustrates several aspects of the first embodiment which have been described above. The dynamic filing tree may be initiated by invoking cell 802 (labeled "DFT") and forwarding a string to be stored in the dynamic filing tree. The string to be stored is associated with the processionist (the thread of execution that traverses cell 802) as the current value using an address pointer to a location in memory that contains the string.
The subspace of the DFT cell 802 contains a cell for each letter of the alphabet (cells 810-835, labeled A-Z in FIG. 8) as well as an additional cell 836 (labeled "Else" in FIG. 8) for strings that do not begin with a letter. Each subspace cell 810-836 is linked with the superspace DFT cell 802 by a super branch 840-866 from the super space DFT cell 802 to the respective subspace cell 810-836. Thus this small network (or "cell assembly") has a hierarchical (or "tree") structure.
The branch table in DFT cell 802 contains the addresses of each subspace cell 810-840 as well as an associated condition for each branch. In this example, the condition for each branch would be that the first letter of the current value (the string associated with the processionist) be equal to the letter for the respective cell. For instance, if the first letter of the string was an "A", branch 842 would be taken to the cell 810 (labeled "A"). Each of the conditions for cells 810-835 (A-Z) would be marked as an exclusive contingency, which means that if a condition is met and the respective branch is taken, no other conditions will be evaluated and no other branches will be taken. Thus, the first branch whose condition is satisfied will be the only branch followed. The corresponding cell 810-835 will be evoked and the string value will be forwarded to the evoked cell along with the processionist. The final entry in the branch table for cell 802 contains the address of cell 836 and the branch is unconditional (which means the branch 866 will always be taken unless one of the exclusive branches to cell 810-835 is taken first). In this way, DFT cell 802 sorts strings based on their first letter.
Each cell 810-835 (A-Z) is initially associated with a cell (870-874) in its subspace. A string may be stored in the dynamic filing tree by placing it in the output behavioral section of a cell (870-874) in the subspace of the cell (810-835) for the respective letter of the alphabet.
This storage operation will be explained with reference to cell 810 (labelled "A") with the assumption that a processionist has entered cell 810 pursuant to a condition on branch 840 with an associated string that begins with the letter "A". The condition for the branch to the first cell 876 (labeled "A[1]") in the branch table of cell 810 will be unconditional so branch 880 will be followed. The branch 880 will then be taken which will cause cell 876 to be evoked. Then a condition for the branch 880 will be modified by an instruction in the output behavioral section of cell 876 to provide that the condition thereafter requires matching with the contents of cell 876, so it will only be taken in the future if the current value is equal to the string that has been stored here upon completion of the present storage operation to the DFT. This condition will be marked as exclusive. A new empty cell 870 will be added to the subspace of cell 810 to be used for future storage, since cell 876 will be used to store the current string. A pointer to cell 882 is returned to cell 810 when the processionist recesses along super branch 880. This pointer will be returned to DFT cell 802 as the processionist recesses along super branch 840. The pointer is returned as the answer to the invocation and then used to store the current value to the output behavioral section 882 of cell 876.
As other strings are forwarded to cell 810, new values will be stored in the preallocated cells 870 and new empty cells will be added for storage. If a string matches a previously stored string, a new cell will not be allocated. Rather a pointer to the previously stored value will be returned. This occurs since the string will match an exclusive condition in the branch table of cell 810 for an existing cell 876 before it reaches the unconditional branch to an empty cell 870.
While a similar dynamic filing tree could be implemented using conventional procedural techniques, advantages are realized by using techniques according to the first embodiment. For instance, since the cells are structured in a well-defined manner, the cell can be dynamically altered in simple ways to greatly modify behavior and accomplish new tasks. For instance, if the strings to be stored are a person's first and last name, the dynamic filing tree may be easily modified to file the string alphabetically under both the first and the last name. The conditions in the branch table of DFT cell 802 would simply be modified to follow a branch if either the first or last name started with the respective letter. For each name, two processionists would diverge from the path selection section of DFT cell 802, and two pointers would be returned to the convergence section of DFT cell 802 and thence to the invoker as a vector. The storage operations based upon the first name and last name would thus occur in parallel using multiprocessing techniques. Thus, the system of the first embodiment can readily support dynamic self-modification and parallel processing.
The dynamic filing tree of FIG. 8 may also use parallel processing techniques according to the first embodiment to handle contingencies without the usual problem that exception handling excludes or diverts the normal completion of procedures. For instance, if a string that does not start with a letter is detected, cell 836 (labeled "Else") may be evoked. The cell 836 may provide desired processing and return a value by recessing back along branch 866 to DFT cell 802. In addition, cell 836 may forward a processionist along a wild branch 890 to another cell assembly 895 for handling contingencies. If DFT cell 802 was invoked, the processionist at cell 836 will be a stated processionist (with state information maintained on its associated stack), and it will not be sent along wild branch 890. Rather, a new processionist will be initiated to follow wild branch 890, and the stated processionist will recess so the stored state can be restored. The new processionist sent to cell assembly 895 will not recess back to the DFT cell 802, but rather will initiate separate processing. For instance, cell assembly 895 may output a message to a system administrator and then recess to a superspace cell unrelated to the DFT. The wild branch 890 may be a branch within the same virtual memory address space as cell 836, or it could be a branch across transmission lines of a network to a cell network on remote equipment. It is an advantage of the system of the first embodiment that the structure and basic operation of cell 836 is the same in either event--the address in the branch table of cell 836 for wild branch 890 is the only thing that changes. Thus, linking computational modules (cells) within a memory space and across a communications network may be accomplished with a consistent structure.
II. Detailed Cell Structure
The operation and structure of a cell according to the first embodiment will now be described in further detail. FIGS. 9A and 9B illustrate the detailed structure of a cell, generally indicated at 900a and 900b (collectively "cell 900"), according to the first embodiment of the present invention. It will be readily understood by those of ordinary skill in the art that this structure is arranged in memory 108 as part of the virtual address space of computer system 100. Referring to FIGS. 9A and 9B, the elements of cell 900 may be classified as active elements 900a (set forth in FIG. 9A) and passive elements 900b (set forth in FIG. 9B). The active elements include executable code which defines the actions taken by a processionist as it passes through the cell. The active elements include the entry zone 906, the output behavioral section 908, the path selection section 910, the convergence section 912, and the exit zone 914. The passive elements include conditions, variables and other data used by the active elements to guide a processionist through the cell by evaluating branch conditions, generating output, and the like. The passive elements include cell header 915, name section 916 and additional components 918. While the specific structure of a cell may vary among embodiments, what is desired is a set of active elements that may be broadly and consistently applied throughout a system (although it will be understood that some cells, while consistently structured, may be scaled down and not include every element) and yet be robust enough to incorporate all of the behavior necessary for integration into the system. What is also desired is a well-defined structure for both active and passive elements so their contents may be dynamically altered to modify a cell's behavior.
The structure and operation of each element of cell 900 will now be described. The active elements will be described in the order that they would be encountered by a processionist passing through the cell. The passive elements will be described in conjunction with the active elements that use them.
1. Entry Zone and Activation Conditions
A cell is referenced by using its cell address (i.e, lowest numbered location in the virtual memory location of this cell). At a standard location relative to this starting address is a table of offsets 931 in the header 915. The offsets 931 can be used to determine the address of each entry point and section of the cell 900. Locks in lock table 930 are checked to determine whether a processionist can enter the cell. If a lock state that precludes evoking exists, branching to the cell will be suspended until the lock is cleared. The locks may include whole cell locks which prevent processionists from entering the cell and fine-grain convergence locks which protect state information related to certain types of convergence and recession. These locks are described in detail in Section III.4 below with reference to Tables 4 and 5.
In the first embodiment, a processionist effectively enters the cell when the program counter of CPU 102 is loaded with an appropriate address within the cell. The CPU 102 then begins executing active elements within the cell. The address at which a cell's execution begins depends upon whether the cell is being evoked or invoked. The entry zone 906 has two entry addresses, an evocation reception address 920 and an invocation reception address 922.
The entry zone 906 also includes a peculiarities section 924 which may include activation conditions and states 926 for determining whether a processionist evoking the cell should be able to activate the cell as well as repetition rules and initialization 962. The activation conditions 926 may be evaluated to determine whether an evoking processionist may activate the cell (i.e, proceed past this section). Several types of activation conditions may be evaluated, including threshold conditions, modulators, and latency periods. Threshold conditions count the number of processionists that enter the cell. The processionists are extinguished (that is each thread of execution is terminated) or forced to exit the cell (without termination) until a certain number, n, has been reached. The nth processionist is then allowed to proceed in the cell. Threshold conditions may also count based upon quantum numbers carried by processionists in their current value or may only allow processionists to enter the cell if their current value meets a condition (for instance, its current value is a number greater than some threshold number). A modulator is essentially an infinite threshold condition that extinguishes processionists (or forces them to exit the cell) as long as the modulator is on. Whether the modulator is on may be determined by a binary switch in the activation conditions 926 or by reference to an external condition (i.e, system clock). Latency periods are conditions that regulate access to the cell based upon a period of time since the cell was last activated by a processionist.
Unlike activation conditions, cell locks apply to both evoking and invoking processionists. Before a processionist enters the cell, it may place a lock on the cell which prevents other processionists from entering the cell to avoid conflicts. Alternatively, the processionist may place a conditional lock on the cell, so only certain processionists can enter the cell. The locks are typically removed when the processionist branches from the cell. Prior to entering the cell, a processionist may place its lock or conditional lock in lock table 930 in the header section 916. These locks essentially act as semaphores for a cell to avoid collisions. Processionists that are locked out of the cell wait until the lock is lifted before entering. However, in contrast to processionists ejected from the cell or terminated due to an activation condition, processionists waiting for a lock should eventually be allowed to proceed.
Later, after all processionists have proceeded from a cell on all eligible branches (as determined by the path selection section), generally locking persists only if either: a) controlled convergence according to certain convergence rules is expected, or b) the cell has a potentially private active repetition section (see Section II.5.2 below) which may cause the current processionist(s) to loop back through the cell and repeat its behavior. Otherwise the cell is unlocked as soon as the last branch is taken. This allows the rest of the cell to respond to evocation and do everything up to branching in the path selection section (which is the first action that affects the non-reentrant convergence state). In alternative embodiments, all cells (or some cells) could be designed to be completely reentrant. Generally, exclusive locking is required only to the extent a cell is not reentrant. Cell locking is described in detail below in Section III.4.
It will be noted that multiple processionists may branch to the entry zone 906 at the same time in a multiprocessing system. Thus, access to offsets 931, entry zone 906, and lock table 930 are controlled by semaphores or other conventional multiprocessing mechanisms. Thus, multiple processionists may attempt to enter a cell, but actual entry will depend on the cell locks, and be sequenced. Note, however, that in most cases parallel, shared evocation of a cell is allowed. However, the sequencing can be as rapid as few instructions of the host processor, and does not usually prevent the cell from being shared by multiple processionists (the cases where the cell cannot be shared are the stated 1) certain forms of parallel convergence; and 2) private looping constructs).
FIGS. 10A and 10B are flow charts illustrating the process of branching into the entry zone 906 of cell 900 in the first embodiment. When a processionist wishes to evoke or invoke another cell (the "target cell"), it first retrieves the address of the target cell from the current cell. The starting address is the address of the header section 915, and the contents of the header section are at known offsets from this starting address. Using this address, the processionists requests a lock for evocation or invocation as appropriate via lock table 930 (as indicated at step 1002 in FIG. 10A). If the lock is not granted (as determined at step 1004), the processionist places its process ID and thread number in a wait queue for the cell and goes dormant to save processor cycles (as indicated at step 1006). When a lock is being removed by a processionist that holds or shares a lock on the cell, it determines whether a lock can be granted to any of the processionists in the wait queue in order. If the requested lock can be granted, an operating system message is sent to the dormant processionist to awaken it and grant the lock. Once a lock is granted, the processionist retrieves offsets 931 for the target cell from the header section 915. In particular, the processionist retrieves the offset to the evocation reception address 920 for evocation and to the invocation reception address 922 for invocation. The address of the appropriate reception address is then calculated as indicated at step 1010, and the processionist jumps to the appropriate reception address (step 1012). It will be understood that a stackless jump is used for evocation, while a stacked jump (e.g. JSR) is preferably used for invocation to save the return address and current state on the stack.
An evoking processionist starts execution at the evocation reception address 920 as shown at step 1020 of FIG. 10B and a cellFrame is created for the processionist. A threshold count may be incremented or decremented as appropriate if a threshold condition is being used to control access to the cell (step 1022). The activation conditions 926 are then evaluated as shown at step 1024. If the activation conditions are not satisfied, the processionist is terminated as shown at step 1026. Once (and if) activation conditions are met at step 1024, the processionist sets any repetition count or conditional at step 1027 (which determines whether the processionist will loop through the cell more than one time) and proceeds to the output behavioral section 908 as indicated at step 1028. The processionist then proceeds to the output behavioral section 908.
When an invoking processionist enters the cell, it starts executing instructions at the invocation reception address 922 as shown at step 1030 and a cellFrame is created for the processionist. As shown at step 1032, a flag is set in the processionist's cellFrame to indicate that this is an invocation as opposed to an evocation. The return address for the invocation may also be stored if it has not already been pushed on the system stack for the current thread of execution as indicated at 1034. The invoking processionist then proceeds to the output behavioral section as shown at step 1036.
In both invoking and evoking, after passing through the entry zone 906, a processionist executes the output behavioral section 908. The behavior of the output behavior section 908 differs slightly for evocation and invocation as indicated by the separate paths shown in FIGS. 9A and 10B. However, it will be understood that the same code may be executed in large part and that the different functionality may be triggered by checking the invocation flag where appropriate. The output behavioral section 908 contains data and executable code for output and behavior as shown at 932. This may reference other cells, system variables, input sources, and additional blocks of data stored elsewhere in the cell (such as 949 FIG. 9). The output and behavior that may be specified is extremely broad.
2. Output Behavioral Section and the Current Value (Evaluation Space, Current Value, Current Value in Progress, Lineal Code, Data Units)
One of the main functions of the output and behavioral section 908, is to modify the current value of a processionist. As described previously, the value carried by a processionist through a cell is referred to as the current value. The processionist enters the output behavioral section carrying its current value from the respective evoking or invoking cell. FIG. 11 illustrates an invoking processionist carrying a current value 1104. As shown in FIG. 11, a processionist represented by CPU 102 in FIG. 11, contains an address register 1102 referencing the processionist's context block 1107 which in turn references an evaluation space (ES) 1103 in memory 108. The context block 1107 also references the cellFrame as shown at 1109. The ES 1103 contains the current value 1104 as well as space allocated for modifying the current value. The space allocated for modifying the current value is referred to as the current value in progress (CVIP). The program counter 1106 of the processionist points to the output behavioral section 908 of cell 900. The executable code in the output behavioral section may operate on the current value by using the address pointer 1102. Since in this example CPU 102 (or a thread of execution for CPU 102) is invoking cell 900 instead of evoking it, a return address has been stored. A stack pointer 1108 points to the system stack 1110 which contains the return address.
Thus, by using address register 1102, the current value of a processionist may be retained, modified or supplanted as it passes through the output behavioral section 908 of cell 900. All modifications are made to the CVIP and then at the end of the output behavioral section 908, the current value 1104 may be deallocated and replaced with the CVIP. See Section III.5.4 below for additional information as to how the current value is modified.
In the first embodiment, if the output section was never specified, the name of the cell as stored at 934 in name section 916 is set as the current value. Otherwise the output behavioral section consists of a sequence of executable code and data that can modify the current value, or supplant it with a new value, and there may also be additional code that does not affect the current value. Data may be output on output channels as indicated at 936a and 936b in FIG. 9. Output channels may have a standardized format similar to sockets in UNIX. An output channel receives data and a descriptor from which the system determines how to handle the output. For instance video data may be sent to an address for a video monitor with the type set to a value indicating the type of video data. The output channel will then process the data appropriately. In this way multiple cells may share output resources and each cell need not contain separate code for processing the various types of data.
At various points in the output contents 938 of the output behavioral section, data found or generated there may replace or modify the current value, and in some cases be sent to the standard output channel (or a specified output channel), or stored into the (corresponding) output contents 938 of a different cell. Output contents 938 consists, in general, of a sequence of (i.e, one or more) items, each of which may include operational code, data and references to other cells (by invocation). In addition, there may be internal references to supplemental block(s) of data 939 (e.g. within 918 in FIG. 9B). While the range of behavior and output is virtually unlimited, one cell might, as an example, output a personalized video clip to a user's screen any time the cell is activated. The current value of the processionist upon entry might be a user's customization choices for displaying the video clip. The data in the cell may include the actual video clip as an encapsulated media object. The output behavioral section might customize the video clip according to the current value and then send it to the appropriate output channel. A user-customizable video game could be implemented by linking a network of such cells together.
While the output contents 938 of the output behavioral section may be limited to a single item of a specialized type (such as a data structure or media object), it also may be a sequence of any number of items. When displayed for editing, the sequence is cast in the form of lineal code consisting of textual characters, plus optionally, icons representing such things as media objects which are non-literal. Certain sequences of lineal code provide for the prescription of new cells, the interconnection among groups of cells, and the modification of existing cells or the linkages between them. Thus, lineal code may be used in the output behavioral section 908 to modify portions of the current cell or to create new cells or networks of cells in the subspace of the current cell or at a specified point in the network. For instance, FIG. 12A illustrates a cell 1202 (named "S") which has stray super branch to cell 1204 (named "A") and a super branch to cell 1206 (named "B"). Cell 1204 (named "A") has a wild branch to cell 1207 (named "Z"). In addition, cell 1202 has an ordinary branch to cell 1208 (named "Y") and a wild branch to cell 1210 (named "X"). Cell 1208 (named "Y") also has a wild branch to cell 1206 (named "B"). FIG. 12B illustrates the same cells in a manner that shows the order of execution. Cell 1202 ("S") is shown as segregated into two portions 1202A and 1202B (labeled S and S'). Portion 1202A represents the entry zone, output behavioral section, and path selection section of cell 1202. These sections are executed before branching to any subspace cells. Portion 1202B represents the convergence section and exit zone which are executed after the subspace has been executed. This network of cells can be specified using a linear textual code. The code specifies the top level cell (cell 1202 "S") as well as all of the branches in its branch table and the names of the cells to which it may branch. Each cell is enclosed in brackets. Cells in the top level cell's subspace (cells A and B) are also set forth in sets of brackets. Cells that are not in the subspace are defined on subsequent lines.
Table 1 lists lineal code that specifies the network of cells in FIG. 12. The open brace on the first line of Table 1 indicates the beginning of a cell. This is followed by the cell name "S". The remainder of the name section including activation conditions and other "peculiarities," and then the output behavioral section may further be specified as described in Appendix A. This corresponds to the first half of the cell (such as portion 1202A) which is executed before branching. Brackets indicate a subspace cell including the branch to it which is a superbranch, while those with a colon indicate a regular branch, or a double colon indicates a regular branch that is wild. The "" symbol indicates a stray subspace. After all subspaces and pseudo-spaces (indicative of branches that are not subspaces) have been specified (but before the closing brace for cell "S"), the rules of the convergence section and results forwarding may be specified. This corresponds to the second half of the cell which is executed upon recession thereto (such as portion 1202B). The last brace on line 1 of Table 1 indicates the end of the specification for cell "S". The exit zone is implicit and is part of each cell. The "S" after the closing brace is an optional repetition of the cell name to clarify which braces match up; it does not represent any contents of the cell.
TABLE 1
______________________________________
{S {A {::Z} } {B} {:Y} {::X} } S
This specifies cell S, its subspace
cells A & B, and other branches
to X, Y, Z.
{Y {::B} } Y This specifies cell Y and its
branch to B.
{X} This specifies cell X (no subspace
or branches)
{Z} This specifies cell Z (no subspace
or branches)
______________________________________
Thus, lineal code can be used to represent a network of cells. In addition, a structured format may be used to indicate the contents of each cell. For instance, the specification of the name section, output behavioral section, and branch table of cell S would be listed at the first "S" in the first line of Table 1. The specification of the convergence section of cell S would be listed prior to the final brace in the first line of Table 1. The actual format for listing a cell's specification is discussed further in Appendix A, which is incorporated herein by reference. However, it will be readily apparent to one of ordinary skill in the art, that subnetworks of cells may be specified in detail in the output section of a cell and passed as a current value in lineal code and then expanded and added to a network of cells at a desired location. Thus, the system is dynamically modifiable in flexible, convenient and powerful ways. A global cell builder module may be shared by multiple cells and used to expand the lineal code into an executable cell. The cell builder will be described further below. In addition, lineal code commands (described further below) may be used to store values in a cell or replace sections of a cell with new variations. Thus, cell components, such as the activation conditions, or branch table may be modified by the output behavioral section of the same or another cell. Since, a cell has a well-defined structure and operation, this allows further dynamic self-modification of the system. (Note that in the current embodiment instructions in the output section of a cell may not be used to modify that output section of that same cell.)
As is apparent, the range of output and behavioral items is quite wide, and encompasses executable code that may include invocations of other cells, expansion of lineal code, explicit lineal code commands, or references to executable programs of any scope stored in memory. Any of these items may modify the current value and may generate explicit outputs. The last or only explicit output will be suppressed from actual outputting if the cell was invoked. This allows a cell's behavior or output material to be used via invocation without necessarily causing the cell's output. Rather, the last value is returned as an answer to the invocation.
After the output behavioral section has completed modifying the current value, the processionist then proceeds to the path selection section 910 where the processionist may branch to the cell's subspace cells and/or other cells. If there are multiple branches, multiple processionists (threads of execution) may be created to follow the branches in parallel. The current value can be copied into memory or tagged with a reference header and thereby read-only shared by multiple processionists as a current value for each new processionist so that it may be carried by the processionist to the appropriate cell. To clarify context, the current value may be referred to as a forwarded value when a processionist carries the value from one cell to another for purposes of convergence and recession. Alternatively, if the current value is larger in storage requirements than a selected threshold size, a pointer to the current value may be used as the forwarded value for the processionist.
In a sophisticated implementation, the current/forwarded value may comprise complex data units. In addition, it may comprise vectors of such data units. This may be desirable where multiple values are returned from the subspace. The convergence section may assemble the values into an ordered set of values which may be used as the forwarded value for a processionist that exits the cell. The representation of a value includes a descriptor that provides the information sufficient for proper handling and expression of the value, whatever its type or structure. Of course an implementation may be specialized for a particular role and optimized for speed or economy or a specific embodiment utilizing technology less general than a computer, in which case values may be restricted to relatively few and simple types.
A current value may also be real or virtual. A current value that is virtual contains a definitive description of the data, whereas a real current value contains the data in literal or iconic form. For operation in real time or relative to other concurrent threads (processionists) implementation decisions include the extent to which the current value, as maintained from moment to moment, will be "real" or "virtual"--that is to say, at which moments must the current value implementation be present as finalized data suitable for output or storage into a cell, versus present in the form of a representation of the required assembly of its several constituents which may include protracted references to cells and other data sources that may change in the interim between the generation of the reference and the final acquisition of the data. Options include: requiring the current value to be real at every step of current value formation and modification; requiring this only at the finalization of the output section (where the CVIP becomes the current value); or reducing the current value to real form only at the point of operations requiring disposition of the data through final outputting or storage. Note that data under consideration may include sequences of like or dissimilar data types, which may include units with inherent internal parallelism, such as, for example, synchronized audio-visual tracks. These decisions may be influenced by implementation-specific considerations of the economy of copying data elements (of various size) to preserve them against change, versus locking of the original (in a cell, etc.) against change while the reference is pending in a virtual current value representation. Thus the decision to carry such a protracted reference to a cell's contents in the current value may be automated under a size criterion, with locking of the original against change during pendency.
More generally, a decision may be made, in each application or instance, whether a protracted reference is intended to refer to the state of the data at the moment the reference is generated versus at the later moment it is utilized, at which time it may be different. Maintaining a current value (or particular elements of it) as virtual for as long as possible has two advantages: (1) to postpone possible conflicts over access until access is available, or else to the last possible moment; (2) to allow bulky items to remain packaged or compressed until and unless actually needed to be internally processed or output or stored in their real form.
When a processionist enters a cell carrying a value, the value is carried through the cell and may be modified in the output behavioral section, replicated for new processionists in the path selection section, and replaced, forwarded or discarded in the convergence section. The value will be passed along branches taken by the processionist from the cell, or will recess with the processionist if none was taken. And if branches were taken from the cell to cells that eventually recess and converge back to the cell, the values(s) returned from those cells will recess back to the convergence section of the cell where they may be assembled into a new current value at that point.
Answering from an invoked cell and recession from an evoked cell may be contrasted. If the cell is evoked, and recession from it eventually occurs, the processionist will recess carrying the value it had when it reached the exit zone. On the other hand, if the cell was invoked, and it eventually answers, it will answer with the processionist carrying the value it had when it reached the exit zone. In either case, this value will be--if the cell had branches that were taken and converged (or one that simply recessed) to the cell's convergence zone--the value returned from the most recently recessed processionist, or otherwise that selected by the convergence and result forwarding rule if any.
Consequently, an invoked cell answers with its current value determined by its final or only output item, or by the result from convergence from its subspace cells, if any. In any event the cell's final or only output item is suppressed from outputting if the cell was invoked rather than evoked, so that the final current value can serve only as an answer to the invocation. This is indicated by the separate output control 932 sections for invocation and evocation. For invocation, the output contents 938 is executed and the processionist proceeds to the path selection section 910 without outputting any final result. For evocation, the output section 938 is executed and then the evocation control outputs the result on output channel 936a. Then the processionist proceeds to the path selection section 910.
Items in the output section are classified as those that yield an output and replace the current value or contribute to the current value in progress (CVIP), and those that do not. For outputting items, the result of the item is output via the prevailing standard output channel, unless it is directed elsewhere (i.e, stored) or suppressed explicitly or by virtue of being the final current value used for answering an invocation. The form of the output depends on the type of the value, and standard channels may be explicitly redirected to nonstandard channels. Common outputs which may be handled in this way include: a number or a body of text directed to a text window, terminal or printer; a graphic image directed to an appropriate display; a digitized acoustical signal directed to an appropriate speaker or telephone line; an audio-video animation or performance directed to an appropriate receiver. As an item executes, it contributes to the CVIP and may also cause the current value to be replaced. If the item is beyond a certain size or complexity (or if, when and as explicitly elected) the CVIP (and later the current value) will actually carry a definitive description of the item rather than its contents, leaving the assembly of the completely "expanded" output to be performed at "the last possible moment"--that is at such time as it is actually required for outputting, display or storage in its literal or iconic form.
Items yielding output may be, incorporating the above: a numerical calculation, line of literal text, or concatenation of such things; a reference to a cell by invocation, or a formula including such references along with any literal or numerical values combined by arithmetic operations or conjunctions; other kinds of references such as to an input source, data file, signal stream or buffer or telecommunications switch, external computer or reference to a different cellular network; any concatenation of these or formula of these combined by arithmetic operators or conjunctions or storage operations or redirection. However if the sequence terminates in a storage operation followed by a cell reference invoked as a destination, the output effect of the entire item is suppressed, although the overall result in any event replaces the current value.
Items not generally yielding output or replacing the current value include: direct commands, allowing that these may in certain instances explicitly command replacement of the current value; metaprogrammic commands, being symbols to be replaced by series of instructions or operations implementing their stated effect; comments; coherent sequences of machine language instructions (operable on the host computer processor implementing the virtual processionists), references to display files not handled by standard output channels available to cells, or references to external programmatic units which direct their outputs elsewhere. It is also electable to dedicate the output section in its entirety to a single item, such as a number, string of text, array or other conventional data structure, "performance unit" (such as a synchronized audio-visual program, stereophonic sound, parallel multilingual presentation, or concatenation of different modalities). Units which would monopolize the output section of a single cell, and probably direct their outputs or other behavioral consequences elsewhere than to the standard-cellular output channels, might include computer programs, operating systems and programming environments.
In addition to the current value, "riders" on the current value may be implemented that follow the same course as the current value as it is carried by the processionist. The rider serves to preserve certain special values against change as the current value gets changed by items in the output behavioral section. The rider receives the new value of current value whenever the curre |
