2008 · 73 citations · 21 references
ComputingComputer ScienceFormal MethodsLogicProgramming LanguagesData TypesFunctional ProgrammingPredicate LogicType CheckingType SystemsDatatypes TheoryFunctional Language DesignHigher-order LogicLogical Framework ApproachOperational SemanticsStructural Operational Semantics
This paper explores a new point in the design space of functional programming: functional programming with dependently-typed higher-order data structures described in the logical framework LF. This allows us to program with proofs as higher-order data. We present a decidable bidirectional type system that distinguishes between dependently-typed data and computations. To support reasoning about open data, our foundation makes contexts explicit. This provides us with a concise characterization of open data, which is crucial to elegantly describe proofs. In addition, we present an operational semantics for this language based on higherorder pattern matching for dependently typed objects. Based on this development, we prove progress and preservation
21
Dependent types in practical programming
Hongwei Xi, Frank Pfenning · 1999 · 584 citations · Full text
Simple unification-based type inference for GADTs
Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich et al. · 2006 · 336 citations
Conor McBride, James McKinna · Journal of Functional Programming · 2004 · 327 citations · Full text