Graph architecture information processing system

A distributed function programmable digital information processing system for use in combination with at least one input-output device such as a keyboard, a mass memory device, a display device, a cathode ray tube, a data link and the like to constitute a complete information processing system, said system comprising:

• a. a plurality of processing elements including:
• (1) a plurality of data processors for performing data transformations on data received from other said processing elements or from one or more input-output devices and for causing transfers of data to other said processing elements or to one or more said input-output devices,
• said data processors each including control logic circuitry including at least one control logic instruction receiver for receiving, interpreting, and initiating said data transformations or transfers in response to control logic instructions received,
• said receivers also having means for transmitting responses to control logic instructions received, and
• (2) a plurality of control processors for controlling said data processors, other said control processors and said system by means of control logic instructions,
• said control processors each including control logic circuitry including at least one control logic instruction transmitter for generating and transmitting control logic instructions in response to one or more of:
• (a) data received from one or more said input-output devices,
• (b) data received from another said processing element, and
• (c) control logic instructions received from another said control processor,
• said transmitters also having means for receiving responses to control logic instructions transmitted,
• at least one said control processor having control logic circuitry which also includes at least one control logic instruction receiver to permit that said control processor to receive as well as transmit control logic instructions whereby an instruction generated and transmitted may be in response to an instruction received, and
• at least one said control processor having control logic circuitry which also includes state defined control circuitry permitting said control processor to assume, in turn, two or more different states whereby said control processor is said to have state defined control and whereby a control logic instruction generated by it is in part a function of its state;
• and
• b. electrical circuit lines interconnecting said processing elements into a heterohierarchic functional grouping and interconnecting said processing elements with other devices including:
• (1) external lines for interconnecting processing elements of said system with input-output devices,
• (2) a plurality of dedicated control logic instruction line sets, each set having two or more electrical conductors and connecting one said instruction transmitter or one said control processor to one said instruction receiver of another said processing element to constitute with said transmitter and receiver a control arc for interconnecting two different processing elements for communication of said instructions, each of said plurality of sets connecting one processing element to one other processing element to connect all of the processing elements into a single system, and
• (3) data lines in addition to said dedicated control logic instruction line sets for carrying said data among said processing elements,
• whereby the network created by said processing elements when interconnected by said dedicated control logic instruction line sets defines a mathematical graph in the sense of graph mathematics over the processing elements with said processing elements constituting the nodes of the graph permitting a theory of operation based on the theory of mathematics.

A distributed function programmable digital information processing system comprising:

• a. a plurality of processing elements including:
• (1) one or more input and output devices for providing information transfer to and from the system,
• (2) a plurality of data processors for performing data transformations on data received from other said processing elements in response to system control logic signals received from control processors and for providing output data to said output devices,
• said data processors each including one or more system control logic signal receivers for receiving, interpreting, responding to, and initiating data transformations in response to said system control logic signals received, and
• (3) a plurality of control processors for controlling said data processors and other said control processors by means of system control logic signals,
• said control processors each including one or more system control logic signal transmitters for generating, transmitting and receiving responses to said system control logic signals, and
• at least one of said control processors also including at least one system control logic signal receiver for receiving, interpreting, responding to, and initiating other said system control logic signals, and
• at least one of said control processors also including state defined control circuitry permitting said control processor to assume, in turn, two or more different states whereby the function performed by said control processor depends in part on its state to constitute the condition of state defined control;
• and
• b. electrical conductors interconnecting said processing elements including:
• (1) a plurality of dedicated system control logic signal conductor sets with each set interconnecting one said system control logic signal transmitter of one said processing element and one said system control logic receiver of another said processing element, to constitute one control arc interconnecting two processing elements, and
• (2) data lines interconnecting said processing elements and interconnecting said input and output devices with said processing elements,
• whereby all said processing elements in the system are connected to one or more other processing elements by said data lines, said dedicated control signal conductors or both and wherein said input and output devices are connected to said data processors or control processors only by said data lines;
• and
• wherein the number of said control arcs is equal to or greater than the total number of control and data processors and the control arcs interconnecting two or more processing elements describe a loop.

A programmable digital string data processor for performing operations of string concatenation, alternation and substring search by manipulating and comparing strings of data words by transferring the words among a plurality of memory stacks comprising:

• a. data input lines and an input register for receipt of data on which operations are to be performed;
• b. an output register and data output lines for transmission of output data;
• c. a plurality of LIFO memory stacks including:
• (1) one LIFO stack designated a left stack which is particularly adapted for loading with a string of data words with the data word representing the right end of the string so located as to be first out,
• (2) at least one LIFO stack designated a right stack which is particularly adapted for loading with a string of data words with the data word representing the left end of the string so located as to be first out;
• d. a memory stack which can be operated as either LIFO or FIFO and is designated as a match stack;
• e. data manipulating and searching means for performing concatenation, alternation and substring searching on strings of data words including:
• (1) conductor means interconnecting said input register, output register, and LIFO memory stacks for transmitting digital signals for:
• (a) moving strings of data words among said registers and said stacks,
• (b) moving a string of data words from the said match stack in LIFO mode onto a string in a said right stack, and
• (c) moving a string of data words from said match stack in FIFO mode onto a string in said left stack,
• (2) digital signal comparator means electrically connected to said conductor means including means for determining the identity or lack of identity of signals representing data words for:
• (a) comparing a string of data words in the match stack word for word with the right end of a string in the left stack, and
• (b) comparing a string of data words in the match stack word for word with the left end of a string of data words in a right stack,
• whereby strings of data words in a right or left stack can be compared word by word while being moved into another stack so as to identify a substring which compares with a string in the match stack, and
• (3) electronic circuitry means for processing digital signals representing characters in said data words for performing the following primitive data operations in support of said comparator means:
• (a) clear, whereby all stored words are obliterated,
• (b) push, whereby additional words are inserted,
• (c) pop, whereby stored words are released and obliterated in sequence,
• (d) read, whereby stored words are read,
• (e) write, whereby new words are inserted while replacing stored words on a one-for-one basis,
• (f) length, whereby the number of words stored in a stack is counted,
• (g) save, whereby words stored in a stack are retained in memory during another operation to permit restoration to the condition existing prior to that other operation, and
• (h) restore, whereby a stack content is returned to content existing prior to an operation,
• (4) programmable control means for selecting the order, time and sequence of said primitive operations;
• and
• f. control connection and communication means connected to said programmable control means for receipt of control signals for controlling said string data processor;
• whereby a sequence of pop operations from one stack and push operations to a second stack results in the concatenation of the string contained in the first stack to the string contained in the second stack,
• whereby a sequence of pop operations from a first stack and pop operations from a second stack wherein each word popped from the first stack is compared by the comparator means with the word popped from the second stack produces the alternation operation which determines whether or not the string contained in the first stack is the same as the string contained in the second stack, and
• whereby a sequence of pop operations on the second stack followed by said alternation operations determines whether or not the string in the first stack is a substring of the string contained in the second stack.

A programmable digital machine for performing lexical and syntax analysis on data representing a higher level language program to determine, from the grammatical definition of the language of that program, what instructions must be issued to and performed by a processor using a lower level machine language for interfacing and interpreting between components of a data processing system using a first higher level language and processing devices used by said system which use a second lower level language comprising:

• a. grammatic rule memory means for storing data representing the rules which grammatically define the language being used;
• b. electrical connector, register, flip-flop and gating means for connecting the machine to and for receiving and carrying out instructions received from another processing element of the system, said electrical connector, register, flip-flop and gating means generating instruction signals in response to instructions received, said instruction signals including signals meaning:
• (1) pass the instruction to another processor (DIRECT),
• (2), do nothing (NOP), which is an instruction used for maintenance purposes,
• (3) initiate program translation using data stored in said grammatic rule memory representing the first such rule, and
• (4) continue program translation from the point in said rules last used;
• c. programmable control circuitry means responsive to data stored in said grammatic rule memory means for generating operation signals to cause the machine to initiate operations, said operation signals including signals meaning:
• (1) scan the next program character,
• (2) convert a string of characters representing numbers to numbers or vice versa,
• (3) change the existing rule state:
• (a) unconditionally,
• (b) based on data comparisons,
• (c) based on data classification, or
• (d) based on external conditions,
• (4) issue instructions to other processing elements,
• (5) access data from other processing elements, and
• (6) temporarily discontinue program translation;
• d. means responsive to data stored in said grammatic rule memory means, to one or more said operation signals, and to data received from said program processor, said means including (i) data comparator means, (ii) data classifier means, (iii) state LIFO memory stack means, and (iv) state register means for determining which grammatic rule is to be used, as a function of:
• (1) a current rule, and
• (2) the current program character;
• e. electrical connector, register, flip-flop and gating means responsive to one or more said operation signals for connecting the machine to and for issuing instructions to other processing elements in the system wherein at least one said processing element is a program memory processor, said means including a control arc transmitter for each other processing element to which said machine will issue instructions as determined by the current grammatic rule in effect;
• f. means including (i) data multiplexer means and (ii) data register means responsive to one or more said operation signals for accessing the data produced by said other processing elements to which instructions are issued by said multiplexer and register means wherein one such processing element is said program memory processor;
• g. means responsive to one or more operation signals and to the current program characters, said means including (i) data multiplexer means and (ii) data register means for converting strings of data characters representing a number to the number itself and vice versa;
• whereby said machine can provide for translation of a higher to a lower level program language to permit programming of the system in said higher language and the operation of selected processing elements of the system on the basis of said lower language, said higher level program language being the language in which the program represented by the data stored in said program memory processor is written, and said lower level program language being the language in which the instructions produced by said machine are written.

A programmable digital display machine providing for control and operation of visual images on at least two dissimilar display devices from a common string of data words which defines the images to be displayed and providing storage for and use of complex visual images made up of more simple display images which in turn may consist of still more simple display images in response to data and control signals received from another system comprising:

• a. a display control unit designated a DSPL control processor for generating instructions for portions of the display machine from a higher level definition of display images originating within the display machine or elsewhere in said system from which said machine receives data and control signals including:
• (1) rule memory means for storing data representing rules defining the visual images to be generated,
• (2) instruction processing means for receiving and carrying out instructions received from a processing element in said system from which said machine receives data and control signals,
• (3) programmable control circuitry means responsive to data stored in said rule memory means for generating signals to cause the said programmable digital display machine to perform operations, said signals including signals meaning:
• (a) scan display program characters from at least two sources,
• (b) convert strings of characters,
• (c) change rule states,
• (d) issue instructions to other portions of the display machine,
• (e) access data from other portions of the display machine, and
• (f) discontinue interpretation of display program;
• (4) comparator, stack and state register means for determining which rule is to be used,
• (5) means including control logic circuitry and interconnections means for issuing instructions to other portions of the display machine wherein at least one portion is a symbol processor,
• (6) data multiplexer and register accessing means for accessing data produced by said other portions of the display machine including said symbol processor,
• whereby said DSPL control processor can define images to be displayed in a lower level machine language responsive to instructions received in a higher level language;
• b. a display interface unit designated a DIU data processor for interconnecting the display machine with at least two dissimilar display devices including:
• (1) means including control logic circuitry and an input instruction register for receiving instructions from said DSPL control processor,
• (2) means including a micro code generation memory and a timing generator circuit for controlling the execution of each instruction received from said DSPL control processor,
• (3) means including a memory and counters for accessing individual bits in said memory for data representing each dot of dots representing a primitive visual image for generating a dot pattern representing a predefined primitive visual image,
• (4) means including an adder, a four location random access memory and a cursor movement read only memory for computing and storing a cursor value representing the x and y coordinates of the desired location on the screen of a display device for showing a primitive visual image wherein said read only memory defines the numbers to be added to an existing cursor value to determine a new cursor value as a function of the instruction being executed and contains numbers which define exactly the value that one or more values of the random access locations are to assume for a given instruction,
• (5) means including counters, multiplexers, flip-flops and gates for generating addresses and control signals for creating a display on a flat panel plasma display,
• (6) counter and gating means for generating addresses and control signals for a refresh memory to allow construction of an x and y coordinate oriented dot image,
• (7) a refresh memory, and
• (8) counter and multiplexer means for reading out of said refresh memory a serial stream of data in the sequence needed by a raster-scan cathode ray display device to allow display of the image on said cathode ray display device;
• and
• c. a symbols data processing element designated a SYM data processor for generating symbols data including:
• (1) means including control logic circuitry and an input instruction register for receiving instructions from said DSPL control processor,
• (2) means including an output data register for holding data results for use by said DSPL processor,
• (3) means including a micro code generation read only memory and a timing circuit for controlling the execution of each instruction received from said DSPL,
• (4) symbol storage means, including a random access memory storage means, a symbol register and addressing circuitry for sequentially accessing data characters in a string, for storing character data representing the definition of a plurality of symbols wherein each symbol definition is a string having an associated start location in said storage means, wherein the last character for the definition of each string in the storage means in a symbol end character and wherein the other characters in such string represent characters for display controls,
• (5) symbol name starting address location memory means including a random access memory, a register, addressing circuitry and interconnections with other components of SYM for storing the starting address of symbols in the starting address memory, for allowing the output of said starting address memory means to be loaded into said symbol storage address register means and for allowing an output of said symbol storage means representing the name of a symbol to be used as the address of the starting address memory whereby one symbol may refer to yet another symbol in its definition,
• (6) return address stack memory including an address stack circuit and interconnection with the symbol storage address register means for the transfer of memory addresses, for storing the addresses of symbol memory locations for use after completion of the execution of a symbol string in those instances in which the symbol is referred to by another more complex symbol.