1,613 results on '"Recursion"'
Search Results
2. Learning to Compose and Reason with Language Tree Structures for Visual Grounding
- Author
-
Hanwang Zhang, Xiaoyu Mo, Xiangnan He, Richang Hong, Daqing Liu, School of Computer Science and Engineering, and School of Electrical and Electronic Engineering
- Subjects
FOS: Computer and information sciences ,Computer science ,Computer Vision and Pattern Recognition (cs.CV) ,Tree Structure ,Computer Science - Computer Vision and Pattern Recognition ,02 engineering and technology ,computer.software_genre ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,Humans ,Learning ,Language ,Parsing ,Recursion ,Binary tree ,business.industry ,Applied Mathematics ,Cognition ,Visual reasoning ,Fine-Grained Detection ,Visualization ,Tree structure ,Computational Theory and Mathematics ,Electrical and electronic engineering [Engineering] ,Computer science and engineering [Engineering] ,020201 artificial intelligence & image processing ,Computer Vision and Pattern Recognition ,Artificial intelligence ,business ,computer ,Algorithms ,Software ,Natural language - Abstract
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)
- Published
- 2022
3. Newly-single and loving it: improving higher-order must-alias analysis with heap fragments
- Author
-
Jay McCarthy and Kimball Germane
- Subjects
Recursion ,Computer science ,Programming language ,Thread (computing) ,Conflation ,computer.software_genre ,Alias analysis ,Sketch ,Control flow analysis ,Resource (project management) ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Safety, Risk, Reliability and Quality ,computer ,Software ,Heap (data structure) - Abstract
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.
- Published
- 2021
4. Expressiveness within Sequence Datalog
- Author
-
Jan Paredaens, Heba Aamer, Jan Hidders, and Jan Van den Bussche
- Subjects
FOS: Computer and information sciences ,Sequence ,Theoretical computer science ,Recursion ,Computer science ,Redundancy (linguistics) ,Context (language use) ,Databases (cs.DB) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Path expression ,Datalog ,Negation ,Computer Science - Databases ,010201 computation theory & mathematics ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,computer ,computer.programming_language - Abstract
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
- Published
- 2022
5. Type Inference of Simple Recursive Functions in Scala
- Author
-
Zoltán Porkoláb, Gábor Oláh, and Gergely Nagy
- Subjects
0209 industrial biotechnology ,Information Systems and Management ,Correctness ,Scala ,Computer science ,0102 computer and information sciences ,02 engineering and technology ,Management Science and Operations Research ,computer.software_genre ,01 natural sciences ,Theoretical Computer Science ,020901 industrial engineering & automation ,Computer Science (miscellaneous) ,Electrical and Electronic Engineering ,Programmer ,computer.programming_language ,Recursion ,Programming language ,Heuristic ,Type inference ,Return type ,010201 computation theory & mathematics ,Computer Vision and Pattern Recognition ,Compiler ,Software_PROGRAMMINGLANGUAGES ,computer ,Software - Abstract
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.
- Published
- 2020
6. Strong functional pearl: Harper’s regular-expression matcher in Cedille
- Author
-
Aaron Stump, Colin McDonald, Stephan Spahn, and Christopher Jenkins
- Subjects
Recursion ,Programming language ,Interface (Java) ,Computer science ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,Mathematical proof ,01 natural sciences ,Continuation ,PEARL (programming language) ,010201 computation theory & mathematics ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,0202 electrical engineering, electronic engineering, information engineering ,Code (cryptography) ,Regular expression ,Safety, Risk, Reliability and Quality ,computer ,Software ,Universe (mathematics) ,computer.programming_language - Abstract
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.
- Published
- 2020
7. O DEBATE EVOLUTIVO É RELEVANTE PARA A LINGUÍSTICA?
- Author
-
Elena Godoy and Maurício Fernandes Neves Benfatti
- Subjects
Statement (computer science) ,Nonverbal communication ,Recursion ,Empirical research ,Selection (linguistics) ,Natural (music) ,Sociology ,Minimalist program ,computer.software_genre ,computer ,Epistemology ,Syntax (logic) - Abstract
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.
- Published
- 2020
8. Recursion Enhanced Random Forest With an Improved Linear Model (RERF-ILM) for Heart Disease Detection on the Internet of Medical Things Platform
- Author
-
Chunyan Guo, Jiabing Zhang, Yang Liu, Yaying Xie, Zhiqiang Han, and Jianshe Yu
- Subjects
General Computer Science ,Heart disease ,diagnosis ,Computer science ,Stability (learning theory) ,02 engineering and technology ,Disease ,Machine learning ,computer.software_genre ,Coronary artery disease ,0202 electrical engineering, electronic engineering, information engineering ,medicine ,General Materials Science ,Recursion ,business.industry ,Deep learning ,020208 electrical & electronic engineering ,General Engineering ,Linear model ,Heart disease detection ,medicine.disease ,Random forest ,linear model ,machine learning ,020201 artificial intelligence & image processing ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,Artificial intelligence ,business ,lcsh:TK1-9971 ,computer ,random forest - Abstract
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.
- Published
- 2020
9. Tapir
- Author
-
William S. Moses, Tao B. Schardl, and Charles E. Leiserson
- Subjects
Computer science ,Optimizing compiler ,02 engineering and technology ,Cilk ,Fork–join queue ,computer.software_genre ,01 natural sciences ,Control flow ,biology.animal ,0103 physical sciences ,0202 electrical engineering, electronic engineering, information engineering ,computer.programming_language ,010302 applied physics ,020203 distributed computing ,Intermediate language ,Multi-core processor ,Recursion ,biology ,Programming language ,computer.file_format ,Computer Science Applications ,Loop scheduling ,Computational Theory and Mathematics ,Hardware and Architecture ,Modeling and Simulation ,Control flow graph ,Executable ,Compiler ,Software_PROGRAMMINGLANGUAGES ,Tapir ,computer ,Software - Abstract
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.
- Published
- 2019
10. A proof-theoretic study of abstract termination principles
- Author
-
Thomas Powell
- Subjects
Recursion ,Logic ,Bar (music) ,Carry (arithmetic) ,010102 general mathematics ,0102 computer and information sciences ,01 natural sciences ,Theoretical Computer Science ,Term (time) ,Algebra ,Arts and Humanities (miscellaneous) ,010201 computation theory & mathematics ,Hardware and Architecture ,Path (graph theory) ,Gödel ,0101 mathematics ,computer ,Software ,computer.programming_language ,Mathematics - Abstract
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.
- Published
- 2019
11. Simplifying the Structural Recursion of the Data Funnel Interface
- Author
-
H. Paul Zellweger
- Subjects
Recursion ,Computer science ,business.industry ,Interface (computing) ,computer.software_genre ,Data mapping ,Data modeling ,Data visualization ,Numbering scheme ,Data model ,Table (database) ,Data mining ,business ,computer - Abstract
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.
- Published
- 2021
12. Supermartingales, Ranking Functions and Probabilistic Lambda Calculus
- Author
-
Andrew Kenyon-Roberts and C.-H. Luke Ong
- Subjects
Range (mathematics) ,Functional programming ,Recursion ,Theoretical computer science ,Computer science ,Probabilistic logic ,Context (language use) ,Function (mathematics) ,Lambda calculus ,computer ,Ranking (information retrieval) ,computer.programming_language - Abstract
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.
- Published
- 2021
13. One WITH RECURSIVE is Worth Many GOTOs
- Author
-
Denis Hirn and Torsten Grust
- Subjects
SQL ,Recursion ,Programming language ,Computer science ,Data_MISCELLANEOUS ,InformationSystems_DATABASEMANAGEMENT ,PL/SQL ,computer.software_genre ,Control flow ,Factor (programming language) ,Table (database) ,Compiler ,computer ,computer.programming_language - Abstract
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.
- Published
- 2021
14. Is Word-Level Recursion Actually Recursion?
- Author
-
Taylor L. Miller and Hannah Sande
- Subjects
recursive word ,050101 languages & linguistics ,Linguistics and Language ,Phrase ,Structure (category theory) ,computer.software_genre ,Kaqchikel ,Language and Linguistics ,030507 speech-language pathology & audiology ,03 medical and health sciences ,prosody ,recursion ,0501 psychology and cognitive sciences ,Subcategorization ,Prosody ,Mathematics ,Recursion ,business.industry ,Group (mathematics) ,Language and Literature ,05 social sciences ,Phonology ,Blackfoot ,Artificial intelligence ,0305 other medical science ,business ,computer ,Natural language processing ,Word (group theory) - Abstract
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.
- Published
- 2021
- Full Text
- View/download PDF
15. Actions You Can Handle: Dependent Types for AI Plans
- Author
-
Ronald P. A. Petrick, Matthew L. Daggitt, Ekaterina Komendantskaya, and Alasdair Hill
- Subjects
FOS: Computer and information sciences ,I.2 ,Recursion ,Computer Science - Programming Languages ,Syntax (programming languages) ,Programming language ,Agda ,Computer science ,Computer Science - Artificial Intelligence ,D.3 ,68Q60, 03B38, 68T27, 03B70 ,Autonomous agent ,F.3 ,F.4 ,Plan (drawing) ,computer.software_genre ,Decidability ,Set (abstract data type) ,Artificial Intelligence (cs.AI) ,Search algorithm ,computer ,Programming Languages (cs.PL) ,computer.programming_language - Abstract
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
- Published
- 2021
16. Distributional learning of recursive structures
- Author
-
Kathryn Schuler and Daoxin Li
- Subjects
Structure (mathematical logic) ,Recursion ,Series (mathematics) ,business.industry ,Computer science ,cognitive science ,Artificial language learning ,computer.software_genre ,Genitive case ,Position (vector) ,Embedding ,Artificial intelligence ,business ,Set (psychology) ,computer ,Natural language processing - Abstract
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.
- Published
- 2021
17. Computational Restrictions on Interative Prosodic Processes
- Author
-
Hossep Dolatian, Kristina Strother-Garcia, Jonathan Rawski, and Nate Koser
- Subjects
Iterative and incremental development ,Recursion ,business.industry ,Syllabification ,Computer science ,Phonology ,Secondary stress ,computer.software_genre ,Focus (linguistics) ,General Earth and Planetary Sciences ,Artificial intelligence ,Prosody ,business ,computer ,Natural language processing ,Epenthesis ,General Environmental Science - Abstract
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.
- Published
- 2021
18. BigData Applications from Graph Analytics to Machine Learning by Aggregates in Recursion
- Author
-
Jin Wang, Carlo Zaniolo, Mingda Li, Ariyam Das, and Youfu Li
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Computer Science - Machine Learning ,SQL ,Computer science ,Semantics (computer science) ,Formal semantics (linguistics) ,Machine learning ,computer.software_genre ,lcsh:QA75.5-76.95 ,Operational semantics ,Machine Learning (cs.LG) ,Datalog ,Prolog ,Computer Science - Databases ,computer.programming_language ,Recursion ,business.industry ,lcsh:Mathematics ,Databases (cs.DB) ,lcsh:QA1-939 ,Logic in Computer Science (cs.LO) ,Scalability ,lcsh:Electronic computers. Computer science ,Artificial intelligence ,business ,computer - Abstract
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)
- Published
- 2019
19. Relating Two Dialects of Answer Set Programming
- Author
-
Amelia Harrison and Vladimir Lifschitz
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Computer science ,Semantics (computer science) ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,Theoretical Computer Science ,Set (abstract data type) ,Answer set programming ,Artificial Intelligence ,0202 electrical engineering, electronic engineering, information engineering ,Equivalence (measure theory) ,Logic programming ,Recursion ,Programming language ,Solver ,Logic in Computer Science (cs.LO) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Hardware and Architecture ,020201 artificial intelligence & image processing ,computer ,Software ,Stable model semantics - Abstract
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
- Published
- 2019
20. People Infer Recursive Visual Concepts from Just a Few Examples
- Author
-
Steven Piantadosi and Brenden M. Lake
- Subjects
Recursion ,Artificial neural network ,business.industry ,Computer science ,Cognitive neuroscience of visual object recognition ,Space (commercial competition) ,Machine learning ,computer.software_genre ,Bayesian inference ,Variable (computer science) ,Neuropsychology and Physiological Psychology ,Concept learning ,Developmental and Educational Psychology ,Artificial intelligence ,business ,computer ,Causal model - Abstract
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.
- Published
- 2019
21. Inclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable
- Author
-
Naoki Kobayashi
- Subjects
Scheme (programming language) ,Reduction (recursion theory) ,Recursion ,General Computer Science ,Computer science ,Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) ,Dyck language ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Theoretical Computer Science ,Undecidable problem ,Algebra ,Indexed language ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Rule-based machine translation ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Computer Science::Programming Languages ,020201 artificial intelligence & image processing ,computer ,Computer Science::Formal Languages and Automata Theory ,computer.programming_language - Abstract
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.
- Published
- 2019
22. Intensional computation with higher-order functions
- Author
-
Barry Jay
- Subjects
Structure (mathematical logic) ,Recursion ,General Computer Science ,Computer science ,Programming language ,Proof assistant ,Gödel's incompleteness theorems ,Term (logic) ,computer.software_genre ,Extensional definition ,Computation Theory & Mathematics ,Theoretical Computer Science ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Program analysis ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Rewriting ,Combinatory logic ,computer ,Halting problem - Abstract
© 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.
- Published
- 2019
23. Recursion in action: An fMRI study on the generation of new hierarchical levels in motor sequences
- Author
-
Roberta Bianco, Daniela Sammler, Arno Villringer, and Mauricio Martins
- Subjects
Adult ,Male ,Computer science ,Short-term memory ,hierarchy ,Motor Activity ,Serial Learning ,computer.software_genre ,050105 experimental psychology ,03 medical and health sciences ,Young Adult ,0302 clinical medicine ,Motor imagery ,recursion ,Feature (machine learning) ,Humans ,0501 psychology and cognitive sciences ,Radiology, Nuclear Medicine and imaging ,Prefrontal cortex ,Research Articles ,prefrontal cortex ,Brain Mapping ,Parsing ,Recursion ,Radiological and Ultrasound Technology ,business.industry ,05 social sciences ,fMRI ,Pattern recognition ,Cognition ,Magnetic Resonance Imaging ,motor ,Transformation (function) ,Memory, Short-Term ,Neurology ,Imagination ,Female ,Neurology (clinical) ,Artificial intelligence ,Anatomy ,Nerve Net ,business ,computer ,030217 neurology & neurosurgery ,Psychomotor Performance ,Research Article - Abstract
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.
- Published
- 2019
24. Practical Subtyping for Curry-Style Languages
- Author
-
Christophe Raffalli and Rodolphe Lepigre
- Subjects
Recursion ,Computer science ,Programming language ,Coinduction ,020207 software engineering ,02 engineering and technology ,Product type ,Mathematical proof ,computer.software_genre ,Subtyping ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,computer ,Software ,Quicksort - Abstract
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.
- Published
- 2019
25. Representations and Optimizations for Embedded Parallel Dataflow Languages
- Author
-
Volker Markl, Alexander Alexandrov, and Georgi Krastev
- Subjects
SQL ,Source code ,Java ,Scala ,Dataflow ,Computer science ,media_common.quotation_subject ,02 engineering and technology ,computer.software_genre ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Programmer ,computer.programming_language ,media_common ,Intermediate language ,Recursion ,Programming language ,Method chaining ,020207 software engineering ,Python (programming language) ,Monad (functional programming) ,XQuery ,Programming paradigm ,Compiler ,computer ,Information Systems - Abstract
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.
- Published
- 2019
26. GLL syntax analysers for EBNF grammars
- Author
-
Adrian Johnstone and Elizabeth Scott
- Subjects
Parsing ,Recursion ,Grammar ,Syntax (programming languages) ,Computer science ,Programming language ,media_common.quotation_subject ,Parse tree ,020207 software engineering ,0102 computer and information sciences ,02 engineering and technology ,Recursive descent parser ,computer.software_genre ,01 natural sciences ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Rule-based machine translation ,010201 computation theory & mathematics ,Formal specification ,0202 electrical engineering, electronic engineering, information engineering ,computer ,Software ,media_common - Abstract
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.
- Published
- 2018
27. Rec.HTML: Declarative HTML
- Author
-
Bob Reynders and Kwanghoon Choi
- Subjects
Functional programming ,Recursion ,Programming language ,Event (computing) ,Computer science ,Interface (Java) ,media_common.quotation_subject ,computer.software_genre ,Reading (process) ,Programming paradigm ,State (computer science) ,computer ,Declarative programming ,media_common - Abstract
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.
- Published
- 2021
28. Smart Factory and the Unique Digital Order Twin
- Author
-
Hartmut Zadek and Wilmjakob Johannes Herlyn
- Subjects
Focus (computing) ,Recursion ,Exploit ,Computer science ,business.industry ,Final product ,Automotive industry ,Product (business) ,PEARL (programming language) ,Order (business) ,Software engineering ,business ,computer ,computer.programming_language - Abstract
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.
- Published
- 2021
29. RL-GRIT: Reinforcement Learning for Grammar Inference
- Author
-
Walt Woods
- Subjects
Structure (mathematical logic) ,FOS: Computer and information sciences ,Computer Science - Machine Learning ,Computer Science - Cryptography and Security ,Computer Science - Programming Languages ,Parsing ,Recursion ,Computer science ,business.industry ,computer.software_genre ,JSON ,Machine Learning (cs.LG) ,Set (abstract data type) ,Regular language ,Reinforcement learning ,Artificial intelligence ,business ,computer ,Cryptography and Security (cs.CR) ,Natural language ,Natural language processing ,computer.programming_language ,Programming Languages (cs.PL) - Abstract
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
- Published
- 2021
- Full Text
- View/download PDF
30. Practical Aspects of Declarative Languages
- Author
-
Bhargav Shivkumar, Enrique Naudon, and Lukasz Ziarek
- Subjects
Functional programming ,Recursion ,Computer science ,Programming language ,Work (physics) ,Type inference ,Gradual typing ,Type system ,computer.software_genre ,Representation (mathematics) ,Implementation ,computer - Abstract
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.
- Published
- 2021
31. A practical mode system for recursive definitions
- Author
-
Gabriel Scherer, Alban Reynaud, Jeremy Yallop, Apollo - University of Cambridge Repository, École normale supérieure de Lyon (ENS de Lyon), Automatisation et ReprésenTation: fOndation du calcUl et de la déducTion (PARTOUT), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Cambridge [UK] (CAM), École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, and Department of Computer Science and Technology, University of Cambridge, Cambridge, UK
- Subjects
FOS: Computer and information sciences ,Semantics (computer science) ,Computer science ,functional programming ,0102 computer and information sciences ,02 engineering and technology ,computer.software_genre ,01 natural sciences ,Set (abstract data type) ,call-by-value ,recursion ,0202 electrical engineering, electronic engineering, information engineering ,types ,Safety, Risk, Reliability and Quality ,Rule of inference ,semantics ,Soundness ,Functional programming ,Computer Science - Programming Languages ,[INFO.INFO-PL]Computer Science [cs]/Programming Languages [cs.PL] ,Recursion ,Programming language ,Static analysis ,Data structure ,ML ,010201 computation theory & mathematics ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,020201 artificial intelligence & image processing ,computer ,Software ,Programming Languages (cs.PL) - Abstract
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
- Published
- 2021
32. Splitting recursion schemes into reversible and classical interacting threads
- Author
-
Armando B. Matos, Luca Roversi, and Luca Paolini
- Subjects
Scheme (programming language) ,FOS: Computer and information sciences ,Computer Science - Programming Languages ,Recursion ,Simple (abstract algebra) ,Computer science ,Recursive functions ,Order (ring theory) ,computer ,Algorithm ,computer.programming_language ,Programming Languages (cs.PL) - Abstract
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
- Published
- 2021
- Full Text
- View/download PDF
33. Vertical Federated Learning for Higher-Order Factorization Machines
- Author
-
Masakazu Ishihata and Kyohei Atarashi
- Subjects
Recursion ,Point (typography) ,Computer science ,business.industry ,Feature vector ,Collaborative learning ,Recommender system ,Machine learning ,computer.software_genre ,Feature (machine learning) ,Artificial intelligence ,Raw data ,Cluster analysis ,business ,computer - Abstract
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 .
- Published
- 2021
34. Towards Expectation-Maximization by SQL in RDBMS
- Author
-
Junzhou Huang, Jeffrey Xu Yu, Ming Liao, Kangfei Zhao, and Yu Rong
- Subjects
050101 languages & linguistics ,SQL ,Recursion ,Computer science ,business.industry ,05 social sciences ,Probabilistic logic ,InformationSystems_DATABASEMANAGEMENT ,02 engineering and technology ,Relational algebra ,Machine learning ,computer.software_genre ,Automatic summarization ,Relational database management system ,Expectation–maximization algorithm ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,0501 psychology and cognitive sciences ,Artificial intelligence ,Cluster analysis ,business ,computer ,computer.programming_language - Abstract
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.
- Published
- 2021
35. Translating Lambda Calculus into C++ Templates
- Author
-
Vít Šefl
- Subjects
Generic programming ,Recursion ,Semantics (computer science) ,Computer science ,Programming language ,computer.software_genre ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Template ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Algebraic data type ,Compiler ,Variety (universal algebra) ,Lambda calculus ,computer ,computer.programming_language - Abstract
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.
- Published
- 2021
36. On Adding Pattern Matching to Haskell-Based Deeply Embedded Domain Specific Languages
- Author
-
Andy Gill, David Young, and Mark Grebe
- Subjects
050101 languages & linguistics ,Domain-specific language ,Recursion ,Computer science ,Programming language ,05 social sciences ,02 engineering and technology ,computer.software_genre ,Control flow ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,0501 psychology and cognitive sciences ,Haskell ,Compiler ,Pattern matching ,Programmer ,Combinatory logic ,computer ,computer.programming_language - Abstract
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.
- Published
- 2021
37. Commutative Monads for Probabilistic Programming Languages
- Author
-
Michael W. Mislove, Bert Lindenhovius, Vladimir Zamdzhiev, Xiaodong Jia, Hunan University [Changsha] (HNU), Johannes Kepler Universität Linz (JKU), Tulane University, Designing the Future of Computational Models (MOCQUA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), and Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
FOS: Computer and information sciences ,Computer Science - Logic in Computer Science ,Complete partial order ,Computer science ,Semantics (computer science) ,0102 computer and information sciences ,computer.software_genre ,01 natural sciences ,Denotational semantics ,Computer Science::Logic in Computer Science ,Mathematics::Category Theory ,FOS: Mathematics ,Category Theory (math.CT) ,0101 mathematics ,Commutative property ,ComputingMilieux_MISCELLANEOUS ,computer.programming_language ,Probabilistic logic ,Recursion ,Computer Science - Programming Languages ,Calculus ,Programming language ,010102 general mathematics ,[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] ,Mathematics - Category Theory ,Cost accounting ,Monad (functional programming) ,Semantics ,Logic in Computer Science (cs.LO) ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,010201 computation theory & mathematics ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Lambda calculus ,computer ,Computer languages ,Programming Languages (cs.PL) - Abstract
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.
- Published
- 2021
- Full Text
- View/download PDF
38. Reasoning About Iteration and Recursion Uniformly Based on Big-Step Semantics
- Author
-
Zhiping Shi, Yong Guan, Qianying Zhang, Guohui Wang, and Ximeng Li
- Subjects
Soundness ,Recursion ,Computer science ,Semantics (computer science) ,Programming language ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Completeness (logic) ,Proof assistant ,Mathematical proof ,computer.software_genre ,computer ,Operational semantics - Abstract
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.
- Published
- 2021
39. Machine-Checked Semantic Session Typing
- Author
-
Hinrichsen, Jonas Kastberg, Louwrink, Daniël, Krebbers, R.J., Bengtson, Jesper, Hritcu, Catalin, Popescu, Andrei, and Hritcu, C.
- Subjects
Separation logic ,Correctness ,Recursion ,Computer science ,Programming language ,Concurrency ,Session types ,Iris ,020207 software engineering ,02 engineering and technology ,computer.software_genre ,Mathematical proof ,Message passing ,Asynchronous communication ,020204 information systems ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Type safety ,Software Science ,0202 electrical engineering, electronic engineering, information engineering ,Coq ,Session (computer science) ,computer ,Semantic typing - Abstract
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.
- Published
- 2021
40. Domain-independent interprocedural program analysis using block-abstraction memoization
- Author
-
Karlheinz Friedberger and Dirk Beyer
- Subjects
Model checking ,Recursion ,Predicate abstraction ,Program analysis ,Programming language ,Computer science ,Memoization ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,computer.software_genre ,CPAchecker ,computer ,Software verification ,Abstraction (linguistics) - Abstract
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.
- Published
- 2020
41. Theory and Praxis
- Author
-
Elliot Murphy
- Subjects
Hierarchy ,Praxis ,Recursion ,Syntax (programming languages) ,Programming language ,Computer science ,media_common.quotation_subject ,computer.software_genre ,Semantics ,computer ,media_common - Published
- 2020
42. Tunnel Parsing with counted repetitions
- Author
-
Elena Somova and Nikolay Handzhiyski
- Subjects
Computer Networks and Communications ,Left recursion ,Computer science ,media_common.quotation_subject ,computer.software_genre ,Rule-based machine translation ,Artificial Intelligence ,Computer Science (miscellaneous) ,Time complexity ,media_common ,Parsing ,Recursion ,Grammar ,business.industry ,Computer Graphics and Computer-Aided Design ,Tree (data structure) ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Concrete syntax ,Computational Theory and Mathematics ,Code refactoring ,Modeling and Simulation ,Computer Vision and Pattern Recognition ,Artificial intelligence ,business ,computer ,Natural language processing - Abstract
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.
- Published
- 2020
43. Vadalog: A modern architecture for automated reasoning with large knowledge graphs
- Author
-
Luigi Bellomarini, Georg Gottlob, Emanuel Sallinger, and Davide Benedetto
- Subjects
Recursion ,Computational complexity theory ,Knowledge representation and reasoning ,Programming language ,Computer science ,02 engineering and technology ,computer.software_genre ,Datalog ,Memory management ,Knowledge graph ,Hardware and Architecture ,020204 information systems ,Graph traversal ,0202 electrical engineering, electronic engineering, information engineering ,Ontology ,020201 artificial intelligence & image processing ,Automated reasoning ,Execution model ,computer ,Software ,Information Systems ,computer.programming_language - Abstract
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.
- Published
- 2022
44. Moving Recursion Out of the RDBMS for Transactional Graph Workloads
- Author
-
Matthew Clark and Christine F. Reilly
- Subjects
SQL ,Theoretical computer science ,Recursion ,Computer science ,05 social sciences ,050301 education ,02 engineering and technology ,computer.file_format ,computer.software_genre ,Transactional leadership ,Relational database management system ,Server ,0202 electrical engineering, electronic engineering, information engineering ,Graph (abstract data type) ,020201 artificial intelligence & image processing ,RDF ,0503 education ,computer ,computer.programming_language - Abstract
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.
- Published
- 2020
45. An Algorithm for Constructing Equations of Geometry Fractals Based on Theories of R-functions
- Author
-
Golib Berdiev, Zulaykho Ibrokhimova, and Shahzoda Anarova
- Subjects
Set (abstract data type) ,Algebra ,Recursion ,Fractal ,Chart ,computer.file_format ,Raster graphics ,computer ,Mathematics - Abstract
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.
- Published
- 2020
46. On the Semantic Expressiveness of Recursive Types
- Author
-
Dominique Devriese, Marco Patrignani, Eric Mark Martin, Informatics and Applied Informatics, and Software Languages Lab
- Subjects
Phrase ,Theoretical computer science ,Interface (Java) ,Computer science ,Backtranslation ,Coinductive Equi-recursive types ,Fully-abstract compilation ,Iso-recursive types ,Lambda Calculus ,Recursive types ,cs.PL ,02 engineering and technology ,Type (model theory) ,computer.software_genre ,Mathematical proof ,GeneralLiterature_MISCELLANEOUS ,020204 information systems ,0202 electrical engineering, electronic engineering, information engineering ,Safety, Risk, Reliability and Quality ,GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries) ,Abstraction (linguistics) ,computer.programming_language ,Recursion ,020207 software engineering ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,ComputingMilieux_COMPUTERSANDSOCIETY ,Compiler ,Lambda calculus ,computer ,Software - Abstract
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.
- Published
- 2020
47. Optimal Play for Multiple Lottery Wins
- Author
-
Richard Stong and Skip Garibaldi
- Subjects
Focus (computing) ,Recursion ,Applied Mathematics ,media_common.quotation_subject ,Pascal (programming language) ,State (functional analysis) ,Theoretical Computer Science ,Probability of success ,Combinatorics ,Lottery ,Computational Theory and Mathematics ,Cash ,Discrete Mathematics and Combinatorics ,Geometry and Topology ,computer ,Mathematical economics ,Binomial coefficient ,Mathematics ,computer.programming_language ,media_common - Abstract
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.
- Published
- 2020
48. Substructural Observed Communication Semantics
- Author
-
Ryan Kavanagh
- Subjects
FOS: Computer and information sciences ,Conjecture ,Recursion ,Computer Science - Programming Languages ,Computer science ,Semantics (computer science) ,Programming language ,Congruence relation ,computer.software_genre ,Operational semantics ,Denotational semantics ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS ,Observational equivalence ,Communications protocol ,computer ,Programming Languages (cs.PL) - Abstract
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
- Published
- 2020
49. Sequential Pattern Mining for the U.S. Presidential Elections Using Google Cloud Platform (GCP)
- Author
-
G. Madhukar, K. N. S. S. S. Srinivas, B. Kavitha Rani, and M. Varaprasad Rao
- Subjects
Moment (mathematics) ,Recursion ,Basis (linear algebra) ,Computer science ,business.industry ,Cloud computing ,Data mining ,Pattern matching ,Sequential Pattern Mining ,computer.software_genre ,business ,Time complexity ,computer - Abstract
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).
- Published
- 2020
50. The Integers as a Higher Inductive Type
- Author
-
Luis Scoccola and Thorsten Altenkirch
- Subjects
FOS: Computer and information sciences ,Discrete mathematics ,Computer Science - Logic in Computer Science ,Recursion ,Agda ,020207 software engineering ,Natural number ,Mathematics - Logic ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,Mathematical proof ,01 natural sciences ,Logic in Computer Science (cs.LO) ,010201 computation theory & mathematics ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Homotopy type theory ,Inductive type ,Logic (math.LO) ,computer ,Universe (mathematics) ,computer.programming_language ,Mathematics - Abstract
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
- Published
- 2020
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.