Lightweight Formal Verification in Classroom Instruction of Reasoning about Functional Code

In college courses dealing with material that requires mathematical rigor, the adoption of a machine-readable representation for formal arguments can be advantageous. Students can focus on a specific collection of constructs that are represented consistently. Examples and counterexamples can be evaluated. Assignments can be assembled and checked with the help of an automated formal reasoning system. However, usability and accessibility do not have a high priority and are not addressed sufficiently well in the design of many existing machine-readable representations and corresponding formal reasoning systems. In earlier work [Lap09], we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. We report on our attempt to evaluate our proposed design criteria by deploying within the classroom a lightweight formal verification system designed according to these criteria. The lightweight formal verification system was used within the instruction of a common application of formal reasoning: proving by induction formal propositions about functional code. We present all of the formal reasoning examples and assignments considered during this deployment, most of which are drawn directly from an introductory text on functional programming. We demonstrate how the design of the system improves the effectiveness and understandability of the examples, and how it aids in the instruction of basic formal reasoning techniques. We make brief remarks about the practical and administrative implications of the system’s design from the perspectives of the student, the instructor, and the grader.

The Practice and Understanding of the Eucharist in the United Church of Christ: A Practical Theological Study

This dissertation explores the complexity of the understanding and practice of the Eucharist in the United Church of Christ as revealed in a textual analysis of the UCC Book of Worship (1986) and a qualitative study of five representative UCC congregations. Little has been written on this topic, save for several brief articles on the history of the theology of the sacrament in the two bodies that merged to form the UCC in 1957: the Congregational Christian Churches (CC) and the Evangelical and Reformed Church (E&R). This dissertation advances the topic through a practical-theological study that brings into critical conversation contemporary eucharistic practices in five congregations and a historical theological analysis of liturgical traditions in the UCC and antecedent denominations. Through this conversation, the study articulates common themes of a UCC eucharistic theology and explores implications for ongoing theology and practice in the denomination. The introduction explicates the methodology employed in this study, guided by Don Browning's work. The first two chapters present the findings of the focus group interviews and an interpretation of those results respectively. Chapter three analyzes the eucharistic liturgies in three historic books of worship used in the E&R heritage. In chapter four, two of the antecedent resources utilized in the CC tradition are analyzed. The short-lived Hymnal of the United Church of Christ, published in 1974, includes liturgies that would find fuller expression in the 1986 Book of Worship. That hymnal is examined in chapter five. Chapter six interprets the two services of "Word and Sacrament" found in the Book of Worship. Chapter seven offers a comparative analysis of the focus group findings and the theology inherent in the Book of Worship. The final chapter offers strategic recommendations for revised theory and practice. The conclusion points toward areas for further research: it propels a critical conversation around the notion of covenant, Christ's presence in the meal, and who can receive and officiate at the Eucharist. This dissertation concludes that the UCC lives within a balance of multiple, complementary theologies and challenges the denomination to make stronger connections between the meal and mission, reconciliation, and tradition.

Towards Eco-Dharma: The Contribution of Gandhian Thought to Ecological Ethics in India

Ecological concern prompts poor and indigenous people of India to consider how a society can ensure both protection of nature and their rightful claim for a just and sustainable future. Previous discussions defended the environment while ignoring the struggles of the poor for sustenance and their religious traditions and ethical values. Mohandas Karamchand Gandhi addressed similar socio-ecological concerns by adopting and adapting traditional religious and ethical notions to develop strategies for constructive, engaged resistance. The dissertation research and analysis verifies the continued relevance of the Gandhian understanding of dharma (ethics) in contemporary India as a basis for developing eco-dharma (eco-ethics) to link closely development, ecology, and religious values. The method of this study is interpretive, analytical, and critical. Françoise Houtart’s social analytical method is used to make visible and to suggest how to overcome social tensions from the perspective of marginalized and exploited peoples in India. The Indian government's development initiatives create a nexus between the eco-crisis and economic injustice, and communities’ responses. The Chipko movement seeks to protect the Himalayan forests from commercial logging. The Narmada Bachao Andolan strives to preserve the Narmada River and its forests and communities, where dam construction causes displacement. The use of Gandhian approaches by these movements provides a framework for integrating ecological concerns with people's struggles for survival. For Gandhi, dharma is a harmony of satya (truth), ahimsa (nonviolence), and sarvodaya (welfare of all). Eco-dharma is an integral, communitarian, and ecologically sensitive ethical paradigm. The study demonstrates that the Gandhian notion of dharma, implemented through nonviolent satyagraha (firmness in promoting truth), can direct community action that promotes responsible economic structures and the well-being of the biotic community and the environment. Eco-dharma calls for solidarity, constructive resistance, and ecologically and economically viable communities. The dissertation recommends that for a sustainable future, India must combine indigenous, appropriate, and small- or medium-scale industries as an alternative model of development in order to help reduce systemic poverty while enhancing ecological well-being.

A Direct Algorithm for the Type Interference in the Rank 2 Fragment of the Second--Order λ-Calculus

We study the problem of type inference for a family of polymorphic type disciplines containing the power of Core-ML. This family comprises all levels of the stratification of the second-order lambda-calculus by "rank" of types. We show that typability is an undecidable problem at every rank k ≥ 3 of this stratification. While it was already known that typability is decidable at rank ≤ 2, no direct and easy-to-implement algorithm was available. To design such an algorithm, we develop a new notion of reduction and show how to use it to reduce the problem of typability at rank 2 to the problem of acyclic semi-unification. A by-product of our analysis is the publication of a simple solution procedure for acyclic semi-unification.

A Linearization of the Lambda-Calculus and Consequences

If every lambda-abstraction in a lambda-term M binds at most one variable occurrence, then M is said to be "linear". Many questions about linear lambda-terms are relatively easy to answer, e.g. they all are beta-strongly normalizing and all are simply-typable. We extend the syntax of the standard lambda-calculus L to a non-standard lambda-calculus L^ satisfying a linearity condition generalizing the notion in the standard case. Specifically, in L^ a subterm Q of a term M can be applied to several subterms R1,...,Rk in parallel, which we write as (Q. R1 \wedge ... \wedge Rk). The appropriate notion of beta-reduction beta^ for the calculus L^ is such that, if Q is the lambda-abstraction (\lambda x.P) with m\geq 0 bound occurrences of x, the reduction can be carried out provided k = max(m,1). Every M in L^ is thus beta^-SN. We relate standard beta-reduction and non-standard beta^-reduction in several different ways, and draw several consequences, e.g. a new simple proof for the fact that a standard term M is beta-SN iff M can be assigned a so-called "intersection" type ("top" type disallowed).

Principles of Safe Policy Routing Dynamics

We introduce the Dynamic Policy Routing (DPR) model that captures the propagation of route updates under arbitrary changes in topology or path preferences. DPR introduces the notion of causation chains where the route flap at one node causes a flap at the next node along the chain. Using DPR, we model the Gao-Rexford (economic) guidelines that guarantee the safety (i.e., convergence) of policy routing. We establish three principles of safe policy routing dynamics. The non-interference principle provides insight into which ASes can directly induce route changes in one another. The single cycle principle and the multi-tiered cycle principle provide insight into how cycles of routing updates can manifest in any network. We develop INTERFERENCEBEAT, a distributed algorithm that propagates a small token along causation chains to check adherence to these principles. To enhance the diagnosis power of INTERFERENCEBEAT, we model four violations of the Gao-Rexford guidelines (e.g., transiting between peers) and characterize the resulting dynamics.

Verification with Natural Contexts: Soundness of Safe Compositional Network Sketches

In research areas involving mathematical rigor, there are numerous benefits to adopting a formal representation of models and arguments: reusability, automatic evaluation of examples, and verification of consistency and correctness. However, accessibility has not been a priority in the design of formal verification tools that can provide these benefits. In earlier work [30] we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. In this report we evaluate our proposed design criteria by utilizing within the context of novel research a formal reasoning system that is designed according to these criteria. In particular, we consider how the design and capabilities of the formal reasoning system that we employ influence, aid, or hinder our ability to accomplish a formal reasoning task – the assembly of a machine-verifiable proof pertaining to the NetSketch formalism. NetSketch is a tool for the specification of constrained-flow applications and the certification of desirable safety properties imposed thereon. NetSketch is conceived to assist system integrators in two types of activities: modeling and design. It provides capabilities for compositional analysis based on a strongly-typed domain-specific language (DSL) for describing and reasoning about constrained-flow networks and invariants that need to be enforced thereupon. In a companion paper [13] we overview NetSketch, highlight its salient features, and illustrate how it could be used in actual applications. In this paper, we define using a machine-readable syntax major parts of the formal system underlying the operation of NetSketch, along with its semantics and a corresponding notion of validity. We then provide a proof of soundness for the formalism that can be partially verified using a lightweight formal reasoning system that simulates natural contexts. A traditional presentation of these definitions and arguments can be found in the full report on the NetSketch formalism [12].