International Journal of Foundations of Computer Science

In this paper, we study λ_→-representability of functions over (open or closed) term algebras. First, by extending the standard notion of λ_→-representation of closed (or variable-free) terms to open terms and extending the notion of λ_→-representable functions accordingly, we give a recursion-theoretic characterization of the class of λ_→-representable functions over open term algebras. Then, based on this result, we obtain two characterizations of the class of λ_→-representable functions over closed term algebras (i.e., free structures). As a related topic, in the Appendix we give a simple formulation of the recursive word functions, and study their properties in relation to recursive functions on natural numbers and type-free pure λ-calculus.

This paper treats Martin-Löf's type theory as an open-ended framework composed of (i) flexibly extensible languages into which various forms of objects and types can be incorporated, (ii) their uniform, effectively given semantics, and (iii) persistently valid inference rules. The class of expression systems is introduced here to define an open-ended body of languages underlying the theory. Each expression system consists of two parts: the computational part is a structured lazy evaluation system with a bisimulation-like program equivalence; the structural part is a system of strictly positive inductive definitions for type constructors in terms of partial equivalence relations. Types and their objects are uniformly and inductively constructed from a given expression system as a type system, which can provide a semantics of the theory. Building on these concepts, this paper presents two main results. First, all the inference rules of the theory are sound; that is, they remain valid in every type system built from an extension of an initial expression system. This result gives a characterization of the class of types that can be introduced into the theory. Second, each type system is complete with respect to the underlying bisimulation-like program equivalence. This result provides a useful form of type-free equational reasoning in the theory.

In this work, we consider term rewriting from a functional point of view. A rewrite rule is a function that can be applied to a term using an explicit application function. From this starting point, we show how to build more elaborated functions, describing first rewrite derivations, then sets of derivations. These functions, that we call strategies, can themselves be defined by rewrite rules and the construction can be iterated leading to higher-order strategies. Furthermore, the application function is itself defined using rewriting in the same spirit. We present this calculus and study its properties. Its implementation in the language is used to motivate and exemplify the whole approach. The expressiveness of is illustrated by examples of polymorphic functions and strategies.

Two-Stage Programming (2SP) is an experimental programming language, the first implementation of the Specification-Consistent Coordination Model (SCCM). The SCCM proposes a new, mixed-paradigm (functional/imperative) approach to developing reliable programs based on complete run-time checking of computations with respect to a given specification. A 2SP program consists of a functional specification and an imperative coordination tightly connected to the specification. The coordination maps the specification to an imperative and possibly parallel/distributed program. Normal termination of a 2SP program execution implies the correctness of the computed results with respect to the specification, for that execution. We present the basic feautures of the SCCM/2SP, a new message-spassing system of 2SP with integrated run-time checking, and a larger case study. We show that 2SP provides: functional specifications, specification-consistent imperative coordinations, automatic run-time result verification and error detection, enhanced debugging support, and good efficiency.