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.

Answer 2

Would depend on the version of Prolog; for example, CProlog is (unsurprisingly) written in C, so all built-in predicates are implemented in a imperative language.

Answer 3

Prolog was developed for language parsing. So, a arithmetic expression like

3 + - ( 4 * 12 ) / 2 + 7

after parsing is just a prolog term (representing the parse tree), with operator/3 providing the semantics to guide the parser's operation. For basic arithmetic expressions, the terms are

• '-'/2. Negation
• '*'/2, '/'/2. Multiplication, division
• '+'/2, '-'/2. Addition, subtraction

The sample expression above is parsed as

'+'( '+'( 3 , '/'( '-'( '*'(4,12) ) , 2 ) ) , 7 )

'is'/2 simply does a recursive walk of the parse tree representing the right hand side, evaluating each term in pretty much the same way an RPN (reverse polish notation) calculator does. Once that expression is evaluated, the result is unified with the left hand side.

Each basic operation — add, subtract, multiply, divide, etc. — has to be done in machine code, so at the end of the day, some machine code routine is being invoked to compute the result of each elemental operation.

Whether is/2 is written entirely in native code or written mostly in prolog, with just the leaf operations written in native code, is pretty much an implementation choice.