NEW MEXICO STATE UNIVERSITY
Department of Computer Science

Logic Programming Qualifying Examination
January 12th, 1999 -- 12-14pm

1.

[40 pts] Prolog is frequently praised for its ability to write meta-interpreters, i.e., extended Prolog interpreters written in Prolog itself. The simplest example is represented by the traditional Vanilla meta-interpreter which simply duplicates (pure) Prolog's behavior

    interpret(true).
    interpret((Goal1,Goal2)) :-
            interpret(Goal1),
            interpret(Goal2).
    interpret(Goal) :-
            clause(Goal,Body),
            interpret(Body).

Extend the Vanilla meta-interpreter to produce a sound implementation of negation as failure. Your meta-interpreter should delay the execution of non-ground negative goals and signal an error when floundering occurs.

Do not worry about the finer details of the implementation, focus on providing the general structure of the metainterpreter

Discuss the relations between the execution strategy used by Prolog and the soundness and completeness of negation as failure.

2.

[40 pts] Prolog supplies a built-in predicate, called setof, which allows one to compute all the solutions to a given predicate. The format of a typical call is

setof(X,p(X),L)

and the effect is to collect in a list L all the values of X which satisfy the goal p(X). The setof guarantees that the list L does not contain any repetitions of solutions. This means that for a program containing the facts

        p(a).
        p(b).
        p(a).

the goal setof(X,p(X),L) produces the list

L = [a,b]

Describe how you would produce the same result of setof without using setof. I.e., describe (if possible) a Prolog program that implements setof without using any of the all-solutions predicates of Prolog (i.e., no findall, bagof, etc.). Your solution should also guarantee that no repetitions of solutions occur.

3.

[20 pts] Assuming that you have a magic mechanism that guarantees that Prolog's setof is sound and complete for any goal G having a finite derivation tree, develop a sound and complete implementation of negation as failure relying on the use of setof.