PROLOG-REQUEST@SU-SCORE.ARPA (06/24/83)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Friday, 24 Jun 1983 Volume 1 : Issue 11
Today's Topics:
Implementations - VAX Prolog & Paranoia,
Applications - Using Prefix Operators & Definitions
----------------------------------------------------------------------
Date: Wednesday, 15-Jun-83 19:24:56-BST
From: RAE (on ERCC DEC-10) <Rae@EDXA>
Subject: Prolog For The VAX
Steve,
You correctly state that POPLOG and Franz have been identified
by the UK IKBS initiative as systems for getting people off the ground
in IKBS. DEC-20 Prolog is not classified with them, unfortunately, as
the other vital ingredient for the software infra-structure is the
operating system, and UNIX has been adopted. So DEC-20 Prolog will
not be relevant.
You should also, to be fair, point out that C-Prolog has also been
identified for providing Prolog capability.
-- Robert
------------------------------
Date: Sat 18 Jun 83 12:49:21-PDT
From: PEREIRA@SRI-AI.ARPA
Subject: Re: Prolog For The Vax
As a result of the paranoia induced by the Japanese 5th Generation
proposals, there was a lot of discussion about what the UK should do
to keep up with the foreign competition in AI and computing in
general. Eventually several government initiatives where started,
amounting to several 100 million dollars spread over five years or so.
In particular, the Science and Engineering Research Council (SERC),
whose closest US analogue is the NSF, started the Intelligent
Knowledge Based Systems initiative (IKBS), which is applied AI under a
different name (it seems the name "AI" is not very popular in UK
government and academic circles). Discussions sponsored by the IKBS
initiative have decided on a common software base, built around Unix
{a trademark of Bell Labs.}, Prolog (POPLOG and C-Prolog) and Lisp
(Franz). The machines to be used are VAXes and PERQs (the UK computer
company ICL builds PERQs under license, have implemented a derivative
of Unix on it, so this is a case of "support your local computer
manufacturer").
The fact that none of the systems mentioned above is nearly the ideal
for AI research is recognized by many of the UK researchers, but less
so by the administrators. Efforts to build a really efficient
portable compiler-based Prolog that would be for the new machines what
DEC-10/20 Prolog is for the machines it runs on have been hampered by
the sluggish response of The Bureaucrats, and by uncertainty about how
that huge amount of money was going to be allocated.
However, implementation of a portable compiler - based Prolog is now
going on at Edinburgh. Robert Rae is certainly in a better position
than I to describe how the project is progressing.
-- Fernando Pereira
------------------------------
Date: 21 June 1983 1023-EDT (Tuesday)
From: Vijay.Saraswat@CMU-CS-A (C410VS90)
Subject: Defining 'Equal' in Prolog
Here is a much shorter brain_teaser than the usual ones:
Define a predicate equal(X, Y) which is true iff X and Y are the
'same' terms up to renaming of variables (X and Y should not be
instantiated as a result of the call to equal). Note however that
\+ equal(foo(X,X), foo(Y,Z))
but of course:
equal(foo(X,Y),foo(D,O)).
Here is a 'quick and dirty' implementation:
eq(X,Y):-
assert(temp1(X)),
assert(temp2(Y)),
retract(temp1(A)),
retract(temp2(B)),
numbervars(A, 0,M),
!, numbervars(B, 0, M),
!, A == B.
------------------------------
Date: Monday, 20-Jun-83 22:29:19-BST
From: RICHARD HPS (on ERCC DEC-10) <okeefe.r.a.@edxa>
Reply-to: okeefe.r.a.%edxa%ucl-cs@isid
Subject: Operators and Prolog, a reply to Steve Hardy
Using Operators in Prolog.
As Steve Hardy says, using :-op to tell the Prolog operator
precedence parser about his operators gives him two problems (by
the way, please don't call syntax properties "modes"; confusion
between :-op declarations and :-mode declarations is something the
Prolog community can do without)
1) The parser accepts more things than he expected.
This is a general property of operator precedence parsing,
and is one of the reasons people bother about LL and LR
parsing. Possibly the only way around it would be to have
an extra "legality" check in the routine that bolts terms
together.
2) They do not ascribe the structures he expected to some terms.
He cites "if all x:happy(x) then arrived(utopia)".
It is important to realise that the Prolog reader is NOT
''mis-parsing'' [sic] these terms, it is doing exactly what
he told it to. The problem is that he couldn't tell it what
he really wanted. All he wants is to give ':' narrow left
scope and wide right scope, and almost all operator precedence
parsers would be let him have exactly that. This is NOT a
problem with operator precedence parsing.
In a fragment "A + B", where "+" indicates any binary operator,
there are five priorities to be considered:
OL -- the priority the Operator wants on its Left
AL -- the priority the form A actually has
OR -- the priority the Operator wants in its Right
AR -- the priority the form B actually has
OC -- the priority the Operator ascribes to the Combination
To be well formed, the fragment must satisfy AL <= OL & AR <= OR.
The priority of the whole will then be OC. As you see, there are
THREE priorities associated with the operator. Dec-10 Prolog and the
systems based on it impose the restriction that
OC-1 <= OL <= OC & OC-1 <= OR <= OC
This was largely in the interests of simplicity, so that people would
only have to bother about one number.
All the Prolog parsers known to me interface to the syntax
properties through a table
isop(+Operator, +Class, -OL, -OC, -OR)
where Class is prefix|infix|postfix. The representation depends
on whether the implementation language is Prolog, Pseudo-Prolog,
IMP, C, or PDP-11 assembler, but the basic idea is the same. The
parsers, therefore, are *already* able to cope with Steve Hardy's
example, and it is only a matter of generalising :-op suitably.
This need not involve anyone in system hackery. The Dec-10
Prolog tokeniser has been available to user programs for nearly
two years. If you look in the VCHECK program in the toolkit part
of the <PROLOG> directory at SRI-AI (see Fernando Pereira's
message in the Prolog digest about [V1 #8 -ed] that directory
and what is in it) you will find an example of its use. Beware:
it is only available to COMPILED code. Alan Mycroft of the Edinburgh
CS department keep asking for changes to the syntax of Prolog, and I
finally ripped out the 'read'/1 routine, made it work as a
user-level routine, tidied it up, added a few comments, and said
"here you are, you want it, you write it, and tell us about it
when you've done". He did in fact find one or two minor bugs in
the 'read'/1 predicate, and fixed them in this version, but
decided to live with the syntax as it was. This utility should
also be in <PROLOG>@SRI-AI; at Edinburgh the files are
RDTOK.PL -- interface to the tokeniser
NREAD.PL -- editable 'read'
NREAD is "semi-portable"; if you provide a tokeniser which
delivers the right sort of tokens, it doesn't require anything
that a good Prolog shouldn't already have. The one thing that
might be lacking in some (and is lacking in older versions of C
Prolog) is current_op, but that is precisely what Steve Hardy
needs to change.
Steve Hardy also has some critical comments about DCGs. He
says "DCGs have more of the flavour of a user-group library
routine than of a carefully thought out feature of the language."
In fact DCGs (or rather "grammaires de metamorphose") are the
reason why Prolog exists. DCGs are just a notational variant of
Horn clauses, nothing more. They were intended as a tool for
writing NATURAL language grammars, e.g. French, Spanish,
Portuguese, English &c, and have proved to be very good at it.
Writing a grammar that is driven off keywords isn't too hard.
Writing a grammar based on a large set of operators at several
different priority levels, especially in Prolog where the syntax
properties of an atom may change from one call to the next, is
very much harder. DCGs and operator precedence are different
solutions to the same parsing problem, and you can't expect
combining them to be any easier than combining LL and LR parsing
in the same parsing machine.
There is no great problem in getting error messages from a
DCG. The problem is in relating it to the original text, which
may never have existed. NREAD gets around the problem by saving
the length of the unparsed end, failing out, and then read's 2nd
alternative is to print the erroneous text. Given that DCGs use
lists, and do not work one token at a time, it is difficult to
see what better could be done. Can anyone tell me how you get
good error messages out of an ATN? Don't forget backtracking!
It is also agreed that more extensibility in the syntax of
Prolog would be a Good Thing. Distfix operators (e.g. all _ : _
or if _ then _ else _) are the most promising candidate, if only we
can find someone to adapt the HOPE parser. If anyone gets distfix
working, please do it by adapting NREAD.PL, please maintain the
property that an atom can be infix, prefix, postfix, any two, or
all three with possibly differing priorities, and please tell the
Prolog Digest about it when it works.
Steve Hardy's complaint "I'd like the internals of the Prolog
system to be more accessible, especially the routines for reading
and writing" is understandable, but years late (unless he is
***Sender closed connection***
=== Network Mail from host su-score on Fri Jun 24 00:43:41 ===PROLOG-REQUEST@SU-SCORE.ARPA (06/24/83)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Friday, 24 Jun 1983 Volume 1 : Issue 11
Today's Topics:
Implementations - VAX Prolog & Paranoia,
Applications - Using Prefix Operators & Definitions
----------------------------------------------------------------------
Date: Wednesday, 15-Jun-83 19:24:56-BST
From: RAE (on ERCC DEC-10) <Rae@EDXA>
Subject: Prolog For The VAX
Steve,
You correctly state that POPLOG and Franz have been identified
by the UK IKBS initiative as systems for getting people off the ground
in IKBS. DEC-20 Prolog is not classified with them, unfortunately, as
the other vital ingredient for the software infra-structure is the
operating system, and UNIX has been adopted. So DEC-20 Prolog will
not be relevant.
You should also, to be fair, point out that C-Prolog has also been
identified for providing Prolog capability.
-- Robert
------------------------------
Date: Sat 18 Jun 83 12:49:21-PDT
From: PEREIRA@SRI-AI.ARPA
Subject: Re: Prolog For The Vax
As a result of the paranoia induced by the Japanese 5th Generation
proposals, there was a lot of discussion about what the UK should do
to keep up with the foreign competition in AI and computing in
general. Eventually several government initiatives where started,
amounting to several 100 million dollars spread over five years or so.
In particular, the Science and Engineering Research Council (SERC),
whose closest US analogue is the NSF, started the Intelligent
Knowledge Based Systems initiative (IKBS), which is applied AI under a
different name (it seems the name "AI" is not very popular in UK
government and academic circles). Discussions sponsored by the IKBS
initiative have decided on a common software base, built around Unix
{a trademark of Bell Labs.}, Prolog (POPLOG and C-Prolog) and Lisp
(Franz). The machines to be used are VAXes and PERQs (the UK computer
company ICL builds PERQs under license, have implemented a derivative
of Unix on it, so this is a case of "support your local computer
manufacturer").
The fact that none of the systems mentioned above is nearly the ideal
for AI research is recognized by many of the UK researchers, but less
so by the administrators. Efforts to build a really efficient
portable compiler-based Prolog that would be for the new machines what
DEC-10/20 Prolog is for the machines it runs on have been hampered by
the sluggish response of The Bureaucrats, and by uncertainty about how
that huge amount of money was going to be allocated.
However, implementation of a portable compiler - based Prolog is now
going on at Edinburgh. Robert Rae is certainly in a better position
than I to describe how the project is progressing.
-- Fernando Pereira
------------------------------
Date: 21 June 1983 1023-EDT (Tuesday)
From: Vijay.Saraswat@CMU-CS-A (C410VS90)
Subject: Defining 'Equal' in Prolog
Here is a much shorter brain_teaser than the usual ones:
Define a predicate equal(X, Y) which is true iff X and Y are the
'same' terms up to renaming of variables (X and Y should not be
instantiated as a result of the call to equal). Note however that
\+ equal(foo(X,X), foo(Y,Z))
but of course:
equal(foo(X,Y),foo(D,O)).
Here is a 'quick and dirty' implementation:
eq(X,Y):-
assert(temp1(X)),
assert(temp2(Y)),
retract(temp1(A)),
retract(temp2(B)),
numbervars(A, 0,M),
!, numbervars(B, 0, M),
!, A == B.
------------------------------
Date: Monday, 20-Jun-83 22:29:19-BST
From: RICHARD HPS (on ERCC DEC-10) <okeefe.r.a.@edxa>
Reply-to: okeefe.r.a.%edxa%ucl-cs@isid
Subject: Operators and Prolog, a reply to Steve Hardy
Using Operators in Prolog.
As Steve Hardy says, using :-op to tell the Prolog operator
precedence parser about his operators gives him two problems (by
the way, please don't call syntax properties "modes"; confusion
between :-op declarations and :-mode declarations is something the
Prolog community can do without)
1) The parser accepts more things than he expected.
This is a general property of operator precedence parsing,
and is one of the reasons people bother about LL and LR
parsing. Possibly the only way around it would be to have
an extra "legality" check in the routine that bolts terms
together.
2) They do not ascribe the structures he expected to some terms.
He cites "if all x:happy(x) then arrived(utopia)".
It is important to realise that the Prolog reader is NOT
''mis-parsing'' [sic] these terms, it is doing exactly what
he told it to. The problem is that he couldn't tell it what
he really wanted. All he wants is to give ':' narrow left
scope and wide right scope, and almost all operator precedence
parsers would be let him have exactly that. This is NOT a
problem with operator precedence parsing.
In a fragment "A + B", where "+" indicates any binary operator,
there are five priorities to be considered:
OL -- the priority the Operator wants on its Left
AL -- the priority the form A actually has
OR -- the priority the Operator wants in its Right
AR -- the priority the form B actually has
OC -- the priority the Operator ascribes to the Combination
To be well formed, the fragment must satisfy AL <= OL & AR <= OR.
The priority of the whole will then be OC. As you see, there are
THREE priorities associated with the operator. Dec-10 Prolog and the
systems based on it impose the restriction that
OC-1 <= OL <= OC & OC-1 <= OR <= OC
This was largely in the interests of simplicity, so that people would
only have to bother about one number.
All the Prolog parsers known to me interface to the syntax
properties through a table
isop(+Operator, +Class, -OL, -OC, -OR)
where Class is prefix|infix|postfix. The representation depends
on whether the implementation language is Prolog, Pseudo-Prolog,
IMP, C, or PDP-11 assembler, but the basic idea is the same. The
parsers, therefore, are *already* able to cope with Steve Hardy's
example, and it is only a matter of generalising :-op suitably.
This need not involve anyone in system hackery. The Dec-10
Prolog tokeniser has been available to user programs for nearly
two years. If you look in the VCHECK program in the toolkit part
of the <PROLOG> directory at SRI-AI (see Fernando Pereira's
message in the Prolog digest about [V1 #8 -ed] that directory
and what is in it) you will find an example of its use. Beware:
it is only available to COMPILED code. Alan Mycroft of the Edinburgh
CS department keep asking for changes to the syntax of Prolog, and I
finally ripped out the 'read'/1 routine, made it work as a
user-level routine, tidied it up, added a few comments, and said
"here you are, you want it, you write it, and tell us about it
when you've done". He did in fact find one or two minor bugs in
the 'read'/1 predicate, and fixed them in this version, but
decided to live with the syntax as it was. This utility should
also be in <PROLOG>@SRI-AI; at Edinburgh the files are
RDTOK.PL -- interface to the tokeniser
NREAD.PL -- editable 'read'
NREAD is "semi-portable"; if you provide a tokeniser which
delivers the right sort of tokens, it doesn't require anything
that a good Prolog shouldn't already have. The one thing that
might be lacking in some (and is lacking in older versions of C
Prolog) is current_op, but that is precisely what Steve Hardy
needs to change.
Steve Hardy also has some critical comments about DCGs. He
says "DCGs have more of the flavour of a user-group library
routine than of a carefully thought out feature of the language."
In fact DCGs (or rather "grammaires de metamorphose") are the
reason why Prolog exists. DCGs are just a notational variant of
Horn clauses, nothing more. They were intended as a tool for
writing NATURAL language grammars, e.g. French, Spanish,
Portuguese, English &c, and have proved to be very good at it.
Writing a grammar that is driven off keywords isn't too hard.
Writing a grammar based on a large set of operators at several
different priority levels, especially in Prolog where the syntax
properties of an atom may change from one call to the next, is
very much harder. DCGs and operator precedence are different
solutions to the same parsing problem, and you can't expect
combining them to be any easier than combining LL and LR parsing
in the same parsing machine.
There is no great problem in getting error messages from a
DCG. The problem is in relating it to the original text, which
may never have existed. NREAD gets around the problem by saving
the length of the unparsed end, failing out, and then read's 2nd
alternative is to print the erroneous text. Given that DCGs use
lists, and do not work one token at a time, it is difficult to
see what better could be done. Can anyone tell me how you get
good error messages out of an ATN? Don't forget backtracking!
It is also agreed that more extensibility in the syntax of
Prolog would be a Good Thing. Distfix operators (e.g. all _ : _
or if _ then _ else _) are the most promising candidate, if only we
can find someone to adapt the HOPE parser. If anyone gets distfix
working, please do it by adapting NREAD.PL, please maintain the
property that an atom can be infix, prefix, postfix, any two, or
all three with possibly differing priorities, and please tell the
Prolog Digest about it when it works.
Steve Hardy's complaint "I'd like the internals of the Prolog
system to be more accessible, especially the routines for reading
and writing" is understandable, but years late (unless he is
referring to PopLog?). The tokeniser IS accessible in Dec-10
Prolog. {It isn't in C-Prolog, but it would be about a week's
work to make it accessible. I have a thesis to write. Volunteers?}
The parser IS available as a library file you can edit. In C Prolog,
though the parser and tokeniser aren't modifiable, you CAN apply
your own macro-processing to everything read, by adding your own
clauses to expand_term/2. {expand_term/2 in Dec-10 Prolog isn't
user-extensible, but could be made so if Dec-10 Prolog were still
being worked on.} The write routine, under the name 'print'/1, IS
extensible, just add clauses to 'portray'/1. (Again, some versions
of C Prolog have been released where print doesn't call portray at
each level. You can tell by looking at pl/init. If you have an
old version, ask for a new one.)
DCGs, by the way, are implemented by macro-expansion in
expand_term. They ARE a "one[2] page library procedure", and exactly
what DCGs are and how they are implemented is fully described in
the Clocksin and Mellish book. (Chris Mellish is at Sussex, and
wrote the Prolog component of PopLog.) The preprocessor in that
book actually contains a bug, and I recently submitted a corrected
and improved version of the whole thing to net.sources.
Pop-2, by the way, provides the analogue of yfx operators with
priorities 1..9 . Dec-10 WonderPop also provides 'form' declarations
form keyword {argument keyword}... ;
template
endform
where argument --> reading-function-name : argname
which lets different arguments be parsed by different routines. This
gives you a sort of distfix, and is quite painless to use. I do not
know what Pop-11 (the Pop part of PopLog) lets you do.
------------------------------
End of PROLOG Digest
********************