Description: |
Functional programming concepts and straight-line programs in computer algebra. We present MILONGA, a language based on functional programming concepts, which was designed for the implementation of a new generation of nonterm-rewriting elimination algorithms for multivariate polynomial solving.par These new algorithms profit from an alternative representation of multivariate polynomials by means of straight-line programs, allowing an exponential improvement of theoretical complexity – with respect to computing time and memory space – upon traditional, term-rewriting procedures.par There is a strong analogy between the way how these algorithms employ straight-line programs and the way how functional programming languages treat functions as first-class citizens. Taking advantage of this circumstance, the MILONGA language enables us to analyze the relevance of the functional programming paradigm for the particular kind of task of polynomial equation solving.par The paper contains an exhaustive do-it-yourself description of the programming philosophy of MILONGA, of the development of its compiler, of the operational semantics of its run-time system and of the implementation of a couple of fundamental computer algebra procedures in this language.par The practical efficiency of this philosophy and implementation is outlined by comparative benchmarking on significant test examples. |