Balisage Paper: Extension of the type/token distinction to document structure

Peirce's account

Peirce's account of the distinction runs as follows [Peirce 1906] pp. 423-4:

As may be seen, Peirce's distinction stresses the opposition between the concrete physical existence of the token and the abstract nature (and, in Peirce's terminology, the non-existence!) of the type. He also establishes the usage that tokens can be said to instantiate types.^[1] To be a token, in fact, is to instantiate a type (and vice versa); there are no tokens without associated types.^[2]

Other usages of type and token

There are a number of other usages of the terms type and token which differ from Peirce's, and should not be confused with it.

Peirce's types have nothing to do with Bertrand Russell's logical types, which are classes or orders of sets and belong to a completely different story. The (data) types of programming languages and XML schema languages are similarly distinct concepts.

Some common usages (not only in computing, but particularly visible there), employ an opposition between token and type similar to Peirce's, but divorce it more or less completely from the opposition of concrete physical existence and abstraction; any instance of a particular string (more precisely, of a particular string type) is taken as a token of that type. In a related usage, token is also taken simply as one item in the results produced by a tokenizer, whose task it is to divide a sequence of characters into units. A more careful usage reserves the word token for concrete physical phenomena and uses the term occurrence for what common computing terminology calls tokens, reserving token for particular physical realizations of the type.^[3]

In this paper, we do distinguish between tokens, types, and occurrences of types. The latter will be encountered mainly in what we will call compound types, for example sets or sequences of (other) types. In those cases, the components of the compound type are implicitly understood to be occurrences of types, so we will not say, for example, sequence of occurrences of types (which would be somewhat pleonastic), but simply sequence of types.

Related distinctions

The type/token distinction is sometimes met with under different names (and those who use those different ways of speaking about things may or may not agree with our claim that what they are speaking about is in fact the type/token distinction). In this section we mention two of the more important, without being able to discuss them in the detail they deserve.

Nelson Goodman describes the constituents of a notational system thus [Goodman 1976], p. 131:

Goodman speaks here of characters being classes of inscriptions, but he makes clear elsewhere that this is merely a convenient way of expressing himself and is not intended to commit him to the existence of classes or sets: in a more careful formulation, presumably, Goodman would say that characters are the mereological sums of their inscriptions: complex individuals (entities) made of the individual inscriptions of the character.^[4]

We take Goodman's opposition between inscription and character to be the same as, or very similar to, Peirce's opposition of token and type. The properties Goodman ascribes to characters and inscriptions are precisely those of types and tokens. Goodman makes explicit some properties of types and tokens which are part of the usual view of the matter but are not explicit in the passage from Peirce quoted above. In particular:

The full exploitation of Goodman's work for illumination of the type/token distinction remains a desideratum for the future.

The type/token distinction also resembles the distinction made by most phonologists between specific individual sounds or configurations of the vocal organs (phones) and the distinctive units of phonology (phonemes).^[6] Goodman's remark about the equivalence (at least for syntactic purposes) of the different tokens of a type recalls the occasional supposition by phonologists that different realizations of the same phoneme may be interchanged freely without affecting the acceptability of the utterance.

The phone/phoneme distinction allows linguists to treat sounds in different utterances (or at different locations in the same utterance) as identical for certain purposes, and distinct for others. It thus serves a function analogous to the one we noted above for the type/token distinction. Like types, phonemes are instantiated by physical phenomena which can vary widely in detail. Like types, they are taken to be disjoint from each other (they serve, in a common description, as contrastive units, which we take to mean that one of their functions is to be distinct from each other).

Much of the machinery of phonology can usefully be applied to types and tokens. Just as phonemes can almost always be realized by a number of different phonetic variants (allophones), with the choice of allophone often determined by the phonetic environment, so also do the tokens of a type frequently fall into subclasses which may vary depending on environment or other factors. Conventionally minimal pairs (pairs of words which differ only in a single sound) are taken as evidence for distinctions among phonemes; similarly minimal pairs can be used to distinguish different types from each other. And just as phonologists have found it helpful to define phonemes in terms of sets of minimally distinctive features, so also it may prove helpful to define types in terms of distinctive features. It is interesting to note that defining types in terms of finite sets of distinctive features guarantees that any type so defined will satisfy Goodman's requirement that it be finitely differentiated from other types.

Types and tokens at different levels

One further topic should be discussed at least briefly before we proceed with our elaboration of the type/token distinction. As the title of the paper indicates, its central idea is that the type/token distinction can be applied not just to words and characters, but also to higher-level document structures. Since document structures are generally understood to have internal structure and to nest within other document structures, we must necessarily consider both types and tokens as capable of nesting and having internal structure.

This appears not to be the most common view of the type/token distinction. The distinction is sometimes applied at the character level, and sometimes at the type level, but not (usually) at both levels at the same time. In the passage quoted above, for example, Peirce identifies types and tokens only as ways of looking at words, without mentioning their relation to types or tokens at lower or higher levels of analysis.

It is not unknown, however, to apply the type/token distinction at multiple levels.

Goodman, for example, explicitly applies the term character things which may contain other characters, and expects this to be the normal case: Any symbol scheme consists of characters, usually with modes of combining them to form others. So in Goodman's sense, the initial A of ALGOL is a character, and so is ALGOL itself. The first sentence of the Algol report can be regarded as a character in the same sense, as can the paragraph in which it occurs, and after a few more combinations at higher and higher levels, the Algol 60 report itself as a whole. (Or, in the terminology we prefer as less confusing to users of Unicode, the initial A of ALGOL, the word ALGOL itself, and so on, are all types at various levels, instantiated by tokens at similarly various levels.)

The linguistic concept of phone and phoneme does not allow phonemes to nest. But the idea of phonetic/phonemic contrasts has been widely applied in other areas of linguistics, perhaps most widely and visibly by the linguist Kenneth L. Pike. Pike generalized the distinction between phonetic and phonemic phenomena, coining the terms emic and etic, and applied the distinction not only to other areas of linguistic analysis but also to virtually all of human behavior [Pike 1967]. The emic/etic distinction has apparently achieved wide currency in some schools of anthropology and sociology. And when both phonological and other linguistic levels are analysed in terms of emic and etic units, it is unavoidable that some of those units will have internal structure and nest in other emic and etic units.

Finally, recent discussions of types and tokens by the philosopher Linda Wetzel have devoted significant attention to questions that arise when considering tokens, or types, at multiple levels. If we consider any concrete realization of the sentence from the Algol report quoted above (i.e. any token of the sentence), then it is easy enough to see that the sentence token can be decomposed into word tokens, and the word tokens into character tokens. But of what, asks Wetzel, is the sentence type composed? It cannot be composed of word tokens, because as a type it is abstract. It cannot be composed simply of word types, because the sentence is 28 words long, but there are only 21 word types available for the job. Wetzel concludes, after painstaking investigation of alternatives, arguments, and counter-arguments, that the sentence type consists of 28 occurrences of word types. She elucidates the concept of occurrence with the aid of an appeal to sequences, and then generalizes it to situations where the parts of a larger whole are not arranged in sequences.

Another issue raised by Wetzel may be worth mentioning. In cases where the containing string is written out in full, each token in the string will (as always) constitute a different occurrence of a type, and each occurrence of a type will be signaled by a different token. This has led some philosophers to doubt the utility of any distinction between occurrences and tokens. How, they ask, can a type occur multiple times in a sequence (or other structure) unless it is instantiated by a different token for each occurrence? The question takes on a particular interest in the context of SGML and XML, where multiple references to an entity can in fact easily produce multiple occurrences of a type from a single token. Macros as handled by the C pre-processor have the same effect. Examples outside of mechanical systems appear to be less common, but they do exist. In printed versions of ballads and other songs with refrains, it is not uncommon for only the first occurrence of the refrain to be printed in full, while others are indicated only by the word Refrain, which functions here as a sort of macro or entity reference. And repeat-marks in music seem to make the note tokens so marked correspond to multiple note-type occurrences in the music.

Basic concepts

The basic concepts of the model we propose can be summarized as follows.

The key concepts of the model are those of token and of type, which are defined partly in opposition to each other.

But not all physical marks are tokens: a mark is recognized as a token if and only if it is recognized as being a token of some type.^[8] The recognition of tokens as instances of particular types requires a competent observer (e.g., a human reader, in the case of conventional writing), but we do not here address the perceptual and psychological processes by which humans recognize a token as being of a particular type.

Alternatively (in the spirit of Goodman's calculus of individuals) they may be regarded as collective individuals whose constituent parts are tokens.^[9]

In either case, we will say that tokens instantiate types, and that types are normally conveyed or communicated by being instantiated by tokens.

It must instantiate at least one type, because a mark that does not instantiate a type is not a token. And it cannot instantiate more than one type, because types are mutually disjoint and no token can be of multiple types. (At least, this is the simplest way to start out. But see further the discussion of type repertoires and type systems below.)

In more formal terms: types have identity, but we specify no other properties for them.

abstract sig Type {}

Tokens map to types. The only salient property of a token, and thus the only property we model, is the identity of the type it instantiates.^[10]

abstract sig Token {
 type : Type
}

The declaration type : Type indicates that the type relation links each Token to exactly one Type. It follows, then, that:

Multiple levels of types and tokens

As noted above, earlier authors have contemplated types and tokens which have internal structure and nest; here we take up that principle and formalize it.

Simple examples are the characters of the Latin alphabet and punctuation marks.

Formally: basic types are a kind of type, and basic tokens are a kind of token. The types to which basic tokens map will normally be basic types, but for reasons clarified below this is not required by the model.

sig Basic_Type extends Type {}
sig Basic_Token extends Token {}

We refer to the lower-level types or tokens as the constituents of the higher-level one of which they form a part.

Because in written documents compound tokens typically occupy a discernible and possibly large region of the text carrier, we call them regions. Because compound types are, in the usual case, structural units of a kind familiar to any user of SGML or XML for document markup, we refer to them as S_Units.

Regions can be decomposed into subregions and S_Units have children. It proves useful to postulate that S_Units also have a set of property-value pairs, and are labeled as to their type or (to avoid overloading the word type yet again) their kind.

Formally: compound types and tokens are subsets, respectively, of types and tokens generally. They have subordinate types and tokens, referred to as their children and subregions, respectively.

abstract sig Region extends Token {
  subregions : set Token
}{ 
  type in S_Unit
  type.children = subregions.@type
}
abstract sig S_Unit extends Type {
  kind : lone Kind,
  props : set AVPair,
  children : set Type
}

Simple examples of sequence include the aggregation of sequences of character tokens to form word tokens and similarly the aggregation of sequences of character types to form word types. At higher levels, the aggregation of paragraphs to form a chapter, or of chapters to form a novel, provide further examples. Sets and bags are less frequent in documentary applications, but not unknown; they occur whenever it is meaningless or misleading to ask about the order of the children, or when the children are represented in some sequence of tokens which is explicitly stated to carry no significance.

Formally:

sig Ordered_Region extends Region {
 sub_seq : seq Token
}{
  elems[sub_seq] = subregions
  type in Ordered_S_Unit
  type.ch_seq = sub_seq.@type
}
sig Ordered_S_Unit extends S_Unit {
  ch_seq : seq Type
}{
  elems[ch_seq] = children
}

The declaration sub_seq : seq Token says that each Ordered_Region is associated with a sequence of (sub)tokens; ch_seq : seq Type says the analogous thing for Ordered_S_Unites. The declarations elems[sub_seq] = subregions and elems[ch_seq] = children specify that the elements of those sequence are precisely the constituents of the compound object. The declaration type in Ordered_S_Unit requires that any ordered region instantiate an ordered type.^[11] The declaration type.ch_seq = sub_seq.@type specifies that for any ordered region R, the children of R's type are the types of R's subregions.

Next, we turn to unordered types and tokens (bags and sets):

abstract sig Unordered_Region extends Region {}{
  type in Unordered_S_Unit
}
abstract sig Unordered_S_Unit extends S_Unit {}

Note that those definitions make Ordered_S_Unit and Unordered_S_Unit disjoint from each other, as expected (an S_Unit cannot be both ordered and unordered).

Types and tokens whose constituents are unordered have either set structure or bag structure. Set-structured tokens map to set-structured types (and ditto for those with bag structure). Bag-structured types and tokens keep track of the number of occurrences of each constituent (modeled here by the functions sub_counts and ch_counts, which map from constituents to natural numbers.

abstract sig Set_Structured_Region extends Unordered_Region {}{
  type in Set_Structured_S_Unit
}
abstract sig Set_Structured_S_Unit extends Unordered_S_Unit {}

abstract sig Bag_Structured_Region extends Unordered_Region {
  sub_counts : subregions -> Natural_number
}{
  type in Bag_Structured_S_Unit
}
abstract sig Bag_Structured_S_Unit extends Unordered_S_Unit {
  ch_counts : children -> Natural_number
}

Normally, basic tokens instantiate basic types; exceptions are the disjunctive and conjunctive types defined below. Only compound tokens can successfully instantiate most compound types, because of the rule type.children = subregions.@type in the declaration of regions. Essentially, this requires a kind of compositionality: if the type of a region has child types, then those child types must be instantiated by subregions of the region. Since basic tokens have no subregions, they cannot satisfy this constraint.

Several observations can be made about compound types and tokens.

The lowest level of compound, consisting of a sequence of basic tokens (or types), is frequently an object of special interest. (For example, the text node of the XPath data model is characterized precisely by being a sequence of Unicode characters [here taken as basic] uninterrupted by markup and without any further properties or structure.)^[12]

Basic tokens consist of marks on a text-bearing writing medium; compound tokens consist of collections of other tokens (basic or compound); not infrequently, these are physically proximate and so compound tokens may be identified with regions of the text carrier.^[13]

The compound types instantiated by compound tokens are not infrequently structural units of the kind identified by elements and attributes in standard markup practice.

Among the compound tokens, the document itself is an important edge case, and similarly the text among compound types.^[14]

Finally, some ancillary declarations are needed for the Kind, AVPair, and Natural_number objects appealed to in some of the earlier declarations.

The signatures Kind and AVPair serve purposes analogous to the generic identifiers and attribute-value pairs of SGML and related markup languages. We do not analyse them further. Natural_number is just an integer greater than zero.

abstract sig Kind {}

sig AVPair {
  att_name : Kind,
  att_value : Type
}

sig Natural_number {
  theNumber : Int
}{
  theNumber > 0
}

Ambiguity: disjunction, and conjunction

Our model of the type/token distinction goes beyond the conventional view in a second way: we postulate disjunctive and conjunctive types, to address some cases which are otherwise difficult to handle.

In some documents it may be difficult to say just what type is instantiated by some tokens (e.g., if the document is difficult to read). For example, consider the following extract from a manuscript of Ludwig Wittgenstein:

Figure 1

A word in Wittgenstein's Geheimschrift (Item 118, page 8v).

Transcribers not yet aware that this word is written in Wittgenstein's so-called secret writing (in which A is substituted for Z, B for Y, etc., and vice versa) might have difficulty deciphering the token. Transcriber A might render the word as munonyqi, transcriber B as wunouyqi. Both might accept the other's transcription as just as likely as their own. How, in this case, should a neutral observer whose knowledge of the original is derived only from the transcription, or a transcriber uncertain how to read the philosopher's handwriting, characterize the first letter of this word? Is it a w or an m?

We could of course simply insist that each token be mapped to a unique type as a matter of principle, thus forcing a choice among the possibilities: m or w. But it might provide a more accurate depiction of the state of affairs if we specified not that the first letter is an m, or that it is a w, but specified instead that it is either the one or the other.^[15]

So we extend the model given above by adding the possibility of disjunctive types.

In Alloy notation:

sig Disjunctive_Type extends S_Unit {}{
  kind = Disjunction
  some children
}
one sig Disjunction extends Kind {}

Here again, note that Disjunctive_Type is disjoint from both Ordered_S_Unit and Unordered_S_Unit.

Note that the mapping from token to type remains a function: each token continues to map to a single type, but in cases of uncertainty, that single type simply happens to be a disjunction. Formally, this state of affairs could be handled instead by making the token/type mapping a relation, through which any given token would map to one or more types; we choose to reify the notion of disjunction for reasons which should become clear shortly.

Uncertainty is not the only reason one might wish to map a given token to more than one type. Just as ambiguity in utterance may be either unintentional or intentional, so also polyvalence in the token/type mapping may reflect either the uncertainty of the reader or the purposeful choice of the creator. Some of the most entertaining instances of this phenomenon are the mixtures of calligraphy and puzzle creation known as ambigrams or inversions, in which the marks of a document are carefully constructed to instantiate not single types but two or even more. In the following example, the marks can be read either clockwise or counter-clockwise as tokens of the word infinity.^[16]

Figure 2

An inversion. © Scott Kim, scottkim.com. Reproduced by permission.

We extend the model, therefore, to include conjunctive types.

In Alloy:

sig Conjunctive_Type extends S_Unit {}{
  kind = Conjunction
  some children
}
one sig Conjunction extends Kind {}

As with disjunctive types, no additional fields or machinery are needed: it suffices to classify a type as disjunctive or conjunctive to make clear how the constituent types relate to each other and to the tokens of the type.^[17]

Other cases of willed polyvalence include acrostics (in which individual basic tokens form parts of two compound tokens, not just one) and some simple forms of coded communication (e.g., documents where the intended recipient must read every other word, or every other line, to glean the secret message). These deviate from the normal case in which each token (except the top-most, namely the document) is a constituent of just one higher-level token (and similarly, with appropriate adjustments, for types). In the normal case, that is, both tokens and the types they instantiate can typically be arranged in a simple hierarchy. Violations of this hierarchical assumption do not require a special kind of type like a disjunction or a conjunction; it suffices to avoid requiring that no two tokens, and not two types, share any constituents.

It is not hard to imagine (though it is beyond our ability to provide plausible examples of) cases in which the marks of a document are clearly intended to be polyvalent and thus appear to require a mapping to some conjunctive type, but in which it is not clear which conjunctive type is called for. In such situations, the tokens in question may be regarded as instantiating a disjunctive type whose constituents are conjunctive types. One might also imagine an inversion in which the identity of one conjoined type is certain but the other is not: that may be described by mapping the token in question to a conjunctive type whose constituents are a normal type (compound or basic) and a disjunctive type.