Cohen%UCBKIM%Berkeley@sri-unix.UUCP (11/18/83)
From: Cohen%UCBKIM@Berkeley (Shimon Cohen)
I guess we are all fans of Prolog, are we ? Well, some of
us are convinced that Prolog will take over Lisp, ada and
the next 1000 languages, Some are curious to see what it
is all about, AND some are afraid to be left behind the
JAPANese ...
I guess we all agree that most languages are equivalent
to Turing machine meaning: you can do almost anything in
any language, so the qustion is "what makes one language
"better" then the other ? " Usually we compare: Efficiency,
clarity, readability, features (services provided by the
language) mathematical background etc.
My experience with Prolog shows that it is not always
superior to other languages (for example Lisp) but in certain
applications it is !!! So I ask myself ( and all of you out
there ) :
1. Are you really convinced that Prolog should
replace Lisp, pascal, ada or some of them ?
2. In what areas you feel that Prolog is better
and in what it is the same or worse ?
3. Aren't you afraid that Prolog will become
another APL type language, good for very specific
applications ?
I would like to give an Example where Prolog seems to be superior
to Lisp and other languages. I wrote the famous Eliza program in
Prolog, it seems to be almost 3 times shorter then the Lisp
implementation and much more clear, efficient etc.
/* Start of program */
top :- repeat,write(' you: '),main,fail.
main :- read_sent( Sent ),!,
replace_list( Sent, Rsent ),!, /* replace i --> you etc */
key_list( Rsent, Ks ), sort( Ks, Sk ),reverse( Sk, Skeys ),!,
try_keys( Skeys, Rsent, Answer ), /* get an answer */
write(' doc: '),print_reply( Answer ), nl.
pm( [],[] ). /* pattern matcher in Prolog ... see data file */
pm( [X|L1], [X|L2] ) :- pm(L1,L2),!.
pm( [oneof(Options,X) | L1], [X|L2]) :- member(X,Options), pm(L1,L2).
pm( [mvar(X) | L], L2) :- append(X,L1,L2), pm(L,L1).
replace_list( [], [] ).
replace_list( [X|L], [Y|L1] ) :- replace(X,Y),!, replace_list(L,L1).
replace_list( [X|L], [X|L1] ) :- !,replace_list(L,L1).
key_list( [], [key(-1,none)] ).
key_list( [K|L1], [ key(P,K)|L2] ) :- priority(K,P), key_list(L1,L2).
key_list( [K|L1], L2 ) :- key_list(L1,L2).
try_keys( Keys, Rsent, Outsent ) :-
member( key(P,K1), Keys ), /* select a key (generator) */
trule( K1, Ptrn, Nans, Ans ), /* find a rule */
pm( Ptrn, Rsent ),!, /* match ? */
random( Nans, N ), /* get random number upto Nanswers */
get_answer(Ans,N,Outsent). /* get the answer from choices */
get_answer( [A|L], 0, A).
get_answer( [B|L], N, A) :- N1 is N - 1, get_answer(L,N1,A).
/* end of Eliza main system
The following describes the data file for the Eliza (Doctor) program.
The data consists the following:
1. Transformations rules that are of the form:
trule(Keyword,Pattern,Number_of_answers,Answer_list).
where:
a. Pattern is the sentence pattern for the keyword.
b. Number_of_answers - how many available answers for
this keyword+pattern.
c. Answer_list - list of available answer for this
pattern+keyword.
In the patterns:
mvar(A) stands for zero or more words.
A stands for any one word.
oneof(List,A) stand for A is one of the words in List.
Note that in some cases a keyword can acquire the transformation
rule of another keyword and a certain pattern might include
answers of another keyword.
2. Replacement rules in the form:
replace(A,B) - replace A by B.
3. Priority rules in the form:
priority(A,N) - the priority of keyword A is N.
If a keyword does not have a priority rule it is assumed to
be of priority 0.
The priorities are in ascending order.
EXAMPLES:
---------
/* Note the way variables from the pattern are used in the answers */
trule(your,
[mvar(A),your, oneof([mother,father,brother,sister,husband],C),
mvar(B)], 5,
[['Tell',me,more,about,your,family,'.'],
['Is',your,family,important,to,you,'?'],
['Who',else,in,your,family,B,'?'],
['Your',C,'?'],
['What',else,comes,to,your,mind,when,you,
think,of,your,C,'?']]).
. . ..
replace(i,you).
replace(you,i).
replace(computers,computer).
. . .
priority(computer,40).
priority(remember,5).
priority(if,3).
. . .O'KeefeHPS@sri-unix.UUCP (07/03/84)
From: O'Keefe HPS (on ERCC DEC-10)
I agree that S-expressions are elegant, general, and so on.
{So for that matter are Goedel numbers.} But there is good
reason to believe that they are not well suited to human
reading and writing. That is that ***LISP*** doesn't use
S-expressions for everything. Consider
[A<-(FOR NODE IN NODELIST COLLECT CAR EVAL (NODE:NODEFORM]
which is perfectly good InterLisp. I might be persuaded
that this is readable, though not after the uglyprinter has
had its way with it, but it quite certainly is NOT an S-expression.
Now there is an isolationist section of the Lisp community which
ignores Interlisp (the Common Lisp designers did not, well done).
But as soon as you use ANY sort of read macro, you have left
S-expressions behind. `(cons ,(cadr form) ,(caddr form)) is not
an S-expression. And of course the MacLisp family has (loop ...).
As for the question about whether there are natural binary operations
which are not associative, mathematics is FULL of them. Any function
whose result type differs from its right argument type. Quite a lot
are relations, such as "=", "<", and so on. Note that the extension
of the relational operations to multiple arguments in some Lisps
loses you a lot of nice properties: (>= A B C) is not the same as
(NOT (< A B C)). Depending on implementation subtleties it might not
even be the same as (<= C B A). And the extension STILL doesn't let
you write 0 <= X < Y, you have to write -1 < X < Y which is often more
obscure than an explicit conjunction would have been. The principal
example of a non-associative binary operator is exponentiation.
As an instance of exponentiation, let's take the free monoid over
the ASCII characters, where "abc"^4 = "abcabcabcabc". Any
generalisation of this to take an arbitrary number of arguments will
not treat all the arguments equally. One natural extension to
multiple arguments would be to take an alternating list of strings
and integers (^ S1 N1 ... Sk Nk) = (concat (^ S1 N1) ... (^ Sk Nk))
with omitted integers taken to be 1. But this doesn't place all the
arguments on an equal footing (what should (^ "abc" 2 3) mean?) and
doesn't really generalise to other operators. There is even a
problem with operators which have coincident argument and result
types. For example, why should (CONS x y z) means (CONS x (CONS y z))
rather than (CONS (CONS x y) z)?
I'm afraid the Sigma notation is not an example of mathematicians
retreating in response to an indaequacy in infix notation. When
writing *informally*, mathematicians are as pleased as anyone else
to write a1 + ... + an. Sigma notation specifies three things:
a commutative associative binary operation (if the domain can be
empty the operation must have an identity), a domain, and a
FUNCTION. E.g. in
/\
/ \ f(i) = g(i)^2
i=1..n
the operation is "and", the domain is {1,2,...,n}, and the
function is lambda i. f(i) = g(i)^2. I fully agree that this is a
good thing to have, but it is NOT a thing you can get by allowing
the argument list of everything in sight to have an arbitrary number
of arguments. The number of arguments is still fixed at each CALL.
When the number of operands is unknown, the Lisper still has to write
(apply #'and (mapcar #'(lambda (i)
(eql (f i) (expt (g i) 2))) (num-list 1 n)))
and then finds that he can't, because "and" is a special form and
you can't apply special forms. Quite a few Lisps macro-expand
(plus a b c d) to (plus2 (plus2 (plus2 a b) c) d), and you can have
fun applying #'plus ! What you find yourself having to do all too
often is
(eval (cons #'and (mapcar #'(lambda (i)
(kwote (eql (f i) (expt (g i) 2)) )) (num-list 1 n)) ))
Now there IS a lisp-like language which has faced up to this problem
of some functions sensibly taking an arbitrary number of arguments.
It's called 3-Lisp. Yes, I mean the thing described in Brian Smith's
thesis. It has been implemented and runs quite nicely on Xerox 1108s.
3-lisp distinguishes between PAIRs, written (car . cdr) and SEQUENCES,
written [a1 ... an]. I shan't tell you about the distinction between
sequences and rails. There *is* a notational convention that if you
write (car a1 ... an) {note: no dot after the car} it means
(car . [a1 ... an]). So (+ a b c) means (+ [a b c]). The thing is
that if you employ the language's reflective capabilities to poke
around in the guts of your program while it's running, you'll find
that the rail or sequence really is there. The cdr of a pair can be
any form (as can the car), so if I want to write
(+ . (map f L))
I can.
Given that Prolog is based on relations rather than functions,
you don't find anywhere NEAR as much nesting as you do in a
language based on functions, so the operator priority issue doesn't
really arise, except when the data you are working on are expressions
in some language. MACSYMA, for example, exploits the CGOL parser
to handle its input. Prolog happens to use the analogous thing all
the time.
Prolog lets you use operators when you want to. You don't have
to use any operators at all if you don't want to:
:-(max_min(X,Y,X,Y), >=(X,Y)).
:-(max_min(X,Y,Y,X), <(Y,X)).
is quite acceptable to the Prolog parser, though not to me.
Similarly, Lisp lets you use operators if you want to (in InterLisp
it happens automagically with CLISP, use the CLISPTYPE, UNARYOP, and
LISPFN properties; in PSL you can use RLISP; in MacLisp there is
CGOL), but normally only uses a handful of strange syntactic forms.
Prolog and Lisp are similar internally as well. Modulo all the
exotic data structures like records and hash tables present in all
modern Lisps, which structures have no S-expression representation
{Common Lisp does let you use #(struct-name field-1 "val1" ...)
for defstructs, but there is nothing for hash tables or most forms
of array}, most Lisp data can be viewed as
atomic
or (CONS something something-else)
and functions to hack such structures are indeed easily written.
If you want to write programs that analyse programs, you rapidly
find yourself in very deep water sinking fast. It is a MAJOR
contribution of Common Lisp that they have spelled out exactly
what special forms a program-hacking tools must understand (there
are about 20 of them) and that they have specified ways of telling
whether a form is a macro call and of getting at the macro expansion
without too much pain. The hair in the MASTERSCOPE interface for
coping with InterLisp's "no specifications please, we're power-
assisted programmers!" view is amazing.
Prolog code that wants to hack arbitrary data structures can
similarly view the world as divided into two sorts of objects:
variables
and other terms
Other terms have a function symbol and 0 or more arguments.
For example, 77 is a non-variable whose function symbol is 77
and which has 0 arguments. This is admittedly a wee bit more
complex than basic Lisp, as cons cells are known to have exactly
two components. But I have faithfully described real Prolog;
there is nothing else that a Prolog program can get its hands
on and look inside. A Lisp |print| routine really does have
to worry about what to do with records (defstructs) and arrays
and compiled-code pointers and ...
The list of Prolog "special forms" is embarrassingly large:
?- /1 :- /1 :- /2 , /2
; /2 \+ /1 setof/3 bagof/3 call/1
once/1 forall/2 % some Prologs lack these two
But that's still a LOT less than Common Lisp has.
To summarise:
yes, S-expressions are general, clean, and hackable.
BUT, so are terms.
BUT, there is a LOT more to Lisp syntax and internal
structure both than S-expressions.
Ken Kahn is absolutely right that it is important to have an
internal structure which you can easily build tools for. He
is right that S-expressions are such an internal structure.
(Just don't assert any clauses mentioning arrays...) It is
also true that "Core Prolog" data structures are themselves
convenient to work with. (Some of the toy Prologs that you
can buy for peanuts get basic things like functor/3 wrong so
that it isn't true. But there are several toy implementations
of Lisp which represent a list as a string, so that
DEFINE('CAR(X)')
CAR.PAT = "(" BAL . CAR "." :ON
CAR X CAR.PAT :S(RETURN)F(FRETURN)
Does that mean Lisp data structures are bad?)
Look, we're NEVER going to agree about syntax. I've indulged myself
somewhat in this message, but I have been defending a kind of
syntax (infix operators) and to some extent even a choice of syntax,
rather than any specific form. There is no question about what
Dec-10 syntax IS. There's a parser for it in the Prolog library.
If that's translated into LM-Prolog (with a suitable tokeniser bolted
on the front) LM-Prolog should be able to read Dec-10 Prolog.
This published parser is what we need for portability. We will never
agree about what Dec-10 Prolog syntax SHOULD have been, but it doesn't
<swear-word> well MATTER. If we can agree on a transport syntax,
then I give you a copy of the Dec-10 Prolog parser in transport syntax
and you can use it to read my programs, and you give me a copy of your
parser in transport syntax and I can use it to read your programs.
You can sneer at my infix operators and I can quail at the opacity
of your lists. That doesn't matter. We can still share code.
PLEASE let's stop talking about Prolog syntax. I've had only one
comment about my transport syntax ideas, and that was from Fernando
Pereira. If he'd disagreed I'd have known that I was wrong, so he
and I can't argue much. A transport syntax based only on lists is
entirely out of the question as it can't be used by a Prolog which
distinguishes between lists and other terms. In fact if you look
back at the original proposal, I suggested distinguishing between
control structure (& | and so one) and term structure, a distinction
which the Edinburgh Prologs do not make. So it discriminates against
everybody, which is surely fair enough? An LM-Prolog program to read
my proposed transport syntax and turn it into lists can ignore most
of the distinctions. [I cite LM-Prolog not as a bad example of
anything but as possibly the best Prolog system whose syntax is
radically different from Dec-10 Prolog.] Now I'm quite certain that
both of my proposed transport syntaxes (the everything-is-Polish
one and the control-structures-are-infix one) are seriously deficient
in respects I have failed to consider. There is no point at all in
me going away and writing a paper "Official Standard for Prolog
Transport Syntax", as to be any use at all it needs the assent of the
community, or at least of some number of Prolog implementors.
Remember that it does not matter a continental if the transport
syntax is not to your personal taste: nobody is expected to write
in it. What matters is that the transport syntax should be
[a] capable of representing all existing shared code which is
likely to be useful on more than one implementation. (For
example, if you have some LM-Prolog code that does something
interesting with ZetaLisp flavours, by all means put it in
the library, but I don't think we need to worry about putting
it in transport syntax. Any implementation that can use it
can probably use LM-Prolog syntax directly.)
[b] unambiguous. In particular, if there is a distinction which
a reasonable Prolog might want to make (such as between
control structures and data structures, or between strings and
lists of integers, or between lists and other terms), then the
transport syntax should make that distinction, even if none of
the current Prolog systems needs it. For example, perhaps we
should rule that characters should be represented as #<char>
where <char> is anything that can follow #\ in Common Lisp,
just in case some Prolog implementation finds it convenient to
distinguish between characters and integers. Thus what
DEC-10 Prolog represents as "ab
c" might be represented in transport syntax as
[#a, #b, #newline, #tab, #c].
[c] parseable by a fast bottom-up parser (so that the implementation
language need not be able to support recursion).
[d] We should make sure that we have the same transport syntax by
sharing a parser, best written in C, but Pascal would do.
One very important reason for making a distinction between control
structures and data structures is to permit distinguishing between
predicates and functions. If I am loading a file into C Prolog and
I come across gcguide(20) as a call I know perfectly well that it
doesn't exist in C Prolog. I can complain, or in this case I can
translate the call to 'true'. But if gcguide(20) appears as a
*term* I can do neither of these things; it is correct as it stands.
Anyway, please will someone at the very least comment about whether
they think a transport syntax is a good idea? [I know Frank McCabe
does, but he isn't on the net. If his proposed syntax weren't
identical to his Prolog I'd like it a lot better.] The evidence so
far is that I do, and Fernando does, but everyone else would rather
bicker about DEC-10 syntax or just stand to one side and gawp.
If someone would like to comment on the proposed syntaxes, I entreat
you to do so, and if you're missing those issues I dare say they
could be re-sent. Let's get something PRODUCTIVE out of this
wretched Digest!