Implementing Ruby in a Higher-Order Logic Programming Language

Richard McPhee^{∗}

April 20, 1995

Abstract

Ruby is a relational language for describing hardware circuits. In the past, programming tools existed which only catered for the execution of functional Ruby expressions rather than the complete set of relational ones. In this paper, we develop an implementation of Ruby in λProlog—a higher-order logic programming language—allowing the execution of arbitrary, relational Ruby programs.

1 Introduction

Programming problems can be tackled by specifying a program’s behaviour in an abstract mathematical specification and then, through the application of some appropriate calculus, converting this into an efficient and implementable program. Until recently, the art of deriving computer programs from specification has been performed equationally in a functional calculus [Bir87]. However, it has become evident that a relational calculus affords us a greater degree of expression and flexibility in both specification and proof since a relational calculus naturally captures the notions of non-determinism along with function converses.

Ruby is one such relational language developed by Jones and Sheeran [Jon90, JS90] to describe the behaviour of hardware circuits. However, existing Ruby programming tools only provide for the execution of functional Ruby expressions [LP95, Hut93, Hut92]. In this paper, a purely relational implementation of Ruby is developed in λProlog [LHRB94, NM88]—a higher-order logic programming language—allowing the execution of abstract Ruby circuit specifications. The implementation is purely relational since expressions have a well-defined converse.

The remainder of the paper is organised into four sections. In Section 2, we introduce the Ruby relational language. In Section 3, an implementation of Ruby is developed in λProlog. An example of using the Ruby implementation is presented in Section 4 and we draw several conclusions in Section 5.

∗Author’s Address: Richard McPhee, Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, U.K. Electronic mail: rm@comlab.ox.ac.uk. Telephone: 01865 273865.

Fax: 01865 273839.

2 Ruby

Ruby is a relational language developed by Jones and Sheeran [Jon90, JS90] for describing hardware circuits. The behaviour of a circuit is specified by a relational program which can then be transformed into an equivalent program amenable to implementation in hardware. A circuit in Ruby is represented as a binary relation between simple data values. Recall that a binary relation R : A → B, of type A to B, is a subset of the cartesian product (A× B) of sets A and B. We write a R b to denote that (a, b) ∈ R.

The data values on which these circuits operate consist solely of integers, and both tuples and lists of integers. A tuple is represented in Ruby by the notation (a, b) whose type is (A × B) for any types A and B, and a list is represented by [a_{0}, a_{1}, …, a_{n}] for each element a_{i} having type A and the type of the list is list A. The empty list is denoted by ‘[ ]’. It is worth mentioning that, in this paper, tuples are considered distinct from lists, i.e., a tuple and a list of length two are treated differently. Other descriptions of Ruby [JS91a, Jon90] tend to blur the distinction between tuples and lists, allowing them to be dealt with interchangeably. As a consequence, however, automatic type deduction becomes greatly complicated, so hampering the implementation of Ruby in a strongly typed language, like λProlog.

A relation in Ruby can be given pictorially, corresponding directly to its interpretation as a circuit. For example, the circuit associated with the relation R : A → B can be represented as the single node

R  .

The convention regarding data flow in such a circuit is that domain values “enter” at the left and top sides of the node and range values “exit” at the bottom and right sides. In addition, multiple wires to and from a node are read from bottom to top. Therefore, a relation (a, b)S (c, d) : (A×B) → (C ×D)—taking tuples to tuples—may be represented by the circuit

S a  bc  d .

Ruby expressions are composed hierarchically from primitive relations and higherorder functions. The most fundamental of these are sequential composition, parallel composition, and converse. The sequential composition of two relations R : A → B and S : B → C , written as R ; S : A → C , is given by

R : A → B, S : B → C ⇒ R ; S : A → C ,
a (R ; S) c ≡ ∃b.a R b ∧ b S c.

The first line in this expression denotes the type information of the function in a similar style to that adopted by Jones and Sheeran [JS91b]. The sequential composition of two circuits look like this:

R  S  .

The parallel composition of two relations R and S, written as [R, S], is expressed by

R : A → B, S : C → D ⇒ [R, S] : (A × C ) → (B × D),
(a, c) [R, S] (b, d) ≡ a R b ∧ c S d.

The parallel composition of two circuits simply places them over one another in the following way:

S R  .

Every relation R has a well-defined converse R^{−1}, given straightforwardly by

R : A → B ⇒ R^{−1} : B → A,
b R^{−1} a ≡ a R b.

Converse reverses composition in that (R ; S)^{−1} = S^{−1} ; R^{−1} and is also an involution since (R^{−1})^{−1} = R.

Several primitive relations are used to construct and deconstruct the data values of a circuit. For tuples, we have the relations

a id b ≡ a = b,
(a, b) swap (c, d) ≡ a = d ∧ b = c,
(a, b) outl c ≡ a = c,
(a, b) outr c ≡ b = c,
a fork (b, c) ≡ a = b ∧ a = c,
((a, b), c) lsh (d, (e, f )) ≡ a = d ∧ b = e ∧ c = f ,
(a, (b, c)) rsh ((d, e), f ) ≡ a = d ∧ b = e ∧ c = f .

Of these relations, only id, outl, and outr are essentially primitive in the presence of relational intersection. The intersection of two relations R and S, written as R ∩ S, is defined by

R : A → B, S : A → B ⇒ R ∩ S : A → B,
a (R ∩ S) b ≡ a R b ∧ a S b.

The primitive Ruby relations for lists are

(as, bs) app cs ≡ as ++ bs = cs,
(a, as) apl bs ≡ [a] ++ as = bs,
(as, a) apr bs ≡ as ++ [a] = bs,
a wrap bs ≡ [a] = bs,
a null bs ≡ bs = [ ],

R a  bc  S ef  g

(a, (b, e)) R ↔ S ((c, f ), g)

S e  f  h

R a  c  d

((a, e), f ) R ↕ S (c, (d, h))

Figure 1: The circuits corresponding to beside and below.

where ‘++’ denotes list concatenation. These primitive relations provide us with the bare bones of the Ruby language. The real expressive power is obtained by building higher-order functions—taking relations to relations—from these combining forms. Two commonly used higher-order functions are simple shorthands, given by

fst R ≡ [R, id],
snd R ≡ [id, R].

Since Ruby is a language for designing circuits, a plethora of functions exist for combining circuit elements. For two circuits, denoted respectively by the relations R and S, the function ‘↔’ (pronounced ‘beside’) joins R and S together in the following fashion:

\begin{matrix}R : (A × B) → (C × D) \\ S : (D × E) → (F × G) \end{matrix} \} ⇒ R ↔ S : (A × (B × E)) → ((C × F ) × G),
R ↔ S ≡ rsh ; fst R ; lsh ; snd S ; rsh.

The beauty of Ruby is exemplified when we define the dual of existing functions in terms of themselves, providing a convenient way to produce new circuits. We can obtain the dual of any higher-order function by first taking the converse of all its arguments and then taking the converse of the entire expression. For example, we can manufacture the function ‘↕’ (pronounced ‘below’) in terms of its dual function beside by

\begin{matrix}R : (A × B) → (C × D) \\ S : (E × F ) → (B × H ) \end{matrix} \} ⇒ R ↕ S : ((A × E) × F ) → (C × (D × H )),
R ↕ S ≡ (R^{−1} ↔ S^{−1})^{−1}.

Both beside and below, interpreted as circuits, are shown in Figure 1.

Using beside, we can create a new function row which forms a linear array, cascading the circuit R a number of times, defined by

R : (A × B) → (C × A) ⇒ row R : (A × list B) → (list C × A),
row R ≡ snd wrap^{−1} ; R ; fst wrap

∨ snd apl^{−1} ; (R ↔ row R) ; fst apl.

R  R  R  R  R R R R

Figure 2: Possible circuits corresponding respectively to row R and col R.

Notice that row is defined as a disjunction; the first clause deals with the case where the second component of the domain tuple is the singleton list since row takes non-empty lists. The function col, forming a vertical column of circuits, is defined in terms of its dual function row via

R : (A × B) → (B × C ) ⇒ col R : (list A × B) → (B × list C ),
col R ≡ (row R^{−1})^{−1}.

The circuits represented by both row and col are shown in Figure 2.

The map function represents repeated parallel composition of the relation R and is defined by

R : A → B ⇒ map R : list A → list B,
map R ≡ null^{−1} ; null
∨ apl^{−1} ; [R, map R] ; apl.

Finally, the two functions rdl and rdr relate tuples of values to single values and correspond to the circuit equivalent of “reducing” (or “folding”) in functional programming. They are defined as

R : (A × B) → A ⇒ rdl R : (A × list B) → A,
rdl R ≡ row (R ; outr^{−1}) ; outr,

and

S : (A × B) → B ⇒ rdr S : (list A × B) → B,
rdr S ≡ col (S ; outl^{−1}) ; outl,

respectively. The circuits corresponding to these functions are illustrated in Figure 3.

Figure 3: An illustration of rdl R and rdr R.

3 Programming Ruby in λProlog

The higher-order logic language λProlog, developed by Nadathur and Miller [NM88], naturally supports higher-order programming features in a manner consistent with its underlying logical foundation. In what follows, we examine how to implement Ruby primitives in λProlog [LHRB94]. The syntax of λProlog is introduced informally as the section progresses.

We can define Ruby’s tuple data value in λProlog via the declaration

kind tuple type → type → type.
type :  A → B → (tuple A B).

The ‘kind’ operator creates a new type which is simply a type constructor of arity one less than the number of occurrences of the keyword ‘type’ in the declaration. In the case above, the type constructor tuple is declared taking two arguments to this new type. Function and predicate symbols are introduced via a ‘type’ declaration. The infix function symbol ‘:’ declared above takes two arbitrary types, A and B, and returns a value of type tuple A B.

Notice that λProlog is polymorphically typed and is curried in the same sense as in many functional programming languages, like Haskell, except that type signatures must be given explicitly for all function and predicate symbols. Type variables in λProlog are denoted by identifiers beginning with an upper case letter. The type of propositions (or “truth values”) is the special type ‘o’ and so the type signature of a predicate in λProlog terminates with this type. A small λProlog program defining “Peano” natural numbers, given in Figure 4, demonstrates some of these syntactic points. Natural numbers are thus represented by zero, (succ zero), (succ (succ zero)), and so forth.

We make use of the built-in list type in λProlog in order to implement the primitive

kind nat type.
type zero nat.
type succ nat → nat.
type add (tuple nat nat) → nat → o.

add (M : zero) M .

add (M : succ N ) (succ Y ) ← add (M : N ) Y .

Figure 4: The implementation of Peano natural numbers in λProlog.

relations pertaining to the Ruby list data value. Lists in λProlog are declared as

kind list type → type.
type nil list A.
type :: A → (list A) → (list A).,

where nil denotes the empty list and ‘::’ denotes ‘cons’. The λProlog predicate for list concatenation is append and the basic Ruby relations can now be implemented as shown in Figure 5.

We represent the Ruby primitives of parallel composition and converse by the respective predicates

type par (A → B → o) → (C → D → o) → (tuple A C ) → (tuple B D) → o.
type conv (A → B → o) → B → A → o.
par R S (A : C ) (B : D) ← R A B, S C D.
conv R B A ← R A B.

Several syntactic points are illustrated in this example. We can see from the type declarations of par and conv that they are both higher-order predicates taking other predicates as arguments. Predicates in λProlog may be defined as “infix” and are also curried facilitating substantial notational convenience. For instance, (R par (conv S)) denotes a valid predicate in itself and can be passed as an argument to other higher-order predicates. Therefore, we can construct goals from predicates which take arbitrarily complex relations as arguments.

The conspicuous absence of the definition of sequential composition is deliberate for a technical reason which we now spend a moment to resolve. The implementation of Ruby we present here unfortunately depends critically on the use of an extra-logical predicate flex which determines whether or not a logical variable is instantiated. The reason for using this predicate—a higher-order analogy to the predicate var found in Prolog [CM87]—is to overcome a standard problem encountered in most logic programming languages: As a consequence of the left to right evaluation strategy adopted in logic programming language implementations, whereby the leftmost unsolved goal is selected for

type id  A → A → o.
type swap (tuple A B) → (tuple B A) → o.
type outl (tuple A B) → A → o.
type outr (tuple A B) → B → o.
type fork A → (tuple A A) → o.
type lsh (tuple (tuple A B) C ) → (tuple A (tuple B C )) → o.
type rsh (tuple A (tuple B C )) → (tuple (tuple A B) C ) → o.
type app (tuple (list A) (list A)) → (list A) → o.
type apl (tuple A (list A)) → (list A) → o.
type apr (tuple (list A) A) → (list A) → o.
type wrap A → (list A) → o.
type null A → (list B) → o.

id A A. swap (A : B) (B : A). outl (A : B) A. outr (A : B) B. fork A (A : A). lsh ((A : B) : C ) (A : (B : C )). rsh (A : (B : C )) ((A : B) : C ).

apl (A : AS) BS ← append (A :: nil) AS BS.
apr (AS : A) BS ← append AS (A :: nil) BS.
app (A : B) C ← append A B C .

wrap A (A :: nil). null A nil.

Figure 5: The implementation of the most primitive Ruby relations in λProlog. resolution, certain queries can result in infinite computation. A simple example which demonstrates this undesirable property is the query

?− add (X : Y ) Z , add (X : Y ) (succ succ zero).,

assuming the previous definition of the predicate add. Since the leftmost subgoal add (X : Y ) Z can be satisfied in an infinite number of ways, the whole query results in nontermination in λProlog when all possible solutions are requested. The situation is, in theory, rectified by simply swapping the two subgoals in the conjunction. The problem can essentially be reduced to the fact that conjunction is not commutative in λProlog.

This evaluation problem particularly affects an implementation of Ruby in λProlog since we desire the ability to run queries “in reverse,” i.e., solving for logical variables in either the range or domain positions of a relation. By doing so, we satisfy the requirement that each relation in Ruby has a well defined converse. However, the fundamental Ruby primitive of sequential composition is directly affected by this problem. To see why, consider a naïve, infix implementation of sequential composition in λProlog:

type comp′ (A → B → o) → (B → C → o) → A → C → o.
comp′ R S A C ← sigma B\ (R A B, S B C ).

The λProlog primitive ‘sigma’ denotes existential quantification and the operator ‘\’ denotes infix λ-abstraction, providing a way to create predicates. Then the query

?− add comp′ (conv add) A (succ zero : succ zero).,

decomposes into the expression

?− sigma B\ (add A B, add (succ zero : succ zero) B).,

which is exactly the problematic situation we wish to avoid.

The solution is straightforward although admittedly less declarative than one might prefer. In the definition of sequential composition, we check whether the domain parameter is uninstantiated. If it is, we resolve the clauses in the composition in the reverse order to avoid slipping into an infinite computation. This results in a revised implementation of composition, given in Figure 6. The appearance of the cut ‘!’ in the first clause of comp simply avoids the second clause being attempted should the first one fail. Another point to note is that some type obscuring takes place simply to overcome the fact that a Ruby value comprises of either a number, or a tuple or list of numbers. An alternative method for tackling this difficulty would be to attach an explicit type constructor to each Ruby value to differentiate between them.

Now that we have implemented comp, we can easily implement the other Ruby higherorder functions, as illustrated in Figure 7. An attractive aspect of using λProlog to implement Ruby is the ease with which Ruby operators translate into λProlog syntax; the higher-order functions translate almost identically from their abstract Ruby definitions to their corresponding implementations in λProlog. In the next section, we look at a simple example of how to create new Ruby relations in λProlog.

type comp  (A → B → o) → (B → C → o) → A → C → o.
kind anonymous  type.
type untype  A → anonymous.
type uninstantiated A → o.
type flexible  anonymous → o.
comp R S A C ← uninstantiated A,!, sigma B\ (S B C , R A B).
comp R S A C ← sigma B\ (R A B, S B C ).
uninstantiated A ← flexible (untype A).
flexible (untype A)  ← flex A,!.
flexible (untype (A : B)) ← flexible (untype A), flexible (untype B).
flexible (untype (A :: nil)) ← flexible (untype A).
flexible (untype (A :: AS)) ← flexible (untype A), flexible (untype AS).

Figure 6: The implementation of sequential composition comp in λProlog.

4 A Simple Sorting Circuit in Ruby

In this section, we present a circuit which sorts an arbitrary, non-empty list of natural numbers. We noted earlier that we require the ability to solve logic variables in both the range and domain positions of a relation, so preserving the converse of each Ruby relation. However, the arithmetic primitives of λProlog are unable to support such a flexible computational requirement. As a consequence, we utilise the alternative definition of “Peano” natural numbers introduced in the previous section.

Two alternative methods for describing the sorting circuit have been given in the past, one by Sheeran and Jones [SJ87] and the other by Hutton [Hut92]. We implement the former presentation in this section. The sorting circuit is illustrated in Figure 8. Each node cmp is a comparison operation—taking tuples to sorted tuples—and we can see from the figure that some kind of reduction is being performed with a column of comparisons. In fact, the reduction is the converse of a reduce right, rdr^{−1}. In Ruby notation, we can define the sorting circuit sort as

sort : list nat → list nat,

sort ≡ wrap^{−1} ; wrap
∨ rdr^{−1} (apr^{−1} ; col cmp)^{−1} ; snd wrap^{−1} ; apr.

The translation of this expression into λProlog is shown in Figure 9 including a suitable definition of cmp. We can then query

?− sort (succ succ zero :: zero :: succ succ succ zero :: succ zero :: nil) B.,

type map (A → B → o) → (list A) → (list B) → o.
type beside ((tuple A B) → (tuple C D) → o) →

((tuple D E) → (tuple F G) → o) →

(tuple A (tuple B E)) → (tuple (tuple C F ) G) → o.

type below ((tuple A B) → (tuple C D) → o) →

((tuple E F ) → (tuple B H ) → o) →

(tuple (tuple A E) F ) → (tuple C (tuple D H )) → o.

type row ((tuple A B) → (tuple C A) → o) →

(tuple A (list B)) → (tuple (list C ) A) → o.

type col  ((tuple A B) → (tuple B C ) → o) →

(tuple (list A) B) → (tuple B (list C )) → o.

type rdl  ((tuple A B) → A → o) → ((tuple A (list B))) → A → o.
type rdr  ((tuple A B) → B → o) → ((tuple (list A) B)) → B → o.
map R A B ← (conv apl) comp (par R (map R)) comp apl A B.
map R A B ← (conv null) comp null A B.
beside R S A B ← rsh comp (fst R) comp lsh comp (snd S) comp rsh A B.
below R S A B ← conv ((conv R) beside (conv S)) A B.
row R A B ← (snd (conv apl)) comp (R beside (row R)) comp (fst apl) A B.
row R A B ← (snd (conv wrap)) comp R comp (fst wrap) A B.
col R A B ← conv (row (conv R)) A B.
rdl R A B ← (row (R comp (conv outr))) comp outr A B.
rdr R A B ← (col (R comp (conv outl))) comp outl A B.

Figure 7: The implementation of Ruby higher-order functions in λProlog. cmp

cmp cmp
cmp cmp cmp
cmp cmp cmp cmp

Figure 8: A possible circuit corresponding to sort.

type leq nat → nat → o.
type min (tuple nat nat) → nat → o.
type max (tuple nat nat) → nat → o.
type cmp (tuple nat nat) → (tuple nat nat) → o.
type sort (list nat) → (list nat) → o.

leq zero M .

leq (succ M ) (succ N ) ← leq M N .
min (M : N ) M ← leq M N .
min (M : N ) N ← leq N M .
max (M : N ) M ← leq N M .
max (M : N ) N ← leq M N .
cmp A B ← fork comp (min par max) A B.
sort A B ← (conv (rdr (conv ((conv apr) comp (col cmp))))) comp

(snd (conv wrap)) comp apr A B.

sort A B ← (conv wrap) comp wrap A B.

Figure 9: The implementation of sort in λProlog. to obtain the result B = (zero :: succ zero :: succ succ zero :: succ succ succ zero :: nil). We encounter a more interesting example by solving the converse of sort. The query

?− conv sort (zero :: succ zero :: succ succ zero :: succ succ succ zero :: nil) B.,

computes every permutation of the given list, corresponding to all the lists which, when sorted, result in the given list.

5 Conclusions

In this paper, a relational implementation of Ruby^{1} was developed in λProlog allowing the execution of abstract relational Ruby specifications for the first time. Moreover, the translation of a Ruby specification to its concrete representation in λProlog is natural and straightforward. The implementation of relations presented here demonstrates a previously undocumented use of λProlog, perhaps suggesting a new area for the practical application of higher-order logic programming.

The left to right computational strategy employed in λProlog does, unfortunately, hamper a completely declarative solution since we artificially affect the flow of control in a Ruby program. However, this indicates more of a problem with logic programming languages in general rather than with the Ruby implementation in particular.

As a consequence of this problem, no correctness results are given for the Ruby implementation. It would appear, though, that creating new Ruby relations using only the primitive set presented in this paper suggests that the resulting program should execute correctly.

One of the most interesting aspects of the Ruby implementation is that each relation has a well-defined converse which greatly eases the definition of some other relations. The value of the Ruby implementation presented here is not one of circuit synthesis [LP95, Hut92] but rather of the effective demonstration that a relational calculus can be programmed in λProlog. At this stage, it remains unclear, but certainly an intriguing question, whether higher-order logic programming languages can be used to implement more expressive relational languages [BdM94, ABH^{+}92, Möl92, SS88] than Ruby, particularly given the dependence of this implementation on an extra-logical feature.

Acknowledgements

I would like to extend my sincere thanks to Oege de Moor. Also, I would like to thank Geraint Jones, Graham Hutton, and Wayne Luk for their useful comments. I gratefully acknowledge the financial support of the Engineering and Physical Sciences Research Council of the United Kingdom.

1The λProlog implementation of Ruby is available via anonymous ftp from the site

ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.McPhee/ruby

References

[ABH^{+}92] C. J. Aarts, R. C. Backhouse, P. Hoogendijk, E. Voermans, and J. C. S. P. Van der Woude. A relational theory of datatypes. Available via anonymous ftp

from ftp.win.tue.nl in directory pub/math.prog.construction, September

1992.

[BdM94] R. S. Bird and O. de Moor. Relational program derivation and context-free language recognition. In A.W. Roscoe, editor, A Classical Mind: Essays dedicated to C.A.R. Hoare. Prentice Hall International, 1994.

[Bir87] R. S. Bird. An introduction to the theory of lists. In M. Broy, editor, Logic of Programming and Calculi of Discrete Design, volume 36 of NATO ASI Series F, pages 3–42. Springer–Verlag, 1987.

[CM87] W. Clocksin and C. Mellish. Programming in Prolog. Springer-Verlag, third edition, 1987.

[Hut92] G. Hutton. Between Functions and Relations in Calculating Programs. Research report, Department of Computer Science, Glasgow University, 1992.

[Hut93] G. Hutton. The Ruby Interpreter. Chalmers University of Technology, Sweden, 1993.

[Jon90] G. Jones. Designing circuits by calculation. Technical Report PRG–TR–10–90, Programming Research Group, 11 Keble Road, Oxford OX1 3QD, England, 1990.

[JS90] G. Jones and M. Sheeran. Circuit design in Ruby. In J. Staunstrup, editor, Formal Methods for VLSI Design, pages 13–70. Elsevier Science Publications, 1990.

[JS91a] G. Jones and M. Sheeran. Collecting butterflies. Technical Monograph PRG-91, University of Oxford, Programming Research Group, 1991.

[JS91b] G. Jones and M. Sheeran. Relations and refinement in circuit design. In J. Woodcock and C. Morgan, editors, Third Refinement Workshop, 1990. Springer Workshops in Computing, 1991.

[LHRB94] S. Le Huitouze, O. Ridoux, and P. Brisset. Prolog/Mali reference manual.

Available via anonymous ftp from ftp://ftp.irisa.fr/local/lande/pm,

1994.

[LP95] W. Luk and C. Pitcher. Simulation Facilities in Rebecca. Imperial College of Science, Technology, and Medicine, London, U.K., 1995.

[Möl92] B. Möller. Derivation of graph and pointer algorithms. In B. Möller, H. Partsch, and S. Schuman, editors, Formal Program Development, Proceedings of the IFIP TC2/WG2.1 State of the Art Seminar. Springer, 1992.

[NM88] G. Nadathur and D. Miller. An overview of λProlog. In R. Kowalski and K. A. Bowen, editors, Fifth International Logic Programming Conference, pages 810– 827, Seattle, U.S.A., 1988. MIT Press.

[SJ87] M. Sheeran and G. Jones. Relations + higher-order functions = hardware descriptions. In W. E. Proebster and H. Reiner, editors, Proceedings of the IEEE Comp Euro 87: VLSI and Computers, pages 303–306, Hamburg, 1987.

[SS88] G. Schmidt and T. Ströhlein. Relationen und Grafen. Springer-Verlag, 1988.