C.B. Poulsen
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
34 records found
1
WebDSL is a DSL for creating web applications, combining many different aspects and domains of web design in a single language. The dynamic semantics of this language are not defined, despite multiple attempts, abandoned due to complexity of the language and lack of expression of chosen frameworks. We adapt the algebraic effects and handlers approach and the framework introduced in Datatypes a la carte (Swierstra, 2008) to create a modular denotational semantics model of WebDSL, extending the framework by a bifunctor formulation for multi-sort syntax definition that allows us to distinguish between effects raised by different components of the language. In the process of defining the framework and semantics in Haskell, we encountered obstacles and of working with algebraic effects and handlers paradigm in the language, leading us to compile workarounds, solutions and pitfalls to avoid when constructing and maintaining such model. In evaluation of the framework approach with earlier attempts at defining dynamic semantics for WebDSL, we find algebraic effects and handlers to be a viable and successful approach for modelling a rich DSL such as WebDSL, and propose possible improvements to the WebDSL compiler.
...
WebDSL is a DSL for creating web applications, combining many different aspects and domains of web design in a single language. The dynamic semantics of this language are not defined, despite multiple attempts, abandoned due to complexity of the language and lack of expression of chosen frameworks. We adapt the algebraic effects and handlers approach and the framework introduced in Datatypes a la carte (Swierstra, 2008) to create a modular denotational semantics model of WebDSL, extending the framework by a bifunctor formulation for multi-sort syntax definition that allows us to distinguish between effects raised by different components of the language. In the process of defining the framework and semantics in Haskell, we encountered obstacles and of working with algebraic effects and handlers paradigm in the language, leading us to compile workarounds, solutions and pitfalls to avoid when constructing and maintaining such model. In evaluation of the framework approach with earlier attempts at defining dynamic semantics for WebDSL, we find algebraic effects and handlers to be a viable and successful approach for modelling a rich DSL such as WebDSL, and propose possible improvements to the WebDSL compiler.
The process of using formal verification, in order to ensure that a piece of software meets it functional requirements consists of three main steps: designing a model of the given piece of software, translating the functional requirements, which the piece of software must satisfy, into properties of said model and verifying that the model satisfies those properties. Traditionally, regardless of whether the piece of software is developed based on a predesigned model or the piece of software is developed first and its model is designed after that, the piece of software and its model are two separate entities. Therefore, aside from checking that the model satisfies its properties, it must also be verified that the model accurately represents the given piece of software. While this task may initially seem simple, it gets progressively more difficult, as the piece of software becomes more complex. And, if it turns out that the model is not accurate, then the entire formal verification process is invalid, since it does not provide any guarantees about the actual piece of software. In this thesis we present a solution to this problem: a way of modelling sequential effectful programs, such that the resulting models can be directly translated into runnable programs, thereby guaranteeing the models' accuracy. We achieve this by using algebraic effects, in order to model sequential effectful programs as instances of the coinductive free monad, that could then be translated into runnable pieces of software by applying the necessary effect handlers. Furthermore, we demonstrate that it is possible to express functional requirements as properties of such models using the first-order modal μ-calculus, a fixed-point dynamic logic which has previously been used to reason about labelled transition systems (e.g. in mCRL2).
...
The process of using formal verification, in order to ensure that a piece of software meets it functional requirements consists of three main steps: designing a model of the given piece of software, translating the functional requirements, which the piece of software must satisfy, into properties of said model and verifying that the model satisfies those properties. Traditionally, regardless of whether the piece of software is developed based on a predesigned model or the piece of software is developed first and its model is designed after that, the piece of software and its model are two separate entities. Therefore, aside from checking that the model satisfies its properties, it must also be verified that the model accurately represents the given piece of software. While this task may initially seem simple, it gets progressively more difficult, as the piece of software becomes more complex. And, if it turns out that the model is not accurate, then the entire formal verification process is invalid, since it does not provide any guarantees about the actual piece of software. In this thesis we present a solution to this problem: a way of modelling sequential effectful programs, such that the resulting models can be directly translated into runnable programs, thereby guaranteeing the models' accuracy. We achieve this by using algebraic effects, in order to model sequential effectful programs as instances of the coinductive free monad, that could then be translated into runnable pieces of software by applying the necessary effect handlers. Furthermore, we demonstrate that it is possible to express functional requirements as properties of such models using the first-order modal μ-calculus, a fixed-point dynamic logic which has previously been used to reason about labelled transition systems (e.g. in mCRL2).
Addressing the challenge of reasoning about programs across different evaluation strategies has long been a concern in functional programming. Levy's introduction of the call-by-push-value (CBPV) calculus represents a significant step forward in tackling this. His paradigm provided a more powerful approach that can encapsulate both call-by-value and call-by-name that was even later extended to include call-by-need. In this paper we present the development of an interface that integrates the theory of CBPV with algebraic effects and handlers. We demonstrate how this technique enables the definition and execution of programs, highlighting its capability to defer computations across different evaluation strategies and define operations in a modular fashion. We then define and prove a set of laws that can be used with our interface to reason about programs under varying evaluation regimes. This approach not only enhances the flexibility and modularity of language and library implementation but also allows for direct reasoning about these implementations, beyond the meta-level abstraction.
...
Addressing the challenge of reasoning about programs across different evaluation strategies has long been a concern in functional programming. Levy's introduction of the call-by-push-value (CBPV) calculus represents a significant step forward in tackling this. His paradigm provided a more powerful approach that can encapsulate both call-by-value and call-by-name that was even later extended to include call-by-need. In this paper we present the development of an interface that integrates the theory of CBPV with algebraic effects and handlers. We demonstrate how this technique enables the definition and execution of programs, highlighting its capability to defer computations across different evaluation strategies and define operations in a modular fashion. We then define and prove a set of laws that can be used with our interface to reason about programs under varying evaluation regimes. This approach not only enhances the flexibility and modularity of language and library implementation but also allows for direct reasoning about these implementations, beyond the meta-level abstraction.
Algebraic effects and handlers are a new programming technique that allows for the definition of abstractions as interfaces, with handlers providing modular, concrete implementations of these interfaces. In this paper, we consider algebraic effects and handlers implemented in Haskell, and explore how they behave under fixed-point (value) recursion. We give different possible implementations of fixed-point combinators for effectful functions, and work out their evaluation processes. We find that these functions behave very predictably under normal fixed-point recursion, while value recursion seems to be a much harder problem. We discuss the difficulties of implementing value recursion, and several possibile solutions are explored, but the question of whether a fixed-point combinator with value recursion semantics can exist at all in the presence of algebraic effects remains unanswered.
...
Algebraic effects and handlers are a new programming technique that allows for the definition of abstractions as interfaces, with handlers providing modular, concrete implementations of these interfaces. In this paper, we consider algebraic effects and handlers implemented in Haskell, and explore how they behave under fixed-point (value) recursion. We give different possible implementations of fixed-point combinators for effectful functions, and work out their evaluation processes. We find that these functions behave very predictably under normal fixed-point recursion, while value recursion seems to be a much harder problem. We discuss the difficulties of implementing value recursion, and several possibile solutions are explored, but the question of whether a fixed-point combinator with value recursion semantics can exist at all in the presence of algebraic effects remains unanswered.
Concurrency with effects and handlers
Implementing concurrency with nondeterminism using algebraic effects and handlers
Algebraic effects and handlers are a new paradigm in functional programming. They aim at modularly handling side effects, by separating the declaration of those effects, from how they are handled. In this paper, we show how we can leverage their use to create an interface for concurrency using algebraic effects for which we can prove a list of concurrency laws, and also design handlers that allow us to run programs concurrently, thereby demonstrating the practical application of algebraic effects and handlers in managing concurrency.
...
Algebraic effects and handlers are a new paradigm in functional programming. They aim at modularly handling side effects, by separating the declaration of those effects, from how they are handled. In this paper, we show how we can leverage their use to create an interface for concurrency using algebraic effects for which we can prove a list of concurrency laws, and also design handlers that allow us to run programs concurrently, thereby demonstrating the practical application of algebraic effects and handlers in managing concurrency.
When writing functional code that composes multiple recursive functions that operate on a datastrcuture, we often incur a lot of computational overhead allocating memory, only to later read, use, and discard this information.
This can be alleviated using fusion, a technique that combines these multiple recursive datastructure traversals into one.
This thesis explores shortcut fusion using (Co)Church encodings based on the work of Harper (2011), focusing on two questions: What is needed to reliably achieve fusion in Haskell, and the correctness of these transformations through a formalization in Agda.
The first contribution replicates and extends Harper's (Co)Church encodings in Haskell, uncovering optimizer weaknesses and providing practical insights for achieving fusion within Haskell.
The second contribution formalizes these encodings in Agda, leveraging parametricity and the category theory described by Harper.
The formalization proves the equivalence of these encoded functions to the unencoded ones, showing that the encodings are in fact isomorphisms, as long as parametricity (Wadler, 1989) is assumed.
These findings highlight the effectiveness and correctness of shortcut fusion techniques and show the promise of shortcut fusion: Reduce the computational overhead associated with functional programming while retaining its nice, compositional properties. ...
This can be alleviated using fusion, a technique that combines these multiple recursive datastructure traversals into one.
This thesis explores shortcut fusion using (Co)Church encodings based on the work of Harper (2011), focusing on two questions: What is needed to reliably achieve fusion in Haskell, and the correctness of these transformations through a formalization in Agda.
The first contribution replicates and extends Harper's (Co)Church encodings in Haskell, uncovering optimizer weaknesses and providing practical insights for achieving fusion within Haskell.
The second contribution formalizes these encodings in Agda, leveraging parametricity and the category theory described by Harper.
The formalization proves the equivalence of these encoded functions to the unencoded ones, showing that the encodings are in fact isomorphisms, as long as parametricity (Wadler, 1989) is assumed.
These findings highlight the effectiveness and correctness of shortcut fusion techniques and show the promise of shortcut fusion: Reduce the computational overhead associated with functional programming while retaining its nice, compositional properties. ...
When writing functional code that composes multiple recursive functions that operate on a datastrcuture, we often incur a lot of computational overhead allocating memory, only to later read, use, and discard this information.
This can be alleviated using fusion, a technique that combines these multiple recursive datastructure traversals into one.
This thesis explores shortcut fusion using (Co)Church encodings based on the work of Harper (2011), focusing on two questions: What is needed to reliably achieve fusion in Haskell, and the correctness of these transformations through a formalization in Agda.
The first contribution replicates and extends Harper's (Co)Church encodings in Haskell, uncovering optimizer weaknesses and providing practical insights for achieving fusion within Haskell.
The second contribution formalizes these encodings in Agda, leveraging parametricity and the category theory described by Harper.
The formalization proves the equivalence of these encoded functions to the unencoded ones, showing that the encodings are in fact isomorphisms, as long as parametricity (Wadler, 1989) is assumed.
These findings highlight the effectiveness and correctness of shortcut fusion techniques and show the promise of shortcut fusion: Reduce the computational overhead associated with functional programming while retaining its nice, compositional properties.
This can be alleviated using fusion, a technique that combines these multiple recursive datastructure traversals into one.
This thesis explores shortcut fusion using (Co)Church encodings based on the work of Harper (2011), focusing on two questions: What is needed to reliably achieve fusion in Haskell, and the correctness of these transformations through a formalization in Agda.
The first contribution replicates and extends Harper's (Co)Church encodings in Haskell, uncovering optimizer weaknesses and providing practical insights for achieving fusion within Haskell.
The second contribution formalizes these encodings in Agda, leveraging parametricity and the category theory described by Harper.
The formalization proves the equivalence of these encoded functions to the unencoded ones, showing that the encodings are in fact isomorphisms, as long as parametricity (Wadler, 1989) is assumed.
These findings highlight the effectiveness and correctness of shortcut fusion techniques and show the promise of shortcut fusion: Reduce the computational overhead associated with functional programming while retaining its nice, compositional properties.
Errors from side-effecting operations, such as mutable state, error handling, and I/O operations, can be costly during software development. Haskell's monadic approach often obscures specific operations, limiting the ability to reason about them effectively. This paper explores implementing ML-style references in Haskell using algebraic effects separating the syntax and semantics of side-effecting operations.
ML-style references are mutable storage locations, similar to pointers that ensure type safety and allow imperative programming within a functional language. We address how to implement ML-style references in Haskell using algebraic effects while adhering to Staton's state laws. Our contributions include developing an algebraic effect for mutable references, creating a corresponding handler, and proving adherence to Staton’s state laws.
Additionally, we demonstrate the practical application of these principles by proving the correctness of an imperative-style factorial function. This work provides a flexible and predictable framework for using mutable references in Haskell, enhancing the ability to reason about program behaviour and correctness. ...
ML-style references are mutable storage locations, similar to pointers that ensure type safety and allow imperative programming within a functional language. We address how to implement ML-style references in Haskell using algebraic effects while adhering to Staton's state laws. Our contributions include developing an algebraic effect for mutable references, creating a corresponding handler, and proving adherence to Staton’s state laws.
Additionally, we demonstrate the practical application of these principles by proving the correctness of an imperative-style factorial function. This work provides a flexible and predictable framework for using mutable references in Haskell, enhancing the ability to reason about program behaviour and correctness. ...
Errors from side-effecting operations, such as mutable state, error handling, and I/O operations, can be costly during software development. Haskell's monadic approach often obscures specific operations, limiting the ability to reason about them effectively. This paper explores implementing ML-style references in Haskell using algebraic effects separating the syntax and semantics of side-effecting operations.
ML-style references are mutable storage locations, similar to pointers that ensure type safety and allow imperative programming within a functional language. We address how to implement ML-style references in Haskell using algebraic effects while adhering to Staton's state laws. Our contributions include developing an algebraic effect for mutable references, creating a corresponding handler, and proving adherence to Staton’s state laws.
Additionally, we demonstrate the practical application of these principles by proving the correctness of an imperative-style factorial function. This work provides a flexible and predictable framework for using mutable references in Haskell, enhancing the ability to reason about program behaviour and correctness.
ML-style references are mutable storage locations, similar to pointers that ensure type safety and allow imperative programming within a functional language. We address how to implement ML-style references in Haskell using algebraic effects while adhering to Staton's state laws. Our contributions include developing an algebraic effect for mutable references, creating a corresponding handler, and proving adherence to Staton’s state laws.
Additionally, we demonstrate the practical application of these principles by proving the correctness of an imperative-style factorial function. This work provides a flexible and predictable framework for using mutable references in Haskell, enhancing the ability to reason about program behaviour and correctness.
Algebraic effects and handlers has been a popular approach for modelling side-effects in functional programming languages. Focusing on composability and modularity, this approach separates the effectful syntax from its semantics, which helps programmers to create effect abstractions such that their implementation can be modified without changing the syntax. However, there exist mainstream functional programming languages, like Haskell, which lack built-in frameworks to accommodate specifying side-effects in this manner. In this paper, we provide an interface for Haskell's Software Transactional Memory (STM), a concurrency abstraction, in the framework of algebraic effects and handlers from prior literature. We embed our implementation into a simple concurrency model using higher-order effects, in order to demonstrate it is possible to define and execute effectful concurrent programs that obey the semantics of Haskell's STM. Furthermore, we prove that our implementation satisfies the necessary laws governing our interface, such that programmers can easily reason about programs using our STM model.
...
Algebraic effects and handlers has been a popular approach for modelling side-effects in functional programming languages. Focusing on composability and modularity, this approach separates the effectful syntax from its semantics, which helps programmers to create effect abstractions such that their implementation can be modified without changing the syntax. However, there exist mainstream functional programming languages, like Haskell, which lack built-in frameworks to accommodate specifying side-effects in this manner. In this paper, we provide an interface for Haskell's Software Transactional Memory (STM), a concurrency abstraction, in the framework of algebraic effects and handlers from prior literature. We embed our implementation into a simple concurrency model using higher-order effects, in order to demonstrate it is possible to define and execute effectful concurrent programs that obey the semantics of Haskell's STM. Furthermore, we prove that our implementation satisfies the necessary laws governing our interface, such that programmers can easily reason about programs using our STM model.
Building Type Checker Using Scope Graphs
For a Language with Type Classes
In this paper, we explore scope graphs as a formal model for constructing type checkers for programming languages that support type classes. Type classes provide a powerful mechanism for ad hoc-polymorphism and code reuse. Nevertheless, the incorporation of type classes into type checkers poses challenges, as it necessitates the resolution of instances and the assurance of coherence amidst overlapping instances. Our approach facilitates the separation of concerns between type class resolution and type checking, promoting extensibility and maintainability of the type checker. We contribute with a formal definition of scope graphs for languages with type classes, accompanied by algorithms for type class resolution and type checking. To assess the correctness of this approach, we implement a prototype type checker, and conduct experiments on a collection of representative programs. The results demonstrate the effectiveness of this baseline approach.
...
In this paper, we explore scope graphs as a formal model for constructing type checkers for programming languages that support type classes. Type classes provide a powerful mechanism for ad hoc-polymorphism and code reuse. Nevertheless, the incorporation of type classes into type checkers poses challenges, as it necessitates the resolution of instances and the assurance of coherence amidst overlapping instances. Our approach facilitates the separation of concerns between type class resolution and type checking, promoting extensibility and maintainability of the type checker. We contribute with a formal definition of scope graphs for languages with type classes, accompanied by algorithms for type class resolution and type checking. To assess the correctness of this approach, we implement a prototype type checker, and conduct experiments on a collection of representative programs. The results demonstrate the effectiveness of this baseline approach.
Substructural typing imposes additional constraints on variable usage during type checking and requires specialized approaches to ensure type soundness. In this study, we investigate the implementation of a type checker using scope graphs for languages with substructural type systems. Scope graphs, a data structure representing scoping, provide a foundation for defining type checking algorithms. Our research project extends an existing Haskell library, incorporating typing rules for non-substructural, linear, and affine type systems. Through careful examination and comparison of scope graph and calculus implementations, we evaluate their expressiveness, extensibility, and readability. While the scope graph implementation demonstrates promising results, passing all test cases, the calculus implementation encounters unification errors in a subset of the tests. We conclude that the scope graph implementation offers a solid foundation for substructural typing, with potential for easy extension and integration with other language features. However, further work is needed to develop a comprehensive test suite and address the challenges faced by the calculus implementation. By advancing these areas, we can enhance the effectiveness of substructural type checking and enable more reliable and secure programming practices in languages with substructural type systems.
...
Substructural typing imposes additional constraints on variable usage during type checking and requires specialized approaches to ensure type soundness. In this study, we investigate the implementation of a type checker using scope graphs for languages with substructural type systems. Scope graphs, a data structure representing scoping, provide a foundation for defining type checking algorithms. Our research project extends an existing Haskell library, incorporating typing rules for non-substructural, linear, and affine type systems. Through careful examination and comparison of scope graph and calculus implementations, we evaluate their expressiveness, extensibility, and readability. While the scope graph implementation demonstrates promising results, passing all test cases, the calculus implementation encounters unification errors in a subset of the tests. We conclude that the scope graph implementation offers a solid foundation for substructural typing, with potential for easy extension and integration with other language features. However, further work is needed to develop a comprehensive test suite and address the challenges faced by the calculus implementation. By advancing these areas, we can enhance the effectiveness of substructural type checking and enable more reliable and secure programming practices in languages with substructural type systems.
Type-Checking Modules and Imports using Scope Graphs
A Case Study on a Language with Relative, Unordered and Glob Import Semantics
Scope graphs provide a way to type-check real-world programming languages and their constructs. A previous implementation that type-checks the proof-of-concept language LM, a language with relative, unordered, and glob imports, does not halt. This thesis discusses a five-step approach for constructing and type-checking a scope graph of an LM program. Using manually scheduled queries and auxiliary algorithms, type-checking the majority of examples failing in previous literature succeeds. The introduction of breadth-first-traversal and multi-origin querying is discussed as new scope graph primitives to aid in the reusability of this thesis for type-checkers that require stratified resolution.
...
Scope graphs provide a way to type-check real-world programming languages and their constructs. A previous implementation that type-checks the proof-of-concept language LM, a language with relative, unordered, and glob imports, does not halt. This thesis discusses a five-step approach for constructing and type-checking a scope graph of an LM program. Using manually scheduled queries and auxiliary algorithms, type-checking the majority of examples failing in previous literature succeeds. The introduction of breadth-first-traversal and multi-origin querying is discussed as new scope graph primitives to aid in the reusability of this thesis for type-checkers that require stratified resolution.
Building Type Checkers Using Scope Graphs
Scope Graph-Based Type Checking for a Scala Subset
This paper investigates the viability of using scope graphs to implement type checkers for programming languages, specifically for a Scala subset. The primary objective is to determine if scope graphs can offer a declarative and extensible approach to type checking. To achieve this, we used a phased Haskell library to implement such a type checker. The declarativity and feature extensibility of the approach were evaluated by means of comparation with Rouvoet et al.'s approach in mini-Statix. The results demonstrate that using scope graphs as a basis for type checking yields a modular and extensible solution compared to traditional methods. However, it is noted that this approach may sacrifice a certain degree of declarativity. These findings suggest that scope graphs are a promising tool for type checking, particularly in the context of name binding. Further research is recommended to explore the possibility of implementing similar type checkers for other programming languages. Additionally, the paper suggests incorporating additional features into the targeted Scala subset, thereby enhancing its extensibility.
...
...
This paper investigates the viability of using scope graphs to implement type checkers for programming languages, specifically for a Scala subset. The primary objective is to determine if scope graphs can offer a declarative and extensible approach to type checking. To achieve this, we used a phased Haskell library to implement such a type checker. The declarativity and feature extensibility of the approach were evaluated by means of comparation with Rouvoet et al.'s approach in mini-Statix. The results demonstrate that using scope graphs as a basis for type checking yields a modular and extensible solution compared to traditional methods. However, it is noted that this approach may sacrifice a certain degree of declarativity. These findings suggest that scope graphs are a promising tool for type checking, particularly in the context of name binding. Further research is recommended to explore the possibility of implementing similar type checkers for other programming languages. Additionally, the paper suggests incorporating additional features into the targeted Scala subset, thereby enhancing its extensibility.
For algebraic effects and handlers, we know both small-step and big-step operational semantics and we are familiar with denotational semantics. But, what is missing is a structured showing that one is equivalent to the other. On top of this, most efficient implementations of algebraic effects and handlers closely resemble their denotational semantics by encoding operations in what is called the free monad. In this work, we often refer to these implementations as freer monad-based embeddings of effects and handlers. These embeddings enable programmers to write effectful programs as though they are monadic programs. However, the derivation of such an embedding from an operational semantics remains thusfar unexplored. This work fills in the gap between a denotational interpreter derived by inverse closure conversion and the freer monad-based embedding of effects and handlers. We thus define and show program transformations that extend the steps needed to transform a denotational interpreter to a small-step interpreter and vice versa.
...
For algebraic effects and handlers, we know both small-step and big-step operational semantics and we are familiar with denotational semantics. But, what is missing is a structured showing that one is equivalent to the other. On top of this, most efficient implementations of algebraic effects and handlers closely resemble their denotational semantics by encoding operations in what is called the free monad. In this work, we often refer to these implementations as freer monad-based embeddings of effects and handlers. These embeddings enable programmers to write effectful programs as though they are monadic programs. However, the derivation of such an embedding from an operational semantics remains thusfar unexplored. This work fills in the gap between a denotational interpreter derived by inverse closure conversion and the freer monad-based embedding of effects and handlers. We thus define and show program transformations that extend the steps needed to transform a denotational interpreter to a small-step interpreter and vice versa.
Tydi-Chisel
Collaborative and Interface-Driven Data-Streaming Accelerator Design
In spite of progress on hardware design languages, the design of high-performance hardware accelerators forces many design decisions specializing the interfaces of these accelerators in ways that complicate the understanding of the design and hinder modularity and collaboration. In response to this challenge, Tydi has been presented as an open specification for streaming dataflow designs in digital circuits, allowing designers to express how composite and variable-length data structures are transferred over streams using clear, data-centric types. Earlier efforts in providing an implementation framework for Tydi managed to generate VHDL boilerplate code for Tydi interfaces, but offered limited design value over custom solutions due to VHDL's low abstraction level. In contrast, Chisel, with its high level of abstraction and customizability offers a suitable platform to implement Tydi-based components.
In this thesis, the Tydi-Chisel library is presented along with an A-to-Z design-process description for data-streaming accelerators. A stream-interface solution is presented that offers both compatibility with Tydi in traditional HDLs and maximum utility within Chisel through two intercompatible representations. In addition, design complexity is reduced through novel utilities like stream-complexity conversion, developed to alleviate interface specification mismatches between components. Using the presented toolchain and library, the amount of code required to specify Tydi interfaces for representative use-cases can be reduced several times compared to a Verilog description, while offering increased utility.
Tydi-Chisel aims to simplify the design of data-streaming accelerators through the integration of the Tydi interface standard in Chisel, along with helper components, syntax sugar, and verification tools. In combination Chisel and Tydi help bridge the hardware-software divide, making solo-design and collaboration between designers easier. ...
In this thesis, the Tydi-Chisel library is presented along with an A-to-Z design-process description for data-streaming accelerators. A stream-interface solution is presented that offers both compatibility with Tydi in traditional HDLs and maximum utility within Chisel through two intercompatible representations. In addition, design complexity is reduced through novel utilities like stream-complexity conversion, developed to alleviate interface specification mismatches between components. Using the presented toolchain and library, the amount of code required to specify Tydi interfaces for representative use-cases can be reduced several times compared to a Verilog description, while offering increased utility.
Tydi-Chisel aims to simplify the design of data-streaming accelerators through the integration of the Tydi interface standard in Chisel, along with helper components, syntax sugar, and verification tools. In combination Chisel and Tydi help bridge the hardware-software divide, making solo-design and collaboration between designers easier. ...
In spite of progress on hardware design languages, the design of high-performance hardware accelerators forces many design decisions specializing the interfaces of these accelerators in ways that complicate the understanding of the design and hinder modularity and collaboration. In response to this challenge, Tydi has been presented as an open specification for streaming dataflow designs in digital circuits, allowing designers to express how composite and variable-length data structures are transferred over streams using clear, data-centric types. Earlier efforts in providing an implementation framework for Tydi managed to generate VHDL boilerplate code for Tydi interfaces, but offered limited design value over custom solutions due to VHDL's low abstraction level. In contrast, Chisel, with its high level of abstraction and customizability offers a suitable platform to implement Tydi-based components.
In this thesis, the Tydi-Chisel library is presented along with an A-to-Z design-process description for data-streaming accelerators. A stream-interface solution is presented that offers both compatibility with Tydi in traditional HDLs and maximum utility within Chisel through two intercompatible representations. In addition, design complexity is reduced through novel utilities like stream-complexity conversion, developed to alleviate interface specification mismatches between components. Using the presented toolchain and library, the amount of code required to specify Tydi interfaces for representative use-cases can be reduced several times compared to a Verilog description, while offering increased utility.
Tydi-Chisel aims to simplify the design of data-streaming accelerators through the integration of the Tydi interface standard in Chisel, along with helper components, syntax sugar, and verification tools. In combination Chisel and Tydi help bridge the hardware-software divide, making solo-design and collaboration between designers easier.
In this thesis, the Tydi-Chisel library is presented along with an A-to-Z design-process description for data-streaming accelerators. A stream-interface solution is presented that offers both compatibility with Tydi in traditional HDLs and maximum utility within Chisel through two intercompatible representations. In addition, design complexity is reduced through novel utilities like stream-complexity conversion, developed to alleviate interface specification mismatches between components. Using the presented toolchain and library, the amount of code required to specify Tydi interfaces for representative use-cases can be reduced several times compared to a Verilog description, while offering increased utility.
Tydi-Chisel aims to simplify the design of data-streaming accelerators through the integration of the Tydi interface standard in Chisel, along with helper components, syntax sugar, and verification tools. In combination Chisel and Tydi help bridge the hardware-software divide, making solo-design and collaboration between designers easier.
The dynamic semantics of a programming language formally describe the runtime behavior of any given program. In this thesis, we present Dynamix, a meta-language for dynamic semantics. By writing a specification for a language in Dynamix, a compiler for the language can be derived automatically.
Dynamix specifications compile source programs to the Tim intermediate representation, a language-agnostic target IR designed to be able to be efficiently interpreted or compiled. Dynamix and Tim make use of the continuation-passing style to abstract over control flow, giving language developers fine-grained access to control flow primitives in their specification. A novel abstraction in Dynamix allows the construction of these CPS terms without the traditional friction involved. Dynamix is fully typed and integrated within the Spoofax language workbench. This allows language developers to interact directly with other parts of the workbench, including automatic type signature generation and the ability to query the results of static analysis.
Through case studies for miniStratego and ChocoPy with exceptions, we show that Dynamix is capable of succinctly representing a wide range of source language features and paradigms. Current performance is acceptable, with the foundations for a future efficient compiler for the Tim IR already in place. ...
Dynamix specifications compile source programs to the Tim intermediate representation, a language-agnostic target IR designed to be able to be efficiently interpreted or compiled. Dynamix and Tim make use of the continuation-passing style to abstract over control flow, giving language developers fine-grained access to control flow primitives in their specification. A novel abstraction in Dynamix allows the construction of these CPS terms without the traditional friction involved. Dynamix is fully typed and integrated within the Spoofax language workbench. This allows language developers to interact directly with other parts of the workbench, including automatic type signature generation and the ability to query the results of static analysis.
Through case studies for miniStratego and ChocoPy with exceptions, we show that Dynamix is capable of succinctly representing a wide range of source language features and paradigms. Current performance is acceptable, with the foundations for a future efficient compiler for the Tim IR already in place. ...
The dynamic semantics of a programming language formally describe the runtime behavior of any given program. In this thesis, we present Dynamix, a meta-language for dynamic semantics. By writing a specification for a language in Dynamix, a compiler for the language can be derived automatically.
Dynamix specifications compile source programs to the Tim intermediate representation, a language-agnostic target IR designed to be able to be efficiently interpreted or compiled. Dynamix and Tim make use of the continuation-passing style to abstract over control flow, giving language developers fine-grained access to control flow primitives in their specification. A novel abstraction in Dynamix allows the construction of these CPS terms without the traditional friction involved. Dynamix is fully typed and integrated within the Spoofax language workbench. This allows language developers to interact directly with other parts of the workbench, including automatic type signature generation and the ability to query the results of static analysis.
Through case studies for miniStratego and ChocoPy with exceptions, we show that Dynamix is capable of succinctly representing a wide range of source language features and paradigms. Current performance is acceptable, with the foundations for a future efficient compiler for the Tim IR already in place.
Dynamix specifications compile source programs to the Tim intermediate representation, a language-agnostic target IR designed to be able to be efficiently interpreted or compiled. Dynamix and Tim make use of the continuation-passing style to abstract over control flow, giving language developers fine-grained access to control flow primitives in their specification. A novel abstraction in Dynamix allows the construction of these CPS terms without the traditional friction involved. Dynamix is fully typed and integrated within the Spoofax language workbench. This allows language developers to interact directly with other parts of the workbench, including automatic type signature generation and the ability to query the results of static analysis.
Through case studies for miniStratego and ChocoPy with exceptions, we show that Dynamix is capable of succinctly representing a wide range of source language features and paradigms. Current performance is acceptable, with the foundations for a future efficient compiler for the Tim IR already in place.
Build systems speed up builds by reusing build step outputs from previous builds when possible.
This requires precise definitions of the dependencies for build steps.
PIE is a build system with precise dependencies, but its task definitions in Java are verbose.
The PIE DSL allows pipeline developers to write concise definitions of PIE tasks, but the PIE framework has evolved and the PIE DSL cannot express many tasks and projects.
This thesis presents PIE DSL 2, which improves on PIE DSL 1 in three areas.
It extends the language itself with a module system, generics and support for suppliers and injected values, which allows it to express more tasks within the DSL.
There are four improvements for the code base.
The first two are a specification of the static semantics in Statix and a new compiler backend that compiles to an AST instead of using string interpolation, both of which extend the features for the DSL that can be expressed.
The second pair is constructors for semantic types and tests, which improve development speed of the DSL.
The final area we improve is the user experience, which we improve by adding documentation for expressions and types in the PIE DSL.
We compare PIE DSL 2 to Java in a case study.
Only a single task can be expressed in the DSL, which means that the boilerplate is not reduced.
Furthermore, the Java ecosystem has better error detection except for nullability.
Finally, the PIE DSL is simpler than Java, but only when the full pipeline is supported by the DSL.
We conclude that the DSL is not better than Java for full projects yet, but for tasks that it can express it is a slight improvement over Java.
This leads to the hypothesis that it has potential to become better if it can express enough tasks.
Due to time constraints, the case study did not use the latest version of the DSL.
In theory the latest version of the DSL can express 11 of the 19 tasks, but this has not been verified experimentally.
Overall, this thesis makes improvements to the PIE DSL and its environment, but that has not translated to the DSL being better than Java. ...
This requires precise definitions of the dependencies for build steps.
PIE is a build system with precise dependencies, but its task definitions in Java are verbose.
The PIE DSL allows pipeline developers to write concise definitions of PIE tasks, but the PIE framework has evolved and the PIE DSL cannot express many tasks and projects.
This thesis presents PIE DSL 2, which improves on PIE DSL 1 in three areas.
It extends the language itself with a module system, generics and support for suppliers and injected values, which allows it to express more tasks within the DSL.
There are four improvements for the code base.
The first two are a specification of the static semantics in Statix and a new compiler backend that compiles to an AST instead of using string interpolation, both of which extend the features for the DSL that can be expressed.
The second pair is constructors for semantic types and tests, which improve development speed of the DSL.
The final area we improve is the user experience, which we improve by adding documentation for expressions and types in the PIE DSL.
We compare PIE DSL 2 to Java in a case study.
Only a single task can be expressed in the DSL, which means that the boilerplate is not reduced.
Furthermore, the Java ecosystem has better error detection except for nullability.
Finally, the PIE DSL is simpler than Java, but only when the full pipeline is supported by the DSL.
We conclude that the DSL is not better than Java for full projects yet, but for tasks that it can express it is a slight improvement over Java.
This leads to the hypothesis that it has potential to become better if it can express enough tasks.
Due to time constraints, the case study did not use the latest version of the DSL.
In theory the latest version of the DSL can express 11 of the 19 tasks, but this has not been verified experimentally.
Overall, this thesis makes improvements to the PIE DSL and its environment, but that has not translated to the DSL being better than Java. ...
Build systems speed up builds by reusing build step outputs from previous builds when possible.
This requires precise definitions of the dependencies for build steps.
PIE is a build system with precise dependencies, but its task definitions in Java are verbose.
The PIE DSL allows pipeline developers to write concise definitions of PIE tasks, but the PIE framework has evolved and the PIE DSL cannot express many tasks and projects.
This thesis presents PIE DSL 2, which improves on PIE DSL 1 in three areas.
It extends the language itself with a module system, generics and support for suppliers and injected values, which allows it to express more tasks within the DSL.
There are four improvements for the code base.
The first two are a specification of the static semantics in Statix and a new compiler backend that compiles to an AST instead of using string interpolation, both of which extend the features for the DSL that can be expressed.
The second pair is constructors for semantic types and tests, which improve development speed of the DSL.
The final area we improve is the user experience, which we improve by adding documentation for expressions and types in the PIE DSL.
We compare PIE DSL 2 to Java in a case study.
Only a single task can be expressed in the DSL, which means that the boilerplate is not reduced.
Furthermore, the Java ecosystem has better error detection except for nullability.
Finally, the PIE DSL is simpler than Java, but only when the full pipeline is supported by the DSL.
We conclude that the DSL is not better than Java for full projects yet, but for tasks that it can express it is a slight improvement over Java.
This leads to the hypothesis that it has potential to become better if it can express enough tasks.
Due to time constraints, the case study did not use the latest version of the DSL.
In theory the latest version of the DSL can express 11 of the 19 tasks, but this has not been verified experimentally.
Overall, this thesis makes improvements to the PIE DSL and its environment, but that has not translated to the DSL being better than Java.
This requires precise definitions of the dependencies for build steps.
PIE is a build system with precise dependencies, but its task definitions in Java are verbose.
The PIE DSL allows pipeline developers to write concise definitions of PIE tasks, but the PIE framework has evolved and the PIE DSL cannot express many tasks and projects.
This thesis presents PIE DSL 2, which improves on PIE DSL 1 in three areas.
It extends the language itself with a module system, generics and support for suppliers and injected values, which allows it to express more tasks within the DSL.
There are four improvements for the code base.
The first two are a specification of the static semantics in Statix and a new compiler backend that compiles to an AST instead of using string interpolation, both of which extend the features for the DSL that can be expressed.
The second pair is constructors for semantic types and tests, which improve development speed of the DSL.
The final area we improve is the user experience, which we improve by adding documentation for expressions and types in the PIE DSL.
We compare PIE DSL 2 to Java in a case study.
Only a single task can be expressed in the DSL, which means that the boilerplate is not reduced.
Furthermore, the Java ecosystem has better error detection except for nullability.
Finally, the PIE DSL is simpler than Java, but only when the full pipeline is supported by the DSL.
We conclude that the DSL is not better than Java for full projects yet, but for tasks that it can express it is a slight improvement over Java.
This leads to the hypothesis that it has potential to become better if it can express enough tasks.
Due to time constraints, the case study did not use the latest version of the DSL.
In theory the latest version of the DSL can express 11 of the 19 tasks, but this has not been verified experimentally.
Overall, this thesis makes improvements to the PIE DSL and its environment, but that has not translated to the DSL being better than Java.
This paper compares the generalizing capability of multi-head attention (MHA) models with that of convolutional neural networks (CNNs). This is done by comparing their performance on out-ofdistribution data. The dataset that is used to train both models is created by coupling digits from the MNIST dataset with a set amount of background images from the CIFAR-10 dataset. An out of distribution sample is generated by using a background not used during training. This paper compares the accuracy of both models on such out-ofdistribution samples to indicate the generalizability of both models. Furthermore, the invariance of MHA models towards certain affine data transformations is compared to that of CNNs. The results indicate that MHAs might be slightly better at generalizing to unseen data, but that CNNs are better able to generalize to the data transformations performed in this papers experiments.
...
This paper compares the generalizing capability of multi-head attention (MHA) models with that of convolutional neural networks (CNNs). This is done by comparing their performance on out-ofdistribution data. The dataset that is used to train both models is created by coupling digits from the MNIST dataset with a set amount of background images from the CIFAR-10 dataset. An out of distribution sample is generated by using a background not used during training. This paper compares the accuracy of both models on such out-ofdistribution samples to indicate the generalizability of both models. Furthermore, the invariance of MHA models towards certain affine data transformations is compared to that of CNNs. The results indicate that MHAs might be slightly better at generalizing to unseen data, but that CNNs are better able to generalize to the data transformations performed in this papers experiments.
Effect handler oriented programming (EHOP) is a recently proposed programming paradigm, which aims to provide a separation of concerns by isolating the handling of side-effects from the main application logic. Nowadays, as the core concepts behind EHOP are being added to more and more programming languages, it is evident that EHOP is slowly but steadily growing in popularity. Therefore, it is important to explore the applicability of EHOP for different areas of software development. However, so far, very little research has been conducted on this topic and, thus, barely any possible application domains of EHOP have been investigated. This study focuses on a potential field of application of EHOP, which has not been covered by previous research, namely - text-based game development, and aims to determine the extent to which the usage of EHOP for text-based game development affects the modularity, readability and maintainability of the source code. This goal will be achieved by performing both a qualitative as well as a quantitative analysis of the source code of a text-based game, written in Koka - a state-of-the-art programming language, which supports EHOP. The results show that there are substantial benefits to using EHOP for text-based game development. It significantly improves the modularity, readability and maintainability of the source code at the cost of very little to no performance.
...
Effect handler oriented programming (EHOP) is a recently proposed programming paradigm, which aims to provide a separation of concerns by isolating the handling of side-effects from the main application logic. Nowadays, as the core concepts behind EHOP are being added to more and more programming languages, it is evident that EHOP is slowly but steadily growing in popularity. Therefore, it is important to explore the applicability of EHOP for different areas of software development. However, so far, very little research has been conducted on this topic and, thus, barely any possible application domains of EHOP have been investigated. This study focuses on a potential field of application of EHOP, which has not been covered by previous research, namely - text-based game development, and aims to determine the extent to which the usage of EHOP for text-based game development affects the modularity, readability and maintainability of the source code. This goal will be achieved by performing both a qualitative as well as a quantitative analysis of the source code of a text-based game, written in Koka - a state-of-the-art programming language, which supports EHOP. The results show that there are substantial benefits to using EHOP for text-based game development. It significantly improves the modularity, readability and maintainability of the source code at the cost of very little to no performance.
Effect handler oriented programming or EHOP for short, is a new programming paradigm aiming to achieve separation of concerns in code which will lead to modular, readable and maintainable code. Since EHOP is significantly new, it is important to assess and compare it against traditional, commonly used paradigms in order to see if a wider adoption of EHOP would prove beneficial to computer science. In this research, EHOP was compared with traditional paradigms under the context of data processing applications. An Excel-like command line application called “MiniExcel” was implemented from scratch. Moreover, “Hierarchical EHOP”, a new structural pattern for EHOP was defined which enforces rules between concepts and produces a readable code structure. The main conclusions of this research can be summarized by the following statements. EHOP produces more modular, readable and maintainable code compared to traditional paradigms. Implementing additional concepts and updates to code is seamless using EHOP, yet the lack of development in EHOP’s ecosystem raises frustrating errors and requires the developer to implement libraries that are usually built-in for languages that support traditional paradigms. Functional programming produces faster running code, but EHOP is more memory efficient. Therefore, for applications that interact with users EHOP is the better choice and for applications that only execute code functional programming is more suitable.
...
Effect handler oriented programming or EHOP for short, is a new programming paradigm aiming to achieve separation of concerns in code which will lead to modular, readable and maintainable code. Since EHOP is significantly new, it is important to assess and compare it against traditional, commonly used paradigms in order to see if a wider adoption of EHOP would prove beneficial to computer science. In this research, EHOP was compared with traditional paradigms under the context of data processing applications. An Excel-like command line application called “MiniExcel” was implemented from scratch. Moreover, “Hierarchical EHOP”, a new structural pattern for EHOP was defined which enforces rules between concepts and produces a readable code structure. The main conclusions of this research can be summarized by the following statements. EHOP produces more modular, readable and maintainable code compared to traditional paradigms. Implementing additional concepts and updates to code is seamless using EHOP, yet the lack of development in EHOP’s ecosystem raises frustrating errors and requires the developer to implement libraries that are usually built-in for languages that support traditional paradigms. Functional programming produces faster running code, but EHOP is more memory efficient. Therefore, for applications that interact with users EHOP is the better choice and for applications that only execute code functional programming is more suitable.
Effect Handler Oriented Programming is a promising new programming paradigm, delivering separation of of concerns with regards to side effects in an otherwise functional environment.
This paper discusses the applicability of this new paradigm to static code analysis programs.
Different code analyzers often have many similar, if not identical pieces of code which could be abstracted away.
This abstraction does not come natural to the programming paradigm of Functional Programming but are quite natural within EHOP.
The current programming languages do not yet seem up to the task of rapid generalization of code and elimination of duplicate pieces of code.
However, the concepts present in EHOP will almost certainly be able to eliminate much of this code reduction once the languages have matured further.
The implicit passing of functionality will also allow for clearer code with less unnecessary visual clutter. ...
This paper discusses the applicability of this new paradigm to static code analysis programs.
Different code analyzers often have many similar, if not identical pieces of code which could be abstracted away.
This abstraction does not come natural to the programming paradigm of Functional Programming but are quite natural within EHOP.
The current programming languages do not yet seem up to the task of rapid generalization of code and elimination of duplicate pieces of code.
However, the concepts present in EHOP will almost certainly be able to eliminate much of this code reduction once the languages have matured further.
The implicit passing of functionality will also allow for clearer code with less unnecessary visual clutter. ...
Effect Handler Oriented Programming is a promising new programming paradigm, delivering separation of of concerns with regards to side effects in an otherwise functional environment.
This paper discusses the applicability of this new paradigm to static code analysis programs.
Different code analyzers often have many similar, if not identical pieces of code which could be abstracted away.
This abstraction does not come natural to the programming paradigm of Functional Programming but are quite natural within EHOP.
The current programming languages do not yet seem up to the task of rapid generalization of code and elimination of duplicate pieces of code.
However, the concepts present in EHOP will almost certainly be able to eliminate much of this code reduction once the languages have matured further.
The implicit passing of functionality will also allow for clearer code with less unnecessary visual clutter.
This paper discusses the applicability of this new paradigm to static code analysis programs.
Different code analyzers often have many similar, if not identical pieces of code which could be abstracted away.
This abstraction does not come natural to the programming paradigm of Functional Programming but are quite natural within EHOP.
The current programming languages do not yet seem up to the task of rapid generalization of code and elimination of duplicate pieces of code.
However, the concepts present in EHOP will almost certainly be able to eliminate much of this code reduction once the languages have matured further.
The implicit passing of functionality will also allow for clearer code with less unnecessary visual clutter.