We describe in this paper our implementation of the Xenstored service which is part of the XEN architecture. Xenstored maintains a hierarchical and transactional database, used for storing and managing configuration v...
详细信息
ISBN:
(纸本)9781605583327
We describe in this paper our implementation of the Xenstored service which is part of the XEN architecture. Xenstored maintains a hierarchical and transactional database, used for storing and managing configuration values. We demonstrate in this paper that mixing functional data-structures together with reference cell comparison, which is a limited form of pointer comparison, is: (i) safe;and (ii) efficient. this demonstration is based, first, on an axiomatization of operations on the treelike structure we used to represent the Xenstored database. From this axiomatization, we then derive an efficient algorithm for coalescing concurrent transactions modifying that structure. Finally, we experimentally compare the performance of our implementation, that we called OXenstored, and the C implementation of the Xenstored service distributed withthe XEN hypervisor sources: the results show that OXenstored is much more efficient than its C counterpart. As a direct result of this work, OXenstored will be included in future releases of XENSERVER, the virtualization product distributed by Citrix Systems, where it will replace the current implementation of the Xenstored service.
I explore programming withthe dependently typed functional language, AGDA. I present the progress which AGDA has made, demonstrate its usage in a small development, reflect critically on the state of the art, and spe...
详细信息
High-level scripting languages have become tremendously popular for development of dynamic Web applications. Many programmers appreciate the productivity benefits of automatic storage management, freedom from verbose ...
详细信息
ISBN:
(纸本)9781450336697
High-level scripting languages have become tremendously popular for development of dynamic Web applications. Many programmers appreciate the productivity benefits of automatic storage management, freedom from verbose type annotations, and so on. While it is often possible to improve performance substantially by rewriting an application in C or a similar language, very few programmers bother to do so, because of the consequences for human development effort. this paper describes a compiler that makes it possible to have most of the best of both worlds, coding Web applications in a high-level language but compiling to native code with performance comparable to handwritten C code. the source language is Ur/Web, a domain-specific, purely functional, statically typed language for the Web. through a coordinated suite of relatively straightforward program analyses and algebraic optimizations, we transform Ur/Web programs into almost-idiomatic C code, with no garbage collection, little unnecessary memory allocation for intermediate values, etc. Our compiler is in production use for commercial Web sites supporting thousands of users, and microbenchmarks demonstrate very competitive performance versus mainstream tools.
this document illustrates how functional implementations of formal semantics ( structural operational semantics, reduction semantics, small-step and big-step abstract machines, natural semantics, and denotational sema...
详细信息
ISBN:
(纸本)9781595939197
this document illustrates how functional implementations of formal semantics ( structural operational semantics, reduction semantics, small-step and big-step abstract machines, natural semantics, and denotational semantics) can be transformed into each other. these transformations were foreshadowed by Reynolds in "Definitional Interpreters for Higher-Order programming Languages" for functional implementations of denotational semantics, natural semantics, and big-step abstract machines using closure conversion, CPS transformation, and defunctionalization. Over the last few years, the author and his students have further observed that functional implementations of small-step and of big-step abstract machines are related using fusion by fixed-point promotion and that functional implementations of reduction semantics and of small-step abstract machines are related using refocusing and transition compression. It furthermore appears that functional implementations of structural operational semantics and of reduction semantics are related as well, also using CPS transformation and defunctionalization. this further relation provides an element of answer to Felleisen's conjecture that any structural operational semantics can be expressed as a reduction semantics: for deterministic languages, a reduction semantics is a structural operational semantics in continuation style, where the reduction context is a defunctionalized continuation. As the defunctionalized counterpart of the continuation of a one-step reduction function, a reduction context represents the rest of the reduction, just as an evaluation context represents the rest of the evaluation since it is the defunctionalized counterpart of the continuation of an evaluation function.
Severely resource-constrained devices present a confounding challenge to the functional programmer: we are used to having powerful abstraction facilities at our fingertips, but how can we make use of these tools on a ...
详细信息
ISBN:
(纸本)9781595939197
Severely resource-constrained devices present a confounding challenge to the functional programmer: we are used to having powerful abstraction facilities at our fingertips, but how can we make use of these tools on a device with an 8-or 16-bit CPU and at most tens of kilobytes of RAM? Motivated by this challenge, we have developed Flask, a domain specific language embedded in Haskell that brings the power of functionalprogramming to sensor networks, collections of highly resource-constrained devices. Flask consists of a staging mechanism that cleanly separates node-level code from the meta-language used to generate node-level code fragments;syntactic support for embedding standard sensor network code;a restricted subset of Haskell that runs on sensor networks and constrains program space and time consumption;a higher-level "data stream" combinator library for quickly constructing sensor network programs;and an extensible runtime that provides commonly-used services. We demonstrate Flask through several small code examples as well as a compiler that generates node-level code to execute a network-wide query specified in a SQL-like language. We show how using Flask ensures constraints on space and time behavior. through microbenchmarks and measurements on physical hardware, we demonstrate that Flask produces programs that are efficient in terms of CPU and memory usage and that can run effectively on existing sensor network hardware.
A three-year study collected information bearing on the question of whether studying mathematics improves programming skills. An analysis of the data revealed significant differences in the programming effectiveness o...
详细信息
ISBN:
(纸本)9781581137569
A three-year study collected information bearing on the question of whether studying mathematics improves programming skills. An analysis of the data revealed significant differences in the programming effectiveness of two populations of students: (1) those who studied discrete mathematics through examples focused on reasoning about software and (2) those who studied the same mathematical topics illustrated with more traditional examples. functionalprogramming played a central role in the study because it provides a straightforward framework for the presentation of concepts such as predicate logic and proof by induction. Such topics can be covered in depth, staying almost entirely within the context of reasoning about software. the intricate complexities in logic that mutable variables carry withthem need not arise, early on, to confuse novices struggling to understand new ideas. In addition, because functional languages provide useful and compact ways to express mathematical concepts, and because the choice of notation in mathematics courses is often at the discretion of the instructor (in contrast to the notational restrictions often fiercely guarded by the faculty in programming courses), discrete mathematics courses, as they are found in most computer science programs, provide an easy opportunity to enhance the education of students by exposing them to functionalprogramming concepts.
Many datatype-generic functions need access to the recursive positions in the structure of the datatype, and therefore adopt a fixed point view on datatypes. Examples include variants of fold that traverse the data fo...
详细信息
ISBN:
(纸本)9781605583327
Many datatype-generic functions need access to the recursive positions in the structure of the datatype, and therefore adopt a fixed point view on datatypes. Examples include variants of fold that traverse the data following the recursive structure, or the Zipper data structure that enables navigation along the recursive positions. However, Hindley-Milner-inspired type systems with algebraic datatypes make it difficult to express fixed points for anything but regular datatypes. Many real-life examples such as abstract syntax trees are in fact systems of mutually recursive datatypes and therefore excluded. Using Haskell's GADTs and type families, we describe a technique that allows a fixed-point view for systems of mutually recursive datatypes. We demonstrate that our approach is widely applicable by giving several examples of generic functions for this view, most prominently the Zipper.
To the extent that modular reasoning forms the conceptual foundation for good software engineering principles, the failure of modular reasoning in current aspect-oriented programming (AOP) systems is cause for concern...
详细信息
To the extent that modular reasoning forms the conceptual foundation for good software engineering principles, the failure of modular reasoning in current aspect-oriented programming (AOP) systems is cause for concern. this paper discusses a reconceptualization of AOP that will allow an eventual reconciliation between AOP and modular reasoning.
Current languages allow a programmer to describe an interface only by enumerating its parts, possibly including other interfaces wholesale. Such languages cannot express relationships between interfaces, yet when inde...
详细信息
ISBN:
(纸本)9781595930644
Current languages allow a programmer to describe an interface only by enumerating its parts, possibly including other interfaces wholesale. Such languages cannot express relationships between interfaces, yet when independently developed software components are combined into a larger system, significant relationships arise, To address this shortcoming, we define, as a conservative extension of ML, a language for manipulating interfaces. Our language includes operations for adding, renaming, and removing components;for changing the type associated with a value;for making manifest types abstract and vice versa;and for combining interfaces. these operations can express useful relationships among interfaces. We have defined a formal semantics in which an interface denotes a group of four sets;we show how these sets determine a subtyping relation, and we sketch the elaboration of an interface into its denotation.
A tree transducer is a set of mutually recursive functions transforming an input tree into an output tree. Macro tree transducers extend this recursion scheme by allowing each function to be defined in terms of an arb...
详细信息
ISBN:
(纸本)9781450323895
A tree transducer is a set of mutually recursive functions transforming an input tree into an output tree. Macro tree transducers extend this recursion scheme by allowing each function to be defined in terms of an arbitrary number of accumulation parameters. In this paper, we show how macro tree transducers can be concisely represented in Haskell, and demonstrate the benefits of utilising such an approach with a number of examples. In particular, tree transducers afford a modular programming style as they can be easily composed and manipulated. Our Haskell representation generalises the original definition of (macro) tree transducers, abolishing a restriction on finite state spaces. However, as we demonstrate, this generalisation does not affect compositionality.
暂无评论