Prolog 'is/2' predicate implementation

Question

How is the 'is/2' Prolog predicate implemented? I know that

X is 3*4

is equivalent with

is(X, 3*4)

But is the predicate implemented using imperative programming? In other words, is the implementation equivalent with the following C code?

if(uninstantiated(x)) 
{
    X = 3*4;
}
else
{
    //signal an error
}

Or is it implemented using declarative programming and other predicates?

Answer 1

Depends on your Prolog, obviously, but any practical implementation will do its dirty work in C or another imperative language. Part of is/2 can be simulated in pure Prolog:

is(X, Expr) :-
    evaluate(Expr, Value),
    (var(X) ->
        X = Value
    ;
        X =:= Value
    ).

Where evaluate is a huge predicate that knows about arithmetic expressions. There are ways to implement large parts of it in pure Prolog too, but that will be both slow and painful. E.g. if you have a predicate that adds integers, then you can multiply them as well using the following (stupid) algorithm:

evaluate(X + Y, Value) :-
    % even this can be done in Prolog using an increment predicate,
    % but it would take O(n) time to do n/2 + n/2.
    add(X, Y, Value).
evaluate(X * Y, Value) :-
    (X == 0 ->
        Value = 0
    ;
        evaluate(X + -1, X1),
        evaluate(X1, Y, Value1),
        evaluate(Y + Value1, Value)
    ).

None of this is guaranteed to be either practical or correct; I'm just showing how arithmetic could be implemented in Prolog.