Table space designs for implicit and explicit concurrent tabled evaluation

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Miguel Areias (Autor) FCUP; Ricardo Rocha (Autor) FCUP

Revista

Título: Theory and Practice of Logic Programming

Vol. 18

Páginas: 950-992

ISSN: 1471-0684

Editora: Cambridge University Press

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-00P-JMJ

DOI: 10.1017/s147106841800039x

Abstract (EN): One of the main advantages of Prolog is its potential for the implicit exploitation of parallelism and, as a high-level language, Prolog is also often used as a means to explicitly control concurrent tasks. Tabling is a powerful implementation technique that overcomes some limitations of traditional Prolog systems in dealing with recursion and redundant subcomputations. Given these advantages, the question that arises is if tabling has also the potential for the exploitation of concurrency/parallelism. On one hand, tabling still exploits a search space as traditional Prolog but, on the other hand, the concurrent model of tabling is necessarily far more complex, since it also introduces concurrency on the access to the tables. In this paper, we summarize Yap's main contributions to concurrent tabled evaluation and we describe the design and implementation challenges of several alternative table space designs for implicit and explicit concurrent tabled evaluation that represent different tradeoffs between concurrency and memory usage. We also motivate for the advantages of using fixed-size and lock freedata structures, elaborate on the key role that the engine's memory allocator plays on such environments, and discuss how Yap's mode-directed tabling support can be extended to concurrent evaluation. Finally, we present our future perspectives toward an efficient and novel concurrent framework which integrates both implicit and explicit concurrent tabled evaluation in a single Prolog engine.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 43