We present a new interface for practical functional Reactive programming (FRP) that (1) is close in spirit to the original FRP ideas, (2) does not have the original space-leak problems, without using arrows or advance...
详细信息
ISBN:
(纸本)9781450336697
We present a new interface for practical functional Reactive programming (FRP) that (1) is close in spirit to the original FRP ideas, (2) does not have the original space-leak problems, without using arrows or advanced types, and (3) provides a simple and expressive way for performing I/O actions from FRP code. We also provide a denotational semantics for this new interface, and a technique (using Kripke logical relations) for reasoning about which FRP functions may "forget their past", i.e. which functions do not have an inherent space-leak. Finally, we show how we have implemented this interface as a Haskell library called FRPNow.
We present the design and implementation of a SQL query processor that outperforms existing database systems and is written in just about 500 lines of Scala code - a convincing case study that high-level functional pr...
详细信息
ISBN:
(纸本)9781450336697
We present the design and implementation of a SQL query processor that outperforms existing database systems and is written in just about 500 lines of Scala code - a convincing case study that high-level functionalprogramming can handily beat C for systems-level programming where the last drop of performance matters. the key enabler is a shift in perspective towards generative programming. the core of the query engine is an interpreter for relational algebra operations, written in Scala. Using the open-source LMS Framework (Lightweight Modular Staging), we turn this interpreter into a query compiler with very low effort. To do so, we capitalize on an old and widely known result from partial evaluation known as Futamura projections, which state that a program that can specialize an interpreter to any given input program is equivalent to a compiler. In this pearl, we discuss LMS programming patterns such as mixed-stage data structures (e.g. data records with static schema and dynamic field components) and techniques to generate low-level C code, including specialized data structures and data loading primitives.
this paper presents a personal, qualitative case study of a first course using How to Design Programs and its functional teaching languages. the paper reconceptualizes the book's six-step design process as an eigh...
详细信息
ISBN:
(纸本)9781450328739
this paper presents a personal, qualitative case study of a first course using How to Design Programs and its functional teaching languages. the paper reconceptualizes the book's six-step design process as an eight-step design process ending in a new "review and refactor" step. It recommends specific approaches to students' difficulties with function descriptions, function templates, data examples, and other parts of the design process. It connects the process to interactive "world programs." It recounts significant, informative missteps in course design and delivery. Finally, it identifies some unsolved teaching problems and some potential solutions.
the proceedings contain 20 papers. the topics discussed include: UTC time, formally verified;VCFloat2: floating-point error analysis in coq;the last yard: foundational end-to-end verification of high-speed cryptograph...
ISBN:
(纸本)9798400704888
the proceedings contain 20 papers. the topics discussed include: UTC time, formally verified;VCFloat2: floating-point error analysis in coq;the last yard: foundational end-to-end verification of high-speed cryptography;rooting for efficiency: mechanized reasoning about array-based trees in separation logic;compositional verification of concurrent C programs with search structure templates;unification for subformula linking under quantifiers;PfComp: a verified compiler for packet filtering leveraging binary decision diagrams;memory simulations, security and optimization in a verified compiler;lean formalization of extended regular expression matching with lookarounds;certification of confluence- and commutation-proofs via parallel critical pairs;a temporal differential dynamic logic formal embedding;and strictly monotone Brouwer trees for well-founded recursion over multiple arguments.
Proof assistants like Coq, Lean, or HOL4 rely heavily on stateful meta-programs called scripts to assemble proofs. Unlike pen-and-paper proofs, proof scripts only describe the steps to take (induct on x, apply a theor...
详细信息
ISBN:
(纸本)9781450381765
Proof assistants like Coq, Lean, or HOL4 rely heavily on stateful meta-programs called scripts to assemble proofs. Unlike pen-and-paper proofs, proof scripts only describe the steps to take (induct on x, apply a theorem,.), not the states that these steps lead to;as a result, plain proof scripts are essentially incomprehensible without the assistance of an interactive user interface able to run the script and show the corresponding proof states. Until now, the standard process to communicate a proof without forcing readers to execute its script was to manually copy-paste intermediate proof states into the script, as source code comments - a tedious and error-prone exercise. Additional prose (such as for a book or tutorial) was likewise embedded in comments, preserving executability at the cost of a mediocre text-editing experience. this paper describes a new approach to the development and dissemination of literate proof scripts, with a focus on the Coq proof assistant. Specifically, we describe two contributions: a compiler that interleaves Coq's output withthe original proof script to produce interactive webpages that are complete, self-contained presentations of Coq proofs;and a new literate programming toolkit that allows authors to switch seamlessly between prose- and code-oriented views of the same sources, by translating back and forth between reStructuredText documents and literate Coq source files. In combination, these tools offer a new way to write, communicate, and preserve proofs, combining the flexibility of procedural proof scripts and the intelligibility of declarative proofs.
functional Reactive programming (FRP) is an approach to the development of reactive systems which provides a pure functional interface, but which may be implemented as an abstraction of an imperative event-driven laye...
详细信息
ISBN:
(纸本)9781450323260
functional Reactive programming (FRP) is an approach to the development of reactive systems which provides a pure functional interface, but which may be implemented as an abstraction of an imperative event-driven layer. FRP systems typically provide a model of behaviours (total time-indexed values, implemented as pull systems) and event sources (partial time-indexed values, implemented as push systems). In this paper, we investigate a type system for event-driven FRP programs which provide liveness guarantees, that is every input event is guaranteed to generate an output event. We show that FRP can be implemented on top of a model of sets and relations, and that the isomorphism between event sources and behaviours corresponds to the isomorphism between relations and set-valued functions. We then implement sets and relations using a model of continuations using the usual double-negation CPS transform. the implementation of behaviours as pull systems based on futures, and of event sources as push systems based on the observer pattern, thus arises from first principles. We also discuss a Java implementation of the FRP model.
Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have ...
详细信息
ISBN:
(纸本)9781595930644
Writing loops with tail-recursive function calls is the equivalent of writing them with goto's. Given that loop packages for Lisp-family languages have been around for over 20 years, it is striking that none have had much success in the Scheme world. I suggest the reason is that Scheme forces us to be precise about the scoping of the various variables introduced by our loop forms, something previous attempts to design ambitious loop forms have not managed to do. I present the design of a loop package for Scheme with a well-defined and natural scoping rule, based on a notion of control dominance that generalizes the standard lexical-scope rule of the lambda-calculus. the new construct is powerful, clear, modular and extensible. the loop language is defined in terms of an underlying language for expressing control-flow graphs. this language itself has interesting properties as an intermediate representation.
Cody, Hazel, and theo, two experienced Haskell programmers and an expert in automata theory, develop an elegant Haskell program for matching regular expressions: (i) the program is purely functional;(ii) it is overloa...
详细信息
ISBN:
(纸本)9781605587943
Cody, Hazel, and theo, two experienced Haskell programmers and an expert in automata theory, develop an elegant Haskell program for matching regular expressions: (i) the program is purely functional;(ii) it is overloaded over arbitrary semirings, which not only allows to solve the ordinary matching problem but also supports other applications like computing leftmost longest matchings or the number of matchings, all with a single algorithm;(iii) it is more powerful than other matchers, as it can be used for parsing every context-free language by taking advantage of laziness. the developed program is based on an old technique to turn regular expressions into finite automata which makes it efficient both in terms of worst-case time and space bounds and actual performance: despite its simplicity, the Haskell implementation can compete with a recently published professional C++ program for the same problem.
We describe the implementation of first-class polymorphic delimited continuations in the programming language Scala. We use Scala's pluggable typing architecture to implement a simple type and effect system, which...
详细信息
ISBN:
(纸本)9781605583327
We describe the implementation of first-class polymorphic delimited continuations in the programming language Scala. We use Scala's pluggable typing architecture to implement a simple type and effect system, which discriminates expressions with control effects from those without and accurately tracks answer type modification incurred by control effects. To tackle the problem of implementing first-class continuations under the adverse conditions brought upon by the Java VM, we employ a selective CPS transform, which is driven entirely by effect-annotated types and leaves pure code in direct style. Benchmarks indicate that this high-level approach performs competitively.
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.
暂无评论