The purpose of this paper is twofold. Firstly we show how attributes in an attribute grammar can be simply and e ciently evaluated using a lazy functional language. The class of attribute grammars we can deal with are the most general ones possible: attributes may depend on each other in an arbitrary way, as long as there are no truly circular data dependencies. Secondly, we describe a methodology based on attribute grammars, where, in a fairly straightforward way, we can develop e cient functional programs where direct, conventional solutions yield less e cient programs. We review two examples from a paper by R. Bird (Using circular programs to eliminate multiple traversals of data, Acta Informatica, 21, 1984) where he transforms simple but ine cient multipass programs into more e cient single pass ones, but which on their own can be very hard to understand. We show how such e cient but tangled programs can have natural formulations as attribute grammars. We also propose a language construct, called case rec (akin to the case expression in Standard ML and Lazy ML), that de nes an attribute grammar over a data structure in the language. In e ect, a case rec expression de nes a recursion operator that can handle multiple values, both upwards-propagating and downwards-propagating ones.
A number of systems use lazy functional languages to define evaluators as circular programs REF .
Attribute Grammars as a Functional Programming Paradigm
Functional Programming Languages and Computer Architecture, volume 274 of LNCS
Computer Science