next up previous contents
Next: Parallelism Efficiency Up: Sequential Efficiency Previous: Compile-time Analysis

New Models

While many implementations are based on the Warren Abstract Machine, or at least on models directly derived from this design, in recent years some novel execution models have been proposed, which substantially differ from the WAM. Two of the most successful ones are BinProlog [105] and the Vienna Abstract Machine (VAM) [69].

BinProlog: Developed by P. Tarau, BinProlog is based on the idea of continuation passing. Prolog programs are transformed into binary logic programs--i.e. Prolog programs with at most one literal in the body. This is realized by making explicit the transfer of the continuation of each subgoal, as a new argument.

example667

BinProlog has been implemented as a heap-only system (i.e., no concept of environment is introduced). The fact that the abstract machine has been specialized to binary programs allowed to considerably reduce the number of instructions required and facilitated the introduction of a wide variety of optimizations.

Vienna Abstract Machine: The Vienna Abstract Machine (VAM) developed by A. Krall maintains in many aspects the spirit of the WAM, curing some of the drawbacks in the original Warren's design. In particular, Krall's observation is that one of the main sources of inefficiency in the WAM is represented by the separation between the phase in which the arguments of a subgoal are prepared and the phase in which head unification is performed. The original design of VAM (called VAM tex2html_wrap_inline1266 ) is based on an architecture with two instruction pointers. These are used to combine argument setup and head unification in a unique step (by fetching two instructions at the same time, one coming from the goal and one from the head of the clause). Furthermore the selection of the kind of action required is made very efficient by using a special instruction coding, which allows to identify the desired action by simply adding the codes of the two instructions fetched.


next up previous contents
Next: Parallelism Efficiency Up: Sequential Efficiency Previous: Compile-time Analysis

'Enrico
Tue Mar 19 14:37:09 MST 1996