ñòð. 11 
From the deÂ¯nition of pushout, it follows that a model of this sketch is a
model of the sketch for natural numbers that is simultaneously a model of the
sketch for stacks whose value at the node d of Stack is the same as its value at
the node n of Nat. Models of this sketch can be identiÂ¯ed as stacks of natural
numbers. The eÂ®ect of this construction is to Â¯ll in the data parameter in the
sketch for stacks with an actual data type. Of course, this data type of natural
numbers could be replaced by any data type desired (including stacks of natural
numbers!) by replacing F : Â¡ Nat by an appropriate sketch homomorphism.
!
Although we think of this sketch as being that of stacks of natural numbers,
the pushout construction is completely symmetric and any asymmetry is imposed
by our way of looking at it. It is caused by our (quite reasonable) perception that
the node d of Stack is an input parameter and the node s represents the actual
data type.
30 The category of sketches
3.2.3 Binary trees, revisited again Here is a second example. In ES 1.3.11,
we described a sketch called BinTree and then another sketch of the same name
in ES 2.2.2. Here we describe yet another sketch we call BinTree. This third
and Â¯nal approach is fully parametrized and represents exactly what we mean
by binary trees, no more and no less. We use nodes 1, t+ , t and d. Now the only
operations we put in are empty; incl; val; left and right. We also need the cones
and cocones necessary to say that t+ = 1 + t with inclusions empty and incl and
that t+ = t Â£ d Â£ t with projections left, val and right.
Then if F : Â¡ Nat is as above and H : Â¡ BinTree is deÂ¯ned by H(e) =
! !
d, then the pushout of
 Nat
F
H
? ?
 BinTree(Nat)
BinTree
is a sketch whose models can be interpreted as binary trees of natural numbers.
This operation can be iterated. For example, we
3.2.4 Further combinators
can form the pushout

K BinTree(Nat)
G
? ?

Stack Stack(BinTree(Nat))
with Ke = t or even

L Stack(Nat)
H
? ?

BinTree BinTree(Stack(Nat))
with Le = s. Models of these types will be interpreted as stacks of binary trees of
natural numbers, respectively binary trees of stacks of natural numbers. Clearly
what is at issue here is a notion of a type having an input node and an output
node. However, things are not quite so simple, as the following example shows.
3.2.5 The basic idea of this type is that of nplace records (Pascal) or structures
(C). We leave aside here the use of variant records (which can be adequately
handled by judicious use of Â¯nite sums as C's union type shows). Another question
we do not tackle is that of parametrizing n. At this point, we make no attempt to
3.2 Parametrized data types 31
relate the sketches for twoplace and threeplace records, say, although it seems
clear that in a mature theory this will be done. Parametrizing n is discussed in
[Wagner, 1986] and [Gray, 1989].
So we describe a sketch we will call Recn . It has nodes r and d1 ; d2; : : : ; dn
and one cone
r
Â¡ @
Â¡ @
Â¡ @
Âª
Â¡ @
R
Â¢Â¢Â¢
d1 dn
As it stands, the initial model of this sketch has all values empty. It is really a
shell of a sketch. To give it content, we must Â¯ll in values for the data. To do this
we must Â¯rst recognize that the sketch has n input types and these must all be
speciÂ¯ed. This could be done in n steps, but it is more coherent to do it all at
once.
Let n denote the discrete graph with nodes e1 ; : : : ; en . There is an obvious
arrow Dn : n Â¡ Recn given by Dei = di . If, for example, we formed the pushout
!
Dn 
Recn
n
Fn
? ?

Nat Arrayn
where Fn ei = n; i = 1; : : : ; n, the resultant sketch can be evidently interpreted as
arrays of natural numbers. On the other hand, the pushout
 Rec3
D3
3
? ?

Nat +String + Real
(where we suppose that sketches for String and Real have already been deÂ¯ned)
is a sketch for threeplace records, of which the Â¯rst Â¯eld is natural numbers, the
second is strings and the third is Â°oating point reals.
The ideas in this section are discussed without the explicit use of sketches in
[Thatcher, Wagner and Wright, 1982], [Ehrig et al., 1984] and [Wagner, 1986].
3.2.6 Parametrizing operations The sketch in the upper left corner of
the pushout diagrams can contain operations. For example, let Nat+ denote the
sketch for natural numbers with an added operation + : n Â£ n Â¡ n with diagrams
!
forcing it to be addition in the initial model, and NatÂ¤ a similar sketch with an
32 The category of sketches
added operation Â¤ : n Â£ n Â¡ n forced to be multiplication there. Let Diag be
!
the sketch whose graph contains operations
Â¢ m
n Â¡!nÂ£n Â¡ !n
Â¡ Â¡
a cone with arrows pi : n Â£ n Â¡ n, i = 1; 2, to force n Â£ n to be the indicated
!
product and a diagram to force Â¢ to be the diagonal map in a model. Let BinOp
be the sketch containing n Â£ n Â¡ n and similar data making n Â£ n the indicated
!
product. BinOp is included in both Diag and in each of Nat+ and NatÂ¤ . A
pushout
N
BinOp
? ?

Diag
with N = Nat+ would add a doubling operator to Nat+ and with N = NatÂ¤
would add a squaring operator to NatÂ¤ .
3.2.7 Arithmetic One last, more speculative example will show that we have
barely begun to explore this idea. Let us suppose that we have deÂ¯ned two
sketches called Real and Complex that implement the arithmetic operations
(addition, subtraction, multiplication and division) of real and complex numbers,
respectively, as well as absolute value. While it is true that real numbers are a
special case of complex numbers and therefore do not, in principle, have to be
ñòð. 11 