zbMATH — the first resource for mathematics

A residualizing semantics for the partial evaluation of functional logic programs. (English) Zbl 1042.68023
Recent proposals for multi-paradigm declarative programming combine the most important features of functional, logic and concurrent programming into a single framework. The operational semantics of these languages is usually based on a combination of narrowing and residuation. In this paper, we introduce a non-standard, residualizing semantics for multi-paradigm declarative programs and prove its equivalence with a standard operational semantics. Our residualizing semantics is particularly relevant within the area of program transformation where it is useful, e.g., to perform computations during partial evaluation. Thus, the proof of equivalence is a crucial result to demonstrate the correctness of (existing) partial evaluation schemes.

68N15 Theory of programming languages
68Q55 Semantics in the theory of computing
Full Text: DOI
[1] Albert, E.; Hanus, M.; Vidal, G., Using an abstract representation to specialize functional logic programs, (), 381-398 · Zbl 0988.68516
[2] Albert, E.; Hanus, M.; Vidal, G., A practical partial evaluation scheme for multi-paradigm declarative languages, J. funct. logic programming, 1, (2000)
[3] Albert, E.; Vidal, G., The narrowing driven approach to functional logic program specialization, New generation comput., 20, 1, 3-26, (2002) · Zbl 1016.68024
[4] Antoy, S., Definitional trees, (), 143-157
[5] Antoy, S.; Echahed, R.; Hanus, M., A needed narrowing strategy, J. ACM, 47, 4, 776-822, (2000) · Zbl 1327.68141
[6] Hanus, M., A unified computation model for functional and logic programming, (), 80-93
[7] Hanus, M., Curry: an integrated functional logic language, 2000
[8] Hanus, M.; Prehofer, C., Higher-order narrowing with definitional trees, J. funct. programming, 9, 1, 33-75, (1999) · Zbl 0926.68028
[9] Hortalá-González, T.; Ullán, E., An abstract machine based system for a lazy narrowing calculus, (), 216-232 · Zbl 0987.68855
[10] Jones, N.; Gomard, C.; Sestoft, P., Partial evaluation and automatic program generation, (1993), Prentice-Hall Englewood Cliffs, NJ · Zbl 0875.68290
[11] Lux, W.; Kuchen, H., An efficient abstract machine for curry, (), 171-181
[12] Sørensen, M.; Glück, R.; Jones, N., A positive supercompiler, J. funct. programming, 6, 6, 811-838, (1996) · Zbl 0870.68040
[13] Wadler, P., Deforestation: transforming programs to eliminate trees, Theoret. comput. sci., 73, 231-248, (1990) · Zbl 0701.68013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.