Implementing higher-order algebraic specifications
Jan Heering · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 1991
Writing algebraic specifications that are to be executed as rewrite systems is similar to functional programming.There are some differences, however.Algebraic specification languages allow left-hand sides of equations to be complex first-order patterns that would not be allowed in functional languages.Functional languages, on the other hand, have powerful higher-order features not offered by algebraic specification languages.Some functional languages combine higher-order functions with linear firstorder patterns involving free data type constructors, thus offering a limited (but highly expressive) mixture of functional ,pi'ogramming and algebraic specification.A more ambitious integration of the two is obtained by allowing both signatures and equations in algebraic specifications to be higher-order.Operational experiments with such higher-order algebraic specifications can be performed by translating them to A.Prolog, an extension of Prolog to polymorphically typed A.-terms based on higher-order unification.