Patent GB-1266993-A (GB)
IPC: G06F15/00
Filed: 1970-09-07
Abstract: 1,266,993. Data processing; associative stores. INTERNATIONAL BUSINESS MACHINES CORP. 7 Sept., 1970 [24 Sept., 1969], No. 42714/70. Headings G4A and G4C. A data processing apparatus comprises means for constituting the calculus of lambda conversion as the machine language of the apparatus, and means for effecting processing of data in accordance with the calculus. The following functional units communicate concurrently with respective vertical planes of a 3-dimensional associative memory for associative matching, reading and/or writing (except that the input unit cannot read): (a) input unit for receiving lambda calculus expressions from a keyboard and including a push-down store for holding left parentheses and conditional indicators until left parentheses following their respective right parentheses are known ; (b) store (control) units interconnecting the associative memory and a linear (conventional addressable core) memory; (c) node assembler unit; (d) up unit; (e) beta unit; (f) arithmetic and logic units; (g) output unit (printer). Each vertical plane of the associative memory holds four (horizontal) words each including a vacancy bit and during execution holding information specifying a given node and up to three daughter nodes of a tree corresponding to a lambda calculus expression. The information specifying the given node is its location in the tree. The three daughter nodes of a given node might be an operator and two operands for example, the result from which would correspond to the given node. A daughter node might itself have daughter nodes, and so on. Node information is distinguished as being a variable, definiendum, constant or location, by an accompanying designator. Evaluation of an expression would correspond to progressive contraction of the tree, contraction to the " trunk " causing print out by the output unit. The words in the associative memory are continually shifted through the memory in a closed loop, each word passing parallel-by-bit via intermediate flip-flops to the next word location in the loop, the loop passing from right to left along the top horizontal plane of the memory, then left to right along the next horizontal plane, and so on, finally returning to the right-hand end of the top plane from the right-hand end of the bottom plane. This continual shift enables a typical functional unit to access words intended for it (using associative matching) and write words if necessary. The storage cells in the associative memory are shown as flip-flops, the associative matching using two AND gates per cell connected to the flip-flop and the input bit in true and complement form to produce a mismatch indication if either AND is enabled, but four-state cells are also mentioned as an alternative. Initially the lambda calculus expressions constituting the programme are stored by the input unit in a slightly modified form in the associative memory and passed from it by the store (control) units into the linear memory where they remain throughout execution. For execution the node assembler unit constructs trees in the associative memory (see above) from the programme expressions in the linear memory by means of indications placed in the associative memory by the node assembler unit and detected by the store (control) units. The beta unit substitutes values for variables by utilizing back pointers in the associative memory. The up unit is involved in the contraction of trees as the execution proceeds and expressions are progressively evaluated. Extra node assembler units can be added to permit simultaneous processing of several programmes. The functional units could alternatively each access the whole associative memory, in turn.