Reactive Sorting Networks

Research output: Chapter in Book/Report/Conference proceedingMeeting abstract (Book)

Abstract

Sorting is a central problem in computer science and oneof the key components of many applications. To the best ofour knowledge, no reactive programming implementationof sorting algorithms has ever been presented.In this paper we present reactive implementations of so-called sorting networks. Sorting networks are networks ofcomparators that are wired up in a particular order. Dataenters a sorting network along various input wires and leavesthe sorting network on the same number of output wiresthat carry the data in sorted order.This paper shows how sorting networks can be expressedelegantly in a reactive programming language by aligning thevisual representation of a sorting network with the canonicalDAG representation of reactive programs. We use our ownexperimental language called Haai to do so. With a limitednumber of built-in higher-order reactive programs, we areable to express sorting networks for bubble sort, insertionsort, bitonic sort, pairwise sort and odd-even merge sort.
Original languageEnglish
Title of host publicationREBLS 2020 - Proceedings of the 7th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems
EditorsIvan Perez
PublisherACM
Pages38-50
Number of pages13
ISBN (Electronic)978-1-4503-8188-8
Publication statusPublished - 26 Nov 2020
Event7th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems - Online
Duration: 16 Nov 202016 Nov 2020
https://2020.splashcon.org/home/rebls-2020

Publication series

NameREBLS 2020 - Proceedings of the 7th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems, Co-located with SPLASH 2020

Workshop

Workshop7th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems
Abbreviated titleREBLS 2020
Period16/11/2016/11/20
Internet address

Keywords

  • Reactive Programming
  • Sorting Networks

Fingerprint Dive into the research topics of 'Reactive Sorting Networks'. Together they form a unique fingerprint.

Cite this