License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICLP.2017.10
URN: urn:nbn:de:0030-drops-84537
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8453/
Go to the corresponding OASIcs Volume Portal

Tarau, Paul

A Hitchhiker's Guide to Reinventing a Prolog Machine

pdf-format:
OASIcs-ICLP-2017-10.pdf (0.4 MB)

Abstract

We take a fresh, "clean-room" look at implementing Prolog by deriving its translation to an executable representation
and its execution algorithm from a simple Horn Clause meta-interpreter.

The resulting design has some interesting properties.
The heap representation of terms and the abstract machine instruction encodings are the same.
No dedicated code area is used as the code is placed directly on the heap.
Unification and indexing operations are orthogonal.
Filtering of matching clauses happens without building new structures on the heap.
Variables in function and predicate symbol positions are handled with no performance penalty.
A simple English-like syntax is used as an intermediate representation for clauses and goals and
the same simple syntax can be used by programmers directly as an alternative to classic Prolog syntax.
Solutions of (multiple) logic engines are exposed as answer streams
that can be combined through typical functional programming patterns,
with flexibility to stop, resume, encapsulate and interleave executions.
Performance of a basic interpreter implementing our design is within a factor of 2 of a highly optimized compiled
WAM-based system using the same host language.

To help placing our design on the fairly rich map of Prolog systems, we discuss similarities
to existing Prolog abstract machines, with emphasis on separating necessary
commonalities from arbitrary implementation choices.

BibTeX - Entry

@InProceedings{tarau:OASIcs:2018:8453,
  author =	{Paul Tarau},
  title =	{{A Hitchhiker's Guide to Reinventing a Prolog Machine}},
  booktitle =	{Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)},
  pages =	{10:1--10:16},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-058-3},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{58},
  editor =	{Ricardo Rocha and Tran Cao Son and Christopher Mears and Neda Saeedloei},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8453},
  URN =		{urn:nbn:de:0030-drops-84537},
  doi =		{10.4230/OASIcs.ICLP.2017.10},
  annote =	{Keywords: Prolog abstract machines, heap representation of terms and code, immutable goal stacks, natural language syntax for clauses, answer streams, multi-arg}
}

Keywords: Prolog abstract machines, heap representation of terms and code, immutable goal stacks, natural language syntax for clauses, answer streams, multi-arg
Collection: Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017)
Issue Date: 2018
Date of publication: 14.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI