4 ms·

Never understood why natural numbers (or some set of N) is not in the search space: fib(X,X):- X<2. fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). I tried to get an

Never understood why natural numbers (or some set of N) is not in the search space: fib(X,X):- X<2. fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). I tried to get answer to this kwestion in reddit, but all I got was personal insults.

colanderman 10y ago
You can do this in SWI Prolog using the between/3 predicate for the inequality, and the is/2 predicate for the arithmetic.
- colanderman 10y ago
  Example, now that I'm at a terminal: fib(X, X) :- between(0, 1, X). fib(X, Y) :- (var(Y) -> between(2, infinite, X); MaxX is Y + 1, between(2, MaxX, X)), X1 is X - 1, X2 is X - 2, fib(X1, Y1), fib(X2, Y2), Y is Y1 + Y2. The trick with var/1 allows the fib(-, +) instantiation to terminate (albeit very slowly). Otherwise it's not necessary. What's even cooler is SWI-Prolog's CLP support. You can write fib/2 in the obvious manner and support all instantiations: ?- use_module(library(clpfd)). fib(X, X) :- X #>= 0, X #=< 1, indomain(X). fib(X, Y) :- X #>= 2, X #=< Y + 1, X1 #= X - 1, X2 #= X - 2, Y #= Y1 + Y2, fib(X1, Y1), fib(X2, Y2).
- thisrod 10y ago
  When I tried out Prolog, I was struck by the inelegance of is/2. There has to be something like it, because no one knows how to write an interpreter for arcsin(X,Y) :- sin(Y,X). However, MetaPost can do that for linear expressions. You can say (in Prolog syntax) midpoint(X,Y,Z) :- Z == (X+Y)/2. two(X) :- midpoint(0,X,1). And the MetaPost interpreter will find the solution two(2). Does anyone know of Prolog extensions that can solve linear algebra problems like that?
  - colanderman 10y ago
    SWI-Prolog has CLP extensions to do exactly that: http://www.swi-prolog.org/pldoc/man?section=clp http://www.swi-prolog.org/pldoc/man?section=clp ?- use_module(library(clpq)). midpoint(X, Y, Z) :- {Z =:= (X+Y)/2}. two(X) :- midpoint(0, X, 1). does what you want.
    - thisrod 10y ago
      Thank you. It's a relief to know that I don't need to invent it.
wozer 10y ago
Constraint Programming with finite domains can probably do this. For example http://mozart.github.io/ http://mozart.github.io/
tom_mellior 10y ago
> fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). As others have noted, it's possible to write nicely behaved Prolog versions of this that you can use in various ways: call "fib(3, N)" to find the third Fibonacci number, "fib(3, 6)" to see if the third Fibonacci number is 6, or "fib(I, 6)" to find if 6 is the I-th Fibonacci number for some I. But these solutions use slightly more verbose syntax that makes the evaluation of arithmetic expressions explicit. As for the question why this is the case and why Prolog doesn't support this natively, it's because the Prolog system would have to know (a) which terms represent arithmetic expressions and (b) at what time all the variables in those terms will be instantiated. For (a) you need a static type system, which is a well-known concept, and for (b) something called a "mode system", which is something more or less specific to logic and constraint languages. The mode system tells you when certain variables will be bound to values. Consider the example "fib(3, N)", where X is bound, which allows you to compute "X-1" and "X-2", from which you can compute Y1 and Y2, and from these finally "Y1+Y2", i.e., N. For the call "fib(I, 6)" the whole computation is in reverse: From "6 = Y1+Y2" you would need to derive values for Y1 and Y2 (this already involves a search), from which you can derive values that allow you to find values that should be equal, respectively, to "X-1" and "X-2", and from that you might deduce a value for X. This is a completely different computation. It's doable, but you would need to know data types (which in general you don't, in Prolog), predicate modes (which again you don't), and you would need to use separate computations for each mode. There is a functional/logic language called Mercury, which is a superset of a restricted subset of Prolog, which has static types and modes (using user annotations) and compiles separate versions of each predicate for each mode, and in which something more like what you want is already possible. (If I understand correctly, even in Mercury this example wouldn't work, because it only allows you to unify 6 with "Y1+Y2" if at least one of those variables is known.)

colanderman 10y ago

You can do this in SWI Prolog using the between/3 predicate for the inequality, and the is/2 predicate for the arithmetic.

colanderman 10y ago
Example, now that I'm at a terminal: fib(X, X) :- between(0, 1, X). fib(X, Y) :- (var(Y) -> between(2, infinite, X); MaxX is Y + 1, between(2, MaxX, X)), X1 is X - 1, X2 is X - 2, fib(X1, Y1), fib(X2, Y2), Y is Y1 + Y2. The trick with var/1 allows the fib(-, +) instantiation to terminate (albeit very slowly). Otherwise it's not necessary. What's even cooler is SWI-Prolog's CLP support. You can write fib/2 in the obvious manner and support all instantiations: ?- use_module(library(clpfd)). fib(X, X) :- X #>= 0, X #=< 1, indomain(X). fib(X, Y) :- X #>= 2, X #=< Y + 1, X1 #= X - 1, X2 #= X - 2, Y #= Y1 + Y2, fib(X1, Y1), fib(X2, Y2).
thisrod 10y ago
When I tried out Prolog, I was struck by the inelegance of is/2. There has to be something like it, because no one knows how to write an interpreter for arcsin(X,Y) :- sin(Y,X). However, MetaPost can do that for linear expressions. You can say (in Prolog syntax) midpoint(X,Y,Z) :- Z == (X+Y)/2. two(X) :- midpoint(0,X,1). And the MetaPost interpreter will find the solution two(2). Does anyone know of Prolog extensions that can solve linear algebra problems like that?
- colanderman 10y ago
  SWI-Prolog has CLP extensions to do exactly that: http://www.swi-prolog.org/pldoc/man?section=clp http://www.swi-prolog.org/pldoc/man?section=clp ?- use_module(library(clpq)). midpoint(X, Y, Z) :- {Z =:= (X+Y)/2}. two(X) :- midpoint(0, X, 1). does what you want.
  - thisrod 10y ago
    Thank you. It's a relief to know that I don't need to invent it.

wozer 10y ago

Constraint Programming with finite domains can probably do this. For example http://mozart.github.io/ http://mozart.github.io/

tom_mellior 10y ago

> fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2). As others have noted, it's possible to write nicely behaved Prolog versions of this that you can use in various ways: call "fib(3, N)" to find the third Fibonacci number, "fib(3, 6)" to see if the third Fibonacci number is 6, or "fib(I, 6)" to find if 6 is the I-th Fibonacci number for some I. But these solutions use slightly more verbose syntax that makes the evaluation of arithmetic expressions explicit. As for the question why this is the case and why Prolog doesn't support this natively, it's because the Prolog system would have to know (a) which terms represent arithmetic expressions and (b) at what time all the variables in those terms will be instantiated. For (a) you need a static type system, which is a well-known concept, and for (b) something called a "mode system", which is something more or less specific to logic and constraint languages. The mode system tells you when certain variables will be bound to values. Consider the example "fib(3, N)", where X is bound, which allows you to compute "X-1" and "X-2", from which you can compute Y1 and Y2, and from these finally "Y1+Y2", i.e., N. For the call "fib(I, 6)" the whole computation is in reverse: From "6 = Y1+Y2" you would need to derive values for Y1 and Y2 (this already involves a search), from which you can derive values that allow you to find values that should be equal, respectively, to "X-1" and "X-2", and from that you might deduce a value for X. This is a completely different computation. It's doable, but you would need to know data types (which in general you don't, in Prolog), predicate modes (which again you don't), and you would need to use separate computations for each mode. There is a functional/logic language called Mercury, which is a superset of a restricted subset of Prolog, which has static types and modes (using user annotations) and compiles separate versions of each predicate for each mode, and in which something more like what you want is already possible. (If I understand correctly, even in Mercury this example wouldn't work, because it only allows you to unify 6 with "Y1+Y2" if at least one of those variables is known.)