Fred: An approach to generating real, correct, reusable programs from proofs

In this paper we describe our system for automatically extracting "correct" programs from proofs using a development of the Curry-Howard process. Although program extraction has been developed by many authors, our system has a number of novel features designed to make it very easy to use and as close as possible to ordinary mathematical terminology and practice. These features include 1. the use of Henkin's technique to reduce higher-order logic to many-sorted (first-order) logic; 2. the free use of new rules for induction subject to certain conditions; 3. the extensive use of previously programmed (total, recursive) functions; 4. the use of templates to make the reasoning much closer to normal mathematical proofs and 5. a conceptual distinction between the computational type theory (for representing programs)and the logical type theory (for reasoning about programs). As an example of our system we give a constructive proof of the well known theorem that every graph of even parity, which is non-trivial in the sense that it does not consist of isolated vertices, has a cycle. Given such a graph as input, the extracted program produces a cycle as promised.

Protocols between programs and proofs

In this paper we describe a new protocol that we call the Curry-Howard protocol between a theory and the programs extracted from it. This protocol leads to the expansion of the theory and the production of more powerful programs. The methodology we use for automatically extracting “correct” programs from proofs is a development of the well-known Curry-Howard process. Program extraction has been developed by many authors, but our presentation is ultimately aimed at a practical, usable system and has a number of novel features. These include 1. a very simple and natural mimicking of ordinary mathematical practice and likewise the use of established computer programs when we obtain programs from formal proofs, and 2. a conceptual distinction between programs on the one hand, and proofs of theorems that yield programs on the other. An implementation of our methodology is the Fred system. As an example of our protocol we describe a constructive proof of the well-known theorem that every graph of even parity can be decomposed into a list of disjoint cycles. Given such a graph as input, the extracted program produces a list of the (non-trivial) disjoint cycles as promised.

Extraction of structured programs from specification proofs

We present a method using an extended logical system for obtaining programs from specifications written in a sublanguage of CASL. These programs are “correct” in the sense that they satisfy their specifications. The technique we use is to extract programs from proofs in formal logic by techniques due to Curry and Howard. The logical calculus, however, is novel because it adds structural rules corresponding to the standard ways of modifying specifications: translating (renaming), taking unions, and hiding signatures. Although programs extracted by the Curry-Howard process can be very cumbersome, we use a number of simplifications that ensure that the programs extracted are in a language close to a standard high-level programming language. We use this to produce an executable refinement of a given specification and we then provide a method for producing a program module that maximally respects the original structure of the specification. Throughout the paper we demonstrate the technique with a simple example.

Micro-credit programs and land distribution: a note

"Micro-credit" has come to refer to a popular extension strategy---usually in the agricultural sector---whereby a government or NGO extends credit at favorable rates to poorer borrowers, with repayment being supported by some kind of mortgage on the borrower's social capital. In the commonest case, eligibility is determined by the borrower's wealth, as indexed by his/her landholding. This note shows that, with an imperfect land market, the response to such a program will be to fragment landholdings which are smaller than a certain threshold, while larger holdings remain unaffected. Thus the pattern of landholding will tend to become more polarized.

Community language programs in Australian schools: policy at the crossroads

The linguistic situation in Australia today presents an intriguing case for sociolinguistic inquiries. Despite the recent waves of migration from non Anglo-Celtic regions, the majority of Australians today are primarily monolingual with English being the dominant language. More critical, perhaps, is the diminishing appeal of second language learning even among second generation speakers of the large ethnic communities. This is indeed ironic giving that prior to white settlement in Australia, the Aboriginal inhabitants were predominantly multilingual with more than 250 languages (and many of their dialects) spoken by the 300 000 original inhabitants at the time when Captain James Cook's ship reached Botany Bay in Sydney in 1770. Given the size of the post-War migration, it was not until 1987 that the Australian government adopted a formal national policy on languages becoming 'the first English-speaking country to have such a policy and the first in the world to have a multilingual languages policy' (Australian Alliance for Languages 2001: 2). This paper will discuss the historical context for multilingualism in Australia and the current trend in government policy and funding. It will provide insights into community language programs and the challenges of remaining viable and relevant in the current social and political climate. Statistical analyses will be used to highlight emerging trends and future prospects.

Rationale and design of the national benchmarking and evidence-based national clinical guidelines for chronic heart failure management programs study

OBJECTIVES: The National Benchmarks and Evidence-Based National Clinical Guidelines for Heart Failure Management Programs Study is a national, multicenter study designed to determine the nature, range, and effect of interventions applied by chronic heart failure management programs (CHF-MPs) throughout Australia on patient outcomes. Its primary objective is to use these data to develop national benchmarks and evidence-based clinical guidelines and optimize their cost-effective application by reducing quality and outcome variability. DATA SOURCES/STUDY SETTING: Primary data will be collected from CHF-MP coordinators and CHF patients enrolled in these programs on a national basis. Secondary outcome data will be collected from a national morbidity record and from patients' medical records. STUDY DESIGN: Stage I of the study involves a prospective clinical audit of all CHF-MPs throughout Australia (n = 45) to determine the extent of variability in programs currently. Stage II is a prospective cross-sectional survey design enrolling 1,500 patients (average of 40 patients per program) to firstly determine the typical profile of patients being managed via a CHF-MP in Australia and, secondly, the subsequent morbidity and mortality during the 6-month follow-up. Outcome data will be subject to multivariate analysis to determine the key components of care in this regard. All study data will be then examined in the final stage of the study (III) to develop national benchmarks for the application and auditing of CHF-MPs in Australia. CONCLUSION: Variability in patient outcomes is a product of heterogeneity among CHF-MPs. The development of national benchmarks will minimize such heterogeneity and will provide a greater level of evidence for their cost-effective application.