Prolog reverse lookup and input validation at the same time
I have started learning prolog recently and even though it is refreshing to move away from functional programming, things still seem very foreign. I having trouble understanding how I can write a predicate the checks whether its argument adhere to a certain set of rules and also at the same time if given a variable will set it to the possible values that satisfy those rules.
I was trying to solve the circular table seating problem where you define a set of conditions for people to sit next to each other. So the knowledge base contains 10 individuals with the languages they speak and the goal is to seat them in a way such that two people sitting next to each other must speak the same language.
I defined a predicate speaksSame(X, Y)
which returns true if both individuals X and Y speak the same language. Now the goal is to write a function table-seating such that table-seating([mark, carl, emily, kevin, oliver])
returns true if each two people sitting next to each other in the list speak a common language. Off course for this to happen each person speaks more than one language. And also table-seating(L). Would get the possible table seatings that satisfy the condition.
The way I see it is I can either write a predicate that checks if a previously defined list satisfies the rules or one the builds a list according to these rules. I don't understand how I can do both with one function.
Any help would be really appreciated, thanks!
recursion prolog imperative-programming
add a comment |
I have started learning prolog recently and even though it is refreshing to move away from functional programming, things still seem very foreign. I having trouble understanding how I can write a predicate the checks whether its argument adhere to a certain set of rules and also at the same time if given a variable will set it to the possible values that satisfy those rules.
I was trying to solve the circular table seating problem where you define a set of conditions for people to sit next to each other. So the knowledge base contains 10 individuals with the languages they speak and the goal is to seat them in a way such that two people sitting next to each other must speak the same language.
I defined a predicate speaksSame(X, Y)
which returns true if both individuals X and Y speak the same language. Now the goal is to write a function table-seating such that table-seating([mark, carl, emily, kevin, oliver])
returns true if each two people sitting next to each other in the list speak a common language. Off course for this to happen each person speaks more than one language. And also table-seating(L). Would get the possible table seatings that satisfy the condition.
The way I see it is I can either write a predicate that checks if a previously defined list satisfies the rules or one the builds a list according to these rules. I don't understand how I can do both with one function.
Any help would be really appreciated, thanks!
recursion prolog imperative-programming
add a comment |
I have started learning prolog recently and even though it is refreshing to move away from functional programming, things still seem very foreign. I having trouble understanding how I can write a predicate the checks whether its argument adhere to a certain set of rules and also at the same time if given a variable will set it to the possible values that satisfy those rules.
I was trying to solve the circular table seating problem where you define a set of conditions for people to sit next to each other. So the knowledge base contains 10 individuals with the languages they speak and the goal is to seat them in a way such that two people sitting next to each other must speak the same language.
I defined a predicate speaksSame(X, Y)
which returns true if both individuals X and Y speak the same language. Now the goal is to write a function table-seating such that table-seating([mark, carl, emily, kevin, oliver])
returns true if each two people sitting next to each other in the list speak a common language. Off course for this to happen each person speaks more than one language. And also table-seating(L). Would get the possible table seatings that satisfy the condition.
The way I see it is I can either write a predicate that checks if a previously defined list satisfies the rules or one the builds a list according to these rules. I don't understand how I can do both with one function.
Any help would be really appreciated, thanks!
recursion prolog imperative-programming
I have started learning prolog recently and even though it is refreshing to move away from functional programming, things still seem very foreign. I having trouble understanding how I can write a predicate the checks whether its argument adhere to a certain set of rules and also at the same time if given a variable will set it to the possible values that satisfy those rules.
I was trying to solve the circular table seating problem where you define a set of conditions for people to sit next to each other. So the knowledge base contains 10 individuals with the languages they speak and the goal is to seat them in a way such that two people sitting next to each other must speak the same language.
I defined a predicate speaksSame(X, Y)
which returns true if both individuals X and Y speak the same language. Now the goal is to write a function table-seating such that table-seating([mark, carl, emily, kevin, oliver])
returns true if each two people sitting next to each other in the list speak a common language. Off course for this to happen each person speaks more than one language. And also table-seating(L). Would get the possible table seatings that satisfy the condition.
The way I see it is I can either write a predicate that checks if a previously defined list satisfies the rules or one the builds a list according to these rules. I don't understand how I can do both with one function.
Any help would be really appreciated, thanks!
recursion prolog imperative-programming
recursion prolog imperative-programming
asked Nov 19 '18 at 23:12
Kareem AboughazalaKareem Aboughazala
1251112
1251112
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
I don't understand how I can do both with one function.
Yes, at first this seems odd, but then once you get the hang of it, you miss it in other languages.
The word you want to remember when referencing this is: mode
Also see Mercury Modes reference for more detail related to the Mercury programming language.
In Prolog an argument can be an input, and output, or both used as an input or output depending upon how it is called.
In Type, mode and determinism declaration headers at the bottom is listed 4 examples.
- length(+List:list, -Length:int) is det.
- length(?List:list, -Length:int) is nondet.
- length(?List:list, +Length:int) is det.
- True if List is a list of length Length.
and the definition of length/2
shows
length(?List, ?Int)
meaning
that for the List
argument, the list can be bound or unbound, and
that for the Int
argument, the value can be bound or unbound.
So for the two arguments with two options there are four ways to use length/2
Here they are listed again but in actual usage.
1.
length(+List:list, -Length:int) is det.
in this case List is bound and Length is unbound and always gives one answer.
?- length([1,2,3],N).
N = 3.
2.
length(?List:list, -Length:int) is nondet.
in this case List is unbound and Length is unbound and can return any number of answers.
?- length(List,N).
List = ,
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5
...
3.
length(?List:list, +Length:int) is det.
in this case List is unbound and Length is bound and always gives one answer.
?- length(List,4).
List = [_5332, _5338, _5344, _5350].
4.
True if List is a list of length Length.
in this case List is bound and Length is bound and always acts as predicate to return either true
or false
.
?- length([1,2,3],3).
true.
?- length([1,2,3],5).
false.
So how is this possible?
Prolog uses syntactic unification (↦) and NOT assignment (=).
If we look at the source code for length/2
using listing/1
we get
?- listing(length/2).
system:length(B, A) :-
var(A), !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> C==A,
'$length3'(C, A, D)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(B, A) :-
integer(A),
A>=0, !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> E is A-D,
'$length'(C, E)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(_, A) :-
integer(A), !,
throw(error(domain_error(not_less_than_zero, A),
context(length/2, _))).
system:length(_, A) :-
throw(error(type_error(integer, A), context(length/2, _))).
which is too much detail but does do all 4 modes correctly.
To make it easier to understand we will use this version, but it doesn't support 1 of the modes correctly but it does do more than one mode so it works good enough to demonstrate.
length_2( , 0 ).
length_2([_|Xs] , L ) :-
length_2(Xs,N),
L is N+1 .
Now to see the unification in action we will use the trace feature of SWI-Prolog and to enable all of the ports for the box model use visible/1 and so as not to stop it when running use leash/1.
?- visible(+all),leash(-all).
?- trace.
1.
[trace] ?- length_2([1,2,3],N).
Call: (8) length_2([1, 2, 3], _2352)
Unify: (8) length_2([1, 2, 3], _2352)
Call: (9) length_2([2, 3], _2580)
Unify: (9) length_2([2, 3], _2580)
Call: (10) length_2([3], _2580)
Unify: (10) length_2([3], _2580)
Call: (11) length_2(, _2580)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2584 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2590 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) _2352 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
N = 3.
2.
[trace] ?- length_2(List,N).
Call: (8) length_2(_2296, _2298)
Unify: (8) length_2(, 0)
Exit: (8) length_2(, 0)
List = ,
N = 0 ;
Redo: (8) length_2(_2296, _2298)
Unify: (8) length_2([_2528|_2530], _2298)
Call: (9) length_2(_2530, _2550)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) _2298 is 0+1
Exit: (9) 1 is 0+1
Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
Redo: (9) length_2(_2530, _2550)
Unify: (9) length_2([_2534|_2536], _2556)
Call: (10) length_2(_2536, _2556)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _2560 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_2534], 1)
Call: (9) _2298 is 1+1
Exit: (9) 2 is 1+1
Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
Redo: (10) length_2(_2536, _2556)
Unify: (10) length_2([_2540|_2542], _2562)
Call: (11) length_2(_2542, _2562)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2566 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_2540], 1)
Call: (10) _2572 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_2534, _2540], 2)
Call: (9) _2298 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3
3.
[trace] ?- length_2(List,3).
Call: (8) length_2(_5534, 3)
Unify: (8) length_2([_5724|_5726], 3)
Call: (9) length_2(_5726, _5746)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) 3 is 0+1
Fail: (9) 3 is 0+1
Redo: (9) length_2(_5726, _5746)
Unify: (9) length_2([_5730|_5732], _5752)
Call: (10) length_2(_5732, _5752)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _5756 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_5730], 1)
Call: (9) 3 is 1+1
Fail: (9) 3 is 1+1
Redo: (10) length_2(_5732, _5752)
Unify: (10) length_2([_5736|_5738], _5758)
Call: (11) length_2(_5738, _5758)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _5762 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_5736], 1)
Call: (10) _5768 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_5730, _5736], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736]
Action (h for help) ? abort
% Execution Aborted
4.
[trace] ?- length_2([1,2,3],3).
Call: (8) length_2([1, 2, 3], 3)
Unify: (8) length_2([1, 2, 3], 3)
Call: (9) length_2([2, 3], _2058)
Unify: (9) length_2([2, 3], _2058)
Call: (10) length_2([3], _2058)
Unify: (10) length_2([3], _2058)
Call: (11) length_2(, _2058)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2062 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2068 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
true.
[trace] ?- length_2([1,2,3],5).
Call: (8) length_2([1, 2, 3], 5)
Unify: (8) length_2([1, 2, 3], 5)
Call: (9) length_2([2, 3], _2442)
Unify: (9) length_2([2, 3], _2442)
Call: (10) length_2([3], _2442)
Unify: (10) length_2([3], _2442)
Call: (11) length_2(, _2442)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2446 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2452 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 5 is 2+1
Fail: (9) 5 is 2+1
Fail: (8) length_2([1, 2, 3], 5)
false.
and to turn the trace off
[trace] ?- notrace.
true.
[debug] ?- nodebug.
true.
I won't go through each of the lines in the trace output, but if you understand syntactic unification and can follow the trace, after working through the examples given you will see how variables in Prolog are unified resulting in different modes when compared to imperative programming.
Remember that variables are only bound once in Prolog, and never reassigned, and that the numbers on the left in the trace in parenthesis, e.g. (10), are the stack level, so when a call is made to a predicate again, a new set of variables are made available, and while it may seem the are being reassigned a value, it is actually another variable in the stack, just in a different stack frame.
As an aside when learning Prolog one piece of advise I give is that it is easier to learn if you set aside what you know about imperative and functional programming, except for maybe recursion, and start from the ground up with unification and then backward chaining.
If you can read OCaml, here is a simplified version of unification and backward chaining. Note that this is not a Prolog as it does not have list or the cut operator but if you can understand it, then the ways of unification and backward chaining become apparent.
I have to add that I am not totally satisfied with my answer as I know you are a beginner and this answer is to much information to digest and requires a lot of work on your part to work through the 4 trace examples. However it does answer the question and gives a practical example with more than enough meat on the bone. I am working on trying to think of a better example which would include logical purity and that demonstrates that not only unification but relationships are key to how multiple modes can be accomplishes in one predicate. Be glad I didn't use general relativity as paraphrased by the relativist John Archibald Wheeler, spacetime tells matter how to move; matter tells spacetime how to curve
.
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
add a comment |
I have been doing Prolog for a few years and I feel like my comfort with and understanding of different instantiation patterns has come in several discrete steps. The first significant hurdle is of course recursion, which is all you really need to get your head around for this problem. Basically, you know that your table assignment for two people is correct if they speak the same language, so this is your base case:
table_seating([X,Y]) :- speaksSame(X, Y).
So, what if you add a third person to the mix? You'd do something like this:
% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).
Now hopefully you notice that your new work is speaksSame(A,X)
but your old work has remained the same. Let's just worry about the new person and trust that we could have handled it for the remainder of the list.
table_seating([X,Y,Z|Rest]) :-
speaksSame(X, Y),
table_seating([Y,Z|Rest]).
What we're doing here is saying, assume we have at least three items in the list. Then if the first two speak the same language, and the next two plus the rest can be seated, then they can all be seated. You can always take a correctly-seated table and add a person to the front of the table, if they speak the same language as the person currently at the front of the table.
Recursion almost always has this flavor: how can I set up the minimal correct situation, the base case, and then, how can I add one more thing to that situation correctly?
Now what's interesting is that if you supply a list of some length to this predicate, it will "just work" and produce solutions of that length. Try it like so:
?- length(L, 6), table_seating(L).
You will probably get solutions (I assume speaksSame/2
will generate solutions). This is because all Prolog knows about these variables, it knows about because of your speaksSame/2
predicate. So as long as you use predicates that have many instantiation patterns in your predicates and don't force assignments to things or order things strangely, often your predicates will inherit these modes. This is a reason I recommend people use succ/2
instead of N is N0 + 1
or N0 is N - 1
, because succ/2
defines a relationship between two numbers rather than performing some arithmetic (clpfd takes this idea much, much further).
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53383978%2fprolog-reverse-lookup-and-input-validation-at-the-same-time%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
I don't understand how I can do both with one function.
Yes, at first this seems odd, but then once you get the hang of it, you miss it in other languages.
The word you want to remember when referencing this is: mode
Also see Mercury Modes reference for more detail related to the Mercury programming language.
In Prolog an argument can be an input, and output, or both used as an input or output depending upon how it is called.
In Type, mode and determinism declaration headers at the bottom is listed 4 examples.
- length(+List:list, -Length:int) is det.
- length(?List:list, -Length:int) is nondet.
- length(?List:list, +Length:int) is det.
- True if List is a list of length Length.
and the definition of length/2
shows
length(?List, ?Int)
meaning
that for the List
argument, the list can be bound or unbound, and
that for the Int
argument, the value can be bound or unbound.
So for the two arguments with two options there are four ways to use length/2
Here they are listed again but in actual usage.
1.
length(+List:list, -Length:int) is det.
in this case List is bound and Length is unbound and always gives one answer.
?- length([1,2,3],N).
N = 3.
2.
length(?List:list, -Length:int) is nondet.
in this case List is unbound and Length is unbound and can return any number of answers.
?- length(List,N).
List = ,
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5
...
3.
length(?List:list, +Length:int) is det.
in this case List is unbound and Length is bound and always gives one answer.
?- length(List,4).
List = [_5332, _5338, _5344, _5350].
4.
True if List is a list of length Length.
in this case List is bound and Length is bound and always acts as predicate to return either true
or false
.
?- length([1,2,3],3).
true.
?- length([1,2,3],5).
false.
So how is this possible?
Prolog uses syntactic unification (↦) and NOT assignment (=).
If we look at the source code for length/2
using listing/1
we get
?- listing(length/2).
system:length(B, A) :-
var(A), !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> C==A,
'$length3'(C, A, D)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(B, A) :-
integer(A),
A>=0, !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> E is A-D,
'$length'(C, E)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(_, A) :-
integer(A), !,
throw(error(domain_error(not_less_than_zero, A),
context(length/2, _))).
system:length(_, A) :-
throw(error(type_error(integer, A), context(length/2, _))).
which is too much detail but does do all 4 modes correctly.
To make it easier to understand we will use this version, but it doesn't support 1 of the modes correctly but it does do more than one mode so it works good enough to demonstrate.
length_2( , 0 ).
length_2([_|Xs] , L ) :-
length_2(Xs,N),
L is N+1 .
Now to see the unification in action we will use the trace feature of SWI-Prolog and to enable all of the ports for the box model use visible/1 and so as not to stop it when running use leash/1.
?- visible(+all),leash(-all).
?- trace.
1.
[trace] ?- length_2([1,2,3],N).
Call: (8) length_2([1, 2, 3], _2352)
Unify: (8) length_2([1, 2, 3], _2352)
Call: (9) length_2([2, 3], _2580)
Unify: (9) length_2([2, 3], _2580)
Call: (10) length_2([3], _2580)
Unify: (10) length_2([3], _2580)
Call: (11) length_2(, _2580)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2584 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2590 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) _2352 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
N = 3.
2.
[trace] ?- length_2(List,N).
Call: (8) length_2(_2296, _2298)
Unify: (8) length_2(, 0)
Exit: (8) length_2(, 0)
List = ,
N = 0 ;
Redo: (8) length_2(_2296, _2298)
Unify: (8) length_2([_2528|_2530], _2298)
Call: (9) length_2(_2530, _2550)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) _2298 is 0+1
Exit: (9) 1 is 0+1
Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
Redo: (9) length_2(_2530, _2550)
Unify: (9) length_2([_2534|_2536], _2556)
Call: (10) length_2(_2536, _2556)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _2560 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_2534], 1)
Call: (9) _2298 is 1+1
Exit: (9) 2 is 1+1
Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
Redo: (10) length_2(_2536, _2556)
Unify: (10) length_2([_2540|_2542], _2562)
Call: (11) length_2(_2542, _2562)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2566 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_2540], 1)
Call: (10) _2572 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_2534, _2540], 2)
Call: (9) _2298 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3
3.
[trace] ?- length_2(List,3).
Call: (8) length_2(_5534, 3)
Unify: (8) length_2([_5724|_5726], 3)
Call: (9) length_2(_5726, _5746)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) 3 is 0+1
Fail: (9) 3 is 0+1
Redo: (9) length_2(_5726, _5746)
Unify: (9) length_2([_5730|_5732], _5752)
Call: (10) length_2(_5732, _5752)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _5756 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_5730], 1)
Call: (9) 3 is 1+1
Fail: (9) 3 is 1+1
Redo: (10) length_2(_5732, _5752)
Unify: (10) length_2([_5736|_5738], _5758)
Call: (11) length_2(_5738, _5758)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _5762 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_5736], 1)
Call: (10) _5768 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_5730, _5736], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736]
Action (h for help) ? abort
% Execution Aborted
4.
[trace] ?- length_2([1,2,3],3).
Call: (8) length_2([1, 2, 3], 3)
Unify: (8) length_2([1, 2, 3], 3)
Call: (9) length_2([2, 3], _2058)
Unify: (9) length_2([2, 3], _2058)
Call: (10) length_2([3], _2058)
Unify: (10) length_2([3], _2058)
Call: (11) length_2(, _2058)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2062 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2068 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
true.
[trace] ?- length_2([1,2,3],5).
Call: (8) length_2([1, 2, 3], 5)
Unify: (8) length_2([1, 2, 3], 5)
Call: (9) length_2([2, 3], _2442)
Unify: (9) length_2([2, 3], _2442)
Call: (10) length_2([3], _2442)
Unify: (10) length_2([3], _2442)
Call: (11) length_2(, _2442)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2446 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2452 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 5 is 2+1
Fail: (9) 5 is 2+1
Fail: (8) length_2([1, 2, 3], 5)
false.
and to turn the trace off
[trace] ?- notrace.
true.
[debug] ?- nodebug.
true.
I won't go through each of the lines in the trace output, but if you understand syntactic unification and can follow the trace, after working through the examples given you will see how variables in Prolog are unified resulting in different modes when compared to imperative programming.
Remember that variables are only bound once in Prolog, and never reassigned, and that the numbers on the left in the trace in parenthesis, e.g. (10), are the stack level, so when a call is made to a predicate again, a new set of variables are made available, and while it may seem the are being reassigned a value, it is actually another variable in the stack, just in a different stack frame.
As an aside when learning Prolog one piece of advise I give is that it is easier to learn if you set aside what you know about imperative and functional programming, except for maybe recursion, and start from the ground up with unification and then backward chaining.
If you can read OCaml, here is a simplified version of unification and backward chaining. Note that this is not a Prolog as it does not have list or the cut operator but if you can understand it, then the ways of unification and backward chaining become apparent.
I have to add that I am not totally satisfied with my answer as I know you are a beginner and this answer is to much information to digest and requires a lot of work on your part to work through the 4 trace examples. However it does answer the question and gives a practical example with more than enough meat on the bone. I am working on trying to think of a better example which would include logical purity and that demonstrates that not only unification but relationships are key to how multiple modes can be accomplishes in one predicate. Be glad I didn't use general relativity as paraphrased by the relativist John Archibald Wheeler, spacetime tells matter how to move; matter tells spacetime how to curve
.
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
add a comment |
I don't understand how I can do both with one function.
Yes, at first this seems odd, but then once you get the hang of it, you miss it in other languages.
The word you want to remember when referencing this is: mode
Also see Mercury Modes reference for more detail related to the Mercury programming language.
In Prolog an argument can be an input, and output, or both used as an input or output depending upon how it is called.
In Type, mode and determinism declaration headers at the bottom is listed 4 examples.
- length(+List:list, -Length:int) is det.
- length(?List:list, -Length:int) is nondet.
- length(?List:list, +Length:int) is det.
- True if List is a list of length Length.
and the definition of length/2
shows
length(?List, ?Int)
meaning
that for the List
argument, the list can be bound or unbound, and
that for the Int
argument, the value can be bound or unbound.
So for the two arguments with two options there are four ways to use length/2
Here they are listed again but in actual usage.
1.
length(+List:list, -Length:int) is det.
in this case List is bound and Length is unbound and always gives one answer.
?- length([1,2,3],N).
N = 3.
2.
length(?List:list, -Length:int) is nondet.
in this case List is unbound and Length is unbound and can return any number of answers.
?- length(List,N).
List = ,
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5
...
3.
length(?List:list, +Length:int) is det.
in this case List is unbound and Length is bound and always gives one answer.
?- length(List,4).
List = [_5332, _5338, _5344, _5350].
4.
True if List is a list of length Length.
in this case List is bound and Length is bound and always acts as predicate to return either true
or false
.
?- length([1,2,3],3).
true.
?- length([1,2,3],5).
false.
So how is this possible?
Prolog uses syntactic unification (↦) and NOT assignment (=).
If we look at the source code for length/2
using listing/1
we get
?- listing(length/2).
system:length(B, A) :-
var(A), !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> C==A,
'$length3'(C, A, D)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(B, A) :-
integer(A),
A>=0, !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> E is A-D,
'$length'(C, E)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(_, A) :-
integer(A), !,
throw(error(domain_error(not_less_than_zero, A),
context(length/2, _))).
system:length(_, A) :-
throw(error(type_error(integer, A), context(length/2, _))).
which is too much detail but does do all 4 modes correctly.
To make it easier to understand we will use this version, but it doesn't support 1 of the modes correctly but it does do more than one mode so it works good enough to demonstrate.
length_2( , 0 ).
length_2([_|Xs] , L ) :-
length_2(Xs,N),
L is N+1 .
Now to see the unification in action we will use the trace feature of SWI-Prolog and to enable all of the ports for the box model use visible/1 and so as not to stop it when running use leash/1.
?- visible(+all),leash(-all).
?- trace.
1.
[trace] ?- length_2([1,2,3],N).
Call: (8) length_2([1, 2, 3], _2352)
Unify: (8) length_2([1, 2, 3], _2352)
Call: (9) length_2([2, 3], _2580)
Unify: (9) length_2([2, 3], _2580)
Call: (10) length_2([3], _2580)
Unify: (10) length_2([3], _2580)
Call: (11) length_2(, _2580)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2584 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2590 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) _2352 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
N = 3.
2.
[trace] ?- length_2(List,N).
Call: (8) length_2(_2296, _2298)
Unify: (8) length_2(, 0)
Exit: (8) length_2(, 0)
List = ,
N = 0 ;
Redo: (8) length_2(_2296, _2298)
Unify: (8) length_2([_2528|_2530], _2298)
Call: (9) length_2(_2530, _2550)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) _2298 is 0+1
Exit: (9) 1 is 0+1
Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
Redo: (9) length_2(_2530, _2550)
Unify: (9) length_2([_2534|_2536], _2556)
Call: (10) length_2(_2536, _2556)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _2560 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_2534], 1)
Call: (9) _2298 is 1+1
Exit: (9) 2 is 1+1
Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
Redo: (10) length_2(_2536, _2556)
Unify: (10) length_2([_2540|_2542], _2562)
Call: (11) length_2(_2542, _2562)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2566 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_2540], 1)
Call: (10) _2572 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_2534, _2540], 2)
Call: (9) _2298 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3
3.
[trace] ?- length_2(List,3).
Call: (8) length_2(_5534, 3)
Unify: (8) length_2([_5724|_5726], 3)
Call: (9) length_2(_5726, _5746)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) 3 is 0+1
Fail: (9) 3 is 0+1
Redo: (9) length_2(_5726, _5746)
Unify: (9) length_2([_5730|_5732], _5752)
Call: (10) length_2(_5732, _5752)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _5756 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_5730], 1)
Call: (9) 3 is 1+1
Fail: (9) 3 is 1+1
Redo: (10) length_2(_5732, _5752)
Unify: (10) length_2([_5736|_5738], _5758)
Call: (11) length_2(_5738, _5758)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _5762 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_5736], 1)
Call: (10) _5768 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_5730, _5736], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736]
Action (h for help) ? abort
% Execution Aborted
4.
[trace] ?- length_2([1,2,3],3).
Call: (8) length_2([1, 2, 3], 3)
Unify: (8) length_2([1, 2, 3], 3)
Call: (9) length_2([2, 3], _2058)
Unify: (9) length_2([2, 3], _2058)
Call: (10) length_2([3], _2058)
Unify: (10) length_2([3], _2058)
Call: (11) length_2(, _2058)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2062 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2068 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
true.
[trace] ?- length_2([1,2,3],5).
Call: (8) length_2([1, 2, 3], 5)
Unify: (8) length_2([1, 2, 3], 5)
Call: (9) length_2([2, 3], _2442)
Unify: (9) length_2([2, 3], _2442)
Call: (10) length_2([3], _2442)
Unify: (10) length_2([3], _2442)
Call: (11) length_2(, _2442)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2446 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2452 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 5 is 2+1
Fail: (9) 5 is 2+1
Fail: (8) length_2([1, 2, 3], 5)
false.
and to turn the trace off
[trace] ?- notrace.
true.
[debug] ?- nodebug.
true.
I won't go through each of the lines in the trace output, but if you understand syntactic unification and can follow the trace, after working through the examples given you will see how variables in Prolog are unified resulting in different modes when compared to imperative programming.
Remember that variables are only bound once in Prolog, and never reassigned, and that the numbers on the left in the trace in parenthesis, e.g. (10), are the stack level, so when a call is made to a predicate again, a new set of variables are made available, and while it may seem the are being reassigned a value, it is actually another variable in the stack, just in a different stack frame.
As an aside when learning Prolog one piece of advise I give is that it is easier to learn if you set aside what you know about imperative and functional programming, except for maybe recursion, and start from the ground up with unification and then backward chaining.
If you can read OCaml, here is a simplified version of unification and backward chaining. Note that this is not a Prolog as it does not have list or the cut operator but if you can understand it, then the ways of unification and backward chaining become apparent.
I have to add that I am not totally satisfied with my answer as I know you are a beginner and this answer is to much information to digest and requires a lot of work on your part to work through the 4 trace examples. However it does answer the question and gives a practical example with more than enough meat on the bone. I am working on trying to think of a better example which would include logical purity and that demonstrates that not only unification but relationships are key to how multiple modes can be accomplishes in one predicate. Be glad I didn't use general relativity as paraphrased by the relativist John Archibald Wheeler, spacetime tells matter how to move; matter tells spacetime how to curve
.
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
add a comment |
I don't understand how I can do both with one function.
Yes, at first this seems odd, but then once you get the hang of it, you miss it in other languages.
The word you want to remember when referencing this is: mode
Also see Mercury Modes reference for more detail related to the Mercury programming language.
In Prolog an argument can be an input, and output, or both used as an input or output depending upon how it is called.
In Type, mode and determinism declaration headers at the bottom is listed 4 examples.
- length(+List:list, -Length:int) is det.
- length(?List:list, -Length:int) is nondet.
- length(?List:list, +Length:int) is det.
- True if List is a list of length Length.
and the definition of length/2
shows
length(?List, ?Int)
meaning
that for the List
argument, the list can be bound or unbound, and
that for the Int
argument, the value can be bound or unbound.
So for the two arguments with two options there are four ways to use length/2
Here they are listed again but in actual usage.
1.
length(+List:list, -Length:int) is det.
in this case List is bound and Length is unbound and always gives one answer.
?- length([1,2,3],N).
N = 3.
2.
length(?List:list, -Length:int) is nondet.
in this case List is unbound and Length is unbound and can return any number of answers.
?- length(List,N).
List = ,
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5
...
3.
length(?List:list, +Length:int) is det.
in this case List is unbound and Length is bound and always gives one answer.
?- length(List,4).
List = [_5332, _5338, _5344, _5350].
4.
True if List is a list of length Length.
in this case List is bound and Length is bound and always acts as predicate to return either true
or false
.
?- length([1,2,3],3).
true.
?- length([1,2,3],5).
false.
So how is this possible?
Prolog uses syntactic unification (↦) and NOT assignment (=).
If we look at the source code for length/2
using listing/1
we get
?- listing(length/2).
system:length(B, A) :-
var(A), !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> C==A,
'$length3'(C, A, D)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(B, A) :-
integer(A),
A>=0, !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> E is A-D,
'$length'(C, E)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(_, A) :-
integer(A), !,
throw(error(domain_error(not_less_than_zero, A),
context(length/2, _))).
system:length(_, A) :-
throw(error(type_error(integer, A), context(length/2, _))).
which is too much detail but does do all 4 modes correctly.
To make it easier to understand we will use this version, but it doesn't support 1 of the modes correctly but it does do more than one mode so it works good enough to demonstrate.
length_2( , 0 ).
length_2([_|Xs] , L ) :-
length_2(Xs,N),
L is N+1 .
Now to see the unification in action we will use the trace feature of SWI-Prolog and to enable all of the ports for the box model use visible/1 and so as not to stop it when running use leash/1.
?- visible(+all),leash(-all).
?- trace.
1.
[trace] ?- length_2([1,2,3],N).
Call: (8) length_2([1, 2, 3], _2352)
Unify: (8) length_2([1, 2, 3], _2352)
Call: (9) length_2([2, 3], _2580)
Unify: (9) length_2([2, 3], _2580)
Call: (10) length_2([3], _2580)
Unify: (10) length_2([3], _2580)
Call: (11) length_2(, _2580)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2584 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2590 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) _2352 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
N = 3.
2.
[trace] ?- length_2(List,N).
Call: (8) length_2(_2296, _2298)
Unify: (8) length_2(, 0)
Exit: (8) length_2(, 0)
List = ,
N = 0 ;
Redo: (8) length_2(_2296, _2298)
Unify: (8) length_2([_2528|_2530], _2298)
Call: (9) length_2(_2530, _2550)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) _2298 is 0+1
Exit: (9) 1 is 0+1
Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
Redo: (9) length_2(_2530, _2550)
Unify: (9) length_2([_2534|_2536], _2556)
Call: (10) length_2(_2536, _2556)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _2560 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_2534], 1)
Call: (9) _2298 is 1+1
Exit: (9) 2 is 1+1
Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
Redo: (10) length_2(_2536, _2556)
Unify: (10) length_2([_2540|_2542], _2562)
Call: (11) length_2(_2542, _2562)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2566 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_2540], 1)
Call: (10) _2572 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_2534, _2540], 2)
Call: (9) _2298 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3
3.
[trace] ?- length_2(List,3).
Call: (8) length_2(_5534, 3)
Unify: (8) length_2([_5724|_5726], 3)
Call: (9) length_2(_5726, _5746)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) 3 is 0+1
Fail: (9) 3 is 0+1
Redo: (9) length_2(_5726, _5746)
Unify: (9) length_2([_5730|_5732], _5752)
Call: (10) length_2(_5732, _5752)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _5756 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_5730], 1)
Call: (9) 3 is 1+1
Fail: (9) 3 is 1+1
Redo: (10) length_2(_5732, _5752)
Unify: (10) length_2([_5736|_5738], _5758)
Call: (11) length_2(_5738, _5758)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _5762 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_5736], 1)
Call: (10) _5768 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_5730, _5736], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736]
Action (h for help) ? abort
% Execution Aborted
4.
[trace] ?- length_2([1,2,3],3).
Call: (8) length_2([1, 2, 3], 3)
Unify: (8) length_2([1, 2, 3], 3)
Call: (9) length_2([2, 3], _2058)
Unify: (9) length_2([2, 3], _2058)
Call: (10) length_2([3], _2058)
Unify: (10) length_2([3], _2058)
Call: (11) length_2(, _2058)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2062 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2068 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
true.
[trace] ?- length_2([1,2,3],5).
Call: (8) length_2([1, 2, 3], 5)
Unify: (8) length_2([1, 2, 3], 5)
Call: (9) length_2([2, 3], _2442)
Unify: (9) length_2([2, 3], _2442)
Call: (10) length_2([3], _2442)
Unify: (10) length_2([3], _2442)
Call: (11) length_2(, _2442)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2446 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2452 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 5 is 2+1
Fail: (9) 5 is 2+1
Fail: (8) length_2([1, 2, 3], 5)
false.
and to turn the trace off
[trace] ?- notrace.
true.
[debug] ?- nodebug.
true.
I won't go through each of the lines in the trace output, but if you understand syntactic unification and can follow the trace, after working through the examples given you will see how variables in Prolog are unified resulting in different modes when compared to imperative programming.
Remember that variables are only bound once in Prolog, and never reassigned, and that the numbers on the left in the trace in parenthesis, e.g. (10), are the stack level, so when a call is made to a predicate again, a new set of variables are made available, and while it may seem the are being reassigned a value, it is actually another variable in the stack, just in a different stack frame.
As an aside when learning Prolog one piece of advise I give is that it is easier to learn if you set aside what you know about imperative and functional programming, except for maybe recursion, and start from the ground up with unification and then backward chaining.
If you can read OCaml, here is a simplified version of unification and backward chaining. Note that this is not a Prolog as it does not have list or the cut operator but if you can understand it, then the ways of unification and backward chaining become apparent.
I have to add that I am not totally satisfied with my answer as I know you are a beginner and this answer is to much information to digest and requires a lot of work on your part to work through the 4 trace examples. However it does answer the question and gives a practical example with more than enough meat on the bone. I am working on trying to think of a better example which would include logical purity and that demonstrates that not only unification but relationships are key to how multiple modes can be accomplishes in one predicate. Be glad I didn't use general relativity as paraphrased by the relativist John Archibald Wheeler, spacetime tells matter how to move; matter tells spacetime how to curve
.
I don't understand how I can do both with one function.
Yes, at first this seems odd, but then once you get the hang of it, you miss it in other languages.
The word you want to remember when referencing this is: mode
Also see Mercury Modes reference for more detail related to the Mercury programming language.
In Prolog an argument can be an input, and output, or both used as an input or output depending upon how it is called.
In Type, mode and determinism declaration headers at the bottom is listed 4 examples.
- length(+List:list, -Length:int) is det.
- length(?List:list, -Length:int) is nondet.
- length(?List:list, +Length:int) is det.
- True if List is a list of length Length.
and the definition of length/2
shows
length(?List, ?Int)
meaning
that for the List
argument, the list can be bound or unbound, and
that for the Int
argument, the value can be bound or unbound.
So for the two arguments with two options there are four ways to use length/2
Here they are listed again but in actual usage.
1.
length(+List:list, -Length:int) is det.
in this case List is bound and Length is unbound and always gives one answer.
?- length([1,2,3],N).
N = 3.
2.
length(?List:list, -Length:int) is nondet.
in this case List is unbound and Length is unbound and can return any number of answers.
?- length(List,N).
List = ,
N = 0 ;
List = [_5362],
N = 1 ;
List = [_5362, _5368],
N = 2 ;
List = [_5362, _5368, _5374],
N = 3 ;
List = [_5362, _5368, _5374, _5380],
N = 4 ;
List = [_5362, _5368, _5374, _5380, _5386],
N = 5
...
3.
length(?List:list, +Length:int) is det.
in this case List is unbound and Length is bound and always gives one answer.
?- length(List,4).
List = [_5332, _5338, _5344, _5350].
4.
True if List is a list of length Length.
in this case List is bound and Length is bound and always acts as predicate to return either true
or false
.
?- length([1,2,3],3).
true.
?- length([1,2,3],5).
false.
So how is this possible?
Prolog uses syntactic unification (↦) and NOT assignment (=).
If we look at the source code for length/2
using listing/1
we get
?- listing(length/2).
system:length(B, A) :-
var(A), !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> C==A,
'$length3'(C, A, D)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(B, A) :-
integer(A),
A>=0, !,
'$skip_list'(D, B, C),
( C==
-> A=D
; var(C)
-> E is A-D,
'$length'(C, E)
; throw(error(type_error(list, B), context(length/2, _)))
).
system:length(_, A) :-
integer(A), !,
throw(error(domain_error(not_less_than_zero, A),
context(length/2, _))).
system:length(_, A) :-
throw(error(type_error(integer, A), context(length/2, _))).
which is too much detail but does do all 4 modes correctly.
To make it easier to understand we will use this version, but it doesn't support 1 of the modes correctly but it does do more than one mode so it works good enough to demonstrate.
length_2( , 0 ).
length_2([_|Xs] , L ) :-
length_2(Xs,N),
L is N+1 .
Now to see the unification in action we will use the trace feature of SWI-Prolog and to enable all of the ports for the box model use visible/1 and so as not to stop it when running use leash/1.
?- visible(+all),leash(-all).
?- trace.
1.
[trace] ?- length_2([1,2,3],N).
Call: (8) length_2([1, 2, 3], _2352)
Unify: (8) length_2([1, 2, 3], _2352)
Call: (9) length_2([2, 3], _2580)
Unify: (9) length_2([2, 3], _2580)
Call: (10) length_2([3], _2580)
Unify: (10) length_2([3], _2580)
Call: (11) length_2(, _2580)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2584 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2590 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) _2352 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
N = 3.
2.
[trace] ?- length_2(List,N).
Call: (8) length_2(_2296, _2298)
Unify: (8) length_2(, 0)
Exit: (8) length_2(, 0)
List = ,
N = 0 ;
Redo: (8) length_2(_2296, _2298)
Unify: (8) length_2([_2528|_2530], _2298)
Call: (9) length_2(_2530, _2550)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) _2298 is 0+1
Exit: (9) 1 is 0+1
Exit: (8) length_2([_2528], 1)
List = [_2528],
N = 1 ;
Redo: (9) length_2(_2530, _2550)
Unify: (9) length_2([_2534|_2536], _2556)
Call: (10) length_2(_2536, _2556)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _2560 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_2534], 1)
Call: (9) _2298 is 1+1
Exit: (9) 2 is 1+1
Exit: (8) length_2([_2528, _2534], 2)
List = [_2528, _2534],
N = 2 ;
Redo: (10) length_2(_2536, _2556)
Unify: (10) length_2([_2540|_2542], _2562)
Call: (11) length_2(_2542, _2562)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2566 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_2540], 1)
Call: (10) _2572 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_2534, _2540], 2)
Call: (9) _2298 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_2528, _2534, _2540], 3)
List = [_2528, _2534, _2540],
N = 3
3.
[trace] ?- length_2(List,3).
Call: (8) length_2(_5534, 3)
Unify: (8) length_2([_5724|_5726], 3)
Call: (9) length_2(_5726, _5746)
Unify: (9) length_2(, 0)
Exit: (9) length_2(, 0)
Call: (9) 3 is 0+1
Fail: (9) 3 is 0+1
Redo: (9) length_2(_5726, _5746)
Unify: (9) length_2([_5730|_5732], _5752)
Call: (10) length_2(_5732, _5752)
Unify: (10) length_2(, 0)
Exit: (10) length_2(, 0)
Call: (10) _5756 is 0+1
Exit: (10) 1 is 0+1
Exit: (9) length_2([_5730], 1)
Call: (9) 3 is 1+1
Fail: (9) 3 is 1+1
Redo: (10) length_2(_5732, _5752)
Unify: (10) length_2([_5736|_5738], _5758)
Call: (11) length_2(_5738, _5758)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _5762 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([_5736], 1)
Call: (10) _5768 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([_5730, _5736], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([_5724, _5730, _5736], 3)
List = [_5724, _5730, _5736]
Action (h for help) ? abort
% Execution Aborted
4.
[trace] ?- length_2([1,2,3],3).
Call: (8) length_2([1, 2, 3], 3)
Unify: (8) length_2([1, 2, 3], 3)
Call: (9) length_2([2, 3], _2058)
Unify: (9) length_2([2, 3], _2058)
Call: (10) length_2([3], _2058)
Unify: (10) length_2([3], _2058)
Call: (11) length_2(, _2058)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2062 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2068 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 3 is 2+1
Exit: (9) 3 is 2+1
Exit: (8) length_2([1, 2, 3], 3)
true.
[trace] ?- length_2([1,2,3],5).
Call: (8) length_2([1, 2, 3], 5)
Unify: (8) length_2([1, 2, 3], 5)
Call: (9) length_2([2, 3], _2442)
Unify: (9) length_2([2, 3], _2442)
Call: (10) length_2([3], _2442)
Unify: (10) length_2([3], _2442)
Call: (11) length_2(, _2442)
Unify: (11) length_2(, 0)
Exit: (11) length_2(, 0)
Call: (11) _2446 is 0+1
Exit: (11) 1 is 0+1
Exit: (10) length_2([3], 1)
Call: (10) _2452 is 1+1
Exit: (10) 2 is 1+1
Exit: (9) length_2([2, 3], 2)
Call: (9) 5 is 2+1
Fail: (9) 5 is 2+1
Fail: (8) length_2([1, 2, 3], 5)
false.
and to turn the trace off
[trace] ?- notrace.
true.
[debug] ?- nodebug.
true.
I won't go through each of the lines in the trace output, but if you understand syntactic unification and can follow the trace, after working through the examples given you will see how variables in Prolog are unified resulting in different modes when compared to imperative programming.
Remember that variables are only bound once in Prolog, and never reassigned, and that the numbers on the left in the trace in parenthesis, e.g. (10), are the stack level, so when a call is made to a predicate again, a new set of variables are made available, and while it may seem the are being reassigned a value, it is actually another variable in the stack, just in a different stack frame.
As an aside when learning Prolog one piece of advise I give is that it is easier to learn if you set aside what you know about imperative and functional programming, except for maybe recursion, and start from the ground up with unification and then backward chaining.
If you can read OCaml, here is a simplified version of unification and backward chaining. Note that this is not a Prolog as it does not have list or the cut operator but if you can understand it, then the ways of unification and backward chaining become apparent.
I have to add that I am not totally satisfied with my answer as I know you are a beginner and this answer is to much information to digest and requires a lot of work on your part to work through the 4 trace examples. However it does answer the question and gives a practical example with more than enough meat on the bone. I am working on trying to think of a better example which would include logical purity and that demonstrates that not only unification but relationships are key to how multiple modes can be accomplishes in one predicate. Be glad I didn't use general relativity as paraphrased by the relativist John Archibald Wheeler, spacetime tells matter how to move; matter tells spacetime how to curve
.
edited Nov 20 '18 at 1:29
answered Nov 20 '18 at 0:45
Guy CoderGuy Coder
15.6k43984
15.6k43984
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
add a comment |
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I am thinking Non-transitive dice might work as an example, I just don't know if I can make it simple enough.
– Guy Coder
Nov 20 '18 at 1:41
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
I might try just using Celsius to Fahrenheit and the reverse but it is getting late. The nice thing about this example is that when both values are a variable, it returns an equation, that is something few programming languages are capable of doing..
– Guy Coder
Nov 20 '18 at 1:46
add a comment |
I have been doing Prolog for a few years and I feel like my comfort with and understanding of different instantiation patterns has come in several discrete steps. The first significant hurdle is of course recursion, which is all you really need to get your head around for this problem. Basically, you know that your table assignment for two people is correct if they speak the same language, so this is your base case:
table_seating([X,Y]) :- speaksSame(X, Y).
So, what if you add a third person to the mix? You'd do something like this:
% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).
Now hopefully you notice that your new work is speaksSame(A,X)
but your old work has remained the same. Let's just worry about the new person and trust that we could have handled it for the remainder of the list.
table_seating([X,Y,Z|Rest]) :-
speaksSame(X, Y),
table_seating([Y,Z|Rest]).
What we're doing here is saying, assume we have at least three items in the list. Then if the first two speak the same language, and the next two plus the rest can be seated, then they can all be seated. You can always take a correctly-seated table and add a person to the front of the table, if they speak the same language as the person currently at the front of the table.
Recursion almost always has this flavor: how can I set up the minimal correct situation, the base case, and then, how can I add one more thing to that situation correctly?
Now what's interesting is that if you supply a list of some length to this predicate, it will "just work" and produce solutions of that length. Try it like so:
?- length(L, 6), table_seating(L).
You will probably get solutions (I assume speaksSame/2
will generate solutions). This is because all Prolog knows about these variables, it knows about because of your speaksSame/2
predicate. So as long as you use predicates that have many instantiation patterns in your predicates and don't force assignments to things or order things strangely, often your predicates will inherit these modes. This is a reason I recommend people use succ/2
instead of N is N0 + 1
or N0 is N - 1
, because succ/2
defines a relationship between two numbers rather than performing some arithmetic (clpfd takes this idea much, much further).
add a comment |
I have been doing Prolog for a few years and I feel like my comfort with and understanding of different instantiation patterns has come in several discrete steps. The first significant hurdle is of course recursion, which is all you really need to get your head around for this problem. Basically, you know that your table assignment for two people is correct if they speak the same language, so this is your base case:
table_seating([X,Y]) :- speaksSame(X, Y).
So, what if you add a third person to the mix? You'd do something like this:
% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).
Now hopefully you notice that your new work is speaksSame(A,X)
but your old work has remained the same. Let's just worry about the new person and trust that we could have handled it for the remainder of the list.
table_seating([X,Y,Z|Rest]) :-
speaksSame(X, Y),
table_seating([Y,Z|Rest]).
What we're doing here is saying, assume we have at least three items in the list. Then if the first two speak the same language, and the next two plus the rest can be seated, then they can all be seated. You can always take a correctly-seated table and add a person to the front of the table, if they speak the same language as the person currently at the front of the table.
Recursion almost always has this flavor: how can I set up the minimal correct situation, the base case, and then, how can I add one more thing to that situation correctly?
Now what's interesting is that if you supply a list of some length to this predicate, it will "just work" and produce solutions of that length. Try it like so:
?- length(L, 6), table_seating(L).
You will probably get solutions (I assume speaksSame/2
will generate solutions). This is because all Prolog knows about these variables, it knows about because of your speaksSame/2
predicate. So as long as you use predicates that have many instantiation patterns in your predicates and don't force assignments to things or order things strangely, often your predicates will inherit these modes. This is a reason I recommend people use succ/2
instead of N is N0 + 1
or N0 is N - 1
, because succ/2
defines a relationship between two numbers rather than performing some arithmetic (clpfd takes this idea much, much further).
add a comment |
I have been doing Prolog for a few years and I feel like my comfort with and understanding of different instantiation patterns has come in several discrete steps. The first significant hurdle is of course recursion, which is all you really need to get your head around for this problem. Basically, you know that your table assignment for two people is correct if they speak the same language, so this is your base case:
table_seating([X,Y]) :- speaksSame(X, Y).
So, what if you add a third person to the mix? You'd do something like this:
% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).
Now hopefully you notice that your new work is speaksSame(A,X)
but your old work has remained the same. Let's just worry about the new person and trust that we could have handled it for the remainder of the list.
table_seating([X,Y,Z|Rest]) :-
speaksSame(X, Y),
table_seating([Y,Z|Rest]).
What we're doing here is saying, assume we have at least three items in the list. Then if the first two speak the same language, and the next two plus the rest can be seated, then they can all be seated. You can always take a correctly-seated table and add a person to the front of the table, if they speak the same language as the person currently at the front of the table.
Recursion almost always has this flavor: how can I set up the minimal correct situation, the base case, and then, how can I add one more thing to that situation correctly?
Now what's interesting is that if you supply a list of some length to this predicate, it will "just work" and produce solutions of that length. Try it like so:
?- length(L, 6), table_seating(L).
You will probably get solutions (I assume speaksSame/2
will generate solutions). This is because all Prolog knows about these variables, it knows about because of your speaksSame/2
predicate. So as long as you use predicates that have many instantiation patterns in your predicates and don't force assignments to things or order things strangely, often your predicates will inherit these modes. This is a reason I recommend people use succ/2
instead of N is N0 + 1
or N0 is N - 1
, because succ/2
defines a relationship between two numbers rather than performing some arithmetic (clpfd takes this idea much, much further).
I have been doing Prolog for a few years and I feel like my comfort with and understanding of different instantiation patterns has come in several discrete steps. The first significant hurdle is of course recursion, which is all you really need to get your head around for this problem. Basically, you know that your table assignment for two people is correct if they speak the same language, so this is your base case:
table_seating([X,Y]) :- speaksSame(X, Y).
So, what if you add a third person to the mix? You'd do something like this:
% for exposition only; do not include this clause
table_seating([A,X,Y]) :- speaksSame(A,X), speaksSame(X, Y).
Now hopefully you notice that your new work is speaksSame(A,X)
but your old work has remained the same. Let's just worry about the new person and trust that we could have handled it for the remainder of the list.
table_seating([X,Y,Z|Rest]) :-
speaksSame(X, Y),
table_seating([Y,Z|Rest]).
What we're doing here is saying, assume we have at least three items in the list. Then if the first two speak the same language, and the next two plus the rest can be seated, then they can all be seated. You can always take a correctly-seated table and add a person to the front of the table, if they speak the same language as the person currently at the front of the table.
Recursion almost always has this flavor: how can I set up the minimal correct situation, the base case, and then, how can I add one more thing to that situation correctly?
Now what's interesting is that if you supply a list of some length to this predicate, it will "just work" and produce solutions of that length. Try it like so:
?- length(L, 6), table_seating(L).
You will probably get solutions (I assume speaksSame/2
will generate solutions). This is because all Prolog knows about these variables, it knows about because of your speaksSame/2
predicate. So as long as you use predicates that have many instantiation patterns in your predicates and don't force assignments to things or order things strangely, often your predicates will inherit these modes. This is a reason I recommend people use succ/2
instead of N is N0 + 1
or N0 is N - 1
, because succ/2
defines a relationship between two numbers rather than performing some arithmetic (clpfd takes this idea much, much further).
edited Nov 20 '18 at 7:36
Will Ness
45.5k468124
45.5k468124
answered Nov 20 '18 at 6:57
Daniel LyonsDaniel Lyons
17.6k23863
17.6k23863
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53383978%2fprolog-reverse-lookup-and-input-validation-at-the-same-time%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown