Blogs (1) >>
POPL 2019
Sun 13 - Sat 19 January 2019 Cascais, Portugal
Thu 17 Jan 2019 16:05 - 16:27 at Sala II - Time Chair(s): Andrew Myers

In real-time decision making and runtime monitoring applications, declarative languages are commonly used as they facilitate modular high-level specifications with the compiler guaranteeing evaluation over data streams in an efficient and incremental manner. We introduce the model of Data Transducers to allow modular compilation of queries over streaming data. A data transducer maintains a finite set of data variables and processes a sequence of tagged data values by updating its variables using an allowed set of operations. The model allows unambiguous nondeterminism, exponentially succinct control, and combining values from parallel threads of computation. The semantics of the model immediately suggests an efficient streaming algorithm for evaluation. The expressiveness of data transducers coincides with “streamable regular functions”, a robust and streamable class of functions characterized by MSO-definable string-to-DAG transformations with no backward edges. We show that the novel features of data transducers, unlike previously studied transducers, make them as succinct as traditional imperative code for processing data streams, but the structuring of the transition function permits modular compilation. In particular, we show that operations such as parallel composition, union, prefix-sum, and quantitative analogs of combinators for unambiguous parsing, can be implemented by natural and succinct constructions on data transducers. To illustrate the benefits of such modularity in compilation, we define a new language for quantitative monitoring, QRE-Past, that integrates features of past-time temporal logic and quantitative regular expressions. While this combination allows a natural specification of a cardiac arrhythmia detection algorithm in QRE-Past, compilation of QRE-Past specifications into efficient monitors comes for free thanks to succinct constructions on data transducers.

Thu 17 Jan

Displayed time zone: Belfast change

15:21 - 16:49
TimeResearch Papers at Sala II
Chair(s): Andrew Myers Cornell University
15:21
22m
Talk
Type-Guided Worst-Case Input Generation
Research Papers
Di Wang Carnegie Mellon University, Jan Hoffmann Carnegie Mellon University
Link to publication DOI Pre-print Media Attached File Attached
15:43
22m
Talk
CT-Wasm: Type-Driven Secure Cryptography for the Web Ecosystem
Research Papers
Conrad Watt University of Cambridge, John Renner University of California, San Diego, Natalie Popescu University of California San Diego, Sunjay Cauligi UCSD, Deian Stefan University of California San Diego
Link to publication DOI Media Attached File Attached
16:05
22m
Talk
Modular Quantitative Monitoring
Research Papers
Rajeev Alur University of Pennsylvania, Konstantinos Mamouras University of Pennsylvania, Caleb Stanford University of Pennsylvania
Link to publication DOI Media Attached File Attached
16:27
22m
Talk
CSS Minification via Constraint SolvingTOPLAS
Research Papers
Matthew Hague Royal Holloway, University of London, Anthony Widjaja Lin Oxford University, Chih-Duo Hong University of Oxford
Media Attached File Attached