By **Robert Glück **

This contribution investigates the manipulation of formal language hierarchies,
a prerequisite for overcoming the computational complexity of *linguistic
modeling* [7]. We derive the basic tasks for metacomputation by a systematic
analysis of language hierarchies and show that in order to fully support formal
linguistic modeling in the computer the following transformation have to be
performed effectively and efficiently: flattening translator and interpreter
hierarchies, converting translators into interpreters and vice versa.

It is surprising, that only one case (3a), the conversion of interpreters into translators, has been studied in computer science [1,6]. We argue that the full variety of language hierarchies should be considered in order to achieve the full flexibility of linguistic modeling. We hope that this exposition contributes to a systematic understanding of linguistic modeling both in cybernetics and computer science. It is a continuation of our work on metacomputation [2-5], inspired by Turchin's pioneering works [7,8].

One of the defining features of modern science is the use of *linguistic
models *[7]. *Computer science* is laying the foundations and
developing the research paradigm and scientific methods for the exploration of
*formal linguistic modeling*. Modeling by means of formal language usually
involves the creation of *language hierarchies* [9].

The goal of *metacomputation* (see e.g. [8,4]) is to derive new, more
compact language definitions from arbitrary linguistic hierarchies. Let us
denote the process of performing metacomputation by `Mc`. In order to
express that `Mc` is one level higher than ordinary computation, we will
move the metacomputed expression downwards (see below).

We know of exactly two forms of linguistic definitions: (i) a
*translator*, say `Transi`, of messages from one language, say
L*i*, to another language, say L*i-*1: `<Transi`
`msgi> `=>` msgi-1`; (ii) an *interpreter*, say
`Inti`, of messages from one language, say L*i*, directly through
actions in another language, say L*i*-1: `<Inti` `(msgi,`
`in)> `=>` out`. Each level in a hierarchy is either
translative or interpretive.

We distinguish four cases of metacomputation of language hierarchies.

1. **Translator hierarchy**. The goal of metacomputation is to derive a new
translator `Trans` by *composition* of the translators
`Trans1` ... `Transn`, where `Trans` is a translator from
L*n* to L0.

` <Mc _______________________________________> `=>`
Trans`

` <Trans1 <Trans2 ... <Transn msgn> ...>>`

2. **Interpreter hierarchy**. The goal of metacomputation is to derive a new
interpreter `Int` by *multi-level specialization* of the
interpreters `Int1` ... `Intn`, where `Int` is an
interpreter of L*n* in L0.

` <Mc _______________________________________________>
`=>` Int`

` <Int1` `(Int2,` `(Int3, ... (Intn,` `(msgn,
in)) ...))>`

3. **Conversion to dual definition**. The goal of metacomputation is the
conversion of one form of definition to its dual form.

3a. Converting an interpreter to a translator. 3b. Converting a translator to an interpreter.

4. **General language hierarchy**. The goal of metacomputation is to convert
a mixture of translators and interpreters into one of the two definition forms:
a translator or an interpreter.

- Bjørner D., Ershov A. P., Jones N. D. (eds.),
*Partial Evaluation and Mixed Computation*. North-Holland: Amsterdam 1988. - Glück R., The requirement of identical variety. In:
*Proceedings of the 13th International Congress on Cybernetics*. (Namur, Belgium). 524 529, International Association for Cybernetics 1992. - Glück R., Klimov A. V., Occam's razor in metacomputation: the notion of a perfect process tree. In: Cousot P., Falaschi M., Filè G., Rauzy A. (eds.),
*Static Analysis. Proceedings*. (Padova, Italy). Lecture Notes in Computer Science, Vol. 724, 112-123, Springer-Verlag 1993. - Glück R., Klimov A. V., Metacomputation as a tool for formal linguistic modeling. In: Trappl R. (ed.),
*Cybernetics and Systems '94*. Vol. 2, 1563 1570, World Scientific: Singapore 1994. - Glück R., Klimov A. V., Metasystem transition schemes in computer science and mathematics. In:
*World Futures: the Journal of General Evolution*: (to appear), 1995. - Jones N. D., Gomard C. K., Sestoft P.,
*Partial Evaluation and Automatic Program Generation.*Prentice Hall International Series in Computer Science. Prentice Hall: New York, London, Toronto 1993. - Turchin V. F.,
*The Phenomenon of Science.*Columbia University Press: New York 1977. - Turchin V. F., The concept of a supercompiler. In:
*ACM TOPLAS*, 8(3): 292-325, 1986. - Turchin V. F., On cybernetic epistemology. In:
*Systems Research*, 10(1): 3-28, 1993.