PROLOG-REQUEST@SU-SCORE.ARPA (Chuck Restivo, The Moderator) (09/25/85)
PROLOG Digest Thursday, 26 Sep 1985 Volume 3 : Issue 39
Today's Topics:
LP Philosophy - Hewitt's Challenge,
Programming - DCGs + Left Recursion,
Implementation - Destructive Assignment,
----------------------------------------------------------------------
Date: Fri, 13 Sep 85 10:41:27 bst
From: William Clocksin <wfc%computer-lab.cambridge.ac.uk@ucl-cs>
Subject: Lisp/Prolog
I received issues 36 and 37 late owing to netproblem somewhere
between Stanford and Cambridge. I am puzzled by this Lisp/Prolog
debate started by Carl Hewitt. I use both Prolog and Lisp, and
have never felt the need to use one exclusively. I suppose they
are like screwdrivers and chisels; both are roughly the same,
but for slightly different purposes; to a person unfamiliar with
one of them, the other one might seem redundant. I am also
puzzled about the question of a "foundation" for AI. How can a
language be a "foundation" for anything? Was Latin a "foundation"
of Western civilisation? Seen any fundamental native speakers
lately? Besides, does AI deserve to have foundations attributed
to it anyway?
Another problem is this question about logic. Prolog is a
programming language. It was inspired by logic, but it is not
programming in logic. Proponents of using logic do have a problem
matching impedance with the real world. But Prolog is to logic
as Lisp is to lambda calculus. Those who advocate programming in
lambda calculus have the same problem as those who advocate
programming in pure logic. If Prolog can be said to have any
connection with logic, it is as the FORTRAN of logic programming.
Prolog is useful because you can grow data structures that have
actual variables in them, and because it is easy to define
nondeterministic methods. I know how Prolog searches for a solution
just as I know how flow of control happens in Lisp, say. I am not
disappointed with Prolog's strict strategy just as I am not
disappointed with Lisp's inability to run programs backwards, say.
I take it as it comes, and it is useful for some things. Talking
hypothetically about the "ideal" language is another topic entirely,
and it only muddies the water to bring Prolog and Lisp into it.
------------------------------
Date: Fri, 13 Sep 85 10:07:09 bst
From: William Clocksin <wfc%computer-lab.cambridge.ac.uk@ucl-cs>
Subject: Prolog on/in Lisp
Compiling Prolog into Lisp is one way to provide a fast
Prolog/Lisp. A student did this as a project last year;
no doubt it has been done elsewhere. The Warren New Engine was
used as a model. The compiler, took Prolog procedures and
generated Lisp code in a mixture of procedure calls and macros.
The clever part was getting backtracking right. This was then
compiled into IBM machine code, and run on a 3081. It was not
fast, owing probably to the large size of code body. I forget
how slow, say 10KLIPS or so. The final speed was not important
for the goals of the project. More important was finding out
what special provision could be made in the future (in the form
of Prolog-specific support) to provide a more efficient system.
Also, it was the student's very first Lisp program, so hhe can be
forgiven for doing a few extremely inefficient things.
------------------------------
Date: Thu, 19 Sep 85 16:15:07 PDT
From: Adolfo Di-Mare <dimare@LOCUS.UCLA>
Subject: DCGs + Left Recursion = (:-[) !
I'm writing a little parser for a Pascal like language.
I was going to copy Wirth's grammar into a DCG Prolog
program, but I noticed that left recursion can't be used.
If you have a rule like:
a --> a, [+], b. a --> b. b --> [b].
it translates into:
a(A, B) :- a(A, C), 'C'(C, +, D), b(D, B). 'C'([H|T],H,T).
Any goal of the form a(Sentence,[]) would make the above
rule recurse until end_of_stack.
(Yes, a([b,+,b],[]) doesn't work either: try it!).
My problem is that the grammars I know for parsing expressions
are left recursive. The example in most Prolog manuals uses left
recursion. I ran it, and I got the following result (I include
the code at the end of the message):
| ?- expr(Z,"2-3-4",[]).
Z = 3 ;
no
| ?- Z is 2-3-4.
Z = -5 ;
no
| ?- halt.
Obviously, the 'standard' example is wrong. My question is: Does
any body know a way to do expressions using DCGs that doesn't make
the grammar look like a plate of spaghetti? I know I could translate
my grammar into Griebach Normal Form (or $%#!"%#$" Normal Form, for
that mater), but I could also as well write the whole parser in
8080 assembly language. Here's the grammar:
Script started on Thu Sep 19 15:16:07 1985
h[2:101] c dcg0
% File : /usr/lib/prolog/teach/dcg0
% Author : lost in the mists of time
% Updated: 23 Nov 1983
% Purpose: the standard example of using Prolog grammar rules
% This is a simple grammar which parses an arithmetic expression (of
% digits and operators) and computes its value.
expr(Z) --> term(X), "+", expr(Y), {Z is X+Y}.
expr(Z) --> term(X), "-", expr(Y), {Z is X-Y}.
expr(Z) --> term(Z).
term(Z) --> number(X), "*", term(Y), {Z is X*Y}.
term(Z) --> number(X), "/", term(Y), {Z is X/Y}.
term(Z) --> number(Z).
number(C) --> "+", number(C).
number(C) --> "-", number(X), {C is -X}.
number(X) --> [C], {48=<C, C=<57, X is C-48}.
% In the last rule, C is the ASCII code of a digit.
% The question
%
% | ?- expr(Z,"-2+3*5+1",[]).
%
% will compute Z=14. The two extra arguments here are because
% grammar rules are in fact merely 'syntactic sugar' for ordinary
% Prolog clauses. Each grammar rule takes an input string, analyses
% some initial portion and produces an output portion (the rest,
% possibly enlarged a bit) for further analysis.
h[2:102] uprolog
CProlog version 1.4d.edai
| ?- [dcg0].
dcg0 consulted 1208 bytes 0.78333 sec.
yes
| ?- expr(Z,"2-3-4",[]).
Z = 3 ;
no
| ?- Z is 2-3-4.
Z = -5 ;
no
| ?- halt.
[ Prolog execution halted ]
h[2:103]
script done on Thu Sep 19 15:18:16 1985
------------------------------
Date: Mon, 16 Sep 85 10:26:55 PDT
From: (Rick McGeer) Mcgeer%ucbkim@Berkeley
Subject: Destructive assignment
I would be extremely surprised if you could get away
without destructive assignment. In addition to the other points
I've raised, consider this: many large programs consist of networked
data structures: that is, some data structure (say A) may be a
substructure of structures (B, C, and D). If the only way to modify
A is to create a new structure, A', then the code that modifies A to
produce A' must also create B', C', and D', and so forth recursively.
Now, it's almost impossible to write modular code in such a
situation: the internals of each data structure in such a network
must be apparent to the code which modifies the leaf structures in
the network, or else the network becomes inconsistent.
This sort of problem creeps up all the time in NL understanding
programs, VLSI layout programs, and algorithm-based algebra programs.
To my knowledge, only toy systems have been written in these areas in
Prolog. Both Dwight Hill at Bell Labs and I have independently tried
to write a real layout program in Prolog, but the mechanics of moving
the data structures around and ensuring that the ds network remains
consistent have forced him to abandon his attempt (and write in C):
I have been forced into a reappraisal.
I agree, if it were merely a matter of efficiency then we
could hope for hardware to work its magic. But it's a matter of
sofware engineering, aswell. A language ultimately stands or falls
on its software engineering aspects and not on its semantics (which
are only important to implementers and, to a minor extent, in
ergonomics). I am afraid that Prolog currently does not support
good software engineering techniques, and in fact makes some
software engineering techniques (modularity, data abstraction)
impossible. Unless and until it supports those techniques at least
to the extent that Lisp does, Prolog is a toy language.
-- Rick.
------------------------------
Date: Mon, 23-Sep-85 07:40:31 PDT
From: Vantreeck%logic.DEC@DECWRL.ARPA
Subject: DCGs + Left Recursion = (:-[) !
You are correct in your assertion that most PROLOGs'
DCGs do not handle left recursion. That's because they're
simple top down parsers. There is a PROLOG DCG parser that
uses bottom up parsing (and can handle left recursions).
The parser is called BUP. Need I say it stands for Bottom
Up Parser?
I don't have the references here at work - the papers
are a couple of years old. I'm sure your UCLA libarary can
do a computer search on BUP. Off the top of my head -- A
brief description can be found in a book by Dahl, Natural
Language Understanding with Logic - it's a collection of
papers from a 1984 symposium in France.
The articles I've read on BUP tend to be of the "Gee,
isn't this wonderful!" variety, rather than delving into
enough implementation detail that someone could use it as a
guide to writing a BUP. If anyone finds a paper that gives
an in depth description of the implementation details,
please post it to the net!
-- George
------------------------------
End of PROLOG Digest
********************