Application of metasystem transition to function inversion and transformation

ABSTRACT

We proved by construction an application considered theoretically by Turchin [7] that self-application of metacomputation will allow the automatic construction of inverse algorithms, in particular the algorithm of binary subtraction from the algorithm of binary addition. Further, we will present results concerning the algorithmic construction of an efficient pattern matcher, which leads to the Knuth, Morris and Pratt algorithm. These results were achieved with the first working model of a self-applicable supercompiler system, implementing the concept of metacomputation.

REFERENCES

• 1: BjZrner D., Ershov A.P., Jones N.D. (eds.), Partial Evaluation and Mixed Computation. Proceedings of the iFIP TC2 Workshop, North-Holland, 1988.
• 2: Charles Consel , Olivier Danvy, Partial evaluation of pattern matching in strings, Information Processing Letters, v.30 n.2, p.79-86, January 1989 [doi>10.1016/0020-0190(89)90113-0]
• 3: Futamura Y., Partial Evaluation of Computation Process - An Approach to a Compiler-Compiler. in: Systems, Computers, Controls, 2(5), pp. 45-50, 1971.
• 4: Futamura Y., Nogi K., Generalized Partial Evaluation. in: {1}, pp. 133-151, 1988.
• 5: Neil D. Jones , Peter Sestoft , Harald Sondergaard, An experiment in partial evaluation: the generation of a compiler generator, Proc. of the first international conference on Rewriting techniques and applications, p.124-140, December 1985, Dijon, France
• 6: Knuth D.E., Morris J.H., Pratt V.R., Fast Pattern Matching in Strings. In: SIAM journal of Computer, 6(2), pp. 323- 350, 1977.
• 7: Turchin V.F., Equivalent Transformation of Recursive Functions Defined in Refal. In: Trudy Vsesoyuzn. Simpos Teoria Yazykov i Methody Progr., pp. 31.42, AlushtaoKiew, 1972 (in Russian).
• 8: Turchin V.F. (ed.), Basic Refal and its Implementation on Computers. GOSSTROI SSSR, TsNIPIASS, Moscow, 1977 (in Russian).
• 9: Valentin F. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.3, p.292-325, July 1986 [doi>10.1145/5956.5957]
• 10: Turchin V.F., The Algorithm of Generalization in the Supercompiler. In: {1}, pp. 531-549, 1988.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Computer arithmetic

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory, Verification