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.
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.
functionalprogramming languages ought to play a central role in mathematics education for middle schools (age range: 10-14). After all, functionalprogramming is a form of algebra and programming is a creative activi...
详细信息
ISBN:
(纸本)9781605583327
functionalprogramming languages ought to play a central role in mathematics education for middle schools (age range: 10-14). After all, functionalprogramming is a form of algebra and programming is a creative activity about problem solving. Introducing it into mathematics courses would make pre-algebra course come alive. If input and output were invisible, students could implement fun simulations, animations, and even interactive and distributed games all while using nothing more than plain mathematics. We have implemented this vision with a simple framework for purely functional I/O. Using this framework, students design, implement, and test plain mathematical functions over numbers, booleans, string, and images. then the framework wires them up to devices and performs all the translation from external information to internal data (and vice versa) just like every other operating system. Once middle school students are hooked on this form of programming, our curriculum provides a smooth path for them from pre-algebra to freshman courses in college on object-oriented design and theorem proving.
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.
In this paper, we introduce languages as first-class citizens as a sub-paradigm of language-oriented programming. In this approach, language definitions are in the context of a general purpose programming language wit...
详细信息
ISBN:
(纸本)9781450360296
In this paper, we introduce languages as first-class citizens as a sub-paradigm of language-oriented programming. In this approach, language definitions are in the context of a general purpose programming language withthe same status as any other expression. In particular, language definitions are elevated to be run-time values, that can be assigned to variables, passed to functions, returned by functions, and inserted into lists, to name a few possibilities. this approach offers flexible features in the run-time creation and modification of languages, and may promote new idioms in language-oriented programming. As a proof of concept, we have designed and implemented LANG-N-PLAY, a functional language with languages as first-class citizens. We present the features of LANG-N-PLAY with an example, and show that they naturally enable dynamic programming scenarios.
An interactive graphical environment for supporting the development and use of Haskell applications programs is described. the environment, named Vital, is particularly intended for supporting the open-ended, incremen...
详细信息
An interactive graphical environment for supporting the development and use of Haskell applications programs is described. the environment, named Vital, is particularly intended for supporting the open-ended, incremental development style often preferred by non-specialist users in which successive steps of program development are motivated and informed by results so far obtained. Significant features of Vital include: the graphical display of data structures in a format defined by a datatype-indexed stylesheet, the way that evaluation of (possibly infinite) values is demand-driven by the action of the user scrolling around an unbounded workspace, and support for copy-and-paste graphical editing of data structures. this latter allows, for example, the user to modify a complex data structure by point-and-click operations, or to create (by functional evaluation) a regular data structure and then edit values or expressions into it: the effect of each editing operation is immediately reflected in the Haskell program source code.
暂无评论