Partial evaluation of Maple. (English) Zbl 1215.68277
Summary: Having been convinced of the potential benefits of partial evaluation, we wanted to apply these techniques to code written in Maple, our computer algebra system of choice. Maple is a very large language, with a number of non-standard features. When we tried to implement a partial evaluator for it, we ran into a number of difficulties for which we could find no solution in the literature. Undaunted, we persevered and ultimately implemented a working partial evaluator with which we were able to very successfully conduct our experiments, first on small codes, and now on actual routines taken from Maple’s own library. Here, we document the techniques we had to invent or adapt to achieve these results.
References:
| [1] | Carette, J.: Gaussian elimination: a case study in efficient genericity with metaocaml, Science of computer programming 62, No. 1, 3-24 (2006) · Zbl 1100.68130 · doi:10.1016/j.scico.2005.10.012 |
| [2] | J. Carette, O. Kiselyov, Multi-stage programming with functors and monads: eliminating abstraction overhead from generic code, in: GPCE, 2005, pp. 256–274. · Zbl 1215.68059 |
| [3] | C. Anand, J. Carette, A. Korobkine, Target recognition algorithm employing Maple code generation, in: Maple Summer Workshop, 2004, 13 pages. |
| [4] | C.K. Anand, J. Carette, A. Curtis, D. Miller, COG-PETS: code generation for parameter estimation in time series, in: Maple Conference 2005 Proceedings, Maplesoft, 2005, pp. 198–212. · Zbl 1344.65017 |
| [5] | M. Kucera, J. Carette, Partial evaluation and residual theorems in computer algebra, in: Ranise and Bigatti [34], 14 pages. · Zbl 1215.68277 |
| [6] | M. Kucera, Partial evaluation of maple programs, Master’s Thesis, McMaster University, May 2006. |
| [7] | Jones, N. D.; Gomard, C. K.; Sestoft, P.: Partial evaluation and automatic program generation, (1993) · Zbl 0875.68290 |
| [8] | Elphick, D.; Leuschel, M.; Cox, S.: Partial evaluation of Matlab, , 344-363 (2003) |
| [9] | Sumii, E.; Kobayashi, N.: Online type-directed partial evaluation for dynamically-typed languages, Computer software, iwanami shoten, Japan 17, No. 3, 38-62 (2000) |
| [10] | Sumii, E.; Kobayashi, N.: A hybrid approach to online and offline partial evaluation, Higher-order and symbolic computation 14, No. 2–3, 101-142 (2001) · Zbl 0994.68037 · doi:10.1023/A:1012984529382 |
| [11] | P. Thiemann, Cogen in six lines, in: Proc. ACM SIGPLAN International Conference on Functional Programming 1996, 1996, pp. 180–189. · Zbl 1345.68077 |
| [12] | P. Thiemann, D. Dussart, Partial evaluation for higher-order languages with state, available from first author’s web page, July 1999. |
| [13] | J. Carette, S. Forrest, Mining Maple code for contracts, in: Ranise and Bigatti [34]. 14 pages. |
| [14] | S. Forrest, Property inference for maple: an application of abstract interpretation, Master’s Thesis, McMaster University, September 2007. |
| [15] | Musser, D. R.; Stepanov, A. A.: Generic programming, Lecture notes in computer science 358, 13-25 (1989) |
| [16] | Gruntz, D.; Monagan, M.: Introduction to Gauss, SIGSAM bulletin, Communications on computer algebra 28, No. 2, 3-19 (1994) |
| [17] | P. Thiemann, The PGG System–User Manual, March 2000. |
| [18] | J. Carette, M. Kucera, Partial evaluation for maple, in: ACM SIGPLAN 2007 Workshop on Partial Evaluation and Program Manipulation, 2007, pp. 41–50. |
| [19] | Monagan, M. B.; Geddes, K. O.; Heal, K. M.; Labahn, G.; Vorkoetter, S. M.; Mccarron, J.; Demarco, P.: Maple 10 advanced programming guide, (2005) |
| [20] | Appel, A. W.: Modern compiler implementation in ML, (1998) · Zbl 0888.68035 |
| [21] | Stoutemeyer, D.: Crimes and misdemeanors in the computer algbebra trade, Notices of the AMS, 701-785 (1991) |
| [22] | L.O. Andersen, C program specialization, Tech. Rep., DIKU, University of Copenhagen, May 1992. |
| [24] | Schreye, D. D.; Glück, R.; Jørgensen, J.; Leuschel, M.; Martens, B.; Sørensen, M. H.: Erratum to: ”conjunctive partial deduction: foundations, control, algorithms and experiments”, Journal of logic programming 43, No. 3, 265 (2000) · Zbl 0944.68025 |
| [25] | Leuschel, M.; Bruynooghe, M.: Logic program specialisation through partial deduction: control issues, Tplp 2, No. 4–5, 461-515 (2002) · Zbl 1105.68331 · doi:10.1017/S147106840200145X |
| [26] | Sørensen, M. H.; Glück, R.; Jones, N. D.: A positive supercompiler, Journal of functional programming 6, No. 6, 811-838 (1996) · Zbl 0870.68040 · doi:10.1017/S0956796800002008 |
| [27] | E. Albert, M. Hanus, G. Vidal, A practical partial evaluation scheme for multi-paradigm declarative languages, Journal of Functional and Logic Programming, 2002. · Zbl 1037.68011 |
| [28] | Andersen, L. O.: Partial evaluation of C and automatic compiler generation (extended abstract), Lecture notes in computer science 641, 251-257 (1992) |
| [29] | L.O. Andersen, Binding-time analysis and the taming of c pointers, in: PEPM, 1993, pp. 47–58. |
| [30] | Christensen, N. H.; Glück, R.: Offline partial evaluation can be as accurate as online partial evaluation, ACM transactions on programming languages and systems 26, No. 1, 191-220 (2004) |
| [31] | Ballarin, C.; Kauers, M.: Solving parametric linear systems: an experiment with constraint algebraic programming, SIGSAM bulletin 38, No. 2, 33-46 (2004) · Zbl 1341.68310 |
| [32] | S. Lo, M. Monagan, R. Pearce, Generic linear algebra and quotient rings, in: Maple Conference 2006 Proceedings, 2006, pp. 179–188, ISBN 1-897310-13-7. · Zbl 1107.65030 |
| [34] | , Electronic notes in theoretical computer science (2006) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
