Recent research has shown how boilerplate code, or repetitive code for traversing datatypes, can be eliminated using generic programming techniques already available within some implementations of Haskell. One particu...
详细信息
ISBN:
(纸本)9781595930644
Recent research has shown how boilerplate code, or repetitive code for traversing datatypes, can be eliminated using generic programming techniques already available within some implementations of Haskell. One particularly intractable kind of boilerplate is nameplate, or code having to do with names, name-binding, and fresh name generation. One reason for the difficulty is that operations on data structures involving names, as usually implemented, are not regular instances of standard map, fold, or zip operations. However, in nominal abstract syntax, an alternative treatment of names and binding based on swapping, operations such as a-equivalence, capture-avoiding substitution, and free variable set functions are much better-behaved. In this paper, we show how nominal abstract syntax techniques similar to those of FreshML can be provided as a Haskell library called FreshLib. In addition, we show how existing generic programming techniques can be used to reduce the amount of nameplate code that needs to be written for new datatypes involving names and binding to almost nothing-in short, how to scrap your nameplate.
We present a new way of embedding functional languages into the Coq proof assistant by using meta-programming. this allows us to develop the meta-theory of the language using the deep embedding and provides a convenie...
详细信息
ISBN:
(纸本)9781450370974
We present a new way of embedding functional languages into the Coq proof assistant by using meta-programming. this allows us to develop the meta-theory of the language using the deep embedding and provides a convenient way for reasoning about concrete programs using the shallow embedding. We connect the deep and the shallow embeddings by a soundness theorem. As an instance of our approach, we develop an embedding of a core smart contract language into Coq and verify several important properties of a crowd-funding contract based on a previous formalisation of smart contract execution in blockchains.
Applied Type System (ATS) is recently proposed as a framework for designing and formalizing (advanced) type systems in support Of practical programming. In ATS, the definition of type equality involves a constraint re...
详细信息
ISBN:
(纸本)9781595930644
Applied Type System (ATS) is recently proposed as a framework for designing and formalizing (advanced) type systems in support Of practical programming. In ATS, the definition of type equality involves a constraint relation, which may or may not be algorithmically decidable. To support practical programming, we adopted a design in the past that imposes certain restrictions on the syntactic form of constraints so that some effective means can be found for solving constraints automatically. Evidently, this is a rather ad hoc design in its nature. In this paper, we rectify the situation by presenting a fundamentally different design, which we claim to be both novel and practical. Instead of imposing syntactical restrictions on constraints, we provide a means for the programmer to construct proofs that attest to the validity of constraints. In particular, we are to accommodate a programming paradigm that enables the programmer to combine programming withtheorem proving. Also we present some concrete examples in support of the practicality of this design.
In this paper a language-based approach to functionally correct imperative programming is proposed. the approach is based on a programming language called RSP1, which combines dependent types, general recursion, and i...
详细信息
ISBN:
(纸本)9781595930644
In this paper a language-based approach to functionally correct imperative programming is proposed. the approach is based on a programming language called RSP1, which combines dependent types, general recursion, and imperative features in a type-safe way, while preserving decidability of type checking. the methodology used is that of internal verification, where programs manipulate programmer-supplied proofs explicitly as data. the fundamental technical idea of RSP1 is to identify problematic operations as impure, and keep them out of dependent types. the resulting language is powerful enough to verify statically non-trivial properties of imperative and functional programs. the paper presents the ideas through the examples of statically verified merge sort, statically verified imperative binary search trees, and statically verified directed acyclic graphs.
this paper presents AURA, a programming language for access control that treats ordinary programming constructs (e.g., integers and recursive functions) and authorization logic constructs (e.g., principals and access ...
详细信息
ISBN:
(纸本)9781595939197
this paper presents AURA, a programming language for access control that treats ordinary programming constructs (e.g., integers and recursive functions) and authorization logic constructs (e.g., principals and access control policies) in a uniform way. AURA is based on polymorphic DCC and uses dependent types to permit assertions that refer directly to AURA values while keeping computation out of the assertion level to ensure tractability. the main technical results of this paper include fully mechanically verified proofs of the decidability and soundness for AURA's type system, and a prototype typechecker and interpreter.
By allowing the programmer to write code that can generate code at run-time, meta-programming offers a powerful approach to program construction. For instance, meta-programming can often be employed to enhance program...
详细信息
ISBN:
(纸本)9781581137569
By allowing the programmer to write code that can generate code at run-time, meta-programming offers a powerful approach to program construction. For instance, meta-programming can often be employed to enhance program efficiency and facilitate the construction of generic programs. However, meta-programming, especially in an untyped setting, is notoriously error-prone. In this paper, we aim at making meta-programming less error-prone by providing a type system to facilitate the construction of correct meta-programs. We first introduce some code constructors for constructing typeful code representation in which program variables are replaced with deBruijn indices, and then formally demonstrate how such typeful code representation can be used to support meta-programming. the main contribution of the paper lies in recognition and then formalization of a novel approach to typed meta-programmingthat is practical, general and flexible.
A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly. the key to handling large data objects th...
详细信息
ISBN:
(纸本)9781450308656
A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly. the key to handling large data objects that are subject to relatively small modifications is to process the updates incrementally. Incrementality has been explored in the semi-structured settings of relational databases and graph transformations;this flexibility in structure makes it relatively easy to divide the data into separate parts that can be transformed and updated independently. the same is not true if the data is to be encoded with more general-purpose algebraic datatypes, with transformations defined as functions: dividing data into well-typed separate parts is tricky, and recursions typically create inter-dependencies. In this paper, we study transformations that support incremental updates, and devise a constructive process to achieve this incrementality.
A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly with respect to some laws. One way to redu...
详细信息
ISBN:
(纸本)9781450336697
A bidirectional transformation is a pair of mappings between source and view data objects, one in each direction. When the view is modified, the source is updated accordingly with respect to some laws. One way to reduce the development and maintenance effort of bidirectional transformations is to have specialized languages in which the resulting programs are bidirectional by construction-giving rise to the paradigm of bidirectional programming. In this paper, we develop a framework for applicative-style and higher-order bidirectional programming, in which we can write bidirectional transformations as unidirectional programs in standard functional languages, opening up access to the bundle of language features previously only available to conventional unidirectional languages. Our framework essentially bridges two very different approaches of bidirectional programming, namely the lens framework and Voigtlander's semantic bidirectionalization, creating a new programming style that is able to bag benefits from both.
this paper describes our experience using a functional language, Haskell, to build an embedded, domain-specific language (DSL) for component configuration in large-scale, real-time, embedded systems. Prior to the intr...
详细信息
ISBN:
(纸本)9781595939197
this paper describes our experience using a functional language, Haskell, to build an embedded, domain-specific language (DSL) for component configuration in large-scale, real-time, embedded systems. Prior to the introduction of the DSL, engineers would describe the steps needed to configure a particular system in a handwritten XML document. In this paper, we outline the application domain, give a brief overview of the DSL that we developed, and provide concrete data to demonstrate its effectiveness. In particular, we show that the DSL has several significant benefits over the original, XML-based approach including reduced code size, increased modularity and scalability, and detection and prevention of common defects. For example, using the DSL, we were able to produce clear and intuitive descriptions of component configurations that were sometimes less than 1/30 of the size of the original XML.
this paper describes FC++: a rich library supporting functionalprogramming in C++. Prior approaches to encoding higher order functions in C++ have suffered with respect to polymorphic functions from either lack of ex...
详细信息
ISBN:
(纸本)9781581132021
this paper describes FC++: a rich library supporting functionalprogramming in C++. Prior approaches to encoding higher order functions in C++ have suffered with respect to polymorphic functions from either lack of expressiveness or high complexity. In contrast, FC++ offers full and concise support for higher-order polymorphic functions through a novel use of C++ type inference. Another new element in FC++ is that it implements a subtype polymorphism policy for functions, in addition to the more common parametric polymorphism facilities. Subtype polymorphism is common in object oriented languages and ensures that functions in FC++ fit well within the C++ object model. Apart from these conceptual differences, FC++ is also an improvement in technical terms over previous efforts in the literature. Our function objects are reference-counted and can be aliased without needing to be copied, resulting in an efficient implementation. the reference-counting mechanism is also exported to the user as a general-purpose replacement of native C++ pointers. Finally, we supply a number of useful functional operators (a large part of the Haskell Standard prelude) to facilitate programming with FC++. the end result is a library that is usable and efficient, while requiring no extensions to the base C++ language.
暂无评论