-
Reactive Programming without Functions
Authors:
Bjarno Oeyen,
Joeri De Koster,
Wolfgang De Meuter
Abstract:
Context: Reactive programming (RP) is a declarative programming paradigm suitable for expressing the handling of events. It enables programmers to create applications that react automatically to changes over time. Whenever a time-varying signal changes -- e.g. in response to values produced by event stream (e.g., sensor data, user input...) -- the program state is updated automatically in tandem w…
▽ More
Context: Reactive programming (RP) is a declarative programming paradigm suitable for expressing the handling of events. It enables programmers to create applications that react automatically to changes over time. Whenever a time-varying signal changes -- e.g. in response to values produced by event stream (e.g., sensor data, user input...) -- the program state is updated automatically in tandem with that change. This makes RP well-suited for building interactive applications and reactive (soft real-time) systems.
Inquiry: RP Language implementations are often built on top of an existing (host) language as an Embedded Domain Specific Language (EDSL). This results in application code in which reactive code and non-reactive code is inherently entangled. Using a mechanism known as lifting, one usually has access to the full feature set of the (non-reactive) host language in the RP program. However, lifting is also dangerous. First, host code expressed in a Turing-complete language may diverge, resulting in unresponsive programs: i.e. reactive programs that are not actually reactive. Second, the bi-directional integration of reactive and non-reactive code results in a paradigmatic mismatch that, when unchecked, leads to faulty behaviour in programs.
Approach: We propose a new reactive programming language, that has been meticulously designed to be reactive-only. We start with a simple (first-order) model for reactivity, based on reactors (i.e. uninstantiated descriptions of signals and their dependencies) and deployments (i.e. instances of reactors) that consist of signals. The language does not have the notion of functions, and thus unlike other RP languages there is no lifting either. We extend this simple model incrementally with additional features found in other programming languages, RP or otherwise. These features include stateful reactors (that allow for time-based accumulation), signals with dynamic dependencies by means of conditionals and polymorphic deployments, recursively-defined reactors, and (anonymous) reactors with lexical scope.
Knowledge: In our description of these language features, we not only describe the syntax and semantics, but also how each features compares to the problems that exist in (EDSL) RP languages. I.e. by starting from a reactive-only model, we identify which reactive features (that, in other RP languages are typically expressed in non-reactive code) affect the reactive guarantees that can be enforced by the language.
Grounding: We base our arguments by analysing the effect that each feature has on our language: e.g., by analysing how signals are updated, how they are created and how dependencies between signals can be affected. When applicable, we draw parallels with other languages: i.e. similarities shared with other RP languages will be highlighted and thoroughly analysed, and where relevant the same will also be done with non-reactive languages.
Importance: Our language shows how a purely reactive programming is able to express the same kinds of programs as in other RP languages that require the use of (unchecked) functions. By considering reactive programs as a collection of pure (reactive-only) reactors, we aim to increase how reactive programming is comprehended by both language designers and its users.
△ Less
Submitted 4 March, 2024;
originally announced March 2024.
-
Detecting Relevant Information in High-Volume Chat Logs: Keyphrase Extraction for Grooming and Drug Dealing Forensic Analysis
Authors:
Jeovane Honório Alves,
Horácio A. C. G. Pedroso,
Rafael Honorio Venetikides,
Joel E. M. Köster,
Luiz Rodrigo Grochocki,
Cinthia O. A. Freitas,
Jean Paul Barddal
Abstract:
The growing use of digital communication platforms has given rise to various criminal activities, such as grooming and drug dealing, which pose significant challenges to law enforcement and forensic experts. This paper presents a supervised keyphrase extraction approach to detect relevant information in high-volume chat logs involving grooming and drug dealing for forensic analysis. The proposed m…
▽ More
The growing use of digital communication platforms has given rise to various criminal activities, such as grooming and drug dealing, which pose significant challenges to law enforcement and forensic experts. This paper presents a supervised keyphrase extraction approach to detect relevant information in high-volume chat logs involving grooming and drug dealing for forensic analysis. The proposed method, JointKPE++, builds upon the JointKPE keyphrase extractor by employing improvements to handle longer texts effectively. We evaluate JointKPE++ using BERT-based pre-trained models on grooming and drug dealing datasets, including BERT, RoBERTa, SpanBERT, and BERTimbau. The results show significant improvements over traditional approaches and demonstrate the potential for JointKPE++ to aid forensic experts in efficiently detecting keyphrases related to criminal activities.
△ Less
Submitted 14 September, 2023;
originally announced November 2023.
-
Tackling the Awkward Squad for Reactive Programming: The Actor-Reactor Model
Authors:
Sam Van den Vonder,
Thierry Renaux,
Bjarno Oeyen,
Joeri De Koster,
Wolfgang De Meuter
Abstract:
Reactive programming is a programming paradigm whereby programs are internally represented by a dependency graph, which is used to automatically (re)compute parts of a program whenever its input changes. In practice reactive programming can only be used for some parts of an application: a reactive program is usually embedded in an application that is still written in ordinary imperative languages…
▽ More
Reactive programming is a programming paradigm whereby programs are internally represented by a dependency graph, which is used to automatically (re)compute parts of a program whenever its input changes. In practice reactive programming can only be used for some parts of an application: a reactive program is usually embedded in an application that is still written in ordinary imperative languages such as JavaScript or Scala. In this paper we investigate this embedding and we distill "the awkward squad for reactive programming" as 3 concerns that are essential for real-world software development, but that do not fit within reactive programming. They are related to long lasting computations, side-effects, and the coordination between imperative and reactive code. To solve these issues we design a new programming model called the Actor-Reactor Model in which programs are split up in a number of actors and reactors. Actors and reactors enforce a strict separation of imperative and reactive code, and they can be composed via a number of composition operators that make use of data streams. We demonstrate the model via our own implementation in a language called Stella.
△ Less
Submitted 21 June, 2023;
originally announced June 2023.
-
Latent Network Models to Account for Noisy, Multiply-Reported Social Network Data
Authors:
Caterina De Bacco,
Martina Contisciani,
Jonathan Cardoso-Silva,
Hadiseh Safdari,
Diego Baptista,
Gabriela L. Borges,
Tracy Sweet,
Jean-Gabriel Young,
Jeremy Koster,
Cody T. Ross,
Richard McElreath,
Daniel Redhead,
Eleanor A. Power
Abstract:
Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that inc…
▽ More
Social network data are often constructed by incorporating reports from multiple individuals. However, it is not obvious how to reconcile discordant responses from individuals. There may be particular risks with multiply-reported data if people's responses reflect normative expectations -- such as an expectation of balanced, reciprocal relationships. Here, we propose a probabilistic model that incorporates ties reported by multiple individuals to estimate the unobserved network structure. In addition to estimating a parameter for each reporter that is related to their tendency of over- or under-reporting relationships, the model explicitly incorporates a term for ``mutuality,'' the tendency to report ties in both directions involving the same alter. Our model's algorithmic implementation is based on variational inference, which makes it efficient and scalable to large systems. We apply our model to data from 75 Indian villages collected with a name-generator design, and a Nicaraguan community collected with a roster-based design. We observe strong evidence of ``mutuality'' in both datasets, and find that this value varies by relationship type. Consequently, our model estimates networks with reciprocity values that are substantially different than those resulting from standard deterministic aggregation approaches, demonstrating the need to consider such issues when gathering, constructing, and analysing survey-based network data.
△ Less
Submitted 12 December, 2022; v1 submitted 21 December, 2021;
originally announced December 2021.
-
A momentum preserving frictional contact algorithm based on affine particle-in-cell grid transfers
Authors:
Michael Tupek,
Jacob Koester,
Matthew Mosby
Abstract:
An efficient and momentum conserving algorithm for enforcing contact between solid bodies is proposed. Previous advances in the material point method (MPM) led to a fast and simple, but potentially momentum violating, strategy for enforcing contact. This was achieved through a combination of velocity transfers between background and foreground grids, and a background grid velocity field update. We…
▽ More
An efficient and momentum conserving algorithm for enforcing contact between solid bodies is proposed. Previous advances in the material point method (MPM) led to a fast and simple, but potentially momentum violating, strategy for enforcing contact. This was achieved through a combination of velocity transfers between background and foreground grids, and a background grid velocity field update. We propose a modified strategy which ensures conservation of both linear and angular momentum with a novel use of the affine particle-in-cell (APIC) method. Two issues common to particle-in-cell based algorithms for contact are also addressed: material bodies tend to stick at a gap which is proportional to the grid spacing; and material points tend to stick together permanently when located within the same grid cell, making material rebound and friction challenging. We show that the use of APIC, combined with a grid transfer and momentum update algorithm results in contact being enforced at essentially zero gap. For the second issue, we propose a novel iterative scheme which allows particles interacting through the background grid to naturally separate after contact and enforce friction, while still satisfying momentum conservation.
△ Less
Submitted 4 August, 2021;
originally announced August 2021.
-
Advanced Join Patterns for the Actor Model based on CEP Techniques
Authors:
Humberto Rodriguez Avila,
Joeri De Koster,
Wolfgang De Meuter
Abstract:
Context: Actor-based programming languages offer many essential features for developing modern distributed reactive systems. These systems exploit the actor model's isolation property to fulfill their performance and scalability demands. Unfortunately, the reliance of the model on isolation as its most fundamental property requires programmers to express complex interaction patterns between their…
▽ More
Context: Actor-based programming languages offer many essential features for developing modern distributed reactive systems. These systems exploit the actor model's isolation property to fulfill their performance and scalability demands. Unfortunately, the reliance of the model on isolation as its most fundamental property requires programmers to express complex interaction patterns between their actors to be expressed manually in terms of complex combinations of messages sent between the isolated actors.
Inquiry: In the last three decades, several language design proposals have been introduced to reduce the complexity that emerges from describing said interaction and coordination of actors. We argue that none of these proposals is satisfactory in order to express the many complex interaction patterns between actors found in modern reactive distributed systems.
Approach: We describe seven smart home automation scenarios (in which an actor represents every smart home appliance) to motivate the support by actor languages for five radically different types of message synchronization patterns, which are lacking in modern distributed actor-based languages. Fortunately, these five types of synchronisation patterns have been studied extensively by the Complex Event Processing (CEP) community. Our paper describes how such CEP patterns are elegantly added to an actor-based programming language.
Knowledge: Based on our findings, we propose an extension of the single-message matching paradigm of contemporary actor-based languages in order to support a multiple-message matching way of thinking in the same way as proposed by CEP languages. Our proposal thus enriches the actor-model by ways of declaratively describing complex message combinations to which an actor can respond.
Grounding: We base the problem-statement of the paper on an online poll in the home automation community that has motivated the real need for the CEP-based synchronisation operators between actors proposed in the paper. Furthermore, we implemented a DSL -- called Sparrow -- that supports said operators and we argue quantitatively (in terms of LOC and in terms of a reduction of the concerns that have to be handled by programmers) that the DSL outperforms existing approaches.
Importance: This work aims to provide a set of synchronization operators that help actor-based languages to handle the complex interaction required by modern reactive distributed systems. To the best of our knowledge, our proposal is the first one to add advanced CEP synchronization operators to the -- relatively simplistic single-message based matching -- mechanisms of most actor-based languages.
△ Less
Submitted 30 October, 2020;
originally announced October 2020.
-
Supervised Learning in Temporally-Coded Spiking Neural Networks with Approximate Backpropagation
Authors:
Andrew Stephan,
Brian Gardner,
Steven J. Koester,
Andre Gruning
Abstract:
In this work we propose a new supervised learning method for temporally-encoded multilayer spiking networks to perform classification. The method employs a reinforcement signal that mimics backpropagation but is far less computationally intensive. The weight update calculation at each layer requires only local data apart from this signal. We also employ a rule capable of producing specific output…
▽ More
In this work we propose a new supervised learning method for temporally-encoded multilayer spiking networks to perform classification. The method employs a reinforcement signal that mimics backpropagation but is far less computationally intensive. The weight update calculation at each layer requires only local data apart from this signal. We also employ a rule capable of producing specific output spike trains; by setting the target spike time equal to the actual spike time with a slight negative offset for key high-value neurons the actual spike time becomes as early as possible. In simulated MNIST handwritten digit classification, two-layer networks trained with this rule matched the performance of a comparable backpropagation based non-spiking network.
△ Less
Submitted 26 July, 2020;
originally announced July 2020.
-
Spin-Hall MTJ Cells for Intra-Column Competition in Hierarchical Temporal Memory
Authors:
Andrew W. Stephan,
Steven J. Koester
Abstract:
We propose a dedicated winner-take-all circuit to efficiently implement the intra-column competition between cells in Hierarchical Temporal Memory which is a crucial part of the algorithm. All inputs and outputs are charge-based for compatibility with standard CMOS. The circuit incorporates memristors for competitive advantage to emulate a column with a cell in a predictive state. The circuit can…
▽ More
We propose a dedicated winner-take-all circuit to efficiently implement the intra-column competition between cells in Hierarchical Temporal Memory which is a crucial part of the algorithm. All inputs and outputs are charge-based for compatibility with standard CMOS. The circuit incorporates memristors for competitive advantage to emulate a column with a cell in a predictive state. The circuit can also detect columns 'bursting' by passive averaging and comparison of the cell outputs. The proposed spintronic devices and circuit are thoroughly described and a series of simulations are used to predict the performance. The simulations indicate that the circuit can complete a nine-cell, nine-input competition operation in under 15 ns at a cost of about 25 pJ.
△ Less
Submitted 16 July, 2020;
originally announced July 2020.
-
SHE-MTJ Circuits for Convolutional Neural Networks
Authors:
Andrew W. Stephan,
Steven J. Koester
Abstract:
We report the performance characteristics of a notional Convolutional Neural Network based on the previously-proposed Multiply-Accumulate-Activate-Pool set, an MTJ-based spintronic circuit made to compute multiple neural functionalities in parallel. A study of image classification with the MNIST handwritten digits dataset using this network is provided via simulation. The effect of changing the we…
▽ More
We report the performance characteristics of a notional Convolutional Neural Network based on the previously-proposed Multiply-Accumulate-Activate-Pool set, an MTJ-based spintronic circuit made to compute multiple neural functionalities in parallel. A study of image classification with the MNIST handwritten digits dataset using this network is provided via simulation. The effect of changing the weight representation precision, the severity of device process variation within the MAAP sets and the computational redundancy are provided. The emulated network achieves between 90 and 95\% image classification accuracy at a cost of ~100 nJ per image.
△ Less
Submitted 16 July, 2020;
originally announced July 2020.
-
Nonvolatile Spintronic Memory Cells for Neural Networks
Authors:
Andrew W. Stephan,
Qiuwen Lou,
Michael Niemier,
X. Sharon Hu,
Steven J. Koester
Abstract:
A new spintronic nonvolatile memory cell analogous to 1T DRAM with non-destructive read is proposed. The cells can be used as neural computing units. A dual-circuit neural network architecture is proposed to leverage these devices against the complex operations involved in convolutional networks. Simulations based on HSPICE and Matlab were performed to study the performance of this architecture wh…
▽ More
A new spintronic nonvolatile memory cell analogous to 1T DRAM with non-destructive read is proposed. The cells can be used as neural computing units. A dual-circuit neural network architecture is proposed to leverage these devices against the complex operations involved in convolutional networks. Simulations based on HSPICE and Matlab were performed to study the performance of this architecture when classifying images as well as the effect of varying the size and stability of the nanomagnets. The spintronic cells outperform a purely charge-based implementation of the same network, consuming about 100 pJ total per image processed.
△ Less
Submitted 29 May, 2019;
originally announced May 2019.
-
Convolutional Neural Networks Utilizing Multifunctional Spin-Hall MTJ Neurons
Authors:
Andrew W. Stephan,
Steven J. Koester
Abstract:
We propose a new network architecture for standard spin-Hall magnetic tunnel junction-based spintronic neurons that allows them to compute multiple critical convolutional neural network functionalities simultaneously and in parallel, saving space and time. An approximation to the Rectified Linear Unit transfer function and the local pooling function are computed simultaneously with the convolution…
▽ More
We propose a new network architecture for standard spin-Hall magnetic tunnel junction-based spintronic neurons that allows them to compute multiple critical convolutional neural network functionalities simultaneously and in parallel, saving space and time. An approximation to the Rectified Linear Unit transfer function and the local pooling function are computed simultaneously with the convolution operation itself. A proof-of-concept simulation is performed on the MNIST dataset, achieving up to 98% accuracy at a cost of less than 1 nJ for all convolution, activation and pooling operations combined. The simulations are remarkably robust to thermal noise, performing well even with very small magnetic layers.
△ Less
Submitted 9 May, 2019;
originally announced May 2019.
-
Benchmarking Inverse Rashba-Edelstein Magnetoelectric Devices for Neuromorphic Computing
Authors:
Andrew W. Stephan,
Jiaxi Hu,
Steven J. Koester
Abstract:
We propose a new design for a cellular neural network with spintronic neurons and CMOS-based synapses. Harnessing the magnetoelectric and inverse Rashba-Edelstein effects allows natural emulation of the behavior of an ideal cellular network. This combination of effects offers an increase in speed and efficiency over other spintronic neural networks. A rigorous performance analysis via simulation i…
▽ More
We propose a new design for a cellular neural network with spintronic neurons and CMOS-based synapses. Harnessing the magnetoelectric and inverse Rashba-Edelstein effects allows natural emulation of the behavior of an ideal cellular network. This combination of effects offers an increase in speed and efficiency over other spintronic neural networks. A rigorous performance analysis via simulation is provided.
△ Less
Submitted 21 November, 2018;
originally announced November 2018.
-
Search-based Tier Assignment for Optimising Offline Availability in Multi-tier Web Applications
Authors:
Laure Philips,
Joeri De Koster,
Wolfgang De Meuter,
Coen De Roover
Abstract:
Web programmers are often faced with several challenges in the development process of modern, rich internet applications. Technologies for the different tiers of the application have to be selected: a server-side language, a combination of JavaScript, HTML and CSS for the client, and a database technology. Meeting the expectations of contemporary web applications requires even more effort from the…
▽ More
Web programmers are often faced with several challenges in the development process of modern, rich internet applications. Technologies for the different tiers of the application have to be selected: a server-side language, a combination of JavaScript, HTML and CSS for the client, and a database technology. Meeting the expectations of contemporary web applications requires even more effort from the developer: many state of the art libraries must be mastered and glued together. This leads to an impedance mismatch problem between the different technologies and it is up to the programmer to align them manually. Multi-tier or tierless programming is a web programming paradigm that provides one language for the different tiers of the web application, allowing the programmer to focus on the actual program logic instead of the accidental complexity that comes from combining several technologies. While current tierless approaches therefore relieve the burden of having to combine different technologies into one application, the distribution of the code is explicitly tied into the program. Certain distribution decisions have an impact on crosscutting concerns such as information security or offline availability. Moreover, adapting the programs such that the application complies better with these concerns often leads to code tangling, rendering the program more difficult to understand and maintain. We introduce an approach to multi-tier programming where the tierless code is decoupled from the tier specification. The developer implements the web application in terms of slices and an external specification that assigns the slices to tiers. A recommender system completes the picture for those slices that do not have a fixed placement and proposes slice refinements as well. This recommender system tries to optimise the tier specification with respect to one or more crosscutting concerns. This is in contrast with current cutting edge solutions that hide distribution decisions from the programmer. In this paper we show that slices, together with a recommender system, enable the developer to experiment with different placements of slices, until the distribution of the code satisfies the programmer's needs. We present a search-based recommender system that maximises the offline availability of a web application and a concrete implementation of these concepts in the tier-splitting tool Stip.js.
△ Less
Submitted 4 December, 2017;
originally announced December 2017.
-
Rust-Bio - a fast and safe bioinformatics library
Authors:
Johannes Köster
Abstract:
We present Rust-Bio, the first general purpose bioinformatics library for the innovative Rust programming language. Rust-Bio leverages the unique combination of speed, memory safety and high-level syntax offered by Rust to provide a fast and safe set of bioinformatics algorithms and data structures with a focus on sequence analysis.
We present Rust-Bio, the first general purpose bioinformatics library for the innovative Rust programming language. Rust-Bio leverages the unique combination of speed, memory safety and high-level syntax offered by Rust to provide a fast and safe set of bioinformatics algorithms and data structures with a focus on sequence analysis.
△ Less
Submitted 9 September, 2015;
originally announced September 2015.
-
Towards Composable Concurrency Abstractions
Authors:
Janwillem Swalens,
Stefan Marr,
Joeri De Koster,
Tom Van Cutsem
Abstract:
In the past decades, many different programming models for managing concurrency in applications have been proposed, such as the actor model, Communicating Sequential Processes, and Software Transactional Memory. The ubiquity of multi-core processors has made harnessing concurrency even more important. We observe that modern languages, such as Scala, Clojure, or F#, provide not one, but multiple co…
▽ More
In the past decades, many different programming models for managing concurrency in applications have been proposed, such as the actor model, Communicating Sequential Processes, and Software Transactional Memory. The ubiquity of multi-core processors has made harnessing concurrency even more important. We observe that modern languages, such as Scala, Clojure, or F#, provide not one, but multiple concurrency models that help developers manage concurrency. Large end-user applications are rarely built using just a single concurrency model. Programmers need to manage a responsive UI, deal with file or network I/O, asynchronous workflows, and shared resources. Different concurrency models facilitate different requirements. This raises the issue of how these concurrency models interact, and whether they are composable. After all, combining different concurrency models may lead to subtle bugs or inconsistencies.
In this paper, we perform an in-depth study of the concurrency abstractions provided by the Clojure language. We study all pairwise combinations of the abstractions, noting which ones compose without issues, and which do not. We make an attempt to abstract from the specifics of Clojure, identifying the general properties of concurrency models that facilitate or hinder composition.
△ Less
Submitted 13 June, 2014;
originally announced June 2014.
-
Massively parallel read mapping on GPUs with PEANUT
Authors:
Johannes Köster,
Sven Rahmann
Abstract:
We present PEANUT (ParallEl AligNment UTility), a highly parallel GPU-based read mapper with several distinguishing features, including a novel q-gram index (called the q-group index) with small memory footprint built on-the-fly over the reads and the possibility to output both the best hits or all hits of a read. Designing the algorithm particularly for the GPU architecture, we were able to reach…
▽ More
We present PEANUT (ParallEl AligNment UTility), a highly parallel GPU-based read mapper with several distinguishing features, including a novel q-gram index (called the q-group index) with small memory footprint built on-the-fly over the reads and the possibility to output both the best hits or all hits of a read. Designing the algorithm particularly for the GPU architecture, we were able to reach maximum core occupancy for several key steps. Our benchmarks show that PEANUT outperforms other state-of- the-art mappers in terms of speed and sensitivity. The software is available at http://peanut.readthedocs.org.
△ Less
Submitted 7 March, 2014;
originally announced March 2014.