Semi-inversion of Guarded Equations

  • Torben Æ Mogensen
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3676)


An inverse of a program is a program that takes the output of the original program and produces its input. A semi-inverse of a program is a program that takes some of the input and some of the output of the original program and produces the remaining input and output. Inversion is, hence, a special case of semi-inversion.

We propose a method for inverting and semi-inverting programs written as guarded equations. The semi-inversion process is divided into four phases: Translation of equations into a relational form, refining operators, determining evaluation order for each equation of the semi-inverted functions and translation of semi-inverted functions back to the original syntax. In cases where the method fails to semi-invert a program, it can suggest which additional parts of the programs input or output are needed to make it work.


Partial Function Relational Form Partial Evaluation Original Program Functional Language 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Bondorf, A.: Improving binding times without explicit CPS-conversion. In: ACM Conference on Lisp and Functional Programming, pp. 1–10. ACM Press, New York (1992)CrossRefGoogle Scholar
  2. 2.
    Dijkstra, E.W.: Program inversion. In: Bauer, F.L., Broy, M. (eds.) Program Construction: International Summer School. LNCS, vol. 69, pp. 54–57. Springer, Heidelberg (1978)Google Scholar
  3. 3.
    Glück, R.: Jones optimality, binding-time improvements, and the strength of program specializers. In: Proceedings of the Asian Symposium on Partial Evaluation and Semantics-Based Program Manipulation, pp. 9–19. ACM Press, New York (2002)CrossRefGoogle Scholar
  4. 4.
    Glück, R., Kawabe, M.: Derivation of deterministic inverse programs based on LR parsing. In: Kameyama, Y., Stuckey, P.J. (eds.) FLOPS 2004. LNCS, vol. 2998, pp. 291–306. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  5. 5.
    Gries, D.: The Science of Programming. In: Inverting Programs. Texts and Monographs in Computer Science, ch. 21, pp. 265–274. Springer, Heidelberg (1981)Google Scholar
  6. 6.
    Holst, C.K., Hughes, J.: Towards binding-time improvement for free. In: [7], pp. 83–100 (1991)Google Scholar
  7. 7.
    Jones, S.L.P., Hutton, G., Holst, C.K. (eds.): Functional Programming, Glasgow 1990. Workshops in Computing. Springer, Heidelberg (1991)Google Scholar
  8. 8.
    Knapen, E.: Relational programming, program inversion and the derivation of parsing algorithms. Master’s thesis, Eindhoven University of Technology (1993)Google Scholar
  9. 9.
    Launchbury, J.: Projection Factorisations in Partial Evaluation. In: Distinguished Dissertations in Computer Science. Cambridge University Press, Cambridge (1991)Google Scholar
  10. 10.
    Launchbury, J.: Projections for specialisation. In: Bjørner, D., Ershov, A.P., Jones, N.D. (eds.) Partial Evaluation and Mixed Computation, pp. 299–315. North-Holland, Amsterdam (1988)Google Scholar
  11. 11.
    Mu, S.-C., Hu, Z., Takeichi, M.: An injective language for reversible computation. In: Kozen, D. (ed.) MPC 2004. LNCS, vol. 3125, pp. 289–313. Springer, Heidelberg (2004)CrossRefGoogle Scholar
  12. 12.
    Romanenko, A.Y.: The generation of inverse functions in Refal. In: Bjørner, D., Ershov, A.P., Jones, N.D. (eds.) Partial Evaluation and Mixed Computation, pp. 427–444. North-Holland, Amsterdam (1988)Google Scholar
  13. 13.
    Sterling, L., Shapiro, E.: The Art of Prolog, 2nd edn. MIT Press, Cambridge (1994)zbMATHGoogle Scholar
  14. 14.
    Turchin, V.F.: The use of metasystem transition in theorem proving and program optimization. In: de Bakker, J.W., van Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 645–657. Springer, Heidelberg (1980)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Torben Æ Mogensen
    • 1
  1. 1.DIKUUniversity of CopenhagenDenmark

Personalised recommendations