5 ms·

But can you do it backwards? (note: My experience of Prolog was that it could work out things backwards if you ask it to).

by zandorg 17y ago

mahmud 17y ago
Backward chaining, not backwards. http://en.wikipedia.org/wiki/Backward_chaining http://en.wikipedia.org/wiki/Backward_chaining
- zandorg 17y ago
  I think that's it! Thanks.
silentbicycle 17y ago
Probably not -- it doesn't "work backwards" so much as try to fill in the blanks in a valid way. run(" (defun append (x y) (if x (cons (car x) (append (cdr x) y)) y)) (append '(a b) '(3 4 5))", V). works, because Prolog can unify the former with its result ("does the Lisp expression provided have a result we can determine? Yes, and it's [a, b, 3, 4, 5]"). If you try to unify with the opposite variable unbound ("Is there a valid Lisp expression that results in [a, b, 3, 4, 5]?"), it starts generating a depth-first traversal of every possible valid Lisp expression according to the grammar * (with logic variables; templated, sort of), and could e-ven-tu-a-lly find the append expression. For me, on SWI-Prolog, it just runs out of local stack. If the program had been designed with that use in mind, there would be changes to the design to greatly reduce the search space. Regardless, "Generate every possible syntactically valid program and test each of them until one makes all my test cases pass" is probably a pretty slow way to write code. :) I found Prolog really confusing when I thought about it as "going backwards". Really, it tries to determine if a completely instantiated version of the expression you give it exists (according to the facts and rules you've provided), like trying to fill in a sudoku puzzle. If there isn't a valid solution, it says "no.", otherwise it searches (depth-first) and pauses to present any solutions it finds along the way. "Fill in the missing pieces, backtracking to give multiple solutions" is a fundamentally different style of evaluation than "apply this function to these arguments, return the result", and ideas of forwards/backwards doesn't directly apply. (Unsurprisingly, doing I/O in Prolog gets a bit weird...) In some cases, this means rules have several uses. member(Item, List) can be used both to get each value from a list one at a time ("member(X, [1, 2, 3]" -> 1, 2, 3) and to get all generic lists that contain a value ("member(3, L) --> [3|_G242], [_G241, _3|_G245], [_G241, _G244, 3|_G248], ..."; those are gensyms). This doesn't always work (e.g. add(3, 5, X) succeeds with X=8, add(3, X, 8) needs extra declarations), in part because Prolog doesn't know to try integers unless you tell it (in the above case, "between(X, 1, inf)".) * Based on a quick glance at the code and my understanding of Prolog, thus far.

But can you do it backwards? (note: My experience of Prolog was that it could work out things backwards if you ask it to).

by zandorg 17y ago

But can you do it backwards? (note: My experience of Prolog was that it could work out things backwards if you ask it to).

mahmud 17y ago

Backward chaining, not backwards. http://en.wikipedia.org/wiki/Backward_chaining http://en.wikipedia.org/wiki/Backward_chaining

zandorg 17y ago
I think that's it! Thanks.

silentbicycle 17y ago

Probably not -- it doesn't "work backwards" so much as try to fill in the blanks in a valid way. run(" (defun append (x y) (if x (cons (car x) (append (cdr x) y)) y)) (append '(a b) '(3 4 5))", V). works, because Prolog can unify the former with its result ("does the Lisp expression provided have a result we can determine? Yes, and it's [a, b, 3, 4, 5]"). If you try to unify with the opposite variable unbound ("Is there a valid Lisp expression that results in [a, b, 3, 4, 5]?"), it starts generating a depth-first traversal of every possible valid Lisp expression according to the grammar * (with logic variables; templated, sort of), and could e-ven-tu-a-lly find the append expression. For me, on SWI-Prolog, it just runs out of local stack. If the program had been designed with that use in mind, there would be changes to the design to greatly reduce the search space. Regardless, "Generate every possible syntactically valid program and test each of them until one makes all my test cases pass" is probably a pretty slow way to write code. :) I found Prolog really confusing when I thought about it as "going backwards". Really, it tries to determine if a completely instantiated version of the expression you give it exists (according to the facts and rules you've provided), like trying to fill in a sudoku puzzle. If there isn't a valid solution, it says "no.", otherwise it searches (depth-first) and pauses to present any solutions it finds along the way. "Fill in the missing pieces, backtracking to give multiple solutions" is a fundamentally different style of evaluation than "apply this function to these arguments, return the result", and ideas of forwards/backwards doesn't directly apply. (Unsurprisingly, doing I/O in Prolog gets a bit weird...) In some cases, this means rules have several uses. member(Item, List) can be used both to get each value from a list one at a time ("member(X, [1, 2, 3]" -> 1, 2, 3) and to get all generic lists that contain a value ("member(3, L) --> [3|_G242], [_G241, _3|_G245], [_G241, _G244, 3|_G248], ..."; those are gensyms). This doesn't always work (e.g. add(3, 5, X) succeeds with X=8, add(3, X, 8) needs extra declarations), in part because Prolog doesn't know to try integers unless you tell it (in the above case, "between(X, 1, inf)".) * Based on a quick glance at the code and my understanding of Prolog, thus far.