Program Transformation

10/19/13

Home
Up
Automated RE Tools
Program Transformation
Program Expansion
Functional Programming
Software Testing

 

Theory and Methods of Program Transformation

Principle Investigator, Funded by State Education Commission of China(1988~1991) , Co-Investigator National Science Foundation of China (1990~1991) .

The researches on program transformation include:

(1) The theoretical limitation of existing transformation methods:

The limitations of program transformation methods were investigated. An upper bound of efficiency gain by fold/unfolding transformation was proved. Counterexamples of transformability were obtained, which include the untransformability from linear search into binary search, untransformability from insert sorting into quick sorting.

(2) Novel methods of program transformation:

Two program transformation methods were proposed to achieve the transformation power beyond the folding/unfolding method. One method was to use infinitary logic as formal specification and to derive efficient programs from such specifications. Another method was to achieve transformation by solving program equations based on the theory of infinite orthogonal expansion of functional programs and Backus’ program algebra.

(3) The use of meta-language in transformation:

The basic idea was to provide a very high level language for the user to give human guidance to program transformation. A meta-language is designed and implemented for the purposes of the specification of transformation rules, targets, the syntax of source and target languages, and transformation strategies as well.

Related Publications:

    Zhu, H., How powerful are folding/ unfolding transformations? Journal of Functional Programming, UK, January 1994.

    Jin, L. and Zhu, H., A note on the design of a meta-language for transformational programming, Computer Research and Development, 3. 1990, (In Chinese)

    Zhu, H., Program transformation by solving equations, Journal of Computer Science and Technology, June 1991,

    Zhu, H., On the ability of Folding/Unfolding program transformation, Chinese Journal of Software, 1992.2, (In Chinese).

    Zhu, H., An orthogonal expansion approach to transformation of functional programs, Proc. of International Conference on New Generation of Computer Systems, Beijing, Apr. 1989.

    Jin, L., Zhu, H. and Xu, J., NDTPS -- An experimental meta-language transformational programming system, Proc. of International Conference on New Generation of Computer Systems, Beijing, Apr. 1989.

    Jin, L. and Zhu, H. , Experiences in meta-programming--applications in program synthesis, National Conference on AI and Science of Thinking, 1989.7. (In Chinese).

    Jin, L. and Zhu, H., A Knowledge-based system for synthesising FP programs from examples, Second National Conference on Machine Learning, 1989.7. (In Chinese).

    Zhu, H., Program transformation applied to the simulation of system failure processes, Proc. of The European Simulation Symposium, Vol. 2, pp325-329, Istanbul, Turkey, Oct. 1994. 
 

Home Automated RE Tools Program Transformation Program Expansion Functional Programming Software Testing

This site was last updated 11/04/05