bluuebunny/crossref_metadata_2025 huggingface dataset:
DBT path selection for holistic memory efficiency and performance
Authors: Guha Apala , hazelwood Kim , Soffa Mary Lou
Published: April 2020

Dynamic binary translators(DBTs) provide powerful platforms for building dynamic program monitoring and adaptation tools. DBTs, however, have high memory demands because they cache translated code and auxiliary code to a software code cache and must also maintain data structures to support the code cache. The high memory demands make it difficult for memory-constrained embedded systems to take advantage of DBT-based tools. Previous research on DBT memory management focused on the translated code and auxiliary code only. However, we found that data structures are comparable to the code cache in size. We show that the translated code size, auxiliary code size and the data structure size interact in a complex manner, depending on the path selection (trace selection and link formation) strategy. Therefore, holistic memory efficiency (comprising translated code, auxiliary code and data structures) cannot be improved by focusing on the code cache only. In this paper, we use path selection for improving holistic memory efficiency which in turn impacts performance in memory-constrained environments. Although there has been previous research on path selection, such research only considered performance in memory-unconstrained environments.

The challenge for holistic memory efficiency is that the path selection strategy results in complex interactions between the memory demand components. Also, individual aspects of path selection and the holistic memory efficiency may impact performance in complex ways. We explore these interactions to motivate path selection targeting holistic memory demand. We enumerate all the aspects involved in a path selection design and evaluate a comprehensive set of approaches for each aspect. Finally, we propose a path selection strategy that reduces memory demands by 20% and at the same time improves performance by 5-20% compared to an industrial-strength DBT.
Tailoring dynamic software product lines
Authors: Rosenmüller Marko , Siegmund Norbert , Pukall Mario , Apel Sven
Published: April 2020

Software product lines (SPLs)
and
adaptive systems
aim at variability to cope with changing requirements. Variability can be described in terms of
features
, which are central for development and configuration of SPLs. In traditional SPLs, features are bound statically before runtime. By contrast, adaptive systems support feature binding at runtime and are sometimes called
dynamic SPLs (DSPLs)
. DSPLs are usually built from coarse-grained components, which reduces the number of possible application scenarios. To overcome this limitation, we closely integrate static binding of traditional SPLs and runtime adaptation of DSPLs. We achieve this integration by statically generating a tailor-made DSPL from a highly customizable SPL. The generated DSPL provides only the runtime variability required by a particular application scenario and the execution environment. The DSPL supports self-configuration based on coarse-grained modules. We provide a feature-based adaptation mechanism that reduces the effort of computing an optimal configuration at runtime. In a case study, we demonstrate the practicability of our approach and show that a seamless integration of static binding and runtime adaptation reduces the complexity of the adaptation process.
Less is more
Authors: Arnoldus B. J. , van den Brand M. G.J. , Serebrenik A.
Published: April 2020

A code generator is a program translating an input model into code. In this paper we focus on template-based code generators in the context of the model view controller architecture (MVC).

The language in which the code generator is written is known as a metalanguage in the code generation parlance. The metalanguage should be, on the one side, expressive enough to be of practical value, and, on the other side, restricted enough to enforce the separation between the view and the model, according to the MVC.

In this paper we advocate the notion of
unparser-complete metalanguages
as providing the right level of expressivity. An unparser-complete metalanguage is capable of expressing an unparser, a code generator that translates any legal abstract syntax tree into an equivalent sentence of the corresponding context-free language. A metalanguage not able to express an unparser will fail to produce all sentences belonging to the corresponding context-free language. A metalanguage able to express more than an unparser will also be able to implement code violating the model/view separation.

We further show that a metalanguage with the power of a linear deterministic tree-to-string transducer is unparser-complete. Moreover, this metalanguage has been successfully applied in a non-trivial case study where an existing code generator is refactored using templates.
A DSL for cross-domain security
Authors: Hardin David S. , Slind Konrad L. , Whalen Michael W. , Pham Tuang-Hung
Published: April 2020

Guardol is a domain-specific language focused on the creation of high-assurance network guards and the specification of guard properties. The Guardol system generates Ada code from Guardol programs and also provides specification and automated verification support. Guard programs and specifications are translated to higher order logic, then deductively transformed to a form suitable for a SMT-style decision procedure for recursive functions over tree-structured data. The result is that difficult properties of Guardol programs can be proved fully automatically.
Synthesizing iterators from abstraction functions
Authors: Rayside Derek , Montaghami Vajihollah , Leung Francesca , Yuen Albert , Xu Kevin , Jackson Daniel
Published: April 2020

A technique for synthesizing iterators from declarative abstraction functions written in a relational logic specification language is described. The logic includes a transitive closure operator that makes it convenient for expressing reachability queries on linked data structures. Some optimizations, including tuple elimination, iterator flattening, and traversal state reduction, are used to improve performance of the generated iterators.

A case study demonstrates that most of the iterators in the widely used JDK Collections classes can be replaced with code synthesized from declarative abstraction functions. These synthesized iterators perform competitively with the hand-written originals.

In a user study the synthesized iterators always passed more test cases than the hand-written ones, were almost always as efficient, usually took less programmer effort, and were the qualitative preference of all participants who provided free-form comments.
Local Reasoning for Global Invariants, Part II
Authors: Banerjee Anindya , Naumann David A.
Published: April 2020

Dedicated to the memory of John C. Reynolds (1935--2013).

The hiding of internal invariants creates a mismatch between procedure specifications in an interface and proof obligations on the implementations of those procedures. The mismatch is sound if the invariants depend only on encapsulated state, but encapsulation is problematic in contemporary software due to the many uses of shared mutable objects. The mismatch is formalized here in a proof rule that achieves flexibility via explicit restrictions on client effects, expressed using ghost state and ordinary first order assertions. The restrictions amount to a stateful frame condition that must be satisfied by any client; this dynamic encapsulation boundary complements conventional scope-based encapsulation. The technical development is based on a companion article, Part I, that presents Region Logic---a programming logic with stateful frame conditions for commands.
Local Reasoning for Global Invariants, Part I
Authors: Banerjee Anindya , Naumann David A. , Rosenberg Stan
Published: April 2020

Dedicated to the memory of Stephen L. Bloom (1940--2010).

Shared mutable objects pose grave challenges in reasoning, especially for information hiding and modularity. This article presents a novel technique for reasoning about error-avoiding partial correctness of programs featuring shared mutable objects, and investigates the technique by formalizing a logic. Using a first-order assertion language, the logic provides heap-local reasoning about mutation and separation, via ghost fields and variables of type “region” (finite sets of object references). A new form of frame condition specifies write, read, and allocation effects using region expressions; this supports a frame rule that allows a command to read state on which the framed predicate depends. Soundness is proved using a standard program semantics. The logic facilitates heap-local reasoning about object invariants, as shown here by examples. Part II of this article extends the logic with second-order framing which formalizes the hiding of data invariants.
A constraint programming approach for integrated spatial and temporal scheduling for clustered architectures
Authors: Beg Mirza , Beek Peter van
Published: April 2020

Many embedded processors use clustering to scale up instruction-level parallelism in a cost-effective manner. In a clustered architecture, the registers and functional units are partitioned into smaller units and clusters communicate through register-to-register copy operations. Texas Instruments, for example, has a series of architectures for embedded processors which are clustered. Such an architecture places a heavier burden on the compiler, which must now assign instructions to clusters (spatial scheduling), assign instructions to cycles (temporal scheduling), and schedule copy operations to move data between clusters. We consider instruction scheduling of local blocks of code on clustered architectures to improve performance. Scheduling for space and time is known to be a hard problem. Previous work has proposed greedy approaches based on list scheduling to simultaneously perform spatial and temporal scheduling and phased approaches based on first partitioning a block of code to do spatial assignment and then performing temporal scheduling. Greedy approaches risk making mistakes that are then costly to recover from, and partitioning approaches suffer from the well-known phase ordering problem. In this article, we present a constraint programming approach for scheduling instructions on clustered architectures. We employ a problem decomposition technique that solves spatial and temporal scheduling in an integrated manner. We analyze the effect of different hardware parameters—such as the number of clusters, issue-width, and intercluster communication cost—on application performance. We found that our approach was able to achieve an improvement of up to 26%, on average, over a state-of-the-art technique on superblocks from SPEC 2000 benchmarks.
The Intel labs Haskell research compiler
Authors: Liu Hai , Glew Neal , Petersen Leaf , Anderson Todd A.
Published: April 2020

The Glasgow Haskell Compiler (GHC) is a well supported optimizing compiler for the Haskell programming language, along with its own extensions to the language and libraries. Haskell's lazy semantics imposes a runtime model which is in general difficult to implement efficiently. GHC achieves good performance across a wide variety of programs via aggressive optimization taking advantage of the lack of side effects, and by targeting a carefully tuned virtual machine. The Intel Labs Haskell Research Compiler uses GHC as a frontend, but provides a new whole-program optimizing backend by compiling the GHC intermediate representation to a relatively generic functional language compilation platform. We found that GHC's external Core language was relatively easy to use, but reusing GHC's libraries and achieving full compatibility were harder. For certain classes of programs, our platform provides substantial performance benefits over GHC alone, performing 2x faster than GHC with the LLVM backend on selected modern performance-oriented benchmarks; for other classes of programs, the benefits of GHC's tuned virtual machine continue to outweigh the benefits of more aggressive whole program optimization. Overall we achieve parity with GHC with the LLVM backend. In this paper, we describe our Haskell compiler stack, its implementation and optimization approach, and present benchmark results comparing it to GHC.
Monadic functional reactive programming
Authors: van der Ploeg Atze
Published: April 2020

Functional Reactive Programming (FRP) is a way to program reactive systems in functional style, eliminating many of the problems that arise from imperative techniques. In this paper, we present an alternative FRP formulation that is based on the notion of a reactive computation: a monadic computation which may require the occurrence of external events to continue. A signal computation is a reactive computation that may also emit values. In contrast to signals in other FRP formulations, signal computations can end, leading to a monadic interface for sequencing signal phases. This interface has several advantages: routing is implicit, sequencing signal phases is easier and more intuitive than when using the switching combinators found in other FRP approaches, and dynamic lists require much less boilerplate code. In other FRP approaches, either the entire FRP expression is re-evaluated on each external stimulus, or impure techniques are used to prevent redundant re-computations. We show how Monadic FRP can be implemented straightforwardly in a purely functional way while preventing redundant re-computations.
Adding structure to monoids
Authors: BlaĚević Mario
Published: April 2020

This paper presents the rationale and design of
monoid-subclasses
. This Haskell library consists of a collection of type classes that generalize the interface of several common data types, most importantly those used to represent strings. We demonstrate that the mathematical theory behind
monoid-subclasses
can bring substantial practical benefits to the Haskell library ecosystem by generalizing
attoparsec
, one of the most popular Haskell parsing libraries.
Mio
Authors: Voellmy Andreas Richard , Wang Junchang , Hudak Paul , Yamamoto Kazuhiko
Published: April 2020

Haskell threads provide a key, lightweight concurrency abstraction to simplify the programming of important network applications such as web servers and software-defined network (SDN) controllers. The flagship Glasgow Haskell Compiler (GHC) introduces a run-time system (RTS) to achieve a high-performance multicore implementation of Haskell threads, by introducing effective components such as a multicore scheduler, a parallel garbage collector, an IO manager, and efficient multicore memory allocation. Evaluations of the GHC RTS, however, show that it does not scale well on multicore processors, leading to poor performance of many network applications that try to use lightweight Haskell threads. In this paper, we show that the GHC IO manager, which is a crucial component of the GHC RTS, is the scaling bottleneck. Through a series of experiments, we identify key data structure, scheduling, and dispatching bottlenecks of the GHC IO manager. We then design a new multicore IO manager named Mio that eliminates all these bottlenecks. Our evaluations show that the new Mio manager improves realistic web server throughput by 6.5x and reduces expected web server response time by 5.7x. We also show that with Mio, McNettle (an SDN controller written in Haskell) can scale effectively to 40+ cores, reach a throughput of over 20 million new requests per second on a single machine, and hence become the fastest of all existing SDN controllers.
Extensible effects
Authors: Kiselyov Oleg , Sabry Amr , Swords Cameron
Published: April 2020

We design and implement a library that solves the long-standing problem of combining effects without imposing restrictions on their interactions (such as static ordering). Effects arise from interactions between a client and an effect handler (interpreter); interactions may vary throughout the program and dynamically adapt to execution conditions. Existing code that relies on monad transformers may be used with our library with minor changes, gaining efficiency over long monad stacks. In addition, our library has greater expressiveness, allowing for practical idioms that are inefficient, cumbersome, or outright impossible with monad transformers.

Our alternative to a monad transformer stack is a single monad, for the coroutine-like communication of a client with its handler. Its type reflects possible requests, i.e., possible effects of a computation. To support arbitrary effects and their combinations, requests are values of an extensible union type, which allows adding and, notably, subtracting summands. Extending and, upon handling, shrinking of the union of possible requests is reflected in its type, yielding a type-and-effect system for Haskell. The library is lightweight, generalizing the extensible exception handling to other effects and accurately tracking them in types.
Freeze after writing
Authors: Kuper Lindsey , Turon Aaron , Krishnaswami Neelakantan R. , Newton Ryan R.
Published: April 2020

Deterministic-by-construction parallel programming models offer the advantages of parallel speedup while avoiding the nondeterministic, hard-to-reproduce bugs that plague fully concurrent code. A principled approach to deterministic-by-construction parallel programming with shared state is offered by
LVars
: shared memory locations whose semantics are defined in terms of an application-specific lattice. Writes to an LVar take the least upper bound of the old and new values with respect to the lattice, while reads from an LVar can observe only that its contents have crossed a specified threshold in the lattice. Although it guarantees determinism, this interface is quite limited.

We extend LVars in two ways. First, we add the ability to "freeze" and then read the contents of an LVar directly. Second, we add the ability to attach event handlers to an LVar, triggering a callback when the LVar's value changes. Together, handlers and freezing enable an expressive and useful style of parallel programming. We prove that in a language where communication takes place through these extended LVars, programs are at worst
quasi-deterministic
: on every run, they either produce the same answer or raise an error. We demonstrate the viability of our approach by implementing a library for Haskell supporting a variety of LVar-based data structures, together with a case study that illustrates the programming model and yields promising parallel speedup.
Tabular
Authors: Gordon Andrew D. , Graepel Thore , Rolland Nicolas , Russo Claudio , Borgstrom Johannes , Guiver John
Published: April 2020

We propose a new kind of probabilistic programming language for machine learning. We write programs simply by annotating existing relational schemas with probabilistic model expressions. We describe a detailed design of our language, Tabular, complete with formal semantics and type system. A rich series of examples illustrates the expressiveness of Tabular. We report an implementation, and show evidence of the succinctness of our notation relative to current best practice. Finally, we describe and verify a transformation of Tabular schemas so as to predict missing values in a concrete database. The ability to query for missing values provides a uniform interface to a wide variety of tasks, including classification, clustering, recommendation, and ranking.
Abstract satisfaction
Authors: D'Silva Vijay , Haller Leopold , Kroening Daniel
Published: April 2020

This article introduces an abstract interpretation framework that codifies the operations in SAT and SMT solvers in terms of lattices, transformers and fixed points. We develop the idea that a formula denotes a set of models in a universe of structures. This set of models has characterizations as fixed points of deduction, abduction and quantification transformers. A wide range of satisfiability procedures can be understood as computing and refining approximations of such fixed points. These include procedures in the DPLL family, those for preprocessing and inprocessing in SAT solvers, decision procedures for equality logics, weak arithmetics, and procedures for approximate quantification. Our framework provides a unified, mathematical basis for studying and combining program analysis and satisfiability procedures. A practical benefit of our work is a new, logic-agnostic architecture for implementing solvers.
Abstract effects and proof-relevant logical relations
Authors: Benton Nick , Hofmann Martin , Nigam Vivek
Published: April 2020

We give a denotational semantics for a region-based effect system that supports type abstraction in the sense that only externally visible effects need to be tracked: non-observable internal modifications, such as the reorganisation of a search tree or lazy initialisation, can count as 'pure' or 'read only'. This 'fictional purity' allows clients of a module to validate soundly more effect-based program equivalences than would be possible with previous semantics. Our semantics uses a novel variant of logical relations that maps types not merely to partial equivalence relations on values, as is commonly done, but rather to a proof-relevant generalisation thereof, namely setoids. The objects of a setoid establish that values inhabit semantic types, whilst its morphisms are understood as proofs of semantic equivalence. The transition to proof-relevance solves twoawkward problems caused by naïve use of existential quantification in Kripke logical relations, namely failure of admissibility and spurious functional dependencies.
Verifying eventual consistency of optimistic replication systems
Authors: Bouajjani Ahmed , Enea Constantin , Hamza Jad
Published: April 2020

We address the verification problem of eventual consistency of optimistic replication systems. Such systems are typically used to implement distributed data structures over large scale networks. We introduce a formal definition of eventual consistency that applies to a wide class of existing implementations, including the ones using speculative executions. Then, we reduce the problem of checking eventual consistency to reachability and model checking problems. This reduction enables the use of existing verification tools for message-passing programs in the context of verifying optimistic replication systems. Furthermore, we derive from these reductions decision procedures for checking eventual consistency of systems implemented as finite-state programs communicating through unbounded unordered channels.
Applying quantitative semantics to higher-order quantum computing
Authors: Pagani Michele , Selinger Peter , Valiron Benoît
Published: April 2020

Finding a denotational semantics for higher order quantum computation is a long-standing problem in the semantics of quantum programming languages. Most past approaches to this problem fell short in one way or another, either limiting the language to an unusably small finitary fragment, or giving up important features of quantum physics such as entanglement. In this paper, we propose a denotational semantics for a quantum lambda calculus with recursion and an infinite data type, using constructions from quantitative semantics of linear logic.
Game semantics for interface middleweight Java
Authors: Murawski Andrzej S. , Tzevelekos Nikos
Published: April 2020

We consider an object calculus in which open terms interact with the environment through interfaces. The calculus is intended to capture the essence of contextual interactions of Middleweight Java code. Using game semantics, we provide fully abstract models for the induced notions of contextual approximation and equivalence. These are the first denotational models of this kind.
Proofs that count
Authors: Farzan Azadeh , Kincaid Zachary , Podelski Andreas
Published: April 2020

Counting arguments are among the most basic proof methods in mathematics. Within the field of formal verification, they are useful for reasoning about programs with
infinite control
, such as programs with an unbounded number of threads, or (concurrent) programs with recursive procedures. While counting arguments are common in informal, hand-written proofs of such programs, there are no fully
automated
techniques to construct counting arguments. The key questions involved in automating counting arguments are:
how to decide what should be counted?
, and
how to decide when a counting argument is valid?
In this paper, we present a technique for automatically constructing and checking counting arguments, which includes novel solutions to these questions.
A galois connection calculus for abstract interpretation
Authors: Cousot Patrick` , Cousot Radhia
Published: April 2020

We introduce a Galois connection calculus for language independent specification of abstract interpretations used in programming language semantics, formal verification, and static analysis. This Galois connection calculus and its type system are typed by abstract interpretation.
Polymorphic identifiers
Authors: Weiher Marcel , Hirschfeld Robert
Published: April 2020

In object-oriented programming, polymorphic dispatch of operations decouples clients from specific providers of services and allows implementations to be modified or substituted without affecting clients.

The Uniform Access Principle (UAP) tries to extend these qualities to resource access by demanding that access to state be indistinguishable from access to operations. Despite language features supporting the UAP, the overall goal of substitutability has not been achieved for either alternative resources such as keyed storage, files or web pages, or for alternate access mechanisms: specific kinds of resources are bound to specific access mechanisms and vice versa. Changing storage or access patterns either requires changes to both clients and service providers and trying to maintain the UAP imposes significant penalties in terms of code-duplication and/or performance overhead.

We propose introducing first class identifiers as polymorphic names for storage locations to solve these problems. With these
Polymorphic Identifiers
, we show that we can provide uniform access to a wide variety of resource types as well as storage and access mechanisms, whether parametrized or direct, without affecting client code, without causing code duplication or significant performance penalties.
Cast insertion strategies for gradually-typed objects
Authors: Allende Esteban , Fabry Johan , Tanter Éric
Published: April 2020

Gradual typing enables a smooth and progressive integration of static and dynamic typing. The semantics of a gradually-typed program is given by translation to an intermediate language with casts: runtime type checks that control the boundaries between statically- and dynamically-typed portions of a program. This paper studies the performance of different cast insertion strategies in the context of Gradualtalk, a gradually-typed Smalltalk. We first implement the strategy specified by Siek and Taha, which inserts casts at call sites. We then study the dual approach, which consists in performing casts in callees. Based on the observation that both strategies perform well in different scenarios, we design a hybrid strategy that combines the best of each approach. We evaluate these three strategies using both micro- and macro-benchmarks. We also discuss the impact of these strategies on memory, modularity, and inheritance. The hybrid strategy constitutes a promising cast insertion strategy for adding gradual types to existing dynamically-typed languages.
Automata column
Authors: Bojańczyk Mikołaj
Published: April 2020

It will be my great pleasure and honour to edit the column on automata in the SIGLOG newsletter. The study of connections between logic and automata has seen a lot of development in recent years, and seems to be in robustly good shape. For instance, among the best paper awards for ICALP Track B in the years 2000--2013, all but five awarded papers had the words "automaton" or "regular language" in the title and, of the remaining five, two were also about automata theory. Also promising is a large number of strong new researchers, which means that the field is likely to be around in ten years.
Verification column
Authors: Rybalchenko Andrey
Published: April 2020

Verification can be described as a process applying logical reasoning to mathematical models of computation. Often these models represent software and hardware systems or their components, however, various other application domains, for example, systems biology, can also benefit from verification techniques.
A short introduction to the coalgebraic method
Authors: Silva Alexandra
Published: April 2020

This article contains a brief introduction to coalgebra and an overview of a recent proof of correctness for Brzozowski's algorithm which uses coalgebraic techniques. In the discussion section we briefly discuss the most active research lines in the coalgebra community and take a personal outlook at what future might bring for the field.
Automata column
Authors: Bojańczyk Mikołaj
Published: April 2020

In this column, Sylvain Schmitz summarizes two recent advances on the complexity of the reachability problem for vector addition systems with states. This is one of the most celebrated decidable problems in theoretical computer science, and until now, there was absolutely no upper bound on the complexity. It was only known that the algorithms run in finite time. The first advance described in this column, by Leroux and Schmitz, is a computable upper bound on the running time of the (original) algorithm for the problem. Admittedly, the upper bound puts the Ackermann function to shame -- read the great column to see what it is --- but it's an upper bound. The second advance, by Blondin, Finkel, Göller, Haase and McKenzie, is finding the exact complexity, namely PSPACE complete, of the two dimensional case, something that has also been open for several decades.
Semantics column
Authors: Mislove Michael
Published: April 2020

We begin the New Year with a column by Andy Pitts on
Nominal Techniques.
Nominality -- the property of being nominal (as the dictionary defines it) -- refers to the use of names. Nominal techniques offer a method to define locality of variables in programming languages, for example. Andy's survey covers a wide range of applications, provides a brief history of the area, a state-of-the-art summary and a glimpse into issues that remain unresolved. Because the article is so thorough, there's not much to add to his discussion.
Security by compilation
Authors: Wang Chao , Schaumont Patrick
Published: April 2020

We explain how formal verification and program synthesis can be used to (1) detect side-channel leaks of software code running on portable devices, (2) prove the absence of side-channel leaks, and (3) transform software to eliminate such leaks. We use power side-channel leaks in cryptographic software as examples, but the underlying techniques are applicable to other types of side channels and software systems as well.
Report on POPL 2017
Authors: Toninho Bernardo
Published: April 2020

For researchers working on programming languages (or related fields), mid-January always brings the excitement of a new edition of the ACM Symposium on Principles of Programming Languages (POPL). POPL is a chance to learn about the best work that is happening in the field, usually with more emphasis on the theoretical aspects of programming language research, but not exclusively so - which is one of the many things that makes POPL great.
Conference reports
Authors: Pérez Jorge A.
Published: April 2020

In this installment of the conference report column, Cláudia Nalon, Daniele Nantes Sobrinho, Elaine Pimentel, and João Marcos report on the Brasília Spring on Automated Reasoning. This event brought to South America a whole week of conferences, workshops, and tutorials on Automated Reasoning. The numbers truly speak for the scale and quality of this event: 3 conferences (TABLEAUX, FroCos, and ITP), 4 workshops, 4 tutorials, and 165 participants from all over the world (including 16 invited speakers). I am most grateful to Cláudia, Daniele, Elaine, and João for their availability and detailed report.

I look forward to receiving your reports and/or personal impressions on conferences and scientific meetings broadly related to SIGLOG. As usual, I will also be pleased to hear all your ideas and suggestions for future installments of the column.
Session details: HEART 2012 workshop
Authors: Amano Hideharu , Luk Wayne
Published: April 2020

It is a pleasure for us to hold the Third International Workshop on Highly-Efficient Accelerators and Reconfigurable Technologies (HEART) in Okinawa Japan.

Supercomputing using cost-effective accelerators, such as high-end field-programmable gate arrays, general-purpose graphics processing units and other specialized architectures, has become a major theme in high-performance computing. The goal of this workshop is to establish a forum for reporting state-of-the-art research on high-performance computing with such cost-effective accelerators. The workshop was affiliated to the ACM International Conference on Supercomputing in 2010, and became an independent workshop in 2011. This year it is held on the next two days after IEICE technical meeting on reconfigurable systems sharing some events.

The program of the 3 rd HEART Workshop includes 15 regular papers and 10 posters. They are selected from 35 submissions from 12 countries (China, France, Germany, Hong Kong, Iran, Japan, Singapore, Spain, Sweden, Taiwan, UK, and US). The selected presentations span a wide range of topics related to the aim of the workshop and the two invited keynote lectures focus on Cyber-physical MPSoC Systems and supercomputing with GPU. An invited industrial lecture is a shared event with the IEICE reconfigurable systems technical meeting. Also before the reception, the second FPGA design contest "Connect 6 Revenge" demonstrates real-time matches between FPGA connect6 players.
Summary of the International Conference on Software and System Processes (ICSSP 2018)
Authors: Kuhrmann Marco , O'Connor Rory V. , Houston Dan , Hebig Regina , Raffo David
Published: April 2020

The International Conference on Software and System Processes (ICSSP), continuing the success of Software Process Workshop (SPW), the Software Process Modeling and Simulation Workshop (ProSim) and the International Conference on Software Process (ICSP) conference series, has become the established premier event in the field of software and systems engineering processes. It provides a leading forum for the exchange of research outcomes and industrial best-practices in process development from software and systems disciplines. ICSSP 2018 was held in Gothenburg, Sweden, 26-27 May 2018, co-located with the 40th International Conference on Software Engineering (ICSE). The theme of ICSSP 2018 was studying \Demands on Processes, Processes on Demand" by recognizing the demands on processes that include the need for both welldeveloped plans and incremental deliveries (agile and hybrid processes), utilization of increased automation (model-based engineering and DevOps), higher degrees of customer collaboration, comprehensive analysis of existing products for reuse (open source and COTS), and performance requirements of enterprise-level architectures. Papers presented at ICSSP discussed these issues across different domains, providing concepts, evidence, and experiences.
PROMPT - Master Courses for Professional SoftwareDevelopers
Authors: Eck Stefan , Hansson Hans A.
Published: April 2020

PROMPT [1] is an educational initiative in cooperation with several academic parties and leading industrial companies and organizations. Together, the parties offer advanced level courses in software engineering in a web-based format, tailored to fit professional engineers and software developers who need to be able to combine full-time work and studies. The long-term goal of PROMPT is to guarantee the supply of advanced software competencies and innovativeness in industry. The courses are free of charge within Europe, cover typically 7.5 university credits and are run over a whole semester, at a pace of 25% of full-time. All courses are developed in close cooperation with the Swedish industry and trade organizations.
Summary of the 5th International Workshop on Requirements Engineering and Testing (RET 2018)
Authors: Unterkalmsteiner Michael , Yu Tingting , Gay Gregory , Bjarnason Elizabeth , Borg Markus , Felderer Michael
Published: April 2020

The RET (Requirements Engineering and Testing) workshop series provides a meeting point for researchers and practitioners from the two separate elds of Requirements Engineering (RE) and Testing. The goal is to improve the connection and alignment of these two areas through an exchange of ideas, challenges, practices, experiences and results. The long term aim is to build a community and a body of knowledge within the intersection of RE and Testing, i.e. RET. The 5th workshop was held in colocation with ICSE 2018 in Gothenburg, Sweden. The workshop continued in the same interactive vein as the predecessors. We introduced a new format for the presentations in which the paper authors had the opportunity to interact extensively with the audience. Each author was supported by a member of the organization committee to prepare either an extensive demo, collect more data in form of a questionnaire or perform a hands-on tutorial. We named this new format \X-ray session". In order to create an RET knowledge base, this cross-cutting area elicits contributions from both RE and Testing, and from both researchers and practitioners. A range of papers were presented from short positions papers to full research papers that cover connections between the two elds. The workshop attracted 27 participants and the positive feedback on the new format encourages us to organize the workshop the next year again.
Engineering Multi-Agent Systems
Authors: Mascardi Viviana , Weyns Danny , Ricci Alessandro
Published: April 2020

The continuous integration of software-intensive systems together with the ever-increasing computing power offer a breeding ground for intelligent agents and multi-agent systems (MAS) more than ever before. Over the past two decades, a wide variety of languages, models, techniques and methodologies have been proposed to engineer agents and MAS. Despite this substantial body of knowledge and expertise, the systematic engineering of large-scale and open MAS still poses many challenges. Researchers and engineers still face fundamental questions regarding theories, architectures, languages, processes, and platforms for designing, implementing, running, maintaining, and evolving MAS. This paper reports on the results of the 6th International Workshop on Engineering Multi-Agent Systems (EMAS 2018, 14th-15th of July, 2018, Stockholm, Sweden), where participants discussed the issues above focusing on the state of affairs and the road ahead for researchers and engineers in this area.
Semantics column
Authors: Mislove Michael
Published: April 2020

This quarter's
Semantics
column is devoted to a survey of BI-Logic - the
logic of bunched implications
- by David Pym. BI-Logics have a broad range of applications, including program verification. In particular they underpin Separation Logic which has attracted considerable attention both in the theory community and in industry. Notably, Steve Brookes and Peter O'Hearn were awarded the 2016 Gödel Prize for their work developing Concurrent Separation logic (CSL) (an accomplishment we were pleased to acknowledge in this series [Brookes and O'Hearn 2016]), and CSL has been successfully deployed at Facebook, and elsewhere. In fact, it was Peter who proposed that I invite David to write a column on BI-Logics, a suggestion I am happy to acknowledge.
Helmut Veith memorial workshop 2019 report
Authors: Morak Michael , Prianichnikova Anna , Sokolova Ana
Published: April 2020

Helmut Veith Memorial Workshop (HVW) is a memorial workshop in honour of Helmut Veith, a dear friend and colleague, logician and computer scientist who contributed significantly to the area of verification and logics in computer science, professor at TU Vienna who tragically died too early at the age of 45 years 3 years ago.

The workshop follows his wish for having an informal meeting in the mountains, mixing science and snow fun. The workshop is organised in such a way that half of the day is spent in talks, and the other half skiing, discussing, or working together at a venue in the Austrian Alps. It is a nice opportunity to exchange ideas and meet colleagues from the Austrian logic in computer science community and beyond, as well as to spend pleasant days with science and skiing, and even bring family along.
Trembr
Authors: Fu Tao-Yang , Lee Wang-Chien
Published: April 2020

In this article, we propose a novel representation learning framework, namely
TRajectory EMBedding via Road networks (Trembr)
, to learn
trajectory embeddings
(low-dimensional feature vectors) for use in a variety of trajectory applications. The novelty of Trembr lies in (1) the design of a recurrent neural network--(RNN) based encoder--decoder model, namely
Traj2Vec
, that encodes spatial and temporal properties inherent in trajectories into trajectory embeddings by exploiting the underlying road networks to constrain the learning process in accordance with the matched road segments obtained using road network matching techniques (e.g., Barefoot [24, 27]), and (2) the design of a neural network--based model, namely
Road2Vec
, to learn
road segment embeddings
in road networks that captures various relationships amongst road segments in preparation for trajectory representation learning. In addition to model design, several unique technical issues raising in Trembr, including data preparation in Road2Vec, the road segment relevance-aware loss, and the network topology constraint in Traj2Vec, are examined. To validate our ideas, we learn trajectory embeddings using multiple large-scale real-world trajectory datasets and use them in three tasks, including trajectory similarity measure, travel time prediction, and destination prediction. Empirical results show that Trembr soundly outperforms the state-of-the-art trajectory representation learning models,
trajectory2vec
and
t2vec
, by at least one order of magnitude in terms of mean rank in trajectory similarity measure, 23.3% to 41.7% in terms of mean absolute error (MAE) in travel time prediction, and 39.6% to 52.4% in terms of MAE in destination prediction.
Differentiating Population Spatial Behavior Using Representative Features of Geospatial Mobility (ReFGeM)
Authors: Zhang Rui , Stanley Kevin G. , Fuller Daniel , Bell Scott
Published: April 2020

Understanding how humans use and consume space by comparing stratified groups, either through observation or controlled study, is key to designing better spaces, cities, and policies. GPS data traces provide detailed movement patterns of individuals but can be difficult to interpret due to the scale and scope of the data collected. For actionable insights, GPS traces are usually reduced to one or more features that express the spatial phenomenon of interest. However, it is not always clear which spatial features should be employed, and substantial effort can be invested into designing features that may or may not provide insight. In this article, we present an alternative approach: a standardized feature set with actionable interpretations that can be efficiently run against many datasets. We show that these features can distinguish between disparate human mobility patterns, although no single feature can distinguish them alone.
Exploring Correlation Network for Cheating Detection
Authors: Luo Ping , Shu Kai , Wu Junjie , Wan Li , Tan Yong
Published: April 2020

The correlation network, typically formed by computing pairwise correlations between variables, has recently become a competitive paradigm to discover insights in various application domains, such as climate prediction, financial marketing, and bioinformatics. In this study, we adopt this paradigm to detect cheating behavior hidden in business distribution channels, where falsified big deals are often made by collusive partners to obtain lower product prices—a behavior deemed to be extremely harmful to the sale ecosystem. To this end, we assume that abnormal deals are likely to occur between two partners if their purchase-volume sequences have a strong negative correlation. This seemingly intuitive rule, however, imposes several research challenges. First, existing correlation measures are usually symmetric and thus cannot distinguish the different roles of partners in cheating. Second, the tick-to-tick correspondence between two sequences might be violated due to the possible delay of purchase behavior, which should also be captured by correlation measures. Finally, the fact that any pair of sequences could be correlated may result in a number of false-positive cheating pairs, which need to be corrected in a systematic manner. To address these issues, we propose a correlation network analysis framework for cheating detection. In the framework, we adopt an asymmetric correlation measure to distinguish the two roles, namely,
cheating seller
and
cheating buyer
, in a cheating alliance.
Dynamic Time Warping
is employed to address the time offset between two sequences in computing the correlation. We further propose two
graph-cut
methods to convert the correlation network into a bipartite graph to rank cheating partners, which simultaneously helps to remove false-positive correlation pairs. Based on a 4-year real-world channel dataset from a worldwide IT company, we demonstrate the effectiveness of the proposed method in comparison to competitive baseline methods.
Social Science–guided Feature Engineering
Authors: Beigi Ghazaleh , Tang Jiliang , Liu Huan
Published: April 2020

Many real-world relations can be represented by signed networks with positive links (e.g., friendships and trust) and negative links (e.g., foes and distrust). Link prediction helps advance tasks in social network analysis such as recommendation systems. Most existing work on link analysis focuses on unsigned social networks. The existence of negative links piques research interests in investigating whether properties and principles of signed networks differ from those of unsigned networks and mandates dedicated efforts on link analysis for signed social networks. Recent findings suggest that properties of signed networks substantially differ from those of unsigned networks and negative links can be of significant help in signed link analysis in complementary ways. In this article, we center our discussion on a challenging problem ofsigned link analysis. Signed link analysis faces the problem of data sparsity, i.e., only a small percentage of signed links are given. This problem can even get worse when negative links are much sparser than positive ones as users are inclined more toward positive disposition rather than negative. We investigate how we can take advantage of other sources of information for signed link analysis. This research is mainly guided by three social science theories,Emotional Information,Diffusion of Innovations, andIndividual Personality. Guided by these, we extract three categories of related features and leverage them for signed link analysis. Experiments show the significance of the features gleaned from social theories for signed link prediction and addressing the data sparsity challenge.
Symbolic Verification of Regular Properties for Java Programs
Authors: Chen Zhenbang , Yu Hengbiao , Wang Ji , Dong Wei
Published: April 2020

Verifying the regular properties of a program is challenging. In this extended abstract, we report our recent progress of verifying regular properties based on dynamic symbolic execution (DSE). We propose two algorithms for DSE to improve the scalability of verification. Guiding algorithm boosts the falsification of verification. Slicing algorithm prunes redundant paths to boost path exploration. Based on JPF, we have implemented our verification method for Java programs. The results of the extensive experiments on real-world Java open-source programs are promising.