Grammatical programming: An algebraic approach to the description of design spaces

摘要

The intuitiveness of spatial grammars makes them an attractive method of describing spaces of design. But grammars suffer from several inadequacies that limit their usefulness in design practice: (1) they cannot describe spaces of parametric, constrained designs, (2) they provide no control mechanisms for sequencing sets of rules, (3) they provide no "subroutines" for dealing with complexity, and (4) they do not accommodate transformation mechanisms other than the rewrite rule.;All of these inadequacies may be remedied by embedding grammars in a larger framework of nondeterministic functional programming, a paradigm we call "grammatical programming." In grammatical programs, rewrite rules are obtained from arbitrary nondeterministic functions by means of a "rewrite closure" operator. Both rules and the designs they operate upon may be parametric and have attached constraints, permitting grammatical programs to describe spaces of parametric, constrained designs. Rewrite rules, and more generally, nondeterministic functions, are combined into compound functions by means of the operators of a control algebra, which provides functional composition, union, iteration, and a type of negation called "failure." The resulting modularity permits design space descriptions to be constructed, tested, and debugged piecewise, and to draw upon libraries of standard, debugged grammatical components.;We begin this dissertation with an informal introduction to grammatical programming. We then give a formal, implementation-independent semantics of grammatical programs similar to the semantics of stratified logic programs. We discuss the implementation of a prototype compiler/interpreter and present case studies of the use of the prototype in describing spaces of rectangular dissections and a style of early Gothic traceries. We conclude with a discussion of lessons learned from the case studies and an agenda of further research necessary to make grammatical programming a useful tool in design practice.