A language extension for graph processing and its formal semantics

ABSTRACT

A simple programming language “extension,” Graspe, for processing directed graphs is defined. Graspe consists of a type of directed graph data structure and a set of primitive operations for manipulating these structures. Graspe may be most easily implemented by embedding it in a host language. Emphasis is placed both on Graspe itself and on its method of definition. Commonly, the definition of a language involves definition of the syntactic elements and explanation of the meaning to be assigned them (the semantics). The definition of Graspe here is solely in terms of its semantics; that is, the data structures and operations are defined precisely but without assignment of a particular syntactic representation. Only when the language is implemented is assignment of an explicit syntax necessary. An example of an implementation of Graspe embedded in Lisp is given as an illustration. The advantages and disadvantages of the definition of a language in terms of its semantics are discussed.

REFERENCES

• 1: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 2: P. J. Landin, Correspondence between ALGOL 60 and Church's Lambda-notation: part I, Communications of the ACM, v.8 n.2, p.89-101, Feb. 1965 [doi>10.1145/363744.363749]
• 3: Lucas, P., et al. Method and notation for the formal definition of programming languages. TR 25.087, IBM, Vienna, June 1968 (see also related reports).
• 4: Hart, R. HINT: A graph processing language. Computer Inst. for Social Science Res., Michigan State U., East Lansing, Mich., Feb. 1969.
• 5: S. Crespi-Reghizzi , R. Morpurgo, A language for treating graphs, Communications of the ACM, v.13 n.5, p.319-323, May 1970 [doi>10.1145/362349.362366]
• 6: Friedman, D., Dickson, D., Fraser, J., and Pratt, T. W. GRASPE 1.5: A graph processor and its application. Rep. on ONR-CONTRACr N00014-68-a-01-51, Dep. Comput. Sci., U. of Houston, Texas, Aug. 1969.
• 7: Robert F. Simmons, Natural language question-answering systems: 1969, Communications of the ACM, v.13 n.1, p.15-30, Jan. 1970 [doi>10.1145/361953.361963]
• 8: Zohar Manna, Properties of Programs and the First-Order Predicate Calculus, Journal of the ACM (JACM), v.16 n.2, p.244-255, April 1969 [doi>10.1145/321510.321516]
• 9: Pratt, T. W. A hierarchical graph model of the semantics of programs. Proc. AFIPS 1969 S~CC, Vol. 34, AHPS Press, Montvale, N.J., pp. 813-825.
• 10: Narashiman, R. Programming languages and computers: A unified metatheory. In Advances in Computers, Vol. 8, F. L. Alt, Ed., Academic, New York, 1967.
• 11: Friedman, D. P. ORASPE graph processing: A LISP extension. Rep. TNN-84, Comput. Ctr., U. of Texas, Austin, 1968.
• 12: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]
• 13: Weissman, C. LISP 1.5 Primer. Dickenson Pub. Co., Belmont, Calif., 1968.

INDEX TERMS

Keywords:
Lisp, data structure, directed graph, flowchart, formal semsntics, graph processing, language definition, network, programming language, syntax