PROLOG-REQUEST@SUSHI.STANFORD.EDU.UUCP (04/13/87)
PROLOG Digest Monday, 13 Apr 1987 Volume 5 : Issue 25
Today's Topics:
Programming - 91 Function,
Administration - Apology & Proposal
----------------------------------------------------------------------
Date: Mon, 6 Apr 87 08:23:09 PST
From: pereira@sri-candide.ARPA (Fernando Pereira)
Subject: 91
This seems much fuss about nothing. The obvious translation of the Manna
definition is
f(X, Y) :-
( X > 100 -> Y is X - 10
| Z is X + 11, f(Z, U), f(U, Y) ).
if one is prepared to assume that X is always instantiated when f is
called. If not, the definition with the two complementary comparisons
is needed. Any difficulties here?
-- F
------------------------------
Date: Thu, 9 Apr 87 01:25:58+0900
From: Dongwook Shin <dwshin%csd.kaist.ac.kr@RELAY.CS.NET>
Subject: 91 function
In reply to Paul Hudak's note about the 91 function.
Oh, yes! It seems that there is no Prolog program better than (5).
However, program (5) is not much the same as the definition of 91
function. It is because in Prolog, a relation can not be nested in
other relation except some special impure predicates (assert, univ).
If a logic language allows function definitions as well as relations,
we can make a program much similar to the above pure lisp program.
There are some functional logic languages such as Eqlog, Funlog, LEAF
and Aflog (designed and implemented by us) and these languages allow
function definitions. The program presented below is that of 91
function written in Aflog.
f(X) ==> ( (X>100) ? (X-10)), (6)
f(f(X+11))
In this program, ==> has the same meaning as = in pure lisp and ? has
the same meaning as if-then. The operator ? is called "guard command"
(We call ? "guard command because it is similar to guard command used
in Concurrent Prolog) and if a guard ( e.g. X>100 in this example)
succeeds, the function is reduced to the expression matching this
guard. If no guard succeeds, the last expression which does not have
a guard is chosen.
Let me introduce Aflog briefly. An Aflog program consists of a set of
clauses and a set of functions. A function is defined as a set of pure
equations as in most equational languages (A pure equation means the
equation whose form is A = B, not A = B :-C) and an equation has the
similar form as (6). Equations should not violate two restrictions as
follows.
1. A set of equations should be canonical, i.e., confluent and terminating.
2. Function terms should not have a logical variable when unified with other
terms. In other words, all arguments of of a function must be ground when
the function is to be evaluated.
However, these restrictions are not very restrictive because almost
all functions are deterministic and evaluated in finite times. In
fact, Aflog can support function definition by using Canonical
Unification which is a restricted E-unification and at the same time,
an extension of the unification used in Prolog. I'll take a
complicated example which shows the functional logic features more
comprehensively. The following Aflog program makes a binary sorted
tree taking an input list.
% equations for tree insertion
insert(A, empty) ==> tree(empty,A,empty).
insert(A, tree(L,B,R)) ==> ((A<B) ? tree(insert(A,L),B,R)),
(tree(L,B, insert(A,R))).
% Logical definition
make_binary_tree(L,Tr) :- build_up(L,empty,Tr).
% build a sorted binary tree NewTr
% according to a given list
build_up([],Tr,Tr).
build_up([A|L],Tr,NewTr) :- build_up(L, insert(A,Tr),NewTr).
% end of Aflog program
In this program, build_up predicate has insert function as its
argument and this is one of the most prominent differences from Prolog
program. I'll write down Prolog program which is functionally same as
the above program.
%
make_binary_tree(L,Tr) :- build_up(L,empty,Tr).
% build a sorted binary tree NewTr
% according to a given list
build_up([],Tr,Tr).
build_up([A|L],Tr,NewTr) :-
insert(A,Tr,Tr1),
build_up(L,Tr1,NewTr).
insert(A,empty,tree(empty,A,empty)).
insert(A, tree(L,B,R),tree(New,B,R)) :-
A<B, insert(A,L,New).
insert(A, tree(L,B,R),tree(L,B,New)) :-
A>=B, insert(A,R,New).
% end of Prolog program
In this Prolog program, Tr1 in build_up predicate and New in insert
predicate are unnatural. This unnaturalness is owing to that insert is
defined as relations in spite that it is intrinsically deterministic
and functional. The most important shortcoming in functional logic
programming is that currently developed interpreters are very slow
compared to Prolog. However, Aflog is not much slower than Prolog.
The above Aflog program is executed 30-40 times slower than the next
Prolog program. Considering that Aflog is written in C-Prolog and
C-Prolog is written in C, I'm sure that Aflog is at most 3-4 times
slower than Prolog if it is rewritten in C with some optimization
techniques employed.
-- D.W. Shin
------------------------------
Date: Tue, 31 Mar 87 19:52:13 EST
From: Ken Bowen <kabowen%syr-sutcase.csnet@RELAY.CS.NET>
Subject: Listing Service Proposal
My previous message apologized for a misstep in using the Digest to
inform people about a Prolog compiler in which I have a commercial
interest.
This does raise an issue that has in fact bothered me for some time
in my (continuing) role as a faculty member and researcher, and I
think I have a proposal to cope with it. A major function of the
Digest is to provide a public forum for assisting one another in
solving problems that arise in the course of our work. One of the
general problems we all face is the selection of the best available
tools with which to tackle our various tasks. This ranges from
selection of mathematical tools to the selection of software and/or
hardware. The public exchange of information on techniques and tools
is extremely valuable in this regard: The on-going discussions of PC
Prologs provides a prime example. Our problem is one of balancing
between the goals of maximizing the flow of available information and
minimizing direct commercial impact on the Digest.
I would propose the following solution: The Digest should provide
a listing service for tools (be they compilers, interfaces, etc., etc.),
regardless whether the object is commercial or non-commercial.
Here are my thoughts on how it would work:
1. To minimize the impact on the Moderator, it would be operated
by software similar to the CSNET InfoServer software which one can use
for checking your address, etc. One sends a more or less standard
form message, and the software generates appropriate reply messages to
the originator. In this case, the replies would be messages
containing information from the listing service. So the impact on the
Moderator would be that of maintaining the reply software, but little
else. (And in #5 below, I propose that the community should be able
to build and maintain the software.)
2. In the case of the Prolog Digest, it might maintain a
structure roughly as follows:
A. Top_Level Category: i) Prolog Interpreter/Compiler; ii) Prolog
programming productivity tool; iii) Prolog-coded application,...
B. Within each category would be a listing (alphabetical/chronological?)
of the items.
The software would reply to several forms of messages:
index - would provide a listing of the header entries organized
by category;
<category>/<item> - the complete entry for the given item;
<category>/all - the complete entries for the items in the category;
<category>/all/since <when> - complete entries for items posted after
the indicated date;
{I'm sure we could all multiply these options...}
4. The entries would be provided by the purveyors of the items
(commercial, academic, or whatever). The items might be completely
free-form after the header, or might have a combination of standard
checklist (as in a number of reviews over the past year or so)
together with a free-form portion.
5. There would be no attempt to certify the correctness of the entries.
(Not only would such certification create far too much work for
a moderator, but it would almost certainly raise lots of controversy,
as we have yet to agree on a standard set of benchmarks in the
Prolog community.) It is assumed that the normal discussion mechanism
on the Digest would provide the necessary corrective actions.
6. Prolog is good enough that we (jointly as a community) ought to be able
to evolve a small set of programs which will operate and maintain
such a service. A partial list of component programs would
include:
i) Query program: creates messages of appropriate form for mailing
to the reply software;
ii) Reply program: can read messages created by the query program
and create appropriate reply messages.
iii) Insertion preparation program: Creates messages in appropriate
form for listing new items.
iv) Insertion program: Reads messages prepared by the insertion
preparation program and inserts the new information properly.
I believe that such a service would provide a genuine solution to
the problem: It would make information available while at the same
time controlling direct commercialization of the bulletin board.
I also believe that Prolog is a good tool for building such a
service. (If that turns out to be false, some of us -- both academic
and commercial -- will have to start moderating our claims about the
power of Prolog.)
Finally, I believe that we, as a community, are still friendly and
cooperative enough to jointly evolve such a software-based service --
I'd really hate to be disabused of this belief.
Once more: My apologies to the community for the misstep in my
message about ALS Prolog. I hope the proposal above will lead to a
solution of the problem my message exemplified.
-- Ken Bowen
--------------------
End of PROLOG Digest
********************