Programming with abstract data types, some examples

ABSTRACT

The data structuring facilities of contemporary languages like Algol-68, Pascal and Simula supports only one type of graphs, the general graph. It is only possible to define the structure of a node in a graph, not to define how the nodes are interrelated. Nothing in the languages prevents the programmer from using for instance a node in a binary tree as an element in a double list. This means that the programmer has to prove a lot of invariants on graphs which would not be necessary if the language supported declarations of different graphs. This paper contains some examples of algorithms on different graphs. We use a presentation language which is based on Pascal. We have replaced the pointers in Pascal with a set of type constructors. These type constructors give us a possibility to manipulate different graphs in a safe way.

REFERENCES

• 1: Dijkstra EW: A note on two problems in connexion with graphs. Numerische Matematik 1,269-271 (1959).
• 2: Nordström Bengt: Some concepts for very high level languages without explicit pointers, Ph D thesis. University of Umeá, Sweden.
• 3: Scott D: Data types as lattices, Siam Journal on computing, 5 (1976), pp 522-587
• 4: Scott D: Lattice theory, data types and semantics, NYU Symposium on formal semantics (ed R. Rustin), Prentice Hall, NY (1972)
• 5: F. L. Bauer , J. Eickel, Compiler Construction: An Advanced Course, Springer-Verlag, Berlin, Heidelberg, 1976

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Abstract data types

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Pascal

  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Languages, Theory

Keywords:
Graphs, Mappings, Pascal, Pointers