Search

Context: Edge graphs are graphs whose edges are labelled with identifiers, and nodes can have multiple edges between them. They are used to model a wide range of systems, including networks with distances or degrees of connection and complex relational data. Inquiry: Unfortunately, the homogeneity of this graph structure prevents an effective representation in (functional) programs. Either their interface is riddled with partial functions, or the representations are computationally inefficient to process. Approach: We present a novel data type for edge graphs, based on total and recursive definitions, that prevents usage errors from partial APIs and promotes structurally recursive computations. We follow an algebraic approach and provide a set of primitive constructors and combinators, along with equational laws that identify semantically equivalent constructions. Knowledge: This algebra translates directly into an implementation using algebraic data types, and its homomorphisms give rise to functions for manipulating and transforming these edge graphs. Grounding: We exploit the fact that many common graph algorithms are such homomorphisms to implement them in our framework. Importance: In giving a theoretical grounding for the edge graph data type, we can formalise properties such as soundness and completeness of the representation while also minimising usage errors and maximising re-usability.

Bipartite Experiments are randomized experiments where the treatment is applied to a set of units (randomization units) that is different from the units of analysis, and randomization units and analysis units are connected through a bipartite graph. The scale of experimentation at large online platforms necessitates both accurate inference in the presence of a large bipartite interference graph, as well as a highly scalable implementation. In this paper, we describe new methods for inference that enable practical, scalable analysis of bipartite experiments: (1) We propose CA-ERL, a covariate-adjusted variant of the exposure-reweighted-linear (ERL) estimator [9], which empirically yields 60-90% variance reduction. (2) We introduce a randomization-based method for inference and prove asymptotic validity of a Wald-type confidence interval under graph sparsity assumptions. (3) We present a linear-time algorithm for randomization inference of the CA-ERL estimator, which can be easily implemented in query engines like Presto or Spark. We evaluate our methods both on a real experiment at Meta that randomized treatment on Facebook Groups and analyzed user-level metrics, as well as simulations on synthetic data. The real-world data shows that our CA-ERL estimator reduces the confidence interval (CI) width by 60-90% (compared to ERL) in a practical setting. The simulations using synthetic data show that our randomization inference procedure achieves correct coverage across instances, while the ERL estimator has incorrectly small CI widths for instances with large true effect sizes and is overly conservative when the bipartite graph is dense.

Online A/B testing is widely used in the internet industry to inform decisions on new feature roll-outs. For online marketplaces (such as advertising markets), standard approaches to A/B testing may lead to biased results when buyers operate under a budget constraint, as budget consumption in one arm of the experiment impacts performance of the other arm. To counteract this interference, one can use a budget-split design where the budget constraint operates on a per-arm basis and each arm receives an equal fraction of the budget, leading to ``budget-controlled A/B testing.'' Despite clear advantages of budget-controlled A/B testing, performance degrades when budget are split too small, limiting the overall throughput of such systems. In this paper, we propose a parallel budget-controlled A/B testing design where we use market segmentation to identify submarkets in the larger market, and we run parallel experiments on each submarket. Our contributions are as follows: First, we introduce and demonstrate the effectiveness of the parallel budget-controlled A/B test design with submarkets in a large online marketplace environment. Second, we formally define market interference in first-price auction markets using the first price pacing equilibrium (FPPE) framework. Third, we propose a debiased surrogate that eliminates the first-order bias of FPPE, drawing upon the principles of sensitivity analysis in mathematical programs. Fourth, we derive a plug-in estimator for the surrogate and establish its asymptotic normality. Fifth, we provide an estimation procedure for submarket parallel budget-controlled A/B tests. Finally, we present numerical examples on semi-synthetic data, confirming that the debiasing technique achieves the desired coverage properties.

Some effects are considered to be higher-level than others. High-level effects provide expressive and succinct abstraction of programming concepts, while low-level effects allow more fine-grained control over program execution and resources. Yet, often it is desirable to write programs using the convenient abstraction offered by high-level effects, and meanwhile still benefit from the optimisations enabled by low-level effects. One solution is to translate high-level effects to low-level ones. This paper studies how algebraic effects and handlers allow us to simulate high-level effects in terms of low-level effects. In particular, we focus on the interaction between state and nondeterminism known as the local state, as provided by Prolog. We map this high-level semantics in successive steps onto a low-level composite state effect, similar to that managed by Prolog's Warren Abstract Machine. We first give a translation from the high-level local-state semantics to the low-level global-state semantics, by explicitly restoring state updates on backtracking. Next, we eliminate nondeterminsm altogether in favor of a lower-level state containing a choicepoint stack. Then we avoid copying the state by restricting ourselves to incremental, reversible state updates. We show how these updates can be stored on a trail stack with another state effect. We prove the correctness of all our steps using program calculation where the fusion laws of effect handlers play a central role., Comment: 120 pages

This paper studies the design of cluster experiments to estimate the global treatment effect in the presence of network spillovers. We provide a framework to choose the clustering that minimizes the worst-case mean-squared error of the estimated global effect. We show that optimal clustering solves a novel penalized min-cut optimization problem computed via off-the-shelf semi-definite programming algorithms. Our analysis also characterizes simple conditions to choose between any two cluster designs, including choosing between a cluster or individual-level randomization. We illustrate the method's properties using unique network data from the universe of Facebook's users and existing data from a field experiment.

In online advertising markets, budget-constrained advertisers acquire ad placements through repeated bidding in auctions on various platforms. We present a strategy for bidding optimally in a set of auctions that may or may not be incentive-compatible under the presence of budget constraints. Our strategy maximizes the expected total utility across auctions while satisfying the advertiser's budget constraints in expectation. Additionally, we investigate the online setting where the advertiser must submit bids across platforms while learning about other bidders' bids over time. Our algorithm has $O(T^{3/4})$ regret under the full-information setting. Finally, we demonstrate that our algorithms have superior cumulative regret on both synthetic and real-world datasets of ad placement auctions, compared to existing adaptive pacing algorithms., Comment: 34 pages, 5 figures

Automatic differentiation (AD) is a range of algorithms to compute the numeric value of a function's (partial) derivative, where the function is typically given as a computer program or abstract syntax tree. AD has become immensely popular as part of many learning algorithms, notably for neural networks. This paper uses Prolog to systematically derive gradient-based forward- and reverse-mode AD variants from a simple executable specification: evaluation of the symbolic derivative. Along the way we demonstrate that several Prolog features (DCGs, co-routines) contribute to the succinct formulation of the algorithm. We also discuss two applications in probabilistic programming that are enabled by our Prolog algorithms. The first is parameter learning for the Sum-Product Loop Language and the second consists of both parameter learning and variational inference for probabilistic logic programming., Comment: accepted for publication in the issues of Theory and Practice of Logic Programming dedicated to ICLP 2023

Algebraic effects & handlers have become a standard approach for side-effects in functional programming. Their modular composition with other effects and clean separation of syntax and semantics make them attractive to a wide audience. However, not all effects can be classified as algebraic; some need a more sophisticated handling. In particular, effects that have or create a delimited scope need special care, as their continuation consists of two parts-in and out of the scope-and their modular composition introduces additional complexity. These effects are called scoped and have gained attention by their growing applicability and adoption in popular libraries. While calculi have been designed with algebraic effects & handlers built in to facilitate their use, a calculus that supports scoped effects & handlers in a similar manner does not yet exist. This work fills this gap: we present $\lambda_{\mathit{sc}}$, a calculus with native support for both algebraic and scoped effects & handlers. It addresses the need for polymorphic handlers and explicit clauses for forwarding unknown scoped operations to other handlers. Our calculus is based on Eff, an existing calculus for algebraic effects, extended with Koka-style row polymorphism, and consists of a formal grammar, operational semantics, a (type-safe) type-and-effect system and type inference. We demonstrate $\lambda_{\mathit{sc}}$ on a range of examples.

Algebraic effects & handlers are a modular approach for modeling side-effects in functional programming. Their syntax is defined in terms of a signature of effectful operations, encoded as a functor, that are plugged into the free monad; their denotational semantics is defined by fold-style handlers that only interpret their part of the syntax and forward the rest. However, not all effects are algebraic: some need to access an internal computation. For example, scoped effects distinguish between a computation in scope and out of scope; parallel effects parallellize over a computation, latent effects defer a computation. Separate definitions have been proposed for these higher-order effects and their corresponding handlers, often leading to expedient and complex monad definitions. In this work we propose a generic framework for higher-order effects, generalizing algebraic effects & handlers: a generic free monad with higher-order effect signatures and a corresponding interpreter. Specializing this higher-order syntax leads to various definitions of previously defined (scoped, parallel, latent) and novel (writer, bracketing) effects. Furthermore, we formally show our framework theoretically correct, also putting different effect instances on formal footing; a significant contribution for parallel, latent, writer and bracketing effects.

Automatic differentiation (AD) has been a topic of interest for researchers in many disciplines, with increased popularity since its application to machine learning and neural networks. Although many researchers appreciate and know how to apply AD, it remains a challenge to truly understand the underlying processes. From an algebraic point of view, however, AD appears surprisingly natural: it originates from the differentiation laws. In this work we use Algebra of Programming techniques to reason about different AD variants, leveraging Haskell to illustrate our observations. Our findings stem from three fundamental algebraic abstractions: (1) the notion of module over a semiring, (2) Nagata's construction of the 'idealization of a module', and (3) Kronecker's delta function, that together allow us to write a single-line abstract definition of AD. From this single-line definition, and by instantiating our algebraic structures in various ways, we derive different AD variants, that have the same extensional behaviour, but different intensional properties, mainly in terms of (asymptotic) computational complexity. We show the different variants equivalent by means of Kronecker isomorphisms, a further elaboration of our Haskell infrastructure which guarantees correctness by construction. With this framework in place, this paper seeks to make AD variants more comprehensible, taking an algebraic perspective on the matter.

GitHub hosts hundreds of millions of code repositories written in hundreds of different programming languages. In addition to its hosting services, GitHub provides data and insights into code, such as vulnerability analysis and code navigation, with which users can improve and understand their software development process. GitHub has built Semantic, a program analysis tool capable of parsing and extracting detailed information from source code. The development of Semantic has relied extensively on the functional programming literature; this paper describes how connections to academic research inspired and informed the development of an industrial-scale program analysis toolkit., Comment: 14 pages, 2 figures, submitted to ICFP 2022

In this data release from the LOFAR Two-metre Sky Survey (LoTSS) we present 120-168MHz images covering 27% of the northern sky. Our coverage is split into two regions centred at approximately 12h45m +44$^\circ$30' and 1h00m +28$^\circ$00' and spanning 4178 and 1457 square degrees respectively. The images were derived from 3,451hrs (7.6PB) of LOFAR High Band Antenna data which were corrected for the direction-independent instrumental properties as well as direction-dependent ionospheric distortions during extensive, but fully automated, data processing. A catalogue of 4,396,228 radio sources is derived from our total intensity (Stokes I) maps, where the majority of these have never been detected at radio wavelengths before. At 6" resolution, our full bandwidth Stokes I continuum maps with a central frequency of 144MHz have: a median rms sensitivity of 83$\mu$Jy/beam; a flux density scale accuracy of approximately 10%; an astrometric accuracy of 0.2"; and we estimate the point-source completeness to be 90% at a peak brightness of 0.8mJy/beam. By creating three 16MHz bandwidth images across the band we are able to measure the in-band spectral index of many sources, albeit with an error on the derived spectral index of +/-0.2 which is a consequence of our flux-density scale accuracy and small fractional bandwidth. Our circular polarisation (Stokes V) 20" resolution 120-168MHz continuum images have a median rms sensitivity of 95$\mu$Jy/beam, and we estimate a Stokes I to Stokes V leakage of 0.056%. Our linear polarisation (Stokes Q and Stokes U) image cubes consist of 480 x 97.6 kHz wide planes and have a median rms sensitivity per plane of 10.8mJy/beam at 4' and 2.2mJy/beam at 20"; we estimate the Stokes I to Stokes Q/U leakage to be approximately 0.2%. Here we characterise and publicly release our Stokes I, Q, U and V images in addition to the calibrated uv-data., Comment: 23 figures, 1 table and 29 pages. The catalogues, images and uv-data associated with this data release are publicly available via https://lofar-surveys.org/

Online ad platforms offer budget management tools for advertisers that aim to maximize the number of conversions given a budget constraint. As the volume of impressions, conversion rates and prices vary over time, these budget management systems learn a spend plan (to find the optimal distribution of budget over time) and run a pacing algorithm which follows the spend plan. This paper considers two models for impressions and competition that varies with time: a) an episodic model which exhibits stationarity in each episode, but each episode can be arbitrarily different from the next, and b) a model where the distributions of prices and values change slowly over time. We present the first learning theoretic guarantees on both the accuracy of spend plans and the resulting end-to-end budget management system. We present four main results: 1) for the episodic setting we give sample complexity bounds for the spend rate prediction problem: given $n$ samples from each episode, with high probability we have $|\widehat{\rho}_e - \rho_e| \leq \tilde{O}(\frac{1}{n^{1/3}})$ where $\rho_e$ is the optimal spend rate for the episode, $\widehat{\rho}_e$ is the estimate from our algorithm, 2) we extend the algorithm of Balseiro and Gur (2017) to operate on varying, approximate spend rates and show that the resulting combined system of optimal spend rate estimation and online pacing algorithm for episodic settings has regret that vanishes in number of historic samples $n$ and the number of rounds $T$, 3) for non-episodic but slowly-changing distributions we show that the same approach approximates the optimal bidding strategy up to a factor dependent on the rate-of-change of the distributions and 4) we provide experiments showing that our algorithm outperforms both static spend plans and non-pacing across a wide variety of settings.

Algebraic effects offer a versatile framework that covers a wide variety of effects. However, the family of operations that delimit scopes are not algebraic and are usually modelled as handlers, thus preventing them from being used freely in conjunction with algebraic operations. Although proposals for scoped operations exist, they are either ad-hoc and unprincipled, or too inconvenient for practical programming. This paper provides the best of both worlds: a theoretically-founded model of scoped effects that is convenient for implementation and reasoning. Our new model is based on an adjunction between a locally finitely presentable category and a category of functorial algebras. Using comparison functors between adjunctions, we show that our new model, an existing indexed model, and a third approach that simulates scoped operations in terms of algebraic ones have equal expressivity for handling scoped operations. We consider our new model to be the sweet spot between ease of implementation and structuredness. Additionally, our approach automatically induces fusion laws of handlers of scoped effects, which are useful for reasoning and optimisation., Comment: Extended version of the paper Structured Handling of Scoped Effects in ESOP 2022

The development of programming languages can be quite complicated and costly. Hence, much effort has been devoted to the modular definition of language features that can be reused in various combinations to define new languages and experiment with their semantics. A notable outcome of these efforts is the algebra-based "datatypes a la carte" (DTC) approach. When combined with algebraic effects, DTC can model a wide range of common language features. Unfortunately, the current state of the art does not cover modular definitions of advanced control-flow mechanisms that defer execution to an appropriate point, such as call-by-name and call-by-need evaluation, as well as (multi-)staging. This paper defines latent effects, a generic class of such control-flow mechanisms. We demonstrate how function abstractions, lazy computations and a MetaML-like staging can all be expressed in a modular fashion using latent effects, and how they can be combined in various ways to obtain complex semantics. We provide a full Haskell implementation of our effects and handlers with a range of examples., Comment: extended version of APLAS 2021 paper

Delimited control is a powerful mechanism for programming language extension which has been recently proposed for Prolog (and implemented in SWI-Prolog). By manipulating the control flow of a program from inside the language, it enables the implementation of powerful features, such as tabling, without modifying the internals of the Prolog engine. However, its current formulation is inadequate: it does not capture Prolog's unique non-deterministic nature which allows multiple ways to satisfy a goal. This paper fully embraces Prolog's non-determinism with a novel interface for disjunctive delimited control, which gives the programmer not only control over the sequential (conjunctive) control flow, but also over the non-deterministic control flow. We provide a meta-interpreter that conservatively extends Prolog with delimited control and show that it enables a range of typical Prolog features and extensions, now at the library level: findall, cut, branch-and-bound optimisation, probabilistic programming,..., Comment: Pre-proceedings paper presented at the 31st International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2021), Tallinn, Estonia, and Virtual, September 7-8, 2021 (arXiv:2107.10160). arXiv admin note: substantial text overlap with arXiv:2009.04909

We study the problem of an online advertising system that wants to optimally spend an advertiser's given budget for a campaign across multiple platforms, without knowing the value for showing an ad to the users on those platforms. We model this challenging practical application as a Stochastic Bandits with Knapsacks problem over $T$ rounds of bidding with the set of arms given by the set of distinct bidding $m$-tuples, where $m$ is the number of platforms. We modify the algorithm proposed in Badanidiyuru \emph{et al.,} to extend it to the case of multiple platforms to obtain an algorithm for both the discrete and continuous bid-spaces. Namely, for discrete bid spaces we give an algorithm with regret $O\left(OPT \sqrt {\frac{mn}{B} }+ \sqrt{mn OPT}\right)$, where $OPT$ is the performance of the optimal algorithm that knows the distributions. For continuous bid spaces the regret of our algorithm is $\tilde{O}\left(m^{1/3} \cdot \min\left\{ B^{2/3}, (m T)^{2/3} \right\} \right)$. When restricted to this special-case, this bound improves over Sankararaman and Slivkins in the regime $OPT \ll T$, as is the case in the particular application at hand. Second, we show an $ \Omega\left (\sqrt {m OPT} \right)$ lower bound for the discrete case and an $\Omega\left( m^{1/3} B^{2/3}\right)$ lower bound for the continuous setting, almost matching the upper bounds. Finally, we use a real-world data set from a large internet online advertising company with multiple ad platforms and show that our algorithms outperform common benchmarks and satisfy the required properties warranted in the real-world application.

This paper studies equilibrium quality of semi-separable position auctions (known as the Ad Types setting) with greedy or optimal allocation combined with generalized second-price (GSP) or Vickrey-Clarke-Groves (VCG) pricing. We make three contributions: first, we give upper and lower bounds on the Price of Anarchy (PoA) for auctions which use greedy allocation with GSP pricing, greedy allocations with VCG pricing, and optimal allocation with GSP pricing. Second, we give Bayes-Nash equilibrium characterizations for two-player, two-slot instances (for all auction formats) and show that there exists both a revenue hierarchy and revenue equivalence across some formats. Finally, we use no-regret learning algorithms and bidding data from a large online advertising platform and no-regret learning algorithms to evaluate the performance of the mechanisms under semi-realistic conditions. For welfare, we find that the optimal-to-realized welfare ratio (an empirical PoA analogue) is broadly better than our upper bounds on PoA; For revenue, we find that the hierarchy in practice may sometimes agree with simple theory, but generally appears sensitive to the underlying distribution of bidder valuations.

Resolution and subtyping are two common mechanisms in programming languages. Resolution is used by features such as type classes or Scala-style implicits to synthesize values automatically from contextual type information. Subtyping is commonly used to automatically convert the type of a value into another compatible type. So far the two mechanisms have been considered independently of each other. This paper shows that, with a small extension, subtyping with intersection types can subsume resolution. This has three main consequences. Firstly, resolution does not need to be implemented as a separate mechanism. Secondly, the interaction between resolution and subtyping becomes apparent. Finally, the integration of resolution into subtyping enables first-class (implicit) environments. The extension that recovers the power of resolution via subtyping is the modus ponens rule of propositional logic. While it is easily added to declarative subtyping, significant care needs to be taken to retain desirable properties, such as transitivity and decidability of algorithmic subtyping, and coherence. To materialize these ideas we develop $\lambda_i^{\mathsf{MP}}$, a calculus that extends a iprevious calculus with disjoint intersection types, and develop its metatheory in the Coq theorem prover., Comment: 43 pages, 20 figures; typos corrected, link to artifact added

Model learning (a.k.a. active automata learning) is a highly effective technique for obtaining black-box finite state models of software components. Thus far, generalisation to infinite state systems with inputs/outputs that carry data parameters has been challenging. Existing model learning tools for infinite state systems face scalability problems and can only be applied to restricted classes of systems (register automata with equality/inequality). In this article, we show how we can boost the performance of model learning techniques by extracting the constraints on input and output parameters from a run, and making this grey-box information available to the learner. More specifically, we provide new implementations of the tree oracle and equivalence oracle from RALib, which use the derived constraints. We extract the constraints from runs of Python programs using an existing tainting library for Python, and compare our grey-box version of RALib with the existing black-box version on several benchmarks, including some data structures from Python's standard library. Our proof-of-principle implementation results in almost two orders of magnitude improvement in terms of numbers of inputs sent to the software system. Our approach, which can be generalised to richer model classes, also enables RALib to learn models that are out of reach of black-box techniques, such as combination locks., Comment: To be published in iFM'2020 27 pages, 6 figures, 1 table

Delimited control is a powerful mechanism for programming language extension which has been recently proposed for Prolog (and implemented in SWI-Prolog). By manipulating the control flow of a program from inside the language, it enables the implementation of powerful features, such as tabling, without modifying the internals of the Prolog engine. However, its current formulation is inadequate: it does not capture Prolog's unique non-deterministic nature which allows multiple ways to satisfy a goal. This paper fully embraces Prolog's non-determinism with a novel interface for disjunctive delimited control, which gives the programmer not only control over the sequential (conjunctive) control flow, but also over the non-deterministic control flow. We provide a meta-interpreter that conservatively extends Prolog with delimited control and show that it enables a range of typical Prolog features and extensions, now at the library level: findall, cut, branch-and-bound optimisation, probabilistic programming, . . . This paper is under consideration for publication in Theory and Practice of Logic Programming (TPLP)., Comment: Other version of paper is available at: arXiv:2108.02972. This paper is under consideration for publication in Theory and Practice of Logic Programming (TPLP)

Shopping behaviour analysis through counting and tracking of people in shop-like environments offers valuable information for store operators and provides key insights in the stores layout (e.g. frequently visited spots). Instead of using extra staff for this, automated on-premise solutions are preferred. These automated systems should be cost-effective, preferably on lightweight embedded hardware, work in very challenging situations (e.g. handling occlusions) and preferably work real-time. We solve this challenge by implementing a real-time TensorRT optimized YOLOv3-based pedestrian detector, on a Jetson TX2 hardware platform. By combining the detector with a sparse optical flow tracker we assign a unique ID to each customer and tackle the problem of loosing partially occluded customers. Our detector-tracker based solution achieves an average precision of 81.59% at a processing speed of 10 FPS. Besides valuable statistics, heat maps of frequently visited spots are extracted and used as an overlay on the video stream.

As popularity of algebraic effects and handlers increases, so does a demand for their efficient execution. Eff, an ML-like language with native support for handlers, has a subtyping-based effect system on which an effect-aware optimizing compiler could be built. Unfortunately, in our experience, implementing optimizations for Eff is overly error-prone because its core language is implicitly-typed, making code transformations very fragile. To remedy this, we present an explicitly-typed polymorphic core calculus for algebraic effect handlers with a subtyping-based type-and-effect system. It reifies appeals to subtyping in explicit casts with coercions that witness the subtyping proof, quickly exposing typing bugs in program transformations. Our typing-directed elaboration comes with a constraint-based inference algorithm that turns an implicitly-typed Eff-like language into our calculus. Moreover, all coercions and effect information can be erased in a straightforward way, demonstrating that coercions have no computational content. Additionally, we present a monadic translation from our calculus into a pure language without algebraic effects or handlers, using the effect information to introduce monadic constructs only where necessary., Comment: 57 pages, 29 figures

SURF is the collaborative ICT organisation for Dutch education & research and coordinates the national e-infrastructure (surf.nl). To accelerate scientific discovery, SURF invests in, operates and explores high-end IT solutions for and with researchers in the Netherlands. In this ADASS 2019 contribution we present our latest developments in high performance and high throughput cloud computing. These developments are particularly relevant for Astronomy, as this science domain: (i) generates large (Petabyte sized) data collections, (ii) uses rapid release and deployment schemes for their software, (iii) requires flexible and interactive test and staging environments and (iv) needs to execute complex workflows on diverse data structures. We highlight our new OpenStack-based, cloud infrastructure layer and focus on Spider, our new addition to SURF's high throughput data processing platforms., Comment: 4 pages, conference, ADASS 2019

This paper presents PaSe, an extensible and inspectable DSL embedded in Haskell for expressing micro-animations. The philosophy of PaSe is to compose animations based on sequential and parallel composition of smaller animations. This differs from other animation libraries that focus more on sequential composition and have only limited forms of parallel composition. To provide similar flexibility as other animation libraries, PaSe features extensibility of operations and inspectability of animations. We present the features of PaSe with a to-do list application, discuss the PaSe implementation, and argue that the callback style of extensibility is detrimental for correctly combining PaSe features. We contrast with the GreenSock Animation Platform, a professional-grade and widely used JavaScript animation library, to illustrate this point.

The new generation of high-resolution broad-band radio telescopes, like the Low Frequency Array (LOFAR), produces, depending on the level of compression, between 1 to 10 TB of data per hour after correlation. Such a large amount of scientific data demand powerful computing resources and efficient data handling strategies to be mastered. The LOFAR Two-metre Sky Survey (LoTSS) is a Key Science Project (KSP) of the LOFAR telescope. It aims to map the entire northern hemisphere at unprecedented sensitivity and resolution. The survey consist of 3 168 pointings, requiring about 30 PBytes of storage space. As a member of the German Long Wavelength Consortioum (GLOW) the Forschungszentrum J\"ulich (FSZ) stores in the Long Term Archive (LTA) about 50% of all LoTSS observations conducted to date. In collaboration with SURFsara in Amsterdam we developed service tools that enable the KSP to process LOFAR data stored in the J\"ulich LTA at the supercomputer JUWELS in an automated and robust fashion. Through our system more than 500 out of 800 existing LoTSS observations have already been processed with the prefactor pipeline. This pipeline calibrates the direction-independent instrumental and ionospheric effects and furthermore reduces the data size significantly. For continuum imaging, this processing pipeline is the standard pipeline that is executed before more advanced processing and image reconstruction methods are applied., Comment: 10 pages, 6 figures, NIC Symposium 2020, accepted

In recent years, stream processing has become a prominent approach for incrementally handling large amounts of data, with special support and libraries in many programming languages. Unfortunately, support in Prolog has so far been lacking and most existing approaches are ad-hoc. To remedy this situation, we present lazy stream generators as a unified Prolog interface for stateful computations on both finite and infinite sequences of data that are produced incrementally through I/O and/or algorithmically. We expose stream generators to the application programmer in two ways: 1) through an abstract sequence manipulation API, convenient for defining custom generators, and 2) as idiomatic lazy lists, compatible with many existing list predicates. We define an algebra of stream generator operations that extends Prolog via an embedded language interpreter, provides a compact notation for composing generators and supports moving between the two isomorphic representations. As a special instance, we introduce answer stream generators that encapsulate the work of coroutining first-class logic engines and support interoperation between forward recursive AND-streams and backtracking-generated OR-streams. Keywords: lazy stream generators, lazy lists, first-class logic engines, stream combinators, AND-stream / OR-stream interoperation, Prolog extensions, Comment: In Proceedings ICLP 2019, arXiv:1909.07646

Incentive compatibility (IC) is one of the most fundamental properties of an auction mechanism, including those used for online advertising. Recent methods by Feng et al. and Lahaie et al. show that counterfactual runs of the auction mechanism with different bids can be used to determine whether an auction is IC. In this paper we show that a similar result can be obtained by looking at the advertisers' envy, which can be computed with one single execution of the auction. We introduce two metrics to evaluate the incentive-compatibility of an auction: IC-Regret and IC-Envy. For position auction environments, we show that for a large class of pricing schemes (which includes e.g. VCG and GSP), IC-Envy $\ge$ IC-Regret (and IC-Envy = IC-Regret when bids are distinct). We consider non-separable discounts in the Ad Types environment of Colini-Baldeschi et al. where we show that for a generalization of GSP also IC-Envy $\ge$ IC-Regret. Our final theoretical result is that in all these settings IC-Envy be used to bound the loss in social welfare due advertiser misreports. Finally, we show that IC-Envy is useful as a feature to predict IC-Regret in auction environments beyond the ones for which we show theoretical results. In particular, using IC-Envy yields better results than training models using only price and value features.

The Ad Types Problem (without gap rules) is a special case of the assignment problem in which there are $k$ types of nodes on one side (the ads), and an ordered set of nodes on the other side (the slots). The edge weight of an ad $i$ of type $\theta$ to slot $j$ is $v_i\cdot \alpha^{\theta}_j$ where $v_i$ is an advertiser-specific value and each ad type $\theta$ has a discount curve $\alpha^{(\theta)}_{1} \ge \alpha^{(\theta)}_{2} \ge ... \ge 0$ over the slots that is common for ads of type $\theta$. We present two contributions for this problem: 1) we give an algorithm that finds the maximum weight matching that runs in $O(n^2(k + \log n))$ time for $n$ slots and $n$ ads of each type---cf. $O(kn^3)$ when using the Hungarian algorithm---, and 2) we show to do VCG pricing in asymptotically the same time, namely $O(n^2(k + \log n))$, and apply reserve prices in $O(n^3(k + \log n))$. The Ad Types Problem (with gap rules) includes a matrix $G$ such that after we show an ad of type $\theta_i$, the next $G_{ij}$ slots cannot show an ad of type $\theta_j$. We show that the problem is hard to approximate within $k^{1- \epsilon}$ for any $\epsilon > 0$ (even without discount curves) by reduction from Maximum Independent Set. On the positive side, we show a Dynamic Program formulation that solves the problem (including discount curves) optimally and runs in $O(k\cdot n^{2k + 1})$ time.

Elaboration-based type class resolution, as found in languages like Haskell, Mercury and PureScript, is generally nondeterministic: there can be multiple ways to satisfy a wanted constraint in terms of global instances and locally given constraints. Coherence is the key property that keeps this sane; it guarantees that, despite the nondeterminism, programs still behave predictably. Even though elaboration-based resolution is generally assumed coherent, as far as we know, there is no formal proof of this property in the presence of sources of nondeterminism, like superclasses and flexible contexts. This paper provides a formal proof to remedy the situation. The proof is non-trivial because the semantics elaborates resolution into a target language where different elaborations can be distinguished by contexts that do not have a source language counterpart. Inspired by the notion of full abstraction, we present a two-step strategy that first elaborates nondeterministically into an intermediate language that preserves contextual equivalence, and then deterministically elaborates from there into the target language. We use an approach based on logical relations to establish contextual equivalence and thus coherence for the first step of elaboration, while the second step's determinism straightforwardly preserves this coherence property., Comment: Accepted to ICFP 2019

GADTs were introduced in Haskell's eco-system more than a decade ago, but their interaction with several mainstream features such as type classes and functional dependencies has a lot of room for improvement. More specifically, for some GADTs it can be surprisingly difficult to provide an instance for even the simplest of type classes. In this paper we identify the source of this shortcoming and address it by introducing a conservative extension to Haskell's type classes: Bidirectional Type Class Instances. In essence, under our interpretation class instances correspond to logical bi-implications, in contrast to their traditional unidirectional interpretation. We present a fully-fledged design of bidirectional instances, covering the specification of typing and elaboration into System FC, as well as an algorithm for type inference and elaboration. We provide a proof-of-concept implementation of our algorithm, and revisit the meta-theory of type classes in the presence of our extension.

In this paper we investigate the problem of measuring end-to-end Incentive Compatibility (IC) regret given black-box access to an auction mechanism. Our goal is to 1) compute an estimate for IC regret in an auction, 2) provide a measure of certainty around the estimate of IC regret, and 3) minimize the time it takes to arrive at an accurate estimate. We consider two main problems, with different informational assumptions: In the \emph{advertiser problem} the goal is to measure IC regret for some known valuation $v$, while in the more general \emph{demand-side platform (DSP) problem} we wish to determine the worst-case IC regret over all possible valuations. The problems are naturally phrased in an online learning model and we design $Regret-UCB$ algorithms for both problems. We give an online learning algorithm where for the advertiser problem the error of determining IC shrinks as $O\Big(\frac{|B|}{T}\cdot\Big(\frac{\ln T}{n} + \sqrt{\frac{\ln T}{n}}\Big)\Big)$ (where $B$ is the finite set of bids, $T$ is the number of time steps, and $n$ is number of auctions per time step), and for the DSP problem it shrinks as $O\Big(\frac{|B|}{T}\cdot\Big( \frac{|B|\ln T}{n} + \sqrt{\frac{|B|\ln T}{n}}\Big)\Big)$. For the DSP problem, we also consider stronger IC regret estimation and extend our $Regret-UCB$ algorithm to achieve better IC regret error. We validate the theoretical results using simulations with Generalized Second Price (GSP) auctions, which are known to not be incentive compatible and thus have strictly positive IC regret., Comment: In the Proceedings of the Web Conference 2019 (former WWW'19)

The LOFAR Two-metre Sky Survey (LoTSS) is an ongoing sensitive, high-resolution 120-168MHz survey of the entire northern sky for which observations are now 20% complete. We present our first full-quality public data release. For this data release 424 square degrees, or 2% of the eventual coverage, in the region of the HETDEX Spring Field (right ascension 10h45m00s to 15h30m00s and declination 45$^\circ$00$'$00$''$ to 57$^\circ$00$'$00$''$) were mapped using a fully automated direction-dependent calibration and imaging pipeline that we developed. A total of 325,694 sources are detected with a signal of at least five times the noise, and the source density is a factor of $\sim 10$ higher than the most sensitive existing very wide-area radio-continuum surveys. The median sensitivity is S$_{\rm 144 MHz} = 71\,\mu$Jy beam$^{-1}$ and the point-source completeness is 90% at an integrated flux density of 0.45mJy. The resolution of the images is 6$''$ and the positional accuracy is within 0.2$''$. This data release consists of a catalogue containing location, flux, and shape estimates together with 58 mosaic images that cover the catalogued area. In this paper we provide an overview of the data release with a focus on the processing of the LOFAR data and the characteristics of the resulting images. In two accompanying papers we provide the radio source associations and deblending and, where possible, the optical identifications of the radio sources together with the photometric redshifts and properties of the host galaxies. These data release papers are published together with a further $\sim$20 articles that highlight the scientific potential of LoTSS., Comment: 16 figures, 1 table and 22 pages. This paper is part of the LOFAR surveys data release 1 and has been accepted for publication in a special edition of A&A that will appear in Feb 2019, volume 622. The catalogues and images from the data release will be publicly available on lofar-surveys.org upon publication of the journal

Mature internet advertising platforms offer high-level campaign management tools to help advertisers run their campaigns, often abstracting away the intricacies of how each ad is placed and focusing on aggregate metrics of interest to advertisers. On such platforms, advertisers often participate in auctions through a proxy bidder, so the standard incentive analyses that are common in the literature do not apply directly. In this paper, we take the perspective of a budget management system that surfaces aggregated incentives -- instead of individual auctions -- and compare first and second price auctions. We show that theory offers surprising endorsement for using a first price auction to sell individual impressions. In particular, first price auctions guarantee uniqueness of the steady-state equilibrium of the budget management system, monotonicity, and other desirable properties, as well as efficient computation through the solution to the well-studied Eisenberg-Gale convex program. Contrary to what one can expect from first price auctions, we show that incentives issues are not a barrier that undermines the system. Using realistic instances generated from data collected at real-world auction platforms, we show that bidders have small regret with respect to their optimal ex-post strategy, and they do not have a big incentive to misreport when they can influence equilibria directly by giving inputs strategically. Finally, budget-constrained bidders, who have significant prevalence in real-world platforms, tend to have smaller regrets. Our computations indicate that bidder budgets, pacing multipliers and regrets all have a positive association in statistical terms.

The Low Frequency Array (LOFAR) radio telescope is an international aperture synthesis radio telescope used to study the Universe at low frequencies. One of the goals of the LOFAR telescope is to conduct deep wide-field surveys. Here we will discuss a framework for the processing of the LOFAR Two Meter Sky Survey (LoTSS). This survey will produce close to 50 PB of data within five years. These data rates require processing at locations with high-speed access to the archived data. To complete the LoTSS project, the processing software needs to be made portable and moved to clusters with a high bandwidth connection to the data archive. This work presents a framework that makes the LOFAR software portable, and is used to scale out LOFAR data reduction. Previous work was successful in preprocessing LOFAR data on a cluster of isolated nodes. This framework builds upon it and and is currently operational. It is designed to be portable, scalable, automated and general. This paper describes its design and high level operation and the initial results processing LoTSS data., Comment: Accepted Proceedings for International Symposium on Grids & Clouds 2017. 16 Pages, 7 Figures

We consider the problem of binary prediction with expert advice in settings where experts have agency and seek to maximize their credibility. This paper makes three main contributions. First, it defines a model to reason formally about settings with selfish experts, and demonstrates that "incentive compatible" (IC) algorithms are closely related to the design of proper scoring rules. Designing a good IC algorithm is easy if the designer's loss function is quadratic, but for other loss functions, novel techniques are required. Second, we design IC algorithms with good performance guarantees for the absolute loss function. Third, we give a formal separation between the power of online prediction with selfish experts and online prediction with honest experts by proving lower bounds for both IC and non-IC algorithms. In particular, with selfish experts and the absolute loss function, there is no (randomized) algorithm for online prediction-IC or otherwise-with asymptotically vanishing regret.

Recent work has provided delimited control for Prolog to dynamically manipulate the program control-flow, and to implement a wide range of control-flow and dataflow effects on top of. Unfortunately, delimited control is a rather primitive language feature that is not easy to use. As a remedy, this work introduces algebraic effect handlers for Prolog, as a high-level and structured way of defining new side-effects in a modular fashion. We illustrate the expressive power of the feature and provide an implementation by means of elaboration into the delimited control primitives. The latter add a non-negligible performance overhead when used extensively. To address this issue, we present an optimised compilation approach that combines partial evaluation with dedicated rewrite rules. The rewrite rules are driven by a lightweight effect inference that analyses what effect operations may be called by a goal. We illustrate the effectiveness of this approach on a range of benchmarks. This article is under consideration for acceptance in TPLP., Comment: Paper presented at the 32nd International Conference on Logic Programming (ICLP 2016), New York City, USA, 16-21 October 2016, LaTex, 14 pages, 2 figures

Tabling is a powerful resolution mechanism for logic programs that captures their least fixed point semantics more faithfully than plain Prolog. In many tabling applications, we are not interested in the set of all answers to a goal, but only require an aggregation of those answers. Several works have studied efficient techniques, such as lattice-based answer subsumption and mode-directed tabling, to do so for various forms of aggregation. While much attention has been paid to expressivity and efficient implementation of the different approaches, soundness has not been considered. This paper shows that the different implementations indeed fail to produce least fixed points for some programs. As a remedy, we provide a formal framework that generalises the existing approaches and we establish a soundness criterion that explains for which programs the approach is sound. This article is under consideration for acceptance in TPLP., Comment: Paper presented at the 32nd International Conference on Logic Programming (ICLP 2016), New York City, USA, 16-21 October 2016, 15 pages, LaTeX, 0 PDF figures

Resolution lies at the foundation of both logic programming and type class context reduction in functional languages. Terminating derivations by resolution have well-defined inductive meaning, whereas some non-terminating derivations can be understood coinductively. Cycle detection is a popular method to capture a small subset of such derivations. We show that in fact cycle detection is a restricted form of coinductive proof, in which the atomic formula forming the cycle plays the role of coinductive hypothesis. This paper introduces a heuristic method for obtaining richer coinductive hypotheses in the form of Horn formulas. Our approach subsumes cycle detection and gives coinductive meaning to a larger class of derivations. For this purpose we extend resolution with Horn formula resolvents and corecursive evidence generation. We illustrate our method on non-terminating type class resolution problems., Comment: 23 pages, with appendices in FLOPS 2016

This paper presents the first polynomial-time algorithm for position and matroid auction environments that learns, from samples from an unknown bounded valuation distribution, an auction with expected revenue arbitrarily close to the maximum possible. In contrast to most previous work, our results apply to arbitrary (not necessarily regular) distributions and the strongest possible benchmark, the Myerson-optimal auction. Learning a near-optimal auction for an irregular distribution is technically challenging because it requires learning the appropriate "ironed intervals," a delicate global property of the distribution.

In functional programming, datatypes a la carte provide a convenient modular representation of recursive datatypes, based on their initial algebra semantics. Unfortunately it is highly challenging to implement this technique in proof assistants that are based on type theory, like Coq. The reason is that it involves type definitions, such as those of type-level fixpoint operators, that are not strictly positive. The known work-around of impredicative encodings is problematic, insofar as it impedes conventional inductive reasoning. Weak induction principles can be used instead, but they considerably complicate proofs. This paper proposes a novel and simpler technique to reason inductively about impredicative encodings, based on Mendler-style induction. This technique involves dispensing with dependent induction, ensuring that datatypes can be lifted to predicates and relying on relational formulations. A case study on proving subject reduction for structural operational semantics illustrates that the approach enables modular proofs, and that these proofs are essentially similar to conventional ones., Comment: In Proceedings FICS 2015, arXiv:1509.02826

Tabling is probably the most widely studied extension of Prolog. But despite its importance and practicality, tabling is not implemented by most Prolog systems. Existing approaches require substantial changes to the Prolog engine, which is an investment out of reach of most systems. To enable more widespread adoption, we present a new implementation of tabling in under 600 lines of Prolog code. Our lightweight approach relies on delimited control and provides reasonable performance., Comment: 15 pages. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015

We have conducted two pilot surveys for radio pulsars and fast transients with the Low-Frequency Array (LOFAR) around 140 MHz and here report on the first low-frequency fast-radio burst limit and the discovery of two new pulsars. The first survey, the LOFAR Pilot Pulsar Survey (LPPS), observed a large fraction of the northern sky, ~1.4 x 10^4 sq. deg, with 1-hr dwell times. Each observation covered ~75 sq. deg using 7 independent fields formed by incoherently summing the high-band antenna fields. The second pilot survey, the LOFAR Tied-Array Survey (LOTAS), spanned ~600 sq. deg, with roughly a 5-fold increase in sensitivity compared with LPPS. Using a coherent sum of the 6 LOFAR "Superterp" stations, we formed 19 tied-array beams, together covering 4 sq. deg per pointing. From LPPS we derive a limit on the occurrence, at 142 MHz, of dispersed radio bursts of < 150 /day/sky, for bursts brighter than S > 107 Jy for the narrowest searched burst duration of 0.66 ms. In LPPS, we re-detected 65 previously known pulsars. LOTAS discovered two pulsars, the first with LOFAR or any digital aperture array. LOTAS also re-detected 27 previously known pulsars. These pilot studies show that LOFAR can efficiently carry out all-sky surveys for pulsars and fast transients, and they set the stage for further surveying efforts using LOFAR and the planned low-frequency component of the Square Kilometer Array., Comment: 18 pages, 10 figures, accepted for A&A

LP is a common formalism for the field of databases and CSP, both at the theoretical level and the implementation level in the form of Datalog and CLP. In the past, close correspondences have been made between both fields at the theoretical level. Yet correspondence at the implementation level has been much less explored. In this article we work towards relating them at the implementation level. Concretely, we show how to derive the efficient Leapfrog Triejoin execution algorithm of Datalog from a generic CP execution scheme., Comment: Proceedings of the 13th International Colloquium on Implementation of Constraint LOgic Programming Systems (CICLOPS 2013), Istanbul, Turkey, August 25, 2013

Generic programming (GP) is an increasingly important trend in programming languages. Well-known GP mechanisms, such as type classes and the C++0x concepts proposal, usually combine two features: 1) a special type of interfaces; and 2) implicit instantiation of implementations of those interfaces. Scala implicits are a GP language mechanism, inspired by type classes, that break with the tradition of coupling implicit instantiation with a special type of interface. Instead, implicits provide only implicit instantiation, which is generalized to work for any types. This turns out to be quite powerful and useful to address many limitations that show up in other GP mechanisms. This paper synthesizes the key ideas of implicits formally in a minimal and general core calculus called the implicit calculus, and it shows how to build source languages supporting implicit instantiation on top of it. A novelty of the calculus is its support for partial resolution and higher-order rules (a feature that has been proposed before, but was never formalized or implemented). Ultimately, the implicit calculus provides a formal model of implicits, which can be used by language designers to study and inform implementations of similar mechanisms in their own languages., Comment: 13 pages, extended report of paper accepted at PLDI 2012

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.

We present a technique exploiting Datalog with aggregates to improve the performance of programs with arithmetic (in)equalities. Our approach employs a source-to-source program transformation which approximates the propagation technique from Constraint Programming. The experimental evaluation of the approach shows good run time speed-ups on a range of non-recursive as well as recursive programs. Furthermore, our technique improves upon the previously reported in the literature constraint magic set transformation approach., Comment: Online Proceedings of the 11th International Colloquium on Implementation of Constraint LOgic Programming Systems (CICLOPS 2011), Lexington, KY, U.S.A., July 10, 2011

SWI-Prolog is neither a commercial Prolog system nor a purely academic enterprise, but increasingly a community project. The core system has been shaped to its current form while being used as a tool for building research prototypes, primarily for \textit{knowledge-intensive} and \textit{interactive} systems. Community contributions have added several interfaces and the constraint (CLP) libraries. Commercial involvement has created the initial garbage collector, added several interfaces and two development tools: PlDoc (a literate programming documentation system) and PlUnit (a unit testing environment). In this article we present SWI-Prolog as an integrating tool, supporting a wide range of ideas developed in the Prolog community and acting as glue between \textit{foreign} resources. This article itself is the glue between technical articles on SWI-Prolog, providing context and experience in applying them over a longer period., Comment: 30 pages, 6 figures, 1 table. To appear in Theory and Practice of Logic Programming (TPLP)

Constraint Handling Rules (CHR) is a high-level programming language based on multi-headed multiset rewrite rules. Originally designed for writing user-defined constraint solvers, it is now recognized as an elegant general purpose language. CHR-related research has surged during the decade following the previous survey by Fruehwirth. Covering more than 180 publications, this new survey provides an overview of recent results in a wide range of research areas, from semantics and analysis to systems, extensions and applications., Comment: 49 pages. To appear in Theory and Practice of Logic Programming

Tabled Constraint Logic Programming is a powerful execution mechanism for dealing with Constraint Logic Programming without worrying about fixpoint computation. Various applications, e.g in the fields of program analysis and model checking, have been proposed. Unfortunately, a high-level system for developing new applications is lacking, and programmers are forced to resort to complicated ad hoc solutions. This papers presents TCHR, a high-level framework for tabled Constraint Logic Programming. It integrates in a light-weight manner Constraint Handling Rules (CHR), a high-level language for constraint solvers, with tabled Logic Programming. The framework is easily instantiated with new application-specific constraint domains. Various high-level operations can be instantiated to control performance. In particular, we propose a novel, generalized technique for compacting answer sets., Comment: Accepted for publication in Theory and Practice of Logic Programming