<p dir="ltr">This thesis explores two approaches to bridge the gap between expressiveness and performance in programming languages. It presents two complementary directions that reconcile performance and expressiveness: retrofitting static performance guarantees into an expressive general-purpose language like Scala, and transparently extending a restricted language like Datalog with features like polymorphism and user-defined functions while generating specialized and efficient code.</p><p dir="ltr">We first introduce storage modes, lightweight type qualifiers that enable statically tracking the lifetime of values in Scala programs. This enables stack allocating them and reduce memory pressure on the garbage collector. A key novelty is delaying the popping of the stack frames when returning dynamically-sized stack-allocated values, overcoming limitations of previous approaches.</p><p dir="ltr">Second, we present Flan, a Datalog compiler and embedding in Scala implemented as a multi-stage interpreter. Through staging, Flan can generate highly specialized code for different execution strategies and indexing structures, achieving performance on par with state-of-the-art domain-specific compilers like Soufflé. Moreover, by leveraging the host language, Flan enables seamless extension of Datalog with powerful features like user-defined functions, lattices and polymorphism, retaining the expressiveness of languages like Flix.</p><p dir="ltr">Overall, this work advances the design space for expressive and efficient programming languages, through lightweight annotations in an expressive host language, and transparent compiler specialization of an embedded domain-specific language. The techniques intoduced bridghe the gap between low-level performance and high-level programming abstractions.</p>

Constraint Satisfaction Probleme tauchen in vielen Gebieten der theoretischen Informatik auf. Häufig lassen sie sich auf natürliche Weise als Homomorphieprobleme für eine festgelassene Struktur Gamma formulieren: Die Berechnungsaufgabe besteht dann darin, für eine gegebene Struktur S mit der gleichen relationalen Signatur wie Gamma festzustellen, ob es einen Homomorphismus von S nach Gamma gibt. Dieses Problem wurde für enliche Strukturen Gamma intensiv untersucht. Viele der Constraint Satisfaction Probleme, die in der Literatur betrachtet werden, lassen sich jedoch nicht mit endlichen Schablonen Gamma formulieren. Diese Arbeit verallgemeinert Techniken zur Untersuchung der Berechnungskomplexität von Constraint Satisfaction Problemen mit endlichen Schablonen auf unendliche Schablonen. Insbesondere betrachten wir abzählbar kategorische Schablonen, die von zentraler Bedeutung in Modelltheorie sind. / Constraint satisfaction problems occur in many areas of computer science. Often they have a natural formulation as a homomorphism problem for a fixed relational structure Gamma: Given a structure S with the same relational signature as Gamma, is there a homomorphism from S to Gamma? This problem is known as the constraint satisfaction problem CSP(Gamma) for the template Gamma and is intensively studied for relational structures Gamma with a finite domain. However, many constraint satisfaction problems in the literature can not be formulated with a finite template. This thesis generalizes techniques to determine the complexity of constraint satisfaction with finite templates to constraint satisfaction with templates over an infinite domain. In particular, we study templates that are countably categorical. Such structures are a central and well-studied concept in model-theory.

Our goal is to enable aWeb user to easily specify distributed data managementtasks in place, i.e. without centralizing the data to a single provider. Oursystem is therefore not a replacement for Facebook, or any centralized system,but an alternative that allows users to launch their own peers on their machinesprocessing their own local personal data, and possibly collaborating with Webservices.We introduce Webdamlog, a datalog-style language for managing distributeddata and knowledge. The language extends datalog in a numberof ways, notably with a novel feature, namely delegation, allowing peersto exchange not only facts but also rules. We present a user study thatdemonstrates the usability of the language. We describe a Webdamlog enginethat extends a distributed datalog engine, namely Bud, with the supportof delegation and of a number of other novelties of Webdamlog such as thepossibility to have variables denoting peers or relations. We mention noveloptimization techniques, notably one based on the provenance of facts andrules. We exhibit experiments that demonstrate that the rich features ofWebdamlog can be supported at reasonable cost and that the engine scales tolarge volumes of data. Finally, we discuss the implementation of a Webdamlogpeer system that provides an environment for the engine. In particular, a peersupports wrappers to exchange Webdamlog data with non-Webdamlog peers.We illustrate these peers by presenting a picture management applicationthat we used for demonstration purposes.

L'objectif du problème appelé "Ontology-based data access" (OBDA) est d'améliorer la réponse à des requêtes en prenant en compte des connaissances d'ordre général durant l'évaluation des requêtes. Ces connaissances générales sont représentées à l'aide d'une ontologie, qui est exprimée dans cette thèse grâce à des formules logiques du premier ordre, appelées règles existentielles, et aussi connues sous le nom de "tuple-generating dependencies" et Datalog+/-. L'expressivité des formules utilisées est telle que l'évaluation de requêtes devient un problème indécidable, et cela a conduit la communauté à définir de nombreux cas décidables, c'est-à-dire des restrictions sur les ensembles de règles existentielles considérés. La contribution de cette thèse est double : tout d'abord, nous proposons une vue unifiée sur une grande fraction des cas décidables connus, et fournissons par là même une analyse de complexité et un algorithme optimal dans le pire des cas. Nous considérons également l'approche couramment utilisée de réécriture de requêtes, et proposons un algorithme générique qui permet de surmonter certaines causes évidentes d'explosion combinatoire qui rendent les approches classiques pratiquement inapplicables.

Notre but est de permettre à un utilisateur du Web d'organiser la gestion de ses données distribuées en place, c'est à dire sans l'obliger à centraliser ses données chez un unique hôte. Par conséquent, notre système diffère de Facebook et des autres systèmes centralisés, et propose une alternative permettant aux utilisateurs de lancer leurs propres pairs sur leurs machines gérant localement leurs données personnelles et collaborant éventuellement avec des services Web externes. Dans ma thèse, je présente Webdamlog, un langage dérivé de datalog pour la gestion de données et de connaissances distribuées. Le langage étend datalog de plusieurs manières, principalement avec une nouvelle propriété la délégation, autorisant les pairs à échanger non seulement des faits (les données) mais aussi des règles (la connaissance). J'ai ensuite mené une étude utilisateur pour démontrer l'utilisation du langage. Enfin je décris le moteur d'évaluation de Webdamlog qui étend un moteur d'évaluation de datalog distribué nommé Bud, en ajoutant le support de la délégation et d'autres innovations telles que la possibilité d'avoir des variables pour les noms de pairs et des relations. J'aborde de nouvelles techniques d'optimisation, notamment basées sur la provenance des faits et des règles. Je présente des expérimentations qui démontrent que le coût du support des nouvelles propriétés de Webdamlog reste raisonnable même pour de gros volumes de données. Finalement, je présente l'implémentation d'un pair Webdamlog qui fournit l'environnement pour le moteur. En particulier, certains adaptateurs permettant aux pairs Webdamlog d'échanger des données avec d'autres pairs sur Internet. Pour illustrer l'utilisation de ces pairs, j'ai implémenté une application de partage de photos dans un réseau social en Webdamlog.

Cette thèse traite de l’établissement d’une plateforme logicielle nommée DaWeS permettant le déploiement et la gestion en ligne d’entrepôts de données alimentés par des données provenant de services web et personnalisés à destination des petites et moyennes entreprises. Ce travail s’articule autour du développement et de l’expérimentation de DaWeS. L’idée principale implémentée dans DaWeS est l’utilisation d’une approche virtuelle d’intégration de données (la médiation) en tant queprocessus ETL (extraction, transformation et chargement des données) pour les entrepôts de données gérés par DaWeS. A cette fin, un algorithme classique de réécriture de requêtes (l’algorithme inverse-rules) a été adapté et testé. Une étude théorique sur la sémantique des requêtes conjonctives et datalog exprimées avec des relations munies de limitations d’accès (correspondant aux services web) a été menée. Cette dernière permet l’obtention de bornes supérieures sur les nombres d’appels aux services web requis dans l’évaluation de telles requêtes. Des expérimentations ont été menées sur des services web réels dans trois domaines : le marketing en ligne, la gestion de projets et les services d’aide aux utilisateurs. Une première série de tests aléatoires a été effectuée pour tester le passage à l’échelle. / The role of data warehouse for business analytics cannot be undermined for any enterprise, irrespective of its size. But the growing dependence on web services has resulted in a situation where the enterprise data is managed by multiple autonomous and heterogeneous service providers. We present our approach and its associated prototype DaWeS [Samuel, 2014; Samuel and Rey, 2014; Samuel et al., 2014], a DAta warehouse fed with data coming from WEb Services to extract, transform and store enterprise data from web services and to build performance indicators from them (stored enterprise data) hiding from the end users the heterogeneity of the numerous underlying web services. Its ETL process is grounded on a mediation approach usually used in data integration. This enables DaWeS (i) to be fully configurable in a declarative manner only (XML, XSLT, SQL, datalog) and (ii) to make part of the warehouse schema dynamic so it can be easily updated. (i) and (ii) allow DaWeS managers to shift from development to administration when they want to connect to new web services or to update the APIs (Application programming interfaces) of already connected ones. The aim is to make DaWeS scalable and adaptable to smoothly face the ever-changing and growing web services offer. We point out the fact that this also enables DaWeS to be used with the vast majority of actual web service interfaces defined with basic technologies only (HTTP, REST, XML and JSON) and not with more advanced standards (WSDL, WADL, hRESTS or SAWSDL) since these more advanced standards are not widely used yet to describe real web services. In terms of applications, the aim is to allow a DaWeS administrator to provide to small and medium companies a service to store and query their business data coming from their usage of third-party services, without having to manage their own warehouse. In particular, DaWeS enables the easy design (as SQL Queries) of personalized performance indicators. We present in detail this mediation approach for ETL and the architecture of DaWeS. Besides its industrial purpose, working on building DaWeS brought forth further scientific challenges like the need for optimizing the number of web service API operation calls or handling incomplete information. We propose a bound on the number of calls to web services. This bound is a tool to compare future optimization techniques. We also present a heuristics to handle incomplete information.

In safety-critical, networked embedded systems, it is important that the way in which a fault(s) in one component of the system can propagate throughout the system to other components is analyzed correctly. Many real-world systems, such as modern aircrafts and automobiles, use large-scale networked embedded systems with complex behavior. In this work, we have developed techniques and a software tool, FauPA, that uses those techniques to automate fault-propagation analysis of large-scale, networked embedded systems such as those used in modern aircraft. This work makes three main contributions. 1. Fault propagation analyses. We developed algorithms for two types of analyses: forward analysis and backward analysis. For backward analysis, we developed two techniques: a naive algorithm and an algorithm that uses Datalog. 2. A system description language. We developed a language that we call Communication System Markup Language (CSML) based on XML. A system can be specified concisely and at a high-level in CSML. 3. A GUI-based display of the system and analysis results. We developed a GUI to visualize the system that is specified in CSML. The GUI also lets the user visualize the results of fault-propagation analyses.

La Tesis investiga técnicas ágiles dentro del paradigma declarativo para dar solución a dos problemas: el análisis de programas y la inferencia de especificaciones a partir de programas escritos en lenguajes multiparadigma y en lenguajes imperativos con tipos, objetos, estructuras y punteros. Respecto al estado actual de la tesis, la parte de análisis de programas ya está consolidada, mientras que la parte de inferencia de especificaciones sigue en fase de desarrollo activo. La primera parte da soluciones para la ejecución de análisis de punteros especificados en Datalog. En esta parte se han desarrollado dos técnicas de ejecución de especificaciones en dicho lenguaje Datalog: una de ellas utiliza resolutores de sistemas de ecuaciones booleanas, y la otra utiliza la lógica de reescritura implementada eficientemente en el lenguaje Maude. La segunda parte desarrolla técnicas de inferencia de especificaciones a partir de programas. En esta parte se han desarrollado dos métodos de inferencia de especificaciones. El primer método se desarrolló para el lenguaje lógico-funcional Curry y permite inferir especificaciones ecuacionales mediante interpretación abstracta de los programas. El segundo método está siendo desarrollado para lenguajes imperativos realistas, y se ha aplicado a un subconjunto del lenguaje de programación C. Este método permite inferir especificaciones en forma de reglas que representan las distintas relaciones entre las propiedades que el estado de un programa satisface antes y después de su ejecución. Además, estas propiedades son expresables en términos de las abstracciones funcionales del propio programa, resultando en una especificación de muy alto nivel y, por lo tanto, de más fácil comprensión. / Feliú Gabaldón, MA. (2013). Logic-based techniques for program analysis and specification synthesis [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/33747 / TESIS

<pre>The proliferation of digital data, driven by factors like social media, e-commerce, etc., has created an increasing demand for highly processed data at higher levels of fidelity, which puts increasing demands on modern data processing systems. In the past, data processing systems faced bottlenecks due to limited main memory availability. However, as main memory becomes more abundant, their optimization focus has shifted from disk I/O to optimized computation through techniques like compilation. This dissertation addresses several critical limitations within such compilation-based data processing systems.<br><br>In modern data analytics pipelines, combination of workloads from various paradigms, such as traditional DBMS and Machine Learning, is common. <br>These pipelines are typically managed by specialized systems designed for specific workload types. While these specialized systems optimize their individual performance, substantial performance loss occurs when they are combined to handle mixed workloads. This loss is mainly due to overheads at system boundaries, including data copying and format conversions, as well as the general inability to perform cross-system optimizations.<br><br>This dissertation tackles this problem in two angles. First, it proposes an efficient post-hoc integration of individual systems using generative programming via the construction of common intermediate layers. This approach preserves the best-of-breed performance of individual workloads while achieving state-of-the-art performance for combined workloads. Second, we introduce a high-level query language capable of expressing various workload types, acting as a general substrate to implement combined workloads. This allows the generation of optimized code for end-to-end workloads through<br>the construction of an intermediate representation (IR).<br><br>The dissertation then shifts focus to data processing systems used for incremental view maintenance (IVM). While existing IVM systems achieve high performance through compilation and novel algorithms, they have limitations in handling specific query classes. Notably, they are incapable of handling queries involving correlated nested aggregate subqueries. To address this, our work proposes a novel indexing scheme based on a new data structure and a corresponding set of algorithms that fully incrementalize such queries. This approach result in substantial asymptotic speedups and order-of-magnitude performance improvements for workloads of practical importance.<br><br>Finally, the dissertation explores efficient and expressive fixed-point computations, with a focus on Datalog--a language widely used for declarative program analysis. Although existing Datalog engines rely on compilation and specialized code generation to achieve performance, they lack the flexibility to support extensions required for complex program analysis. Our work introduces a new Datalog engine built using generative programming techniques that offers both flexibility and state-of-the-art performance through specialized code generation.</pre><p></p>

Les grammaires catégorielles abstraites (ou λ-grammaires) sont un formalisme basé sur le λ-calcul simplement typé. Elles peuvent être vues comme des grammaires générant de tels termes, et ont été introduites afin de modéliser l'interface entre la syntaxe et la sémantique du langage naturel, réunissant deux idées fondamentales : la distinction entre tectogrammaire (c.a.d. structure profonde d'un énoncé) et phénogrammaire (c.a.d représentation de la surface d'un énoncé) de la langue, exprimé par Curry ; et une modélisation algébrique du principe de compositionnalité afin de rendre compte de la sémantique des phrases, due à Montague. Un des avantages principaux de ce formalisme est que l'analyse d'une grammaires catégorielle abstraite permet de résoudre aussi bien le problème de l'analyse de texte, que celui de la génération de texte. Des algorithmes d'analyse efficaces ont été découverts pour les grammaires catégorielles abstraites de termes linéaires et quasi-linéaires, alors que le problème de l'analyse est non-élémentaire dans sa forme la plus générale. Nous proposons d'étudier des classes de termes pour lesquels l'analyse grammaticale reste solvable en temps polynomial. Ces résultats s'appuient principalement sur deux théorèmes de typage : le théorème de cohérence, spécifiant qu'un λ-terme donné est l'unique habitant d'un certain typage ; et le théorème d'expansion du sujet, spécifiant que deux termes β-équivalents habitent les même typages. Afin de mener cette étude à bien, nous utiliserons une représentation abstraite des notions de λ-termes et de typages, sous forme de jeux. En particulier, nous nous appuierons grandement sur cette notion afin de démontrer le théorème de cohérence pour de nouvelles familles de λ-termes et de typages. Grâce à ces résultats, nous montrerons qu'il est possible de construire de manière directe, un reconnaisseur dans le langage Datalog, pour des grammaires catégorielles abstraites de λ-termes quasi-affines.