Chapter 2: Generic Proofs for Combinator-based Generic Programs

Reig, Fermín
March 2006
Trends in Functional Programming Volume 5;2006, Vol. 5, p17
Generic programming can bring important benefits to software engineering. In particular, it reduces the burden of verification, since generic proofs can be instantiated at many types. Reasoning about programs that use type classes does not enjoy the benefits of generic reasoning, as it requires providing proofs for an arbitrary number of type instances. This makes the process very impractical. We describe a useful method to reason about a class of programs that use type classes, based on the idea that generic functions implemented using overloading can also be expressed polytypically. We demonstrate the method on functions from the 'scrap-your-boilerplate' library, a collection of combinators for generic programming that has been proposed and implemented recently.


Related Articles

  • Chapter 12: Extensible and Modular Generics for the Masses. Oliveira, Bruno C. d. S.; Hinze, Ralf; Löh, Andres // Trends in Functional Programming Volume 7;2007, Vol. 7, p199 

    A generic function is a function that is defined on the structure of data types: with a single definition, we obtain a function that works for many data types. In contrast, an ad-hoc polymorphic function requires a separate implementation for each data type. Previous work by Hinze on lightweight...

  • A METHODOLOGY TO IDENTIFY THE LEVEL OF REUSE USING TEMPLATE FACTORS. Basha, N. Md Jubair; Mohan, Chandra // International Journal of Software Engineering & Applications;Sep2012, Vol. 3 Issue 5, p103 

    To build large scale software systems, Component Based Software Engineering (CBSE) has played a vital role. The current practices of software industry demands more development of a software within time and budget which is highly productive to them. It became so necessary to achieve how...

  • A Component-Based Framework for Software Reusability. Khan, Adnan; Khan, Khalid; Amir, Muhammad; Khan, M. N. A. // International Journal of Software Engineering & Its Applications;2014, Vol. 8 Issue 10, p13 

    Component-based development allows us to develop and integrate product components which facilitate software reusability, high quality and simplification for testing. Component- Based Software Engineering makes use of approaches which are based on architecture definition languages, object...

  • A Space-Efficient Optimization of Call-by-Need. Burton, F. Warren; Maurer, Dieter; Oberhauser, Hans-Georg; Wilhelm, Reinhard // IEEE Transactions on Software Engineering;Jun87, Vol. 13 Issue 6, p636 

    Call-by-need is widely regarded as an optimal (to within a constant factor) parameter passing mechanism for functional programming languages. Except for certain special cases involving higher order functions, call-by-need is optimal with respect to time. However, call-by-need is far from optimal...

  • Functional Programming, Formal Specification, and Rapid Prototyping. Henderson, Peter // IEEE Transactions on Software Engineering;Feb86, Vol. 12 Issue 2, p241 

    Functional programming has enormous potential for reducing the high cost of software development. Because of the simple mathematical basis of functional programming it is easier to design correct programs in a purely functional style than in a traditional imperative style. We argue here that...

  • Semantics of EqL. Jayaraman, Bharat // IEEE Transactions on Software Engineering;Apr88, Vol. 14 Issue 4, p472 

    We present the formal semantics of a novel language, called EqL, for first-order functional and Horn logic programming. An EqL program is a set of conditional pattern-directed rules, where the conditions are expressed as a conjunction of equations. The programming paradigm provided by this...

  • Using Annotations to Make Recursion Equations Behave. Schwarz, Jerald // IEEE Transactions on Software Engineering;Jan82, Vol. 8 Issue 1, p21 

    The use of annotated recursion equations as a programming technique is investigated by considering the "telegram problem." The annotations are used to select alternative strategies for evaluating the applicative expressions contained in the recursion equations, while the equations serve as an...

  • Software Engineering - Survey of Reusability Based on Software Component.  // International Journal of Computer Applications;Oct2010, Vol. 8, p39 

    The article presents a study which examines the reusability concepts for component based systems in software engineering. The researchers have explored several existing metrics for both white-box and black box components to measure reusability software domain in frequently used components. The...

  • Static Context Model and Metrics for Assessing the Completeness and Understandability of Static Context Model. Thyagaraju, G. S.; Kulkarni, U. P. // IUP Journal of Computer Sciences;Jul2012, Vol. 6 Issue 3, p35 

    Though the number of context-aware applications is increasing day by day along with the users, there is no generic programming paradigm for context-aware applications. This situation could be remedied by designing and developing an appropriate context modeling and programming paradigm for...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics