Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Outrageous but meaningful coincidences : dependent type-safe syntax and evaluation

Mcbride, Conor (2010) Outrageous but meaningful coincidences : dependent type-safe syntax and evaluation. [Proceedings Paper]

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

Tagless interpreters for well-typed terms in some object language are a standard example of the power and benefit of precise indexing in types, whether with dependent types, or generalized algebraic datatypes. The key is to reflect object language types as indices (however they may be constituted) for the term datatype in the host language, so that host type coincidence ensures object type coincidence. Whilst this technique is widespread for simply typed object languages, dependent types have proved a tougher nut with nontrivial computation in type equality. In their type-safe representations, Danielsson [2006] and Chapman [2009] succeed in capturing the equality rules, but at the cost of representing equality derivations explicitly within terms. This article constructs a type-safe representation for a dependently typed object language, dubbed KIPLING, whose computational type equality just appropriates that of its host, Agda. The KIPLING interpreter example is not merely de rigeur - it is key to the construction. At the heart of the technique is that key component of generic programming, the universe.

Item type: Proceedings Paper
ID code: 34657
Keywords: programming techniques, applicative programming, functional programming, design , languages, theory, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
    Depositing user: Pure Administrator
    Date Deposited: 13 Nov 2011 15:05
    Last modified: 23 Aug 2013 12:36
    URI: http://strathprints.strath.ac.uk/id/eprint/34657

    Actions (login required)

    View Item