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.
Type providers [16], pioneered in the F# programming language, are a practical and powerful means of gaining the benefits of a modern static type system when working with data schemas that are defined outside of the p...
详细信息
ISBN:
(纸本)9781450323895
Type providers [16], pioneered in the F# programming language, are a practical and powerful means of gaining the benefits of a modern static type system when working with data schemas that are defined outside of the programming language, such as relational databases. F# type providers are implemented using a form of compile-time code generation, which requires the compiler to expose an internal API and can undermine type safety. We show that with dependent types it is possible to define a type provider mechanism that does not rely on code generation. Using this mechanism, a type provider becomes a kind of generic program that is instantiated for a particular external schema, which can be represented using an ordinary datatype. Because these dependent type providers use the ordinary abstraction mechanisms of the type system, they preserve its safety properties. We evaluate the practicality of this technique and explore future extensions.
the proceedings contain 8 papers. the topics discussed include: histo- and dynamorphisms revisited;generic datatypes á la carte;dependent type providers;N queens problem: a metaprogramming stress test for the com...
ISBN:
(纸本)9781450323895
the proceedings contain 8 papers. the topics discussed include: histo- and dynamorphisms revisited;generic datatypes á la carte;dependent type providers;N queens problem: a metaprogramming stress test for the compiler;usage of generic programming on hackage - experience report;multi-polymorphic programming in bondi;programming macro tree transducers;and generic representations of tree transformations.
We present an application of reduction and higher-order functions in a recent computer-aided composition project. Our objective is the generation of control data for the Chant sound synthesizer using OpenMusic (OM), a...
详细信息
Generic programming language constructs, tools and libraries have been available in Haskell since the first report on the programming language Haskell. At the beginning of the 1990s generic programming techniques coul...
详细信息
ISBN:
(纸本)9781450323895
Generic programming language constructs, tools and libraries have been available in Haskell since the first report on the programming language Haskell. At the beginning of the 1990s generic programming techniques could be used via the deriving construct, and since then numerous generic programming libraries and tools have been developed. At the time of writing, the categories 'generic' and 'generics' on Hackage, the online repository of Haskell software, contain 53 packages. Although not all of these are generic programming libraries or tools, there are many approaches to generic programming to choose from. this brief paper discusses an analysis of the usage of generic programming language constructs, tools, and libraries. We analyse how often which language constructs, tools, and libraries are used on Hackage, how often class instances are derived generically or written manually, and for some libraries, how often the functions that appear in these libraries are used.
We investigate the use of functionalprogramming to develop a numerical linear algebra run-time;i.e. a framework where the solvers can be adapted easily to different contexts and task parallelism can be attained (semi...
详细信息
Programs written using a deterministic-by-construction model of parallel computation are guaranteed to always produce the same observable results, offering programmers freedom from subtle, hard-to-reproduce nondetermi...
详细信息
the proceedings contain 6 papers. the topics discussed include: Bluespec and Haskell;functional synthesis of genetic regulatory networks;encoding secure information flow with restricted delegation and revocation in Ha...
ISBN:
(纸本)9781450323802
the proceedings contain 6 papers. the topics discussed include: Bluespec and Haskell;functional synthesis of genetic regulatory networks;encoding secure information flow with restricted delegation and revocation in Haskell;QuaFL: a typed DSL for quantum programming;embrace, defend, extend: a methodology for embedding preexisting DSLs: case in point, StreamHs: StreamIT in Haskell;abstract resource cost derivation for logical quantum circuit descriptions;and sensitivity analysis using type-based constraints.
the proceedings contain 5 papers. the topics discussed include: correct-by-construction pretty-printing;new equations for neutral terms: a sound and complete decision procedure, formalized;a multi-valued language with...
ISBN:
(纸本)9781450323840
the proceedings contain 5 papers. the topics discussed include: correct-by-construction pretty-printing;new equations for neutral terms: a sound and complete decision procedure, formalized;a multi-valued language with a dependent type system;relational algebraic ornaments;and leveling up dependent types: generic programming over a predicative hierarchy of universes.
Dynamic programming algorithms embody a widely used programming technique that optimizes recursively defined equations that have repeating subproblems. the standard solution uses arrays to share common results between...
详细信息
ISBN:
(纸本)9781450323895
Dynamic programming algorithms embody a widely used programming technique that optimizes recursively defined equations that have repeating subproblems. the standard solution uses arrays to share common results between successive steps, and while effective, this fails to exploit the structural properties present in these problems. Histomorphisms and dynamorphisms have been introduced to expresses such algorithms in terms of structured recursion schemes that leverage this structure. In this paper, we revisit and relate these schemes and show how they can be expressed in terms of recursion schemes from comonads, as well as from recursive coalgebras. Our constructions rely on properties of bialgebras and dicoalgebras, and we are careful to consider optimizations and efficiency concerns. throughout the paper we illustrate these techniques through several worked-out examples discussed in a tutorial style, and show how a recursive specification can be expressed both as an array-based algorithm as well as one that uses recursion schemes.
暂无评论