CODEWITHSUNDEEP
prolog
SuperCow
SuperCow

Reputation: 1613

Prolog: McCarthy 91

I'm learning about recursion and came across the McCarthy 91 function.

I've been able to find examples of it in several languages (C++, Java, Python, Scheme, and so on). I'm trying to find out how it would be written in Prolog though.

I can't find any examples online nor do I have much of an idea about how to write it myself (in Prolog). Could someone post a code example of it or point me towards the proper source online? Thanks greatly for the help.

Upvotes: 1

Views: 427

Answers (3)

false
false

Reputation: 10122

There are several remarkable aspects here. After all, the original intention of this function was to consider it in the context of formal verification.

As long as you encode this function with (is)/2 you will get essentially the same as in other languages - a function where you need to reason about. You need to switch from the moded arithmetic of (is)/2 to the (rudimentary) algebra provided by library(clpfd) to turn Prolog to reason about the relation directly:

:- use_module(library(clpfd)).

m(N0,N):-
   N0#>100,
   N #= N0-10.
m(N0,N):-
   N0#=<100,
   N1 #=N0+11,
   m(N1,N2),
   m(N2,N).

Now, we can not only ask for a concrete result, we can also ask:

?- m(N0,N).
   N0 in 101..sup, N+10#=N0, N in 91..sup
;  N0 = 100, N = 91
;  N0 = 99, N = 91
;  N0 = 98, N = 91
;  N0 = 97, N = 91
;  ... .

Or, more specifically, we might ask when this "function" will be not equal 91:

?- N#\=91, m(N0,N).
   N in 92..sup, N+10#=N0, N0 in 102..sup
;  loops.

The first answer tells us that for values N0 in 102..sup the result will not be 91. Then, the system tries to find the next answer, but needs too much time (that is, too much time for us finite beings).

Ideally, we would have implemented m/2 like so:

m2(N0,N) :-
   N0#>100,
   N #= N0-10.
m2(N0,N):-
   N0#=<100,
   N #= 91.

and in fact, this would be a challenge to a program transformation systems. m2/2 permits Prolog to describe the entire relation with two answers:

?- m2(N0,N).
   N0 in 101..sup, N+10#=N0, N in 91..sup
;  N = 91, N0 in inf..100.

So we have described here infinitely many solutions with finite means!

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

here is a test in SWI-Prolog, using lifter (I left the non lifted clause commented above, to make easier understanding it).

:- [lifter].

%m(N, M) :- N > 100 -> M is N-10 ; T1 is N+11, m(T1, T2), m(T2, M).
 m(N, M) :- N > 100 -> M is N-10 ; m(m(° is N+11, °), M).

and here is the translation in plain Prolog (of course identical to Sergey one, after renaming variables)

6 ?- listing(m).
m(A, B) :-
    (   A>100
    ->  B is A-10
    ;   C is A+11,
        m(C, D),
        m(D, B)
    ).

true.

7 ?- writeln(m(88,°)).
91
true.

Upvotes: 3

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7229

m91(N, M) :-
    ( N > 100 ->
        M is N - 10
    ;
        Np11 is N + 11,
        m91(Np11, M1),
        m91(M1, M)
    ).

It's not really a function, but a predicate. Result is "returned" in the second argument:

?- m91(99, M).
M = 91.

?- m91(87, M).
M = 91.

?- m91(187, M).
M = 177.

Some Prolog implementations allow to use predicates like this as arithmetic functions. Using ECLiPSe:

[eclipse]: M is m91(99).
M = 91
Yes (0.00s cpu)

Upvotes: 2

Related Questions