A Simple and Efficient Implementation of Concurrent Local Tabling

Rui Filipe Pereira Marques; José Alberto Cardoso E Cunha

doi:10.1007/978-3-642-11503-5_22

A Simple and Efficient Implementation of Concurrent Local Tabling

Rui Filipe Pereira Marques, José Alberto Cardoso E Cunha

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

8 Citations (Scopus)

Abstract

Newer Prolog implementations commonly offer support for multi-threading, and many also offer support for tabling. However, most implementations do not yet integrate tabling with multi-threading, and in particular do not support the sharing of a tabled computation among threads. In this paper we present algorithms to share completed tables among threads based on Concurrent Local SLG evaluation (SLG(CL)). SLG(CL) is based on the Local scheduling strategy, and is designed to support applications in which threads concurrently share tabled evaluations. Version 3.2 of XSB implements SLG(CL) in the SLG(CL)WAM, which fully supports well-founded tabled negation, construction of residual programs, tabled constraints and answer subsumption. The implementation of SLG(CL) requires significant additions to a single tabling operation only. As a result. SLG(CL) should be implementable by any tabling systems that uses Local evaluation based on the SLG-WAM or Chat engine, and may also be applicable to those using linear tabling.

Original language	Unknown
Title of host publication	Lecture Notes in Computer Science
Pages	264-278
DOIs	https://doi.org/10.1007/978-3-642-11503-5_22
Publication status	Published - 1 Jan 2010
Event	International Symposium on Practical Aspects of Declarative Languages (PADL) - Duration: 1 Jan 2010 → …

Conference

Conference	International Symposium on Practical Aspects of Declarative Languages (PADL)
Period	1/01/10 → …

Access to Document

10.1007/978-3-642-11503-5_22

Cite this

@inproceedings{ab3cfd4d1f464256b3586adf232dfd09,

title = "A Simple and Efficient Implementation of Concurrent Local Tabling",

abstract = "Newer Prolog implementations commonly offer support for multi-threading, and many also offer support for tabling. However, most implementations do not yet integrate tabling with multi-threading, and in particular do not support the sharing of a tabled computation among threads. In this paper we present algorithms to share completed tables among threads based on Concurrent Local SLG evaluation (SLG(CL)). SLG(CL) is based on the Local scheduling strategy, and is designed to support applications in which threads concurrently share tabled evaluations. Version 3.2 of XSB implements SLG(CL) in the SLG(CL)WAM, which fully supports well-founded tabled negation, construction of residual programs, tabled constraints and answer subsumption. The implementation of SLG(CL) requires significant additions to a single tabling operation only. As a result. SLG(CL) should be implementable by any tabling systems that uses Local evaluation based on the SLG-WAM or Chat engine, and may also be applicable to those using linear tabling.",

author = "Marques, {Rui Filipe Pereira} and Cunha, {Jos{\'e} Alberto Cardoso E}",

year = "2010",

month = jan,

day = "1",

doi = "10.1007/978-3-642-11503-5_22",

language = "Unknown",

isbn = "978-3-642-11502-8",

pages = "264--278",

booktitle = "Lecture Notes in Computer Science",

note = "International Symposium on Practical Aspects of Declarative Languages (PADL) ; Conference date: 01-01-2010",

}

TY - GEN

T1 - A Simple and Efficient Implementation of Concurrent Local Tabling

AU - Marques, Rui Filipe Pereira

AU - Cunha, José Alberto Cardoso E

PY - 2010/1/1

Y1 - 2010/1/1

N2 - Newer Prolog implementations commonly offer support for multi-threading, and many also offer support for tabling. However, most implementations do not yet integrate tabling with multi-threading, and in particular do not support the sharing of a tabled computation among threads. In this paper we present algorithms to share completed tables among threads based on Concurrent Local SLG evaluation (SLG(CL)). SLG(CL) is based on the Local scheduling strategy, and is designed to support applications in which threads concurrently share tabled evaluations. Version 3.2 of XSB implements SLG(CL) in the SLG(CL)WAM, which fully supports well-founded tabled negation, construction of residual programs, tabled constraints and answer subsumption. The implementation of SLG(CL) requires significant additions to a single tabling operation only. As a result. SLG(CL) should be implementable by any tabling systems that uses Local evaluation based on the SLG-WAM or Chat engine, and may also be applicable to those using linear tabling.

AB - Newer Prolog implementations commonly offer support for multi-threading, and many also offer support for tabling. However, most implementations do not yet integrate tabling with multi-threading, and in particular do not support the sharing of a tabled computation among threads. In this paper we present algorithms to share completed tables among threads based on Concurrent Local SLG evaluation (SLG(CL)). SLG(CL) is based on the Local scheduling strategy, and is designed to support applications in which threads concurrently share tabled evaluations. Version 3.2 of XSB implements SLG(CL) in the SLG(CL)WAM, which fully supports well-founded tabled negation, construction of residual programs, tabled constraints and answer subsumption. The implementation of SLG(CL) requires significant additions to a single tabling operation only. As a result. SLG(CL) should be implementable by any tabling systems that uses Local evaluation based on the SLG-WAM or Chat engine, and may also be applicable to those using linear tabling.

U2 - 10.1007/978-3-642-11503-5_22

DO - 10.1007/978-3-642-11503-5_22

M3 - Conference contribution

SN - 978-3-642-11502-8

SP - 264

EP - 278

BT - Lecture Notes in Computer Science

T2 - International Symposium on Practical Aspects of Declarative Languages (PADL)

Y2 - 1 January 2010

ER -