Behind the screen

DyALog uses

1. Logical Push-Down Automata [LPDA] as operational devices to describe various resolution and parsing strategies for logic programs
2. Dynamic Programming techniques to break LPDA computations in elementary sub-derivations that are combinable and sufficiently compact to be tabulable.

This chapter presents briefly the theoretical background behind DyALog and some internal details about its implementation.

LPDA

Logical Push-Down Automata are a natural extension of the Push-Down Automata. They may be non-deterministic. The main difference is the use of unification for transition application.

We consider three basic kinds of transitions:

1. Push
2. Swap
3. Pop

Dynamic Programming

Compilation Process

Given a set of clauses (and eventually a query), the compilation process builds some code of an Abstract Machine and a set of objects that encapsulate this code. The resulting code is either emulated or emitted toward a C file.

From programs to LPDA

From LPDA to Abstract Machine Code

Emitting C code

The emitting phase emits the compiled code to a C file. Futrhermore, some additional code needed to build terms, objects and to run initialization is also emitted.

Execution

Go to the first, previous, next, last section, table of contents.