The Evolution of Complexity - Abstracts.

Metacomputation of Language Hierarchies

By Robert Glück

  • Department of Computer Science
  • University of Copenhagen
  • DK-2100 Copenhagen
  • Denmark
  • Andrei Klimov
  • Keldysh Institute of Applied Mathematics
  • Russian Academy of Science
  • 125047 Moscow
  • Russia
  • Abstract:

    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 Li, to another language, say Li-1: <Transi msgi> => msgi-1; (ii) an interpreter, say Inti, of messages from one language, say Li, directly through actions in another language, say Li-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 Ln 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 Ln 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.

    1. Bjørner D., Ershov A. P., Jones N. D. (eds.), Partial Evaluation and Mixed Computation. North-Holland: Amsterdam 1988.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Turchin V. F., The Phenomenon of Science. Columbia University Press: New York 1977.
    8. Turchin V. F., The concept of a supercompiler. In: ACM TOPLAS, 8(3): 292-325, 1986.
    9. Turchin V. F., On cybernetic epistemology. In: Systems Research, 10(1): 3-28, 1993.