Beside strict linguistic commitments of models to metamodels, documents to schemata, programs to grammars and activities to protocols, we often require or crave more flexible commitments. Some of such types of flexible commitments are well-understood and even formalised, others are considered harmful. In this paper, we make an attempt to classify these types from the language theory point of view, provide concrete examples from software language engineering for each of them and estimate usefulness and possible harm.
In software language engineering people often speak of linguistic commitment,
structural commitment or commitment to grammatical structure [
Any form of flexibility in such commitments is either not present or not considered. In this paper we propose to model it explicitly and classify its forms into several categories, varying in usefulness and the ability to lead to robust systems or to catastrophes.
The paper is organised as follows: §2 state the problem more clearly and formally. Based on that, §3 introduces three kinds of flexible language variations. Then, §4 classifies and explains all flexibly committing mappings within the framework. §5 proposes five kinds of streamlining helper mappings around the same language. §6 gives preliminary outlook at higher order manipulations such as composition of mappings,extension/restriction of them and constructing inverse functions. §7 concludes the paper.
Consider a mapping f ∶ L1 → L2 which domain is a software language L1 and which codomain is a software language L2 (they can be the same in many cases, but let us look at the general case). Following the principle of least surprise, we could assume that f is surjective and total (i.e., its image fully coincides with its codomain and its preimage with its domain) so that it maps every element of L1 to some element of L2 and that every element of L2 is reachable. By flexible linguistic commitment we will understand a situation when this expectation is violated. 3
Consider three variants based on a language L:
◇ By L we will denote a language that is strictly smaller than L: it has more
constraints and less elements. Committing to a subset of a language is in
general not that harmful and means limited applicability of the tool or a
mapping.
◇ By L^ we will denote a similarly strict superset of L which has then more
elements and less constraints. Committing to a bigger language than intended is
considered good practice in some areas that value robustness highly [
In order to stay universally applicable, we consider all definitions to be specific to the problem domain of the software language (without loss of generality, so called general purpose programming and modelling languages are assumed to belong to problem domains of Turing-complete algorithms and the everythingis-a-model paradigm respectfully). For example, unclosed tags are indicators of HÆTM L since the HTML language is meant to be processed in a soft and extremely flexible way, yet they are indicators of XËM L in most cases except for the absolutely trivial ones — say, one could argue that an XML document which is well-formed except one place with the construction like <a><b></a> is in XÆM L since it can be treated as <a><b/></a>. However, even <a><b>c</a> is already in XËM L since it has two intuitively good resolutions: <a><b/>c</a> and <a><b>c</b></a>. Yet, in a subdomain of XML that deals with exclusively empty or complex elements but never with cdata or mixed content, <a><b>c</a> would also belong to XÆML′. : : : → L2
L1 → : : : correct program wrong language o tg: : : → L2 partial applicability n i app: : : → L^2 antirobustness m
~ : : : → L2 fault introduction
mapping from
L1 → : : : non-surjectivity conservativeness perfect assumed liberality ^ L1 → : : : ~
L1 → : : : robustness
overrobustness fault recovery overrecovery fault tolerance overtolerance
semirecovery shotgun effect ilginngouraisntcice
◇ f ∶ L1 → L2 (correct program, wrong language)
Some mappings that look like having flexible linguistic commitments, are in fact (possibly) correct mappings working on a different language than expected. This kind of “flexibility” is easily fixable by correcting the specification. ◇ f ∶ L1 → L2 (partial mapping, limited applicability)
Theoretically this scenario corresponds to the notion of partial function. In practice it can be well disguised in a wrapper that extends f to L1 ∖L1 to behave like an identity function. If this is not done, this kind of flexibility is not flexible at all: it actually means that in order to use f , one needs to normalise its inputs in a more strict way than documented. In certain cases it manifests itself as a works-on-my-machine antipattern when such undocumented constraints concern configuration management and deployment details.
^ ◇ f ∶ L1 → L2 (antirobustness, ungratefulness)
If robustness (see below) is to expect less and provide more, then antirobustness is its exact opposite: the demands on the input in this case are higher than officially specified, and even when they are met, the output is ungratefully relaxed.
~ ◇ f ∶ L1 → L2 (fault introduction)
If antirobust mappings can damage syntactic conformity, this variant can also do semantic damage. Such a tool is flexible beyond reasonable, it is inherently faulty: while holding surprisingly high expectations on its inputs, it generates outputs that are outright wrong. ◇ f ∶ L1 → L2 (non-surjective mapping, conservativeness)
Concervative mappings that transform a language instance into an instance with an even stronger linguistic commitment, are not surjective. For cases of L1 = L2 they are called language reductions and represent a form of traditional normalisers without extra tolerance for input violations. Most code generators are conservative: they cover the entire input language but there exist possible target language programs that will never be generated. Classic canonical normal forms in grammarware and databases are also this kind of conservative mappings: they are proven to exist for all inputs and infer standardised provably equivalent counterparts of them. Formally, this is one of the best kinds of flexibility. ◇ f ∶ L1 → L2 (assumed / perfect)
We list this form of commitment for the sake of completeness, but in fact
it represents no flexibility: this is the standard commitment to grammatical
structure [
^ ◇ f ∶ L1 → L2 (liberality)
In mathematics, a function is under no circumstances allowed to return a value outside its codomain, but from our point of view this variant is a conceptual sibling of the conservativeness discussed above which corresponds to the lack of surjectivity. For the case of L1 = L2 this is called language extension: and it may be intentional — consider a situation of a coupled transformation sequence representing language evolution (if the language is backwards compatible, it will only contain language preserving and extending operators) or some kind of refinement/enrichment plan that recognises patterns of language use and transforms them into constructs of some more sophisticated language.
~ ◇ f ∶ L1 → L2 (fault introduction)
What classifies mappings of this category is the lack of anticipation: it was
probably meant to be a L1 → L2 mapping, and as it turns out, it does not
work correctly on unanticipated instances from L ∖ L. One of the typical
examples is refactoring engines that claim to cover some programming
language but in fact work correctly only on its subset while yielding irregular
results whenever certain concurrency or subtyping patterns are involved [
^ ◇ f ∶ L1 → L2 (robustness)
This is precisely the model of the “be conservative in what you do, be liberal
in what you expect from others”, also known as Postel’s Robustness
Principle [
^ ◇ f ∶ L1 → L2 (recovery)
A mapping that accepts slightly more than obligatory yet remains true to its
output language, represents error recovery: in the simplest case of L1 = L2
this may be the only purpose of the mapping, but it does not have to be. For
example, consider notation-parametric grammar recovery, a technique that
takes a human-written error-containing language document and a definition
of the format it is supposed to have, and yields a well-formed grammar
extracted from it [
^ ^ ◇ f ∶ L1 → L2 (tolerance)
In the terminology of negotiated mappings, the previous kind of flexible
commitment represented adaptation through adjustment; this one is
adaptation through tolerance [
^ ~ ◇ f ∶ L1 → L2 (shotgun effect)
This kind of mapping has been identified in the technological space of
internet security and named “shotgun parsing” there [
~ ◇ f ∶ L1 → L2 (overrobustness)
A few paragraphs above we reintroduced robustness as input type
contravariance and output type covariance. Overrobustness does the same but crosses
the syntax-semantics border and hence becomes dangerously ambiguous,
nondeterministic and in general error-prone. Many examples of
overrobustness leading to security bugs were given by Meredith Patterson et al. at
http://langsec.org [
~ ◇ f ∶ L1 → L2 (overrecovery)
Overrecovery is a process of applying heuristic-based fixes to semantically
incorrect language instances with the goal to return to the intended
output language. Some aggressive heuristics like parenthesis matching from
notation-parametric grammar recovery [
~ ^ ◇ f ∶ L1 → L2 (overtolerance, semirecovery)
Overtolerance is a form of harmful error handling when semantic errors in the input are presumably fixed, but the output is still not always guaranteed to be syntactically correct.
~ ~ ◇ f ∶ L1 → L2 (ignorance)
The ultimate form of flexible linguistic commitment is complete linguistic ignorance: our inputs can be broken beyond any hope of unambiguous repair, and the outputs are not much better in that respect. All lexical analysis : : : → L
L → : : :
4 canoniser id ^ L → : : :
1 normaliser
3 codifier ~ L → : : : ∼ * regulator
≃
calibrator
methods belong to this category and are still being often use due to their
extreme speed, ease of development and virtually unlimited flexibility, despite
limited expressiveness and abundant false positives and negatives. Some
migration and analysis projects of considerable size have been reported being
completed with language ignorant lexical methods [
Before we try to compose flexibly committed mappings and consider higher order combinators, we need to introduce a special subcategory of streamlining mappings that help us “get back” to L or even L whenever we deviate. In particular, we have a need for the following five (summarised on Table 2: ◇ Canoniser (4 ∶ L → L) has a normal (precise) commitment to L and produces a strict subset of it. Typically this is some kind of canonical normal form that makes sense for the chosen technological space; if it is strictly canonical, there is usually a proof of its uniqueness up to L.
^ ◇ Codifier (3 ∶ L → L) is flexible with its input because it applies certain rules for recovery which are applied until the output conforms to all expectations of L. ◇ Normaliser (1 ∶ L^ → L) implements a classic Postel-style normalisation scheme that we have briefly discussed before: it is liberal with respect to its input and conservative with respect to its output. In our formalisation it also means that 1 ≡ 4 ○ 3 (a normaliser is equivalent to the superposition of a codifier and a canoniser), and indeed, any normaliser can be conceptually studied as a composition of two parts implementing the liberality and the conservativeness accordingly. We will consider superposition of flexibly committing functions in the next section in more detail. ◇ Calibrators (≃ ∶ L~ → L) and regulators (*∼ ∶ L~ → L) can be decomposed similarly in various ways, but the key when considering them is remembering that the main distinction between L^ and L~ is that L^ ∖ L is anticipated and L~ ∖ L is not. Hence, when something is not anticipated, it cannot be casually accounted for by an automated streamliner. In practice developing calibrators and regulators requires the same steps as developing codifiers and normalisers, with additional effort dedicated to testing and documenting recovery heuristics, which are usually unreliable.
L′ → : : : ie dL → : : : d lp n p coL^′ → : : : ;a se f
L~′ → : : :
: : : → L f ○ g, if L ⊆ L′ f ○ 4 ○ g f ○ g f ○ g f ○ g g; applied first : : : → L : : : → L^ f ○ 4 ○ g f ○ 1 ○ g
~ : : : → L f ○ *∼ ○ g f ○ g f ○ g f ○ g
f ○ 3 ○ g f ○ ≃ ○ g f ○ g, if L^ ⊆ L′ f ○ ≃ ○ g
^ f ○ 3 ○ g f ○ 3 ○ g f ○ ≃ ○ g For every possible combination of input and output types (strictly speaking, for any input type since output type is irrelevant), a restriction on L is defined straightforwardly as a function which returns whatever the original function would have returned, for all inputs from the restricted set, and is underfined otherwise. An extension of a function deliberately committing to a subset of the intended language, on the other hand, cannot be defined in a general fashion. Hence, for any f which preimage is L, L^ or L~, we get a f SL for free, but the extension f SL for f ∶ L → L′ is, generally speaking, unknown.
A more interesting observation is that restriction can affect the flexibility of the linguistic commitment to the output language as well: for example, if f ∶ L^1 → L2, then f SL1 ∶ L → L2 or possibly f SL1 ∶ L → L2. This has bad consequences on calculating inverses of restrictions. Due to the nature of our formalisation that considers preimages and images instead of domains and codomains, all functions that map between L1, L1, L^1 and L2, L2, L^2, have straightforward inverse mappings. Their non-unique existence is guaranteed (the proof is a direct consequence of the definitions of a premiga and ^ ^ an image). For example, for any f ∶ L1 → L2 there is at least one f −1 ∶ L2 → L1. Inverses of restrictions can be more desirable, but less reliable, since there is no guarantee that for an arbitrary f ∶ L^1 → L^2, the image of f SL1 (L1) ∩ L2 ≠ ∅.
However, the following compositions are also universally safe (variations of L2 correspond to variations of L in the table): ⊚ ∶ (L2 → L3) → (L1 → L2) → (L1 → L3)
^ ⊚ ∶ (L2 → L3) → (L1 → L2) → (L1 → L3)
~ ⊚ ∶ (L2 → L3) → (L1 → L2) → (L1 → L3)
^ ⊚ ∶ (L2 → L3) → (L1 → L2) → (L1 → L3)
~ ⊚ ∶ (L2 → L3) → (L1 → L2) → (L1 → L3)
The result type of such compositions given above is a possible overapproximation, because technically we combine g with f SL2 or f SL2 , not with f itself, so it is possible for f ⊚ g with the codomain L3 to have image L3.
The rest often require streamliners, with two special cases stemming from the fact that in our notation L^ expresses any superset of L and not a particular one. Thus, it can be the case that L2 ⊆ L′2 and then ⊚ ∶ (L′2 → L3) → (L1 → L2) → (L1 → L3) is expressible with a simple superposition: f ⊚ g = f ○ g, but otherwise we need an L′2-canoniser to glue them together: f ⊚ g = f ○ 4 ○ g. Similarly to the safe case discussed above, the image of such composition can be L3 if L2 ≠ L′2. 7
This paper is an attempt to investigate Postel’s Robustness Principle (“be
conservative in what you do, be liberal in what you expect from others”) [