26840234
Software Development by Refinement
This paper presents an overview of the technical foundations and current directions of Kestrel’s approach to mechanizing software development. The approach emphasizes machine-supported refinement of property-oriented specifications to code, based on a category of higher-order specifications. A key idea is representing knowledge about programming concepts, such as algorithm design, and datatype refinement by means of taxonomies of abstract design theories and refinements. Concrete refinements are generated by composing library refinements with a specification.
206511487
Composition and refinement of behavioral specifications
This paper presents a mechanizable framework for specifying, developing, and reasoning about complex systems. The framework combines features from algebraic specifications, abstract state machines, and refinement calculus, all couched in a categorical setting. In particular, we show how to extend algebraic specifications to evolving specifications (especs) in such a way that composition and refinement operations extend to capture the dynamics of evolving, adaptive, and self-adaptive software development, while remaining efficiently computable. The framework is partially implemented in the Epoxi system.
5110731
A Problem Reduction Approach to Program Synthesis
Program synthesis is the transformation of a specification of a user's problem into a computer program. A problem reduction approach to program synthesis is presented. During synthesis the user's problem is decomposed in a top-down manner into a hierarchy of subproblems. with directly solveable subproblems at the bottom. Solving these subproblems results in the bottom-up composition of a program whose structure reflects the subproblem hierarchy. The program is guaranteed to satisfy the specification and to terminate on all legal inputs. We illustrate this approach by presenting the knowledge needed to synthesize a class of divide and conquer algorithms and by deriving a Merge sort algorithm.
13516557
The Design of Divide and Conquer Algorithms
Abstract The structure common to a class of divide and conquer algorithms is represented by a program scheme. A theorem is presented which relates the functionality of a divide and conquer algorithm to its structure and the functionalities of its subalgorithms. Several strategies for designing divide and conquer algorithms arise from this theorem and they are used to formally derive algorithms for sorting a list of numbers, forming the cartesian product of two sets, and finding the convex hull of a set of planar points.
11350926
A Generative Approach to Aspect-Oriented Programming
Aspect-Oriented Software Development (AOSD) offers new insights and tools for the modular development of systems with cross-cutting features. Current tool support for AOSD is provided mainly in the form of code-level constructs. This paper presents a way to express cross-cutting features as logical invariants and to use generative techniques to produce the kind of code that is usually written manually in AOSD. In order to state invariants that express cross-cutting features, we often need to reify certain extra-computational values such as history or the runtime call stack. The generative approach is illustrated by a variety of examples.
5281675
Algorithm Theories and Design Tactics
Abstract Algorithm theories represent the structure common to a class of algorithms, such as divide-and-conquer or backtrack. An algorithm theory for a class A provides the basis for design tactics—specialized methods for designing A -algorithms from formal problem specifications. We illustrate this approach with recent work on the theory of global search algorithms and briefly mention several others. Several design tactics have been implemented in the kids / cypress system and have been used to semiautomatically derive many algorithms.
44972038
Project CALC: Calculus as a Laboratory Course
Calculus is the study of change. The concepts of calculus enable us to model processes that change and to describe properties of these processes that remain constant in the midst of change. Now change has come to the learning of calculus -change driven by the need to respond to the revolution in technology and fueled by funds from the United States National Science Foundation. What should be changed? How and how fast? What should remain constant? In this paper we describe one answer to these questions: Project CALC, a new calculus course developed at Duke University. The key features of our approach are real-world problems, hands-on activities, discovery learning, writing and revision of writing, teamwork, and intelligent use of available tools.
8267445
Explaining design plans
The paper describes a methodology for generating quality explanations from design plans. In selecting items of information for inclusion in an explanation, the methodology considers the rationales behind the strategic knowledge and object-level knowledge specified in a design plan. Rhetorical structure theory and discourse focus tracking are utilised to determine textual structure, and to maintain discourse coherence and cohesion. Using a simple system of user modelling, it is shown how the methodology flexibly includes consideration of a user's knowledge, thus resulting in more focused and convincing explanations. The methodology is used to investigate follow-up explanations, and the generation of explanations from plans which contain a misconception on the part of the designer.
2813562
Context-Based Morphological Disambiguation with Random Fields
Finite-state approaches have been highly successful at describing the morphological processes of many languages. Such approaches have largely focused on modeling the phone- or character-level processes that generate candidate lexical types, rather than tokens in context. For the full analysis of words in context, disambiguation is also required (Hakkani-Tur et al., 2000; Hajic et al., 2001). In this paper, we apply a novel source-channel model to the problem of morphological disambiguation (segmentation into morphemes, lemmatization, and POS tagging) for concatenative, templatic, and inflectional languages. The channel model exploits an existing morphological dictionary, constraining each word's analysis to be linguistically valid. The source model is a factored, conditionally-estimated random field (Lafferty et al., 2001) that learns to disambiguate the full sentence by modeling local contexts. Compared with baseline state-of-the-art methods, our method achieves statistically significant error rate reductions on Korean, Arabic, and Czech, for various training set sizes and accuracy measures.
13000609
Disambiguating Geographic Names in a Historical Digital Library
Geographic interfaces provide natural, scalable visualizationss for many digital library collections, but the wide range of data in digital libraries presents some particular problems for identifying and disambiguating place names. We describe the toponym-disambiguation system in the Perseus digital library and evaluate its performance. Name categorization varies significantly among different types of documents, but toponym disambiguation performs at a high level of precision and recall with a gazetteer an order of magnitude larger than most other applications.
7569023
Journey planning based on user needs
In this paper we discuss potential developments to the design of pre-trip in-home journey planning services, to include support for additional user needs. These needs were identified through stakeholder interviews as contributing to actual decisions in route selection scenarios and include: safety, weather and even fitness. A journey planner was designed to allow users to articulate these constraints and a series of paper prototypes were evaluated through cognitive walkthroughs. An exploratory study compared three designs and provided rationale for the most effective interaction method, informing an implementation plan.