Xref: utzoo ont.events:1353 uw.talks:56 uw.cs.grad:52 Path: utzoo!attcan!utgpu!watmath!maytag!water!wlrush From: wlrush@water.waterloo.edu (Wenchantress Wench Wendall) Newsgroups: ont.events,uw.talks,uw.cs.grad Subject: PROGRAMMING LANGUAGES SEMINAR Keywords: Prof. R.A. Frost, University of Windsor Message-ID: <2723@water.waterloo.edu> Date: 26 Oct 89 15:21:55 GMT Distribution: ont Organization: U of Waterloo, Ontario Lines: 61 DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF WATERLOO SEMINAR ACTIVITIES PROGRAMMING LANGUAGES SEMINAR -Friday, November 3, 1989 Professor R.A. Frost, School of Computer Science, University of Windsor will speak on ``Use of Algebraic Identities in the Calculation of Programs Constructed as Executable Specifications of Attribute Grammars.'' TIME: 1:30 p.m. ROOM: DC 1304 ABSTRACT There is a growing interest in the notion that programs can be `calculated' by transforming executable specifications to more efficient provably equivalent forms using algebraic identities. Such calculation is facilitated if the executable specifications are variable-free and have no explicit recursion. This can be achieved by expressing specifications as compositions of higher order functions which capture common patterns of computation. These specifications can then be transformed using algebraic identities that have been proven for the higher order functions. In this seminar we describe how this approach can be used in the calculation of programs constructed as executable specifications of attribute grammars. Programs are regarded as language processors and are calculated using algebraic identities proven for higher order ``language processor generators.'' The approach is tolerant of inaccurate and incomplete initial specifications and is `environmentally friendly' in that there is little wasted effort. We give an example showing how a program which converts arbitrary expressions of propositional logic to clausal form can be transformed to an efficient theorem prover for propositional logic; the original executable attribute grammar uses synthesised attributes only, the more efficient form uses inherited as well as synthesised attributed. The programming environment that we have built may be thought of as a realization of a suggestion made by Knuth in 1971 that executable attribute grammars might provide a viable declarative programming language. The integration of this idea with transformations based on algebraic identities as suggested by Backus and Bird has been greatly facilitated by the availability of Turner's higher order, pure, lazy functional programming language Miranda.* The contribution ----------- Miranda is a trademark of Research Software Ltd. - 2 - of the work described in the seminar is to bring these things together to form a viable new programming paradigm.