Search

Grounding natural language in images, such as localizing "the black dog on the left of the tree", is one of the core problems in artificial intelligence, as it needs to comprehend the fine-grained and compositional language space. However, existing solutions rely on the association between the holistic language features and visual features, while neglect the nature of compositional reasoning implied in the language. In this paper, we propose a natural language grounding model that can automatically compose a binary tree structure for parsing the language and then perform visual reasoning along the tree in a bottom-up fashion. We call our model RVG-TREE: Recursive Grounding Tree, which is inspired by the intuition that any language expression can be recursively decomposed into two constituent parts, and the grounding confidence score can be recursively accumulated by calculating their grounding scores returned by sub-trees. RVG-TREE can be trained end-to-end by using the Straight-Through Gumbel-Softmax estimator that allows the gradients from the continuous score functions passing through the discrete tree construction. Experiments on several benchmarks show that our model achieves the state-of-the-art performance with more explainable reasoning., Comment: Accepted to IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)

Theories of higher-order must-alias analysis, often under the guise of environment analysis, provide deep behavioral insight. But these theories---in particular those that are most insightful otherwise---can reason about recursion only in limited cases. This weakness is not inherent to the theories but to the frameworks in which they're defined: machine models which thread the heap through evaluation. Since these frameworks allocate each abstract resource in the heap, the constituent theories of environment analysis conflate co-live resources identified in the abstract, such as recursively-created bindings. We present heap fragments as a general technique to allow these theories to reason about recursion in a general and robust way. We instantiate abstract counting in a heap-fragment framework and compare its performance to a precursor entire-heap framework. We also sketch an approach to realizing binding invariants, a more powerful environment analysis, in the heap-fragment framework.

Motivated by old and new applications, we investigate Datalog as a language for sequence databases. We reconsider classical features of Datalog programs, such as negation, recursion, intermediate predicates, and relations of higher arities. We also consider new features that are useful for sequences, notably, equations between path expressions, and "packing". Our goal is to clarify the relative expressiveness of all these different features, in the context of sequences. Towards our goal, we establish a number of redundancy and primitivity results, showing that certain features can, or cannot, be expressed in terms of other features. These results paint a complete picture of the expressiveness relationships among all possible Sequence Datalog fragments that can be formed using the six features that we consider., This paper is the extended version of a paper presented at PODS 2021

Scala is a well-established multi-paradigm programming language known for its terseness that includes advanced type inference features. Unfortunately this type inferring algorithm does not support typing of recursive functions. This is both against the original design philosophies of Scala and puts an unnecessary burden on the programmer. In this paper we propose a method to compute the return types for simple recursive functions in Scala. We make a heuristic assumption on the return type based on the non-recursive execution branches and provide a proof of this method's correctness. The algorithm does not have a significant effect on the compilation speed. We implemented our method as an extension prototype in the Scala compiler and used it to successfully test our method on various examples. The compiler extension prototype is available for further tests.

This paper describes an implementation of Harper's continuation-based regular-expression matcher as a strong functional program in Cedille; i.e., Cedille statically confirms termination of the program on all inputs. The approach uses neither dependent types nor termination proofs. Instead, a particular interface dubbed a recursion universe is provided by Cedille, and the language ensures that all programs written against this interface terminate. Standard polymorphic typing is all that is needed to check the code against the interface. This answers a challenge posed by Bove, Krauss, and Sozeau.

O programa minimalista propõe um modelo de evolução da linguagem e um programa de pesquisas comparativo, interdisciplinar e empírico para a questão. A concepção de que a linguagem é uma capacidade emergente somente na nossa espécie sugere que os processos de seleção e de adaptação não influenciaram decisivamente na emergência de tal característica. Paralelamente, a pragmática cognitiva de orientação relevantista desenvolve, há mais de trinta anos, uma concepção de evolução de comportamento comunicativo que diverge das posturas centrais do programa minimalista. Este trabalho tem o intuito de apontar para questões epistemológicas e metodológicas que decorrem da confrontação entre ambas as propostas. A afirmação principal defendida aqui é a de que a adoção de uma perspectiva fortemente adaptacionista para a comunicação (viés relevantista) e fracamente adaptacionista para a linguagem/recursividade (viés minimalista), considerando a recursividade, assim como a comunicação verbal, capacidades emergentes da cognição humana, é possível desde que a centralidade da sintaxe, defendida pelo modelo gerativista e sutilmente reafirmada no programa minimalista, seja deixada de lado em prol de um modelo que não se furte a apontar uma explicação natural da comunicação via linguagem.

Nowadays, Heart disease is one of the crucial impacts of mortality in the country. In clinical data analysis, predicting cardiovascular disease is a primary challenge. Deep learning (DL) has been demonstrated to be effective in helping to determine and forecast a huge amount of data produced by the health industry. In this paper, the proposed Recursion enhanced random forest with an improved linear model (RFRF-ILM) to detect heart disease. This paper aims to find the key features of the prediction of cardiovascular diseases through the use of machine learning techniques. The prediction model is adding various combinations of features and various established methods of classification. it produces a better level of performance with precision through the heart disease prediction model. In this study, the factors leading to cardiovascular disease can be diagnosed. A comparison of important variables showed with the Internet of Medical Things (IoMT) platform, for data analysis. This indicates that coronary artery disease develops more often in older ages. Also important in this disease's outbreak is high blood pressure. For this purpose, measures must be taken to prevent this disease and Diabetes provides a further aspect that should be taken into consideration in the occurrence of coronary artery disease with 96.6 % accuracy,96.8% stability ratio and 96.7% F-measure ratio.

Tapir (pronounced TAY-per) is a compiler intermediate representation (IR) that embeds recursive fork-join parallelism, as supported by task-parallel programming platforms such as Cilk and OpenMP, into a mainstream compiler’s IR. Mainstream compilers typically treat parallel linguistic constructs as syntactic sugar for function calls into a parallel runtime. These calls prevent the compiler from performing optimizations on and across parallel control constructs. Remedying this situation has generally been thought to require an extensive reworking of compiler analyses and code transformations to handle parallel semantics. Tapir leverages the “serial-projection property,” which is commonly satisfied by task-parallel programs, to handle the semantics of these programs without an extensive rework of the compiler. For recursive fork-join programs that satisfy the serial-projection property, Tapir enables effective compiler optimization of parallel programs with only minor changes to existing compiler analyses and code transformations. Tapir uses the serial-projection property to order logically parallel fine-grained tasks in the program’s control-flow graph. This ordered representation of parallel tasks allows the compiler to optimize parallel codes effectively with only minor modifications. For example, to implement Tapir/LLVM, a prototype of Tapir in the LLVM compiler, we added or modified less than 3,000 lines of LLVM’s half-million-line core middle-end functionality. These changes sufficed to enable LLVM’s existing compiler optimizations for serial code—including loop-invariant-code motion, common-subexpression elimination, and tail-recursion elimination—to work with parallel control constructs such as parallel loops and Cilk’s Cilk_Spawn keyword. Tapir also supports parallel optimizations, such as loop scheduling, which restructure the parallel control flow of the program. By making use of existing LLVM optimizations and new parallel optimizations, Tapir/LLVM can optimize recursive fork-join programs more effectively than traditional compilation methods. On a suite of 35 Cilk application benchmarks, Tapir/LLVM produces more efficient executables for 30 benchmarks, with faster 18-core running times for 26 of them, compared to a nearly identical compiler that compiles parallel linguistic constructs the traditional way.

We carry out a proof-theoretic analysis of the wellfoundedness of recursive path orders in an abstract setting. We outline a general termination principle and extract from its wellfoundedness proof subrecursive bounds on the size of derivation trees that can be defined in Gödel’s system T plus bar recursion. We then carry out a complexity analysis of these terms and demonstrate how this can be applied to bound the derivational height of term rewrite systems.

The paper describes recent improvements made to the structural recursion of the Data Funnel Interface. This end user interface organizes the raw data in a database table into a series of nested data lists that guide users to information. The new developments outlined in the article streamline the recursive algorithm and the data files that it produces. The program logic constructs a new SELECT statement on each recursive pass to retrieve a unique subset of attribute data from the table. Next, it transforms the subset’s structure into a structure of nested data lists that users can navigate in the interface. The branching data model (BDM) provides the framework for combining these two objectives into a single, recursive algorithm. The data BDM features a detailed description of the data mapping between two table attributes as one-to-many data relationships. The input data for the recursion is a list of table attributes that models the data funnel network. Each new subset of data in the series folds into the former one until it reaches the final subset, a primary key value. The prior algorithm draws on the depth-first tree growing methodology of the OHDS structure to manage these subsets. The paper introduces a new numbering scheme to organize the subsets of data. This improvement assigns a unique list number to each new subset when adding it to the database table. This capability replaces the need for the OHDS in the table. It also simplifies the data funnel software and makes it easier to maintain.

We introduce a method for proving almost sure termination in the context of lambda calculus with continuous random sampling and explicit recursion, based on ranking supermartingales. This result is extended in three ways. Antitone ranking functions have weaker restrictions on how fast they must decrease, and are applicable to a wider range of programs. Sparse ranking functions take values only at a subset of the program’s reachable states, so they are simpler to define and more flexible. Ranking functions with respect to alternative reduction strategies give yet more flexibility, and significantly increase the applicability of the ranking supermartingale approach to proving almost sure termination, thanks to a novel (restricted) confluence result which is of independent interest. The notion of antitone ranking function was inspired by similar work by McIver, Morgan, Kaminski and Katoen in the setting of a first-order imperative language, but adapted to a higher-order functional language. The sparse ranking function and confluent semantics extensions are unique to the higher-order setting. Our methods can be used to prove almost sure termination of programs that are beyond the reach of methods in the literature, including higher-order and non-affine recursion.

PL/SQL integrates an imperative statement-by-statement style of programming with the plan-based evaluation of SQL queries. The disparity of both leads to friction at runtime, slowing PL/SQL execution down significantly. This work describes a compiler from PL/SQL UDFs to plain SQL queries. Post-compilation, evaluation entirely happens on the SQL side of the fence. With the friction gone, we observe execution times to improve by about a factor of 2, even for complex UDFs. The compiler builds on techniques long established by the programming language community. In particular, it uses trampolined style to compile arbitrarily nested iterative control flow in PL/SQL into SQL's recursive common table expressions.

There is a longstanding debate in the literature about if, and where, recursion occurs in prosodic structure. While there are clear cases of genuine recursion at the phrase level and above, there are very few convincing cases of word-level recursion. Most cases are—by definition—not recursive and instead best analyzed as different constituents (e.g., the Composite Group, Prosodic Word Group, etc.). We show that two convincing cases of prosodic word-level recursion can easily be reanalyzed without recursion if phonology and prosody are evaluated cyclically at syntactic phase boundaries. Our analysis combines phase-based spell-out and morpheme-specific subcategorization frames of Cophonologies by Phase with Tri-P Mapping prosodic structure building. We show that apparent word-level recursion is due to cyclic spell-out, and non-isomorphisms between syntactic and prosodic structure are due to morpheme-specific prosodic requirements.

Verification of AI is a challenge that has engineering, algorithmic and programming language components. For example, AI planners are deployed to model actions of autonomous agents. They comprise a number of searching algorithms that, given a set of specified properties, find a sequence of actions that satisfy these properties. Although AI planners are mature tools from the algorithmic and engineering points of view, they have limitations as programming languages. Decidable and efficient automated search entails restrictions on the syntax of the language, prohibiting use of higher-order properties or recursion. This paper proposes a methodology for embedding plans produced by AI planners into dependently-typed language Agda, which enables users to reason about and verify more general and abstract properties of plans, and also provides a more holistic programming language infrastructure for modelling plan execution., 14 pages, 5 figures, Accepted to TyDe 2021

Languages differ regarding the depth, structure, and syntactic domains of recursive structures. Even within a single language, some structures allow infinite self-embedding while others are more restricted. For example, English allows infinite free embedding of the prenominal genitive -s, whereas the postnominal genitive of is largely restricted to only one level and to a limited set of items. Therefore, while the ability for recursion is considered as a crucial part of the language faculty, speakers need to learn from experience which specific structures allow free embedding and which do not. One effort to account for the mechanism that underlies this learning process, the distributional learning proposal, suggests that the recursion of a structure (e.g. X1’s-X2) is licensed if the X1 position and the X2 position are productively substitutable in the input. A series of corpus studies have confirmed the availability of such distributional cues in child directed speech. The present study further tests the distributional learning proposal with an artificial language learning experiment. We found that, as predicted, participants exposed to productive input were more likely to accept unattested strings at both one and two-embedding levels than participants exposed to unproductive input. Therefore, our results suggest that speakers can indeed use distributional information at one level to learn whether or not a structure is freely recursive.

We demonstrate a computational restriction on iterative prosody in phonology by using logical transductions. We show that the typology is fundamentally local but requires output recursion, formulated via quantifier-free transductions and least-fixed-point operators, respectively. We focus on two case studies from iterative prosody. One is iterative secondary stress. The other is more complex: iterative syllabification and epenthesis in Arabic dialects. The second case study involves formalizing Ito (1989)'s analysis of directional syllabification.

In the past, the semantic issues raised by the non-monotonic nature of aggregates often prevented their use in the recursive statements of logic programs and deductive databases. However, the recently introduced notion of Pre-mappability (PreM) has shown that, in key applications of interest, aggregates can be used in recursion to optimize the perfect-model semantics of aggregate-stratified programs. Therefore we can preserve the declarative formal semantics of such programs while achieving a highly efficient operational semantics that is conducive to scalable implementations on parallel and distributed platforms. In this paper, we show that with PreM, a wide spectrum of classical algorithms of practical interest, ranging from graph analytics and dynamic programming based optimization problems to data mining and machine learning applications can be concisely expressed in declarative languages by using aggregates in recursion. Our examples are also used to show that PreM can be checked using simple techniques and templatized verification strategies. A wide range of advanced BigData applications can now be expressed declaratively in logic-based languages, including Datalog, Prolog, and even SQL, while enabling their execution with superior performance and scalability., In Proceedings ICLP 2019, arXiv:1909.07646. Paper presented at the 35th International Conference on Logic Programming (ICLP 2019), Las Cruces, New Mexico, USA, 20-25 September 2019, 7 pages (short paper - applications track)

The input language of the answer set solver clingo is based on the definition of a stable model proposed by Paolo Ferraris. The semantics of the ASP-Core language, developed by the ASP Standardization Working Group, uses the approach to stable models due to Wolfgang Faber, Nicola Leone, and Gerald Pfeifer. The two languages are based on different versions of the stable model semantics, and the ASP-Core document requires, "for the sake of an uncontroversial semantics," that programs avoid the use of recursion through aggregates. In this paper we prove that the absence of recursion through aggregates does indeed guarantee the equivalence between the two versions of the stable model semantics, and show how that requirement can be relaxed without violating the equivalence property. The paper is under consideration for publication in Theory and Practice of Logic Programming., Comment: Paper presented at the 35th International Conference on Logic Programming (ICLP 2019), Las Cruces, New Mexico, USA, 20-25 September 2019, 20 pages

Machine learning has made major advances in categorizing objects in images, yet the best algorithms miss important aspects of how people learn and think about categories. People can learn richer concepts from fewer examples, including causal models that explain how members of a category are formed. Here, we explore the limits of this human ability to infer causal “programs”—latent generating processes with nontrivial algorithmic properties—from one, two, or three visual examples. People were asked to extrapolate the programs in several ways, for both classifying and generating new examples. As a theory of these inductive abilities, we present a Bayesian program learning model that searches the space of programs for the best explanation of the observations. Although variable, people’s judgments are broadly consistent with the model and inconsistent with several alternatives, including a pretrained deep neural network for object recognition, indicating that people can learn and reason with rich algorithmic abstractions from sparse input data.

In 1970's, Nivat studied recursive program schemes (a.k.a order-1 higher-order recursion schemes in modern terminology), first-order tree grammars for generating possibly infinite trees. We consider the inclusion problem between the frontier language of a non-deterministic recursive program scheme (equivalently, an order-2 word language or indexed language) and the Dyck language, and prove that it is undecidable by a reduction from the undecidability of Hilbert's 10th problem. Essentially the same result has recently been proved by Uezato and Minamide, but our proof is arguably more direct, demonstrating the expressive power of higher-order grammars.

© 2019 Elsevier B.V. Intensional computations are those that query the internal structure of their arguments. In a higher-order setting, such queries perform program analysis. This is beyond the expressive power of traditional term rewriting systems, such as lambda-calculus or combinatory logic, as they are extensional. In such settings it has been necessary to encode or quote the program before analysis. However, there are intensional calculi, specifically confluent term rewriting systems, that can analyse higher-order programs within the calculus proper, without quotation; there are even programs that produce the Goedel numbers of their program argument. This paper summarizes the current situation. Highlights include the following observations. We have known since 2011 that the simplest intensional calculus, SF-calculus, supports arbitrary queries of closed normal forms, including equality, pattern-matching, searching and self-interpretation. Recent work, verified using the Coq proof assistant, has shown that all recursive programs can be represented as closed normal forms in SF-calculus, and even in combinatory logic. Thus, we can here deduce that SF-calculus (but not combinatory logic) can define queries of programs. These results are compatible with direct support for lambda-abstraction. Although these results conflict with the traditional understanding of expressive power of combinatory logic and λ-calculus, as developed by Church and Kleene, our recent publication has shown that their approach is compromised by its reliance on encodings. To drive the point home, this paper uses a non-standard encoding to lambda-define a trivial solution of the Halting Problem.

Generation of hierarchical structures, such as the embedding of subordinate elements into larger structures, is a core feature of human cognition. Processing of hierarchies is thought to rely on lateral prefrontal cortex (PFC). However, the neural underpinnings supporting active generation of new hierarchical levels remain poorly understood. Here, we created a new motor paradigm to isolate this active generative process by means of fMRI. Participants planned and executed identical movement sequences by using different rules: a Recursive hierarchical embedding rule, generating new hierarchical levels; an Iterative rule linearly adding items to existing hierarchical levels, without generating new levels; and a Repetition condition tapping into short term memory, without a transformation rule. We found that planning involving generation of new hierarchical levels (Recursive condition vs. both Iterative and Repetition) activated a bilateral motor imagery network, including cortical and subcortical structures. No evidence was found for lateral PFC involvement in the generation of new hierarchical levels. Activity in basal ganglia persisted through execution of the motor sequences in the contrast Recursive versus Iteration, but also Repetition versus Iteration, suggesting a role of these structures in motor short term memory. These results showed that the motor network is involved in the generation of new hierarchical levels during motor sequence planning, while lateral PFC activity was neither robust nor specific. We hypothesize that lateral PFC might be important to parse hierarchical sequences in a multi‐domain fashion but not to generate new hierarchical levels.

We present a new, syntax-directed framework for Curry-style type systems with subtyping. It supports a rich set of features, and allows for a reasonably simple theory and implementation. The system we consider has sum and product types, universal and existential quantifiers, and inductive and coinductive types. The latter two may carry size invariants that can be used to establish the termination of recursive programs. For example, the termination of quicksort can be derived by showing that partitioning a list does not increase its size. The system deals with complex programs involving mixed induction and coinduction, or even mixed polymorphism and (co-)induction. One of the key ideas is to separate the notion of size from recursion. We do not check the termination of programs directly, but rather show that their (circular) typing proofs are well-founded. Termination is then obtained using a standard (semantic) normalisation proof. To demonstrate the practicality of the system, we provide an implementation accepting all the examples discussed in the article.

Parallel dataflow engines such as Apache Hadoop, Apache Spark, and Apache Flink are an established alternative to relational databases for modern data analysis applications. A characteristic of these systems is a scalable programming model based on distributed collections and parallel transformations expressed by means of second-order functions such as map and reduce. Notable examples are Flink’s DataSet and Spark’s RDD programming abstractions. These programming models are realized as EDSLs—domain specific languages embedded in a general-purpose host language such as Java, Scala, or Python. This approach has several advantages over traditional external DSLs such as SQL or XQuery. First, syntactic constructs from the host language (e.g., anonymous functions syntax, value definitions, and fluent syntax via method chaining) can be reused in the EDSL. This eases the learning curve for developers already familiar with the host language. Second, it allows for seamless integration of library methods written in the host language via the function parameters passed to the parallel dataflow operators. This reduces the effort for developing analytics dataflows that go beyond pure SQL and require domain-specific logic. At the same time, however, state-of-the-art parallel dataflow EDSLs exhibit a number of shortcomings. First, one of the main advantages of an external DSL such as SQL—the high-level, declarative Select-From-Where syntax—is either lost completely or mimicked in a non-standard way. Second, execution aspects such as caching, join order, and partial aggregation have to be decided by the programmer. Optimizing them automatically is very difficult due to the limited program context available in the intermediate representation of the DSL. In this article, we argue that the limitations listed above are a side effect of the adopted type-based embedding approach. As a solution, we propose an alternative EDSL design based on quotations. We present a DSL embedded in Scala and discuss its compiler pipeline, intermediate representation, and some of the enabled optimizations. We promote the algebraic type of bags in union representation as a model for distributed collections and its associated structural recursion scheme and monad as a model for parallel collection processing. At the source code level, Scala’s comprehension syntax over a bag monad can be used to encode Select-From-Where expressions in a standard way. At the intermediate representation level, maintaining comprehensions as a first-class citizen can be used to simplify the design and implementation of holistic dataflow optimizations that accommodate for nesting and control-flow. The proposed DSL design therefore reconciles the benefits of embedded parallel dataflow DSLs with the declarativity and optimization potential of external DSLs like SQL.

GLL is a worst-case cubic, recursive descent based parsing technique which can be applied to all BNF grammars without the need for grammar modification. However, EBNF grammars are often used, both for their compactness and their relative expressive simplicity. In this paper we give a formal specification for a parse tree representation of derivations which reflects the EBNF structure of the grammar, is worst case cubic size, and captures all derivations in the case of ambiguity. Particular care is need in the case of closures with nullable bodies. We also describe an extension of GLL which directly supports the EBNF constructs. The resulting parsers are worst case cubic and follow the structure of the specifying EBNF grammar, making the parser behaviour easy to reason about. The parsers exploit the efficiency of factorisation and the use of iteration rather than recursion, retaining the structure of the specification in the presence of embedded semantic actions.

Interactive user experiences on the web are becoming the norm. Client-side programs are becoming more complicated and have to deal with event handling, reading HTML document state and updating the interface. In this paper we propose a declarative language that supports these three facets of client-side browser development declaratively and provides a programming model where complex interfaces can be written using simple programming techniques such as records, functions and recursion.

Smart Factories are designed by Universities [e.g. 7, 1] and Research Institutes (e.g. IPA, IFF, IOSB, IFF, DFKI). Also, automotive companies are developing their ‘own’ Smart Factories [e.g. 3, 6]. The focus is on manufacturing processes, technical equipment, and control of technical processes but not on business and order processes [4, 5]. To run a Smart Factory also a concept for a “Digital Order Twin” (DOT) is needed to ensure that for each final product the right components are available in the right quantity at the right time and at the right place, especially if the product is configurated by a customer or dealer. But existing IT-Systems for Enterprise-Resource-Planning (ERPS), Material-Requirement-Planning (MRP) and Manufacturing Execution (MES) are not able to exploit the huge amount of acquired data ‘in-time’, because they are separated IT-Modules which are connected by batch-oriented interfaces only, the concept and algorithm base on the “Water-Fall-Model” without recursion to a preceding IT-System or IT-Module. In an autonomously controlled Smart Factory the right components must be referenced to each single final product instantly and in a more flexible way than the concept of pearl chain can do, instead of a unique DOT uses instantly data of RFID, QR-Code, Smart Devices and Cyber-Physical Objects and can interact in time with Systems and Modules.

When working to understand usage of a data format, examples of the data format are often more representative than the format's specification. For example, two different applications might use very different JSON representations, or two PDF-writing applications might make use of very different areas of the PDF specification to realize the same rendered content. The complexity arising from these distinct origins can lead to large, difficult-to-understand attack surfaces, presenting a security concern when considering both exfiltration and data schizophrenia. Grammar inference can aid in describing the practical language generator behind examples of a data format. However, most grammar inference research focuses on natural language, not data formats, and fails to support crucial features such as type recursion. We propose a novel set of mechanisms for grammar inference, RL-GRIT, and apply them to understanding de facto data formats. After reviewing existing grammar inference solutions, it was determined that a new, more flexible scaffold could be found in Reinforcement Learning (RL). Within this work, we lay out the many algorithmic changes required to adapt RL from its traditional, sequential-time environment to the highly interdependent environment of parsing. The result is an algorithm which can demonstrably learn recursive control structures in simple data formats, and can extract meaningful structure from fragments of the PDF format. Whereas prior work in grammar inference focused on either regular languages or constituency parsing, we show that RL can be used to surpass the expressiveness of both classes, and offers a clear path to learning context-sensitive languages. The proposed algorithm can serve as a building block for understanding the ecosystems of de facto data formats., Comment: 13 pages, published at IEEE LangSec 2021 (https://langsec.org/spw21/papers.html). ArXiv version: lacking correct 'minted' package behavior, so some atoms may look a little off

In this paper, we describe our experience incorporating gradual types in a statically typed functional language with Hindley-Milner style type inference. Where most gradually typed systems aim to improve static checking in a dynamically typed language, we approach it from the opposite perspective and promote dynamic checking in a statically typed language. Our approach provides a glimpse into how languages like SML and OCaml might handle gradual typing. We discuss our implementation and challenges faced -- specifically how gradual typing rules apply to our representation of composite and recursive types. We review the various implementations that add dynamic typing to a statically typed language in order to highlight the different ways of mixing static and dynamic typing and examine possible inspirations while maintaining the gradual nature of our type system. This paper also discusses our motivation for adding gradual types to our language, and the practical benefits of doing so in our industrial setting.

In call-by-value languages, some mutually-recursive value definitions can be safely evaluated to build recursive functions or cyclic data structures, but some definitions (let rec x = x + 1) contain vicious circles and their evaluation fails at runtime. We propose a new static analysis to check the absence of such runtime failures. We present a set of declarative inference rules, prove its soundness with respect to the reference source-level semantics of Nordlander, Carlsson, and Gill (2008), and show that it can be (right-to-left) directed into an algorithmic check in a surprisingly simple way. Our implementation of this new check replaced the existing check used by the OCaml programming language, a fragile syntactic/grammatical criterion which let several subtle bugs slip through as the language kept evolving. We document some issues that arise when advanced features of a real-world functional language (exceptions in first-class modules, GADTs, etc.) interact with safety checking for recursive definitions., Author version of POPL'21 article. 29 pages + Appendices

Given a simple recursive function, we show how to extract from it a reversible and an classical iterative part. Those parts can synchronously cooperate under a Producer/Consumer pattern in order to implement the original recursive function. The reversible producer is meant to run on reversible hardware. We also discuss how to extend the extraction to a more general compilation scheme., Comment: The first 10 pages will appear in the proceedings of 13th Conference on Reversible Computation. Appendix is for this authors version. arXiv admin note: substantial text overlap with arXiv:2102.09436

In the real world, multiple parties sometimes have different data of common instances, e.g., a customer of a supermarket can be a patient of a hospital. In other words, datasets are sometimes vertically partitioned into multiple parties. In such a situation, it is natural for those parties to collaborate to obtain more accurate prediction models; however, sharing their raw data should be prohibitive from the point of view of privacy-preservation. Federated learning has recently attracted the attention of machine learning researchers as a framework for efficiently collaborative learning of predictive models among multiple parties with privacy-preservation. In this paper, we propose a lossless vertical federated learning (VFL) method for higher-order factorization machines (HOFMs). HOFMs take into feature combinations efficiently and effectively and have succeeded in many tasks, especially recommender systems, link predictions, and natural language processing. Although it is intuitively difficult to evaluate and learn HOFMs without sharing raw feature vectors, our generalized recursion of ANOVA kernels enables us to do it. We also propose a more efficient and robust VFL method for HOFMs based on anonymization by clustering. Experimental results on three real-world datasets show the effectiveness of the proposed method .

Integrating machine learning techniques into RDBMSs is an important task since many real applications require modeling (e.g., business intelligence, strategic analysis) as well as querying data in RDBMSs. Without integration, it needs to export the data from RDBMSs to build a model using specialized ML toolkits and frameworks, and import the model trained back to RDBMSs for further querying. Such a process is not desirable since it is time-consuming and needs to repeat when data is changed. In this paper, we provide an SQL solution that has the potential to support different ML models in RDBMSs. We study how to support unsupervised probabilistic modeling, that has a wide range of applications in clustering, density estimation, and data summarization, and focus on Expectation-Maximization (EM) algorithms, which is a general technique for finding maximum likelihood estimators. To train a model by EM, it needs to update the model parameters by an E-step and an M-step in a while-loop iteratively until it converges to a level controlled by some thresholds or repeats a certain number of iterations. To support EM in RDBMSs, we show our solutions to the matrix/vectors representations in RDBMSs, the relational algebra operations to support the linear algebra operations required by EM, parameters update by relational algebra, and the support of a while-loop by SQL recursion. It is important to note that the SQL ’99 recursion cannot be used to handle such a while-loop since the M-step is non-monotonic. In addition, with a model trained by an EM algorithm, we further design an automatic in-database model maintenance mechanism to maintain the model when the underlying training data changes. We have conducted experimental studies and will report our findings in this paper.

The C++ template system is capable of performing arbitrary compile-time computations, which is typically exploited in generic programming libraries. However, the template language itself is syntactically cumbersome. A variety of tools, ranging from libraries to dedicated compilers, was created to alleviate this issue. One such approach is translating a functional program into a template metaprogram. In this work, we present a new way of translating functional programs based on lambda calculus into template metaprograms. The translation produces metaprograms with clearly defined lazy semantics and supports common functional features such as recursion and algebraic data types. We demonstrate its viability by providing a proof-of-concept implementation.

Capturing control flow is the Achilles heel of Haskell-based deeply embedded domain specific languages. Rather than use the builtin control flow mechanisms, artificial control flow combinators are used instead. However, capturing traditional control flow in a deeply embedded domain specific language would support the writing of programs in a natural style by allowing the programmer to use the constructs that are already builtin to the base language, such as pattern matching and recursion. In this paper, we expand the capabilities of Haskell-based deep embeddings with a compiler extension for reifying conditionals and pattern matching. With this new support, the subset of Haskell that we use for expressing deeply embedded domain specific languages can be cleaner, Haskell-idiomatic, and more declarative in nature.

International audience; A long-standing open problem in the semantics of programming languages supporting probabilistic choice is to find a commutative monad for probability on the category DCPO. In this paper we present three such monads and a general construction for finding even more. We show how to use these monads to provide a sound and adequate denotational semantics for the Probabilistic FixPoint Calculus (PFPC) - a call-by-value simply-typed lambda calculus with mixed-variance recursive types, term recursion and probabilistic choice. We also show that in the special case of continuous dcpo's, all three monads coincide with the valuations monad of Jones, and we fully characterise the induced Eilenberg-Moore categories by showing that they are all isomorphic to the category of continuous Kegelspitzen of Keimel and Plotkin.

A reliable technique for deductive program verification should be proven sound with respect to the semantics of the programming language. For each different language, the construction of a separate soundness proof is often a laborious undertaking. In language-independent program verification, common aspects of computer programs are addressed to enable sound reasoning for all languages. In this work, we propose a solution for the sound reasoning about iteration and recursion based on the big-step operational semantics of any programming language. We give inductive proofs on the soundness and relative completeness of our reasoning technique. We illustrate the technique at simplified programming languages of the imperative and functional paradigms, with diverse features. We also mechanism all formal results in the Coq proof assistant.

Session types- A family of type systems for message-passing concurrency-have been subject to many extensions, where each extension comes with a separate proof of type safety. These extensions cannot be readily combined, and their proofs of type safety are generally not machine checked, making their correctness less trustworthy. We overcome these shortcomings with a semantic approach to binary asynchronous affine session types, by developing a logical relations model in Coq using the Iris program logic. We demonstrate the power of our approach by combining various forms of polymorphism and recursion, asynchronous subtyping, references, and locks/mutexes. As an additional benefit of the semantic approach, we demonstrate how to manually prove typing judgements of racy, but safe, programs that cannot be type checked using only the rules of the type system.

Whenever a new software-verification technique is developed, additional effort is necessary to extend the new program analysis to an interprocedural one, such that it supports recursive procedures. We would like to reduce that additional effort. Our contribution is an approach to extend an existing analysis in a modular and domain-independent way to an interprocedural analysis without large changes: We present interprocedural block-abstraction memoization (BAM), which is a technique for procedure summarization to analyze (recursive) procedures. For recursive programs, a fix-point algorithm terminates the recursion if every procedure is sufficiently unrolled and summarized to cover the abstract state space. BAM Interprocedural works for data-flow analysis and for model checking, and is independent from the underlying abstract domain. To witness that our interprocedural analysis is generic and configurable, we defined and evaluated the approach for three completely different abstract domains: predicate abstraction, explicit values, and intervals. The interprocedural BAM-based analysis is implemented in the open-source verification framework CPAchecker. The evaluation shows that the overhead for modularity and domain-independence is not prohibitively large and the analysis is still competitive with other state-of-the-art software-verification tools.

The article describes a new and efficient algorithm for parsing, called Tunnel Parsing, that parses from left to right on the basis of a context-free grammar without left recursion and rules that recognize empty words. The algorithm is applicable mostly for domain-specific languages. In the article, particular attention is paid to the parsing of grammar element repetitions. As a result of the parsing, a statically typed concrete syntax tree is built from top to bottom, that accurately reflects the grammar. The parsing is not done through a recursion, but through an iteration. The Tunnel Parsing algorithm uses the grammars directly without a prior refactoring and is with a linear time complexity for deterministic context-free grammars.

The introduction of novel Datalog +/- fragments with good theoretical properties, together with the growing use of enterprise knowledge graphs motivated the development of Vadalog, a knowledge graph management system developed at the University of Oxford. It adopts Warded Datalog +/- as the core of its language for knowledge representation and reasoning, which exhibits a very good tradeoff between computational complexity of reasoning and expressive power, capturing PTIME data complexity while allowing ontological reasoning and full recursion. In this paper, we provide a detailed illustration of the Vadalog system, presenting: the essentials of the first implementation of Warded Datalog +/-; a comprehensive overview of the architecture with specific focus on runtime execution model, memory management, graph traversal strategies and join algorithms; and a detailed experimental evaluation. This paper is a substantially expanded version of the AMW 2019 paper “Datalog-based reasoning for Knowledge Graphs”. To stand apart from previous works on the topic, our focus in this work shall be a comprehensive presentation of the architecture of the Vadalog system and showing how our techniques work together to provide a full-fledged KGMS. In particular, roughly half of this paper is new material created particularly for this comprehensive architectural view. This includes a new series of experiments designed to shed light on architectural choices and alternatives.

This paper presents work in progress that focuses on querying transactional graph data that is stored in a relational database system (RDBMS). We focus on transactional workloads where there are frequent insert and update operations. Although these types of workloads are common in social network, scientific, and business applications, much of the prior work has focused on graph analytics workloads where there is little to no change to the data over time. We introduce an approach that combines simple database queries with parallel programming, and compare our approach to the recursive SQL operations that are known to have poor performance. Our initial experiments and results provide guidance for the future directions of this project where we will refine the parallel programing approach and structure of the experiment in order to better compare these two approaches.

This article discusses the construction of fractal equations, the classical set of Cantor and consisting of spirals based on theories of R-functions (RFM), using recursion procedures. According to the constructed equations, various prefractals can be generated depending on the number of iterations. All results are shown as a raster chart.

Recursive types extend the simply-typed lambda calculus (STLC) with the additional expressive power to enable diverging computation and to encode recursive data-types (e.g., lists). Two formulations of recursive types exist: iso-recursive and equi-recursive. The relative advantages of iso- and equi-recursion are well- studied when it comes to their impact on type-inference. However, the relative semantic expressiveness of the two formulations remains unclear so far. This paper studies the semantic expressiveness of STLC with iso- and equi-recursive types, proving that these formulations are equally expressive. In fact, we prove that they are both as expressive as STLC with only term-level recursion. We phrase these equi-expressiveness results in terms of full abstraction of three canonical compilers between these three languages (STLC with iso-, with equi-recursive types and with term-level recursion). Our choice of languages allows us to study expressiveness when interacting over both a simply-typed and a recursively-typed interface. The three proofs all rely on a typed version of a proof technique called approximate backtranslation. Together, our results show that there is no difference in semantic expressiveness between STLCs with iso- and equi-recursive types. In this paper, we focus on a simply-typed setting but we believe our results scale to more powerful type systems like System F.

We determine the optimal strategy for a family of lottery games involving repeated drawings with the same conditions, which includes Brazil's jogo do bicho and games typically offered by state lottery organizations in the United States under names such as Daily 4 or Cash 3. The proof that the strategy is optimal and the resulting formula for the probability of success both rely on a solution to a recursion that generalizes the usual Pascal recursion for binomial coefficients, which itself relies on a count of lattice paths. We illustrate how our result can be applied to focus on-the-ground investigations of suspicious patterns of lottery wins.

Session-types specify communication protocols for communicating processes, and session-typed languages are often specified using substructural operational semantics given by multiset rewriting systems. We give an observed communication semantics for a session-typed language with recursion, where a process's observation is given by its external communications. To do so, we introduce fair executions for multiset rewriting systems, and extract observed communications from fair process executions. This semantics induces an intuitively reasonable notion of observational equivalence that we conjecture coincides with semantic equivalences induced by denotational semantics, bisimulations, and barbed congruences for these languages., In Proceedings EXPRESS/SOS 2020, arXiv:2008.12414

All traditional growth-based pattern methods for sequential pattern mining can result recursively with length (k + 1) models on the basis of the given long-k pattern databases. In log2 (k + 1) recursion rates at best, you can detect a length-k pattern which leads to fewer recursion rates and quicker pattern development. Here we suggested a cloud-based strategy in the minimum moment and precision to obtain patterns. On the basis of the U.S. presidential candidate donations, the suggested method is implemented. These patterns are easily identified using Cloud Dataprep application from Google Cloud Platform. The time taken to generate the patterns is linear i.e., O(n).

We consider the problem of defining the integers in Homotopy Type Theory (HoTT). We can define the type of integers as signed natural numbers (i.e., using a coproduct), but its induction principle is very inconvenient to work with, since it leads to an explosion of cases. An alternative is to use set-quotients, but here we need to use set-truncation to avoid non-trivial higher equalities. This results in a recursion principle that only allows us to define function into sets (types satisfying UIP). In this paper we consider higher inductive types using either a small universe or bi-invertible maps. These types represent integers without explicit set-truncation that are equivalent to the usual coproduct representation. This is an interesting example since it shows how some coherence problems can be handled in HoTT. We discuss some open questions triggered by this work. The proofs have been formally verified using cubical Agda., 11 pages