Method for starting processing of an iconic programming system

• US 5,313,574 A
• Filed: 10/24/1991
• Issued: 05/17/1994
• Est. Priority Date: 06/13/1990
• Status: Expired due to Term

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Beethe, Douglas C.
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Breene, John E.
• Application Number:
  US07/782,220
• Time in Patent Office: 936 Days
• Field of Search: 395/155-161, 395/375, 395/650, 395/275, 395/700, 340/709-710, 340/721, 340/723, 364/488-491, 364/474.24, 345/157, 345/163
• US Class Current: 715/763
• CPC Class Codes: G06F 8/34 Graphical or visual programming
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A iconic programming system process represented by a directed graph of icons and connections. When a user starts execution of the iconic system, the system first separates the icons into a list of threads starting with icons at the highest level of the graph. Icons at lower levels of the graph, such as icons within subprograms or virtual threads, will be placed on a thread when the subprogram or virtual thread is started. Virtual threads contain all icons connected to the output of an iteration icon. Each thread is processed by selecting a start icon, or by randomly selecting an unconstrained icon if no start icons are present. Processing continues by processing each icon which has all data input available. Each of the threads is processed by processing one icon per thread in each cycle, until all icons have been processed.

Claims

1. In an iconic programming system having multiple icons executing in a computer system, wherein each icon in said programming system may have zero or more data input connections and zero or more data output connections, and wherein said icons are graphically connected together by a user of the computer system graphically connecting data output connections to data input connections to form a network of icons, a computer implemented method for processing said icons of said network to perform data processing functions represented by said icons, said computer implemented method for processing comprising the steps of:

(a) programmatically examining all icons within said network and discontinuing processing if all data input connections of all said icons are not connected to a data output connection of another icon;

(b) programmatically examining all icons within said network and discontinuing processing if any data input connection of any of said icons is connected to a data output connection of more than one other icon;

(c) programmatically examining all icons within said network and programmatically scheduling all start icons in said network to be processed before any other icons are processed;

(d) when said network contains no start icons, randomly scheduling all icons having no data input connections to be processed before any other icons are processed;

(e) when processing an icon, programmatically scheduling, for processing, all icons connected to data output connections of said icon being processed;

(f) when an icon is being processed, and said icon contains data input connections that have not received data, either from a current or previous execution of the icon supplying data, discontinuing processing of said icon; and

(g) processing each said icon of said network of icons after said icon is scheduled and said icon has received data on all said input connections of said icon.

2. The computer implemented method for processing of claim 1 wherein said step (c) further comprises the step of examining said network and discontinuing processing if said network contains one or more feedback loops, wherein a data output of a first icon connects directly or through at least one other icon to a data input of said first icon, and said network does not contain at least one start icon.

3. In an iconic programming system having multiple icons executing in a computer system, wherein each icon in said programming system may have zero or more data input connections, zero or more data output connections, an optional sequence input connection and an optional sequence output connection, and wherein said icons are graphically connected together by a user of the computer system graphically connecting data output connections and sequence output connections of icons to data input connections and to sequence input connections of other icons to form a network of icons, a computer implemented method for processing said icons of said network to perform data processing functions represented by said icons, said computer implemented method for processing comprising the steps of:

(a) programmatically placing all start icons in said network into a pending queue to cause said start icons to be processed before processing any other icons;

(b) when said network contains no start icons, randomly placing all icons having no data input connections into said pending queue to cause said icons having no data input connections to be processed before processing any other icons; and

(c) processing a next icon from said pending queue comprising the steps of

(c1) if said next icon has a sequence input connection and said sequence input has received a signal from a sequence output connection of another icon, and each data input connection of said next icon has had data transferred to said data input connection from a data output connection of another icon, processing said next icon comprising the steps of

(a) programmatically executing any data processing functions defined for said next icon,

(b) transferring output data, created by programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of said next icon, and

(c) programmatically placing all icons connected to said data output connections of said next icon into said pending queue for subsequent processing, and

(c2) if said next icon has no sequence input connection and each data input connection of said next icon has had data transferred to said data input connection from a data output connection of another icon, processing said icon comprising the steps of

(c2a) programmatically executing any data processing functions defined for said next icon,

(c2b) transferring output data, created by programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of said next icon, and

(c2c) programmatically placing all icons connected to said data output connections of said next icon into said pending queue for subsequent processing.

4. The process of claim 3 wherein each icon in said programming system may further have zero or more control input connections, and wherein step (c) of said computer implemented method for processing further comprises the step of:

(c3) when said next icon has input on a control input, programmatically executing any data processing functions defined only for said control input.

5. The process of claim 3 wherein each icon in said programming system may further have zero or more execute input connections, and wherein step (c) of said computer implemented method for processing further comprises the step of:

(c3) if said next icon has received data on an execute input, processing said next icon comprising the steps of

(c3a) programmatically executing any data processing functions defined for said next icon,

(c3b) transferring output data, created programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of said next icon, and

(c3c) programmatically placing all icons connected to said data output connections of aid next icon into said pending queue for subsequent processing.

6. The process of claim 3 further comprising the following steps wherein the following step (c3) is performed after step (c2) and wherein the following steps (d) through (i) are performed after step (c3):

(C3) after an icon is processed, programmatically placing said icon at a top location on a done stack;

(d) repeating step (c) until said pending queue is empty;

(e) removing a top icon from a top location of said one stack;

(f) programmatically sending a sequence signal to all icons connected to a sequence output of said top icon;

(g) programmatically placing all icons connected to said sequence output of said top icon into said pending queue;

(h) if said pending queue is not empty, continuing with step (c); and

(i) if said done stack is not empty, continuing with step (e).

7. The process of claim 3 wherein step (a) further comprises the step of:

(a1) programmatically examining said network of icons and discontinuing processing if said network of icons contains one or more feedback loops, wherein a data output connection of a first icon is connected directly or through at least one other icon to a data input connection of said first icon, and said network of icons does not contain at least one start icon.

8. In an iconic programmatic system having multiple icons executing in a computer system, wherein each icon in said programming system may have zero or more data input connections, zero or more data output connections, an optional sequence input connection and an optional sequence output connection, and wherein said icons are graphically connecting together by a user of the computer system graphically connecting data output connections and sequence output connections of icons to data input connections and to sequence input connections of other icons to form at least one network of icons, a computer implemented method for processing said icons of said network to perform data processing functions represented by said icons, said computer implemented method for processing comprising the steps of:

(a) programmatically separating said icons into a list of connected icon threads comprising the steps of

(a1) selecting a first icon for a thread,

(a2) selecting all icons connected to data output connections or sequence output connections of said first icon for said thread,

(a3) repeating step (a2) for all icons selected in step (a2), and

(a4) repeating steps (a1) through (a3) if unselected icons remain in said network of icons;

(b) programmatically creating a pending queue and a done stack for each of said threads;

(c) programmatically placing all start icons selected for each of said threads into said pending queue for said thread;

(d) when a thread contains no start icons, randomly placing all icons in said thread that have no data input connections into said pending queue for said thread;

(e) selecting one of said threads for processing;

(f) if said pending queue of said selected thread is not empty, selecting a next icon from said pending queue and processing said next icon comprising the steps of

(f1) if said next icon has a sequence input connection and said sequence input connection has received a signal from a sequence output connection of another icon, and each data input connection of said next icon has had data transferred to said data input connection from a data output connection of another icon, processing said next icon comprising the steps of

(f1a) programmatically executing any data processing functions defined for said next icon,

(f1b) transferring output data, created by programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of said next icon, and

(f1c) programmatically placing all icons connected to said data output connections of said next icon into said pending queue for subsequent processing,

(f2) if said next icon has no sequence input connection and each data input connection of said next icon has had data transferred to said data input connection from a data output connection of another icon, processing said next icon comprising the steps of

(f2a) programmatically executing any data processing functions defined for said next icon,

(f2b) transferring output data, created by programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of said next icon, and

(f2c) programmatically placing all icons connected to said data output connections of said next icon into said pending queue for subsequent processing, and

(f3) if said next icon was processed by step (f1) or step (f2), placing said next icon at a top location on said done stack of said selected thread;

(g) if said pending queue for said selected thread is empty and said done stack of said selected thread is not empty, processing said thread comprising the steps of

(g1) removing a top icon from a top location of said done stack,

(g2) programmatically sending a sequence signal to all icons connected to a sequence output connection of said top icon, and

(g3) programmatically placing all icons connected to said sequence output connection of said top icon on said pending queue of said selected thread; and

(h) repeating steps (e) through (g) until all pending queues and all done stacks created in step (b) are empty.

9. The process of claim 8 wherein step (d) further comprises the step of:

(d1) programmatically examining each of said threads and discontinuing processing if any thread contains one or more feedback loops, wherein a data output connection of a first icon connects directly or through at least one other icon to a data input connection of said first icon, and said thread does not contain at least one start icon.

10. In an iconic programmatic system having multiple icons executing in a computer system, wherein each icon in said programming system may have zero or more data input connections, zero or more data output connections, an optional sequence input connection and an optional sequence output connection, and wherein said icons are graphically connected together by a user of the computer system graphically connecting data output connections and sequence output connections of icons to data input connections and to sequence input connections of other icons to form at least one network of icons, a computer implemented method for processing said icons of said network to perform data processing functions represented by said icons, said computer implemented method for processing comprising the steps of:

(a) programmatically separating said icons into a list of connected icon threads comprising the steps of

(a1) selecting a first icon for a thread,

(a2) selecting all icons connected to data output connections or sequence output connections of said first icon for said thread,

(a3) repeating step (a2) for all icons selected in step (a2), and

(a4) repeating steps (a1) through (a3) if unselected icons remain in said network of icons;

(b) programmatically creating a pending queue and a done stack for each of said threads;

(c) programmatically placing all start icons selected for each of said threads into said pending queue for said thread;

(d) when a thread contains no start icons, randomly placing all icons in said thread that have no data input connections into said pending queue for said thread;

(e) selecting one of said threads for processing;

(f) if said pending queue of said selected thread is not empty, selecting a next icon from said pending queue and processing said next icon comprising the steps of

(f1) if said next icon is an iteration icon, placing all icons connected, directly or through at least one other icon, to data output connections of said next icon into a virtual thread, blocking any further processing of said selected thread, placing said virtual thread onto said list of threads, selecting said virtual thread for processing, then continuing with step (f),

(f2) if said next icon is a subprogram icon, placing all icons below said subprogram icon into a subthread, blocking any further processing of said selected thread, placing said subthread onto said list of threads, selecting said subthread for processing, then continuing with step (f),

(f3) if said next icon has a sequence input connection and said sequence input connection has received a signal from a sequence output connection of another icon, and each data input connection of said next icon has had data transferred to said data input connected from a data output connection of another icon, processing said next icon comprising the steps of

(f3a) programmatically executing any data processing functions defined for said next icon,

(f3b) transferring output data, created by programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of aid next icon, and

(f3c) programmatically placing all icons connected to said data output connections of said next icon into said pending queue for subsequent processing, and

(f4) if said next icon has no sequence input and each data input connection of said next icon has had data transferred to said data input connection from a data output connection of another icon, processing said next icon comprising the steps of

(f4a) programmatically executing any data processing functions defined for said next icon,

(f4b) transferring output data, created by programmatically executing said data processing functions defined for said next icon, to all icons connected to data output connections of said next icon, and

(f4c) programmatically placing all icons connected to said data output connections of said next icon into said pending queue for subsequent processing, and

(f5) if said next icon was processed by step (f3) or step (f4), placing said icon at a top location on said done stack of said selected thread;

(g) if said pending queue of said selected thread is empty and said done stack of said selected thread is not empty, processing said thread comprising the steps of

(g1) removing a top icon from a top location of said done stack of said selected thread,

(g2) programmatically sending a sequence signal to all icons connected to a sequence output connection of said top icon, and

(g3) programmatically placing all icons connected to said sequence output connection of said next icon on said pending queue of aid selected thread;

(h) if said pending queue of said selected thread is empty and said done stack of said selected thread is empty, processing said thread comprising the steps of

(h1) if said selected thread is a virtual thread, removing said selected thread from said list of threads and unblocking said thread containing said iteration icon from which said virtual thread was created, whereby said thread containing said iteration icon is allowed to continue processing, and

(h2) if said thread is a subthread, unblocking said thread containing said subprogram icon that called said subthread and placing said subprogram icon on said done stack, whereby said thread containing said subthread icon is allowed to continue processing; and

(i) repeating steps (e) through (h) until all said pending queues and all said done stacks of all said threads are empty.

11. The process of claim 10 wherein step (d) further comprises the step of:

(d1) programmatically examining each of said threads and discontinuing processing if any thread contains one or more feedback loops, wherein a data output of a first icon connects directly or through at least one other icon to a data input of said first icon, but does not contain at least one start icon.