Dataflow processing with events

Abstract

Interactive event-driven programs are structured and executed using two types of constructs: interconnectable processing components and flow objects with associated data. Components are interconnected in a hierarchical dataflow network, and references which provide access to flow objects flow on the interconnections. Response to events and bidirectional coordination over multicomponent data paths, even in a distributed object system, employ unidirectional dataflows and intercomponent message sequences mediated by flow objects. Scaling and abstraction of complexity are facilitated by encapsulation of constructed networks into new component definitions. An interactive debugger preserves state as an executing program is edited, permitting an event-driven program to be modified in the intervals between processing of events without reinitialization. A component protection method employs multiple Levels of usage authorization within components, enabling developers to define and distribute new protected components in a decentralized component market.

Claims

What is claimed is:

1. A method of processing data comprising

providing a flow object,

providing a network of interconnected processing components none of which is a flow object and at least one of which is not a user-interface component,

associating the flow object with data that has been or is to be processed,

enabling a flow within the network which transports from one processing component to another a reference which provides access to the flow object,

enabling processing components to use the reference to obtain access to the flow object for the purpose of processing the flow object or the data associated with the flow object, and

maintaining consistency across the network, as the flow object or the data associated with it are processed, of the components' views of the flow object and its data, by a sequence of communications which comprises

a communication from a sending processing component to the flow object, and

a communication from the flow object to a receiving processing component.

2. The method of claim 1 wherein

an interconnection touches a pair of processing components associated with the interconnection, and

a reference which provides access to the flow object is transported across the interconnection.

3. The method of claim 2 wherein references which provide access to the same flow object are transported across different interconnections.

4. The method of claim 2 wherein the reference which provides access to the flow object is transported in only one direction across the interconnection, from a sending component associated with the interconnection, which component sends the flow, to a receiving component associated with the interconnection, which component receives the flow.

5. The method of claim 4 wherein the sending processing component is the processing component associated with the flow object's owner.

6. The method of claim 4 comprising a selector processing component, wherein

the selector processing component is a receiving component of a reference which provides access to an input flow object whose associated data comprises a base collection, and

the selector processing component is a sending component of a reference which provides access to a list flow object whose associated data comprises a selected collection instance based on the base collection.

7. The method of claim 6 in which the selector processing component is a sending component of a reference which provides access to an output flow object, wherein

the associated data of the output flow object provides access to the subcollection of the base collection specified by the selected collection instance associated with the list flow object, and

a modification to the selected collection instance causes the value of the associated data of the output flow object to update to provide access to the subcollection specified by the modified selected collection instance.

8. The method of claim 7 wherein

the output flow object has an owner, and

the selector processing component is associated with the owner of the output flow object.

9. The method of claim 6 wherein

the list flow object has an owner, and

the selector processing component is associated with the owner of the list flow object.

10. The method of claim 4 comprising a launcher processing component, wherein

the launcher processing component is configured to be a receiving component of a reference which provides access to an argument flow object,

the launcher processing component is configured to be a receiving component of a reference which provides access to a flow object whose associated data denotes an instantiable processing component type,

an instance of the instantiable processing component type is configured to be a receiving component of a reference which provides access to a flow object, and

the launcher processing component is configured to perform an instantiation processing operation, wherein

the instantiation processing operation causes to be created an instance of the instantiable processing component type, and

if the launcher processing component is a receiving component of a reference which provides access to an argument flow object, then the created instance is a receiving component of a reference which provides access to said argument flow object.

11. The method of claim 4 wherein, when the receiving component receives a reference which provides access to the flow object, then the receiving component is enabled to process the flow object or its associated data.

12. The method of claim 4 wherein,

when a processing component of the network which is configured to be both a receiving component and a sending component receives a flow of a reference which provides access to the flow object,

then the processing component is enabled to send a flow of a reference which provides access to the flow object.

13. The method of claim 4 wherein

a processing component A of the network is a sending component with respect to the flow object and with respect to interconnection I, and

a processing component B of the network is a receiving component with respect to the flow object and with respect to interconnection J, wherein

interconnection I is different from interconnection J.

14. The method of claim 4 comprising a composite processing component which comprises an internal network of interconnected processing components, wherein

if the composite processing component receives a flow which transports a reference A which provides access to flow object F, then there exists a processing component of the integral network which receives a flow which transports a reference B which provides access to flow object F, and

if the composite processing component sends a flow which transports a reference C which provides access to flow object G, then there exists a processing component of the internal network which sends a flow which transports a reference D which provides access to flow object G.

15. The method of claim 4 comprising

a processing component configured to be a sending component with respect to an interconnection, and

a processing operation of the processing component, a result of which processing operation is a result object, wherein

upon completion of the processing operation, the processing component is enabled to initiate a flow of a reference which provides access to a flow object whose associated data comprises the result object.

16. The method of claim 1 wherein processing comprises modification of an aspect of the flow object or of the data associated with the flow object.

17. The method of claim 1 wherein a reference which provides access to the flow object is used by one of the processing components to communicate to the flow object.

18. The method of claim 1 wherein a reference which provides access to one of the processing components is used by the flow object to communicate to the processing component.

19. The method of claim 1 wherein

the flow object has an owner and comprises a reference which provides access to the owner, and

the owner is associated with one of the processing components.

20. The method of claim 19 wherein the owner comprises the owner's associated processing component and an interconnection which touches that processing component.

21. The method of claim 19 wherein one of the processing components which is processing the flow object or the data associated with the flow object maintains consistency between itself and the processing component associated with the owner of the flow object.

22. The method of claim 19 wherein the processing component associated with the owner maintains consistency between itself and the processing component associated with a dependent of the flow object.

23. The method of claim 22 wherein the processing component associated with the dependent is configured to ignore an aspect of a received communication.

24. The method of claim 19 wherein the owner comprises a processing component of the network.

25. The method of claim 19 wherein the owner is associated with exactly one processing component of the network.

26. The method of claim 19 wherein the owner is configured to interact with its associated processing component.

27. The method of claim 1 wherein the flow object has one or more dependents and comprises one or more references which provide access to the one or more dependents, wherein

each of the dependents is associated with one of the processing components.

28. The method of claim 27 wherein a dependent comprises the dependent's associated processing component and an interconnection which touches that processing component.

29. The method of claim 27 wherein the flow object communicates to the processing component respectively associated with each of its dependents.

30. The method of claim 27 wherein a dependent comprises a component of the network.

31. The method of claim 1 wherein a flow comprises copying a reference which provides access to the flow object.

32. The method of claim 1 wherein at least one of the communications comprises giving notice that processing has occurred.

33. The method of claim 1 wherein processing comprises projecting an aspect of the flow object or data associated with the flow object onto a user interface.

34. The method of claim 33 wherein for every displayed element of the user interface there exists a flow object wherein the displayed element is a projection of an aspect of the flow object or of data associated with the flow object.

35. The method of claim 1 wherein one of the processing components is configured to receive an event.

36. The method of claim 35 wherein the event comprises a signal originated by a device.

37. The method of claim 1 wherein the components of the network are arranged hierarchically.

38. The method of claim 1 wherein the data associated with the flow object comprises an object.

39. The method of claim 38 wherein the object comprises a process.

40. The method of claim 1 wherein the data associated with the flow object comprises a flow object.

41. The method of claim 1 wherein the data associated with the flow object comprises a collection of flow objects.

42. The method of claim 1 wherein the association between the flow object and its associated data comprises the flow object comprising a reference which provides access to the associated data.

43. The method of claim 1 wherein more than one flow object is associated with the same data.

44. The method of claim 33 wherein the associated data of the created flow object is created other than by the processing component which creates the flow subject.

45. The method of claim 1 wherein the data associated with a first flow object has a nonempty intersection with the data associated with a second flow object.

46. The method of claim 1 wherein at least some of the processing components of the network are organized in types, instances of which comprise these processing components.

47. The method of claim 1 wherein at least some of the processed data are organized in types, instances of which comprise these processed data.

48. The method of claim 47 wherein one of the data instances denotes a processing component type.

49. The method of claim 48 wherein one of the processing components of the network creates an instance of the denoted processing component type.

50. The method of claim 49 wherein the processing component initiates the execution of the created component instance.

51. The method of claim 47 comprising a selected collection processed data type, an instance of which comprises

a reference which provides access to a base collection on which the selected collection instance is based, and

a selection on the base collection, which selection comprises a specification of a possibly empty subcollection of the base collection.

52. The method of claim 51 comprising a flow object associated with an instance of the selected collection processed data type, wherein

there is an editor processing component of the network which is configured to modify the selection in the flow object's associated selected collection instance, and

there is a projector processing component of the network which is configured to project onto a user interface an aspect of the selected collection instance.

53. The method of claim 52 wherein a modification to the selected collection instance causes the projector processing component to respond by updating its projection to be consistent with the resulting value of the selected collection instance.

54. The method of claim 1 comprising a flow object whose response to processing is consistent with the response to said processing of a null object.

55. The method of claim 1 wherein one of the processing components is configured to create a flow object.

56. The method of claim 43 wherein the processed data comprises the settable processing component's setting value.

57. The method of claim 56 wherein

there is a flow object whose associated processed data comprises an aspect of the settable processing component's setting value, and

there is an operating processing component of the network configured to process said flow object or associated processed data.

58. The method of claim 57 wherein

the flow object has an owner associated with an owning processing component of the network, a dependent associated with a user processing component of the network, and a dependent associated with the operating processing component, and

the owning processing component, the operating processing component, and the user processing component participate in a consistency-maintaining sequence of coordinations.

59. The method of claim 58 wherein the owning processing component is the settable processing component.

60. The method of claim 55 wherein a creator processing component which creates the flow object is configured to send a flow of a reference which provides access to the flow object.

61. The method of claim 60 wherein the created flow object has an owner and the owner is configured to enable performance of a processing operation by a user processing component of the network which comprises a reference which provides access to the flow object.

62. The method of claim 61 wherein the owner is associated with the creator processing component.

63. The method of claim 1 wherein the flow object yields an identifier which is distinctive of the flow object.

64. The method of claim 63 wherein the distinctive identifier may be data or an object.

65. The method of claim 63 wherein one of the processing components uses the identifier in processing.

66. The method of claim 65 wherein processing comprises projection of an aspect of the identifier onto a user interface.

67. The method of claim 65 wherein processing comprises a table lookup.

68. The method of claim 1 wherein the flow object comprises a reference which provides access to a processing component of the network.

69. The method of claim 1 wherein the processing components of the network include a settable processing component which comprises a setting value.

70. The method of claim 69 wherein the setting value becomes persistent when the network is encapsulated.

71. The method of claim 70 wherein the setting value may be changed either before or after encapsulation.

72. The method of claim 1 wherein at least some of the flow objects are organized in types, instances of which comprise these flow objects.

73. The method of claim 1 wherein there is a proxy object which is in relationship to the flow object.

74. The method of claim 73 wherein a processing component of the network communicates to the flow object by communicating to the proxy object which forwards the communication to the flow object and returns the result to the processing component.

75. The method of claim 73 wherein the flow object communicates to the processing component by communicating to the proxy object, which forwards the communication to the processing component and returns the result to the flow object.

76. The method of claim 75 wherein the flow object has an owner and communicates to the processing component associated with the owner via the proxy object.

77. The method of claim 75 wherein the flow object has a dependent and communicates to the processing component associated with the dependent via the proxy object.

78. The method of claim 73 wherein

at least one communication is sent via a proxy object.

79. The method of claim 1 wherein

there is an editor processing component of the network which is configured to modify aspect A of the flow object or the flow object's associated processed data, and

there is a user processing component of the network which is configured to employ aspect B in processing of the flow object or of the flow object's associated processed data.

80. The method of claim 79 wherein there occurs a consistency-maintaining sequence of coordinations comprising

coordination between the editor processing component and a relay processing component of the network, wherein the editor processing component notifies the relay processing component, by a sequence of communications, that modification has occurred, and

coordination between the relay processing component and the user processing component wherein the relay processing component notifies the user processing component, by a sequence of communications, that modification has occurred.

81. The method of claim 80 wherein the user processing component is configured so that, in response to notice that modification has occurred, the user processing component employs in its processing the modified flow object or its associated modified data.

82. The method of claim 1 comprising a command flow object which has

an owner associated with an actuator processing component of the network, configured to perform a designated processing operation, and

a dependent associated with an initiator processing component of the network, configured to receive a signal, wherein

when the initiator processing component receives the signal it notifies the actuator processing component, by a sequence of communications, that the signal has been received, and

the actuator processing component performs the designated processing operation.

83. The method of claim 82 wherein the signal arises in consequence of a processing operation.

84. The method of claim 82 comprising a projector processing component which projects an aspect of the command flow object or its associated data on a user interface, wherein the occurrence of an event at the user interface causes the initiator processing component to receive a signal.

85. The method of claim 84 wherein the projector processing component is the initiator processing component.

86. A tool for developing a software program,

the tool comprising a program under development and a possibly null flow object,

the program under development comprising a network comprising components and interconnections,

the tool being configured to restructure the network,

an interconnection denoting a flow object and being attached to two components, one of the attachments being asource and the other being a sink, the source being associated with a source function,

an output from the source function determining the flow object denoted by the interconnection,

an input to the source function comprising a flow object denoted by a sink of the source's component, and

a nonnull flow object comprising a processed object, wherein

a component is configured to send a processing message to the processed object,

a component is configured to communicate to the nonnull flow object denoted by an interconnection attached to the component, and

a component is configured to enable the nonnull flow object denoted by an interconnection attached to the component to communicate to the component.

87. The tool of claim 86 comprising a program control mechanism configured to stop and start the program under development, wherein

when the program under development is stopped, the interconnection denotes a null flow object.

88. The tool of claim 86 wherein a network computation comprises a source function, the network computation being configured so that execution of the network computation is begun when the program under development is started, wherein

if the network computation terminates without error and then the network is restructured

then the network computation is reconfigured based on the resultant network structure, and execution of the resultant network computation is begun if the program is not stopped.

89. The tool of claim 88 wherein the network computation is iterative.

90. The tool of claim 88 wherein all functions of the network computation are performed, one function at a time.

91. The tool of claim 90 wherein, if the value of a function is dependent on the value of at most one input, then the function is evaluated whenever that input value changes.

92. The tool of claim 90 wherein, if the value of a function is dependent on the value of more than one input there is a pending status associated with the function, wherein

the pending status of the function is set to pending if the value of an input on which the value of the function is dependent changes when the pending status of the function is not pending,

the pending status of the function is set to not pending when the program under development is stopped, and

the pending status of the function is set to not pending when the function's evaluation is complete.

93. The tool of claim 92 wherein the network computation does not terminate until the pending status of every function of the network computation is not pending.

94. The tool of claim 93 comprising a network computation control mechanism which seeks to minimize the total number of function evaluations.

95. The tool of claim 92 wherein a designator of the function is placed at the rear of a first-in first-out queue when the pending status of the function is set to pending, and the function designator is removed when it reaches the front of the queue, after which removal the function is evaluated.

96. The tool of claim 95 wherein the network computation has terminated when the queue is empty after completion of evaluation of the function.

97. The tool of claim 95 comprising loop detection to determine nontermination of the computation.

98. The tool of claim 88 comprising a network computation control mechanism which seeks to minimize the total network computation time.

99. The tool of claim 88 wherein the network computation also comprises a state function.

100. The tool of claim 88 wherein the network computation comprises all source functions and all state functions of the network.

101. The tool of claim 88 wherein a function of the network computation is configured to query a database.

102. The tool of claim 86 comprising a connector, wherein

the connector is attached to a component,

the connector comprises either a sink connector or a source connector, wherein

either the source connector comprises a source, in which case the source connector is attached to the source's interconnection, the source connector denotes the flow object denoted by the interconnection, and the source connector comprises the source's source function, or else the source connector is not attached to an interconnection, and

either the sink connector comprises a sink, in which case the sink connector is attached to the sink's interconnection and the sink connector denotes the flow object denoted by the interconnection, or else the sink connector is not attached to an interconnection.

103. The tool of claim 86 wherein the program under development comprises a user interface.

104. The tool of claim 86 comprising a composite component type which comprises a network of component templates and interconnection templates, wherein

each interconnection template has two attached component templates,

said composite component type being configured to create an instance which is a composite component comprising a network of components and interconnections, wherein

a component template creates a component

an interconnection template creates an interconnection, and

the components attached to the interconnection are created by the component templates attached to the interconnection template which creates the interconnection.

105. The tool of claim 104 wherein a component template comprises either a composite component template or a primitive component template.

106. The tool of claim 105 wherein a composite component template comprises a composite component type, and a primitive component template comprises a primitive component type.

107. The tool of claim 106 wherein a component type comprises either a composite component type or a primitive component type.

108. The tool of claim 107 comprising a restriction mechanism wherein the component type comprises a restriction.

109. The tool of claim 108 wherein an instance of the type comprises the restriction.

110. The tool of claim 104 wherein the instance is attached to an outside sink connector.

111. The tool of claim 110 wherein the network of the instance comprises a component attached to an inside sink connector, wherein

the inside sink connector and the outside sink connector denote the same flow object.

112. The tool of claim 104 wherein the instance is attached to an outside source connector.

113. The tool of claim 112 wherein the network of the instance comprises a component attached to an inside source connector, wherein

the inside source connector and the outside source connector denote the same flow object.

114. The tool of claim 86 in which the program under development comprises an instance of a composite component type.

115. The tool of claim 86 configured to create an instance of a component type.

116. The tool of claim 86 whose program under development comprises at least one component with a source connector which, upon commencement of the program, denotes a nonnull flow object.

117. The tool of claim 86 wherein every component of the program under development is created by a component template.

118. The tool of claim 117 wherein a component's template's type determines the number of sink and source connectors and the identity of each sink and source connector of the component.

119. The tool of claim 118 wherein the type of the component determines the source function of each source connector of the component.

120. The tool of claim 119 wherein the source function's input comprises either or both of a flow object denoted by a sink of the source's component or a state variable of the component.

121. The tool of claim 86 wherein the program under development comprises a component which comprises a state variable.

122. The tool of claim 121 wherein the identity and initial value of the state variable are determined by the component's type.

123. The tool of claim 122 wherein the state variable is set to its initial value when the program is stopped.

124. The tool of claim 122 wherein the state variable is associated with a state function, determined by the components type, the output from the state function determining the state variable's value and the input to the state function comprising either or both of a flow object denoted by a sink of the source's component or a state variable of the component.

125. The tool of claim 121 wherein the state variable provides access to a storage system external to the component.

126. The tool of claim 86 wherein the state variable provides access to the result of a database query.

127. The tool of claim 121 wherein the component projects an aspect of the state variable onto the user interface of the program under development.

128. The tool of claim 86 in which the program under development comprises a component which comprises a setting variable.

129. The tool of claim 128 wherein the component's type determines the identity of the setting variable.

130. The tool of claim 128 wherein the initial value of the setting variable is determined by the template from which the component is created.

131. The tool of claim 130 wherein the setting variable is set to its initial value when the program is stopped.

132. The tool of claim 128 wherein a source function's input comprises a flow object denoted by a sink of the source's component or the value of a state variable of the component or the value of the setting variable, and a state function's input comprises a flow object denoted by a sink of the source's component or the value of a state variable of the component or the value of the setting variable.

133. The tool of claim 86 wherein the processed object comprises a state variable.

134. The tool of claim 86 wherein the processed object comprises a setting variable.

135. The tool of claim 86 wherein a component is configured to receive an event.

136. The tool of claim 135 wherein the event is sent by the tool.

137. The tool of claim 135 wherein the event is sent by the user interface of the program under development.

138. The tool of claim 135 wherein the component comprises a state variable whose value is modified by the component's receipt of the event.

139. The tool of claim 86 wherein the program under development comprises a communication mechanism in which an aspect of one component is configured to communicate with an aspect of another component.

140. The tool of claim 86 wherein a function of the network computation is configured to modify an aspect of the processed object.

141. The tool of claim 86 comprising a developer interface.

142. The tool of claim 142 wherein the developer interface comprises the user interface of the program under development.

143. The tool of claim 142 comprising a selection mechanism configured to choose a portion of the network on which an operation is to be performed.

144. The tool of claim 143 wherein the restriction mechanism interacts with the menu mechanism to modify either the availability of an opportunity to perform an operation on the portion of the network or the behavior of the operation.

145. The tool of claim 142 comprising a menu mechanism configured to present an opportunity to perform an operation.

146. The tool of claim 86 comprising a data inspection mechanism wherein an aspect of any of a state variable, a setting variable, or a flow object is projected onto the developer interface.

147. The tool of claim 86 comprising a program inspection mechanism wherein an aspect of the network is projected onto the developer interface.

148. The tool of claim 86 comprising a stepping mechanism configured to control and inspect the progress of the network computation.

149. The tool of claim 148 wherein the stepping mechanism cooperates with the program inspection mechanism to project on the developer interface information which visually depicts the state changes of the program under development.

150. The tool of claim 86 comprising a type library comprising a component type.

151. The tool of claim 86 wherein an input of a function of the network computation comprise an aspect of the processed object.

Description

BACKGROUND OF THE INVENTION

The invention relates to programs with graphical user interfaces.

Graphical user interfaces typically employ graphical displays for output to the user and one or more devices for input from the user, possibly including a keyboard and a pointing device like a "mouse" with one or more buttons for signalling the application program. The term "display-out event-in" is used here to describe such user interfaces. The emphasis of the present discussion is on reducing the complexity with which the designers and builders of these systems must deal.

The display-out event-in user interface was largely pioneered at Xerox Palo Alto Research Center (PARC). Many of the ideas developed at PARC were embodied in the Smalltalk and Alto systems developed there. The PARC group used the term "modeless user interface" to mean, among other ideas, that the interpretation of input events depends on the position of the mouse pointer with respect to the possibly several figures being displayed, and also on the relative positions of these several figures with respect to each other. Thus, in more recent systems descended from Smalltalk and Alto, particularly in the Apple Macintosh and the Microsoft Windows operating systems, characters typed on the keyboard are interpreted as input to the "window" figure which is the "top" of several possibly "overlapping" windows, and a mouse-button depression is interpreted as being "directed to" the visible figure, such as a "button," which is "under" (i.e., whose graphical region encloses the position of) the mouse pointer. We assume that this context-dependent character of event interpretation is present in the display-out event-in user interfaces being discussed here.

Implementation of a data processing system employing a display-out event-in user interface is complex and difficult, being centered about a low-level "event loop" which is continually sampling the input devices for input events. Once an event is detected, a possibly quite complex decision sequence is undertaken to discover the display figure with respect to which this input event is to be interpreted. Once this display figure is isolated, some form of signal is sent to an entity, usually a software object or function, associated with this display figure. This entity then interprets the event in the context of the application program in whose service all this machinery exists.

The design of a "user-interface management system" (UIMS) consists, in part, of deciding what desirably maximum set of functions (such as the event-identification function described above) can be isolated from the application program and packaged as a general set of services available to all application programs, thus reducing the total complexity of multiple application programs which use the UIMS. Even with such UIMSs, the construction of application programs with display-out event-in user interfaces remains complex and difficult.

Many designers have employed two common strategies for simplifying the structure and construction of application programs. The first strategy is based on the observation that the sequential aspects of programming contribute substantially to the difficulty of the task. This first strategy consists of finding a way to divide the structure of the program into a sequential part and a static part in such a way that the builder of the application program needs to pay minimal attention to the sequential part. The second strategy consists of finding a way to partition the remaining sequential part so its subparts are typically simple and have minimal interaction with each other.

The first simplification strategy is facilitated by dividing the universe of applications into similarity-groups, such that all the members of each similarity-group share a common design for the sequential part. Then a "sequence engine" common to all members of the similarity-group can be built and used by all application program builders as the implementation of the common sequential part. The task of a builder of an application from one of these similarity-groups is ideally reduced to a static parameterization of the sequence engine; the builder can largely ignore the internal details of the sequence engine.

An historically important application of the first simplification strategy has been with respect to the similarity-group of report-generation programs based on sequential files. The strategy was employed in the design of the wiring panels of nonstored-program punched-card tabulating machines such as the IBM 407 (whose underlying sequential "card cycle" is largely implicit in the wiring panel) and then subsequently to the successors of the IBM 407, including the RPG programming system for the IBM 1401 computer and a long line of report-generator program successors to RPG. All of these instances of the first simplification strategy insulated the application program builder from the sequential details of the underlying record-processing cycle and focused on the static formats of data in files and reports, with the choice of alternative report formats based on data values.

Applications with display-out event-in user interfaces form a similarity-group in the sense described above, because they have in common the underlying event-loop processing cycle. Attempts to exploit the first simplification strategy with respect to the similarity-group of display-out event-in programs (and thus to make construction of application programs from this group a simpler, more static process) have had some success.

The earliest well developed application of the first simplification strategy to display-out event-in systems is the Model-View-Controller (MVC) design paradigm developed at PARC as part of the Smalltalk programming system. In the MVC paradigm the application is divided into three parts: the View part expresses display appearance, the Controller part expresses event-identification behavior, and the Model part expresses everything else, namely the "internal" (i.e., non-user-interface) application logic, which communicates with the user via the View and Controller parts. All three parts are built using the Smalltalk language. Importantly, the application program developer can largely limit his/her attention to the Model part, since the View and Controller parts are incorporated into the Smalltalk system. (The sequence engine is hidden in the Controller part.)

Microsoft Visual Basic (VB) is a representative and widely-used contemporary example of both simplification strategies. In VB the structure of an application program is organized into two major portions, which we can call Forms and Procedures. Forms express the visual aspects of the user interface and contain collections of "controls," which are specific visual features with specific behaviors, for example, buttons. (It is an additional benefit of major practical importance, although that benefit is not immediately relevant to the present discussion, that the specification of Forms in VB is entirely pictorial.)

VB is an application of the second simplification strategy in that Procedures consist of many (typically) small modules of code and, furthermore, that these modules are grouped by, and logically associated with, the controls appearing in the Forms. Each code module is dedicated to the handling of one event which "originates" from its associated control. Thus the design of VB assigns each code module uniquely to a point in the space of ordered pairs (control, event). This partitioning is an effective application of the second simplification strategy because there is typically little interaction between these ordered pairs.

In the current art as widely practiced, sequential procedure code has been largely removed from the specification of the appearance of the display but remains in the specification of the handling of events and in the specification of application logic, namely those aspects of the design which, in the MVC paradigm, are collectively called the Model. A program constructed according to contemporary practice consists of two quite distinct specification "layers:" a static (and visual) Form layer and a Procedure layer containing a collection of partially interacting code modules. There is in such practice an undesirable conceptual and cognitive discontinuity between these two layers.

As distinct from the two-layer model described above, Fabrik [D. Ingalls et al, "Fabrik: A Visual Programming Environment," Proceedings of OOPSLA (Conference on Object-Oriented Programming Systems, Languages, and Applications), September 1988] conceptualizes a display-out event-in application program as a constraint network [A. H. Borning, "ThingLab, a Constraint-Oriented Simulation Laboratory," Tech. Report SSL-79-3, Xerox Palo Alto Research Center, July 1979]. This constraint network is visualized as a set of components with connectors on their edges. Wires can be drawn between the connectors. Typically of constraint-oriented specification models, the Fabrik conceptual model is quasi-static and does not embody the two-layer conceptual discontinuity described above. The hidden sequence engine of Fabrik is in two parts. It consists of the above-described sequence engine of the display-out event-in user interface as contained in certain components associated with user-interface events, plus a distributed constraint-maintenance protocol associated with the set of wires. The distributed constraint-maintenance protocol assures that the dataflow values at both ends of each wire are the same. The constraint-maintenance protocol is local (i.e., it deals only with the values at the two ends of each wire) and it permits bidirectional flow along certain wires. As an example of the practical consequence of the locality of Fabrik's constraint-maintenance protocol, the extended path from a data value in a database component to its user-interface display component must be fully bidirectional, in order to manage the propagation of data changes which can occur either in the database or at the user interface. This need for full bidirectionality in extended data paths adds substantial complexity to the task of building practical programs and to the task of building components, particularly for the majority of components which have more than two connectors, because of the combinatorial growth of the number of cases of change propagation which must be handled.

SUMMARY

In general, in one aspect, the invention features a computer software method in which references to a flow object are flowed through a network of processing components, and the processing components are enabled to have direct access to a common version of the flow object for the purpose of performing operations with respect to the flow object.

Implementations of the invention may include one or more of the following features.

The reference to the flow object may flow in only one direction through the network. One of the operations may include modification of the flow object. The flow object reference may be used by a component to send a message directly to the flow object. The flow object may use a reference to a component to send a message directly to the component. The flow object may have an owner component, may contain a reference to its owner component, and may use the reference to refer to its owner component. The flow object may have one or more dependent components and may contain references to refer to the one or more dependent components. The reference may be used in message-passing communication acts to keep the components synchronized in their use of the flow object. The message-passing communication acts may occur in alternating patterns of messages, component to flow object, flow object to component, and so on. The message-passing communication acts may give notice that a flow object has been operated on.

The processing of a component may project the flow object onto an event driven user interface. Every displayed element of the user interface may be a projection of a flow object. The events may include key strokes and pointer actions. The components may be hierarchical.

The flow object may include a reference to an object. The object referred to in the flow object may be a not-pure-data object. The not-pure-data object may include a process to be executed, or a flow object, or a collection of flow objects. At least one of the components may operate on the flow object by means of a reference without flowing references to the flow object through the network. A component which is operating on a flow object may advise the flow object's owner component, by a message-passing communication act, when the flow object has been operated on. The component which is operating on the flow object may apply the communication act to the flow object. The owner component may advise dependent components, by message-passing communication acts, when the flow object has been operated on. Action on the advice to dependent components may be blocked at the operating component.

At least some communication between components may be achieved by flowing references to the flow object from a serving component through the network including into another component, and then having the other component engage in message-passing communication acts directly with the serving component. A component may generate and operate on a derivative of the flow object without copying the parts of the flow object, by using references to the parts of the flow object. Components may be organized in types, instances of which comprise the components of the network.

Flow objects may be organized in types, instances of which comprise the flow objects the references to which flow in the network. One of the flow object types may be a type that has at least one MO instance. One of the flow object types may represent a component type. Instances of the flow object type may be spawned by an instance of one of the component types. Instances of one of the component types may invoke the component type represented by a flow object instance. Flow objects may include any of DoIt, port, dialog projector, component type description, tool, or child window projector. A flow object may yield an identifier which can be used to distinguish it from other flow objects, e.g., a picture or text. The flow object may include a wrapper which yields a value of the identifier, or yields component references. A component may use the identifier in taking an action, such as displaying of the identifier onto a user interface, or a table lookup.

A component may include a persistent value, which may be set when a network containing the component is encapsulated. The value may be changed either before or after encapsulation.

In general, in another aspect, the invention features a reusable component type comprising a template according to which the component type may create component instances, the template including information about external characteristics of the type and about internal characteristics of the type.

Implementations of the invention may include one or more of the following. The internal characteristics may include information about actions that may be taken by the component instances, e.g., operating on a flow object, or originating a flow from a source. The component instance may contain or receive via a sink connector a representation of a flow object type and the action may include creating an instance of that type. The action may include the origination of a message-passing communication act. The effect of the action when a flow object referred to at a sink is MO may be the same as if the flow-object reference in the sink were invalid. The action may occur in response to receipt by the component instance of an event or of a flow or a message-passing communication act.

The internal characteristics may include the ability of the component instances to respond to and to initiate flows and message-passing communication acts. The external characteristics may include the ability of the sinks of the component instances to respond to invalidate sink connector and receive flow messages. The component instances may respond to owner be notified and dependent be notified messages from flow objects, to stop, idle, and run messages, and to event messages and to pick messages from DoIts of which they are the server.

The external characteristics may also include a connector type which acts as a template for creating connector instances according to which the component instance comprises the connector instance, and the connector instance has storage which holds a flow object reference. The flow object reference may be valid or invalid, and, if invalid, does not refer to a flow object and, if valid, refers to a flow object. The connector type may include a sink type whose instances receive references via connections from source connector instances of components or a source type whose instances send references via connections to source connector instances of components.

The component type may include a mechanism for communicating with a flow object referred to. The component type may be embodied in one data structure and the component instance may be embodied in another data structure. The component type data structure may be persistent and the component instance data structure may be transient. The component type may include a primitive component type. The component type may include a composite component type which contains a reference to a component type. Except for the number of sink connector types and source connector types comprised therein, the component type may be indistinguishable in its external characteristics from other component types. The boundaries of a composite component instance may be hidden with respect to message-passing communication acts.

In general, in another aspect, the invention features a connector component type which includes expressions of the functional relationship between internal network interconnections of a composite component type and external connections of a reference to the composite component type in a manner that represents encapsulation of the internal network interconnections whose only connections to the outside of the component type are through connector component instances.

Implementations of the invention may include one or more of the following. The connector component type may include a sink connector component type, or a source connector component type. The connector component type may be configured to be effectively transparent to flows.

In general, in another aspect, the invention features an indirect selector component type which creates a component instance used in a network. The type includes a sink connector for sinking a reference to a flow object which contains a reference to a collection, and a source connector for sourcing a reference to a selected collection flow object which refers to the original collection and to a selection on it.

Implementations of the invention may include one or more of the following. The selection may include zero or any number of elements of the collection. The collection may be of flow objects. A source connector may source a reference to a flow object which is either MO or is a selection from the collection. The flow object may include MO when the selected collection flow object refers to an empty selection and otherwise may include the selection referred to by the selected collection flow object. The selected collection flow object may be sourced to a choose-one component. The choose-one component may make an empty selection or a selection comprising any number of elements of the collection. The choose-one component may include a user interface element. The selection may be expressed in a modification of the selected collection flow object. The indirect selector component may be notified when the selected component flow object is modified. The choose-one component may display identifiers obtained from the elements of the collection. The choose-one component may make a selection based on an event received from the user interface. The choose-one component may make a selection based on the values of the identifiers obtained from the elements of the collection.

In general, in another aspect, the invention features a software application. In the software application, a program array contains objects representing component type descriptions, some component type descriptions of which array may contain references to elements of the array and information about interconnections between these references. The application includes a network of component instances derived from the elements of the program array, including the interconnection information, and a single projection mechanism sufficing to enable a user to edit, debug, and run the application.

All of the elements of the program array may occur uniquely. Each component type in the array may include a set of command behaviors specific to the type of the component. The activation of a command behavior may trigger a behavior, e.g., any behavior of the kind that may be triggered by the picking of a DoIt.

For editing, the elements of the program array may be projected onto the user interface. A designator of each command behavior may be projected onto the user interface and may be selected for activation. For running, user-interface components of the network may be projected onto the user interface based on a program which includes component instances, component type descriptions, and information about pending processes. The information about pending processes may include a processor stack, or a pending-action list used to defer processing of component instances having multiple sinks.

The application may be debugged while running, using the single projection mechanism, by using information about component types and their interconnections obtained from the program array, and using component instance information including flow object information and communication act information obtained from the running program. Flow object information may be projected onto the user interface by means of flow object references in connectors. The projection may be done by user-interface components. The state of a component instance may be projected onto the user interface. The state of the component instance may include the values of settings and of flow objects referenced by the component's connectors.

For debugging, the information about message-passing and flow communication acts may be projected onto the user interface by visual modification of interconnections and components in the network. The information may be projected a step at a time under control by a user. The debugging may be single stepped by pausing the running of the program after each of the message-passing or flow communication acts. The projection mechanism may control editing and running by sending stop, idle, and run messages to the application which then sends these messages to the component instances. The stop messages may invalidate the flow-object references of all connectors. The message passing and flow communication-act behavior of the application may begin upon issuance of the idle message to component instances, which precedes the start point of the application at the time the run message issues.

For running, the stop-idle-run sequence may be sent all at once. For editing and debugging, the stop-idle may be sent together, and the run message may be sent when chosen by a developer. Editing may be permitted after a stop-idle sequence. Activation of command behavior may be permitted after a stop-idle sequence. Adding a connection between component type references during editing may force a flow to occur in the running of the corresponding program. Removing a connection between component type references during editing may force an MO flow. Adding a component type reference to the network may force creation of a corresponding component instance.

In general, in another aspect, the invention features a setting component type for use in a network of references to component types, the setting component type comprising a variable which can have a distinct value for each reference to the setting component type.

Implementations of the invention may include one or more of the following. Each instance of this reference to this type is an owner of a flow object referencing a distinct copy of this reference's value and which sources a reference to this flow object when the instance receives an idle message. The value associated with each reference can be changed, before a network of component instances corresponding to the network containing this reference is encapsulated, by means of the activation of a command behavior of the component type. The value associated with each instance can be changed by means of a transaction register component.

In general, in another aspect, the invention features a command component type for use in a network of references to component types comprising a sink connector and a setting.

Implementations of the invention may include the following features. After a network in which it occurs is encapsulated, the network may impart a command behavior to the resulting composite component type such that the designator of the command behavior is determined by the setting. When the command behavior is activated, the instance of the component type may cause a DoIt flow object referenced by the sink connector of the instance to be picked.

In general, in another aspect, the invention features a method of handling control flow in a network of components, in which a transaction register component manages a transaction object, and flows and message-passing communication acts to and from the transaction register component are used to control actions on the transaction object.

Implementations of the invention may include the following features. The transaction object may contain a current object and a reference to an underlying object. The transaction object may receive an open message which creates a current object which is a copy of the underlying object. The transaction object may accept an abort message, which destroys the transaction object, and a confirm message, which first copies the instance variables of the current object to the underlying object and then destroys the transaction object. After the transaction object is created, the transaction register component may source a reference to a flow object which references the transaction object, the transaction register component being the owner of that flow object. A dialog component may sink a reference to the sourced flow object and may open a dialog projecting onto the user interface the instance variables of the current object of the referenced transaction object and permitting changes which the user makes to these variables in the user interface to be effected directly in the respective instance variables of the current object. The dialog component, upon receiving an abort or confirm event from the user interface, may close the dialog and cause the sending of an abort or confirm message to the transaction object referenced by the flow object, thereby changing the instance variables of the underlying object only if the confirm message is received.

In general, in another aspect, the invention features a user interface component type whose instances have a display-out/event in behavior that is defined entirely by flow objects.

Implementations of the invention may include the following. There may be a combination of component types. The component instance may accept a flow object to be projected onto the user interface, a projector class flow object, and a tool flow object. The projector class flow object may define the appearance of the display. The tool flow object may define the response to user-interface events.

In general, in another aspect, the invention features an item of commerce which includes a description of a component type expressed in an interchange format permitting the component type to be encapsulated hierarchically and referred to within a network defining interrelationships of component types, the component types being arranged to permit references to flow objects to pass into and out of their instances. In implementations of the invention, the component type description may be stored in libraries.

In general, in another aspect, the invention features a computer program comprising a component type. In implementations of the invention, the computer program may be expressed in an interchange format, and may be in a form capable of freestanding execution on a computer.

In general, in another aspect, the invention features an assembly tool which enables a user to store component type descriptions and to manipulate and interconnect references to component type descriptions to form other component type descriptions.

Implementations of the invention may include the following features. The assembly tool may be adapted to run and enable debugging for programs derived from component types. The assembly tool may be arranged to allow generation of an application which is executable independently of the assembly tool. The assembly tool may be arranged to provide a graphical work space enabling a user to manipulate representations of component types to form other component types. The assembly tool may be arranged to accept component type descriptions in an interchange format, and to export component type descriptions in an interchange format. The component type may have aspects defining what can be done with it and the assembly tool may include a restriction mechanism that controls use of different aspects by a holder of the component type.

In general, in another aspect, the invention features a type description component type, an instance of which has a setting whose value references a component type, and a source connector which, when the instance receives an idle message, sources a flow object representing the referenced component type.

In general, in another aspect, the invention features a type invocation component type, an instance of which includes a sink, which accepts a flow object representing a component type, a source which sources a DoIt, the type invocation component instance being the DoIt's server, and other sinks and sources. In implementations of the invention, when the DoIt is picked, an instance of the represented component type may be created; a program based on the represented component type and the instance may be built; stop and idle messages may be sent to the program; inputs derived from flows arriving at the additional sinks of the type invocation component type may be flowed to the corresponding sinks of the instance; a run message may be sent to the program; and any flows sourced by connectors of the represented component instance may be sent to the sinks which are connected to those additional sources of the type invocation component which correspond to the sources of the represented component instance.

Other advantages and features will be demonstrated by the following description and the claims.

DESCRIPTION

The invention employs a conceptually unified quasi-static constraint-network model. The constraint-maintenance protocol employs only unidirectional dataflows, greatly simplifying the design and construction of components, and it is nonlocal.

The nonlocal property of the constraint-maintenance protocol eliminates the need for the application builder's explicit management of bidirectional consistency constraints between related data in widely separated parts of the program network. For example, the practical programming issues associated with maintaining consistency among different displays of the same object value or among object values in databases and multiple displays of these values (even while any of these values might be caused to change) are handled automatically by the nonlocal constraint-maintenance protocol. The practical effect of this automatic maintenance of data consistency across the whole program network is the consequent greater conceptual simplicity of the total design and construction task.

One measure of the power of a construction paradigm which employs the simplification strategies discussed above is whether a programming tool which implements such a construction paradigm can be built using itself. With respect to the similarity-group of display-out event-in systems, this measure of power is rarely achieved. MVC exhibits this power, but MVC is all code. Conceptual systems extensively employing static description, such as VB and Fabrik for example, have not been realized by tools whose internal structures both are instances of these conceptual systems and which can build themselves. The present invention can be used to build a display-out event-in programming tool, based on the invention, which can then build itself.

Table of Contents of Description

Figure List

1 Structure and Behavior of Programs

1.1 Structure of a Program

1.2 Flow Objects

1.3 Communication Acts

1.4 The Routing Communication-act Function

1.5 The Message-passing Communication-act Function

1.6 Interpretation of Flows; The Projection Paradigm

1.7 Interpretation of Picks

1.8 Events

1.9 Interpretation of Notify Owner and Notify Dependent Communication Acts

1.10 Interpretation of Notify Hosts Communication Acts

2 Program Sequence Control

2.1 The Steady and Busy States of Applications

2.2 Sink State Change

2.3 Clear-before-send rule

2.4 An Example of Change Propagation

3 Composite Components

3.1 Primitive and Composite Components

3.2 Connector Components

3.3 Flows Into and Out of a Composite Component

3.4 Summary of Sink Behaviors

3.5 Structure of an Application Program

4 A Fundamental Set of Primitive Components

4.1 Settings

4.2 Collection Components

4.3 Window Components

4.4 Filter Components

4.5 Glue Components

4.6 An Analysis of a Wiring Diagram

5 Component Forms

5.1 Data Structure Definitions

5.2 The Component Forms

5.3 Definitions of Library Forms

5.4 Example of a Library Form

5.5 Definitions of Executable Forms

5.6 Example of an Executable Form

5.7 Definitions of Instance Forms

5.8 Example of an Instance Form

5.9 On the Distinction Between "Wiring Time" and "Run Time"

5.10 Components Which Participate in the Development Process

5.11 Definitions of Editable Forms

5.12 Example of an Editable Form

5.13 What the Wiring Workspace Does

Using Flow Objects for Control

6.1 Transactions

6.2 Dialog Projectors

6.3 An Example of Branching

6.4 Coupling Protocol

6.5 Component Invocation Components

6.6 Tools

6.7 Child Window Projectors

6.8 Example of Projection

7 Example of a Recursive Algorithm

7.1 Program Description vs. Algorithm Description

7.2 A Conditional Component

7.3 Computational Components

7.4 Bootstrapping Recursive Definitions

8 A Component Type Market Model

8.1 Component Type Interchange

8.2 Assembly Tool Structure

8.3 The Structure of Restriction

How The Use of Components Is Restricted

9.1 Licensing of Component-type Aspects

9.2 Forwarding of Licenses

FIGURE LIST

FIG. 1 is a diagram of an example program.

FIGS. 2 and 3 are diagrams of a source connector and a sink connector.

FIG. 4 is a diagram of a flow object.

FIG. 5 illustrates the projection of data onto the user interface.

FIG. 6 illustrates the coupling protocol.

FIG. 7 shows an example program.

FIG. 8 shows the total network of the example program.

FIG. 9 shows the route of the text flow object Z in the example program.

FIG. 10 shows the dependent set of the flow object z.

FIG. 11 shows the dependent set of the flow object Y after the Y button is pushed.

FIGS. 12 and 13 show a Source Connector component and a Sink Connector component.

FIG. 14 shows the effect of a Sink Connector component on a flow.

FIGS. 15 and 16 show the effect of a Source Connector component on a flow with a single wire and multiple wires connected to the corresponding source connector.

FIG. 17 shows a source wired to four sinks for purposes of analysis.

FIGS. 18 and 19 show a generic Setting Source component and a Text Source component.

FIGS. 20 and 21 show an Indexed Collector component and an Indexed Splitter Component.

FIG. 22 shows a Named Splitter component.

FIGS. 23 and 24 show a Direct Selector component and an Indirect Selector component.

FIG. 25 shows a characteristic idiom combining an Indirect Selector component and a choose-one component.

FIG. 26 shows a Map Collection component.

FIG. 27 shows a Main Window component.

FIG. 28 shows a Map Port component.

FIG. 29 shows six Child Window components: Horizontal Palette, Vertical Palette, List Box, Button, Text Edit Box, and Generic.

FIG. 30 shows the port wiring for a main window with three child windows.

FIG. 31 shows a Menu component.

FIG. 32 shows a File Contents Filter component connected to a Map Collection Component.

FIG. 33 shows a Subfiles Filter component and a Subdirectories Filter component.

FIG. 34 shows a Text Distinguisher Filter component.

FIG. 35 shows a Change Distinguisher Filter component.

FIG. 36 shows a To DoIt Filter component.

FIG. 37 shows the combination of a To DoIt Filter component and a Map Collection component acting as a choose-one component.

FIG. 38 shows a Data Change Detector component.

FIG. 39 shows a Pass-through component.

FIG. 40 shows a Register component.

FIG. 41 shows a Boolean Selector component.

FIG. 42 shows a Match component.

FIG. 43 shows a Pick-at-Run component.

FIG. 44 shows a DoIt Sequencer component.

FIG. 45 shows the same example program as FIG. 1.

FIG. 46 shows the outside of the composite component defined by the wiring diagram of FIG. 45.

FIG. 47 shows the use of a button to duplicate the function of double-clicking a list box.

FIGS. 48 and 49 show alternative ways to wire a double-click of a list box and a button to close a window.

FIG. 50 shows a menu of letters used in the naming of forms.

FIG. 51 shows a syntax diagram for library forms.

FIG. 52 shows the general structure of the library form of the composite component defined by the example in FIG. 45.

FIG. 53 shows a table of the subcomponents of the example, with the subcomponent numbers as they appear in the library form.

FIG. 54 repeats the wiring diagram of FIG. 45 with the addition of subcomponent and wire numbers.

FIG. 55 augments the table of FIG. 53 by the addition of the number of sources on each subcomponent.

FIG. 56 adds the <VA>and <LUD>structures to the table of FIG. 53.

FIG. 57 shows the <LWDA>wire array structure.

FIG. 58 shows the complete structure of the library form shown in FIG. 52.

FIG. 59 shows the wiring diagram of an example file content browser.

FIGS. 60 and 61 show the subcomponent array and the wire array of the file browser type description.

FIG. 62 shows the library form of the file browser type description.

FIG. 63 shows the stages of the application of the P() function applied to the file browser.

FIG. 64 shows the <XGA>of the file browser program.

FIGS. 65 and 66 show the X-form type descriptions for the file browser and the file dialog type descriptions.

FIG. 67 shows the overall structure of the <XGA>of the file browser program.

FIG. 68 shows a syntax diagram for instance forms.

FIG. 69 repeats FIG. 64, the gross structure of the file browser program definition <XGA>.

FIG. 70 shows the stages of the application of the I() function applied to the file browser program definition.

FIG. 71 shows a table of the key features of the 21 component instances in the file browser program.

FIGS. 72 and 73 show the instance structures for the two composite components in the file browser: the top-level anonymous component and the file dialog component.

FIG. 74 shows the gross structures of the instance array and the program definition array, with the references between and within them.

FIG. 75 applies the projection paradigm to the process of wiring, debugging, and running a program.

FIG. 76 shows a Command component.

FIG. 77 shows a Probe component.

FIG. 78 shows the wiring diagram of the file browser enhanced by the addition of coordinates for the positions of the components.

FIG. 79 shows the file browser type definition with all E-form information present.

FIG. 80 shows a transaction object and its relationship to its current object and the underlying object.

FIG. 81 shows a Transaction Register component.

FIG. 82 shows the use of a Transaction Register component in the construction of a dialog.

FIG. 83 shows a File Transaction Register component.

FIG. 84 shows an Open Dialog component.

FIG. 85 shows a characteristic idiom combining a Transaction Register component and an Open Dialog component.

FIG. 86 shows an Open Dialog Projector component.

FIG. 87 shows a first approximation to a file-open wiring diagram.

FIG. 88 shows the final form of the file-open wiring diagram after addition of a new composite component.

FIG. 89 shows a Question Box component.

FIG. 90 shows the wiring diagram of the new composite component added to the file-open wiring diagram.

FIGS. 91 and 92 show a Component Description component and a Component Invocation component.

FIG. 93 shows a Display List Child Window component.

FIG. 94 shows four Drawing Tool components.

FIG. 95 shows an example drawing program.

FIG. 96 shows the communication paths among a Projector object, a Projectee object, and a child window.

FIGS. 97 and 98 show a Generic Projector Child Window component and a Projector Engine component.

FIG. 99 shows how the Generic Projector Child Window component and Projector Engine component are wired together.

FIG. 100 shows the most general form of the wiring of the Generic Projector Child Window component and Projector Engine component.

FIG. 101 shows the communication paths among a Tool object, a Projector object, a Projectee object, and a child window.

FIG. 102 shows the wiring diagram of a composite component which implements a conditional functional.

FIG. 103 shows a constant computational component.

FIGS. 104 and 105 show two applications of a unary computational component.

FIG. 106 shows a binary computational component used for multiplication.

FIGS. 107, 108, and 109 show the wiring diagrams of the three function composite components used as inputs to the conditional functional component.

FIG. 110 shows the final definition of the factorial component.

FIG. 111 shows a component market model.

FIG. 112 shows a high-level block diagram of an assembly tool.

FIG. 113 shows, in tabular form, nine aspects of every component type.

FIG. 114 shows the relationships among component producer, component consumer, assembly tool, and component type aspects.

FIG. 115 shows, as an example, a transaction among three component producers and one component consumer involving three component types.

PART 1 STRUCTURE AND BEHAVIOR OF PROGRAMS

Section 1.1 Structure of a Program

A program (also called an application program or application) consists of component instances which are interconnected by wires..sup.1 (Where the context makes the language unambiguous, component instances will be called components.) Each component instance is an instance of some component type. .sup.2 3

.sup.1 The use of italics signifies the first significant occurrence of a term which has a particular meaning. Usually the term is defined, either explicitly or by implication, in connection with its first significant occurrence.

.sup.2 The software model used in the descriptive language is object-oriented-programming. The term "type" is used as the terms "type" or "class" would be used in object-oriented programming. Similarly, "subtype" is used as "derived type" or "subclass" would be used in object-oriented programming.

.sup.3 Object-oriented programming is the source of concepts used in the language of this description; that is not to say that the thing being described is object-oriented programming. However, there is one point of view in which what is described is an extension to object-oriented programming.

FIG. 1 shows a visual rendering of the structure of an example program. The program performs the principal function of a standard file dialog box, namely the coordination of a directory list box and a file list box in assisting the user to find and designate a file anywhere in a hierarchical file system. This example is analyzed in detail in Section 4.6.

Every component has an inside and an outside. The outsides of all components have a similar general plan, whereas the insides of different components might be constructed from different plans.

The construction plan (and, by implication, the functional design) for the inside of a component is determined by the component's type. Component types are divided into two broad categories, primitive and composite (see Section 3.1).

Here is the plan for the construction of the outside of every component. The outside of each component consists solely of zero or more connectors. Each connector is an instance of one of two types: the source connector type, whose instances are source connectors (sources), shown in FIG. 2, and the sink connector type, whose instances are sink connectors (sinks), shown in FIG. 3. The source connector type and the sink connector type are derived from a common connector type. The common connector type prescribes that every connector has a storage register (instance variable) called flow storage, which can hold a value which is either unambiguously invalid (such as a "nil" pointer), or is a reference to a flow object (to be described below). If a connector's flow storage has a valid reference to a flow object, the connector refers to the flow object.

Wire instances (wires) are instances of the wire type. Wires are the means by which components are interconnected. A wire has two ends. In any given program one end of each wire is uniquely identified with ("ends in" or "connects to") some source connector of some component.

The other end of the same wire is identified with some sink connector of some component (almost always a different component from the one at the other end of the wire). Each wire (considered as an object) must be able to supply the identity of the component and sink connector at its sink end.

Every wire must be connected to one sink and one source. Every source may be connected to any number of wires, including zero. Every sink may be connected to zero or one wire, but no other number of wires.

Section 1.2 Flow Objects

The type flow object is an abstract type whose subtype instances contain the objects processed by the program.

Every flow object (i.e., every instance of an instantiating subtype of flow object) has a protocol (i.e., a repertoire of oop messages.sup.4 to which it responds), part of which is common to all flow objects (the common protocol), and part of which is specific to the particular type of which the flow object is an instance.

The common protocol contains, in addition to other messages to be discussed later, messages which return the following values. Unless the method by which a return value is determined is specifically implied by the text below, it may vary from flow object to flow object, and even from time to time for the same flow object. (Terms introduced in this list will be described below.)

1. Characterizing string. A short text string which characterizes the flow object as a member of a type, class, or category.

2. Distinguishing string. A short text string which distinguishes the flow object from other flow objects of the same type, class, or category. Each flow object has an instance variable, called the text distinguisher, which can store such a string; if the variable is empty the string is computed using a rule defined by the type of the flow object.

3. Characterizing icon. One or more small graphics ("icons") which characterize the flow object.

4. Distinguishing icon. One or more small graphics ("icons") which distinguish the flow object. Each flow object has an instance variable, called the icon distinguisher, which can store one or more such icons; if the variable is empty the appropriate

.sup.4 An oop message is a message to an object in the sense of object-oriented programming. icon is computed using a rule defined by the type of the flow object.

.sup.5. Owner. Each flow object has an instance variable which can be invalid, or can contain an ordered pair (reference to component, reference to source connector on component); the component is called the owner of the flow object.

.sup.6. Dependent set. Each flow object has an instance variable which contains a (possibly empty) collection, containing no duplicates, of ordered pairs (reference to component, reference to sink connector on component). The components are called the dependents of the flow object. (A dependent of a flow object is a component which needs to be notified when some aspect of a flow object's value has changed. The owner of a flow object is the component with the responsibility to notify all the dependents when such a change occurs.)

.sup.7. Host set. Each flow object has an instance variable which contains a (possibly empty) collection, containing no duplicates, of references to components called the hosts of the flow object. (A host is a component which participates in some specific interaction with another component.)

The subobject of each flow object consisting of the instance variables named above which are common to all flow objects (namely the text distinguisher, the icon distinguisher, the owner, the dependent set, and the host set), together with the common protocol, is called the wrapper of the flow object.

There is a flow object type whose instances are called MO (meaningless object), and any connector can have a valid reference to an MO.

FIG. 4 shows the data structure of a flow object as it might actually be implemented in a dynamic object-oriented programming system.

The following comments apply to FIG. 4.

1. Every object has an implementation-specific object header, which might be empty in some implementations. Other than the object header, the flow object consists of an array of pointers or handles. (A handle is an implementation-specific designator of a storage-occupying object which is location-invariant, thus permitting the object to be moved while the unchanged handle remains valid.)

2. The arrows point to the objects denoted by the handles. A dotted arrow indicates that a handle might be nil, i.e., it denotes no object (or, in some implementations, it denotes the nil object).

3. Each of the two reference sets might be empty. (The host set is typically empty.)

4. The structure of a component reference is unspecified here.

5. The structure of the thing stored in a connector as a flow object reference is also unspecified here. It might, for example, be a handle.

6. Note that the data object is not in the flow object. This permits multiple flow objects "containing" the same data object. In particular, it permits making copies of flow objects which "contain" the same data object.

7. Each MO is an instance of a unique data type. What distinguishes the type of MO is simply that, under a design rule discussed in Section 2.2, all components must accept MO as a value at all sinks.

8. The object labeled "MO or other object" might not be a data object but might be a reference to a data object. The form of the reference is unspecified. (This additional level of indirection might be required in a distributed-object system.)

Section 1.3 Communication Acts

The behavior of a program is described in terms of communication acts. [Note: in conventional terms, the behavior of a program is described by the changes which occur on its interface(s) to the world outside the program. We will from time to time be relating this external-interface behavior (which we can call external behavior) to the behavior being presently described (which we can call internal behavior).]

The internal behavior of a program is a sequence of communication acts. (There can be generalizations of this model in which some communication acts may be considered to occur concurrently.) Every communication act occurs between two components, one called the sender and one called the receiver.

Each communication act performs one or the other of two distinct communication-act functions: routing and message passing. Of the five distinct types of communication acts, the routing function is performed by the flow communication act, and the message-passing function is performed by the notify owner, notify dependents, notify hosts, and pick communication acts..sup.5

.sup.5 Message-passing communication acts are not oop messages. (They might, however, be implemented using oop messages.) The words "communication act" will be retained in places where they will help to eliminate possible ambiguity of interpretation.

Section 1.4 The Routing Communication-act Function

The total network of any particular program is the directed graph whose nodes are all the components of the program and whose branches are all the wires of the program. The direction of a branch is from source to sink. (The total network looks like the wiring diagram, except that all the connectors of each component are lumped together into a single node. It is possible for the total network of a program to contain cycles, as the example of FIG. 1 does.)

The route of a flow object is a subgraph of the total network such that

1. the nodes of the route are in one-to-one correspondence with that subset of all components, each component of which subset has some connector which refers to the flow object, and

2. the branches of the route are in one-to-one correspondence with that subset of all wires, each wire of which subset has a connector at the source end which refers to the flow object and a connector at the sink end which refers to the flow object.

Flow. Communication acts called flows determine the routes of flow objects, which in turn make the flow objects available at the sinks of certain components for processing. A flow copies a flow object reference from a source connector to a sink wired to that source and makes the receiving component aware of the arrival. The flow object itself is neither moved nor copied. The component containing the source connector may be said to be "sourcing" the flow or the flow object, and the other component may be said to be "sinking" the flow or the flow object.

One or more flows from a particular source connector is implemented as follows.

1. At some point in its processing or creation of a flow object and prior to initiating the flow(s), the sending component must place a flow object reference in the flow storage of this source connector. It does this by sending an assign flow object reference or an assign hosted flow object reference oop message to that source connector, with the flow object reference as a parameter (see below for details).

2. Subsequently, the sending component begins the flow(s) by sending a send flow oop message to the source connector (see below for details).

Assign flow object reference/Assign hosted flow object reference. When a source connector receives an assign flow object reference or assign hosted flow object reference message, it performs the following two steps.

1. It checks whether its flow storage validly references a flow object; if so,

a. (in the case of the hosted variant) it removes any reference to its component from the referenced flow object's wrapper's host set, and

b. for each sink connector wired to it, the source sends this sink an invalidate sink connector oop message (see below for details).

2. Then the source connector puts the flow object reference in the message parameter into its flow storage, making it valid. In the case of the hosted variant, it adds a (nonduplicate) reference to its component to the flow object's wrapper's host set.

Invalidate sink connector. When an invalidate sink connector oop message is received by a particular sink connector on the outside of a particular component, the connector checks whether its flow storage is valid. If not, the operation is complete. If the flow storage contains a valid reference to a flow object,

a. the sink removes any reference to its component from the referenced flow object's host set,

b. the sink removes any reference to its component and itself from the referenced flow object's dependent set,

c. it sends a sink connector invalidated oop message to its component with the following two parameters: the flow object reference in its flow storage, and a reference to itself, and

d. it invalidates its flow storage.

(A component's response to the sink connector invalidated message is discussed in Section 2.2. This message is typically ignored.)

Send flow. The source connector iterates over the collection of wires connected to it, sending, for each wire, a receive flow oop message, with the flow object reference as a message parameter, to the sink connector at the other end of this wire.

Receive flow. The sink connector places the flow object reference into its flow storage. (The flow storage is already invalid.)

The sink connector then sends a flow received oop message, with an identifier of the sink connector as a message parameter, to its component. (A component's response to the flow received message is discussed in Section 2.2. It will be discussed in Section 3.4 that the sink connectors associated with composite components do not behave as described here.)

Section 1.5 The Message-passing Communication-act Function

A communication act message is passed from a sending component to a receiving component. Message passing is defined with respect to a given flow object, and the sender and receiver of the message are both on the route of the flow object..sup.6 Indeed, it is a function of the flow to put in place the component and flow-object references which are used during message passing.

The four message-passing communication acts are notify owner, notify dependents, notify hosts, and pick.

Notify owner. The notify owner communication act is implemented as follows. The sending component sends a notify owner oop message (with optional parameter(s)) to a flow object referenced by one of the component's connectors. That flow object sends an owner be notified oop message (with the owner's source as the first parameter and any other parameter(s) following) to the component referenced in the owner instance variable of its wrapper.

Notify dependents. The notify dependents communication act is implemented as follows. The sending component (typically the flow object's owner) sends a notify dependents oop message (with optional parameter(s)) to a flow object referenced by one of the component's connectors. For each (component, sink) element in its wrapper's dependent set, the flow object sends a dependent be notified oop message (with the named sink as the first parameter and any other parameter(s) following) to the referenced component.

.sup.6 Note that the route of a flow object serves to define at run time the scope of candidate recipients of a message-passing communication act analogously to the way, in a dynamic object-oriented programming language, the ancestor-class chain of the receiving object of an oop message performs this function.

A dependent of a flow object is a component which needs to be notified when some aspect of a flow object's value has changed. (The additional parameters of the dependent be notified message might contain specific information about what aspect of the flow object has changed.)

Notify hosts. The notify hosts communication act is implemented as follows. The sending component sends a notify hosts oop message to a flow object referenced by one of the component's connectors. The first parameter of the notify hosts message is the name of the oop message to be sent to the receiving component(s); there may be additional parameter(s). For each element in its wrapper's host set, the flow object sends to the component named in this element the message whose name is the first parameter (with any additional parameter(s) attached to the message). If the host component does not recognize the message, this is not an error, simply a null operation. (During this iteration, each component should receive this message at most once; this is assured by the no-duplicate property of the host set.)

The designer of a component decides whether the component is to be a host of a flow object which arrives at a particular sink or which it is sourcing at a particular source. If so:

1. If the connector is a source, the component uses the assign hosted flow object reference variant when setting up a flow out of the source.

2. If the connector is a sink, the component sends an identify host oop message to the sink. This adds a (nonduplicate) reference to the component to the referenced flow object's wrapper's host set.

Pick. The pick communication act is associated only with flow objects of the type DoIt (pronounced "do it"); it is implemented as follows. The sending component sends a pick oop message (with optional parameter(s)) to a DoIt flow object referenced by one of the component's connectors. The DoIt flow object contains instance variables which reference the receiving component (called the Dolt server) and the name of the message to be sent to the DoIt server, with space for additional parameters. In addition, a DoIt has a Boolean instance variable which carries enabled/disabled state information. When the DoIt receives a pick oop message, if and only if the DoIt is enabled, the named message, with the optional parameters attached, is sent to the DoIt server.

Section 1.6 Interpretation of Flows; The Projection Paradigm

It is important to note that a flow goes in only one direction on each wire, from source to sink. Informally, if components are drawn with sinks on their left and sources on their right, this means that the general movement of flows is left-to-right across the wiring diagram of the program. The components in which flow objects end up are often user-interface components. This is a major aspect of the relationship between internal behavior and external behavior: flows push data (more correctly, flows push references to flow objects referencing data) out to the user interface, where the flow objects' data are presented to the user. (See FIG. 5.) For example, a flow object which carries a body of formatted text may end up in a component whose function is to display formatted text in a child window. (Keep in mind that flow objects do not move; only references move.)

This interpretation in which the purpose of flows is to push data out to the user interface will here be called the "projection paradigm," which suggests that the program is analogous to a photographic projector projecting data onto the user-interface "screen" at the right side of the wiring diagram. The following two points hold for the projection paradigm. (Much of the subsequent discussion in this description is directed to making the following two points concrete.)

1. The projection paradigm is a generally applicable model of applications with display-out/event-in user interfaces.

2. Applying the projection paradigm to programming tools leads to a model of program development which is distinct from the sequential file-processing model associated with text editors, compilers and linkers. The projection-based model does not contain the traditional distinction between the time at which program preparation occurs and the time at which the prepared program is run. Rather, these two operations can be thought of as occurring concurrently. Thus, the projection paradigm contains within it a theory of program development in which "source-level debugging" occurs naturally.

A major distinction of this invention is the way the bidirectional control and communication requirements of display-out/event-in applications are implemented within a formal system with the following elements.

1. Components and the way they are wired determine unidirectional flows.

2. The unidirectional flows determine which components make reference to which flow objects, and which flow objects make reference to which components.

3. Control and communication occurs across chains of these reference paths, from component to flow object and from flow object to component, in such a way that the process of component design is strongly decoupled from the process of component application.

Section 1.7 Interpretation of Picks

A DoIt is a relatively simple flow object for signaling to a DoIt server that a process specified by the DoIt is to be invoked.

In the terms of the projection metaphor, DoIts often end up in user interface components which implement such user-interface control elements as buttons and menu items. A DoIt can be viewed as a mechanism by which a server component which implements an event-triggered function projects itself onto the user interface. The enabled/disabled instance variable of the DoIt shows up in the user-interface element as "graying" or "disabling" of a button or menu item. When the user-interface item is enabled, pushing the button or picking the menu item initiates the server component's function. (Section 6.3 discusses an example in which variable routing of DoIts accomplishes what is called branching in conventional programming.)

Section 1.8 Events

An event is not a communication act, but is similar in that it has a sender and a receiver. The sender of an event, however, is outside the program structure described here (for example, the sender might be the operating system in whose environment the program operates). The receiver of an event is a component. For example, a user-interface component whose function is to show a button and which has a sink connector which receives a DoIt, picks that DoIt in response to receipt of a button-push event from the user-interface management system. It is important to note that the possibly quite complex sequence of communication acts generated by that pick has completed before control returns to the button component from the pick oop message.

Section 1.9 Interpretation of Notify Owner and Notify Dependent Communication Acts

Owner and dependent notifies are used to propagate data changes in such a way as to maintain consistency throughout the wiring diagram and the user interface. For example, user-interface components which project data onto the user interface are dependents of the flow objects containing those data. When such a component receives a dependent be notified message, it looks at the flow object referred to in the flow storage of the connector specified in the message and refreshes the user interface.

User-interface components can also change data. For example, a dialog box can cause an element of a database to be changed. If the change at the dialog is confirmed (the OK button is pushed) the dialog sends a notify owner message to the flow object being projected onto the dialog. The owner receives from the flow object an owner be notified message, and it sends a notify dependents message back to the flow object. Note that the owner does not need to change the data; the dialog has already done that.

The "coupling protocol" with which owner and dependent notifies maintain consistency of data across a wiring diagram is discussed in more detail in Section 6.4.

To avoid race conditions or duplicate updating, each dependent sending a notify owner sets a local blocking flag at the beginning of the notify owner communication act and resets the flag after control returns from that communication act, the purpose of which blocking flag is to disable the response of the component to the dependent be notified message which the owner may cause to be issued. The duration of the notify owner message sent by the dialog component contains entirely within it the durations of all dependent be notified messages sent by the owner.

A component is never an owner and a dependent of the same flow object.

FIG. 6 shows a typical application of the coupling protocol. There are components A, B, C, D, and E, and flow objects x and y. A is owner of x and B is owner of y. The little squares next to the connectors reveal the contents of flow storage. The sequence of steps is as follows.

1. C changes x directly and has recomputed its outputs based on the new value of x. C is thus obliged to notify the world. It does this by sending message a: notify owner to x.

2. x knows that A is its owner, so sends message b: owner be notified to A.

3. Because the owner be notified message named the source connector referencing the flow object which had changed, A knows to send c: notify dependents to x.

4. x knows that its dependents are C and D, so sends out messages d and e: dependent be notified to C and D.

5. C does not act on the message because it has set its blocking flag before sending message a. (C will reset its blocking flag after control returns from message a.) D, however, has just learned about the change to x, so recomputes its outputs based on the new input.

Section 1.10 Interpretation of Notify Hosts Communication Acts

Host notification protocols are used to handle whatever action-at-a-distance communication between components is not accommodated by the preceding communication acts. In effect, host notification protocols cover those (relatively rare) forms of intercomponent coupling which are not naturally accommodated by the projection metaphor. An example will be discussed in Section 6.6.

Part 2 Program Sequence Control

Section 2.1 The Steady and Busy States of Applications

Each component spends most of its time in reset state, sitting around waiting for a communication act. When it gets such a stimulus, it responds immediately. This component-type-specific response can include sourcing flow objects, performing message-send communication acts, and (for user-interface or system-interface components) changing the appearance of the application or sending messages to the environment. Similarly, if a component is defined to be sensitive to certain kinds of events, it responds immediately to those events, with the same repertoire of potential responses. Thus, the application spends most of its time in a steady state, and then occasionally it is very busy pushing things around (the busy state), then it gets quiet again in steady state.

During the application's steady state, when all components are in reset state, the relationships between inputs and outputs of components are defined by the specifications of the components. During the busy state, component input-output relationships are in transition. Here is a fundamental property of the model: The only thing that causes the application to switch from the steady state to the busy state is receipt of an event. (Explanation: If it were anything other than an event, it would have come from a component inside the application, which is then, by definition, already in busy state.)

In a processing environment with a single processor, the behavior of an application is sequential. That is, if a component has a list of communication acts to perform in response to an input, it does them sequentially, waiting for the completion of the response to each act before beginning the next act. Moreover, each communication act that it performs does not complete until all the actions which that communication act provokes are complete, Thus, if component A sends a flow to component B (where B has only one sink and therefore responds immediately to the flow; see below), the lifetime of the response behavior of component B is considered to be nested inside the lifetime of the flow act performed by component A. Thus, during the busy state all responses are nested inside the response of a component which is responding to an event. Such nesting implies a stack of communication acts. Since in a single-processor system an event-receptive component will only receive an event when the application is in the steady state, event responses are always and only the outermost responses in the response stack.

Section 2.2 Sink State Change

There are two cases, in which a component is notified that the state of one of its sinks is changed, that we must consider.

1. Propagation of new invalidity of an existing input.

The component receives a sink connector invalidated oop message from one of its sinks. This is the case when an input becomes invalid, and the previously valid input has caused the computation of outputs which are now likely to be incorrect. By design, the sink connector invalidated is always followed by a flow received oop message (see Section 1.4).

Normally, the component ignores the former and responds to the latter.

2. Propagation of a new valid input. The component receives a flow received message from one of its sinks, or the component receives a dependent be notified message with that sink as the first parameter. These two conditions lead to what is called input change. This is the case when an input is made valid with a flow object for which the output response of the component must be computed. The following discussion covers this case.

Flow received. If by design the component is a dependent of the flow object arriving at the sink, the pair (component, sink) is added to the flow object's wrapper's dependent set. Then, continue at input change.

Dependent be notified. Continue at input change.

Input change. If a component has only one sink connector, the component computes its new output(s) immediately (including side effects such as user-interface changes). Then, for the new output value at each source, the component executes the new-output procedure.

New-output procedure. If (1) the reference to the flow object of the new output at the source connector is unchanged, and (2) the source was valid previous to this new output, then the component sends a notify dependents message to the flow object referenced by the source. Otherwise, the component initiates a flow from the source using the new output value.

What if the component has more than one sink? Because of sequentiality, it will receive input changes one at a time. When does it respond to all the input changes which it is going to get? Neither of the following assumptions about the arrival of input changes is necessarily a valid assumption.

1. The component knows which subset of its sinks is going to receive input changes during this particular busy state. (For example,.sup.7 during a particular busy state a Direct Selector component might receive a new index at its index sink and might, or might not, receive a new collection at its collection sink. Furthermore, if it receives both, there will be a transient nonsense condition after the first, and before the second, receipt.)

2. The component knows in what order the input changes will arrive.

Therefore, the component does not know, by itself, when the "last" input change has arrived so it can begin its response.

Inputs to some sinks of multi-sink components can properly lead to immediate responses. For example, by design, input to either sink of a List Box component can properly be processed immediately, whereas input to a sink of a Collector with more than one sink wired should not necessarily be processed immediately. The following discussion concerns the latter case, when a component receives an input change, and the computation in response to that input change requires at least one well-defined input at another sink.

.sup.7 The forward references to yet-to-be-defined component types can be ignored on the first reading.

Here is how the response to an input change of a multiple-sink component is initiated. There is a pending-action list associated with the program. Each multi-sink component which, because of its design, may need to wait for multiple inputs, contains a single procedure which responds to the set of sink inputs after all inputs which are going to change have changed; this procedure is called the component's complete-input-response procedure. When such a multi-sink component receives an input change with respect to a sink connector, the component adds a reference to itself to the end of the program's pending-action list. (The list does not contain duplicates; any attempt to add a duplicate to the list will do nothing.) That's all the component does. (The sink connector, of course, has stored a valid reference to the received flow object.) The component has now left reset state and is in pending state.

The program is an object which consists of a (typically composite) component (see Section 3.5), plus the pending-action list.

Unwind-pending procedure. The program has an unwind-pending procedure which does the following.

1. Examine the pending-action list. If it is empty, exit the procedure.

2. Otherwise, remove the first component reference from the pending-action list.

3. Execute the complete-input-response procedure of the referenced component.

4. Go back to step 1.

Note that step 3 can add to the pending-action list, so a definition of the unwind-pending procedure which simply iterates through a snapshot of the list would be incorrect.

Complete-input-response procedure. This is the general outline of every component's complete-input-response procedure.

1. The component examines whether a computation of outputs can be performed with the existing set of valid sinks. If so, the computation is performed (including side effects such as user-interface changes), the new-output procedure is performed for each source with a new output, the component returns to reset state, and the procedure exits.

2. Otherwise, the component adds a reference to itself to the end of the pending-action list, the component remains in pending state, and the procedure exits.

The program's unwind-pending procedure is called at the end of the event-response procedure in each component which is event-sensitive.

Event-response procedure. Here is what happens when an event arrives at an event-sensitive component.

a. The application is in steady state before the event-sensitive component receives the event. The transition to busy state occurs when the operating system gives control to the event-sensitive component.

b. The response of the component to the event is to execute a sequence of one or more communication acts, as well as possible component-specific processes (such as updating a user-interface display).

c. At the end of this sequence of acts the pending-action list may be nonempty. If so, that means that there are some multisink components which are in pending state. To negate this condition, the event-sensitive component always calls the program's unwind-pending procedure. If the program is correct, the net effect of calling the unwind-pending procedure is to empty the pending-action list and to leave all components in the reset state.

d. Finally, control is returned to the operating system, which return of control defines the end of busy state and the beginning of steady state.

The plan presented here guarantees that each component will be left in reset state when the application re-enters steady state. However, a nonterminating loop, in which a component keeps adding itself to the pending-action list because it does not have sufficient valid inputs, is possible. This means that the inputs to the component which keeps adding itself to the pending-action list are incorrectly wired.

This nonterminating loop condition can be avoided by adopting a component design rule which requires all components which can cause such a nonterminating loop

1. to accept and meaningfully respond to MO on all sinks, and

2. to terminate the response to every input change in reset state, sourcing MO as necessary where meaningful outputs cannot be computed.

Under this design rule the busy state will always terminate; the cost of the design rule is the possibility of some spurious recalculations. Also under this design rule, flashing can be minimized by requiring that user-interface components not change their displays when receiving MO for display.

This design rule is assumed in the following discussions of specific components. Under this design rule, the semantics of MO are as follows: a component reacts to an MO input at a sink the same as if that sink's flow storage were invalid.

Section 2.3 Clear-before-send Rule

Receipt of an oop message resulting from a pick, notify owner, or notify hosts is not a sink state change in the above sense. In general, a component responds immediately to receipt of such a message; however, flows may need to be complete before the response is begun. (The use of a DoIt for synchronization, for example, requires that all flows be complete before the DoIt begins its action.) For this reason we adopt the clear-before-send rule.

Clear-before-send rule. Every component which initiates a message-passing communication act must first call the program's unwind-pending procedure. (The exception occurs when it is known that no component can be in pending state, for example, the button component which picks a DoIt immediately after receiving an event.)

Thus, the program's unwind-pending procedure is called under two conditions:

1. as the result of application of the clear-before-send rule, and

2. at the end of the event-response procedure in each event-sensitive component.

Section 2.4 An Example of Change Propagation

FIG. 7 shows a display captured from an assembly tool, with the wiring diagram above and the window created by the running program below. (A full understanding of this example will require a second reading after a reading of the component definitions in Part 4.)

The three strings, "X", "Y", and "Z", sourced by the three Text Source components at the left are grouped into a collection by the left-hand Collector component. Their three text distinguishers, X, Y, and Z, show up in the child window produced by the Horizontal Palette component (at the top). In the window displayed by the running program, the Z button is depressed, causing the third element of the collection to show up in the text entry child window, seen below the palette in the running-program window.

FIG. 8 shows the total network of the program. (The components are labeled informally.)

FIG. 9 shows the route of the text flow object Z. Notice that there is no line between the collector and the selector, because what flows between them is a collection flow object, not any element of the collection.

The dependent set in the wrapper of the text flow object Z looks like FIG. 10 (the components and connectors are labeled informally).

The Text Entry component has made itself a dependent of the flow object which arrives at its sink because it must be notified if the text value changes, in order to update the display in its child window.

Now assume that the user clicks the Y button of the palette. The environment's user-interface management system (or the Palette component, or a combination of them) causes the middle button to appear depressed; the Selector, as the owner of the collection which the Palette component sinks and displays, receives from the Palette component (indirectly, via the (X,Y,Z) selected collection flow object) an owner be notified message, which causes it to conclude that it must change its selection from the third to the second element of its input list. Because the Selector is a one-sink component, it directly executes a new-output procedure with respect to its second source connector.

Here are the steps of the new-output procedure. Since a new flow object reference is to be put into the lower source, the Selector sends an assign hosted flow object reference oop message to this source. (An example showing why the Selector makes itself a host of its selected output is given in Section 6.6.) As part of the execution of this message, the source removes the reference to the Selector component in the host set of the wrapper of text flow object Z, and sends an invalidate sink connector oop message to the sink of the Text Entry component, which causes the following actions (see Section 1.4).

1. The sink connector removes the reference to the Text Entry component and itself in the dependent set of the wrapper of text flow object Z (see FIG. 10), emptying the set. Thus, the Text Entry component is no longer a dependent of text flow object Z.

2. The sink connector sends a sink connector invalidated oop message to the Text Entry component, which does nothing.

3. Then the sink connector invalidates its flow storage.

Then the assign hosted flow object reference oop message puts a reference to the newly selected flow object (text flow object Y) into the flow storage of the Indirect Selector component's second source connector. It also adds a reference to the Selector component to the host set of the wrapper of text flow object Y.

Then the Selector component sends a send flow oop message to its second source connector. This sends a receive flow message (with a reference to text flow object Y as a parameter) to the sink of the Text Entry component. The sink then sends a flow received oop message to the Text Entry component, with a parameter which identifies the sink.

The response to the flow received oop message, from Section 2.2, is as follows.

1. The Text Entry component makes itself a dependent of text flow object Y. It does this by adding (component, sink) to text flow object Y's wrapper's dependent set, so that the latter looks like FIG. 11.

2. The component then updates the display with the new data.

Part 3 Composite Components

Section 3.1 Primitive and Composite Components

The program definition structures described above can be called wiring diagrams. The description of Parts 1 and 2 has dealt entirely with the outsides of components and with communication-act behaviors.

The inside of each component determines how that component behaves in response to the communication acts that it receives. The way the inside of a component is built may be called the implementation of the component.

Component implementations (hence, component types) fall into two broad categories.

1. The implementation of a primitive component is defined outside this model. For example, a component might be implemented using a procedural language available to a programming environment.

2. A composite component is implemented with a wiring diagram.

The following discussion describes how a wiring diagram is considered to be encapsulated, resulting in the definition of a composite component type, from which instances are created whose responses to communication acts are defined entirely by the wiring diagram. The outside of a composite component produced by encapsulation follows entirely the description of Part 1. The inside of the composite component is the wiring diagram..sup.8

Section 3.2 Connector Components

There are two primitive component types which participate in a special way in the definition of encapsulation; these are called connector component types. (Note that these are component types and are not the connector types described in Part 1.) There is a source connector component type and a sink connector component type. These primitive component types define the functional relationships between the wiring diagram inside a composite component and the wiring diagram outside the composite component.

Connector components play the role of formal parameters in procedural abstraction, formally constraining what about the inside can be known from the outside. There is a one-to-one correspondence between the set of connector components in the wiring diagram inside a composite component (which wiring diagram defines its implementation). and the set of connectors on the outside of that composite component.

1. Each source connector primitive component contains one sink connector (the small circle on the left of FIG. 12). The source connector primitive component corresponds to one source connector on the outside of the composite component. The name box at the

.sup.8 Notice that, because of these properties, the rules of program structure define an extensible program-description language. bottom of the icon establishes the correspondence between this connector component and a label associated with the outside connector. The hatched vertical bar is intended to suggest the wall between the inside (on the left) and the outside (on the right) of the composite component. The large circle on the right is nonfunctional; it is meant to suggest the corresponding source on the outside of the wall.

2. Each sink connector primitive component contains one source connector (the small circle on the right of FIG. 13). The sink connector primitive component corresponds to one sink connector on the outside of the composite component. The name box at the bottom of the icon establishes the correspondence between this connector component and a label associated with the outside connector. The hatched vertical bar is intended to suggest the wall between the inside (on the right) and the outside (on the left) of the composite component. The large circle on the left is nonfunctional; it is meant to suggest the corresponding sink on the outside of the wall.

The example of Section 1.1 shows a source connector component in a wiring diagram which defines (the inside of) a composite component.

Section 3.3 Flows Into and Out of a Composite Component

Each connector component on the inside directly communicates with its corresponding connector on the outside, as follows.

Informally, the wall separating the inside and the outside of a composite component can be considered to be removed, and the wire(s) connecting an outside connector and the wire(s) connecting the corresponding inside connector component can be considered to be the same wire(s). We consider the following two cases.

1. Flows sinked by a composite component. Every flow received by a sink connector of a composite component immediately initiates a flow sourced by the source connector of the corresponding inside sink connector component, with the same flow object.

The wrapper of the flow object is unchanged. See FIG. 14.

2. Flows sourced by a composite component. Every flow received by the sink connector of an inside source connector component immediately initiates a flow sourced by the corresponding outside source connector, with the same flow object. The wrapper of the flow object is unchanged. See FIG. 15.

In the second case there is an additional possibility to consider. The outside source connector can connect to more than one sink via more than one wire, one wire to each outside sink. In this case, we consider that the inside source is directly wired to each of the outside sinks, via the dotted wires in FIG. 16.

The above paragraphs completely define encapsulation. Note that composite components are not even seen by message-passing communication acts. That is, message-passing communication acts pass from primitive component to primitive component, passing transparently through the walls of composite components as necessary. This observation has the following consequences.

1. A composite component is never the owner of a flow object.

2. A composite component is never a dependent or host of a flow object.

3. Every