L-hat(ID:5443/lha001)
SHARE Information Algebra
or L with a Circumflex or better still
![]("images/l-hat.gif")
Language from the SHARE committee which was trying to develop an information algebra from a different perspective to the CODASYL Information Algebra, by developing a system that was not derived mainly from practical considerations.
Based in part on Zermelo set theory and the protosyntactical primitive of Quine.
Places
Related languages
| Quine | => | L-hat | Based on | |
| SHARE Information Algebra | => | L-hat | Evolution of | |
| Zermelo-Fraenkel | => | L-hat | Based on |
References:
THE FOUNDATIONS OF A THEORY OF DATA PROCESSING
Thomas B. Steel, Jr.
System Development Corporation
Until quite recently the only serious effort to develop a comprehensive theoretical formulation of the science of data processing, apart from purely linguistic considerations, has been the establishment of the theory of autoa mata in the framework of mathematical logic. Although having undoubted intrinsic merit, this study has rarely, if ever, provided insights into the practical, day-to-day problem of applied data processing. This situation may not persist forever, but it is clear that, at present, a large gap exists between the abstract machine of theory and the real machine of the shop. Many specific problem areas, of course, have seen considerable analysis of a theoretical nature. Examples would include the sorting problem and the compiling problem. Certainly one major aspect of the subject, numerical computation, has been under intensive development since the time of Gauss. In none of these cases, however, has there been a serious search for unifying principles° In view of the current efforts to define programning languages which include the ability to prescribe complex processes, this absence of a coherent theory of such processes is deplorable. Several attempts to correct this situation are under development at the present time. Two of these activities, the information algebra of the CODASYL Language Structures Group and the investigation of generalized arrays by the SHARE Theory of Information Handling Commttee, have provided the principal inspiration for the studies reported in this paper. While superficially quite different, these two investigations have an underlying unity that is evident on close study. This emerging isomorphism is taken as a heuristic argument for the general soundness of the approach. Specifically, the work reported here is the embedding of the notion of generalized array in a system of formal logic. The objective is twofold. First, it permits the analyst to bring to bear the fruits of an intensively cultivated field on the objects of study. Secondly, the involvement of a formal structure suggests the possibility that macaine processing of the results of these studies may not be so remote. Tae author is convinced taat it has been tae failure to employ explicit formal systems that is primarily responsible for the sea of confusion now surrounding the subject of a theory of data processing.
Time and space prohibit the complete delineation of the formal system.
In essence it is an axiomatic set theory built on an underlying logical foundation similar to that developed by Quine. Following Zermelo, the various antinomies are avoided by admitting only certain classes to membership in the universe° The usual definitions of "subclass", "union", "intersection", "complement" and "unit class" are then made and traditional Boolean algebra is derived in a standard fashion.
The critical notion for the definition of generalized arrays is that of "ordered pair". If we employ the notation:
{•••x•••}
to represent the set whose members are Just those entities displayed within the curly brackets, "ordered pair" may be defined as follows:
A "relation" is defined as a set, each of whose members is an ordered pair, and a "function" is defined as a relation, each of whose members has a unique second coordinate. The "domain" of a relation, symbolized as "D ", is defined as the set of all first coordinates of member pairs, and the "converse domain" of a relation, symbolized as "^D" [used in place of upside down D in original], is defined as the set of all second coordinates of member pairs. Viewing second coordinates as arguments and first coordinates as the corresponding values in the case of a function, it is evident that all functions are single valued. Given a function, f, whose values are non-empty sets, another function, g, is said to be a "selection function" with respect to f if ^Df = ^Dg and, for all arguments, x, g(x) Epsilon f(x). Thus, for any argument, the function g selects a member of the value of f for that argument.
An "array" is defined as any function whose converse domain is the set of all selection functions with respect to same function, called the "dimension function" of the array. Here, the arguments of the dimension function are the names of the dimensions of the array and the values of the dimension function are the sets of index values which the corresponding dimensions can take. Note that this definition has no element of ordering in its construction.
This notion of an array is best explicated by an example [omitted]
The dimension function of the above array is the following:
[omitted]
In this formulation of the notion of array, the names and index values of the dimensions are given exact status. It is possible, therefore, to define a set of mapping operators to modify these names and values so that a collection of arrays can be given identical or distinct names and values for any or all dimensions° In addition, a new dimension with a single index value caube created without modifying the information contained in the actual values of the array itself. In this way compatibility of the number of dimensions can be gained for a set of arrays. Finally, a coupling operator can be defined which specializes into union, intersection, dot product or cross product, depending on the earlier application of name modification operators.
Careful reflection on the nature of these arrays and the possible kinds of operations on them shows that classical operations of file maintenance and data retrieval are describable in these terms as well as the obvious treatment of the more usual kinds of arrays.
in Proceedings of the 16th ACM National Conference, January 1961 view details
in Proceedings of the 16th ACM National Conference, January 1961 view details
in Proceedings of the 16th ACM National Conference, January 1961 view details
Introduction
The development in recent years of programming languages, such as COBOL, FACT and JOVIAL, whose principal field of application is other than scientific computing, has led to a growing recognition of the importance of data description. Virtually all theoretical work concerning programming languages, however, has been concentrated on the procedure aspect of these languages. It is the object of the study upon which this paper reports to develop a comprehensive theory of data structures and their descriptions in such a fashion that it can be wedded to a theory of algorithms, yielding a more complete theory of programming languages. Two interlocked efforts comprise the heart of the study to date. The first is the development of a mathematical construct--called a general array--designed to have as models the possible data structures relevant to discrete automata. Study of this construct as a mathematical object will, it is hoped, lead to valuable insights into the manipulatable properties of the models. Some evidence is presented that, in fact, this hope may be realized, although it is yet too early to claim success.
The second effort is the construction of a formal theory, adequate to cope with the array constructs as well as the better known linguistic entities that constitute programming languages. This is done by adapting a formal system which includes Zermelo set theory and the protosyntactical primitive of Quine, slightly reinterpreted to permit a complex alphabet. Additionally, an innovation is made whereby abbreviations are not to be construed as imaginary; rather, they form an integral part of the system. This is done in recognition of the fact that data processing machinery has finite and bounded storage devices.
The resulting language, called "
", together with a designated inference scheme, has all the power, as well as all the pitfalls, of typical formalizations of set theory. In contrast to the bulk of such systems studied in modern logic, however, is designed to expedite the resolution of solvable problems, not to aid in the delineation of unsolvable ones. Accordingly, it may well appear unnecessarily fussy to the working programmer and, at the same time, overly disorganized to the logician. It is offered as a first iteration at a suitable compromise between elegance and utility.Most of the work done to date that has pretensions of being theoretical[ analyses of data structures (Colilla and Sams [1962], Gower [1962], Hoffman [1962], etc.) suffers from being obviously practical. The object of these researches has been to develop something that would be a useful algorithm for immediate application, and as a result little attention has been given to the general problem of characterizing all possible data structures. Notably different in approach has been the work of two committees: the Language Structures Group of the CODASYL Development Committee and the SHARE Theory of Information Handling Committee. The former work has been reported in Bosak [1961] and CODASYL [1962], the latter in Smith [1961], Steel [1961] and Steel [1962], and both have been briefly treated in McGee [1962]. The spirit of this enterprise has been much the same as that shown in Levien [1962] with respect to algorithm theory; reaching for full generality in the concepts and absolute rigor, yet hopefully maintaining at least one toe on the ground.
The remarks in the preceding two paragraphs should not be read as demeaning the other work. Practical problems do require solution. On the other hand, so little work is being done on the theory of data structures by comparison with the effort being expended ors the theory of command languages, that a plea for more seems not out of order.
The real heart of this paper is the description of the language
. A not yet complete document exactly explicating -- and just that part included here -- already runs to more than 150 pages--a length of discourse not appropriate in the present context. Therefore, the description in this paper has been pared considerably. An astute reader with the proper background could probably puzzle it all out in time, but nobody with any sense would try.Accordingly, some brief, informal remarks are prefixed, concentrating on the problem of general arrays, in the hope of leading the reader to a grasp of the concept if not its detail. Even so, it is necessary to assume some sophistication on the part of the reader, i.e. at ]east an understanding of elementary set theory such as one finds in Halmos [1960]. For this the author can only regret that progress and pedagogy are so often far apart.
in [ACM] CACM 7(02) (Feb 1964) includes Papers presented at a Working Conference on Mechanical Language Structures, Princeton, N. J., August 1963 view details