PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (01/24/86)
PROLOG Digest Monday, 27 Jan 1986 Volume 4 : Issue 5
Today's Topics:
Implementation - Syntactic Sugar & Coding Algorithms,
LP Philosophy - What is the expressive ability of Prolog?
----------------------------------------------------------------------
Date: 20 Jan 86 16:59:46-EST (Mon)
From: Zerksis D. Umrigar <Zerksis%sutcase.bitnet@wiscvm.arpa>
Subject: More syntactic sugar for Prolog.
One can drastically reduce the use of cuts in Prolog programs
by the use of if-then-else control constructs. However, I feel
that the syntax of 'if P then Q else R' in most Prolog implement
-ations (P-> Q ; R) leaves much to be desired. By introducing
a declaration similar to op, it should be possible to permit non
-iterative control constructs similar to those found in most
procedural languages, while still retaining the syntax of Prolog
"clauses" as terms.
Basically, the idea is that one should allow general parentheses,
with general punctuation. Hence one can think of 'if' as left
parenthesis with say 'end_if' as the closing parenthesis. 'then'
and 'else' would be general punctuation marks. The precedence of
any term enclosed within general parentheses would be identical to
that enclosed within '(' and ')' (0 for DEC-10 Prolog). The
declaration could be something like :-paren([if,then,else,end_if]).
By allowing suitable meta-characters in the declaration, one
could specify optional punctuation, or punctuation characters
which are repeated 0 or more times. This would make possible the
use of if-then and case control constructs. (The semantics of
the case statement would be to commit to the first alternative
whose guard is solved successfully). Another useful
construct would be something similar to case, which would allow
backtracking over the "guards" - (equivalent to cut-free disjunction
in regular Prolog).
If the implementation looks at the control constructs at the
top-level of a "clause", it should be possible for it to
automatically generate indexing information to obtain rapid
access to the chosen alternative. This should make it
possible to write efficient single-"clause" procedures.
Hopefully, this sugared syntax should be easier to read and
comprehend than regular Prolog syntax.
Any comments?
------------------------------
Date: 22 Jan 1986 00:04-CST
From: Kale@uiucdcsb.CS.UIUC.EDU
Subject: Coding an interesting algorithm in Prolog
Recently, I was reading an algorithm (fairly complex, it seemed)
for finding the median of a set of numbers in linear time. At the
back of my mind were arguments I recently had regarding the
suitability of Prolog for coding complex algorithms. So I decided
to code it. I was pleasnatly surprised at the simplicity of code
and the ease of coding.
Here is the code:
/* Given a list of length N and a number K, `select' selects an
element, E, of the list such that there are exactly K-1 elemets
less than E. This can be used for finding the median by calling
it with K = length/2.
The algorithm requires 28*N comparisons. */
select(L,K,V) :- length(L,N), N < 28, !, sort(L,L1), nth_member(L1,K,V).
select(L,K,V) :-
choose(L,M), /* Choose a member of L that is `close' to
the median */
partition(L,M,L1,Length1,L2),
((K =< Length1, select(L1,K,V)) ;
(K2 is K - Length1, select(L2,K2,V))).
choose(L,M) :- medians(L,S,Length_S), N is (Length_S // 2)+1, select(S,N,M).
medians([X1,X2,X3,X4,X5,X6,X7|Rest],[Y|New],Length1) :- !,
sort([X1,X2,X3,X4,X5,X6,X7],[_,_,_,Y,_,_,_]),
medians(Rest,New,Length), Length1 is Length+1.
medians(L,[],0).
partition([],M,[],0,[]).
partition([First|Rest],M,[First|L1],Length1,L2) :-
First < M, !,
partition(Rest,M,L1,Length,L2),
Length1 is Length + 1.
partition([First|Rest],M,L1,Length1,[First|L2]) :-
partition(Rest,M,L1,Length1,L2).
nth_member([F|R],1,F).
nth_member([F|R],N,M) :- N > 1, N1 is N-1, nth_member(R,N1,M).
/* coded for CProlog */
The algorithm is taken from the book `combinatorial algorithms'
by Reingold, Deo, and Nievergelt.
I used the system sort here, which is ok ONLY IF the original
list does not have duplicates. The system sort eats up the
duplicates. Write your own (bubble) sort if you have duplicates.
The first clause can be taken to provide the definition of the
problem, (without the `length < 28' check). For linearity, all
that you have to ensure is that the first clause requires
(< 28*n) comparisons.
Proof of Linearity: The `choose' predicate finds a member that
is close to the median in the sense that there are at least
(n*2/7) on either side of it. Thus the worst case recursive-call
will be on a list of length 5n/7, taking 28*5n/7 =20n comparisons
by inductive hypothesis. `choose' itself takes 3n comparisons to
sort the sublists of length 7 each, and 4n to find the `median of
the medians' recursively (28*n/7).
`partition' takes n more comps. , so the total is: 20n+3n+4n+n=28n!
The first clause provides the BASIS for the inductive proof.
-- Kale
p.s. Do people out there have examples of complex data structures
being coded in Prolog? Some of my concerns are algorithms for
graph traversals that need to repeatedly update values at nodes,
connectionist algorithms etc.
------------------------------
Date: Mon 20 Jan 86 11:31:04-PST
From: Fernando Pereira <PEREIRA@SRI-CANDIDE.ARPA>
Subject: Expressive ability
The expressive power of machine languages it the power of
being able to instruct a machine to do any elementary step
(machine instruction) that the machine has been designed to
do. That kind of expressive power is thus irrevocably tied
to a particular machine architecture, so let's call it
``machine power''.
Like many other computer scientists, advocates of logic
programming understand the advantages of relinquishing machine
power in favor of ``abstraction power'': the ability to express
abstract relationships and processes without having to delve
into the peculiarities of the implementation of that expression
on a particular machine.
The discipline needed to keep abstractions alive in a language
with substantial machine power (such as Lisp) seems beyond the
grasp of most programmers, to judge by their products. Learning
to use a language with superior abstraction power but little
machine power takes time and also requires discipline, but pays
off in better products: maintainable, reusable.
The tremendous growth and success of modern mathematics depended
in no small measure on the acquisition by mathematicians of
increasingly powerful abstraction tools. The laborious combinato
-rial methods of 19th century algebra (the mathematical counter
-part of machine power), are today of only historical interest,
and no one (well, almost no one...) would blame a present-day
mathematician for not being able to work in those terms.
Our inability to build reliable software products is not due to
lack of machine power in our tools (we have had plenty ot that...)
but to our inability to predict the interactions between components
for which there are no good abstract specifications and implementa
-tions. The practice of Lisp programming shows this clearly. Current
logic programming tools are somewhat better, but clearly not good
enough, particularly with respect to modularity.
We should not let criticisms of logic programming from the point of
view of a programming practice discredited by the unreliability of
its products manuever us into wasting our effort trying to increase
the machine power of logic programming tools rather than building on
logic programming's strength, abstraction power.
-- Fernando Pereira
------------------------------
End of PROLOG Digest
********************PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (01/27/86)
PROLOG Digest Tuesday, 28 Jan 1986 Volume 4 : Issue 5
Today's Topics:
Implementation - Syntactic Sugar & Coding Algorithms,
LP Philosophy - What is the expressive power of Prolog?
----------------------------------------------------------------------
Date: 20 Jan 86 16:59:46-EST (Mon)
From: Zerksis D. Umrigar <Zerksis%sutcase.bitnet@wiscvm.arpa>
Subject: More syntactic sugar for Prolog.
One can drastically reduce the use of cuts in Prolog programs
by the use of if-then-else control constructs. However, I feel
that the syntax of 'if P then Q else R' in most Prolog implement
-ations (P-> Q ; R) leaves much to be desired. By introducing
a declaration similar to op, it should be possible to permit non
-iterative control constructs similar to those found in most
procedural languages, while still retaining the syntax of Prolog
"clauses" as terms.
Basically, the idea is that one should allow general parentheses,
with general punctuation. Hence one can think of 'if' as left
parenthesis with say 'end_if' as the closing parenthesis. 'then'
and 'else' would be general punctuation marks. The precedence of
any term enclosed within general parentheses would be identical to
that enclosed within '(' and ')' (0 for DEC-10 Prolog). The
declaration could be something like :-paren([if,then,else,end_if]).
By allowing suitable meta-characters in the declaration, one
could specify optional punctuation, or punctuation characters
which are repeated 0 or more times. This would make possible the
use of if-then and case control constructs. (The semantics of
the case statement would be to commit to the first alternative
whose guard is solved successfully). Another useful
construct would be something similar to case, which would allow
backtracking over the "guards" - (equivalent to cut-free disjunction
in regular Prolog).
If the implementation looks at the control constructs at the
top-level of a "clause", it should be possible for it to
automatically generate indexing information to obtain rapid
access to the chosen alternative. This should make it
possible to write efficient single-"clause" procedures.
Hopefully, this sugared syntax should be easier to read and
comprehend than regular Prolog syntax.
Any comments?
------------------------------
Date: 22 Jan 1986 00:04-CST
From: Kale@uiucdcsb.CS.UIUC.EDU
Subject: Coding an interesting algorithm in Prolog
Recently, I was reading an algorithm (fairly complex, it seemed)
for finding the median of a set of numbers in linear time. At the
back of my mind were arguments I recently had regarding the
suitability of Prolog for coding complex algorithms. So I decided
to code it. I was pleasnatly surprised at the simplicity of code
and the ease of coding.
Here is the code:
/* Given a list of length N and a number K, `select' selects an
element, E, of the list such that there are exactly K-1 elemets
less than E. This can be used for finding the median by calling
it with K = length/2.
The algorithm requires 28*N comparisons. */
select(L,K,V) :- length(L,N), N < 28, !, sort(L,L1), nth_member
(L1,K,V).
select(L,K,V) :-
choose(L,M), /* Choose a member of L that is `close' to
the median */
partition(L,M,L1,Length1,L2),
((K =< Length1, select(L1,K,V)) ;
(K2 is K - Length1, select(L2,K2,V))).
choose(L,M) :- medians(L,S,Length_S), N is (Length_S // 2)+1, select
(S,N,M).
medians([X1,X2,X3,X4,X5,X6,X7|Rest],[Y|New],Length1) :- !,
sort([X1,X2,X3,X4,X5,X6,X7],[_,_,_,Y,_,_,_]),
medians(Rest,New,Length), Length1 is Length+1.
medians(L,[],0).
partition([],M,[],0,[]).
partition([First|Rest],M,[First|L1],Length1,L2) :-
First < M, !,
partition(Rest,M,L1,Length,L2),
Length1 is Length + 1.
partition([First|Rest],M,L1,Length1,[First|L2]) :-
partition(Rest,M,L1,Length1,L2).
nth_member([F|R],1,F).
nth_member([F|R],N,M) :- N > 1, N1 is N-1, nth_member(R,N1,M).
/* coded for CProlog */
The algorithm is taken from the book `combinatorial algorithms'
by Reingold, Deo, and Nievergelt.
I used the system sort here, which is ok ONLY IF the original
list does not have duplicates. The system sort eats up the
duplicates. Write your own (bubble) sort if you have duplicates.
The first clause can be taken to provide the definition of the
problem, (without the `length < 28' check). For linearity, all
that you have to ensure is that the first clause requires
(< 28*n) comparisons.
Proof of Linearity: The `choose' predicate finds a member that
is close to the median in the sense that there are at least
(n*2/7) on either side of it. Thus the worst case recursive-call
will be on a list of length 5n/7, taking 28*5n/7 =20n comparisons
by inductive hypothesis. `choose' itself takes 3n comparisons to
sort the sublists of length 7 each, and 4n to find the `median of
the medians' recursively (28*n/7).
`partition' takes n more comps. , so the total is: 20n+3n+4n+n=28n!
The first clause provides the BASIS for the inductive proof.
-- Kale
p.s. Do people out there have examples of complex data structures
being coded in Prolog? Some of my concerns are algorithms for
graph traversals that need to repeatedly update values at nodes,
connectionist algorithms etc.
------------------------------
Date: Mon 20 Jan 86 11:31:04-PST
From: Fernando Pereira <PEREIRA@SRI-CANDIDE.ARPA>
Subject: Expressive ability
The expressive power of machine languages it the power of
being able to instruct a machine to do any elementary step
(machine instruction) that the machine has been designed to
do. That kind of expressive power is thus irrevocably tied
to a particular machine architecture, so let's call it
``machine power''.
Like many other computer scientists, advocates of logic
programming understand the advantages of relinquishing machine
power in favor of ``abstraction power'': the ability to express
abstract relationships and processes without having to delve
into the peculiarities of the implementation of that expression
on a particular machine.
The discipline needed to keep abstractions alive in a language
with substantial machine power (such as Lisp) seems beyond the
grasp of most programmers, to judge by their products. Learning
to use a language with superior abstraction power but little
machine power takes time and also requires discipline, but pays
off in better products: maintainable, reusable.
The tremendous growth and success of modern mathematics depended
in no small measure on the acquisition by mathematicians of
increasingly powerful abstraction tools. The laborious combinato
-rial methods of 19th century algebra (the mathematical counter
-part of machine power), are today of only historical interest,
and no one (well, almost no one...) would blame a present-day
mathematician for not being able to work in those terms.
Our inability to build reliable software products is not due to
lack of machine power in our tools (we have had plenty ot that...)
but to our inability to predict the interactions between components
for which there are no good abstract specifications and implementa
-tions. The practice of Lisp programming shows this clearly. Current
logic programming tools are somewhat better, but clearly not good
enough, particularly with respect to modularity.
We should not let criticisms of logic programming from the point of
view of a programming practice discredited by the unreliability of
its products manuever us into wasting our effort trying to increase
the machine power of logic programming tools rather than building on
logic programming's strength, abstraction power.
-- Fernando Pereira
------------------------------
End of PROLOG Digest
********************