Programming with narrowing: A tutorial

Narrowing is a computation implemented by some declarative programming languages. Research in the last decade has produced significant results on the theory and foundation of narrowing, but little has been published on the use of narrowing in programming. This paper introduces narrowing from a programmer’s viewpoint; shows, by means of examples, when, why and how to use narrowing in a program; and discusses the impact of narrowing on software development activities such as design and maintenance. The examples are coded in the programming language Curry, which provides narrowing as a first class feature.     

Ricerca random pesata in tavole hash

A new search method in hash table is presented: collisions are resolved by a pseudorandom function depending on the key, in such a way that the search is free from clustering and at a comparable cost with respect to previous methods.     

Using term rewriting to verify software

This paper describes a uniform approach to the automation of verification tasks associated with while statements, representation functions for abstract data types, generic program units, and abstract base classes. Program units are annotated with equations containing symbols defined by algebraic axioms. An operation's axioms are developed by using strategies that guarantee crucial properties such as convergence and sufficient completeness. Sets of axioms are developed by stepwise extensions that preserve these properties. Verifications are performed with the aid of a program that incorporates term rewriting, structural induction, and heuristics based on ideas used in the Boyer-Moore prover. The program provides valuable mechanical assistance: managing inductive arguments and providing hints for necessary lemmas, without which formal proofs would be impossible. The successes and limitations of our approaches are illustrated with examples from each domain     

A Monadic Semantics for Core Curry

We give a deterministic, big-step operational semantics for the essential core of the Curry language, including higher-order functions, call-by-need evaluation, non-determinism, narrowing, and residuation. The semantics is structured in modular monadic style, and is presented in the form of an executable interpreter written in Haskell. It uses monadic formulations of state, non-determinism, and resumption-based concurrency.     

Automatically checking an implementation against its formalspecification

We propose checking the execution of an abstract data type's imperative implementation against its algebraic specification. An explicit mapping from implementation states to abstract values is added to the imperative code. The form of specification allows mechanical checking of desirable properties such as consistency and completeness, particularly when operations are added incrementally to the data type. During unit testing, the specification serves as a test oracle. Any variance between computed and specified values is automatically detected. When the module is made part of some application, the checking can he removed, or may remain in place for further validating the implementation. The specification, executed by rewriting, can be thought of as itself an implementation with maximum design diversity, and the validation as a form of multiversion-programming comparison     

A recursive algorithm for quick and efficient bit reversing

An algorithm to generate the permutation by bit reversal of the sequence of integers (0, 1,…,2ⁿ ? 1) is presented. To generate a sequence of length k = 2ⁿ the algorithm requires only k ? 1 additions and k ? 2 multiplications by 2. With respect to previous methods, the reduction of the computing time is O(log₂k).     

Contour plotting for function specified at nodal points of a mesh based on a set of irregular profiles

A FORTRAN IV subroutine entitled CMAP is provided for determining the contour lines of a function specified on a mesh made by a set of irregular profiles. The subroutine is independent of the support medium holding the mesh, thus it is possible to work on a large set of data with a small computer.     

Lazy Context Cloning for Non-Deterministic Graph Rewriting

We define a rewrite strategy for a class of non-confluent constructor-based term graph rewriting systems and prove its correctness. Our strategy and its extension to narrowing are intended for the implementation of non-strict non-deterministic functional logic programming languages. Our strategy is based on a graph transformation, called bubbling, that avoids the construction of large contexts of redexes with distinct replacements, an expensive and frequently wasteful operation executed by competitive complete techniques.