What paradigm is this?

Question

I have a question regarding different paradigms, I have this code example in Prolog

fib(0, 0).
fib(1, 1).
fib(V, VF) :-
    B is V - 1, C is V - 2,
    fib(B, BF), fib(C, CF),
    VF is BF + CF.

can someone please tell me what paradigm this is and why it is that? Thank you in advance!

Write `:-` in place of `:` and note that `fib(0,1)` does not terminate. — false, Jan 16 '15 at 19:01
... and there should be a minus operator between `V` and 1 and between `V` and 2. — Tudor Berariu, Jan 16 '15 at 19:06
I'm not sure I understand the question, *...what paradigm this is...?* It's recursive (and very inefficiently so) if that's what you mean. — lurker, Jan 16 '15 at 19:14
@OP: if you're not referring to the obvious answer: *logic programming*, then you should give some more details. — Tudor Berariu, Jan 16 '15 at 19:15
well i'm wondering why it's a logical programmin paradigm? like what is the motivation for it because i can't really see why it is logical, only based on that it's written in prolog — martoo, Jan 16 '15 at 19:26

score 4 · Accepted Answer · answered Jan 16 '15 at 20:59

4

Let me first make the program easier to understand and also more general by using true arithmetic relations between integers instead of low-level arithmetic:

:- use_module(library(clpfd)).

fib(0, 0).
fib(1, 1).
fib(V, VF) :-
        V #> 1,
        B #= V - 1,
        C #= V - 2,
        VF #= BF + CF,
        fib(B, BF),
        fib(C, CF).

Notice that since we are stating the solution in terms of true relations, we can also freely move the goals.

The following queries now make it pretty clear why this is called logic programming:

First, you can ask: Is there any solution?

?- fib(X, Y).
X = Y, Y = 0 .

Yes, there is!

Then, you can ask for example: What is the 20-th Fibonacci number?

?- fib(20, Y).
Y = 6765 .

Further, you can ask: Which Fibonacci number(s) equal 233?

?- fib(X, 233).
X = 13 .

Further, you can ask: Is it true that the 10th Fibonacci number is 54?

?- fib(10, 54).
false.

No, it is not true.

Thus, since we can ask logical questions and describe solutions by stating what holds in terms of logical relations, it is called logic programming.

answered Jan 16 '15 at 20:59

mat

40,498
3
51
78

This is good (+1). My original comment to the OP applied when the clauses us `is/2`. – lurker Jan 16 '15 at 21:55
1

`fib(X, 233).` will ask for more solutions after `X = 13` and die from infinite recursion. But I think including `BF #> 0, CF #> 0` constrains it. – lurker Jan 17 '15 at 02:24
This would over-constrain it, since then `?- fib(2, Y)` yields `false`. Nevertheless, your thinking goes in the right direction (+1), and you may find a set of additional constraints that will make the query terminate when either of the arguments is instantiated of even only sufficiently constrained. – mat Jan 17 '15 at 10:43
Ah I see. Probably `BF #>= 0, CF #>= 0`. I wasn't looking carefully. – lurker Jan 17 '15 at 12:36
@lurker: Why not just `VF #>= 0`? – false Jan 17 '15 at 14:43
@false wouldn't then the sum be unnecessarily satisfied by mixed negative and positive values of `BF` and `CF`? – lurker Jan 17 '15 at 15:48
@lurker: do you have an example where the differences shows? – false Jan 17 '15 at 16:08
@false, OK I think I goofed. I actually have a slightly modified version of mat's algorithm in which I had put that constraint, and there it works fine. Just putting the constraint in mat's still yields a very, very long wait (and possible exception). But, mat's answer directly and correctly responds to the OP's question, which is really about logic programming, not a good solution to `fib`, so probably not worth posting. My comment about the constraint is just a side bar. – lurker Jan 17 '15 at 17:42
@false, yep understood. Thanks. As an aside, my other algorithm removes the double recursion by holding one of the prior computed values. – lurker Jan 17 '15 at 17:45

What paradigm is this?

1 Answers1