A computer is disclosed wherein the machine language thereof is a particular formal system, i.e., the "calculus of lambda conversion." Such machine language is the language of the "well-formed" formulas of the aforementioned lambda calculus whereby the theoretical properties of the lambda calculus are implemented in the computer. Consequently, the computer is capable of computing all computable functions with time and space being the only limitations. The nerve center of the system is termed a tablet which in one implementation may essentially consist of an array of high-speed registers, each one large enough to hold a primitive term together with its designator. The nodes of a tree given by some formula corresponds to rows in the tablet and the branches extending from the nodes correspond to columns in the tablet. In one embodiment, the tablet has three columns for the branches and can have a fourth column which holds the tree addresses of the nodes. Associative techniques permit access to a row upon a match with the contents of the data or designator fields of one or more columns. The basic unit of information consists of the contents of a complete row of the tablet, such unit being termed a "message." The tablet, functioning as a central communication device, communicates with functional units, memory units, and input-output units, the latter issuing and accepting messages, or merging them with existing ones when the units obtain access to the tablet. The invention contemplates either the accessing by the units of the whole tablet, one after another in a fixed sequence, or the accessing by each unit of only a subset of the tablet, all units simultaneously accessing discrete subsets respectively. In order to render all messages available to all units, all of the messages are circulated, i.e., shifted through the whole tablet.
This disclosure relates to a reduction processor for the evaluation of one or more functions which are stored in memory in the form of a series of nodes of a treelike graph where the nodes implement a variable-free applicative language. The respective function operators are reduced through a progressive series of transformations or substitutions until a result is obtained. During the reduction process, the processor transfers nodes to and from memory and performs various operations as required on those nodes. The processor can also create new nodes in memory and delete unused ones.
This disclosure is directed toward a data driven network of uniform processing or function modules and local storage units which network may be readily partitioned to accommodate various concurrent operations or tasks. Data transfer is serial in nature so that data segments can be of any length. Execution by each function module is initiated by arrival of all of the required data structures, one of which contains an operator and may be stored in the associated local storage unit. The other data structure may contain operands and modifiers. Thus, a series of such operators may be distributed throughout the network to increase processing performance and throughput. A particular character set and data structure format is also disclosed.
The invention is directed to a computer including an input unit, an arithmetic logic unit, a memory unit, a control unit, an output unit, and a signal bus system connected to each of the units to permit signal communication between each of the units. The control unit of the present invention includes a problem section coupled to the memory unit, for fetching binary encoded source elements of a problem expression stored in the memory unit. In addition, the control unit includes result generator, coupled to the problem section, for generating a result expression from at least one of the source elements of the problem expression. Further, the control unit comprises a transfer unit, coupled to the result generator and the memory unit, for storing the result expression into a result area of the memory unit. The result expression comprises a plurality of address pointers to pre-identified source elements of the problem expression. The control unit further comprises a reslut section, coupled to the memory unit, for fetching the result expression from the result area of the memory unit, writing unit, coupled to the result section and the memory unit, for writing the result expression into the environment area of the memory unit; environment section, coupled to the memory unit, for fetching the result expression from the environment area of the memory unit; and comparing unit, coupled to the memory unit, for comparing at least one storage location from the result area of the memory unit with at least one storage location from the environment area of the memory unit to monitor the storage capacity of the result area and the environment area.
A character-serial electronic digital computer utilizing a four character vocabulary, each character being represented by two binary bits, is structured to process character-serial data arriving at the computer in a manner specified and initiated by the arriving data. Data structures that may represent program or operations to be performed on data arriving at the computer input are stored in the computer's storage area in the form of nested data structures that may be illustrated as tree structures in which each node of the tree structure represents an operation. Data structures that may represent operands are also supplied to the computer in a nested organization. This operand data addresses a certain node or operation resident in the computer storage area. The linking up of the arriving operand data with its program data triggers execution of the operation. In a case where more than one operand is needed before an operation can be performed, the arrival of a first operand without the second causes storage of the first operand until arrival of the second arrival of the second operand triggers the operation to begin. This interrelationship of program data and operand data, that is, the dynamic data being linked with the static data to trigger the operation, exists whether the program data is stored and static or the operand data is stored and static. Utilizing a four character vocabulary, to represent data, two of the characters being utilized to indicate the beginning and end of a data field, facilitates the implementation of an error checking technique wherein only sensed characters indicating the beginning and end of a data field are counted. The utilization of beginning and end of data field characters in the data structures consisting of nested data fields permits at will expansion and contraction of the fields within it.
A large number of processor cells 11, the majority of which are standard cells 12 and others special cells 13, are connected to a communication network 14 in the form of several binary trees. The cells 11 are connected at the leaf positions of the binary trees, and the nodes of the binary trees are formed by switching circuits that allow individual cells to control the formation of signal paths through the nodes. In operation, cells may be in a waiting state, a free state, a calling state, searching state, a communicating state, or an internal operation state. Cells 12 in the free state transmit a free signal into the network 14. Cells 12 or 13 in a searching state transmit a searching signal into the network 14 where, on meeting a free signal at a node, a route is formed from the searching state cell to a free state cell. A calling state cell 12 establishes, with a calling signal, a route through the network 14 to another cell identified by destination information in the calling signal. Cells 11 in the waiting state are waiting to be called by a cell 12 in the calling state. Expressions, in the form of lambda expressions, to be reduced to a final result are so distributed through groups of the cells 11 that only primitive operations and communication need be carried out by the cells 11.
