Mem-theory(ID:6725/mem001)

Graph-based universal language 


Language based on general theory of elements in relation and changes of relation. This in contrast to the "pure" algorithmic and functional approaches which see memory access as a "necessary evil" - hence memory-theory - the theory designed to investigate the relations between the meaning and acts of memory accss.

Influenced also by the IPL and the LT machine.

The research grew out of the GP and ACT projects at Univac and ADR, and Holt's subsequent PhD in Applied Linguistics at Pennsylvania U. and the Information Theory project at Computer Associates Mass.

Described by Earley as originating graph-theory in programming languages


from Austin
"First, we must specify the effect of any event; i.e., the change in binding to be effected. The syntactic specification is borrowed from the mem-theory of Holt et al, which is a general theory of elements in relation and changes of relation. Briefly, the state of binding is represented by a graph whose (labelled) nodes represent system resources and whose edges represent relations (bonds) among them. Edges might be uniquely differentiated by their endpoints{ if not, they may be labelled or directed. The distinct labels on nodes or edges identify particular resources or classes of resources (or bonds). The change of binding to be effected is specified by a second graph depicting the final binding state in a similar manner. Special conventions are provided to indicate insertion or deletion of items in ordered sets. (The order relation on the set must be specified outside the graphic syntax.)"


People:
Related languages
ACT => Mem-theory   Evolution of
IPL-V => Mem-theory   Influence
Mem-theory => VERS   Influence

References:
  • Holt, Anatol W. "Program organization and record keeping for dynamic storage allocation" view details
          in [ACM] CACM 4(10) (October 1961) "Proceedings of a Symposium on Storage Allocation" view details
  • Holt, Anatol W. "Program Organization and Record Keeping for Dynamic Storage Allocation" pp539-544 view details
          in Popplewell, Cicely M. (Ed.) Information Processing 62, Proceedings of the 2nd IFIP Congress, Munich, Aug. 1962. North Holland Publ. Co., 1963. view details
  • Holt, A. W. Some Theorizing on Memory Structure and Information Retrieval. pp166-178 view details Abstract: Outlines some theoretical work aimed at showing that the operations of accessing are fundamental in comput,ing, and hence are the proper beginning for a theory of computation; that the resulting theory will cover the ground normally reserved to algorithms. This is in clear opposition to a widely prevalent trend in which the operations of accessing are regarded as a necessary evil, the compromises with reality, the so-called "efficiency questions", which always appear at, the end to spoil the pristine beauty of abstract algorithms. In the author's view, the meaning of thw most abstract algorithms will ultimately be understood as a strategy for performing accesses in the light of some assumed (but expressed) restrictions of the memory structure in which the process must go forward
          in Information Processing Machines: Proceedings of the Symposium held in Prague on September 7th-9th, 1964. Czechislovak Academy of Sciences (Prague) and Iliffe Books, Ltd. (London) 1965 view details
  • Holt, A.W. Mem-theory, a mathematical method for the description and analysis of discrete finite information systems, Applied Data Research, Inc., 1965 view details
          in Information Processing Machines: Proceedings of the Symposium held in Prague on September 7th-9th, 1964. Czechislovak Academy of Sciences (Prague) and Iliffe Books, Ltd. (London) 1965 view details
  • Holt, A.W., Changon, S. O., Shapiro, R. M., and Warshall, S. 1965. Information System Theory Project, Vol. 1, Document AD 629-819 (National Technical Information Service, Springfield, Va.). view details
          in Information Processing Machines: Proceedings of the Symposium held in Prague on September 7th-9th, 1964. Czechislovak Academy of Sciences (Prague) and Iliffe Books, Ltd. (London) 1965 view details
  • Holt, A.W. INFORMATION SYSTEM THEORY PROJECT, FINAL REPORT. Applied Data Research, Inc. (Princeton, New Jersey) report no. ADR-Ref-6606, USAF Rome Air Development Center report no. RADC-TR-68-305, CFSTI report no. AD-676 972, 359 pages. 1968 September. view details Abstract: The Information System Theory Project has been engaged in basic research aimed at developing theory and technique for the analysis and description of data structures. Three principal objectives were defined at the outset: Description of data structures with precision and conciseness for communication between designers, implementers, and users; Description of data structures leading to implementation insights; Description of data structures leading to evaluations of the form:  Given a particular computing system and a class of storage and retrieval problems, how suitable is a described structure as a means of accomplishing problem solutions on the proposed equipment. This report gives the main results to date of the project.
          in Information Processing Machines: Proceedings of the Symposium held in Prague on September 7th-9th, 1964. Czechislovak Academy of Sciences (Prague) and Iliffe Books, Ltd. (London) 1965 view details
  • Holt, A. W. and Commoner, F. 1970. "Events and Conditions". Technical Report (Massachusetts Computer Associates, Inc., Wakefield, Ma.). view details
          in Information Processing Machines: Proceedings of the Symposium held in Prague on September 7th-9th, 1964. Czechislovak Academy of Sciences (Prague) and Iliffe Books, Ltd. (London) 1965 view details
  • Earley, Jay "Toward an understanding of data structures" view details Extract: Programming Languages and an Implementation Facility
    Programming Languages and an Implementation Facility
    We have presented a notion of the semantics of data structures. We would now like to explore the possibility of using this idea as the basis for a programming language. (We are, in fact, doing this with a language called VERS.) The simplest approach is just to embed the V-graph primitives in a language, extending them with some kind of control structure, subroutines, etc., that one finds in any programming language. But how does one refer to a V-graph in such a language, and what happens to such standard notions as those of variable and assignment statement?
    The important observation to make along these lines is that there are basically two categories of objects in a programming language--a fixed number of "static" objects whose names can be written in a program, and an arbitrary number of "dynamic" objects which are created by the program at run-time and may be referenced only through the static objects. Thus in VERS there are static and dynamic varieties of nodes, links, and atoms. Static nodes are headers for data structures whose identity cannot be changed by the program. (The symbol table header is an example of this.) Dynamic nodes are created by the CREATE primitive and are parts of data structures which can be altered (such as stack element nodes). They may be referenced only through links. Static links are links which do not come from nodes, but have an existence of their own. These would be used to represent the concept of a variable in an ordinary language. The links emanating from nodes are dynamic and represent access paths in the data structure. Similarly, a static atom is a constant, and a dynamic atom is the value of a variable or a value stored in a data structure.
    If we include transformations in VERS, then they can be used to specify primitive operations on the data structures and also as data structure descriptions from which information may be deduced by a compiler. Our ultimate aim is that a programmer would express his algorithm in VERS using V-graphs and being as unconcerned with implementation as he likes. Then the compiler would process his data structure descriptions, determine a good implementation, and carry it out. However, we are not at the point where this is feasible. We do not yet understand enough about alternative implementations of V-graphs or the process of specifying an implementation or the mathematical properties of V-graphs.
    Therefore, in order to gain some experience with these things and also so that such a language may be programmer may describe the implementation of a data structure whose semantics is expressed by V-graphs. Higher level languages have for a long time given us the ability to write programs in a way which avoids some of the extraneous details and bookkeeping which must go on in the computer. In the process of doing away with the bookkeeping, however, most languages take away from the programmer some control over implementation which he may need for efficiency. In fact, because of this, low level systems-programming languages have developed [12-15] in order to restore some of this control (especially over data structures) without reverting to machine language. However, these languages usually lack much of the power of higher level languages. Our concept of an implementation facility is an attempt to provide the advantages of both.
    A programmer first writes his algorithm in VERS, obtaining the advantages of V-graphs and a higher level language. He can debug the algorithm by using a general default implementation which is good for any V-graph, supplied by the VERS compiler. He may then, if he wants, insert declarations and/or code into his program to specify how the data structures are to be implemented. Ideally, he may go into as much detail as he needs to achieve the efficiency he wants. He may experiment with several implementations in order to get the best one for his needs, this being feasible because it does not mean rewriting the basic code of the program as it would ordinarily. He may even ignore implementation entirely if the program is already good enough for his needs.
    This idea has been used successfully in a very limited way in the field declaration facility of L6 [11], which is a special case of our system. It has been proposed on a larger scale by Balzer [16], but not implemented. In addition, although we agree with his concept of an implementation facility, we much prefer V-graphs to his data structures (hierarchical ordered sets).
    The basic idea of the implementation facility is that one specifies the implementation of a high level V-graph in terms of lower level V-graphs which more closely (or exactly) reflect the structure of the data in the machine. In the most general case, this means that for each node-type and for each possible kind of link from that node-type, the programmer writes an algorithm in VERS to implement each of the primitives which work on that node-type and link. Thus the "primitives" are no longer primitives but are instead subroutines (or macros) for the next lower level of implementation. At the lowest level, each node, link, and atom in the V-graph corresponds exactly to some allocatable resource in the machine.
    For current machines, we have decided that a node should correspond to a bead [23] (a contiguous block of words in memory), each of its links should correspond to a field of bits within this block, and each atom should correspond to a pattern of bits. At this level, the primitives do not need to be recoded. Instead the programmer just declares the size of the bead for the node and the locations of the fields for the links, much as in L6[12].

          in [ACM] CACM 14(10) October 1971 view details
  • Austin, Joseph H. Jr. "Specification languages for control programs" pp34-37 view details Abstract: This study (1) describes an approach to the formal specification of control programs based on the generalized concept of binding. From this viewpoint, the individual operations of a control program may be described by a graphic specification language [related to mem-theory (2)], whose statements are pairs of graphs depicting the original and final binding states of system elements. A global view of interrelationships and dynamic behavior of the system may be described by an extension of Petri-nets (3, 4) depicting the flow of system elements from one state of local binding to another. A rational approach to the design of a new programming language must begin with an analysis of the ?meanings? that are to be expressed; an appropriate, compilable syntax can then be developed around this skeleton. Consequently, we seek to identify, the characteristic features of operating system programming, and in particular those that differentiate these programs from conventional ones. DOI
          in SIGPLAN Notices 8(09) June 1973 Proceedings of ACM SIGPLAN - SIGOPS interface meeting on Architectural Support for Programming Languages and Operating Systems, Savannah, Georgia, 1973 view details
  • Liskov, Barbara and Zilles, Stephen "Specification techniques for data abstractions" pp72-87 view details
          in Proceedings of the International Conference on Reliable software Los Angeles, California 1975 view details