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