Network Working Group Richard Winter, Jeffrey Hill, Warren Greiff
RFC # 610 CCA
NIC # 21352 December 15, 1973
Further Datalanguage Design Concepts
Richard Winter
Jeffrey Hill
Warren Greiff
Computer Corporation of America
December 15, 1973
Winter, Hill & Greiff [Page 1]
RFC 610 Further Datalanguage Design Concepts December 1973 Acknowledgment During the course of the Datacomputer Project, many people have contributed to the development of datalanguage. The suggestions and criticisms of Dr. Gordon Everest (University of Minnesota), Dr. Robert Taylor (University of Massachusetts), Professor Thomas Cheatham (Harvard University) and Professor George Mealy (Harvard University) have been particularly useful. Within CCA, several people in addition to the authors have participated in the language design at various stages of the project. Hal Murray, Bill Bush, David Shipman and Dale Stern have been especially helpful. Winter, Hill & Greiff [Page 2]
RFC 610 Further Datalanguage Design Concepts December 1973 1. Introduction 1.1 The Datacomputer System The datacomputer is a large-scale data utility system, offering data storage and data management services to other computers. The datacomputer differs from traditional data management systems in several ways. First, it is implemented on dedicated hardware, and comprises a separate computing system specialized for data management. Second, the system is implemented on a large scale. Data is intended to be stored on mass storage devices, with capacities in the range of a trillion bits. Files on the order of one hundred billion bits are to be kept online. Third, it is intended to support sharing of data among processes operating in diverse environments. That is, the programs which share a given data base may be written in different languages, execute on different hardware under different operating systems, and support end users with radically different requirements. To enable such shared use of a data base, transformations between various hardware representations and data structuring concepts must be achieved. Finally, the datacomputer is designed to function smoothly as a component of a much larger system: a computer network. In a computer network, the datacomputer is a node specialized for data management, and acting as a data utility for the other nodes. The Arpanet, for which the datacomputer is being developed, is an international network which has over 60 nodes. Of these, some are presently specialized for terminal handling, others are specialized for computation (e.g., the ILLIAC IV), some are general purpose service nodes (e.g., MULTICS) and one (CCA) is specialized for data management. 1.2 Datalanguage Datalanguage is the language in which all requests to the datacomputer are stated. It includes facilities for data description and creation, for retrieval of or changes to stored data, and for access to a variety of auxiliary facilities and services. In datalanguage it is possible to specify any operation the datacomputer is capable of performing. Datalanguage is the only language accepted by the datacomputer and is the exclusive means of access to data and services. Winter, Hill & Greiff [Page 3]
RFC 610 Further Datalanguage Design Concepts December 1973 1.3 Present Design Effort We are now engaged in developing complete specifications for datalanguage; this is the second iteration in the language design process. A smaller, initial design effort developed some concepts and principles which are described in the third working paper in this series. These have been used as the basis of software implementations resulting in an initial network service capability. A user manual for this system was published as working paper number 7. As a result of experience gained in implementation and service, through further study of user requirements and work with potential users, and through investigation of other work in the data management field, quite a few ideas have been developed for the improvement of datalanguage. These are being assimilated into the language design in the iteration now in progress. When the language design is complete, it will be incorporated into the existing software (requiring changes to the language compiler, but having little impact on the rest of the system). Datacomputer users will first have access to the new language during 1975. 1.4 Purpose of this Paper This paper presents concepts and preliminary results, rather than a completed design. There are two reasons for publishing now. The first is to provide information to those planning to use the datacomputer. They may benefit from knowledge of our intentions for development. The second is to enable system and language designers to comment on our work before the design is frozen. 1.5 Organization of the Paper The remainder of the paper is divided into four sections. Section 2 discusses the most global considerations for language design. This comprises our view of the problem; it has influenced our work to date and will determine most of our actions in completion of the design. This section provides background for section 3, and reviews some Winter, Hill & Greiff [Page 4]
RFC 610 Further Datalanguage Design Concepts December 1973 material that will be familiar to those who have been following our work closely. Section 3 discusses some of the specific issues we have worked on. The emphasis is on solutions and options for solution. In sections 2 and 3 we are presenting our "top-down" work: this is the thinking we have done based on known requirements and our conception of the desirable properties of datalanguage. We have also been working from the opposite end, developing the primitives from which to construct the language. Section 4 presents our work in this area: a model datacomputer which will ultimately provide a precise semantic definition of datalanguage. Section 4 explains that part of the model which is complete, and relates this to our other work. Section 5 discusses work that remains, both on the model and in our top-down analysis. Winter, Hill & Greiff [Page 5]
RFC 610 Further Datalanguage Design Concepts December 1973 2. Considerations for Language Design 2.1 Introduction Data management is the task of managing data as a resource, independent of hardware and applications programs. It can be divided it into five major sub-tasks: (1) _creating_ databases in storage, (2) making the data _available_ (e.g., satisfying queries), (3) _maintaining_ the data as information is added, deleted and modified, (4) assuring the _integrity_ of the data (e.g., through backup and recovery systems, through internal consistency checks), (5) _regulating_access_, to protect the databases, the system, and the privacy of users. These are the major data-related functions of the datacomputer; while the system will ultimately provide other services (such as accounting for use, monitoring performance) these are really auxiliary and common to all service facilities. This section presents global considerations for the design of datalanguage, based on our observations about the problem and the environment in which it is to be solved. The central problem is data management, and the datacomputer shares the same goals as many currently available data management systems. Several aspects of the datacomputer create a unique set of problems to be solved. 2.2 Hardware Considerations 2.2.1 Separate Box The datacomputer is a complete data management utility in a separate, closed box. That is, the hardware, the data and the data management software are segregated from any general-purpose processing facilities. There is a separate installation dedicated to data management. Datalanguage is the only means users have for communicating with the datacomputer and the sole activity of the datacomputer is to process datalanguage requests. Dedicating hardware provides an obvious advantage: one can specialize it for data management. The processor(s) can be modified to have data management "instructions"; common low-level software functions can be built into the hardware. Winter, Hill & Greiff [Page 6]
RFC 610 Further Datalanguage Design Concepts December 1973 A less obvious, but possibly more significant, advantage is gained from the separateness itself. The system can be more easily protected. A fully-developed datacomputer on which there is only maintenance activity can provide a very carefully controlled environment. First, it can be made as physically secure as required. Second, it needs to execute only system software developed at CCA; all user programs are in a high-level language (datalanguage) which is effectively interpreted by the system. Hence, only datacomputer system software processes the data, and the system is not very vulnerable to capture by a hostile program. Thus, since there is the potential to develop data privacy and integrity services that are not available on general-purpose systems, one can expect less difficulty in developing privacy controls (including physical ones) for the datacomputer than for the systems it serves. 2.2.2 Mass Storage Hardware The datacomputer will store most of its data on mass storage devices, which have distinctive access characteristics. Two examples of such hardware are Precision Instruments' Unicon 690 and Ampex Corporation's TBM system. They are quite different from disks, and differ significantly from one another. However, almost all users will be ignorant of the characteristics of these devices; many will not even know that the data they use is at the datacomputer. Finally, as the development of the system progresses, data may be invisibly shunted from one datacomputer to another, and as a result be stored in a physical format quite different from that originally used. In such an environment, it is clear that requests for data should be stated in logical, not physical terms. 2.3 Network Environment The network environment provides additional requirements for datacomputer design. 2.3.1 Remote Use Since the datacomputer is to be accessed remotely, the requirement for effective data selection techniques and good mechanisms for the expression of selection criteria is amplified. This is because of the narrow path through which network users communicate with the datacomputer. Presently, a typical process-to-process transfer rate over the Arpanet is 30 kilobits per second. While this can be increased through optimization of software and protocols, and through additional Winter, Hill & Greiff [Page 7]
RFC 610 Further Datalanguage Design Concepts December 1973 expenditure for hardware and communications lines, it seems safe to assume that it will not soon approach local transfer rates (measured in the megabits per second). A typical request calls for either transfer of part of a file to a remote site, or for selective update to a file already stored at the datacomputer. In both of these situations, good mechanisms for specifying the parts of the data to be transmitted or changed will reduce the amount of data ordinarily transferred. This is extremely important because with the low per bit cost of storing data at the datacomputer, transmission costs will be a significant part of the total cost of datacomputer usage. 2.3.2 Interprocess Use of the Datacomputer System Effective use of the network requires that groups of processes, remote from one another, be capable of cooperating to accomplish a given task or provide a given service. For example, to solve a given problem which involves array manipulation, data retrieval, interaction with a user at a terminal, and the generalized services of a language like PL/I, it may be most economical to have four cooperating processes. One of these could execute at the ILLIAC IV, one at the datacomputer, one at MULTICS, and one at a TIP. While there is overhead in setting up these four processes and in having them communicate, each is doing its job on a system specialized for that job. In many cases, the result of using the specialized system is a gain of several orders of magnitude in economy or efficiency (for example, online storage at the datacomputer has a capital cost two orders of magnitude lower than online costs on conventional systems). As a result, there is considerable incentive to consider solutions involving cooperating processes on specialized systems. To summarize: the datacomputer must be prepared to function as a component of small networks of specialized processes, in order that it can be used effectively in a network in which there are many specialized nodes. 2.3.3 Common Network Data Handling A large network can support enough data management hardware to construct more than one datacomputer. While this hardware can be combined into one even larger datacomputer, there are advantages to configuring it as two (or possibly more) systems. Each system should be large enough to obtain economies of scale in data storage and to support the data management software. Important data bases can be duplicated, with a copy at each datacomputer; if one datacomputer fails, or is cut off by Winter, Hill & Greiff [Page 8]
RFC 610 Further Datalanguage Design Concepts December 1973 network failure, the data is still available. Even if duplicating the file is not warranted, the description can be kept at the different datacomputers so that applications which need to store data constantly can be guaranteed that at least one datacomputer is available to receive input. These kinds of failure protection involve cooperation between a pair of datacomputers; in some sense, they require that the two datacomputers function as a single system. Given a system of datacomputers (which one can think of as a small network of datacomputers), it is obviously possible to experiment with providing additional services on the datacomputer-network level. For example, all requests could be addressed simply to the datacomputer-network; the datacomputer-network could then determine where each referenced file was stored (i.e., which datacomputer), and how best to satisfy the request. Here, two kinds of cooperation in the network environment have been mentioned: cooperation among processes to solve a given problem, and cooperation among datacomputers to provide global optimizations in the network-level data handling problem. These are only two examples, especially interesting because they can be implemented in the near term. In the network, much more general kinds of cooperation are possible, if a little farther in the future. For example, eventually, one might want the datacomputer(s) to be part of a network-wide data management system, in which data, directories, services, and hardware were generally distributed about the network. The entire system could function as a whole under the right circumstances. Most requests would use the data and services of only a few nodes. Within this network-wide system, there would be more than one data management system, but all systems would be interfaced through a common language. Because the datacomputers represent the largest data management resource in the network, they would certainly play an important role in any network-wide system. The language of the datacomputer (datalanguage) is certainly a convenient choice for the common language of such a system. Thus a final, albeit futuristic, requirement imposed by the network on the design of the datacomputer system, is that it be a suitable major component for network-wide data management systems. If feasible, one would like datalanguage to be a suitable candidate for the common language of a network-wide group of cooperating data management systems. 2.4 Different Modes of Datacomputer Usage Within this network environment, the datacomputer will play several roles. In this section four such roles are described. Each of them imposes constraints on the design of datalanguage. We can analyze them in terms of four overlapping advantages which the datacomputer provides: Winter, Hill & Greiff [Page 9]
RFC 610 Further Datalanguage Design Concepts December 1973 1. Generalized data management services 2. Large file handling 3. Shared access 4. Economic volume storage Of course, the primary reason for using the datacomputer will be the data management services which it provides. However, for some applications size will be the dominating factor in that the datacomputer will provide for online access to files which are so large that previously only offline storage and processing were possible. The ability to share data between different network sites with widely different hardware is another feature provided only by the datacomputer. Economies of scale make the datacomputer a viable substitute for tapes in such applications as operating system backup. Naturally, a combination of the above factors will be at work in most datacomputer applications. The following subsections describe some possible modes of interaction with the datacomputer. 2.4.1 Support of Large Shared Databases This is the most significant application of the datacomputer, in nearly every sense. Projects are already underway which will put databases of over one hundred billion bits online on the Arpanet datacomputer. Among these are a database which will ultimately include 10 years of weather observations from 5000 weather stations located all over the world. As online databases, these are unprecedented in size. They will be of international interest and be shared by users operating on a wide variety of hardware and in a wide variety of languages. Because these databases are online in an international network, and because they are expected to be of considerable interest to researchers in the related fields, it seems obvious that there will be extremely broad patterns of use. A strong requirement, then, is a flexible and general approach to handling them. This requirement of providing different users of a database with different views of the data is an overriding concern of the datalanguage design effort. It is discussed separately in Section 2.5. 2.4.2 Extensions of Local Data management Systems We imagine local data handling systems (data management systems, applications-oriented packages, text-handling systems, etc.) wanting to take advantage of the datacomputer. They may do so because of the Winter, Hill & Greiff [Page 10]
RFC 610 Further Datalanguage Design Concepts December 1973 economics of storage, because of the data management services, or because they want to take advantage of data already stored at the datacomputer. In any case, such systems have some distinctive properties as datacomputer users: (1) most would use local data as well as datacomputer data, (2) many would be concerned with the translation of local requests into datalanguage. For example, a system which does simple data retrieval and statistical analysis for non-programming social scientists might want to use a census database stored at the datacomputer. Such a system may perform a range of data retrieval functions, and may need sophisticated interaction with the datacomputer. Its usage patterns would make quite a contrast with those of a single application program whose sole use of the datacomputer involves printing a specific report based on a single known file. This social-science system would also use some local databases, which it keeps at its own site because they are small and more efficiently accessed locally. One would like it to be convenient to think of data the same way, whether it is stored locally or at the datacomputer. Certainly at the lower levels of the local software, there will have to be differences in interfacing; it would be nice, however, if local concepts and operations could easily be translated into datalanguage. 2.4.3 File Level Use of the Datacomputer In this mode of use, other computer systems take advantage of the online storage capacity of the datacomputer. To these systems, datacomputer storage represents a new class of storage: cheaper and safer than tape, nearly as accessible as local disk. Perhaps they even automatically move files between local online storage and the datacomputer, giving users the impression that everything is stored locally online. The distinctive feature of this mode of use is that the operations are on whole files. A system operating in this mode uses only the ability to store, retrieve, append, rename, do directory listings and the like. An obvious way to make such file level handling easily available to the network community is to make use of the File Transfer Protocol (see Network Information Center document #17759 -- File Transfer Protocol) already in use for host to host file transfer. Although such "whole file" usage of the datacomputer would be motivated primarily by economic advantages of scale, data sharing at the file level could also be a concern. For example, the source files of common network software might reside at the datacomputer. These files have Winter, Hill & Greiff [Page 11]
RFC 610 Further Datalanguage Design Concepts December 1973 little or no structure, but their common use dictates that they be available in a common, always accessible place. It is taking advantage of the economics of the datacomputer, more than anything else, since most of these services are available on any file system. This mode of use is mentioned here because it may account for a large percentage of datalanguage requests. It requires only capabilities which would be present in datalanguage in any case; the only special requirement is to make sure it is easy and simple to accomplish these tasks. 2.4.4 Use of Datacomputer for File Archiving This is another economics-oriented application. The basic idea is to store on the datacomputer everything that you intend to read rarely, if ever. This could include backup files, audit trails, and the like. An interesting idea related to archiving is incremental archiving. A typical practice, with regard to backing up data stored online in a time-sharing system, is to write out all the pages which are different than they were in the last dump. It is then possible to recover by restoring the last full dump, and then restoring all incremental dumps up to the version desired. This system offers a lower cost for dumping and storage, and a higher cost for recovery; it is appropriate when the probability of needing a recovery is low. Datalanguage, then, should be designed to permit convenient incremental archiving. As in the case of the previous application (file system), archiving is important as a design consideration because of its expected frequency and economics, not because it necessarily requires any extra generality at the language level. It may dictate that specialized mechanisms for archiving be built into the system. 2.5 Data Sharing Controlled sharing of data is a central concern of the project. Three major sub-problems in data sharing are: (1) concurrent use, (2) independent concepts of the same database, and (3) varying representations of the same database. Concurrent use of a resource by multiple independent processes is commonly implemented for data on the file level in systems in which files are regarded as disjoint, unrelated objects. It is sometimes implemented on the page level. Considerable work on this problem has already been done within the Winter, Hill & Greiff [Page 12]
RFC 610 Further Datalanguage Design Concepts December 1973 datacomputer project. When this work is complete, it will have some impact on the language design; by and large however, we do not consider this aspect of concurrent use to be a language problem. Other aspects of the concurrent use problem, however, may require more conscious participation by the user. They relate to the semantics of collections of data objects, when such collections span the boundaries of files known to the internal operating system. Here the question of what constitutes an update conflict is more complex. Related questions arise in backup and recovery. If two files are related, then perhaps it is meaningless to recover an earlier state of one without recovering the corresponding state of the other. These problems are yet to be investigated. Another problem in data sharing is that not all users of a database should have the same concept of that database. Examples: (1) for privacy reasons, some users should be aware of only part of the database (e.g., scientists doing statistical studies on medical files do not need access to name and address), (2) for program-data independence, payroll programs should access only data of concern in writing paychecks, even though skill inventories may be stored in the same database, (3) for global control of efficiency, simplicity in application programming, and program-data independence each application program should "see" a data organization that is best for its job. To further analyze example (3), consider a database which contains information about students, teachers, subjects and also indicates which students have which teachers for which subjects. Depending on the problem to be solved, an application program may have a strong requirement for one of the following organizations: (1) entries of the form (student,teacher,subject) with no concern about redundancy. In this organization an object of any of the three types may occur many times. (2) entries of the form (student, (teacher,subject), (teacher,subject), . . . (teacher,subject)) (3) entries of the form (teacher, subject,(student...student), subject,(student...student), subject,(student.. .student)) and other organizations are certainly possible. One approach to this problem is to choose an organization for stored data, and then have application programs write requests which organize Winter, Hill & Greiff [Page 13]
RFC 610 Further Datalanguage Design Concepts December 1973 output in the form they want. The application programmer applies his ingenuity in stating the request so that the process of reorganization is combined with the process of retrieval, and the result is relatively efficient. There are important, practical situations in which this approach is adequate; in fact there are situations in which it is desirable. In particular, if efficiency or cost is an overriding consideration, it may be necessary for every application programmer to be aware of all the data access and organization factors. This may be the case for a massive file, in which each retrieval must be tuned to the access strategy and organization; any other mode of operation would result in unacceptable costs or response times. However, dependence between application programs and data organization or access strategy is not a good policy in general. In a widely-shared database, it can mean enormous cost in the event of database reorganization, changes to access software, or even changes in the storage medium. Such a change may require reprogramming in hundreds of application programs distributed throughout the network. As a result, we see a need for a language which supports a spectrum of operating modes, including: (1) application program is completely independent of storage structure, access technique, and reorganization strategy, (2) application program parametrically controls these, (3) application program entirely controls them. For a widely-shared database, mode (1) would be the preferred policy, except when (a) the application programmer could do a better job than the system in making decisions, and (b) the need for this increment of efficiency outweighed the benefits of program-data independence. In evaluating this question for a particular application, it is important to realize the role of global efficiency analysis. When there are many users of a database, in some sense the best mode of operation is that which minimizes the total cost of processing all requests and the total cost of storing the data. When applications come and go, as real-world needs change, then the advantages of centralized control are more likely to outweigh the advantages of optimization for a particular application program. The third major sub-problem arises in connection with item level representations. Because of the environment in which it executes, each application program has a preferred set of formatting concepts, length indicators, padding and alignment conventions, word sizes, character representations, and so on. Once again it is better policy for the application program to be concerned only with the representations it wants and not with the stored data representation. However, there will be cases in which efficiency for a given request overrides all other factors. Winter, Hill & Greiff [Page 14]
RFC 610 Further Datalanguage Design Concepts December 1973 At this level of representation, there is at least one additional consideration: potential loss of information when conversion takes place. Whoever initiates a type conversion (and this will sometimes be the datacomputer and sometimes the application program) must also be responsible for seeing that the intent of the request is preserved. Since the datacomputer must always be responsible for the consistency and the meaning of a shared database, there are some conflicts to be resolved here. To summarize, it seems that the result of wide sharing of databases is that a larger system must be considered in choosing a data management policy for a particular database. This larger system, in the case of the datacomputer, consists of a network of geographically distributed applications programs, a centralized database, and a centralized data management system. The requirement for datalanguage is to provide flexibility in the management of this larger system. In particular, it must be possible to control when and where conversions, data re- organizations, and access strategies are made. 2.6 Need for High Level Communication All of the above considerations point to the need for high level communication between the datacomputer and its users. The complex and distinct nature of datacomputer hardware make it imperative that requests be put to the datacomputer so that it can make major decisions regarding the access strategies to be used. At the same time, the large amounts of data stored and the demand of some users for extremely high transmission bandwidths make it necessary to provide for user control of some storage and transmission schemes. The fact that databases will be used by applications which desire different views of the same data and with different constraints means that the datacomputer must be capable of mapping one users request onto another users data. Interprocess use of the datacomputer means that datasharing must be completely controllable to avoid the need for human intervention. Extensive facilities for ensuring data integrity and controlling access must be provided. 2.6.1 Data Description Basic to all these needs is the requirement that the data stored at the datacomputer be completely described in both functional and physical parameters. A high level description of the data is especially important to provide the sharing and control of data. The datacomputer must be able to map between different hardware and different applications. In its most trivial form this means being able to convert between floating point number representations on different machines. On Winter, Hill & Greiff [Page 15]
RFC 610 Further Datalanguage Design Concepts December 1973 the other extreme it means being able to provide matrix data for the ILLIAC IV as well as being able to provide answers to queries from a natural language program, both addressed to the same weather data base. Data descriptions must provide the ability to specify the bit level representations and the logical properties and relationships of data. 2.6.2 Data integrity and Access Control In the environment we have been describing, the problems of maintaining data integrity and controlling use of data assume extreme importance. Shared use of datacomputer files depends on the ability of the datacomputer to guarantee that the restrictions on data-access are strictly enforced. Since different users will have different descriptions, the access control mechanism must be associated with the descriptions themselves. One can control access to data by controlling access to its various descriptors. A user can be constrained to access a given data base only through one specific description which limits the data he can access. In a system where the updaters of a database may be unknown to each other, and possibly have different views of the data, only the datacomputer can assure data integrity. For this reason, all restrictions on possible values of data objects, and on possible or necessary relationships between objects must be stated in the data description. 2.6.3 Optimization The decisions regarding data access strategy must ordinarily be made at the datacomputer, where knowledge of the physical considerations is available. These decisions cannot be made intelligently unless the requests for data access are made at a high level. For example, compare the following two situations: (1) a request calls for output of _all_ weather observations made in California exhibiting certain wind and pressure conditions, (2) a series of requests is sent, each one retrieving California weather observations; when a request finds an observation with the required wind and pressure conditions, it transmits this observation to a remote system. Both sessions achieve the same result: the transmission of a certain set of observations to a remote site for processing. In the first session, however, the datacomputer receives, at the outset, a description of the data that is needed; in the second, it processes a series of requests, each one of which is a surprise. In the first case, a smart datacomputer has the option of retrieving all of the needed data in one access to the mass storage device. It can then buffer this data on disk until the user is ready to accept it. In Winter, Hill & Greiff [Page 16]
RFC 610 Further Datalanguage Design Concepts December 1973 the second case, the datacomputer lacks the information it needs to make such an optimization. The language should permit and encourage users to provide the information needed to do optimization. The cost of not doing it is much higher with mass storage devices and large files than it is in conventional systems. 2.7 Application Oriented Concerns In the above sections we have described a number of features which the datacomputer system must provide. In this section we focus on what is necessary to make these features readily available to users of the datacomputer. 2.7.1 Datacomputer-user Interaction An application interacts with the datacomputer in a _session_. A session consists of a series of requests. Each session involves connecting to the datacomputer via the network, establishing identities, and setting up transmission paths for both data and datalanguage. Datalanguage is transmitted in character mode (using network standard ASCII) over the datalanguage connection. Error and status messages are sent over this connection to the application program. The data connection (called a PORT) is viewed as a bit stream and is given its own description. These descriptions are similar to those given for stored data. At a minimum this description must contain enough information for the datacomputer to parse the incoming bit stream. It also may contain data validation information as well. To store data at the datacomputer, the stored data must also have a description. The user supplies the mapping between the descriptions of the stored and transmitted data. Winter, Hill & Greiff [Page 17]
RFC 610 Further Datalanguage Design Concepts December 1973 _____________________________________ | | / / | ______ ___________ | \ \ | | |---| | | / / | | | | DATA | | \ \ | | | |DESCRIPTION| _______ | DATALANGUAGE ___________ | | | |___________| | |<-------------------->| | | |STORED| |________| USER | | PATH |APPLICATION| | | DATA |__________________|REQUEST| | | PROGRAM | | | | |_______|<----!--------------->|___________| | | | ___________ | ! DATA PATH | | | | | | ! / / | | | | PORT |-----! \ \ | | | |DESCRIPTION| | / / | |______| |___________| | \ \ |_____________________________________| / / NETWORK Figure 2-1 A Model of Datacomputer/User Interaction 2.7.2 Application Features for Data Sharing In using data stored at the datacomputer, users may supply a description of the data which is customized to the application. This description is mapped onto the description of the stored data. These descriptions may be at different levels. That is, one may merely rearrange the order of certain items, while another could call for a total restructuring of the stored representation. So that each user may be able to build upon the descriptions of another, data entities should be given named types. These type definitions are of course to be stored along with the data they describe. In addition, certain functions are so closely tied to the data (in fact may be the data in the virtual description case -- see section 3), that they must also reside in the datacomputer and their tie with the data items should be maintained by the datacomputer. For example, one user can describe a data base as made up of structures containing data of the types _latitude_ and _longitude_. He could also describe functions for comparing data of this type. Other users, not concerned with the structure of the _latitude_ component itself, but interested in using this information simply to extract other fields of interest can then use the commonly provided definitions and functions. Furthermore, by adopting this strategy as many users as possible can be made insensitive to changes in the file which are tangential to their main interests. For example, _latitudes_ could be changed from binary representation to a character form and if use of that field were restricted to its definitions and associated functions, existing Winter, Hill & Greiff [Page 18]
RFC 610 Further Datalanguage Design Concepts December 1973 application systems would be unaffected. Conversion functions could be defined to eliminate the impact on currently operating programs. The ability of such definitional facilities means that groups of users can develop common functions and descriptions for dealing with shared data and that conventions for use of shared data can be enforced by the datacomputer. These facilities are discussed under _extensibility_ in Section 3. ___________________________________________ _______________ | ____________ | | ___________ | | |APPLICATION | | | |APPLICATION| | | _| DATA |_|____|_| PROGRAM | | | | |DESCRIPTIONS| | | |___________| | | | |____________| | |_______________| | | ^ | HOST 1 | ______ | | | | | | | _____|______ | | | | | | DATA | | | | | | | FUNCTIONS | | | | | | |____________| | _______________ | | | ___________ | ____________ | | ___________ | | | | | STORED |__| | | | | |APPLICATION| | | | |__| DATA |____| |_|____|_| PROGRAM | | | |STORED| |DESCRIPTION|__ | | | | |___________| | | | DATA | |___________| | |____________| | | | | | | ^ | ____________ | | ___________ | | | | | | | | | | |APPLICATION| | | | | _____|_____ | | |_|____|_| PROGRAM | | | | | | DATA | |_| | | | |___________| | | | | | FUNCTIONS | |____________| | |_______________| | |______| |___________| | HOST 2 |___________________________________________| DATACOMPUTER Figure 2-2 Multiple User Interaction with the Datacomputer 2.7.3 Communication Model We intend that datalanguage, while at a high level conceptually, will be at a low level syntactically. Datalanguage provides a set of primitive functions, and a set of commonly used higher level functions (see section 4 on the datalanguage model). In addition, users can define their own functions so that they can communicate with the datacomputer at a level as conceptually close to the application as possible. Winter, Hill & Greiff [Page 19]
RFC 610 Further Datalanguage Design Concepts December 1973 There are two reasons for datalanguage being at a low level syntactically. First, it is undesirable to have programs composing requests into an elaborate format only to be decomposed by the datacomputer. Second, by choosing a specific high level syntax, the datacomputer would be imposing a set of conventions and terminology which would not necessarily correspond to those of most users. DATACOMPUTER ENVIRONMENT | OUTSIDE ENVIRONMENT | _______ | |____ | __|GENERAL|____ | | DMS |____ | | |_______| _________ ________ _________ | | | | HIGHER | | |__| _______ ________ |PRIMITIVE|___| LEVEL |___|LOW-LEVEL|_____|COBOL | | COBOL | |LANGUAGE | |LANGUAGE| | SYNTAX |__ |SERVER |___|PROGRAM | |_________| |________| |_________| | |_______| |________| | | _______ |__|ON LINE| | | QUERY |_______ |_______| | | ___|____ |TERMINAL| | | USERS | |________| | APPLICATION APPLICATIONS | SERVERS Figure 2-3 Datacomputer/User Working Environment 2.8 Summary In this section we have presented the major considerations which have influenced the current datalanguage design effort. The datacomputer has much in common with most large-scale shared data management systems, but also has a number of overriding concerns unique to the datacomputer concept. The most important of these are the existence of a separate box containing both hardware and software, the control of an extremely large storage device, and embedding in a computer network environment. Data sharing in such an environment is a central concern of the design. Both extensive data description facilities and high level communication Winter, Hill & Greiff [Page 20]
RFC 610 Further Datalanguage Design Concepts December 1973 between user and datacomputer are necessary for data integrity and for datacomputer optimization of user requests. In addition, the expected use of the datacomputer involves satisfying several conflicting constraints for different modes of operation. One way of satisfying various user needs is to provide datalanguage features so that users may develop their own application packages within datalanguage. Winter, Hill & Greiff [Page 21]
RFC 610 Further Datalanguage Design Concepts December 1973 3. Principal Language Concepts This section discusses the principal facilities of datalanguage. Specific details of the language are not presented, however, the discussion includes the motivation behind the inclusion of the various language features and also defines, in an informal way, the terms we use. 3.1 Basic Data Items Basic data are the atomic level of all data constructions; they cannot be decomposed. All higher level data structures are fundamentally composed of basic data items. Many types of basic data items will be provided. The type of an item determines what operations can be performed on the item and the meaning of those operations. Datalanguage will provide those primitive types of data items which are commonly used in computing systems to model the real world. The following basic types of data will be available in datalanguage: _fixed_point_numbers_, _floating_point_numbers_, _characters_, _booleans_, and _bits_. These types of items are "understood" by the datacomputer system to the extent that operations are based on the type of an item. Datalanguage will also include an _uninterpreted_ type of item, for data which will only be moved (including transmitted) from one place to another. This type of data will only be understood in the trivial sense that the datacomputer can determine if two items of the uninterpreted type are identical. Standard operations on the basic types of items will be available. Operations will be included so that the datacomputer user can describe a wide range of data management functions. They are not included with the intent of encouraging use of the datacomputer for the solving of highly computational problems. 3.2 Data Aggregates Data aggregates are compositions of basic data items and possibly other data aggregates. The types of data aggregates which are provided allow for the construction of hierarchical relationships of data. The aggregates which will definitely be available are classified as _structs_, _arrays_, _strings_, _lists_, and _directories_. A struct is a static aggregate of data items (called _components_). A struct is static in the sense that the components of a struct cannot be added or deleted from the struct, they are inextricably bound to the struct. Associated with each component of the struct is a name by which that component may be referenced relative to the struct. The struct aggregate may be used to model what is often thought of as a record, Winter, Hill & Greiff [Page 22]
RFC 610 Further Datalanguage Design Concepts December 1973 with each component being a field of that record. A struct can also be used to group components of a record which are more strongly related, conceptually, than other components and may be operated on together. Arrays allow for repetition in data structures. An array, like a struct, is a static aggregate of data items (called _members_). Each member of an array is of the same type. Associated with each member is an index by which that member can be referenced relative to the array. Arrays can he used to model repeating data in a record (repeating groups). The concept of string is actually a hybrid of basic data and data aggregates. Strings are aggregates in that they are compositions (similar to arrays) of more primitive data (e.g., characters). They are, however, generally conceived of as basic in that they are mostly viewed as a unit rather than as a collection of items, where each item has individual importance. Also the meaning of a string is highly dependent on the order of the individual components. In more concrete terms, there are operations which are defined on specific types of strings. For example, the logical operators (_and_, _or_, etc.) are defined to operate on strings of bits. However, there are no operations which are defined on arrays of bits, although there are operations defined on both arrays, in general, and on bits. Strings of characters, bits, and uninterpreted data will be available in datalanguage. Lists are like arrays in that they are collection of similar members. However, lists are dynamic rather than static. Members of a list can be added and deleted from the list. Although, the members of a list are ordered (in fact more than one ordering can be defined on a list), the list is not intended to be referenced via an index, as is the case with an array. Members of a list can be referenced via some method of sequencing through the list. A list member, or set (see discussion under virtual data) of members, can also be referenced, by some method of identification by content. The list structure can be used to model the common notion of a file. Also restrictive use of lists as components of structs provides power with respect to the construction of dynamic hierarchical data relationships below the file level. For example, the members of a list may themselves be, in part, composed of lists, as in a list of families, where each family contains a list of children as well as other information. Directories are dynamic data aggregates which may contain any type of data item. Data items contained in a directory are called _nodes_. Associated with each node of a directory is a name by which that data item can be referenced relative to the directory. As with lists, items may be dynamically added to and deleted from a directory. The primary motivation behind providing the directory capability is to allow the user to group conceptually related data together. Since directories Winter, Hill & Greiff [Page 23]
RFC 610 Further Datalanguage Design Concepts December 1973 need not contain only file type information, "auxiliary" data can be kept as part of the directory. For example, "constant" information, like salary range tables for a corporation data base; or user defined operations and data types (see below) can be maintained in a directory along with the data which may use this information. Also directories may themselves be part of a directory, allowing for a hierarchy of data grouping. Directories will also be defined so that system controlled information can be maintained with some of the subordinate items (e.g. time of creation, time of update, privacy locks, etc.). It may also be possible to allow the data user to define and control his own information which would be maintained with the data. At the least, the design of datalanguage will allow for parametric control over the information managed by the system. Directories are the most general and dynamic type of aggregate data. Both the name and description (see below) of directory nodes exist with the nodes themselves, rather than as part of the description of the directory. Also the level of nesting of a directory is dynamic since directories can be dynamically added to directories. Directories are the only aggregate for which this is true. Datalanguage will also provide some specific and useful variations of the above data aggregates. Structs will be available which allow for optional components. In this case the existence of a component would be based on the contents of other components. It may also he possible to allow for the existence to be based on information found at a higher level of data hierarchy. Similarly, components with _unresolved_ type will be provided. That is the component may be one of a fixed number of types. The type of the component would be based on the contents of other components of the struct. It is also desirable to allow the type or existence of a component to be based on information other than the contents of other components. For instance, the type of one component might be based on the type of another component. In general, we would like for datalanguage to allow for the attributes (see below) of one item to be a function of the attributes of other items. We would also like to provide mixed lists. Mixed lists are lists which contain more than one type of member. In this case the members would have to be self defining. That is, the type of all member would have to be "alike" to the degree that information which defines the type of that member could be found. Similar to components whose type is unresolved are Arrays with unresolved length. In this case, information defining the length of the array must be carried with the array or perhaps with other components of an aggregate which encompasses the array. Winter, Hill & Greiff [Page 24]
RFC 610 Further Datalanguage Design Concepts December 1973 In all of the above cases the type of an item is unresolved to some degree and information which totally resolves the type is carried with the item. It is possible that in some or perhaps all of these cases the datacomputer system could be responsible for the maintenance of this information, making it invisible to the data user. 3.3 General Relational Capabilities The data aggregates described above allow for the modeling of various relationships among data. All relationships which can be constructed are hierarchical. Two approaches can he taken to provide the capability of modeling non- hierarchical relationships. New types of data aggregates can be introduced which will broaden the range of data relationships expressible in datalanguage. Or, a basic data type of "pointer" can be introduced which will serve as a primitive out of which relations can be represented. Pointer would be a data type which establishes some kind of correspondence from one item to another. That is, it would be a method of finding one item, given another . Providing the ability to have items of type pointer does not necessitate the introduction of the concept of address which we deem to be a dangerous step. For example, an item defined to point to a record in a personnel file could contain a social security number which is contained in each record of the file and uniquely identifies that record. In general a pointer is an item of information which can be used to uniquely identify another item. While the pointer approach provides the greater degree of flexibility, it does this at the price of relegating much of the work to the user as well as severely limiting the amount of control the datacomputer system has over the data. A hybrid solution is possible, where some new aggregate data types are provided as well as a restricted form of pointer data type. While the approach to be taken is still being studied, the datalanguage design will include some method of expressing non-hierarchical data structures. 3.4 Ordering of Data Lists are generally viewed as ordered. It is possible, however, that a list can be used to model a dynamic collection of similar items which are not seen as ordered. The unordered case is important, in that, given this information the datacomputer can be more efficient since new members can be added wherever it is convenient. There are a number of ways a list can be ordered. For instance, the ordering of a list can be based on the contents of its members. In the Winter, Hill & Greiff [Page 25]
RFC 610 Further Datalanguage Design Concepts December 1973 simplest case this involves the contents of a basic data item. For example, a list of structs containing information on employees of a company may be ordered on the component which contains the employee's social security number. More complex ordering criteria are possible. For example, the same list could be ordered alphabetically with respect to the employee's last name. In this case the ordering relation is a function of two items, the last and first names. The user might also want to define his own ordering scheme, even for orderings based on basic data items. An ordering could be based on an employee's job title which might even utilize auxiliary data (i.e. data external to the list). It is also possible to maintain a list in order of insertion. In the most general case, the user could dynamically define his ordering by specification of where an item is to be placed as part of his insertion requests. In all of the above cases, data could be maintained in ascending or descending order. In addition to maintenance of a list in some order, it is possible to define one or more orderings "imposed" on a list. These orderings must be based on the contents of a list's members. This situation is similar to the concept of virtual data (see below) in that the list is not physically maintained in a given order, but retrieved as if it were. Orderings of this type can be dynamically formed (see discussion of set under virtual data). Imposed orderings can be accomplished via the maintenance of auxiliary structures (see discussion under internal representation) or by utilization of a sorting strategy on retrievals. Much work has been done with regard to effective implementation of the maintenance and imposition of orderings on lists. This work is described in working paper number 2. 3.5 Data Integrity An important feature of any data management system is the ability to have the system insure the integrity of the data. Data needs to be protected against erroneous manipulation by people and against system failure. Datalanguage will provide automatic validity checks. Many flavors need to be provided so that appropriate trade-offs can be made between the degree of insurance and the cost of validation. The datalanguage user will be able to request constant validation: where validity checks are made whenever the data is updated; validation on access: where validity checks are performed when data is referenced but before it is retrieved; regularly scheduled validation: where the data is checked at regular intervals; background validation: where the system will run checks in its spare time; and validation on demand. Constant validation and validation on access are actually special cases of the more general concept of event triggered validation. In this case the user specifies Winter, Hill & Greiff [Page 26]
RFC 610 Further Datalanguage Design Concepts December 1973 an event which will cause data validation procedures to be invoked. This feature can be used to accomplish such things as validation following a "batch" of updates. Also, some mechanism for specifying combinations of these types would be useful. In order for some of the data validation techniques to be effective, it may be necessary to keep some data validation "bookkeeping" information with the data. For example, information which can be used to determine whether an item has been checked since it was last updated might be used to cause validation on access if there has not been a recent background validation. The datacomputer may provide for optional automatic maintenance of such special kinds of information. In order for the datacomputer system to insure data validity, the user must define what valid is. Two types of validation can be requested. In the first case the user can tell the datacomputer that a specific data item may only assume one of a specific set of values. For example, the color component of a struct may only assume the values 'red', 'green', or 'blue'. The other case is where some relation must hold between members of an aggregate. For example, if the sex component of a struct is 'male' then the number of pregnancies component must be 0. Data validation is only half of the data integrity picture. Data integrity involves methods of restoring damaged data. This requires maintenance of redundant information. Features will be provided which will make the datacomputer system responsible for the maintenance of redundant data and possibly even automatic restoration of damaged data. In section 2 we discussed possible uses of the datacomputer for file backup. All features which are provided for this purpose will also be available as methods of maintaining backup information for restoration of files residing at the datacomputer. 3.6 Privacy Datalanguage will have to provide extensive privacy and protection capabilities. In its simplest form a privacy lock is provided at the file level. The lock is opened with a password key. Associated with this key is a set of privileges (reading, updating, etc.). Two degrees of generality are sought. Privacy should be available at all levels of data. Therefore, groups of related data, including groups of files could be made private by creating private directories. Also, specific fields of records could be made private by having private components of a struct where other components of the struct are visible to a wider (or different) class of users. We would also like the user to be able to define his own mechanism. In this way, very personalized, complex, and hence secure mechanisms can be defined. Also features such as 'everyone can see his own salary' might be possible. Winter, Hill & Greiff [Page 27]
RFC 610 Further Datalanguage Design Concepts December 1973 3.7 Conversion Many types of data are related in that some or all of the possible values of one type of data have an "obvious" translation to the values of another. For example, the character '6' has a natural translation to the integer 6, or the six character string 'abc ' (three trailing blanks) has a natural translation to the four character string 'abc ' (one trailing blank). Datalanguage will provide conversion capabilities for the standard, commonly called for, translations. These conversions can be explicitly invoked by the user or implicitly invoked when data of one type is needed for an operation but data of another type is provided. In the case of implicit invocation of conversion of data the user will have control over whether conversion takes place for a given data item. More generally we would like to provide a facility whereby the user could specify conditions which determine when an item is to be converted. Also, the user should be able to define his own conversion operations, either for a conversion between types which is not provided by the datacomputer system or to override the standard conversion operation for some or all items of a given type. 3.8 Virtual and Derived Data Often, information important to users of data is embedded in that data rather than explicitly maintained. For example, the dollar value of an individual's interest in a company in a file of stock holders. Since the value of the company changes frequently, it is not feasible to maintain this information with each record. It is useful to be able to use the file as if information of this type was part of each record. When referencing the dollar value field of a record, the datacomputer system would automatically use information in the record, such as percentage of ownership in the company, possibly in conjunction with information which is not part of the record but is maintained elsewhere, such as company assets, to compute the dollar value. In this way the data user need not be concerned with the fact that this information is not actually maintained in the record. The _set_, which is a specific type of virtual container in datalanguage, deserves special mention. A set is a virtual list. For example, suppose there is a real list of people representing some population sample. By real (or actual) data we mean data which is physically stored at the datacomputer. A set could be defined to contain all members of this list who are automobile owners. The set concept provides a powerful feature for viewing data as belonging to more than one collection without physical duplication. Sets are also useful, in that, they can be dynamically formed. Given an actual list, sets based on that list can be created without having been previously described. Winter, Hill & Greiff [Page 28]
RFC 610 Further Datalanguage Design Concepts December 1973 As mentioned above, virtual data can be very economical. These economies may become most important with respect to the use of sets. Savings are found not only in regard to storage requirements, but also in regard to processing efficiency. Processing time can be reduced as a result of calculations being performed only when the data is accessed. The ability to obtain efficient operation by optimization becomes greater when virtual data is defined in terms of other virtual data. For sets, large savings may be realized by straight forward "optimization" of the nested calculations. The above ideas are made more clear by example. Having created a set of automobile owners, A, a set of home owners, HA, can be defined based on A. The members of HA can be produced very efficiently, in one step, by retrieving people who are both automobile owners and home owners. This is more efficient than actually producing the set, A and then using it to create HA. This is true when one or both pieces of information (automobile ownership and home ownership) are indexed (see discussion under internal representation) as well as when neither is indexed. The same gains are achieved when operations on virtual data are requested. For example, if a set, H, had been defined as the set of homeowners based on the original list of people, the set, HA, could have been defined as the intersection (see discussion on operators) of A and H. In this case too, HA can be calculated in one step. Use of sets allows the user to request data manipulations in a form close to his conceptual view, leaving the problem of effective processing of his request to the datacomputer. Another use of virtual data is to accomplish data sharing. An item could be defined, virtually, as the contents of another item. If no restriction is placed on what this item can be, we have the ability to define two paths of access to the same data. Hence, data can be made subordinate to two or more aggregate structures. Stated another way, there are two or more paths of access to the data. This capability can be used to model data which is part of more than one data relationship. For example, two files could have the same records without maintaining duplicate copies. It will also be possible, via data sharing to look at data in different ways. Shared data might behave differently depending on how (and ultimately by whom) it is accessed. Although, the ability to have multiple paths to the same data and the ability to have data which is calculated on access are both part of the general virtual data capability, datalanguage will probably provide these as separate features, since they have different usage characteristics. Derived data is similar to virtual data in that it is redundant data which can be calculated from other information. Unlike virtual data it Winter, Hill & Greiff [Page 29]
RFC 610 Further Datalanguage Design Concepts December 1973 is physically maintained. The user can choose between virtual and derived data as a result of considering trade-offs based on: estimated cost of calculation; frequency of update; estimated cost of storage; and frequency of access. For example, suppose a file contains a list of budgets for various projects in a department. The departmental budget can be calculated as a function of the individual project budgets. This information might be defined as derived data since it is expected to be updated infrequently (e.g., once a year), while it is expected to be accessed relatively often. Options will be provided which give the user control with regard to when the calculation of derived data is to be done. These options will be similar to those provided for control of data validity operations. The data validation and derived data concepts are similar in that some operation must be performed on related data. In the case of data validation, the information derived is the condition of data. 3.9 Internal Representation To this point, we have discussed only the high level, logical, aspects of data. Since data, at any given time, must reside on some physical device a representation of the data must be chosen. In some cases it is appropriate to leave this choice to the datacomputer system. For example, the representation of information which is used in the process of transmitting other data, but which itself resides solely at the datacomputer may not be of any concern to the user. However, it is important that the user be capable of controlling the choice of representation. In any application which requires mostly transmission of data rather than interpretation of the data by the datacomputer, the data should be maintained in a form consistent with the system which communicates with the datacomputer. With respect to basic types of data, datalanguage will provide most representations commonly used in systems with which it interacts. For some types (e.g., fixed point) this will be accomplished by providing for parametric (e.g., sign convention, size) description of the representation. In other cases (e.g., floating point) specific representations will be offered (e.g., system 360 short floating point, system 360 long floating point, pdp-10 floating point, etc.). Another aspect of the internal representation problem regards aggregate structures. The method chosen to represent aggregate structures may largely affect the cost of manipulating the data. The user must have control over this representation since only he has any idea of how the data is to be used. Datalanguage will provide a variety of representational options which will allow for efficient implementation of data structures. This includes the availability of auxiliary Winter, Hill & Greiff [Page 30]
RFC 610 Further Datalanguage Design Concepts December 1973 structures, automatically maintained by the data computer system. These structures can be used to effect efficient retrieval of subsets of data collections based on the contents of the members (i.e. the common concept of indices), efficient maintenance of orderings on a collection of data, maintenance of redundant information for the purpose of data integrity, and efficient handling of shared data whose behavioral characteristics are dependent on the path of access. It should be noted here that, the datalanguage design effort, will attempt to provide methods whereby the data user can describe the expected use of his data, so that details of internal representation can be left to the datacomputer. 3.10 Data Attributes and Data Classes The type of an item determines the operations which are valid on that item and what they mean. _Data_attributes_ are refinements on the type of data. The data attributes affect the meaning of operations. For example, we would like to provide for the option of defining fixed point items to be scaled. The scale factor, in this case, would be an attribute of fixed point data. It effects the meaning of operations on that data. The attribute concept is useful in that it allows information concerning the manipulation of an item to be associated with the item rather than with the invocation of all operations on that item. The attribute concept can be applied to aggregate as well as basic data. For example, one attribute of a list could define where a new member is to be inserted. Options might be: insert at the beginning of the list; insert at the end of the list; or insert in some order based on the contents of the member. Adding a new member to a list with one of the above attributes could be done by issuing a simple insert request without having to specify where the new member is to be inserted. The _data_class_ concept is actually the inverse of the data attribute concept. A data class is a collection of data types. The data class concept allows for definition of operations, independent of specific type of an item. For example, by defining the data class arithmetic to be composed of fixed point and floating point types of data, the comparison operators (_equal_, _less_than_, etc.) can be defined to operate on arithmetic data, independent of whether it is fixed or floating point. Also the concept of data aggregate can be seen as a class encompassing directories, lists, etc. As there are operations defined on arithmetic data, there are also operations defined on arbitrary aggregates. The inverse relationship between data classes and data attributes is very strong. For example, the concept of list can be seen as a data class, encompassing all types of lists (e.g., lists of integers, lists Winter, Hill & Greiff [Page 31]
RFC 610 Further Datalanguage Design Concepts December 1973 of character strings, etc.), independent of the types of their members. The type of a list's members (e.g., integer, character string, etc.) are then seen as attributes. Data attributes and classes are also relative concepts. While the concept of list can be viewed as a data class, it can also be seen as an attribute, relative to the concept of data aggregate. 3.11 Data Description A _data_description_ is a statement of the properties (see discussion of attributes) of a data item. Examples of properties which are recorded in a description are: the name of an item; its size; its data type; its internal representation; privacy information; etc. Datalanguage will contain mechanisms for specifying data descriptions. These descriptions will be processed by the data computer, and used whenever the data item is referenced. The user will be able to physically create data only by first specifying their descriptions. The properties of a description can be divided into groups according to their function. Some have the function of specifying details of representation, which will not be of interest to most users, while others, such as the name are of almost universal interest. All user data is a part of some larger (user or system) data structure. The structures containing data establish a path of access to the data. In the process of following this path the datacomputer system must accrue a complete description of the data item. For example, the description of a data item of a directory may be found associated with that node of the directory. Members of a list or array are described as part of the description of the list or array. We must dispose of two seeming exceptions. First, while aspects of data may (on user request) be left to the system, those aspects are still described, they are described by the system. As discussed above, some data will be, to some degree, self describing (e.g. members of mixed lists). However, it is fully described in some encompassing structure, in that a method of determining the full description is described. It is worth noting here that the sooner a complete description is found in the path of access, the more effective the datacomputer is likely to be in processing requests which manipulate a data item. However, the ability to have data whose complete description does not exist at high levels of the access path provides greater flexibility in the definition of data structures. Winter, Hill & Greiff [Page 32]
RFC 610 Further Datalanguage Design Concepts December 1973 3.12 Data Reference Data cannot be manipulated unless it can be referenced. In the same way that data cannot exist without its being described, it cannot exist unless there is a path of access to the data. The method of data reference is to define the path of access to the data. As mentioned above, there is a method of referencing any item relative to the data aggregate which contains it. Nodes of directories and components of structs are referenced via the name associated with the node or component. Members of arrays are referenced via the index associated with the member. Members of lists are referenced via some method of specifying the position of the member or by uniquely identifying the member by content. To reference any arbitrary data item the path of access must be fully defined by either explicit or implicit definition of each link in the chain. In the case of virtual data there is an extra implicit link in the chain, that being the method employed to obtain the data from other data items. It should be noted also that if pointers are provided (see discussion on general relational capabilities) they can also serve as a link in the chain of access to an item. The design of datalanguage will ease the problem (and reduce the cost) of referencing data items by providing methods whereby part of the access path can be implicitly defined. For example, datalanguage will provide a concept of "context". During the course of interacting with the datacomputer, levels of context can be set up so that data can be referenced directly, in context. For example, on initiating a session the user may (in fact will probably be required to) define a directory which will be the context of that session. All items subordinate to this directory can be referenced directly in this context. Another feature will be partial qualification. Each level of struct need not be mentioned in order to reference an item embedded in a deep nest of structs. Only those intermediate levels which are sufficient to uniquely identify the item need be specified. 3.13 Operations In this section we discuss the builtin functions of datalanguage which are of central importance in manipulating data. Functions which operate on items, functions which operate on aggregates, primitive functions and high-level functions are discussed. Of the primitives which operate on items, those of most interest are assignment, comparisons, logicals, arithmetics and conversion functions. Primitive assignment transfers a value from one item to another; these items must be of the same type. When they are of different types, Winter, Hill & Greiff [Page 33]
RFC 610 Further Datalanguage Design Concepts December 1973 either conversion must be performed, or some non-primitive form of assignment is involved. The comparison operators accept a pair of items of the same type, and return a boolean object which indicates whether or not a given condition obtains. The type determines how many different conditions can be compared for. A pair of numeric items can be compared to see which is greater, while a pair of uninterpreted items can be compared only for equality. In general, a concept of "greater than" is builtin for a datatype only if it is a very widely applied concept. The comparison operators are used in the construction of inclusion conditions when defining subsets of aggregate data. The result of a comparison operation is a boolean item: one whose value is either TRUE or FALSE. Logical primitives are provided and generalized boolean functions can be constructed from them. With logical and comparison operators, complex conditions for inclusion of objects in sets can be specified. Arithmetic operators will be available for the manipulation of numeric data. Here, we are not interested in generalized computation, but in applications of arithmetic in data selection, space allocation, subscript calculation, iteration control, etc. Conversion is an important part of generalized data translation, and we are interested in providing a substantial builtin conversion facility. In particular, we will want to provide an efficient system routine for each "standard" or widely-used conversion function. Of particular importance are conversions to and from character string data; in character string representation of, for example, numeric items, there are many possible formats corresponding to a single data type. Conversion between character sets and dealing with padding and truncation are viewed as conversion problems. There are two principal classes of primitive operators defined on aggregates: those related to data reference (see previous section) and those which add and delete components. Changing an existing component is accomplished through assignment, and is an operation on the component, not the aggregate. Addition and deletion of components is defined only for aggregates which are not inherently static in composition. Thus one can add a component to a LIST, but not to an ARRAY. To specify deletion it is necessary to specify which component is to be deleted, and from which aggregate (in the case that it is shared). Addition requires specification of new component, aggregate, and sometimes auxiliary information. For example, some aggregate types would permit addition of new components anywhere in the structure; in these a position must be indicated, relative to any Winter, Hill & Greiff [Page 34]
RFC 610 Further Datalanguage Design Concepts December 1973 existing components. Often it is desirable to operate on some of the members of a list, or to treat a group of members as a list in its own right. For example, it might be common to transmit to a remote program for analysis, the medical history of patients developing heart disease before the age of 30. These may be just a few of the members of a large list of patients. In this case, the operation to be performed is transmission to the remote system; this operation is performed on several members of the list of patients. The ones to be transmitted are thought of as a _set_; the set is specified as containing all the members of a given list satisfying two conditions: (1) age less than 30, and (2) has heart disease. Sets can be defined explicitly, or implicitly simply with appropriate reference mechanisms. _Definition_ of a set is distinct from _identification_of_membership_, which is distinct from _access_to_membership_. Definition involves specifying the candidates for set membership and specifying a rule by which members of the set can be distinguished from non-members; for example, an inclusion condition such as "under 30 with heart disease". Identification involves effective application of the rule to all candidates for membership. When the membership has been identified, it can be counted, but the data itself has not necessarily been accessed. When a member is accessed, its contents can be operated on. Primitives to accomplish each of these operations on a set will be provided; however, it will ordinarily be optimal for the datacomputer to determine when each step should be performed. To enable users to operate at a level at which the datacomputer can optimize effectively, higher-level operators on sets will be provided. Some of these are logical operators, such as union and intersection. These input and output sets. Also available is an operator which complements a set (since the definition establishes all possible candidates, a set always has a well-defined complement). These higher level operators can be applied to any defined set; the set members need not be identified or accessed. The system will perform such operations without actually accessing members if it can. Some of the other operators on sets are counting membership, partitioning a set into a set of sets, uniting a set of sets into a set. A set can be used to reference another set, providing there is a well- defined way to identify members of the second set given the first set. For example, a set C may contain all the children doing poorly in school. A set F may be defined, where the members of F are the records about families having a child in set C. Winter, Hill & Greiff [Page 35]
RFC 610 Further Datalanguage Design Concepts December 1973 Some other useful operations on sets are: adding all the members of a set to an aggregate, deleting all the members of a set (frequently such a massive change can be performed far more efficiently than the same set of changes individually requested), changing all the members of a set in a given way. A set can be made into a list, by actually accessing each member and physically collecting them. Some of the operations on lists are: concatenation of lists into larger lists, division of a list into smaller lists, sorting a list, merging a pair of ordered lists (preserving order). This is not intended to be a full enumeration of high-level operations, but to be suggestive. We are planning to build in high-level functions for operations which are used very commonly, and can be implemented within the system significantly better than they can be implemented by users in the language. For most of the functions mentioned here, considerable knowledge is accumulated on good implementations. In particular, the techniques used for inverted file access provide many set operations to be performed without actual access to the data. 3.14 Control The control features of datalanguage are to the basic operations as data aggregates are to the basic data items. Control features are used to create complex requests out of the basic requests provided by datalanguage. Conditional requests allow the user to alter the normal request flow by specifying that certain requests are to be executed under certain conditions. In general datalanguage will provide the ability to chose at most one of a number of requests to be made based on some set of conditions or the value of some item. In its simplest form the conditional allows for optional execution of a given request. Iterative requests cause a request (called the body) to be executed a fixed or variable number of times or until a given condition is met. Datalanguage will provide iterative requests that will allow for similar manipulations to be performed on all members of some aggregate structure as well as the standard type of iterative request based on counters. By providing a capability of directly expressing manipulations on aggregates which require processing all of the items subordinate to the aggregate, the datacomputer can be more efficient in processing user requests. For example, a user defined conversion process which operates on character strings, can be implemented far more efficiently if the datacomputer is explicitly informed that the process requires sequential Winter, Hill & Greiff [Page 36]
RFC 610 Further Datalanguage Design Concepts December 1973 processing of the characters. Datalanguage will also provide for parallel iteration. For example, the user will be able to specify operations which require sequencing through two or more lists in parallel. This would be done if the contents of one file were to be updated based on a file of correction information. Compound requests are collections of requests which act as one. They are primarily provided to allow for the conditional performance of or iteration on more than one statement. Compound requests also provide request reference points which can be used to control the request processing flow. That is, compound requests can be "named". The datalanguage user will be able to specify control information which will conditionally cause a compound request to be exited. By providing naming, the user may cause any number of previously entered compound requests to be exited. We do not intend to provide the traditional _goto_ capability. By not including a goto request, the chances for efficient operation (via optimization) of the datacomputer are increased. We also hope, in this way, to force the datalanguage user to specify his data manipulations in a clear sty1e. Two forms of the compound request will be provided, ordered and unordered. In the unordered case the user is informing the datacomputer that the requests can be performed in any order. This should allow the datacomputer to perform more efficiently and might even allow for parallel processing. During a session with the datacomputer it is likely that a user will find a need for temporary data. That is, data which is used to remember, for a short term, information which is needed for the processing of requests. This short term might be a session or a small part of a session. Datalanguage will provide a temporary data facility. Temporary data will be easy to create, use and dispose of. This will be accomplished by allowing the system to (optionally) make many decisions regarding the data. For example the representation of a temporary integer item will often be of no concern to the user. Some features which are provided for permanent data will be deemed irrelevant with regard to temporary data. Temporary data will be associated with a collection of requests in what will be called a block. A block will be no different than a compound request with the exception that data is defined with the requests which compose it and is automatically created on entrance to the block and destroyed on exiting the block. Winter, Hill & Greiff [Page 37]
RFC 610 Further Datalanguage Design Concepts December 1973 3.15 Extensibility The goals of datalanguage are to provide facilities of data structure at two levels. At one level the user may take advantage of high level data capabilities which will do much of his data management work automatically and which allows for the data computer to operate more effectively in some cases since it has been given control of the data. At another level, however, features are provided which allow the user to describe his application in terms of primitive concepts. In this way the datacomputer user may compose a large variety of data constructs and has great flexibility with respect to the manipulations he can perform on his data. Also by interacting with the datacomputer at the primitive level, the user can exercise a good deal of control over the methods employed by the datacomputer which may result in more effective usage of resources for non-standard applications. Datalanguage will provide features which allow the user to create an environment whereby the datacomputer system appears to provide features especially tailored to his application. The control features discussed above allow the user to extend the operations available on data by appropriate composition of the operations. Datalanguage will provide a method of defining a composite request to be a new request (called a _function_). In this way a new operation on specific data can be defined once and then used repeatedly. In order that the user may define general operations, datalanguage will provide functions which can be parameterized. That is, functions will not only be able to operate on specific data but may be defined to work on any data of a specific type. This capability will not be limited to basic data types (e.g. integers) or even specific aggregate types (e.g. array of integers) but will also include the ability to define functions which operate on classes of data. For example, functions can be defined which operate on lists independent of the type of the list members. Also provided, will be the ability to expand and modify existing functions as well as creating new functions. This includes expanding the types of data for which a function is defined or modifying the behavior of a function for certain types of data. As with operations, the data aggregates discussed above allow the user to extend the primitive data types by appropriate composition. For example, a two dimensional array of integers can be created by creating an array of arrays of integers. The situation for data types is analogous to that of operations. Datalanguage will provide the ability to define a composition of data to be a new data type. Also the capability of defining general data structures will be provided by essentially parameterizing the new data definition. This would allow the general concept of two dimensional array to be defined as an array of arrays. Once defined, one could create two dimensional arrays of integers, two dimensional arrays of booleans, etc. As with functions Winter, Hill & Greiff [Page 38]
RFC 610 Further Datalanguage Design Concepts December 1973 there is also a need to expand or modify existing data types. One might want to expand the attributes which apply to a given data type, in that he might want to add new attributes, or add new choices for the existing attributes. The control features can be extended also. Special control features might be needed to process a data structure in a special way or to process a user defined data structure. For example, if a tree type data structure has been defined in terms of lists of lists, the user might like to define a control function which causes a specified operation to be performed on each item of a specified tree. As with data types and functions, there is a need to be able to modify and extend existing control features as well as the ability to create new ones. Datalanguage will provide the ability to treat data descriptions and operations in much the same way that data is treated. One can describe and manipulate descriptions and operations in the same way that he can describe and manipulate data. It is impossible to talk about data types without consideration of operations and equally as impossible to talk about operations without an understanding of the data types they operate on. In order for the user to be able to effect the behavior of the datacomputer system, the design of datalanguage will include a definition of the operational cycle of the datacomputer. Precise definitions of all aspects of data (data attributes, data classes, relationship of aggregates to their subordinate items, etc.) in terms of their interaction with datalanguage operations will be made. In this way the datacomputer can offer tools which will give the datacomputer user the ability to be an active participant in the design of the datalanguage which he uses. Winter, Hill & Greiff [Page 39]
RFC 610 Further Datalanguage Design Concepts December 1973 4. A Model for Datalanguage Semantics For the purpose of defining and experimenting with language semantics and with language processing techniques, we are developing a model datacomputer. The principal elements of the model are the following: (1) A set of primitive functions (2) An environment in which data objects can be created, manipulated and deleted, using the primitives (3) A structure for the representation of collections of data values, their descriptions, their relationships, and their names. (4) An interpreter which executes the primitives (5) A compiler which inputs requests in a very simple language, performs binding and macro expansion operations, and generates calls to the internal semantic primitives. If our modeling efforts are successful, the model will evolve until it accepts a language like the datalanguage whose properties we have described in sections 2 and 3 of this paper. Then the process of writing the final specification will simply require reconciliation of details not modeled with structure that has been modeled. One rather large detail which we may never handle within the model is syntax; in this case reconciliation will be more involved; however, we firmly believe that the semantic structure should determine the syntax rather than the opposite, so we will be in the proper position to handle the problem. By constructing a model for each of the elements listed above, we are "implementing" the language as we design it, in a very loose sense. In effect, we work in a laboratory, rather than working strictly on paper. Since we aren't concerned with the performance or usability of the datacomputer we are building in the laboratory, we are able to build without becoming involved with some of the most time-consuming concerns of an implementor. However, because we are building and tinkering, rather than simply working on paper, we do get some of the advantages that normally come with the experience of implementing one's ideas. The model datacomputer is a program, developed in ECL, using the EL1 language. Presently we are interested in the process of developing the program, not running it. Our primary requirement is to have, in advance of the existence of datalanguage, a well-defined and flexible notation in which to specify data structures, function definitions and examples. EL1 is convenient for this. Having a program which actually works and acts like a simple datacomputer is really a by-product of specifying semantics in a programming language. It is not necessary for the program to work, but it does provide some nice features. It enhances the "laboratory" effect, by doing such things as automatically compiling Winter, Hill & Greiff [Page 40]
RFC 610 Further Datalanguage Design Concepts December 1973 strings of primitives, displaying the state of the environment in complicated examples, automatically discovering inconsistencies (in the form of bugs), and so on. There are two major reasons that EL1 is a convenient notation for specifying datalanguage semantics. One is that the languages have a certain amount in common, in both concepts and in goals in data description. (In part, this is because EL1 itself has been a good source of ideas in attacking the datalanguage problem). Both languages emphasize operations on data, independent of underlying representation. A second reason that EL1 is a convenient way to specify datalanguage, is that EL1 is extensible; in fact, many primitive functions could be embedded directly into EL1 by using the extension facilities. At times, we have chosen to embed less than we could, to expose problems of interest to us. So far, the model has been useful primarily in exposing design issues and relationships between design decisions. Also, because it includes so many of the elements of the full system (compiler, interpreter, environment, etc.), it encourages a fairly complete analysis of any proposal. In presenting the model in this section, we have chosen to emphasize ideas and examples, rather than formal definitions in EL1. This is because the ideas are more permanent and relevant at this point (the formalisms are changing rather frequently) and because we imagine people reading the formal definitions only to get at the ideas. The formal definitions may be interesting in themselves when the language is complete; at this point they are probably of interest only to us. The section is organized into a large number of sub-sections. The first few are concerned with the basic concepts of data objects, descriptions, and relationships between objects. We then discuss primitive semantic functions and present informal definitions and examples in sections 4.7 and 4.8. Section 4.9 is a brief discussion of compilation, interpretation and the execution cycle. Section 4.10 provides a fairly elaborate example of how primitive functions can be combined to do something of interest: a selective retrieval by content. The last two sections wrap up with discussions of high-level functions and some conclusions. 4.1 Objects An _object_ has a name, a description, and a value. It can be related to other objects. The _name_ is a symbol, which can be used to access the object from Winter, Hill & Greiff [Page 41]
RFC 610 Further Datalanguage Design Concepts December 1973 language functions. The _description_ is a specification of properties of the object, many of which relate to the meaning or the representation of the value. The _value_ is the information of ultimate interest in the object. The relationships between objects are hierarchical. Each object can be related directly to at most four other objects, designated as its _parent_, its _child_, its _left_sibling_, and its _right_sibling_. This specific concept of relationship is all that has been built in to the model to date. One of our primary objectives in the future is to experiment with more general relationships among objects. 4.2 Descriptions A description has the components _name_, _type_ and _type- dependent_parameters_. It can be related hierarchically to other descriptions, according to a scheme similar to the one described for objects in 4.1. The _name_ has a role in referencing, as in the case of objects. _Type_ is an undefined, intuitive idea for which we expect to develop a precise meaning within datalanguage(see section 3.10 for some of the ideas about this). In terms of the present model, it simply means one of the following: LIST, STRUCT, STRING, BOOL, DESC, DIR, FUNC, 0PD. Each of these refers to a sort of value corresponding to common ideas in programming (with the exception of OPD, which is explained in section 4.7), and on which certain operations are defined. Examples of _type-dependent_parameters are the two items needed to define a STRING: size option and size. A STRING is a sequence of characters; the size of the STRING is the number of characters in it. If a STRING has a fixed size, then size option is FIXED and size is the number of characters it always contains. If a STRING has a varying size, then size option is VARYING, and size is its maximum (clearly, it might also have a minimum in a more refined scheme). When the description of an object has a type of STRING, it is commonly said that the object is a STRING. 4.3 Values The value is the data itself. Winter, Hill & Greiff [Page 42]
RFC 610 Further Datalanguage Design Concepts December 1973 An object of type BOOL can have only either the value TRUE or the value FALSE. An object of type STRING has values such as 'ABC', 'JOHN', or 'BOSTON'. Each value has a representation, in bits. Thus a BOOL is represented by a single bit, which will be a 'one' to represent TRUE and a 'zero' to represent FALSE. 4.4 Some examples Here are some examples of structures involving objects, descriptions, and values. In these explanations and drawings, the objective is to convey some ideas about these primitive structures; considerable detail is omitted in the drawings in the interest of clarity. Figure 4-1 shows two objects. X is of type string and has value 'ABC'. Y is of type bool and has value TRUE. Winter, Hill & Greiff [Page 43]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | | | _____________ | | | X | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | STRING | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | VALUE | | ____________ |___________|_____| | | OBJECT |____________\| "ABC" | /|____________| VALUE _________________ | | | _____________ | | | Y | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | BOOL | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | VALUE | | ____________ |___________|_____| | | OBJECT |____________\| TRUE | /|____________| VALUE Figure 4-1 Two elementary objects Figure 4-2 illustrates an object of type dir (a _directory_) and related objects. The directory has name SMITH. There are two objects entered in this directory, named X and Y. Winter, Hill & Greiff [Page 44]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | _____________ | | | SMITH | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | DIR | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | CHILD | | |___________|_____| OBJECT | ___________V_____ | _____________ | | | X | | | |_____________| | | NAME | _________________ | _____________ | | _____________ | _____|_|____ | | | | Y | | | | |_____________| | | |_____________| | | | DESCRIPTION | | NAME | | | _____________ | | _____________ | | __|_|____ | | | | ____|_|_____ | | | |_____________| | | |_____________| | | | | | VALUE | | DESCRIPTION | | | | | _____________ | | _____________ | | | | | | ____|_|_____\| | ____|_|__ | | | | |_____________| | /| |_____________| | | | | | | SIBLING | | VALUE | | | | | |_________________| |_________________| | | | | OBJECT OBJECT | | | | _________________ _________________ | | | |_\| "ABC" | | FALSE |/_| | | /|_________________| |_________________|\ | | VALUE VALUE | | _________________ _________________ | | | _____________ | | _____________ | | | | | STRING | | | | BOOL | | | |____\| |_____________| | | |_____________| |/____| /| TYPE | | TYPE |\ |_________________| |_________________| DESCRIPTION DESCRIPTION Figure 4-2: A directory with two members Winter, Hill & Greiff [Page 45]
RFC 610 Further Datalanguage Design Concepts December 1973 The idea of a dir is similar to the idea of a file directory in most systems. A directory is a place where one can store named objects, freely adding and deleting them. The entries in the directory are all objects whose parent is that directory. Figure 4-3 shows a more rigidly structured group of objects. Here we have R, a struct, and A and B, a pair of strings. Note that the boxes labeled 'object' in figure 4-3 bear precisely the same relationships to one another as those labeled 'object' in 4-2. However, there are two conditions which hold for 4-3 but do not hold for 4-2: (1) the value of R contains the values of A and B, and (2) the descriptions of R, A and B are all related. Structs have the following properties: (1) name and description of each component in the struct is established when the struct is created, and (2) in a value of the struct, the order of occurrence of component values is fixed. Winter, Hill & Greiff [Page 46]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | R | | | | STRUCT | | | |_____________| | | |_____________| | | NAME | | TYPE | | _____________ | | _____________ | | | ____|_|______\| | | | | |_____________| | /| |__________|__| | | DESCRIPTION | | CHILD | | | _____________ | |____________|____| _____|_|____ | | DESCRIPTION | | | |_____________| | ____________V____ | | VALUE | | _____________ | | | _____________ | | | STRING | | | | | | | | |_____________| | | | |_________|___| | ___\| TYPE | _____________ | | CHILD | | | /| _____________ | | _________ | | |___________|_____| | | | ____|_|______\| | STRING | | | OBJECT | | | |_____________| | /| |_________| | | | | | SIBLING | | TYPE | | ___________V_____ | |_________________| |_____________| | | _____________ | | DESCRIPTION DESCRIPTION A | | | A | | | | | | |_____________| | | _________________ | | | NAME | | | _____________ | | | | _____________ | | | | B | | | | | | ____|_|__| | |_____________| | | | | |_____________| | | NAME | | | | DESCRIPTION | | _____________ | | | | _____________ | | | ____|_|___________________| | __|_|____ | | | |_____________| | | | | |_____________| | | DESCRIPTION | | | | VALUE | | _____________ | | | | _____________ | | | ____|_|____ | | | | ____|_|______\| |_____________| | | | | | |_____________| | /| VALUE | | | | | SIBLING | | _____________ | | | | |_________________| | | | | | | | OBJECT | |_____________| | | | | | SIBLING | | | | |_________________| | | |__________ OBJECT _____________| | _______|__________________________|_______ |____\| _____V_______ _______V_____ | /| | "ABC" | | FALSE | | Figure 4-3 | |_____________| |_____________| | A STRUCT with |__________________________________________| two members Winter, Hill & Greiff [Page 47]
RFC 610 Further Datalanguage Design Concepts December 1973 Figure 4-4 shows a list named L. Here a similar structure of objects is implied, but because of the regularity of the structure, not all the boxes labeled 'object' are actually present. _________________ | _____________ | | | L | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | LIST | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | | ________ | | | | | | | | | | |_______|_____| | | |______|_| | | VALUE | | | CHILD | | |_________|_______| |________|___| OBJECT | DESCRIPTION | | | _________V_______ ________V___ | | | ________ | | _____________ | | | STRING | | | | "ABC" | | | |________| | | |_____________| | | TYPE | | _____________ | |____________| | | "XY" | | DESCRIPTION | |_____________| | | _____________ | | | "ZLM" | | | |_____________| | | : | | : | | _____________ | | | "BBBF" | | | |_____________| | |_________________| VALUE Figure 4-4 A LIST L has a variable number of components, all satisfying the description subordinate to L's description. Winter, Hill & Greiff [Page 48]
RFC 610 Further Datalanguage Design Concepts December 1973 We could imagine an 'object' box for each string in L. Each of these boxes would point to its respective string and to the common description of these strings. Instead, we think in terms of creating such boxes as we need them. 4.5 Definitions of types Following are some more precise definitions of types, in terms of the present model. These serve the purpose of establishing more firmly the semantics of our structure of objects, descriptions and values; however, they should not be thought of as providing a definition for the completed language specification. An object of type STRING has a value which is a sequence of characters (figure 4-1). An object of type BOOL has a value which is a truth value (TRUE or FALSE -- figure 4-1). An object of type DIR has subordinate objects, each having its own description and value. Subordinate objects can be added and deleted at will (figure 4-2). An object of type STRUCT has subordinate objects, each of which has a description which is subordinate to the STRUCT's description, and a value contained in the STRUCT's value. The number, order and description of components is fixed when the STRUCT is created (figure 4-3). An object of type LIST may be thought of as having imaginary subordinate objects, whose existence is simulated by the use of appropriate techniques in processing the LIST. Each of these has the same description, which is subordinate to the description of the LIST. Each has a distinct value, contained in the value of the LIST. In fact, only the LIST object, the LIST and component descriptions, and the values exist (figure 4-4). An object of type DESC has a description as its value. This value is the same sort of entity which serves as the description of other objects. An object of type FUNC has a function call as its value. We will be able to say more about this after functions have been discussed. An object of type OPD has an operation descriptor as its value. (see 4.7 for details). Winter, Hill & Greiff [Page 49]
RFC 610 Further Datalanguage Design Concepts December 1973 4.6 Object environment There are three categories of objects in the model datacomputer. These are p/objects, t/objects, and i/objects. P/objects are permanent objects created explicitly with language functions. They correspond to the idea of stored data in the real datacomputer. There are three special objects. These are special only in that they are created as part of initializing the environment, rather than as the result of executing a language function. These are named STAR, BLOCK and TOP/LEVEL. All three are of type DIR. An object is a p/object if it is subordinate to STAR; it is a t/object if it is subordinate to BLOCK. TOP/LEVEL is subordinate to BLOCK. (see figures 4-5 and 4-6). _________________ | | | _____________ | | | STAR | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | DIR | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | CHILD | | |___________|_____| OBJECT | | | | V ALL P/OBJECTS Figure 4-5 STAR and p/objects T/objects are temporary objects, also created explicitly with language functions. However, these correspond to user-defined temporaries, both local to requests and "top-level" (i.e. not local to any request, but existing until deletion or logout.) Winter, Hill & Greiff [Page 50]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | | | _____________ | | | BLOCK | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | DIR | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | VALUE | | |___________|_____| OBJECT | | | ___________V_____ | | | _____________ | | | TOP/LEVEL | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | DIR | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | ____|_|___ DESCRIPTION | |_____________| | | | SIBLING | | | _____________ | |___\ ALL BLOCKS AND | | | | / LOCAL T/OBJECTS | |_________|___| | | CHILD | | |___________|_____| | | V ALL GLOBAL T/OBJECTS Figure 4-6 BLOCK, TOP/LEVEL and t/objects Winter, Hill & Greiff [Page 51]
RFC 610 Further Datalanguage Design Concepts December 1973 I/objects are internal, system-defined objects whose creation and deletion is implicit in the execution of some language function. I/objects are hung directly off of function calls (objects of type FUNC), and are always local to the execution of such function calls. They correspond to the notions of (1) literal, and (2) compiler- or interpreter-generated temporary. 4.7 Primitive Language Functions Here we discuss the primitive language functions presently implemented in the model and likely to be of most interest. In this section, the emphasis is on relating functions to one another. Section 4.8 contains more detail and examples. _Assign_ operates on a pair of objects, called the target and the source. The value of the source is copied into the value of the target. Figure 4-7 shows a pair of objects, X and Y, before and after execution of an assignment having X as target and Y as source. Presently, assignment is defined only for objects of type BOOL and objects of type STRING. The objects involved must have identical descriptions. Winter, Hill & Greiff [Page 52]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | | | | | _____________ | | _____________ | | | | | | | | | | | X | | | | Y | | | |_____________| | | |_____________| | | NAME | | NAME | | _____________ | | _____________ | | | | | | | | | | |_______|_____| | | |_______|_____| | | VALUE | | | VALUE | | |_________|_______| |_________|_______| OBJECT | OBJECT | | | _________V_______ _________V_______ | | | | | "ABC" | | "DEF" | |_________________| |_________________| VALUE VALUE BEFORE ASSIGNMENT _________________ _________________ | | | | | _____________ | | _____________ | | | | | | | | | | | X | | | | Y | | | |_____________| | | |_____________| | | NAME | | NAME | | _____________ | | _____________ | | | | | | | | | | |_______|_____| | | |_______|_____| | | VALUE | | | VALUE | | |_________|_______| |_________|_______| OBJECT | OBJECT | | | _________V_______ _________V_____ | | | | | "DEF" | | "DEF" | |_________________| |_________________| VALUE VALUE AFTER ASSIGNMENT Figure 4-7 Effect of assignment Winter, Hill & Greiff [Page 53]
RFC 610 Further Datalanguage Design Concepts December 1973 A class of primitive functions for manipulating LISTs is defined. These are called _listops_. All listops input a special object called an _operation_descriptor_ or OPD. To accomplish a complete operation on a LIST, a sequence of listops must be executed. There are semantic restrictions on the composition of such sequences, and it is best to think of the entire sequence as one large operation. The state of such an operation is maintained in the OPD. Refer back to figure 4-4. There is one box labeled "object" in this picture; this box represents the list as a whole. To operate on any given member we need an object box to represent that member. Figure 4-8 shows the structure with an additional object box; the new box represents one member at any given moment. Its value is one of the components of the LIST value; its description is subordinate to the LIST description. In 4-8, the name of this object is M. In 4-8 we have enough structure to provide a description and value for M, and this is sufficient to permit the execution of operations on M as an item. However, there is no direct link between object M and object L. The structure is completed by the addition of an OPD, shown in figure 4-9. Winter, Hill & Greiff [Page 54]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | | | _____________ | | _____________ | | | | | | | L | | | |_____________| | | |_____________| | | TYPE | | NAME | | _____________ | | _____________ | | | | | | | ____|_|______\| |__________|__| | | |_____________| | /| CHILD | | | DESCRIPTION | |____________|____| | _____________ | DESCRIPTION | | | | | | | |_________|___| | ____________V____ | VALUE | | | _____________ | |___________|_____| | | STRING | |/___ OBJECT | | |_____________| |\ | | | TYPE | | ___________V_____ |_________________| | | | DESCRIPTION | | _____________ | | | | "ABC" | | _________________ | | |_____________| | | | | | _____________ | | _____________ | | | | "XY" | | | | M | | | | |_____________| | | |_____________| | | | _____________ | | NAME | | | | "ZLM" |/|___ | _____________ | | | |_____________|\| | | | ____|_|____| | : | | | |_____________| | | : | | | DESCRIPTION | | _____________ | | | _____________ | | | "BBBF" | | |___|_|____ | | | |_____________| | | |_____________| | |_________________| | VALUE | VALUE |_________________| OBJECT Figure 4-8 LIST and member objects Winter, Hill & Greiff [Page 55]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | L | | | | | | | |_____________| | | |_____________| | | NAME | | TYPE | | _____________ | | _____________ | | | ____|_|______\| | | | | |_____________| | /| |__________|__| | | DESCRIPTION | | CHILD | | | _____________ | |____________|____| | | | |/__ DESCRIPTION | | |_________|___| |\ | ____________V____ | VALUE | | | | _____________ | |___________|_____| | | | STRING | |/___ OBJECT | | | |_____________| |\ | | | | TYPE | | ___________V_____ | |_________________| | | _____________ | | DESCRIPTION | | | "ABC" | | | _________________ | | |_____________| | | | | | | _____________ | | | _____________ | | | | "XY" | | |___|_|____ | | | | |_____________| | | |_____________| | | | _____________ | | LIST | | | | "ZLM" | | | _____________ | | | |_____________| | | | | | | | : | | |_________|___| | | | : | | MEMBER | | | | _____________ | | : | | | | | "BBBF" |/|___ | : | | | | |_____________|\| | |___________|_____| | |_________________| | OPD | | VALUE | ___________V_____ | | | _____________ | | | | | M | | | | | |_____________| | | | | NAME | | | | _____________ | | | | | ____|_|____| | | |_____________| | | | DESCRIPTION | | | _____________ | |___|_|____ | | | |_____________| | Figure 4-9 | VALUE | OPD, LIST and member |_________________| OBJECT Winter, Hill & Greiff [Page 56]
RFC 610 Further Datalanguage Design Concepts December 1973 The OPD establishes the object relationship, and contains information about the sequence of primitive listops in progress. When sufficient information is maintained in the OPD, we have in 4-9 a structure which is adequate for the maintenance of the integrity of the LIST and of the global list operation. In addition to LIST and member pointers, the OPD contains information indicating: (1) which suboperations are enabled for the sequence, (2) the current suboperation, (3) the instance number of the current LIST member, (4) an end-of-list indicator. The suboperations are add/member, delete/member, change/member and get/member. All apply to the current member. Only suboperations which have been enabled at the beginning of a sequence may be executed during that sequence; eventually, the advance knowledge of intentions that is implied by this will provide important information for concurrency control and optimization. Presently, an OPD relates a single member object to a single LIST object. This imposes an important restriction on the class of operation sequences which can be expressed. Any LIST transformation requiring simultaneous access to more than one member must be represented as more than one sequence. (And we do not yet solve the problems implied in concurrent execution of such sequences, even when both are controlled by one process.) Any transformation of a LIST can still be achieved by storing intermediate results in temporary objects; however, it is certainly more desirable to incorporate the idea of multiple current members into the semantics of the language, than it is to use such temporaries. An important future extension of the listops will deal with this problem. There are six listops: listop/begin, listop/end, which/member, end/of/list, open/member and close/member. Listop/begin and listop/end perform the obvious functions of beginning and terminating a sequence of listops. Listop/begin inputs LIST and member objects, an OPD, and a specification of suboperations to enable. It initializes the OPD, including establishment of the links to LIST and MEMBER objects. After the OPD-LIST-member relationship has been established, it is only necessary to supply the OPD and auxiliary parameters as input to a listop in the sequence. From the OPD everything else can be derived. Listop/end clears the OPD and frees any resources acquired by listop/begin. Which/member establishes the current member for any suboperations. This is either the first LIST member, the last LIST member, or the next LIST member. This listop merely identifies which member is to be operated on; it does not make the contents of the member accessible. Winter, Hill & Greiff [Page 57]
RFC 610 Further Datalanguage Design Concepts December 1973 Open/member and close/member bracket a suboperation. The suboperation is indicated as an argument to open/member. Open/member always establishes a pointer from the member object to the member value; close/member always clears this pointer. In addition, each of these listops may take some action, depending on the suboperation. The details of the action would be dependent on the representation of the LIST in storage, the size of a LIST member, and choices made in implementation. Between execution of the open/member and the close/member, the data is accessible. It can always be read; in the case of the add/member and change/member suboperations, it can also be written into. End/of/list tests a flag in the OPD and returns an object of type BOOL. The value of the object is the same as the value of the flag; it is TRUE if a get/member, change/member or delete/member would be unsuccessful due to a which/member having moved "beyond the end". T his listop is provided so that it is possible to write procedures which terminate conditionally when all members have been processed. Get/struct/member provides the ability to handle STRUCTs. Given a STRUCT object which points to the STRUCT value, it will establish a pointer from a given member object to the member value. (The pointer it establishes is represented by a dashed line in figure 4-10). Winter, Hill & Greiff [Page 58]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | F | | | | STRUCT | | | |_____________| | | |_____________| | | NAME | | TYPE | | _____________ | | _____________ | | | ____|_|______\| | | | | |_____________| | /| |__________|__| | | DESCRIPTION | | CHILD | | | _____________ | |____________|____| | | | | DESCRIPTION | | |___________|_| | ____________V____ _________________ | VALUE | | | _____________ | | _____________ | | ___________|_ | | | STRING | | | | STRING | | | | | | | | |_____________| | | |_____________| | | |_________|_|_| | | TYPE | | TYPE | | CHILD | | | | _____________ | | _____________ | |___________|_|___| ____\| | | | | | | | OBJECT | | | /| |_____________| | | |_____________| | | | | | SIBLING | | SIBLING | | | | |_________________| |_________________| | | | DESCRIPTION DESCRIPTION A | | | ______________________________________ | | | | | ____________ ____________ | | | | | | | "ABC" | | FALSE | | | | |_____|_____| |____________| |____________| | | | | |________A_____________________________| | | | ............: VALUE | ___________V_____ | : _________________ | | _____________ | | : | _____________ | | | | A | | | : | | B | | | | |_____________| | | : | |_____________| | | | NAME | | : | NAME | | | _____________ | | : | _____________ | | | | ____|_|_| : | | ____|_|_______________________| | |_____________| | : | |_____________| | | DESCRIPTION | : | DESCRIPTION | | _____________ | : | _____________ | | | ....|.|....: | | | | | |_____________| | | |_____________| | | VALUE | | VALUE | | _____________ | | _____________ | | | ____|_|______\| | | | | |_____________| | /| |_____________| | | SIBLING | | SIBLING | |_________________| |_________________| Figure 4-10 OBJECT OBJECT Effect of GET/STRUCT/MEMBER Winter, Hill & Greiff [Page 59]
RFC 610 Further Datalanguage Design Concepts December 1973 The primitives discussed so far (assign, listops, and get/struct/member) provide a basic facility for operating on structures of LISTs, STRUCTs and elementary items. Using only them, it is possible to transfer the contents of one hierarchical structure to another, to append structures, to delete portions of structures, and so on. To perform more interesting operations facilities for control and selection are needed. A rudimentary control facility is provided through the primitives if/then, if/then/else, till and while. All of these evaluate one primitive function call, which must return a BOOL. Based on the value of this BOOL some action is taken. Let A and B be function calls. If/then(A,B) will execute B if A returns TRUE. If/then/else(A,B,C) will execute B if A returns TRUE; it will execute C if A returns FALSE. The while and till operators iterate, executing first A then B. While terminates the loop when A returns FALSE; till terminates the loop when A returns TRUE. If this happens the first time, B is never executed. So far, we have mentioned one function which returns a BOOL: the listop, end/of/list. Two other classes of functions which have this property are the booleans and the comparisons. There are 3 primitive booleans (and, or, not) and six primitive comparisons (equal, less/than, greater/than, not/equal, less/than/or/equal, greater/than/or/equal -- only equal is implemented at time of publication). The booleans input and output BOOLs; the comparisons input pairs of elementary objects having the same description and output BOOLs. Expressions composed of booleans and comparisons on item contents are one of the principal tools used in selectively referencing data in data management systems. With the booleans, the comparisons, and the primitives identified earlier, we can perform selective "retrievals". That is, we can transfer to LIST B all items in LIST A having a value of 'ABC'. In fact, we now have a (semantically) general ability to perform content- based retrievals and updates on arbitrary hierarchical structures. We can even program something as complex as the processing of a list of transactions against a master list, which is one of the typical applications in business data processing. Of course, we would not expect users of datalanguage to express requests at the level of listops. Further, the listops defined here are not a very efficient way of performing some of the tasks we have mentioned. To get good solutions, we need both higher-level operators and other primitives which use other techniques in processing. In addition to those already discussed, the model contains functions Winter, Hill & Greiff [Page 60]
RFC 610 Further Datalanguage Design Concepts December 1973 for: (1) referencing an object by qualified name, (2) generating a constant, (3) generating data descriptions, (4) writing compound functions and blocks with local variables, (5) creating objects. The facilities for generating constants and data descriptions (which are a special case of constants) are marginal, and have no features of special interest. Obviously, data description will be an important concern in the modeling effort later on. Object referencing functions permit reference to t/objects and p/objects (these terms are defined in 4.6). A p/object is referenced by giving the pathname from STAR to it. A t/object is referenced by giving the pathname from the block directory in which it is defined to it. Compound/function permits a sequence of function calls to be treated syntactically as a single call. Thus, for example, in if/then(A,B), B is frequently a call to compound/function, which in turn calls a sequence of other functions. Create takes two inputs: a superior object and a description. The superior must be a directory. The new object is created as the leftmost child of the directory; its name is determined by the description. 4.8 Details of primitive language functions This section provides specifications for the primitives discussed in the previous section. We are still omitting details when we judge them to be of no general interest; the objective is to provide enough information for the reader to examine examples. Most of the primitives occur at two levels in the model. The internal primitives are called i/functions and the external, or language primitives are called l/functions. The relationship between the two types are explained in 4.9. In this section we discuss i/functions. L/functions input and output _forms_, which are tree structures whose terminal nodes are atoms. The atoms are such things as function names, object names, literal string constants, truth va1ues and delimiters. Calls to i/functions are also expressed as forms. Any form can be evaluated, yielding some object. A form which is an i/function call yields the value returned by the i/function: another form. In general, the form returned by an i/function call will, when evaluated, yield a datalanguage object (that is, the sort of object we have been represented by an "object box" in the drawings). Winter, Hill & Greiff [Page 61]
RFC 610 Further Datalanguage Design Concepts December 1973 4.8.1 Name recognition functions These return a form which evaluates to an object. L/TOBJ Input must name a temporary object subordinate either to TOP/LEVEL or a block directory. L/POBJ Input must name a permanent object (i.e., an object subordinate to STAR). Typical calls are L/POBJ(X.Y.Z) and L/TOBJ(A). 4.8.2 Constant generators Each of these inputs an atomic symbol yielding a value for a constant to be created. Each returns a form which will evaluate to an object having the specified value and an appropriate description. LC/STRING - a typical call is LC/STRING('ABC') LC/BOOL - a typical call is LC/BOOL(TRUE) 4.8.3 Elementary item functions These input and output forms evaluating to elementary objects (objects which can have no subordinate object -- in effect, objects whose value is regarded as atomic). Eventually all the comparison operators will be implemented. L/ASSIGN Inputs must evaluate either to STRINGs or BOOLs. Outputs a form which transfers the value of the second to the first. Typical call: L/ASSIGN(L/TOBJ(A),LC/STRING('XYZ')) The output form, when evaluated, will copy 'XYZ' into A's value. L/EQUAL Inputs a pair of forms evaluating to objects, which must have identical descriptions and be BOOLs or STRINGs. Returns a form evaluating to an object of type BOOL. Value of this object is TRUE if inputs have identical descriptions and values; otherwise it is false. Typical call: Winter, Hill & Greiff [Page 62]
RFC 610 Further Datalanguage Design Concepts December 1973 L/EQUAL(L/TOBJ(X),LC/STRING('DEF')) L/AND, L/OR, L/NOT The standard boolean operators. Inputs are forms evaluating to BOOLs; output is a form evaluating to a BOOL. L/AND and L/OR take two inputs; L/NOT one. Typical call: L/AND( L/EQUAL(L/TOBJ(X),LC/STRING('DEF')), L/EQUAL(T/TOBJ(Y),LC/STRING('GHI')) ) The form returned will, when evaluated, return TRUE if both X has value 'DEF' and Y has value 'GHI'. 4.8.4 Data description functions These all return a form evaluating to a description (i.e. that which is represented in our drawings by a box labeled "description"). LD/STRING Inputs 3 parameters specifying the name, size option and size for the string. Typical call: LD/STRING(X,FIXED,3) This call returns a form evaluating to a description for a fixed-length 3-character string named X. LD/LIST Inputs two forms. The first is the name of the LIST and the second evaluates to a description of the LIST member. Typical call: LD/LIST(L,LD/STRING(M,FIXED,3)) Creates the structure shown in figure 4-11, and returns a form evaluating to the description represented by the upper box. Winter, Hill & Greiff [Page 63]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | _____________ | | | L | | | |_____________| | | NAME | | _____________ | | | LIST | | | |_____________| | | TYPE | | _____________ | | | | | | |________|____| | | CHILD | | |__________|______| DESCRIPTION | | __________V______ | _____________ | | | M | | | |_____________| | | NAME | | _____________ | | | STRING | | | |_____________| | | TYPE | | _____________ | | | _________ | | | | | FIXED | | | | | |_________| | | | | _________ | | | | | 3 | | | | | |_________| | | | |_____________| | | PARAMETERS | |_________________| DESCRIPTION Figure 4-11 LIST and member descriptions LD/STRUCT Inputs a form to use as the name for the STRUCT and one or more forms evaluating to descriptions; these are taken as the descriptions of the members. Typical call: Winter, Hill & Greiff [Page 64]
RFC 610 Further Datalanguage Design Concepts December 1973 LD/STRUCT(R, LD/STRING(A,FIXED,3) LD/BOOL(B) ) produces the structure shown in 4-12; returns a form evaluating to the top box. _________________ | _____________ | | | R | | | |_____________| | | NAME | | _____________ | | | STRUCT | | | |_____________| | | TYPE | | _____________ | | | | | | |_________|___| | | CHILD | | |___________|_____| DESCRIPTION | | ___________V_____ | _____________ | | | A | | | |_____________| | | NAME | | _____________ | | | STRING | | | |_____________| | | TYPE | _________________ | _____________ | | _____________ | | | | | | | B | | | |_____________| | | |_____________| | | PARAMETER | | NAME | | _____________ | | _____________ | | | ____|_|______\| | BOOL | | | |_____________| | /| |_____________| | | SIBLING | | TYPE | |_________________| |_________________| DESCRIPTION DESCRIPTION Figure 4-12 STRUCT and member descriptions Winter, Hill & Greiff [Page 65]
RFC 610 Further Datalanguage Design Concepts December 1973 LD/BOOL, LB/DIR, LD/OPD, LD/FUNC, LD/DESC Each inputs a name and produces a single description; each returns a form evaluating to the description produced. Typical call: LD/BOOL(X) 4.8.5 Data creation L/CREATE Inputs two forms and evaluates them. First must yield an object of type DIR; second must yield a description for the object to be created. Creates the object and returns a form, which, when evaluated, will generate a value for the new object. A simple example: L/CREATE(L/TOBJ(X),LD/B0OL(Y)) Figure 4-13 shows the directory X before execution of the above call. It contains only an OPD. After execution, the directory appears as in 4- 14. Creation of a value for Y occurs when the form returned by L/CREATE is evaluated (covered in section 4.9). Winter, Hill & Greiff [Page 66]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | | | _____________ | | | X | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | DIR | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | CHILD | | |___________|_____| OBJECT | | | ___________V_____ | | | _____________ | | | Z | | | |_____________| | | NAME | ____________ | _____________ | | ________ | | | ____|_|______\| | OPD | | | |_____________| | /| |________| | | DESCRIPTION | | TYPE | | _____________ | |____________| | | | | DESCRIPTION | |_________|___| | | VALUE | | ____________ |___________|_____| | | OBJECT |____________\| | /|____________| OPD Figure 4-13 X and Z before creation of Y Winter, Hill & Greiff [Page 67]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | _____________ | | | X | | | |_____________| | _________________ | NAME | | _____________ | | _____________ | | | DIR | | | | ____|_|______\| |_____________| | | |_____________| | /| TYPE | | DESCRIPTION | |_________________| | _____________ | DESCRIPTION | | | | | |_________|___| | | VALUE | | |___________|_____| OBJECT | ___________V_____ | _____________ | | | Y | | | |_____________| | _________________ | NAME | | _____________ | | _____________ | | | BOOL | | | | ____|_|______\| |_____________| | | |_____________| | /| TYPE | | DESCRIPTION | |_________________| | _____________ | DESCRIPTION | | | | | |_____________| | | VALUE | | _____________ | | | ____|_|______________ | |_____________| | | | SIBLING | | |_________________| ______V__________ _________________ OBJECT | _____________ | | _____________ | | | Z | | | | OPD | | | |_____________| | __\| |_____________| | | NAME | | /| TYPE | | _____________ | | |_________________| | | ____|_|___| DESCRIPTION | |_____________| | | DESCRIPTION | | _____________ | _________________ | | ____|_|______\| | Figure 4-14 | |_____________| | /|_________________| X, Y, and Z after | VALUE | OPD L/CREATE |_________________| OBJECT Winter, Hill & Greiff [Page 68]
RFC 610 Further Datalanguage Design Concepts December 1973 4.8.6 Control L/IF/THEN, L/IF/THEN/ELSE Used to request conditional evaluation of a form. Typical call: L/IF/THEN(L/EQUAL(L/TOBJ(A),LC/STRING('ABC'), L/ASSIGN(L/TOBJ(B),LC/STRING('DE'))) The form returned will do the following, when evaluated: if A has value 'ABC', then store 'DE' in the value of B. L/WHILE, L/TILL These iterate conditionally, as explained in the previous section. Examples appear later. L/CF Compound function: it inputs one or more forms and returns a form which, when evaluated, will evaluate each input in sequence. Typical call: L/CF(L/ASSIGN(L/TOBJ(R.A),LC/STRING('XX')), L/ASSIGN(L/TOBJ(R.B),LC/STRING('YY'))) When the output of L/CF is evaluated, it will assign new values to R.A and R.B. 4.8.7 Listops These primitives are executed in sequences in order to perform operations on LISTs. With the exception of L/END/OF/LIST these functions output forms which are evaluated for effect only; that is, the output forms do not themselves return values. L/LISTOP/BEGIN Inputs forms evaluating to: (1) a LIST, (2) an object to represent the current LIST member, (3) an OPD. Also, inputs a list of atomic forms whose values are taken as suboperations to enable. Typical call: L/LISTOP/BEGIN(L/POBJ(F),L/TOBJ(R), L/TOBJ(OPF),ADD,DELETE) This returns a form that will initialize a sequence of listops to be performed on F. Caller has previously created R and OPF. He intends to ADD and DELETE list members. All subsequent calls in this sequence of listops need specify only the OPD and auxiliary parameters. Winter, Hill & Greiff [Page 69]
RFC 610 Further Datalanguage Design Concepts December 1973 L/LISTOP/END Inputs a form evaluating to an OPD. Outputs a form which, when evaluated, clears OPD and breaks relationships between OPD, LIST and member objects. L/WHICH/MEMBER Inputs two forms. First evaluates to an OPD; second is one of FIRST, LAST, NEXT. The form output, when evaluated, will establish a new current member for the next suboperation. Note: this does not make the value of the member accessible, it simply identifies it by setting the instance number in the OPD. A typical call: L/WHICH/MEMBER(L/TOBJ(OPF),NEXT) When a which/member causes advance beyond the end of the list, a flag is set in the OPD. L/END/OF/LIST Inputs a form evaluating to an OPD. Outputs a form which, when evaluated, returns a BOOL. This has value TRUE if the end of list flag in the OPD is on. L/OPEN/MEMBER Inputs a form evaluating to an OPD and a form which must be one of ADD, DELETE, GET, CHANGE. Outputs a form which, when evaluated, will initiate the requested suboperation on the current LIST member. The suboperation always establishes the pointer from the member object to the current member value instance. In addition, in the case of ADD this value must be created. Typical call: L/OPEN/MEMBER (L/TOBJ (OPF) ,ADD) L/CLOSE/MEMBER Inputs a form evaluating to an OPD. Outputs a form which, when evaluated, will complete the suboperation in progress. A typical call: L/CLOSE/MEMBER(L/TOBJ(OPF)) Always clears the pointer from member object to member value. In addition, in the case of DELETE, removes the member value from the LIST. In the case of ADD enters the member value in the LIST. Makes the member added the current member, so that a sequence of ADDs executed without intervening which/members will add the new members in sequence. An elaborate example, involving listops and several other primitives, appears in section 4.10. Winter, Hill & Greiff [Page 70]
RFC 610 Further Datalanguage Design Concepts December 1973 4.9 Execution cycle The model datacomputer has a two-part execution cycle: it first compiles requests, then interprets them. A "request" is an l/function call; "compilation" is the aggregate result of executing all the l/function calls involved in the request (typically this is many calls, as there are usually several levels of nested calls, with the results of the inner calls being delivered as arguments to the next level of calls). Usually, the process of executing an l/function involves a simple macro expansion, preceded by some binding, checking and (eventually) optimization. The compiled form consists wholly of atomic symbols and i/function calls. The i/functions are internal primitives which input and output datalanguage objects (the entities represented by the boxes labeled "object" in the drawings). Each of the l/functions discussed compiles into a single i/function; thus the macro expansion aspect of compilation is presently trivial. However, this will not be true in general; it is only that these are _primitive_ l/functions that makes it true now. The decision to use a compile-and-interpret cycle calls for some explanation. The way to understand this, is to think in terms of the functions that would be performed in a strictly interpretive system. There would still be a requirement to perform global checks on the validity of the request in advance of the execution of any part of it. This is because partial execution of an incorrect request can leave a database in an inconsistent state; if this is a large or complex database, the cost of recovery will be considerable. Thus it pays to do as much checking as is possible; when the system is fully developed, this will include a certain element of simple prediction of execution flow; in any case, much more than syntactic checking is implied. Since any such global checks will be performed in advance of actual execution, they are effectively not part of the execution itself, for any given form. By performing them as part of a separate compilation process, we only formalize a modularity which already effectively exists. There will still be cases, however, in which checking, binding and optimization functions must be executed during interpretation, if at all. This will occur when the information needed is not available until some of the data has been accessed. When practical, we will provide for such occurrences by designing most functions so that they can be executed as part of either "half" of the cycle. As the model develops, we expect to get a better feel for this problem; Winter, Hill & Greiff [Page 71]
RFC 610 Further Datalanguage Design Concepts December 1973 it is certainly reasonable to end up with a structure in which there are many cycles of compilation and interpretation, perhaps forming a structure in which nesting of cycles within cycles occurs. 4.10 Examples of operations on LISTs Here we develop an example of an operation on a LIST using primitive l/functions. We first show the function calls required to create a LIST named F and give it a few member values. We then selectively copy certain members to a second LIST G. To create F: L/CREATE("STAR",LD/LIST(F, LD/STRUCT(R, LD/STRING(A,FIXED,2), LD/STRING(B,FIXED,2)))) This creates F as a member of the permanent directory STAR (see section 4.6 for details about STAR). The symbol STAR has a special status in the "language", in that it is one of the few atomic symbols to evaluate directly to an object. (Recall that most permanent objects are referenced through a call to L/POBJ; reserving the symbol STAR is equivalent to reserving STAR as a name and writing L/POBJ(STAR). The solution we choose here is easier to write.) Execution of this call builds the structure shown in 4-15 (except for STAR, which existed in advance of the call). The value initially created for F is an empty LIST--a LIST of zero members. Winter, Hill & Greiff [Page 72]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | STAR | | | | F | | | |_____________| | | |_____________| | | NAME | | NAME | | _____________ | | _____________ | | | | | | | LIST | | | |_________|___| | | |_____________| | | CHILD | | | TYPE | |___________|_____| | _____________ | OBJECT | | | | | | | |___________|_| | ___________V_____ __\| CHILD | | | _____________ | | /|_____________|___| | | F | | | DESCRIPTION | | |_____________| | | | | NAME | | _____________V___ | _____________ | | | _____________ | | | ____|_| | | | R | | | |_____________| |___| | |_____________| | | DESCRIPTION | | NAME | | _____________ | | _____________ | | | | | | | STRUCT | | | |_________|___| | | |_____________| | | VALUE | | | TYPE | |___________|_____| | _____________ | OBJECT | | | | | | | |___________|_| | ___________V_____ | CHILD | | | | |_____________|___| | | DESCRIPTION | |_________________| _____________V___ VALUE | _____________ | | | A | | | |_____________| | | NAME | _________________ | _____________ | | _____________ | | | STRING | | | | B | | | |_____________| | | |_____________| | | TYPE | | NAME | | _____________ | | _____________ | | | ____|_|_____\| | STRING | | Figure 4-15 | |_____________| | /| |_____________| | F immediately after | SIBLING | | TYPE | creation |_________________| |_________________| DESCRIPTION DESCRIPTION Winter, Hill & Greiff [Page 73]
RFC 610 Further Datalanguage Design Concepts December 1973 To add members to F, we need to use listops, and for this we must create two more objects: an object to represent the current member and an operation descriptor (OPD). These are temporaries rather than permanent objects; they are also "top level" (i.e., not local to a request). Temporary, top level objects are created as members of the directory TOP/LEVEL. The calls to create them are: L/CREATE(L/TOBJ(TOP/LEVEL), LD/STRUCT(M, LD/STRING(A,FIXED,2), LD/STRING(B,FIXED,2))) L/CREATE(L/TOBJ(TOP/LEVEL),LD/OPD(OPF)) We create M to represent the current member; its description is the same as the one input for a member of F (see the call which created F). The proper way to accomplish this is with a mechanism which shares the actual LIST member description with M; however, this mechanism does not yet exist in our model. We now wish to add some data to F; each member will be a STRUCT containing two two-character STRINGs. To begin the listop sequence: L/LISTOP/BEGIN(L/POBJ(F),L/TOBJ(M), L/TOBJ(OPF),ADD) This call establishes the structure shown in figure 4-16. It initializes the OPD, making it point to F and M and recording that only the ADD suboperation is enabled. Winter, Hill & Greiff [Page 74]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | STAR | | | | OPF | | | |_____________| | | |_____________| | | NAME | | NAME | | _____________ | | _____________ | | | | | | | | | | |_________|___| | | |_______|_____| | | CHILD | | | VALUE | | |___________|_____| |_________|_______| OBJECT | OBJECT | ___________V_____ _________V______ | _____________ | | _____________ | | | F | |/______|_|____ | | | |_____________| |\ | |_____________| | | NAME | | LIST | | _____________ | | _____________ | | | | | | | | | | |_________|___| | | |________|____| | | VALUE | | | MEMBER | | |___________|_____| |__________|______| OBJECT | VALUE | OPD | __________V______ ___________V_____ | _____________ | | | | | M | | | LIS | | |_____________| | |_________________| | NAME | VALUE | _____________ | | | | | | |________|____| | | CHILD | | |__________|______| OBJECT | __________V______ _________________ | _____________ | | _____________ | | | A | | | | B | | | |_____________| | | |_____________| | | NAME | | NAME | | _____________ | | _____________ | | | ____|_|_____\| | | | | |_____________| | /| |_____________| | | SIBLING | | | |_________________| |_________________| OBJECT OBJECT Figure 4-16 F, OPF and M after L/BEGIN/LISTOP Winter, Hill & Greiff [Page 75]
RFC 610 Further Datalanguage Design Concepts December 1973 Next we must establish a current member. We want to add members to the end (in this case, adding them anywhere would get the same effect, since the LIST is empty), which is done by making LAST the current member. L/WHICH/MEMBER(L/TOBJ(OP1),LAST) Now, to add a new member to F, we can execute the following: L/OPEN/MEMBER(L/TOBJ(OPF),ADD) L/ASSIGN(L/TOBJ(M.A),LC/STRING('AB')) L/ASSIGN(L/TOBJ(M.B),LC/STRING('CD')) L/CLOSE/MEMBER(L/TOBJ(OPF)) L/OPEN/MEMBER creates a STRUCT value for M. It does not affect the value of F. Each member of the STRUCT value is initialized when the STRUCT is created. The result is shown in 4-17; notice that the STRUCT member values are as yet unrelated to the objects M.A and M.B. Figure 4-18 shows the changes accomplished by the first L/ASSIGN; the pointer from the object M.A to the value was set up by a GET/STRUCT/MEMBER compiled by L/TOBJ(M.A). The value was filled in by the assign operator. The second assign has similar effect, filling in the second value. The call to L/CLOSE/MEMBER takes the value shown for M in 4-18 (with the second member value filled in) and adds it to the value of F. The result is shown in 4-19; compare with 4-16. Winter, Hill & Greiff [Page 76]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | M | | | | STRUC | | | |_____________| | | |_____________| | | NAME | | TYPE | | _____________ | | _____________ | | | ____|_|______\| | | | | |_____________| | /| |__________|__| | | DESCRIPTION | | CHILD | | | _____________ | |____________|____| _____|_|____ | | DESCRIPTION | | | |_____________| | | | | VALUE | ____________V____ | | _____________ | | _____________ | | | | | | | | STRING | | | | |_________|___| | | |_____________| | | | CHILD | | ___\| TYPE | _____________ | |___________|_____| | /| _____________ | | _________ | | OBJECT | | | | ____|_|______\| | STRING | | | | | | |_____________| | /| |_________| | | ___________V_____ | | SIBLING | | TYPE | | | _____________ | | |_________________| |_____________| | | | A | | | DESCRIPTION DESCRIPTION A | | |_____________| | | | | | NAME | | _________________ | | | _____________ | | | _____________ | | | | | ____|_|__| | | B | | | | | |_____________| | | |_____________| | | | | DESCRIPTION | | NAME | | | | _____________ | | _____________ | | | | | | | | | ____|_|___________________| | | |_____________| | | |_____________| | | | VALUE | | DESCRIPTION | | | _____________ | | _____________ | | | | ____|_|______\| | | | | | |_____________| | /| |_____________| | | | SIBLING | | VALUE | | |_________________| |_________________| | OBJECT OBJECT |___________________________ | _____________________V____________________ | _____________ _____________ | | | | | | | | |_____________| |_____________| | |__________________________________________| Figure 4-17 VALUE After L/OPEN/MEMBER Winter, Hill & Greiff [Page 77]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | M | | | | STRUC | | | |_____________| | | |_____________| | | NAME | | TYPE | | _____________ | | _____________ | | | ____|_|______\| | | | | |_____________| | /| |__________|__| | | DESCRIPTION | | CHILD | | | _____________ | |____________|____| _____|_|____ | | DESCRIPTION | | | |_____________| | | | | VALUE | ____________V____ | | _____________ | | _____________ | | | | | | | | STRING | | | | |_________|___| | | |_____________| | | | CHILD | | ___\| TYPE | _____________ | |___________|_____| | /| _____________ | | _________ | | OBJECT | | | | ____|_|______\| | STRING | | | | | | |_____________| | /| |_________| | | ___________V_____ | | SIBLING | | TYPE | | | _____________ | | |_________________| |_____________| | | | A | | | DESCRIPTION DESCRIPTION A | | |_____________| | | | | | NAME | | _________________ | | | _____________ | | | _____________ | | | | | ____|_|__| | | B | | | | | |_____________| | | |_____________| | | | | DESCRIPTION | | NAME | | | | _____________ | | _____________ | | | __|_|____ | | | | ____|_|___________________| | | | |_____________| | | |_____________| | | | | VALUE | | DESCRIPTION | | | | _____________ | | _____________ | | | | | ____|_|______\| | | | | | | |_____________| | /| |_____________| | | | | SIBLING | | VALUE | | | |_________________| |_________________| | | OBJECT OBJECT | |___________ | | | ________|_________________________________ | | ______V______ _____________ | |____\| | "AB" | | | | /| |_____________| |_____________| | |__________________________________________| Figure 4-18 VALUE After first L/ASSIGN Winter, Hill & Greiff [Page 78]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ _________________ | _____________ | | _____________ | | | STAR | | | | OPF | | | |_____________| | | |_____________| | | NAME | | NAME | | _____________ | | _____________ | | | | | | | | | | |_________|___| | | |___________|_| | | CHILD | | | VALUE | | |___________|_____| |_____________|___| OBJECT | OBJECT | ___________V_____ _____________V___ | _____________ | | _____________ | | | F | |/______|_|____ | | | |_____________| |\ | |_____________| | | NAME | | LIST | | _____________ | | _____________ | | | | | | | | | | |_________|___| | | |___________|_| | | VALUE | | | MEMBER | | |___________|_____| |_____________|___| OBJECT | VALUE | OPD | _____________V___ ______________V_________ | _____________ | | ______________________ | | | M | | || _________ _________ || | |_____________| | ||| "AB" || "CD" ||| | NAME | |||_________||_________||| | _____________ | ||______________________|| | | | | | / | | |___________|_| | | / | |_____________|___| |_______________/________| OBJECT | VALUE / / _____________V___ _________________ / / | _____________ | | _____________ | / / | | | | | | B | | / LIST | |_____________| | | |_____________| | / | NAME | | NAME | / | _____________ | | _____________ | NEW MEMBER VALUE | | ____|_|_____\| | | | | |_____________| | /| |_____________| | |_________________| |_________________| OBJECT OBJECT Figure 4-19 After L/CLOSE/MEMBER Winter, Hill & Greiff [Page 79]
RFC 610 Further Datalanguage Design Concepts December 1973 By executing similar groups of four primitives, varying only values of constants, we can build up the LIST F shown in 4-20. The calls required are shown below: L/OPEN/MEMBER(L/TOBJ(OPF),ADD) L/ASSIGN(L/TOBJ(M.A),LC/STRING('FF')) L/ASSIGN(L/TOBJ(M.B),LC/STRING('GH')) L/CLOSE/MEMBER(L/TOBJ(OPF)) L/OPEN/MEMBER(L/TOBJ(OPF),ADD) L/ASSIGN(L/TOBJ(M.A),LC/STRING('AB')) L/ASSIGN(L/TOBJ(M.B),LC/STRING('IJ')) L/CLOSE/MEMBER(L/TOBJ(OPF)) L/OPEN/MEMBER(L/TOBJ(OPF),ADD) L/ASSIGN(L/TOBJ(M.A),LC/STRING('CD')) L/ASSIGN(L/TOBJ(M.B),LC/STRING('LM')) L/CLOSE/MEMBER(L/TOBJ(OPF)) The add suboperation has the effect of making the member just added, the current member; thus no L/WHICH/MEMBER calls are needed in this sequence. To terminate the sequence of listops: L/END/LISTOP(L/TOBJ(OPF)) Winter, Hill & Greiff [Page 80]
RFC 610 Further Datalanguage Design Concepts December 1973 _________________ | _____________ | | | F | | | |_____________| | | NAME | | _____________ | | | ____|_|_________\ | |_____________| | / | DESCRIPTION | | _____________ | | | | | | |_________|___| | | VALUE | | |___________|_____| OBJECT | | _______________V______________ | __________________________ | | | _________ _________ | | | | | | | | | | | | | "AB" | | "CD" | | | | | |_________| |_________| | | | |__________________________| | | __________________________ | | | _________ _________ | | | | | | | | | | | | | "EF" | | "GH" | | | | | |_________| |_________| | | | |__________________________| | | __________________________ | | | _________ _________ | | | | | | | | | | | | | "AB" | | "IJ" | | | | | |_________| |_________| | | | |__________________________| | | __________________________ | | | _________ _________ | | | | | | | | | | | | | "CD" | | "LM" | | | | | |_________| |_________| | | | |__________________________| | |______________________________| VALUE Figure 4-20 After L/END/LISTOP Winter, Hill & Greiff [Page 81]
RFC 610 Further Datalanguage Design Concepts December 1973 A slightly more interesting exercise is to construct calls which create a LIST named G, having the same description as F, and then to copy into G all members of F having A equal to 'AB'. We must first create G, an OPD and an object to represent the current member. L/CREATE("STAR",LD/LIST(G, LD/STRUCT(R, LD/STRING(A,STRING,2), LD/STRING(B,STRING,2))) L/CREATE(L/TOBJ(TOP/LEVEL),LD/OPD(OPG)) L/CREATE(L/TOBJ(TOP/LEVEL) ,LD/STRUCT(GM, LD/STRING(A,STRING,2), LD/STRING(B,STRING,2))) We now need to initiate two sequences of listops, one on G and one on F. L/BEGIN/LISTOP(L/POBJ(F),L/TOBJ(M), L/TOBJ(OPF),GET) L/BEGIN/LISTOP(L/POBJ(G),L/TOBJ(GM), L/TOBJ(OPG),ADD) L/WHICH/MEMBER(L/TOBJ(OPF),FIRST) L/WHICH/MEMBER(L/TOBJ(OPG),LAST) We will now sequence through the members of F; whenever the current member has A equal to 'AB', we will add a member to G. We then copy the values of the current member of F into the newly added member of G. When the current member does not meet this criterion, we do nothing with it. First, to write a loop that will execute until we get to the end of F: L/TILL(L/END/OF/LIST(L/TOBJ(OPF)),x) Whatever we put in this call to replace "x" will execute repeatedly until the end/of/list flag has been set in OPF. We must replace "x" with a single function call to in order to give L/TILL what it is looking for. However, we will be executing "x" once for each member of F, and will need to execute several listops each time. The solution is to use L/CF, the compound-function function: L/TILL(L/END/OF/LIST(L/TOBJ(OPF)),L/CF(y)) We can now replace "y" with a sequence of function calls. Each time we iterate, we need to process a new member of F; initially we are set up to get the first member. The following sequence, then, is needed: L/CF( L/OPEN/MEMBER(L/TOBJ(OPF),GET), z L/CLOSE/MEMBER(L/TOBJ(OPF)), L/WHICH/MEMBER(L/TOBJ(OPF),NEXT) ) Winter, Hill & Greiff [Page 82]
RFC 610 Further Datalanguage Design Concepts December 1973 The above is a compound function which will open the current member of F, do something to it (represented above by "z"), close it, and ask for the next member. We want to replace "z" by a function call which tests the contents of A in the current member of F, and either does nothing or adds a member to G, copying the values of the current member of F. If "w" represents the action of adding a member to G and copying the values, then we can express this: L/IF(L/EQUAL(L/TOBJ(M.A),LC/STRING('AB')),w) A suitable way to express "add a member and copy values" is: L/CF(L/OPEN/MEMBER(L/TOBJ(OPG),ADD), L/ASSIGN(L/TOBJ(GM.A),L/TOBJ(M.A)), L/ASSIGN(L/TOBJ(GM.B),L/TOBJ(M.B)), L/CLOSE/MEMBER(L/TOBJ(OPG)) This is similar enough to the previous example so that no explanation should be necessary. Putting this all together, we get: L/TILL(L/END/OF/LIST(L/TOBJ(OPF)), L/CF( L/OPEN/MEMBER(L/TOBJ(OPF),GET), L/IF(L/EQUAL(L/TOBJ(A),LC/STRING('AB')), L/CF( L/OPEN/MEMBER(L/TOBJ(OPG),ADD), L/ASSIGN(L/TOBJ(GM.A),L/TOBJ(M.A)), L/ASSIGN(L/TOBJ(GM.B),L/TOBJ(M.B)), L/CLOSE/MEMBER/L/TOBJ(OPG)) ) ) L/CLOSE/MEMBER(L/TOBJ(OPF)), L/WHICH/MEMBER(L/TOBJ(OPF),NEXT) ) ) To conclude the operation, we execute: L/LISTOP/END(L/TOBJ(OPG)) L/LISTOP/END(L/TOBJ(OPF)) The result is a LIST G whose first member has value ('AB','CD'), and whose second member has value ('AB','IJ'). With a few variations on the above example, quite a few LIST operations can be performed. 4.11 Higher level functions While these primitive i/functions are useful, we would not ordinarily expect users to operate in datalanguage at this low level. We want to make these primitives available to users so that they can handle the exceptional case, and so that they can construct their own high-level functions for atypical applications. Ordinarily, they ought to operate at least at the level of the following construction (which is legal in the real datalanguage currently implemented): Winter, Hill & Greiff [Page 83]
RFC 610 Further Datalanguage Design Concepts December 1973 FOR G.R,F.R WITH A EQ 'AB' G.R=F.R END This relatively concise expression accomplishes the same result as the elaborate construction of i/functions given at the close of the preceding section. We could define i/functions very similar to the semantic functions used in the running software, and write the above request as: L/FOR(L/POBJ(G),R L/POBJ(F),R,L/WITH(L/EQUAL(L/TOBJ(A), LC/STRING('AB'))) The differences between the i/function call and the datalanguage request above it are principally syntactic. In designing functions such as L/FOR and L/WITH, the central problems have to do with choosing the right restrictions. One cannot have all the generality available at the primitive level. Some important choices for these particular functions are: (1) handling multiple inputs and outputs, (2) when FORs are nested, how outer FORs restrict the options available to inner FORs, (3) generality of selection functions (may then in turn generate FORs?), (4) options with regard to where processing should start (are we updating, replacing or appending to the output list(s)?). Finally, this problem is related to the more general problem of dealing with _sets_, which are a generalization of the idea of a collection of members in a LIST having common properties. FOR is only one of many operators that can input sets. 4.12 Conclusion The present model, though embryonic, already contains enough primitives and data types to permit definition and generalized manipulation of hierarchical data structures. Common data management operations, such as retrieval by content and selective update can be expressed. The use of this model in developing these primitives has resulted in precise, well-defined and internally consistent specifications for language elements and processing functions. Operating in the laboratory environment provided by the model seems to be a substantial benefit. Winter, Hill & Greiff [Page 84]
RFC 610 Further Datalanguage Design Concepts December 1973 5. Further Work In this section, we review what has been accomplished so far in the design and describe what work remains to be done before this design iteration of datalanguage is complete. 5.1 A Review Most important, among our accomplishments, we feel that we have delineated the problems and presented the broad outlines of a solution to development of a language for the datacomputer system. Key elements of our approach are the primacy of data description in capturing all the aspects of the data, the separation of logical and physical characteristics of data description, the ability of users to define different views of the same data, the ability to associate functions with different uses of data items, an attempt to capture common aspects of data at every possible level, and the ability of users to communicate with the datacomputer in as high a level as their application permits. 5.2 Topics for Further Research Although more work needs to be done in general to turn out a finished design for datalanguage, we can single out certain issues which in particular need further investigation. So far, only hierarchal data structures (i.e. those that can be modeled by physical containment) have been developed to any extent. We also intend to investigate and provide other types of data structures. We are confident that our language framework does not make assumptions that would prohibit such additions. Our current work on access regulation centers on the use of multiple descriptions for data. We need to do more work on both the technical and administrative aspects of access regulation. Problems of encrypting data for both transmission and storage will also be investigated. Another issue requiring further research is the protocol requirement for process interaction with the datacomputer. Separation of the description into independent modules needs further research. In particular, we need to look into work which has already been done on separate specifications of logical descriptions, physical descriptions, and mappings between the two. Winter, Hill & Greiff [Page 85]
RFC 610 Further Datalanguage Design Concepts December 1973 5.3 Datalanguage Syntax We have not yet proposed a syntax for the datalanguage we are developing. Certainly the most difficult parts of the problem have been the semantic and pragmatic issues. We are confident that various syntactic forms can be chosen and implemented without excessive difficulty. It may be best to develop different syntactic forms for the language for different types of users or even for the various subparts of the language itself. As discussed in section 2, the user syntax for the datacomputer is supposed to be at a low level. It should be easy for _programs_ to generate datalanguage requests in this syntax. 5.4 Further Work on the Datalanguage Model The model provides an excellent foundation on which to build up a language with the facilities described in section 3. Much work is yet to be done. For a while, emphasis will be on sets, high-level operators, language extension and data description. We expect to model sets as a new datatype, whose value is ordinarily shared with other objects. Some further work on binding and sharing of values is needed to support this. Sets can be regarded as a special case of generalized relations, which will come somewhat later. High-level operators such as FOR will be constructed from the existing primitives, and will eventually be defined to have one effect but several possible expansions. The expansion will depend on the representation of the data and the presence of auxiliary structures. Alternate expansions will be possible when the data description has been broken up into its various modules. This, also, requires some further research. We feel that the language extension problem is much more easily attacked in the environment provided by the model datacomputer. In particular, we expect the laboratory environment to be helpful in evaluating the complex interactions and pervasive effects of operators in the language which extend the language. Data description work in the near term will focus on the isolation of attributes, the representation of variable structure in description, the description of descriptions and the development of a sufficient set of builtin data types. Winter, Hill & Greiff [Page 86]
RFC 610 Further Datalanguage Design Concepts December 1973 Later, we expect to model the semantics of pointers as a datatype, when the representation of the pointer and the semantics of the address space into which it points are specified in the description of the pointer. A large number of lower-level issues will be attacked, including some of the problems discovered in the modeling to date. Some of these are pointed out in the discussions in section 4. 5.5 Applications Support The datalanguage we are designing is intended to provide services to sub-systems solving a broad class of problems related to data management. Examples of such sub-systems are: report generators, online query systems for non-programmers, document-handling systems, transaction processing systems, real-time data collection systems, and library and bibliographic systems. There are many more. The idea is that such systems will run on other machines, reference or store data at the datacomputer, and make heavy use of datalanguage. Such a system would not be written entirely in datalanguage, but a large component of its function would be expressed in datalanguage requests; some controlling module would build the requests and perform the non- datalanguage functions. While we have experience with such applications in other environments, and we talk to potential users, it will require some work to determine that our language is actually adequate for them. That is, we are not attacking directly the problem of building a human-oriented online query system; we are trying to provide the tools which will make it easy to build one. There is a definite need to analyze whether the tools are likely to be good enough. Of course, the ultimate test will be in actual use, but we want to filter out as many problems as we can before implementation. An important component of supporting applications is that the using programs will frequently be written in high-level languages such as FORTRAN, COBOL or PL/1. We will want to investigate the ability of datalanguage to support such users, while the design is taking shape. 5.6 Future Plans This paper has laid the foundations for a new design of datalanguage. Section 3 provides an outline for a datalanguage design, which will be filled in during the coming months. Following the issue of a detailed specification, we anticipate extensive review, revisions, and Winter, Hill & Greiff [Page 87]
RFC 610 Further Datalanguage Design Concepts December 1973
incorporation into the implementation plans. Implementation will occur
in stages, compatible with the established plans for development of
datacomputer service and data management capabilities.
[ This RFC was put into machine readable form for entry ]
[ into the online RFC archives by Alex McKenzie with ]
[ support from GTE, formerly BBN Corp. 1/2000 ]
Winter, Hill & Greiff [Page 88]
mirror server hosted at Truenetwork, Russian Federation.