| 1. |
- Aronsson, Markus, 1990, et al.
(author)
-
Stream Processing for Embedded Domain Specific Languages
- 2014
-
In: Proceedings of the 26nd 2014 International Symposium on Implementation and Application of Functional Languages. - New York, NY, USA : ACM. - 9781450332842 ; 01, s. 1-12
-
Conference paper (peer-reviewed)abstract
- We present a library for expressing digital signal processing (DSP) algorithms using a deeply embedded domain-specific language (EDSL) in Haskell. The library supports definitions in functional programming style, reducing the gap between the mathematical description of streaming algorithms and their implementation. The deep embedding makes it possible to generate efficient C code without any overhead associated with the high-level programming model. The signal processing library is intended to be an extension of the Feldspar EDSL which, until now, has had a rather low-level interface for dealing with synchronous streams. However, the presented library is independent of the underlying expression language, and can be used to extend any pure EDSL for which a C code generator exists with efficient stream processing capabilities. The library is evaluated using example implementations of common DSP algorithms and the generated code is compared to its handwritten counterpart.
|
|
| 2. |
- Axelsson, Emil, 1978
(author)
-
A Functional Language-Based Approach to Low-Level Hardware Design
- 2006
-
Licentiate thesis (other academic/artistic)abstract
- The semiconductor industry is facing increasing problems with designing complex circuits with tight constraints on area, performance and power consumption. Worse still, these circuits must be designed and verified very quickly. The existing design tools have great problems with handling the complexity of the designs, and time consuming manual intervention is often needed in order to reach a satisfactory result.One factor in this increasing complexity is the fact that routing wires dominate logical gates in today's high-performance circuits when non-functional properties such as signal delay and power consumption are considered.In conventional design methods, information about routing wires is not included until the later design stages, so that bad choices early on are not discovered until after the time consuming physical design stage.In order to overcome this problem, we need design methods which take wire effects into account right from the start. This requires better abstraction techniques that faithfully model the lower-level implications, even when working at a high level of abstraction.We propose a system called {\em Wired}, which allows layout- and wire-aware design at higher abstraction level than any similar approach that we know of. Wired is based on a simple relational programming language, which in turn, is embedded in the functional programming language Haskell. This gives a very powerful and flexible system for describing low-level aware circuit generators.Combining Wired with Lava -- a similar system, but with less support for the analysis of low-level properties -- gives a powerful design flow in which a design can start off as a relatively high-level functional Lava description, and then be gradually refined into a low-level Wired description.We demonstrate through case studies of parallel prefix networks that the link between the high-level and the low-level description can be made very clear, allowing changes to be propagated up and down through the abstractions.The system supports the analysis of non-functional properties that depend on wire effects. In particular, a bidirectional analysis that calculates RC-delays has been implemented, exploiting the fact that Wired is a relational programming language. This, combined with succinct circuit descriptions, enables rapid design exploration, in which candidate designs are compared for performance.
|
|
| 3. |
- Axelsson, Emil, 1978
(author)
-
A generic abstract syntax model for embedded languages
- 2012
-
In: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - New York, NY, USA : ACM. - 0730-8566. - 9781450310543 ; 47:9, s. 323-334
-
Conference paper (peer-reviewed)abstract
- Representing a syntax tree using a data type often involves having many similar-looking constructors. Functions operating on such types often end up having many similar-looking cases. Different languages often make use of similar-looking constructions. We propose a generic model of abstract syntax trees capable of representing a wide range of typed languages. Syntactic constructs can be composed in a modular fashion enabling reuse of abstract syntax and syntactic processing within and across languages. Building on previous methods of encoding extensible data types in Haskell, our model is a pragmatic solution to Wadler's "expression problem". Its practicality has been confirmed by its use in the implementation of the embedded language Feldspar.
|
|
| 4. |
- Axelsson, Emil, 1978
(author)
-
Compilation as a Typed EDSL-to-EDSL Transformation
- 2016
-
Reports (other academic/artistic)abstract
- This article is about an implementation and compilation technique that is used in RAW-Feldspar which is a complete rewrite of the Feldspar embedded domain-specific language (EDSL) (Axelsson et al. 2010). Feldspar is high-level functional language that generates efficient C code to run on embedded targets. The gist of the technique presented in this post is the following: rather writing a back end that converts pure Feldspar expressions directly to C, we translate them to a low-level monadic EDSL. From the low-level EDSL, C code is then generated. This approach has several advantages:1. The translation is simpler to write than a complete C back end.2. The translation is between two typed EDSLs, which rules out many potential errors.3. The low-level EDSL is reusable and can be shared between several high-level EDSLs.Although the article contains a lot of code, most of it is in fact reusable. As mentioned in Discussion, we can write the same implementation in less than 50 lines of code using generic libraries that we have developed to support Feldspar.
|
|
| 5. |
- Axelsson, Emil, 1978
(author)
-
Efficient and Compositional Evaluation of Untyped Expressions
- 2014
-
In: Trends in Functional Programming.
-
Conference paper (other academic/artistic)abstract
- We give an efficient and compositional implementation of evaluation for an untyped representation of expressions. Building on Baars and Swierstra's "Typing Dynamic Typing", all tag checking is deferred to an initial dynamic compilation phase after which evaluation proceeds without any tag checking. The technique lends itself particularly well to a compositional implementation, where parts of the expression are defined separately, and this is also where we see the highest performance gains.
|
|
| 6. |
- Axelsson, Emil, 1978
(author)
-
Efficient Evaluation for Untyped and Compositional Representations of Expressions
- 2014
-
Reports (other academic/artistic)abstract
- This report gives a simple implementation of A. Baars and S.D. Swierstra's "Typing Dynamic Typing" using modern (GHC) Haskell features, and shows that the technique is especially beneficial in a compositional setting, where parts of the expression are defined separately.Evaluating expressions that are represented as algebraic data types typically requires using tagged unions to represent values. Tagged unions can introduce runtime overhead due to tag checking, and this overhead is unnecessary if the evaluated expression is well-typed. Likewise, pattern matching on the constructors of the expression causes overhead which is unnecessary if the same expression is evaluated multiple times. Typing Dynamic Typing solves both of these problems by deferring all tag checking to an initial "dynamic compilation" phase after which evaluation proceeds without any tag checking or pattern matching. The problems of tag checking and pattern matching are worse in a compositional setting, and our measurements show that the technique gives especially good performance gains for compositional expressions.
|
|
| 7. |
|
|
| 8. |
- Axelsson, Emil, 1978, et al.
(author)
-
Feldspar: A Domain Specific Language for Digital Signal Processing algorithms
- 2010
-
In: Eighth ACM/IEEE International Conference on Formal Methods and Models for Codesign. - 9781424478859 ; , s. 169-178
-
Conference paper (peer-reviewed)abstract
- A new language, Feldspar, is presented, enabling high-level and platform-independent description of digital signal processing (DSP) algorithms. Feldspar is a pure functional language embedded in Haskell. It offers a high-level dataflow style of programming, as well as a more mathematical style based on vector indices. The key to generating efficient code from such descriptions is a high-level optimization technique called vector fusion. Feldspar is based on a low-level, functional core language which has a relatively small semantic gap to machine-oriented languages like C. The core language serves as the interface to the back-end code generator, which produces C. For very small examples, the generated code performs comparably to hand-written C code when run on a DSP target. While initial results are promising, to achieve good performance on larger examples, issues related to memory access patterns and array copying will have to be addressed.
|
|
| 9. |
- Axelsson, Emil, 1978, et al.
(author)
-
Feldspar: Application and Implementation
- 2012
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 7241, s. 402-439
-
Conference paper (peer-reviewed)abstract
- The Feldspar project aims to develop a domain specific language for Digital Signal Processing algorithm design. From functional descriptions, imperative code (currently C) is generated. The project partners are Ericsson, Chalmers and ELTE, Budapest. The background and motivation for the project have been documented elsewhere [3]. We aim to raise the level of abstraction at which algorithm developers and implementors work, and to generate, from Feldspar descriptions, the kind of code that is currently written by hand. These lecture notes first give a brief introduction to Feldspar and the style of programming that it encourages. Next, we document the implementation of Feldspar as a domain specific language (DSL), embedded in Haskell. The implementation is built using a library called Syntactic that was built for this purpose, but also designed to be of use to other implementors of embedded domain specific languages. We show the implementation of Feldspar in sufficient detail to give the reader an understanding of how the use of the Syntactic library enables the modular construction of an embedded DSL. For those readers who would like to apply these techniques to their own DSL embedded in Haskell, further instructions are given in section 5. The programming examples are available in the CEFP directory of the Feldspar package, version 0.5.0.1: http://hackage.haskell.org/package/ feldspar-language-0.5.0.1 The code can be fetched by running: > cabal unpack feldspar-language-0.5.0.1 All code is written in Haskell, and has been tested using the Glasgow Haskell Compiler (GHC), version 7.0.2, and the packages syntactic-0.8 feldspar-language-0.5.0.1 feldspar-compiler-0.5.0.1
|
|
| 10. |
|
|
| 11. |
- Axelsson, Emil, 1978
(author)
-
Functional Programming Enabling Flexible Hardware Design at Low Levels of Abstraction
- 2008
-
Doctoral thesis (other academic/artistic)abstract
- Continuous down-scaling of sizes in VLSI circuits causes low-level electrical phenomena to become more and more prominent performance stoppers in modern chip technologies. This forces designers to work at a lower level of abstraction than desired in order to gain control over these effects. The most dominating contributors to low-level performance problems are the routing wires, which are used to connect the gates (computational units) on the chip. Hardware description languages (HDLs) – which naturally strive for generality and reusablility – tend to focus on higher levels of abstraction. This means that the low-level effects are not visible and thus very hard to control. To date, we are not aware of any HDL that allows control over the effects of routing wires in a really useful way, so when high-performance is crucial, designers are left to interfacing directly with CAD tools for physical chip design.This thesis presents a flexible wire-aware design system called Wired and shows how it has developed from a preliminary idea to a relatively mature system that can now be tried on real-world challenges. The present Wired builds upon the existing HDL Lava, and extends it with: (a) finer control over geometry, (b) support for geometrical refinement, (c) more accurate performance models, (d) basic wire-awareness, and (e) support for descriptions with abstract signal flow.Wired is implemented in the functional programming language Haskell. It has a simple modular implementation consisting of three separate main components: (1) The Lava library, for representing the structural circuit view, (2) a new monadic library for expressing layout, and (3) a new library for light-weight logical variables.The system is used to improve the accuracy of an algorithm for searching for fast, low-power parallel prefix networks. More experiments are needed in order to reach industrially applicable results, but the main contribution here is the fact that physically aware design exploration is actually achievable at this level of flexibility. Although not yet tested on industrial problems, Wired seems like a very promising system that has a good potential of reducing the effort of generating high-quality layouts of complex circuits.
|
|
| 12. |
- Axelsson, Emil, 1978, et al.
(author)
-
Lightweight Higher-Order Rewriting in Haskell
- 2015
-
In: Trends in Functional Programming.
-
Conference paper (other academic/artistic)abstract
- We present a generic Haskell library for expressing rewrite rules with a safe treatment of variables and binders. Both sides of the rules are written as typed EDSL expressions, which leads to syntactically appealing rules and hides the underlying term representation. Matching is defined as an instance of Miller's pattern unification, which makes for efficient execution when rules are applied in a bottom-up fashion. The restrictions of pattern unification are captured in the types of the library, and we show by example that the library is capable of expressing useful simplifications that might be used in a compiler.
|
|
| 13. |
- Axelsson, Emil, 1978, et al.
(author)
-
Lightweight Higher-Order Rewriting in Haskell
- 2016
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 9547, s. 1-21
-
Conference paper (peer-reviewed)abstract
- We present a generic Haskell library for expressing rewrite rules with a safe treatment of variables and binders. Both sides of the rules are written as typed EDSL expressions, which leads to syntactically appealing rules and hides the underlying term representation. Matching is defined as an instance of Miller's higher-order pattern unification and has the same complexity as first-order matching. The restrictions of pattern unification are captured in the types of the library, and we show by example that the library is capable of expressing useful simplifications that might be used in a compiler.
|
|
| 14. |
- Axelsson, Emil, 1978, et al.
(author)
-
Teaching Hardware Description and Verification
- 2005
-
In: 2005 International Conference on Microelectronic Systems Education. - 0769523749 ; , s. 119-120
-
Conference paper (peer-reviewed)abstract
- We outline the course "Hardware Description and Verification", taught at the department of computing science, and how the course and our research benefit from each other.
|
|
| 15. |
- Axelsson, Emil, 1978, et al.
(author)
-
The Design and Implementation of Feldspar: An Embedded Language for Digital Signal Processing
- 2011
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783642242755 ; 6647, s. 121-136
-
Conference paper (peer-reviewed)abstract
- Feldspar is a domain specific language, embedded in Haskell, for programming digital signal processing algorithms. The final aim of a Feldspar program is to generate low level code with good performance. Still, we chose to provide the user with a purely functional DSL. The language is implemented as a minimal, deeply embedded core language, with shallow extensions built upon it. This paper presents full details of the essential parts of the implementation. Our initial conclusion is that this approach works well in our domain, although much work remains.
|
|
| 16. |
- Axelsson, Emil, 1978, et al.
(author)
-
The Design and Implementation of Feldspar: an Embedded Language for Digital Signal Processing
- 2010
-
In: IFL 2010, the 22nd Symposium on Implementation and Application of Functional Languages.
-
Conference paper (other academic/artistic)abstract
- Feldspar is a Domain Specific Language, embedded in Haskell, for programming Digital Signal Processing algorithms. The final aim of a Feldspar program is to generate low level code with good performance. Still, we chose to provide the user with a purely functional DSL. The language is implemented as a minimal, deeply embedded core language, with shallow extensions built upon it. This paper presents full details of the essential parts of the implementation. Our initial conclusion is that this approach works well in our domain, although much work remains.
|
|
| 17. |
- Axelsson, Emil, 1978, et al.
(author)
-
Using Circular Programs for Higher-Order Syntax Functional pearl
- 2013
-
In: SIGPLAN Notices (ACM Special Interest Group on Programming Languages). - : Association for Computing Machinery (ACM). - 0730-8566 .- 0362-1340 .- 1558-1160. ; 48:9, s. 257-262
-
Journal article (peer-reviewed)abstract
- This pearl presents a novel technique for constructing a first-order syntax tree directly from a higher-order interface. We exploit circular programming to generate names for new variables, resulting in a simple yet efficient method. Our motivating application is the design of embedded languages supporting variable binding, where it is convenient to use higher-order syntax when constructing programs, but first-order syntax when processing or transforming programs.
|
|
| 18. |
- Axelsson, Emil, 1978, et al.
(author)
-
Using circular programs for higher-order syntax: Functional pearl
- 2013
-
In: Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP. - New York, NY, USA : ACM. - 9781450323260 ; , s. 257-262
-
Conference paper (peer-reviewed)abstract
- This pearl presents a novel technique for constructing a firstorder syntax tree directly from a higher-order interface. We exploit circular programming to generate names for new variables, resulting in a simple yet efficient method. Our motivating application is the design of embedded languages supporting variable binding, where it is convenient to use higher-order syntax when constructing programs, but firstorder syntax when processing or transforming programs.
|
|
| 19. |
- Axelsson, Emil, 1978, et al.
(author)
-
Using Lava and Wired for Design Exploration
- 2006
-
In: Proceedings of the sixth international workshop on designing correct circuits, March, Vienna, Mary Sheeran and Tom Melham (editors).
-
Journal article (other academic/artistic)abstract
- Lava has been used successfully in structural circuit description and layout generation for FPGAs. It has been demonstrated that Lava is suitable for describing so-called "clever" or adaptive circuits -- circuits whose structure adapts to various properties of their contexts. This can be incorporated quite naturally into the descriptions due to the fact that Lava is embedded in the powerful functional programming language Haskell.The rising problems associated with chip design in the deep sub-micron (DSM) era calls for new methods that are able to account for low-level effects already in higher-level descriptions. In particular, interconnect wires need to be modeled in order to get reliable estimates of non-functional properties, such as delay and power consumption.We are working on a system -- Wired -- which aims to bring the ideas from Lava down to lower levels. What distinguishes Wired from other layout-aware languages is the fact that we are modeling Wires explicitly, and that we can have adaptive descriptions whose structure adapts to accurate estimates of, for example, signal delays in their context.Here we demonstrate a flow for design exploration using parallel prefix circuits \cite{PP} as example. The descriptions start of in Lava, and are then transformed, surprisingly smoothly, into corresponding Wired descriptions. We demonstrate several classic parallel prefix structures as well as a family of new ones.Wired has the capability of performing a number of different signal analyses on the descriptions. We can, for example, analyse for signal flow direction and delay. Our most advanced delay model uses Elmore approximation to appropriately take account of fanout and load capacitance. We will use the available analysis methods to compare the different parallel prefix structures. Hopefully, we will also be able to demonstrate examples of delay-adaptive circuits in time for the DCC workshop.
|
|
| 20. |
- Axelsson, Emil, 1978, et al.
(author)
-
Wired - a Language for Describing Non-Functional Properties of Digital Circuits
- 2004
-
In: Proceedings of International Workshop on Designing Correct Circuits. Barcelona, Spain, March 2004.
-
Conference paper (other academic/artistic)abstract
- Increasingly, designers need to estimate non-functional properties such as area, power consumption and timing, even when working at a high level of abstraction, early in the design. In deep sub-micron processes, it is the routing wires that account for most of the power consumption and signal delays. So, information about the wires is vital for controlling non-functional properties. To deal with more and more complex constructions, current design methods and languages strive towards higher and higher levels of abstraction, and provide only very limited possibilities for low-level control. Often, detailed information about wire properties is only available in the very last design stages - after placement and routing. We propose a language, Wired, that aims to bridge this gap in abstraction levels. The main idea is construction with combinators and higher-order connection patterns. The key to the usefulness of this style is that the combinators have both functional and geometric interpretations. This allows us to construct circuits at high-level, without loosing control over lower levels. Wired goes further than previous methods in that it offers more precise and flexible control over the geometry.
|
|
| 21. |
- Axelsson, Emil, 1978
(author)
-
Wired: Wire-aware Circuit Description
- 2005
-
In: Proceedings of TECHCON, Semiconductor Research Corporation. Portland, Oregon, Oct 2005.
-
Conference paper (other academic/artistic)abstract
- As we strive towards higher abstraction levels, the designer can lose control over low-level details, which eventually turn out to have significant impact on circuit performance. In particular, it is the routing wires that dominate the non-functional properties of circuits in deep sub-micron technologies. In the proposed system, called Wired, the designer can express circuit function together with detailed placement of cells and wires, in order to get more precise control over the result. The system allows direct analysis of non-functional properties, and in fact, the result of such analyses can be used to guide instantiation decisions. Case studies show that common structures, such as parallel prefix computations, and even non-trivial versions, are described efficiently in Wired.
|
|
| 22. |
- Axelsson, Emil, 1978, et al.
(author)
-
Wired: Wire-Aware Circuit Design
- 2005
-
In: Correct Hardware Design and Verification Methods. - 3540291059 ; 3725, s. 5-19
-
Conference paper (peer-reviewed)
|
|
| 23. |
- Bahr, Patrick, et al.
(author)
-
Generalising tree traversals and tree transformations to DAGs: Exploiting sharing without the pain
- 2017
-
In: Science of Computer Programming. - : Elsevier BV. - 0167-6423. ; 137, s. 63-97
-
Journal article (peer-reviewed)abstract
- We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recursion scheme allows the programmer to implement a tree traversal or a tree transformation and then apply it to compact graph representations of trees instead. The resulting graph traversal or graph transformation avoids recomputation of intermediate results for shared nodes – even if intermediate results are used in different contexts. Consequently, this approach leads to asymptotic speedup proportional to the compression provided by the graph representation. In general, however, this sharing of intermediate results is not sound. Therefore, we complement our implementation of the recursion scheme with a number of correspondence theorems that ensure soundness for various classes of traversals. We illustrate the practical applicability of the implementation as well as the complementing theory with a number of examples.
|
|
| 24. |
- Bahr, Patrick, et al.
(author)
-
Generalising Tree Traversals to DAGs - Exploiting Sharing Without the Pain
- 2015
-
In: Proceedings of the 2015 Workshop on Partial Evaluation and Program Manipulation. - New York, NY, USA : ACM. - 9781450332972 ; , s. 27-38
-
Conference paper (peer-reviewed)abstract
- We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recursion scheme allows the programmer to implement a tree traversal and then apply it to compact graph representations of trees instead. The resulting graph traversals avoid recomputation of intermediate results for shared nodes -- even if intermediate results are used in different contexts. Consequently, this approach leads to asymptotic speedup proportional to the compression provided by the graph representation. In general, however, this sharing of intermediate results is not sound. Therefore, we complement our implementation of the recursion scheme with a number of correspondence theorems that ensure soundness for various classes of traversals. We illustrate the practical applicability of the implementation as well as the complementing theory with a number of examples.
|
|
| 25. |
- Dévai, Gergely, et al.
(author)
-
Efficient Code Generation from the High-level Domain-specific Language Feldspar for DSPs
- 2010
-
In: ODES-8: 8th Workshop on Optimizations for DSP and Embedded Systems, workshop associated with IEEE/ACM International Symposium on Code Generation and Optimization (CGO).
-
Conference paper (peer-reviewed)abstract
- Software for digital signal processors (DSPs) is traditionally highly hardware-dependent and hence porting it to new processors usually requires significant design effort. In this paper we present Feldspar (Functional Embedded Language for DSP and Parallelism), an embedded, high-level, domain-specific language for DSP algorithm design and the compilation techniques we developed for generating C code from specifications written in Feldspar. While Feldspar allows description of algorithms on specification level, we show that with the right set of abstractions and transformations this high level, functional specification can be transformed into C code that is comparable or better than reference, hand-crafted C language implementations. The Feldspar compiler is highly modular and plugin-based, hence future hardware-specific plugins will enable automatic generation of efficient, hardware-specific code. This approach enables the encapsulation of knowledge of hardware completely in the compiler and thus allows description of algorithms in completely hardware-independent, portable manner.
|
|
| 26. |
- Naylor, Matthew, et al.
(author)
-
A Functional-Logic Library for Wired
- 2007
-
In: Proceedings of International Workshop on Hardware Design and Functional Languages. Braga, Portugal, March 2007. ; , s. 95-113
-
Conference paper (other academic/artistic)abstract
- We develop a Haskell library for functional-logic programming and apply it to the implementation of Wired, a relational language for describing and analysing circuits at the VLSI-layout level. Compared to a previous library for logic programming by Claessen, our main contribution is to add support for residuation. Compared to the published paper on Wired, we implement a useful version of the language while demonstrating the use of relations rather than functions in the design of high-performance circuits. Finally, we evaluate the success of our library by comparing it with the dedicated functional-logic language Curry.
|
|
| 27. |
- Naylor, Matthew, et al.
(author)
-
A Functional-Logic Library for Wired
- 2007
-
In: Proceedings of the ACM SIGPLAN 2007 Haskell Workshop. Freiburg, Germany, Sept 2007. - New York, NY, USA : ACM. - 9781595936745 ; , s. 37-48
-
Conference paper (peer-reviewed)abstract
- We develop a Haskell library for functional-logic programming, motivated by the implementation of Wired, a relational embedded domain-specific language for describing and analysing digital circuits at the VLSI-layout level. Compared to a previous library for logic programming by Claessen and Ljunglöf, we support residuation, easier creation of logical data types, and pattern matching. We discuss other applications of our library, including test-data generation, and various extensions, including lazy narrowing.
|
|
| 28. |
- Persson, Anders, 1972, et al.
(author)
-
Generic Monadic Constructs for Embedded Languages
- 2012
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 7257
-
Conference paper (peer-reviewed)abstract
- We present a library of generic monadic constructs for embedded languages. It is an extension of Syntactic, a Haskell library for defining and processing generic abstract syntax. Until now, Syntactic has been mostly suited to implement languages based on pure, side effect free, expressions. The presented extension allows the pure expressions to also contain controlled side effects, enabling the representation of expressions that rely on destructive updates for efficiency. We demonstrate the use- fulness of the extension by giving examples from the embedded language Feldspar which is implemented using Syntactic.
|
|
| 29. |
- Persson, Anders, 1972, et al.
(author)
-
Generic monadic constructs for embedded languages
- 2011
-
In: IFL 2011, the 23rd Symposium on Implementation and Application of Functional Languages.
-
Conference paper (other academic/artistic)abstract
- We present a library for generic monadic constructs for em- bedded languages. It is an extension of Syntactic, a Haskell library for defining and processing generic abstract syntax. Syntactic works best to implement languages based on pure, side effect free, expressions. The presented extension allows the pure expressions to also contain controlled side effects, enabling efficient representation of expressions that rely on destructive updates for efficiency.
|
|
| 30. |
- Persson, Anders, 1972, et al.
(author)
-
Programmable Signatures
- 2015
-
In: Trends in Functional Programming.
-
Conference paper (other academic/artistic)abstract
- When compiling EDSLs into other languages, types in the source language must be translated into corresponding types in the target language. The translation is often driven by a small set of rules that map a single type in the source language into a single type in the target language. However, this simple approach is limiting when there are multiple possible mappings, and it may lead to poor interoperability and performance in the generated code. Instead of hard-wiring a single set of translation rules into a compiler, this paper introduces a small language that lets the programmer describe the mapping of each argument and function separately.
|
|
| 31. |
- Persson, Anders, 1972, et al.
(author)
-
Programmable Signatures
- 2016
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Cham : Springer International Publishing. - 1611-3349 .- 0302-9743. ; 9547, s. 124-135
-
Conference paper (peer-reviewed)abstract
- When compiling Embedded Domain Specific Languages (EDSLs) into other languages, the compiler translates types in the source language into corresponding types in the target language. The translation is often driven by a small set of rules that map a single type in the source language into a single type in the target language. This simple approach is limiting when there are multiple possible mappings, and it may lead to poor interoperability and poor performance in the generated code. Instead of hard-wiring a single set of translation rules into a compiler, this paper introduces a small language that lets the programmer describe the mapping of each argument and function separately.
|
|
| 32. |
|
|
| 33. |
- Svenningsson, Josef, 1976, et al.
(author)
-
Combining Deep and Shallow Embedding for EDSL
- 2013
-
In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783642404467 ; 7829, s. 21-36
-
Conference paper (peer-reviewed)abstract
- When compiling embedded languages it is natural to use an abstract syntax tree to represent programs. This is known as a deep embedding and it is a rather cumbersome technique compared to other forms of embedding, typically leading to more code and being harder to extend. In shallow embeddings, language constructs are mapped directly to their semantics which yields more flexible and succinct implementations. But shallow embeddings are not well-suited for compiling embedded languages. We present a technique to combine deep and shallow embedding in the context of compiling embedded languages in order to provide the benefits of both techniques. In particular it helps keeping the deep embedding small and it makes extending the embedded language much easier. Our technique also has some unexpected but welcome knock-on effects. It provides fusion of functions to remove intermediate results for free without any additional effort. It also helps to give the embedded language a more natural programming interface.
|
|
| 34. |
- Svenningsson, Josef, 1976, et al.
(author)
-
Combining deep and shallow embedding of domain-specific languages
- 2015
-
In: Computer Languages, Systems and Structures. - : Elsevier BV. - 1477-8424. ; 44, s. 143-165
-
Journal article (peer-reviewed)abstract
- We present a technique to combine deep and shallow embedding in the context of compiling embedded languages in order to provide the benefits of both techniques. When compiling embedded languages it is natural to use an abstract syntax tree to represent programs. This is known as a deep embedding and it is a rather cumbersome technique compared to other forms of embedding, typically leading to more code and being harder to extend. In shallow embeddings, language constructs are mapped directly to their semantics which yields more flexible and succinct implementations. But shallow embeddings are not well-suited for compiling embedded languages.Our technique uses a combination of deep and shallow embedding, which helps keeping the deep embedding small and makes extending the embedded language much easier. The technique also has some unexpected but welcome secondary effects. It provides fusion of functions to remove intermediate results for free without any additional effort. It also helps us to give the embedded language a more natural programming interface.
|
|
| 35. |
- Svenningsson, Josef, 1976, et al.
(author)
-
Efficient Monadic Streams
- 2015
-
In: Trends in Functional Programming.
-
Conference paper (other academic/artistic)abstract
- Functional stream representations allow for a high-level, compositional way of programming digital signal processing algorithms. However, some algorithms, such as filters, cannot be efficiently implemented using purely functional techniques, due to excessive copying of data. We present a monadic representation of streams which introduces the ability to use mutation for efficiency when implementing algorithms. Still, our representation enjoys many of the benefits of purely functional streams, such as a functional API and fusion. Our representation enables further optimizations: we show how to remove duplicate loop variables, and how to keep buffers entirely in references. Our measurements show that the new monadic representation consistently outperforms the functional representation by at least a factor of four when evaluated in the context of the Feldspar embedded DSL.
|
|
