Practical Aspects of Declarative Languages

On top of a neural network-based dependency parser and a graph-based natural language processing module we design a Prolog-based dialog engine that explores interactively a ranked fact database extracted from a text document.

We reorganize dependency graphs to focus on the most relevant content elements of a sentence, integrate sentence identifiers as graph nodes and after ranking the graph we take advantage of the implicit semantic information that dependency links bring in the form of subject-verb-object, “is-a” and “part-of” relations.

Working on the Prolog facts and their inferred consequences, the dialog engine specializes the text graph with respect to a query and reveals interactively the document’s most relevant content elements.

The open-source code of the integrated system is available at https://​github.​com/​ptarau/​DeepRank.

The graph isomorphism, subgraph isomorphism, and graph edit distance problems are combinatorial problems with many applications. Heuristic exact and approximate algorithms for each of these problems have been developed for different kinds of graphs: directed, undirected, labeled, etc. However, additional work is often needed to adapt such algorithms to different classes of graphs, for example to accommodate both labels and property annotations on nodes and edges. In this paper, we propose an approach based on answer set programming. We show how each of these problems can be defined for a general class of property graphs with directed edges, and labels and key-value properties annotating both nodes and edges. We evaluate this approach on a variety of synthetic and realistic graphs, demonstrating that it is feasible as a rapid prototyping approach.

When a composite web service—i.e., a composition of individual web services—is executed and fails, it is desirable to reuse as much as possible the results that have been obtained thus far. For example, a travel agent, after receiving an order to arrange for a trip from LA to NY from a customer, would typically identify the flights and the hotels, obtain the confirmation from the customer, and place the reservations using the credit card information provided by the user; if something is wrong (e.g., at the last step, the credit card information was wrong), the travel agent would prefer to place the reservations using another means (e.g., a different card) instead of starting from the beginning.

This paper introduces an approach for dealing with service failures in the context of workflow execution. The paper defines the notion of a web service composition (WSC) problem and the notion of a solution workflow for a WSC problem. The paper describes two approaches to repair a partially executed workflow, with the goal of effectively reusing parts of the workflow that have been successfully executed. The usefulness of these approaches are demonstrated in an implementation using Answer Set Programming (ASP) in the well-known shopping domain.

AQuA (ASP-based Question Answering) is an Answer Set Programming (ASP) based visual question answering framework that truly “understands” an input picture and answers natural language questions about that picture. The knowledge contained in the picture is extracted using YOLO, a neural network-based object detection technique, and represented as an answer set program. Natural language processing is performed on the question to transform it into an ASP query. Semantic relations are extracted in the process for deeper understanding and to answer more complex questions. The resulting knowledge-base—with additional commonsense knowledge imported—can be used to perform reasoning using an ASP system, allowing it to answer questions about the picture, just like a human. This framework achieves 93.7% accuracy on CLEVR dataset, which exceeds human baseline performance. What is significant is that AQuA translates a question into an ASP query without requiring any training. Our framework for Visual Question Answering is quite general and closely simulates the way humans operate. In contrast to existing purely machine learning-based methods, our framework provides an explanation for the answer it computes, while maintaining high accuracy.

In this paper we describe our work towards automating diagnosing failures of data processing pipelines at Google Inc. using action language Hybrid \(\mathcal {ALE}\). We describe Diagnostic Modeling Library - a component providing a novel abstraction layer on top of Hybrid \(\mathcal {ALE}\), describe the requirements and give an overview of our system, which has been deployed on a limited number of data processing pipelines.

Answer Set Programming (ASP) is a dominant programming paradigm in Knowledge Representation. It is used to build intelligent agents – knowledge-intensive software systems capable of exhibiting intelligent behaviors. It is found that ASP can also be used to teach computer science in middle and high schools. However, the current ASP systems do not provide direct support for a programmer to produce an intelligent agent that a general user can directly interact with, which may greatly compromise the potential attraction of ASP to the secondary school students. In this paper, we propose a Virtual Reality (VR) programming environment called VRASP that allows a student to produce an avatar (agent) in a virtual world that is able to answer questions in spoken natural language from a general user. The VR application is accessible from anywhere so that the students’ friends can interact with the agent. As a result, it gives the students a feeling of achievement and thus encourages them to solve problems using ASP. VRASP was evaluated with 10 users. Results of these studies show that students are able to communicate with the environment intuitively with an accuracy of 78%.

We present a region-based memory management scheme with support for generational garbage collection. The scheme is implemented in the MLKit Standard ML compiler, which features a compile-time region inference algorithm. The compiler generates native x64 machine code and deploys region types at runtime to avoid write barrier problems and to support partly tag-free garbage collection. We measure the characteristics of the scheme, for a number of benchmarks, and compare it to the Mlton state-of-the-art Standard ML compiler and configurations of the MLKit with and without region inference and generational garbage collection enabled. Although region inference often serves the purpose of generations, we demonstrate that, in some cases, generational garbage collection combined with region inference is beneficial.

There is a growing interest in leveraging functional programming languages in real-time and embedded contexts. Functional languages are appealing as many are strictly typed, amenable to formal methods, have limited mutation, and have simple, but powerful concurrency control mechanisms. Although there have been many recent proposals for specialized domain specific languages for embedded and real-time systems, there has been relatively little progress on adapting more general purpose functional languages for programming embedded and real-time systems. In this paper we present our current work on leveraging Standard ML in the embedded and real-time domains. Specifically we detail our experiences in modifying MLton, a whole program, optimizing compiler for Standard ML, for use in such contexts. We focus primarily on the language runtime, re-working the threading subsystem and garbage collector. We provide preliminary results over a radar-based aircraft collision detector ported to SML.

Programming with explicit timing information is often tedious and error prone. This is especially visible in music programming where, when played, the specified durations of notes and rests must be shortened in order to compensate the actual duration of all surrounding processing. In this paper, we develop the notion of timed extension of a monad that aims at relieving programmers from such a burden. We show how, under simple conditions, such extensions can be built, and how useful features of monad programming such as asynchronous concurrency with promises or data-flow programming with monadic streams can be uniformly lifted to the resulting timed programming framework. Even though presented and developed in the abstract, the notion of timed extension of a monad is nevertheless illustrated by two concrete instances: a default timed IO monad where programmers specify durations in microseconds, and a musically timed IO monad, where programmers specify durations in number of beats, the underlying tempo, that is, the speed of the music in beats per minute, possibly changed whenever needed.

Bounded treewidth is one of the most cited combinatorial invariants, which was applied in the literature for solving several counting problems efficiently. A canonical counting problem is #Sat, which asks to count the satisfying assignments of a Boolean formula. Recent work shows that benchmarking instances for #Sat often have reasonably small treewidth. This paper deals with counting problems for instances of small treewidth. We introduce a general framework to solve counting questions based on state-of-the-art database management systems (DBMS). Our framework takes explicitly advantage of small treewidth by solving instances using dynamic programming (DP) on tree decompositions (TD). Therefore, we implement the concept of DP into a DBMS (PostgreSQL), since DP algorithms are already often given in terms of table manipulations in theory. This allows for elegant specifications of DP algorithms and the use of SQL to manipulate records and tables, which gives us a natural approach to bring DP algorithms into practice. To the best of our knowledge, we present the first approach to employ a DBMS for algorithms on TDs. A key advantage of our approach is that DBMS naturally allow to deal with huge tables with a limited amount of main memory (RAM), parallelization, as well as suspending computation.

We present a fast and scalable algorithm to induce non-monotonic logic programs from statistical learning models. We reduce the problem of search for best clauses to instances of the High-Utility Itemset Mining (HUIM) problem. In the HUIM problem, feature values and their importance are treated as transactions and utilities respectively. We make use of TreeExplainer, a fast and scalable implementation of the Explainable AI tool SHAP, to extract locally important features and their weights from ensemble tree models. Our experiments with UCI standard benchmarks suggest a significant improvement in terms of classification evaluation metrics and training time compared to ALEPH, a state-of-the-art Inductive Logic Programming (ILP) system.

We present an approach for explaining dynamic programming that is based on computing with a granular representation of values that are typically aggregated during program execution. We demonstrate how to derive more detailed and meaningful explanations of program behavior from such a representation than would otherwise be possible. To illustrate the practicality of this approach we also present a Haskell library for dynamic programming that allows programmers to specify programs by recurrence relationships from which implementations are derived that can run with granular representation and produce explanations. The explanations essentially answer questions of why one result was obtained instead of another. While usually the alternatives have to be provided by a user, we will show that with our approach such alternatives can be in some cases anticipated and that corresponding explanations can be generated automatically.

Expressing linear integer constraints and assertions over integer ranges—as becomes necessary when reasoning about arrays—in a legible and succinct form poses a challenge for deductive program verification. Even simple assertions, such as integer predicates quantified over finite ranges, become quite verbose when given in basic first-order logic syntax. In this paper, we propose a domain-specific language (DSL) for assertions over integer ranges based on Reynolds’s interval and partition diagrams, two diagrammatic notations designed to integrate well into linear textual content such as specifications, program annotations, and proofs. We extend intervalf diagrams to the more general concept of mapping diagrams, representing partial functions from disjoint integer intervals. A subset of mapping diagrams, colorings, provide a compact notation for selecting integer intervals that we intend to constrain, and an intuitive new construct, the legend, allows connecting colorings to first-order integer predicates. Reynolds’s diagrams have not been supported widely by verification tools. We implement the syntax and semantics of partition and mapping diagrams as a DSL and theory extension to the Why3 program verifier. We illustrate the approach with examples of verified programs specified with colorings and legends. This work aims to extend the verification toolbox with a lightweight, intuitive DSL for array and integer range specifications.

Variability-aware computing is the efficient application of programs to different sets of inputs that exhibit some variability. One example is program analyses applied to Software Product Lines (SPLs). In this paper we present the design and development of a variability-aware version of the Soufflé Datalog engine. The engine can take facts annotated with Presence Conditions (PCs) as input, and compute the PCs of its inferred facts, eliminating facts that do not exist in any valid configuration. We evaluate our variability-aware Soufflé implementation on several fact sets annotated with PCs to measure the associated overhead in terms of processing time and database size.