Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> 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.)



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: