Browse Prior Art Database

Determination of a Program Logic Graph

IP.com Disclosure Number: IPCOM000088129D
Original Publication Date: 1977-Apr-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 3 page(s) / 16K

Publishing Venue

IBM

Related People

Dapron, FE: AUTHOR

Abstract

A recurrent problem in program design is the determination of a valid program graph to solve the given problem.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 3

Determination of a Program Logic Graph

A recurrent problem in program design is the determination of a valid program graph to solve the given problem.

This disclosure reveals a technique for developing such a graph by extension of a formal analysis of the sequential constraints of the problem variables, logical and data, and development of a viable sequence of performing the logical tests and data transformations, i.e., a valid precedence matrix over the entire problem, and then abstracting those nodes necessary to a complete graph of the program. Basic Concepts:.

A precedence matrix over the sequential relationships in a problem can be renamed the interconnection matrix over a graph of one program to mechanize the problem, a graph which has just been proven isomorphic to the problem.

Any valid program to solve this problem must be homomorphic to the structure just defined.

Such a homomorphic structure will be a subset of the original structure's nodes, which implies all of them. Rules of Sequential Dependency: 1. Existence
(a) If a variable is referenced, either by logic or as a factor in a calculation or manipulation, the referencing step is dependent on all steps which establish (set) a value valid in the referencing step. (b) If a variable is set in a step, that step is dependent on all steps which reference it at a previous value. 2. Path Dependence If a logic or state function is to be performed only in certain paths or skipped in certain paths, that step is dependent on the step(s) containing the logic functions which differentiate those paths. 3. Path Independence If any logic or state function is independent of certain logic paths, i.e., performed (or skipped) in the same way regardless of which path is taken, it should be in a path common to them, either preceding or following the divergent paths. (a) If it is to precede the divergence, the logic which causes the divergence is dependent on it. (b) If it is to follow, the independent step is dependent on all logic and state functions in the diverse paths including the logic which divides the paths. (c) If neither (a) nor
(b) can be done in a way which satisfies all sequence constraints, a poor third choice is to implement redundant logic and/or state functions within the diverse paths. This alternative is not illustrated here. 4. Exits Any terminal (exit) step is dependent on all paths which lead to it and, also, on all steps in those paths. Details of the Technique:.

The first step is to postulate a sequence of execution and construct a precedence matrix over this sequence. While no knowledge of sequential constraints should be ignored, this is not meant to be a final effort, i.e., some flaws are expected in this first approximation. Each step is laid out in a vertical sequence and an identical sequence laid out horizontally. The principal diagonal is set to `0s'.

The horizontal axis represents steps on which some step represented on the vertical axis may be dependent. A...