Functional Method for Universal Computation by Extended Formal Matrix Product

Abstract

Functional Method for Universal Computation by Extended Formal Matrix Product. The invention targets central processing units (1) that can be programmed by functional software devices (3) relying on the sole notion of application, (6) to (10), without any set of instructions whose complex sequential decoding is opposed to a parallelism independent of the software devices themselves (3), allowing, by the product (5) of binary matrices (2), a first parallelism said technical (24), autonomous and independent of functional algorithms, nevertheless performing these latter in a parallel way independently of their initial description (3). A second parallelism, said applicative, constituted by binary diagonally matrix (4) extended with indexes (13) situated inside the technical parallelism (2), performs simultaneously several tasks (4), always without instructions, nor task scheduler. The method is constituted of an extended matrix product operation (24) on two set of memory words, (13) to (16), representing two triangular matrix (2), such that one allows to write the result of the product of its opposite (extended to a square matrix) by itself and reciprocally (2), according to three phases, called application (A), expansion (E) and reduction (R). The results are expressed by some binary connections (24) defined by the binary product between lines and columns. The software devices are vectors (17) of sequences of binary diagonally matrix (4) extended with index words (13) for each dimension, referring to positions into the software device (17). The method according to the invention is particularly intended to formal intrinsic computations (6), in computer science and in cognitive semantic.

Claims

1. Functional Method for Universal Computation by Extended Formal Matrix Product to perform applicative computations by means of a central processing unit (1) and the corresponding software device (17) characterized in that the said central processing unit (1) includes two identical parts (2) and opposite in their operation, each one including a triangular matrix (2) of binary diagonally matrices (4) extended with an index word (13) for each dimension, each part (2) being also extended with one additional index word (e); each part (2) serving by turns respectively as a computation support (5) by the extension into a square matrix of the said triangular matrix of the said current part (2), and for the corresponding effective result, through an extended matrix product operation (5) of the said square matrix by itself; or in an equivalent manner for each part (2) respectively, including a set of binary memory words (14), (15) extended with additional index words (13), (16), (e), each index referring to places in the said sequence of binary words (17) of elements of the same nature (4) defining the said software device.

2. Method according to the claim 1 characterized in that the order of the current values of the applicative expressions (6) is given by the order formed by the product (24) of the said binary matrices (4) and each value (6) is effectively given by the values of the said indexes (13) associated to each dimension, corresponding to the values «true» or «1» of the said binary matrices (4) of the current part (2), read according to the said traversal order (24).

3. Method according to the claim 1 and the claim 2 characterized in that the extended matrix product operation (5) includes a first phase (A) of duplication of a value of the index word (e) in a new column of the said index word (e), also moving the corresponding value «true» or «1» in a new column of the corresponding binary matrix (4), with the same current values (6) according to the claim 2.

4. Method according to the claim 2 and the claim 3, characterized in that the said phase (A) is successively performed in each of the said opposite triangular parts (2), by successive writings of binary diagonally matrices (4) as long as there are several values «true» or «1» on the same column of a given binary matrix (4), that is, on the same index value (13), during the successive readings of the current values (6) by the said central processing unit (1) according to the claim 2.

5. Method according to the claim 1, characterized in that the extended matrix product operation (5) includes a second phase (E) adding a column with the value «true» or «1» on the right, to a left binary matrix (11) according to a matrix product (4) given by the said matrix product operation (5), and adding a line (to the bottom) and a column (to the right) such that the value «to the bottom on the right», or on the diagonal, is «true» or «1», of the corresponding right matrix (12) of the said product.

6. Method according to the claim 5 and the claim 2, characterized in that the said phase (E) is successively performed in (5) each of the said opposite triangular parts (2), by successive writings (5) of binary diagonally matrices (4), as long as the number of lines added by one unit, of the left matrix of the software device (17), given by the first index (13) of the given current value according to the claim 2, is different from the number of columns of the left matrix (4) of the said matrix product operation of the current part (2).

7. Method according to the claim 1 and the claim 2 characterized in that the extended matrix product operation (5) includes a third phase (R) in the immediate absence of applications between indexes during the product, that follows, of the said left matrix with the corresponding right matrix [FIG. 32]; that is in the absence of a common occupied position during the comparison of the «column» index words, of the left and right matrix; in a first step, the transformation of the sequence of the binary diagonally matrix of the current part (2), in the said opposite part (2), into another sequence of binary diagonally matrices (25) added of two matrices, (19) and (18), by the middle (14) of the current product (24); and in a second step, the effective matrix product operation in the opposite part (2).

8. Method according to the claim 7 and the claim 2 characterized in that in a first step, the left matrix of the software device (17) identified by the head index (13) of the given current result according to the claim 2, is copied with its indexes (13) added of one unit, inside, at the middle on the left (19) and shifted of one erasure (20) to the right and to the bottom, or «to the bottom on the right», in the said opposite binary diagonally matrix; and the right matrix (18) of the corresponding product is constituted by a line word of «true» or «1», also shifted of one line and one column to the right and to the bottom.

9. Method according to the claim 7 and the claim 2 characterized in that in the presence of a «direct» or «internal» application of index, the said copy is performed by delaying the application by making copies of the corresponding left and right matrices into new diagonally matrices that are extended to the identity, such that the result of the product of these diagonally matrices is at the same reading value as the current product according to the claim 2.

10. Method according to the claim characterized in that during the second step of the reduction phase (R), that is during the effective matrix product to the opposite part (2), the index word (e) shifts towards the inside of the matrix product according to the number of columns of the last left matrix of the current global product.

Description

[0035] Example I: The left matrix or word ‘.square-solid...square-solid.’ represents any «binary» expression as for example ‘(Wf)x’, ‘(fy)x’ or ‘(fx)(gx)’, or again ‘(fx)x’.

[0036] The differences between these expressions are given by the composition with the associated right matrix ‘2x_’.

[0037] If the binary combinator W is considered in the expression ‘(Wf)x’, the computation is «blocked» in the absence of «currying» because the parentheses mark the result of the application of W to ‘f’; if the left parentheses have no influence on the final result, they cannot be removed arbitrarily in ‘(Wf)x’.

[0038] Example II: The left matrix or word ‘.square-solid...square-solid...square-solid.’ represents any expression «ternary» as for example ‘Wfx’, ‘fyx’ or ‘fx(gx)’, or ‘fxx’.

[0039] The differences between these expressions are given by the composition with the associated right matrix ‘3x_’; there is no intermediate result except the expression ‘(gx)’ in ‘fx(gx)’.

[0040] Example III: «regular» is said of a combinator or matrix whose value of the first column of the first line of the right matrix of the corresponding matrix product is ‘.square-solid.’.

[0041] The product ‘.square-solid.*.square-solid.=.square-solid.’ between the matrices of the first columns of each line does not introduce any change in the first column of the first line of the result.

[0042] Example IV: See the transformation associated to combinator B in the illustration [FIG. 3]; the left matrix of the matrix product (11), is composed in parallel (technical parallelism) with the right matrix (12), such that the product «above» establishes connections between indexes or places associated with lines or columns (13).

[0043] In the said illustration, such a resulting application ‘2(34)’ cannot be represented by the present method since only one number may be associated with a line or a column and not an application of number or index.

[0044] The present method therefore «extends» the matrix product operation into three phases (A), (E) and (R), described later in the present invention, such as the principle to have only one number or index associated to a line or column is respected ([FIG. 14] to [FIG. 34]).

[0045] The example is given as an understanding in the first part of the answer to the present issue; the second part will systematize the fact to put all applications inside the matrix product itself.

[0046] Still in [FIG. 3], the two computations «outside» the current matrix product, and which are also matrix products, are represented by (14) and (15).

[0047] Therefore be the data of a word (line) or of several binary words (composed), constituting a matrix or product, of the form: ‘.square-solid. . . . .square-solid.’ where each ‘.square-solid.’, synonymous of «true» or ‘1’ represents:

[0048] An applicative relation (or a relation between an input or column and an output or line) between: the column relative to its position in the current word and the current line; another column and another line by adding an integer number (13) relative to the current column or the current line, representing an index in the word matrix of the current software device (17).

[0049] An applicative subexpression which is obtained by the composition of the said word with another matrix where the same principles apply, and by the reading above the product, and so on.

[0050] When the value is ‘.square-solid.’ or «1» there is application, when the value is □ («false» or ‘0’), there is no application.

[0051] The present method applies the following rules of the binary «product»: .square-solid.*.square-solid.=.square-solid.; .square-solid.*□=□: □*.square-solid.=□; □*□=□.

[0052] The present method applies the following rules of the «sum»: .square-solid.+.square-solid.=.square-solid.; .square-solid.+□=.square-solid.; □+.square-solid.=.square-solid.; □+□=□.

[0053] All of the matrix representations are entirely binary, only the lines and columns can be added with the maximum of an integer number per line and per column.

[0054] The method according to the present invention is mainly based on matrix products which are representations in the plan R.sup.2 or the two-dimensional space or more.

[0055] These representations are not usual of the «numerical» machines; other isomorphic representations are therefore necessary to allow the method to be effectively carried out by means of a central processing unit.

[0056] It is defined that the matrix product is a particular case of the tensor product that generalizes it to dimensions greater than two, while relying on a product «line-column».

[0057] A system thus obtained can be compared, only by the number of manipulated dimensions (2 and more), to the so-called «neural networks» systems; indeed, the present method then constitutes a network of «formal neurons» relying on the concept of application via binary matrices of dimensions greater than two.

[0058] The implementation of such a system requires integrating into the words that follow several dimensions, that is words or tables of dimensions greater than two, by adding words of integer encoding these dimensions and the sum of the products of these dimensions to allow access through index words of length equals to the dimension of the manipulated matrices.

[0059] The tensor product algorithm may then be deduced from that of the matrix product, by decomposing the product in subproducts of smaller dimensions until it becomes equivalent to a «line column» product.

[0060] The whole then forms chains of structured products in significant formal little chains, that can be compared to internal formal expressions of the software device; these formal elements, and respectively these formal little chains, may then compose themselves into formal chains, double, or triple, or in some more complex structures, and then be computed identically.

[0061] The construction of a processing unit based on the tensor product or the generalized matrix product rely on given principles by the present method, extended to dimensions greater than two.

[0062] In the same way as the matrix product allows the construction of a level of technical parallelism, the tensor product allows the extension of the technical parallelism level to take into account matrices of dimensions greater than two.

[0063] The matrices or matrix products are therefore represented in the form of a Directed Ordered Acyclic Graph (from now on DOAG) structure (25) where each internal node of the said structure represents either a matrix product (P) or a diagonally matrix (M).

[0064] This DOAG structure (25) is in turn represented in the form of binary words extended with index words.

[0065] To perform effectively a numerical machine, the representation in the form of binary words is chosen, while keeping properties of the representation in the form of a matrix (and those in the form of a DOAG «product»).

[0066] The transformation or encoding of the DOAG into words is performed by the following chaining procedure [FIG. 13]:

[0067] In a left-to-right DOAG traversal, starting from the root, the latter may eventually be fictitious if one wanted to implement some «applicative» parallelism or in an equivalent manner, several simultaneous or parallel entangled DOAGs (sharing a same «fictitious» root).

[0068] By successive readings [FIG. 13] from the root to the leaves, ‘1’ is marked when the node has not already been passed and ‘0’ when the node has already been passed.

[0069] The encoding always starts with a word of ‘1’ that defines the path from the root to the first leaf which is the more on the left; a word is obtained (or a binary vector) and represented in the form of a particular vector (14) of which the number of columns is even or multiple of two times the number of parallel applications.

[0070] The present method traverses, manages, handles, thus simultaneously all the columns “two by two” of the said vector.

[0071] The matrix product structure, attached to this DOAG, then relies on another binary word (15) where the ‘1’ characterizes an internal node of the DOAG as a product, and the ‘0’ as a diagonally matrix containing other matrices, either also diagonally, or terminal binary leaf matrices; this binary word is constituted by the same path of reading as the DOAG corresponding structure, but each ‘1’ or ‘0’ marks only an internal node of the DOAG structure.

[0072] Thus a leaf is identified as a ‘1’ followed by a ‘0’ or of the end of the word defining the DOAG «product».

[0073] As well as for the DOAG structure, this word is represented (15) by a vector whose column number is even and according to the applicative parallelism.

[0074] To each leaf of the DOAG corresponds a binary matrix {0,1}; that is the information relating to the line number and the column number, and also the binary values of the said matrix.

[0075] The line and column informations can also be represented by words of integer for lines and respectively for columns organized according to the same DOAG structure and the matrix product structure such that the DOAG traversal allows to access the corresponding data in the matrices; these words of lines and columns are represented by (16).

[0076] Each line and column of each matrix (leaf) can be extended (according to the different combinators) with a maximum of one positive integer (per line and per column) representing indexes or positions in a word of matrix product (17); if such an information is not present, the index is given by the current column in the reading above the product.

[0077] Index (strictly positive) designing places in a word of matrix product (17) forming the software device associated to the central processing unit define an annotation word of the leaves, in the same way that the concept of product (P) and of diagonally matrix (M) annotate the internal nodes of the DOAG structure.

[0078] Adding these annotations on the leaves is performed by a supplementary vector representing the annotations (13) associated to the matrices whose number of column is multiple of two, followed by words (13) of corresponding indexes data.

[0079] A word of integers is defined thus for the lines and another for the columns of the terminal matrix; ‘0’ is not considered as an index value.

[0080] Always in [FIG. 13], the set of the words can easily be represented by a word structure (17) representing an element of a software device and containing some elements of different sizes, that is indexed by the sum of the products of the respective sizes for each sub-element.

[0081] The integration of external operations as arithmetic or logical operations computed by dedicated computational units, is performed by adding the corresponding information of the said external operations by words or supplementary annotations to the DOAG.

[0082] If the presence of an index refers to some internal operations to the matrix product, the presence of another «annotation» in another word, of the DOAG causes the corresponding operation to start such as the result is associated to an input of the following composition; we will make sure that there is only one annotation value or one order in the taking into account by the central processing unit.

[0083] The set of different word structures (17), constituted of the DOAG «product» with its extended «matrix» leaves as previously described, forms the software device or combinatory «program» (see [FIG. 22], the initialization of the computation since the software device); for understanding needs, the DOAG structure will be removed in the elementary or simple cases.

[0084] The matrix product made by the central processing unit, performing itself «above» the DOAG structure (or of words), the latter is a «miror» structure, so that the leaf matrices of left sub-DOAGs compose themselves with their analogues right sub-DOAGs compared to the root (see [FIG. 4], [FIG. 15], [FIG. 16] and [FIG. 17]).

[0085] The only constraints are therefore those related to the product lines per columns of the leaf matrices between them.

[0086] Each «local» binary product is directed by the number of lines of the left leaf matrix and the number of columns of the right leaf matrix, the «undefined» values are equal to ‘□’ or «zero» as described above.

[0087] When there is no correspondence at the level of the terminal matrix (see for example the combinator S [FIG. 18]), a grouping of binary values at a higher level is performed.

[0088] The algorithm of DOAG traversal (and of DOAG computation) is as such performed by level or «class of equivalence» [FIG. 16] and [FIG. 17]:

[0089] The two branches or columns of the vector are simultaneously traversed (14), at each traversal of a «product» node (p) (other than the root) the traversal of following branches may be performed in parallel ([FIG. 17] and [FIG. 18]); there is no «return up» on the product nodes.

[0090] The word (15) allows to identify the depth of the computation, the reading of this word advances only when a ‘1’ is encountered on the word (14); at each cycle the depth is reduced by 1.

[0091] Each branch of the said DOAG can be traversed in parallel (see [FIG. 17] for the reduction; [FIG. 23] and [FIG. 24] for the construction or expansion).

[0092] If the DOAG traversal encounters another product node, then each sub-branch is traversed in parallel also: the «left son» then resumes the DOAG at the current level and the «right son» resumes the DOAG word at the next ‘0’.

[0093] A terminal matrix must compose with another one or a «leaf» matrix; the number and the organization of the resulting leaf matrices are determined by the leaf matrices product.

[0094] The size of the last «left» terminal matrix defines the number of operands (index) that simultaneously enter in the matrix product (e).

[0095] During the reduction phase of the matrix product, gradually as the descent of the DOAG product occurs, the central processing unit assigns (in parallel) respectively the places for the writing of the results.

[0096] The size and therefore the places of these words in the resulting word are simply deduced from the corresponding line and column words, by the lines of the left matrix and the columns of the right matrix.

[0097] The different words of the resulting matrix product are deduced from the traversed DOAG and constructed according to the same principles as the traversal occurs, independently from the values of the said dimensions.

[0098] In an analogous way, during the construction or expansion phase, the words (or matrices) can be constructed according to the same principles as the «in miror» diagonally matrix.

[0099] The word representing the indexes is therefore copied again in the resulting and corresponding matrix(ces) according to the properties of the matrix product.

[0100] The algorithm of matrix product is performed on the matrix nodes or the leaves; once it is achieved, the processing resources of the central unit are released to serve again to other computations in the part (2) opposite to the current part and so on.

[0101] The present method of computation is thus characterized by two antagonistic actions:

[0102] The first action, through the matrix product, aims to construct or concentrate the software devices in more and more reduced matrices, until it obtains connections or applications between places (index) or by default a product (to remind there is no operation allowing to «group» indexes or applying them one over another in a same word—certain figures derogate this principle, [FIG. 27], to allow the understanding and the distinction with other approaches which develop them from pointers on memory addresses).

[0103] The second is «inverse» to the first and aims to construct some products or diagonally matrices such as the connections between the indexes are performed by the reading above the product.

[0104] If an application between this index appears inside the matrix product, the diagonally matrix structure is modified to introduce a «delay» in the application of the indexes, at the same reading value of the corresponding applicative expression by reading above the matrix product.

[0105] The corresponding algorithm is relatively simple: it is necessary to construct some inverse products of «identity» diagonally matrix whose values are immediately deduced from the current product by «reading equality».

[0106] The matrices being linked two by two in a product, if a matrix is processed, then the homologous matrix also, so that the reading above is preserved for the product.

[0107] These two antagonistic actions are performed by the three phases called Application (A), Extension (E) and Reduction (R).

[0108] The present invention thus aims to construct matrix expressions that «are sufficient on their own», that is to say, they integrate all the transformations (as for example the successive erasures of the applications) relating to the application of combinators to each other, encoded by the binary matrix product itself.

[0109] The said central processing unit (1) includes two identical parts (2) and opposite in their operation, each one including a triangular matrix (2) of binary diagonally matrices (4) extended with an index word (13) for each dimension, each part (2) being also extended with one additional index word (e); each part (2) serving by turns respectively as a computation support (5) by the extension into a square matrix of the said triangular matrix of the said current part (2), and for the corresponding effective result, through an extended matrix product operation (5) of the said square matrix by itself; or in an equivalent manner for each part (2) respectively, including a set of binary memory words (14), (15) extended with additional index words (13), (16), (e), each index referring to places in the said sequence of binary words (17) of elements of the same nature (4) defining the said software device.

[0110] The right upper matrix is arbitrarily retained as the starting matrix in the present description. Each part or triangular matrix successively serves to write the result of the composition of the opposite part extended to a square matrix.

[0111] The synchronization of the technical parallelism is thus automatically performed at each cycle, independently of the current software device.

[0112] In the following phases, the different changes of the matrices can be performed by fully relying on the DOAG structure, that is to say by adding some branch to the latter, as well as leaf matrices, by successive writings into each respective part of the central processing unit.

[0113] For each transformation, the central processing unit reserves, in a first step, a memory space of which it can easily know the size from the leaves of the DOAG product of the «source» diagonally matrix or from theses of the software device: sum of the lines of the «left» leaf matrices and sum of the columns of the «right» leaf matrices.

[0114] A certain number of tests can be performed at each moment to check the consistency of the software device (see the global illustration [FIG. 4] and the particular case [FIG. 22]):

[0115] The first matrix (left) must begin at the column equal to its own number of lines+1.

[0116] The left lower «corner» of the matrix (left) «touches» or descends to the diagonal.

[0117] The second matrix (right) must have the same number of lines as the number of columns of the left matrix.

[0118] The right matrix begins at the right lower «corner» of the left matrix and must also descends to the diagonal.

[0119] Each matrix may be subdivided into a different number of sub-matrices, but such that the «sum» of the matrices respects the properties of the matrix product.

[0120] The matrix product structure is global and «above» the different matrices, which considered separately may not be able to compose with their homologous matrix.

[0121] APPLICATION PHASE: The extended matrix product operation (5) includes a first phase (A) of duplication of a value of the index word (e) in a new column of the said index word (e), also moving the corresponding value «true» or «1» in a new column of the corresponding binary matrix (4), with the same current values (6) according to the reading above the matrix product.

[0122] The said phase (A) is successively performed in each of the said opposite triangular parts (2), by successive writings of binary diagonally matrices (4) as long as there are several values «true» or «1» on the same column of a given binary matrix (4), that is, on the same index value (13), during the successive readings of the current values (6) by the said central processing unit (1).

[0123] EXPANSION PHASE: The extended matrix product operation (5) includes a second phase (E) adding a column with the value «true» or «1» on the right, to a left binary matrix (11) according to a matrix product (4) given by the said matrix product operation (5), and adding a line (to the bottom) and a column (to the right) such that the value «to the bottom on the right», or on the diagonal, is «true» or «1», of the corresponding right matrix (12) of the said product.

[0124] The said phase (E) is successively performed in (5) each of the said opposite triangular parts (2), by successive writings (5) of binary diagonally matrices (4), as long as the number of lines added by one unit, of the left matrix of the software device (17), given by the first index (13) of the given current value according to the reading above the product, is different from the number of columns of the left matrix (4) of the said matrix product operation of the current part (2).

[0125] REDUCTION PHASE: The extended matrix product operation (5) includes a third phase (R) in the immediate absence of applications between indexes during the product, that follows, of the said left matrix with the corresponding right matrix [FIG. 32]; that is in the absence of a common occupied position during the comparison of the «column» index words, of the left and right matrix; in a first step, the transformation of the sequence of the binary diagonally matrix of the current part (2), in the said opposite part (2), into another sequence of binary diagonally matrices (25) added of two matrices, (19) and (18), by the middle (14) of the current product (24); and in a second step, the effective matrix product operation in the opposite part (2).

[0126] During the first step, the left matrix of the software device (17) identified by the head index (13) of the given current result according to the claim 2, is copied with its indexes (13) added of one unit, inside, at the middle on the left (19) and shifted of one erasure (20) to the right and to the bottom, or «to the bottom on the right», in the said opposite binary diagonally matrix; and the right matrix (18) of the corresponding product is constituted by a line word of «true» or «1», also shifted of one line and one column to the right and to the bottom.

[0127] In the presence of a «direct» or «internal» application of index, the said copy is performed by delaying the application by making copies of the corresponding left and right matrices into new diagonally matrices that are extended to the identity, such that the result of the product of these diagonally matrices is at the same reading value as the current product; a «lazy» or «delay» principle available for all applications distinct from the head application.

[0128] The construction of the said new diagonally matrices is relatively simple. The size of the said «identity» matrix is given by the «left» leaf matrix of the current product, then the current reading above the product gives the respective values of the lines and columns as well as the corresponding indexes, such that there is identity of the reading above the product.

[0129] During the second step of the reduction phase (R), that is during the effective matrix product to the opposite part (2), the index word (e) shifts towards the inside of the matrix product according to the number of columns of the last left matrix of the current global product.