A Language Extension for Graph Processing and Its Formal Semantics 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. CACM July, 1971 Pratt, T. W. Friedman, D. P. graph processing, programming language, formal semantics, directed graph, Lisp, network, data structure, flowchart, syntax, language definition 4.20 4.22 5.23 5.24 5.32 CA710704 JB February 3, 1978 9:24 AM 1086 4 2178 1132 4 2178 1234 4 2178 1263 4 2178 1265 4 2178 1270 4 2178 1323 4 2178 1358 4 2178 1379 4 2178 1380 4 2178 1453 4 2178 1464 4 2178 1469 4 2178 1484 4 2178 1486 4 2178 1491 4 2178 1491 4 2178 1498 4 2178 1613 4 2178 1614 4 2178 1781 4 2178 1781 4 2178 1781 4 2178 1825 4 2178 1860 4 2178 2083 4 2178 2178 4 2178 2178 4 2178 2178 4 2178 2178 4 2178 2178 4 2178 2179 4 2178 2252 4 2178 2325 4 2178 2326 4 2178 2326 4 2178 2341 4 2178 2396 4 2178 2470 4 2178 2546 4 2178 2561 4 2178 2645 4 2178 2652 4 2178 2684 4 2178 2684 4 2178 2684 4 2178 2842 4 2178 2929 4 2178 2934 4 2178 3044 4 2178 3069 4 2178 669 4 2178 679 4 2178 691 4 2178 761 4 2178 949 4 2178 989 4 2178 1303 5 2178 1323 5 2178 2059 5 2178 2127 5 2178 2178 5 2178 2178 5 2178 2178 5 2178 3184 5 2178