Concurrent network of reduction processors for executing programs stored as treelike graphs employing variable-free applicative language codes

Claim 2

A network of reduction processing systems for executing variable-free applicative language code, said network comprising: a plurality of random access storage means each storing a portion of said code in various storage locations therein as two-cell nodes, some of said cells of said nodes containing storage addresses of other of said node storage locations so as to link said nodes to form a treelike graph, other of said cells of said nodes containing functional variables, still other of said cells of said nodes containing operators each of which defines a reduction transformation of a graph containing that operator, to a new graph not containing that operator; and a plurality of processor means, one for each random access storage means, each processor means including retrieving means coupled to said corresponding one of said random access storage means to retrieve said graph and transformation means to produce a reduced graph through execution of one or more steps of a series of said graph transformations defined by one or more of said operators in said graph.

Claim 3

A network according claim 1 including: a data section in each processor means, said data section including register file means coupled to said storage means to receive said two-cell nodes from said storage means.

Claim 4

A network according to claim 2 wherein: said data section includes an arithmetic and logic means coupled to said register file means to perform primitive functions on the cells stored in said register file means.

Claim 5

A network according to claim 2 further including: a control section in each of said processor means and coupled to said respective data section to provide control signals thereto so as to enable said substitutions to be performed.

Claim 6

A network according to claim 4 wherein: said control section includes microcode memory means and a control register coupled between said microcode memory means and said data section to receive control signals stored in said microcode memory for transmission to said data section.

Claim 7

A network according to claim 1 wherein: said plurality of storage means are interconnected by a series of arbiter switches and selector switches where each arbiter switch receives a message from one of two selector switches and provides said message as an output to a third selector switch and each selector switch receives a message from an arbiter switch and switches it to one of two other arbiter switches.

Claim 8

A network of reduction processing systems for executing variable-free applicative language code, said network comprising: a plurality of random access storage means each storing a portion of said code in various storage locations therein as two-cell nodes, some of said cells of said nodes containing storage addresses of other of said node storage locations so as to link said nodes to form a treelike graph, other of said cells of said nodes containing functional variable, still other of said cells of said nodes containing operators each of which defines a reduction transformation of a graph containing that operator, to a new graph not containing that operator; and a plurality of processor means, one for each random access storage means, each processor means including retrieving means coupled to said corresponding one of said random access storage means to retrieve said graph and transformation means to produce a reduced graph through execution of one or more steps of a series of said graph transformations defined by one or more of said operators in said graph; said transformation means including a data section having register file means coupled to said retrieving means to receive said one of said graphs from said corresponding storage means, upon which graph said transformations are to be performed, and an arithmetic logic means coupled to said register file means to perform primitive functions on those node cells containing functional variables and received by said register file means.

Claim 9

A network of reduction processing systems for executing variable-free applicative language code, said network comprising: a plurality of random access storage means each storing a portion of said code in various storage locations therein as two-cell nodes, some of said cells of said nodes containing storage addresses of other of said node storage locations so as to link said nodes to form a treelike graph, other of said cells of said nodes containing functional variable, still other of said cells of said nodes containing operators each of which defines a reduction transformation of a graph containing that operator, to a new graph not containing that operator; and a plurality of processor means, one for each random access storage means, each processor means including retrieving means coupled to said corresponding one of said random access storage means to retrieve said graph and transformation means to produce a reduced graph through execution of one or more steps of a series of said graph transformations defined by one or more of said operators in said graph; said transformation means including a data section having register file means coupled to said retrieving means to receive said one of said graphs from said corresponding storage means, upon which graph said transformations are to be performed, and an arithmetic logic means coupled to said register file means to perform primitive functions on those node cells containing functional variables and received by said register file means.

Claim 10

A network according to claim 7 wherein: said plurality of random access storage means are interconnected by a series of arbiter switches and selector switches where each arbiter switch receives a message from one of two selector switches and provides said message as an output to a third selector switch and each selector switch receives a message from an arbiter switch and switches it to one of two other arbiter switches.

Claim 11

In a network of reduction processing systems having a plurality of random access storage means for receiving programs written in a variable-free applicative code and storing said code in various storage locations therein as two-cell nodes, some of said cells of said nodes containing storage addresses of other node storage locations so as to link said nodes to form a treelike graph, other of said cells of said nodes containing functional variables and still other of said cells of said nodes containing variable-free operators each of which defines a reduction transformation of said graph containing that operator, to a new graph not containing that operator, said system also including a plurality of processor means coupled to said respective random access storage means, said plurality of random access storage means being interconnected by a series of arbiter switches and selector switches where each arbiter switch receives a message from one of two inputs and provides an output and each selector switch receives a message as an input and switches it to one of two outputs, the method comprising: retrieving by graph said processor means, said graph from said respective random access storage means; and performing one or more steps of a series of said reduction transformations to produce a reduced graph.

Claim 12

In a network of reduction processing systems having a plurality of random access storage means for receiving programs written in a variable-free applicative code and storing said code in various storage locations therein as two-cell nodes, some of said cells of said nodes containing storage addresses of other node storage locations so as to link said nodes to form a treelike graph, other of said cells of said nodes containing functional variables and still other of said cells of said nodes containing variable-free operators each of which defines a reduction transformation of said graph containing that operator, to a new graph not containing that operator, said system also including a plurality of processor means coupled to said respective random access storage means, said plurality of random access storage means being interconnected by a series of arbiter switches and selector switches where each arbiter switch receives a message from one of two inputs and provides an output and each selector switch receives a message as an input and switches it to one of two outputs, the method comprising: retrieving by graph said processor means, said graph from said respective random access storage means; and performing one or more steps of a series of said reduction transformations to produce a reduced graph.

Claim 13

A method according to claim 9 wherein each two cell node contains a mark bit field, said method including the step of: setting a bit in said mark bit field whenever another two-cell node contains an address referencing said two-cell node in said storage means.

Claim 14

A method according to claim 9 wherein each two-cell node contains a reference field, said method including the step of: incrementing said reference field whenever another two-cell node contains an address referencing said two-cell node in said storage means.

Claim 15

A method according to claim 9 further including the step of: routing messages between said plurality of storage means by way of said arbiter switches and selector switches.