Orthogonal Program Expansion – A Theory of Functional Programming and its Applications (1988~1990, 1991~ 1993): funded by State Education Commission of China.

In these two projects, the theory of program orthogonal expansion proposed in my Ph.D. thesis was further developed, and applied to the proof of program properties, program transformations and program synthesis from examples. The main results of the researches include:

  1. A theory of program orthogonal expansion, which generalized Backus’ expansion theorems so that any program can be expanded on any complete set of orthogonal systems of functions. Theorems about the conditions that a program can be equivalently expressed as orthogonal expansions (i.e. the least upper bound of a set of orthogonal functions composed with coefficients functions) were proved. Rules for deriving orthogonal expansions of recursive functions were proposed and their correctness were proved.

  2. Applications of orthogonal expansions to program transformation were investigated. A method of program transformation by solving program equations was proposed.

  3. Application of orthogonal expansions to program synthesis from input/output examples were studied. A method of knowledge-based program synthesis is proposed. A synthesis system was developed. (See also A. Huchinson, Algorithmic Learning, Oxford University Press, 1994)

Related Publications

Zhu, H., Orthogonal decomposition in Complete Partially Ordered Sets, Chinese Journal of Computer Science, 1991.2, (In Chinese).

Zhu, H. and Jin, L., A knowledge-based system to synthesize FP programs from examples, Proc. of EPIA'89, Lecture Notes in Computer Science, Vol. 390, 1989,

Zhu, H. and Jin, L., A knowledge-based approach to program synthesis from examples, Journal of Computer Science and Technology, January 1991.

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

Zhu, H. A theory of program expansion, Scientia Sinica, (Science in China) Series A, Dec. 1988.

Zhu, H., Some mathematical properties of the functional programming language FP, Journal of Computer Science and Technology, Vol. 2. No.3, July, 1987.

Zhu, H. and Jin, L., Derivation of efficient programs from specifications in first order infinitary logic, Proc. of ICYCS'91, Beijing, 1991.

Zhu, H, Jin, L., Meta-programming ---- Applications to program synthesis from examples, Proc. of ISYCP, 1989.

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).

Back to Hong Zhu's Home Page