info
Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Critique of Prolog Program
137 views
Skip to first unread message
Ronald Modesitt
Feb 1, 2018, 11:55:12 PM2/1/18
to
I would appreciate it if Markus or another Prolog expert would look at my solution to the following problem from "Techniques of Prolog Programming ..." by Te Van Le, and show me a better Prolog approach.
Please note, this IS NOT a school assignment. I am a retired engineer learning Prolog on my own.
Problem 1.5
Convert the following information into a Prolog program:
- Everyone born in Australia is an Australian citizen.
- Children of Australian citizens are Australian citizens.
- Peter is John's father and was born in New Zealand.
- Mary is John's mother and was born in Australia.
Write Prolog queries to the following questions:
- Is John an Australian citizen?
- Who are Australian citizens?
My Solution:
citizen(X,Y) :- child(X,Z),
bornIn(Z,Y);
bornIn(X,Y).
child(john,mary).
child(john,peter).
bornIn(mary, australia).
bornIn(peter, newZeland).
The queries
citizen(john,australia). Yields true
citizen(X,australia) yields:
X=john;
X=mary.
Please note, this IS NOT a school assignment. I am a retired engineer learning Prolog on my own.
Problem 1.5
Convert the following information into a Prolog program:
- Everyone born in Australia is an Australian citizen.
- Children of Australian citizens are Australian citizens.
- Peter is John's father and was born in New Zealand.
- Mary is John's mother and was born in Australia.
Write Prolog queries to the following questions:
- Is John an Australian citizen?
- Who are Australian citizens?
My Solution:
citizen(X,Y) :- child(X,Z),
bornIn(Z,Y);
bornIn(X,Y).
child(john,mary).
child(john,peter).
bornIn(mary, australia).
bornIn(peter, newZeland).
The queries
citizen(john,australia). Yields true
citizen(X,australia) yields:
X=john;
X=mary.
Joachim Schimpf
Feb 2, 2018, 4:57:06 AM2/2/18
to
On 02/02/18 04:55, Ronald Modesitt wrote:
> I would appreciate it if Markus or another Prolog expert would look at my solution to the following problem from "Techniques of Prolog Programming ..." by Te Van Le, and show me a better Prolog approach.
>
> Please note, this IS NOT a school assignment. I am a retired engineer learning Prolog on my own.
>
> Problem 1.5
>
> Convert the following information into a Prolog program:
> - Everyone born in Australia is an Australian citizen.
> - Children of Australian citizens are Australian citizens.
> - Peter is John's father and was born in New Zealand.
> - Mary is John's mother and was born in Australia.
>
> Write Prolog queries to the following questions:
> - Is John an Australian citizen?
> - Who are Australian citizens?
>
> My Solution:
>
> citizen(X,Y) :- child(X,Z),
> bornIn(Z,Y);
>
> bornIn(X,Y).
>
> child(john,mary).
> child(john,peter).
> bornIn(mary, australia).
> bornIn(peter, newZeland).
Let me start with the style: a semicolon (disjunction) should always
> I would appreciate it if Markus or another Prolog expert would look at my solution to the following problem from "Techniques of Prolog Programming ..." by Te Van Le, and show me a better Prolog approach.
>
> Please note, this IS NOT a school assignment. I am a retired engineer learning Prolog on my own.
>
> Problem 1.5
>
> Convert the following information into a Prolog program:
> - Everyone born in Australia is an Australian citizen.
> - Children of Australian citizens are Australian citizens.
> - Peter is John's father and was born in New Zealand.
> - Mary is John's mother and was born in Australia.
>
> Write Prolog queries to the following questions:
> - Is John an Australian citizen?
> - Who are Australian citizens?
>
> My Solution:
>
> citizen(X,Y) :- child(X,Z),
> bornIn(Z,Y);
>
> bornIn(X,Y).
>
> child(john,mary).
> child(john,peter).
> bornIn(mary, australia).
> bornIn(peter, newZeland).
be formatted in a very visible way, usually like this:
citizen(X,Y) :-
(
child(X,Z),
bornIn(Z,Y)
;
bornIn(X,Y)
).
If a clause consists only of a disjunction, it is often more neater
to write separate clauses instead:
citizen(X,Y) :- child(X,Z), bornIn(Z,Y).
citizen(X,Y) :- bornIn(X,Y).
Traditionally, in Prolog we use CamelCaseForVariableNames, but
underscore_separated_words_for_functors.
As for the logic:
You have only incompletely captured the rule
"Children of Australian citizens are Australian citizens".
On the other hand, your code also computes New Zealand citizenship,
which the problem statement says nothing about.
Hope that helps,
Joachim
Julio Di Egidio
Feb 2, 2018, 5:22:31 AM2/2/18
to
On Friday, 2 February 2018 05:55:12 UTC+1, Ronald Modesitt wrote:
> Convert the following information into a Prolog program:
> - Everyone born in Australia is an Australian citizen.
citizenAustralia(Person) IF bornAustralia(Person).
> Convert the following information into a Prolog program:
> - Everyone born in Australia is an Australian citizen.
Pretty poor exercises if you ask me...
Julio
iamj...@gmail.com
Feb 2, 2018, 5:44:32 AM2/2/18
to
Might be it will do Ronald some good to trace how Prolog arrives
such conclusion:
Recap and label the rules you have given to Prolog:
citizen(X,Y) :- child(X,Z), bornIn(Z,Y). /* rule 1 */
citizen(X,Y) :- bornIn(X, Y). /* rule 2 */
child(john,mary). /* rule 3 */
child(john,peter). /* rule 4 */
bornIn(mary, australia). /* rule 5 */
bornIn(peter, newZeland). /* rule 6 */
% Let's start with your query:
citizen(X, australia).
% To Prolog, you have indeed "instantiated" Y to 'australia':
citizen(X, Y=australia).
% Prolog then starts following rule 1:
citizen(X, Y=australia) :- child(X, Z), bornIn(Z,Y=australia).
% By rule 5, Z is found:
citizen(X, Y=australia) :- child(X, Z=mary), bornIn(Z=mary,Y=australia).
% By rule 3, X is found:
citizen(X=john, Y=australia) :- child(X=john, Z=mary), bornIn(Z=mary,Y=australia).
% Thus it founds X=john, perfect.
% Prolog would then tries to "backtrack" the rules it have
% applied to see if more alternative could be found:
% By rule 3, any more X can be matched? No...
% By rule 5, any more Z can be matched? No...
% By rule 1, any more Y can be matched? No...
% Back to beginning, then Prolog applies rule 2:
citizen(X, Y=australia) :- bornIn(X, Y=australia).
% By rule 5, X is found:
citizen(X=mary, Y=australia) :- bornIn(X=mary, Y=australia).
% Thus X=mary. Now you got what you have!
This is one aspect of how Prolog works: a diligent backtracking machine.
Jim
such conclusion:
Recap and label the rules you have given to Prolog:
citizen(X,Y) :- child(X,Z), bornIn(Z,Y). /* rule 1 */
citizen(X,Y) :- bornIn(X, Y). /* rule 2 */
child(john,mary). /* rule 3 */
child(john,peter). /* rule 4 */
bornIn(mary, australia). /* rule 5 */
bornIn(peter, newZeland). /* rule 6 */
% Let's start with your query:
citizen(X, australia).
% To Prolog, you have indeed "instantiated" Y to 'australia':
citizen(X, Y=australia).
% Prolog then starts following rule 1:
citizen(X, Y=australia) :- child(X, Z), bornIn(Z,Y=australia).
% By rule 5, Z is found:
citizen(X, Y=australia) :- child(X, Z=mary), bornIn(Z=mary,Y=australia).
% By rule 3, X is found:
citizen(X=john, Y=australia) :- child(X=john, Z=mary), bornIn(Z=mary,Y=australia).
% Thus it founds X=john, perfect.
% Prolog would then tries to "backtrack" the rules it have
% applied to see if more alternative could be found:
% By rule 3, any more X can be matched? No...
% By rule 5, any more Z can be matched? No...
% By rule 1, any more Y can be matched? No...
% Back to beginning, then Prolog applies rule 2:
citizen(X, Y=australia) :- bornIn(X, Y=australia).
% By rule 5, X is found:
citizen(X=mary, Y=australia) :- bornIn(X=mary, Y=australia).
% Thus X=mary. Now you got what you have!
This is one aspect of how Prolog works: a diligent backtracking machine.
Jim
iamj...@gmail.com
Feb 2, 2018, 6:16:01 AM2/2/18
to
And I think constraint logic programming (CLP) takes Prolog to another level. A less difficult to grasp example is N-queen:
https://www.metalevel.at/queens/
The pure Prolog method (i.e. not using CLP library at all) will still work but it probably takes forever to yield even the first solution.
Nonetheless I recommend having an understanding on backtracking / unification before diving into CLP. Otherwise it could add more confusion to learner.
Jim
https://www.metalevel.at/queens/
The pure Prolog method (i.e. not using CLP library at all) will still work but it probably takes forever to yield even the first solution.
Nonetheless I recommend having an understanding on backtracking / unification before diving into CLP. Otherwise it could add more confusion to learner.
Jim
Ronald Modesitt
Feb 2, 2018, 10:31:32 AM2/2/18
to
Jim,
Many thanks for your comments. I am using SWI-Prolog. However, I am such a beginner I didn't realize I was using the CLP functionality provided. It is obvious I have a lot to learn! I appreciate the patience and willingness of Prolog experts like yourself to help a beginner.
Ron
Many thanks for your comments. I am using SWI-Prolog. However, I am such a beginner I didn't realize I was using the CLP functionality provided. It is obvious I have a lot to learn! I appreciate the patience and willingness of Prolog experts like yourself to help a beginner.
Ron
Ronald Modesitt
Feb 2, 2018, 10:33:46 AM2/2/18
to
Again, many thanks.
Ronald Modesitt
Feb 2, 2018, 10:39:28 AM2/2/18
to
Julio,
Thank you for replying. I am such a beginner that I don't recognize a good exercise from a poor one. I would appreciate it if you could direct me to a source containing quality Prolog exercises.
My comments to Jim below also apply to yourself. I truly appreciate the help this forum provides to beginners like me. At my age (71) I might not live long enough to understand Prolog without the help of this forum and experts like yourself.
Ron
Thank you for replying. I am such a beginner that I don't recognize a good exercise from a poor one. I would appreciate it if you could direct me to a source containing quality Prolog exercises.
My comments to Jim below also apply to yourself. I truly appreciate the help this forum provides to beginners like me. At my age (71) I might not live long enough to understand Prolog without the help of this forum and experts like yourself.
Ron
burs...@gmail.com
Feb 2, 2018, 10:52:03 AM2/2/18
to
Well you were not using CLP functionality. You only
use CLP functionality if you place a CLP(X) module
import at the beginning of your code.
Like for finite domains:
:- use_module(library(clpfd().
/* in Jekejeke Prolog :- use_module(library(finite/clpfd)) */
Like for SAT solver:
:- use_module(library(clpb)).
/* in Jekejeke Prolog :- use_module(library(finite/clpb)) */
You have then available additional predicates which
are little bit more complete or little bit more efficient
like if you would directly model it in the herbrand domain.
For example finite domain you could model the positive
integers as peano z, s(z), s(s(z)), in the herbrand domain,
and SAT you could model as true and false in the herbrand domain.
But since using CLP(X) is as simple as a use_module, yes,
its more or less really easy to use. So easy to use that
other languages such as Python, Java, Closure, Haskell, etc..
could only dream of. Especially since CLP(X) integrates with
the existing Prolog logical variables. At least as far as constant
and variable instantiations can communicate with normal Prolog flow.
use CLP functionality if you place a CLP(X) module
import at the beginning of your code.
Like for finite domains:
:- use_module(library(clpfd().
/* in Jekejeke Prolog :- use_module(library(finite/clpfd)) */
Like for SAT solver:
:- use_module(library(clpb)).
/* in Jekejeke Prolog :- use_module(library(finite/clpb)) */
You have then available additional predicates which
are little bit more complete or little bit more efficient
like if you would directly model it in the herbrand domain.
For example finite domain you could model the positive
integers as peano z, s(z), s(s(z)), in the herbrand domain,
and SAT you could model as true and false in the herbrand domain.
But since using CLP(X) is as simple as a use_module, yes,
its more or less really easy to use. So easy to use that
other languages such as Python, Java, Closure, Haskell, etc..
could only dream of. Especially since CLP(X) integrates with
the existing Prolog logical variables. At least as far as constant
and variable instantiations can communicate with normal Prolog flow.
burs...@gmail.com
Feb 2, 2018, 11:01:29 AM2/2/18
to
For example the integration with Prolog variables
easily allows defininig predicates that make use
of constraint variables. Here is an example:
Without constraint variables:
sum([X|Y], S) :- sum(Y, H), S is X+H.
sum([], 0).
?- sum([1,2,3],X).
X = 6
?- sum([1,X,3],6).
ERROR: Arguments are not sufficiently instantiated
Now the same with FD constraint variables:
:- use_module(library(clpfd)).
sum([X|Y], S) :- sum(Y, H), S #= X+H.
sum([], 0).
?- sum([1,2,3],X).
X = 6.
?- sum([1,X,3],6).
X = 2.
At least a nice show case that purports the illusion
of something that is more intelligent than
standard Prolog execution...
easily allows defininig predicates that make use
of constraint variables. Here is an example:
Without constraint variables:
sum([X|Y], S) :- sum(Y, H), S is X+H.
sum([], 0).
?- sum([1,2,3],X).
X = 6
?- sum([1,X,3],6).
ERROR: Arguments are not sufficiently instantiated
Now the same with FD constraint variables:
:- use_module(library(clpfd)).
sum([X|Y], S) :- sum(Y, H), S #= X+H.
sum([], 0).
?- sum([1,2,3],X).
X = 6.
?- sum([1,X,3],6).
X = 2.
At least a nice show case that purports the illusion
of something that is more intelligent than
standard Prolog execution...
Ronald Modesitt
Feb 2, 2018, 12:30:04 PM2/2/18
to
Joachim,
Thank you for cleaning up the formatting, especially for the ";" case.
My past experience with programming (Python, C) usually guided me to create a function that was flexible. That was the reason for not specifying "australia" specifically but allowing a variable. I agree that it did not meet the requirements of the problem statement. Did you think there was another issue with my solution?
Ron
Thank you for cleaning up the formatting, especially for the ";" case.
My past experience with programming (Python, C) usually guided me to create a function that was flexible. That was the reason for not specifying "australia" specifically but allowing a variable. I agree that it did not meet the requirements of the problem statement. Did you think there was another issue with my solution?
Ron
Joachim Schimpf
Feb 2, 2018, 12:53:03 PM2/2/18
to
On 02/02/18 17:30, Ronald Modesitt wrote:
> Did you think there was another issue with my solution?
If john had a child, i.e. if you added the fact
> Did you think there was another issue with my solution?
child(alan,john).
the query
?- citizen(alan,australia).
should succeed, but doesn't!
iamj...@gmail.com
Feb 3, 2018, 3:12:03 AM2/3/18
to
Hi Ronald,
Sorry for my lousy grammar in first reply. It was written in quite a hurry.
Probably I should not have mentioned CLP as you have just started with Prolog.
Here is the way I acquired Prolog:
1. Have a lot of practical sessions. I followed exercises in <Prolog Experiments in Discrete Mathematics, Logic, and Computability>, authored by James L. Hein.
2. When bumping into mysterious behaviour of Prolog which needed elaboration, I counsulted textbook such as <Prolog Programming for Artificial Intelligence> by Ivan Bratko. Despite the "AI taste" suggested by the name, it does introduces Prolog from beginning.
3. Ask for help/discussion in comp.lang.prolog would be good, I believe.
Hope that helps.
Jim
Sorry for my lousy grammar in first reply. It was written in quite a hurry.
Probably I should not have mentioned CLP as you have just started with Prolog.
Here is the way I acquired Prolog:
1. Have a lot of practical sessions. I followed exercises in <Prolog Experiments in Discrete Mathematics, Logic, and Computability>, authored by James L. Hein.
2. When bumping into mysterious behaviour of Prolog which needed elaboration, I counsulted textbook such as <Prolog Programming for Artificial Intelligence> by Ivan Bratko. Despite the "AI taste" suggested by the name, it does introduces Prolog from beginning.
3. Ask for help/discussion in comp.lang.prolog would be good, I believe.
Hope that helps.
Jim
Julio Di Egidio
Feb 3, 2018, 7:10:04 AM2/3/18
to
On Friday, 2 February 2018 16:39:28 UTC+1, Ronald Modesitt wrote:
I know a good one is The Art of Prolog, anyway I was quick but I did not really
mean to bash the book you are reading (I did find the problem statement a bit
lacking, but never mind, I haven't seen the context): overall I'd say as long as
you feel you are learning, go on with it, it's quite a long journey anyway, and
no one single book or course is going to cover it all. Moreover, I do think
every programmer should learn Prolog: there are three programming language
paradigms, and Prolog is the C of the logical paradigm... in my opinion.
OTOH, I disagree with any naïve equivalence of Prolog with logic proper and the
natural languages: there are historical reasons for it which I do respect, but
in 2018 Prolog is what it is, a programming language with an operational
semantics, period. Indeed at least one thing I'd say: that if a book does not
make at least clear the distinction and exact meaning of the denotational (was
that the name?) vs the operational semantics of Prolog, then it's worse than
useless...
(One suggestion is please quote the relevant context when replying, otherwise
following up becomes difficult. Usually not the whole post, just the headers
and the parts you are directly replying to.)
For now, I wish you fun with Prolog and welcome to the group,
Julio
> Julio,
> Thank you for replying. I am such a beginner that I don't recognize a good
> exercise from a poor one. I would appreciate it if you could direct me to a
> source containing quality Prolog exercises.
Hi Ronald,
> Thank you for replying. I am such a beginner that I don't recognize a good
> exercise from a poor one. I would appreciate it if you could direct me to a
> source containing quality Prolog exercises.
I know a good one is The Art of Prolog, anyway I was quick but I did not really
mean to bash the book you are reading (I did find the problem statement a bit
lacking, but never mind, I haven't seen the context): overall I'd say as long as
you feel you are learning, go on with it, it's quite a long journey anyway, and
no one single book or course is going to cover it all. Moreover, I do think
every programmer should learn Prolog: there are three programming language
paradigms, and Prolog is the C of the logical paradigm... in my opinion.
OTOH, I disagree with any naïve equivalence of Prolog with logic proper and the
natural languages: there are historical reasons for it which I do respect, but
in 2018 Prolog is what it is, a programming language with an operational
semantics, period. Indeed at least one thing I'd say: that if a book does not
make at least clear the distinction and exact meaning of the denotational (was
that the name?) vs the operational semantics of Prolog, then it's worse than
useless...
(One suggestion is please quote the relevant context when replying, otherwise
following up becomes difficult. Usually not the whole post, just the headers
and the parts you are directly replying to.)
For now, I wish you fun with Prolog and welcome to the group,
Julio
burs...@gmail.com
Feb 3, 2018, 8:56:00 AM2/3/18
to
What is the operational semantics of CLP(X). Is it the
same for CLP(B) and CLP(FD)?
same for CLP(B) and CLP(FD)?
burs...@gmail.com
Feb 3, 2018, 9:03:43 AM2/3/18
to
In my opinion Prolog is THE example of a language without
a fixed operational semantics. Its very subtle for ordinary
Prolog, but it exists. For example if you would
measure operationally visible the unifications that Prolog
is doing, than with and without indexing, with and without
choice point elimination, with and without pre-cutting or
post-cutting (yeah you can implement cut differently), there
is a totally different behaviour. The same holds much
more for CLP(X).
Different CLP(X) might behaviourally do completely different
things during labeling, use totally different problem
representations internally, so that the specification
for such libraries must be on a much higher level than
just some operational behaviour. So that mathematical logic
becomes an indispensable tool.
a fixed operational semantics. Its very subtle for ordinary
Prolog, but it exists. For example if you would
measure operationally visible the unifications that Prolog
is doing, than with and without indexing, with and without
choice point elimination, with and without pre-cutting or
post-cutting (yeah you can implement cut differently), there
is a totally different behaviour. The same holds much
more for CLP(X).
Different CLP(X) might behaviourally do completely different
things during labeling, use totally different problem
representations internally, so that the specification
for such libraries must be on a much higher level than
just some operational behaviour. So that mathematical logic
becomes an indispensable tool.
burs...@gmail.com
Feb 3, 2018, 9:11:32 AM2/3/18
to
With attributed variables the usually invisible
unification becomes visible. If you freeze a variable
you will see what unification attemps will be
made by the Prolog interpreter, since your user
land code will be executed, the goal that you attached
during freeze to the variable.
This carries over to CLP(X), there unification
becomes visible, not so much for user land. Since
now CLP(X) solver code will be executed when
a variable is woken up. But also CLP(X) might have
different propagation strategies and differently react
to user land unification, so there might be
again some subtle impact. A more clear impact is
seen in CHR, where again user land code will be
executed upon unifications.
This would be all horribly chaotic and divergent,
if there werent some mathematical logic convergent
ideas behind it...
unification becomes visible. If you freeze a variable
you will see what unification attemps will be
made by the Prolog interpreter, since your user
land code will be executed, the goal that you attached
during freeze to the variable.
This carries over to CLP(X), there unification
becomes visible, not so much for user land. Since
now CLP(X) solver code will be executed when
a variable is woken up. But also CLP(X) might have
different propagation strategies and differently react
to user land unification, so there might be
again some subtle impact. A more clear impact is
seen in CHR, where again user land code will be
executed upon unifications.
This would be all horribly chaotic and divergent,
if there werent some mathematical logic convergent
ideas behind it...
Ronald Modesitt
Feb 3, 2018, 9:41:26 AM2/3/18
to
Ron
Barb Knox
Feb 8, 2018, 7:27:44 PM2/8/18
to
On 2/02/18 23:22, Julio Di Egidio wrote:
> On Friday, 2 February 2018 05:55:12 UTC+1, Ronald Modesitt wrote:
>
>> Convert the following information into a Prolog program:
>> - Everyone born in Australia is an Australian citizen.
>
> citizenAustralia(Person) IF bornAustralia(Person).
>
> Pretty poor exercises if you ask me...
What do you dislike about the exercise Is it inconsistent with
> On Friday, 2 February 2018 05:55:12 UTC+1, Ronald Modesitt wrote:
>
>> Convert the following information into a Prolog program:
>> - Everyone born in Australia is an Australian citizen.
>
> citizenAustralia(Person) IF bornAustralia(Person).
>
> Pretty poor exercises if you ask me...
Australia's actual citizenship rules?
I've seen and commented on some truly atrocious exercises, which appear
to have been given out by instructors who are firmly rooted in the
procedural language paradigm (C, Java, etc.)
IMO this Prolog exercise is entirely OK.
> Julio
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | ,008015L080180,022036,029037
| B B a a r b b | ,047045,L014114L4.
| BBB aa a r bbb |
-----------------------------
Barb Knox
Feb 8, 2018, 8:18:18 PM2/8/18
to
On 4/02/18 01:10, Julio Di Egidio wrote:
[...]
"operational") and a declarative semantics, both of which are useful.
The declarative semantics is very useful for (among other things)
explaining recursions to beginners who have a procedural mindset from
earlier exposure to Basic etc.
A simple example is the recursive append predicate:
%% append(?List1, ?List2, ?List1AndList2)
%
% List1AndList2 is the concatenation of List1 and List2
%
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :-
append(Xs, Ys, Zs).
Here's a declarative reading of the code:
Clause 1: Appending an empty list in front of a list equals that list.
Clause 2: Appending [X|Xs] in front of a list equals the result of
appending Xs in front of the list, and then putting X in front of that
result.
This neatly avoids any recursion boggle for beginners. Indeed, it
doesn't even look like programming as they have known it.
After understanding this declarative reading they can then run traces of
append's execution on various examples and more readily understand what
is going procedurally.
> Indeed at least one thing I'd say: that if a book does not
> make at least clear the distinction and exact meaning of the denotational (was
> that the name?)
No. "Denotational semantics" in logic involves mapping syntactic
structures into semantic sets; in programming languages it usually
involves Scott's Domain Theory (which is a denotational semantics in the
logical sense).
> vs the operational semantics of Prolog, then it's worse than
> useless...
Making the distinction between Prolog's declarative and procedural
semantics (semanticses? semantices?) is indeed useful, as in my above
example. But IMO it's not the /sine quo non/ of learning Prolog.
[...]
[...]
> in 2018 Prolog is what it is, a programming language with an operational
> semantics, period.
I strongly disagree. Prolog has *both* a procedural (your
> semantics, period.
"operational") and a declarative semantics, both of which are useful.
The declarative semantics is very useful for (among other things)
explaining recursions to beginners who have a procedural mindset from
earlier exposure to Basic etc.
A simple example is the recursive append predicate:
%% append(?List1, ?List2, ?List1AndList2)
%
% List1AndList2 is the concatenation of List1 and List2
%
append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :-
append(Xs, Ys, Zs).
Here's a declarative reading of the code:
Clause 1: Appending an empty list in front of a list equals that list.
Clause 2: Appending [X|Xs] in front of a list equals the result of
appending Xs in front of the list, and then putting X in front of that
result.
This neatly avoids any recursion boggle for beginners. Indeed, it
doesn't even look like programming as they have known it.
After understanding this declarative reading they can then run traces of
append's execution on various examples and more readily understand what
is going procedurally.
> Indeed at least one thing I'd say: that if a book does not
> make at least clear the distinction and exact meaning of the denotational (was
> that the name?)
structures into semantic sets; in programming languages it usually
involves Scott's Domain Theory (which is a denotational semantics in the
logical sense).
> vs the operational semantics of Prolog, then it's worse than
> useless...
semantics (semanticses? semantices?) is indeed useful, as in my above
example. But IMO it's not the /sine quo non/ of learning Prolog.
[...]
Julio Di Egidio
Feb 9, 2018, 7:44:16 AM2/9/18
to
On Friday, 9 February 2018 02:18:18 UTC+1, Barb Knox wrote:
> On 4/02/18 01:10, Julio Di Egidio wrote:
> [...]
> > in 2018 Prolog is what it is, a programming language with an operational
> > semantics, period.
>
> I strongly disagree. Prolog has *both* a procedural (your
> "operational") and a declarative semantics, both of which are useful.
<snip>
> On 4/02/18 01:10, Julio Di Egidio wrote:
> [...]
> > in 2018 Prolog is what it is, a programming language with an operational
> > semantics, period.
>
> I strongly disagree. Prolog has *both* a procedural (your
> "operational") and a declarative semantics, both of which are useful.
It's operational vs denotational, and you just don't know what you are talking
about.
Julio
Julio Di Egidio
Feb 9, 2018, 7:50:31 AM2/9/18
to
On Friday, 9 February 2018 01:27:44 UTC+1, Barb Knox wrote:
> I've seen and commented on some truly atrocious exercises, which appear
> to have been given out by instructors who are firmly rooted in the
> procedural language paradigm (C, Java, etc.)
I don't know if more atrocious is your condescendence or your plain
> I've seen and commented on some truly atrocious exercises, which appear
> to have been given out by instructors who are firmly rooted in the
> procedural language paradigm (C, Java, etc.)
incompetence. Sure is that a computer scientist who hasn't got his or her
head around the meaning of Donald Knuth's most famous disclaimer is worse
than useless.
*Plonk*
Julio
burs...@gmail.com
Feb 9, 2018, 4:10:00 PM2/9/18
to
Hi,
I nevertheless like your mention of CLP(X). I tried
to find some video, showing an introduction to CLP(X).
But I tried to avoid something from the MiniKanren camp,
which made it more difficult to find a video. But this
video is quite charming, since it offers an end-user
perspective and its from 2015:
"Constraint logic programming is a paradigm that allows
solving hard combinatorial problems with minimal
programming effort. In this workshop you will learn
the basics of the Prolog-based constraint logic
programming system ECLiPSe, solve several puzzles,
and get hints how constraint logic programming can
be useful in your real-life projects."
LambdaConf 2015 - Introduction to Constraint
Logic Programming - Sergii Dymchenko
https://www.youtube.com/watch?v=84amHOgCEe8
Bye
I nevertheless like your mention of CLP(X). I tried
to find some video, showing an introduction to CLP(X).
But I tried to avoid something from the MiniKanren camp,
which made it more difficult to find a video. But this
video is quite charming, since it offers an end-user
perspective and its from 2015:
"Constraint logic programming is a paradigm that allows
solving hard combinatorial problems with minimal
programming effort. In this workshop you will learn
the basics of the Prolog-based constraint logic
programming system ECLiPSe, solve several puzzles,
and get hints how constraint logic programming can
be useful in your real-life projects."
LambdaConf 2015 - Introduction to Constraint
Logic Programming - Sergii Dymchenko
https://www.youtube.com/watch?v=84amHOgCEe8
Bye
burs...@gmail.com
Feb 9, 2018, 7:51:12 PM2/9/18
to
Hi,
Do you mean: "Beware of bugs in the
above code; I have only proved it correct,
not tried it.". -- Knuth
Maybe he shouldn't use paper and pencil
for his proofs, and of course some specs
could be wrong.
Anyway, just had a nice glossing over:
Logic Programming: Operational Semantics
and Proof Theory - James H. Andrews
https://www.era.lib.ed.ac.uk/bitstream/handle/1842/13484/Andrews1991.Pdf
You find a Stack of Stacks model in
it, so its not the usual SLD resolution
explanation of Prolog...
Do you mean: "Beware of bugs in the
above code; I have only proved it correct,
not tried it.". -- Knuth
Maybe he shouldn't use paper and pencil
for his proofs, and of course some specs
could be wrong.
Anyway, just had a nice glossing over:
Logic Programming: Operational Semantics
and Proof Theory - James H. Andrews
https://www.era.lib.ed.ac.uk/bitstream/handle/1842/13484/Andrews1991.Pdf
You find a Stack of Stacks model in
it, so its not the usual SLD resolution
explanation of Prolog...
Julio Di Egidio
Feb 10, 2018, 4:00:34 AM2/10/18
to
On Saturday, 10 February 2018 01:51:12 UTC+1, burs...@gmail.com wrote:
> Hi,
>
> Do you mean: "Beware of bugs in the
> above code; I have only proved it correct,
> not tried it.". -- Knuth
Yes. (I'd have said "I have not *tested* it", but I am already an engineer
> Hi,
>
> Do you mean: "Beware of bugs in the
> above code; I have only proved it correct,
> not tried it.". -- Knuth
while that's for the scientist, so I take it it's fine as it is.)
> Maybe he shouldn't use paper and pencil
> for his proofs, and of course some specs
> could be wrong.
principles meant to establish the scope and meaning of the discipline itself.
E.g. for Engineering that is Murphy's Law (*): with the premise that Computer
Science is not in fact my main expertise, I take Knuth's disclaimer to be it,
the limit of Computer Science.
(*) <http://architectando.blogspot.it/2015/06/the-source-of-all-certainty.html>
Julio
Julio Di Egidio
Feb 10, 2018, 4:03:08 AM2/10/18
to
On Saturday, 10 February 2018 10:00:34 UTC+1, Julio Di Egidio wrote:
> On Saturday, 10 February 2018 01:51:12 UTC+1, burs...@gmail.com wrote:
> > Hi,
> >
> > Do you mean: "Beware of bugs in the
> > above code; I have only proved it correct,
> > not tried it.". -- Knuth
>
> Yes. (I'd have said "I have not *tested* it", but I am already an engineer
> while that's for the scientist, so I take it it's fine as it is.)
P.S. The "scientist" in question rather being a mathematician, but that's yet
> On Saturday, 10 February 2018 01:51:12 UTC+1, burs...@gmail.com wrote:
> > Hi,
> >
> > Do you mean: "Beware of bugs in the
> > above code; I have only proved it correct,
> > not tried it.". -- Knuth
>
> Yes. (I'd have said "I have not *tested* it", but I am already an engineer
> while that's for the scientist, so I take it it's fine as it is.)
another story...
Julio
Ronald Modesitt
Feb 10, 2018, 8:36:58 AM2/10/18
to
On Friday, February 9, 2018 at 2:10:00 PM UTC-7, burs...@gmail.com wrote:
> Hi,
>
> I nevertheless like your mention of CLP(X). I tried
> to find some video, showing an introduction to CLP(X).
> But I tried to avoid something from the MiniKanren camp,
>
> which made it more difficult to find a video. But this
> video is quite charming, since it offers an end-user
> perspective and its from 2015:
>
> "Constraint logic programming is a paradigm that allows
> solving hard combinatorial problems with minimal
> programming effort. In this workshop you will learn
> the basics of the Prolog-based constraint logic
> programming system ECLiPSe, solve several puzzles,
> and get hints how constraint logic programming can
> be useful in your real-life projects."
>
> LambdaConf 2015 - Introduction to Constraint
> Logic Programming - Sergii Dymchenko
> https://www.youtube.com/watch?v=84amHOgCEe8
>
> Bye
>
burs
> Hi,
>
> I nevertheless like your mention of CLP(X). I tried
> to find some video, showing an introduction to CLP(X).
> But I tried to avoid something from the MiniKanren camp,
>
> which made it more difficult to find a video. But this
> video is quite charming, since it offers an end-user
> perspective and its from 2015:
>
> "Constraint logic programming is a paradigm that allows
> solving hard combinatorial problems with minimal
> programming effort. In this workshop you will learn
> the basics of the Prolog-based constraint logic
> programming system ECLiPSe, solve several puzzles,
> and get hints how constraint logic programming can
> be useful in your real-life projects."
>
> LambdaConf 2015 - Introduction to Constraint
> Logic Programming - Sergii Dymchenko
> https://www.youtube.com/watch?v=84amHOgCEe8
>
> Bye
>
Thank you for the reference. It's a bit above my head now but I will return to it as I progress.
Ron
burs...@gmail.com
Feb 10, 2018, 9:20:33 AM2/10/18
to
Why does this make any dent in semantics for Prolog?
The verb "prove" by Knuth refers not to the
same "prove" as a Prolog execution could be viewed.
They relate to each other like Peano arithmetic
relates to Robinson arithmetic. Thats why Program
verification is not the same as Prolog.
For example this Prolog program:
nat(0).
nat(s(X)) :- nat(X).
You can ask Prolog:
?- nat(X).
X = 0
X = s(0)
Etc..
So it generates Robinson arithmetic. But you
cannot ask Prolog the following:
?- forall X nat(X).
Because it doesn't have the induction axiom
available, so its stupid as Robinson. The
clark completion does also not sneak in the
induction axiom. You would need extra axioms,
that are not around when you "execute" Prolog.
At least I am not aware of them so maybe correct me,
if I am claiming something wrong. But Horn is
not the same as IND-Horn, where IND would be some
induction schemas added for some domains.
https://en.wikipedia.org/wiki/Robinson_arithmetic
The verb "prove" by Knuth refers not to the
same "prove" as a Prolog execution could be viewed.
They relate to each other like Peano arithmetic
relates to Robinson arithmetic. Thats why Program
verification is not the same as Prolog.
For example this Prolog program:
nat(0).
nat(s(X)) :- nat(X).
You can ask Prolog:
?- nat(X).
X = 0
X = s(0)
Etc..
So it generates Robinson arithmetic. But you
cannot ask Prolog the following:
?- forall X nat(X).
Because it doesn't have the induction axiom
available, so its stupid as Robinson. The
clark completion does also not sneak in the
induction axiom. You would need extra axioms,
that are not around when you "execute" Prolog.
At least I am not aware of them so maybe correct me,
if I am claiming something wrong. But Horn is
not the same as IND-Horn, where IND would be some
induction schemas added for some domains.
https://en.wikipedia.org/wiki/Robinson_arithmetic
0 new messages