Restricted two-level grammars as a technique for formalizing programming schemes
Marguerite E. Saacks, Johnette Hassell · 1989
Researchers in software engineering have formulated models that attempt to describe the process an expert programmer uses to solve problems. A programming scheme is one such model. The programming scheme model is a hierarchical model in which an expert forms abstractions to the solution to a problem. These abstractions capture the essential features of the process that is used to solve the problem. When developing a more concrete solution, the expert refines the abstraction until a specific representation is obtained. The refinement is depicted by levels in the hierarchical model. This dissertation focuses on the formal mechanisms used for modeling these programming schemes. This research examines the syntactic and semantic issues associated with the choice of a restricted two-level grammar as the formal model for programming schemes. The relationship between the hierarchical levels of a programming scheme and the restricted two-level grammar that defines the scheme is studied. Programming schemes that reference other schemes are also examined. This examination establishes a connection between a scheme that references another scheme as opposed to one that completely elaborates a scheme within it. This connection describes a relationship between an expert's programming scheme and a novice's programming scheme. A less developed hierarchy is also studied and a transformation is formulated from this less developed programming scheme to a fully developed model. The transformation establishes a formal link between a programming scheme used by a novice and a programming scheme used by an expert. The study of the semantic issues begins with the definition of the denotational semantics of the restricted two-level grammar. This work also examines the overall meaning of a programming scheme. This meaning is defined using a generalization of pre- and post-conditions. The semantic relationships between the levels of the programming scheme are also studied. Finally, an algorithm is developed that combines two programming schemes. This algorithm creates a new programming scheme, called an envelope, that models the optimized process an expert programmer uses in integrating new schemes and representations into an existing knowledge structure.