RESTIVO@SU-SCORE.ARPA (07/29/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Monday, 29 Jul 1985 Volume 3 : Issue 34
Today's Topics:
Implementation - Standards & Semantics & POPLOG,
LP Library - Shapiro's Debugger
----------------------------------------------------------------------
Date: Fri, 19 Jul 85 09:49:36 bst
From: William Clocksin <wfc%computer-lab.cambridge@ucl-cs>
Subject: Prolog standards
A number of contributors have recently displayed their
preferences about Prolog syntax, mentioning the context
of a Prolog standard. As Prolog has adherents for nearly
every syntactic convention imaginable, it is clear that a
Standard, if drafted, will not be able to satisfy everybody.
Part of the problem stems from how people like to see their
activity with Prolog: ordinary programming? Making
mathematical formalisms? Designing new languages?
The purpose of a standard is not to force people to program
in a particular way, but to determine whether a given
implementation is standard-conforming. Then, people can
offer standard-conforming implementations, and program in a
standard-conforming way. It need not cramp anyone's style
if they think they have no need to program in a standard
conforming way.
I am a member of a committee set up by the NPL (like the
US's NBS) and the BSI (a standards body) to attempt to draft
a Prolog standard. In our meetings we discuss in depth many
topics. Without wishing to denigrate Prolog Digest or its
contributors, I should say that we probably do a better job
of discussion than the slanging matches in Prolog Digest.
Contributions to Prolog Digest on this topic are important
because it give us on the committee. It would be even more
helpful if opinions were backed up by a short list of Pros
and Cons. For example, if you think that ',' should be
replaced by AND, give Pros and Cons of doing this. (Aside:
actually, ',' is not really an 'and' of any sort given the
usual Prolog execution strategy, so this would be an example
of a Con).
One more point. Believe it or not, there is a negligible
chance of having a national standard adopted as an international
standard unless the ISO 7-bit character set is used. This caters
for international variants, for example Swedish, which has three
extra letters. Character codes are reserved for the variants.
In English we use these slots for curly brackets among other
things. In a standard we are not allowed to use these slots!
This is so that non-English users can actually spell their name
by sacrificing curly brackets. And, we all know there are a lot
of non-English Prolog users. I welcome suggestions on a Prolog
syntax which does not use the characters reserved for national
variants. The relevant character code is ISO 646. The reserved
codes are what the English variant uses for square brackets, curly
brackets, backslash, vertical bar, tilde, up-arrow, at-sign, and
accent. Bother!
-- William Clocksin
------------------------------
Date: Sun 21 Jul 85 17:22:15-MDT
From: Uday Reddy <U-REDDY@UTAH-20.ARPA>
Subject: Semantics of equality
We have had some discussion on this topic a few months
ago, in which Joseph Goguen and Paul Voda participated.
In continuation of this discussion, I compare the
conventional semantics of equality with its
domain-theoretic semantics through a simple and elegant
example suggested to me by Seif Haridi.
Consider the equation
f(x,x) = 1
assuming no other equations for f. Now, given an
expression f(e,d) - where e and d are some expressions -
we want to test if f(e,d) = 1.
By equational logic semantics, f(e,d) would be 1, if e
and d can be proved equal from the equations of the
program. If both e and d are ground, and we know in
advance that they have normal forms, then we can reduce
them to their normal forms and check the normal forms
for syntactic equality. But, when they are non-ground,
or when we do not know if they have normal forms (i.e.
when we do not know if their reductions terminate), we
need to reduce or narrow e and d in parallel, and check
pairwise all their intermediate forms of expressions for
syntactic equality. This leads to potential
combinatorial explosion.
By domain-theoretic semantics, on the other hand, normal
forms of expressions are treated as their "values" and
attain semantic significance. Expressions which do not
have normal forms are deemed to have a special value
"unknown" (or "bottom") as their value. Similarly,
expressions which cannot be reduced completely, such as
f(1,2), are also deemed to have "unknown" as their
value. A partial order is then imposed on the domain of
values, by which "unknown" is treated as less defined
than the others.
"unknown" <= v for all normal values v
v <= v for all normal values v
Further, all functions are required to be monotonic with
respect to this partial order.
Coming to the problem of whether f(e,d) = 1, if e does
not have a normal form, then its value would be
"unknown". What can be the value of
f("unknown",v)
where v is some value? It can only be "unknown" or 1.
If it were 1, then, by the monotonicity of f, f(w,v)
would also have to be 1 for all values w. But, f(w,v) =
"unknown" whenever w and v are distinct values. So,
f("unknown",v) has to be "unknown". By a similar
argument f(e,d) has to be "unknown" if d is "unknown".
Even if it seems paradoxical, f("unknown", "unknown")
would also have to be "unknown".
The operational significance of this observation is that
if either e or d does not have a normal form, then
f(e,d) cannot be equal to 1. Hence, it is legal to
completely reduce e and d to their normal forms and then
check the normal forms for syntactic equality. The
combinatorial explosion is thus avoided.
Note that these considerations would not apply for
g(x,y) = 1
In this case, g("unknown", "unknown") can either be
"unknown" or 1 without violating the monotonicity
restriction. The language designer/implementor chooses
between the two choices depending on whether an
innermost or an outermost strategy is used in the
implementation.
As an aside, it is possible to distinguish between
expressions which do not have normal forms, and those
that have illegitimate normal forms, by introducing
another special value "fail" (similar to Prolog's
notion of fail) with the partial order
"unknown" <= "fail"
"unknown" <= v
v <= v
for all normal values v. Now, the function f would be
f("unknown", "unknown) |
f("unknown", "fail") |
f("fail", "unknown") | = "unknown"
f("unknown", v) |
f(v, "unknown") |
f("fail", "fail") |
f(v, "fail") | = "fail"
f("fail", v) |
f(v, w) = "fail" if v and w are distinct
f(v, v) = 1
for all normal values v and w.
-- Uday Reddy
------------------------------
Date: 23 Jul 1985 23:58:11-BST
From: Aaron Sloman <aarons%svgv@ucl-cs>
Subject: POPLOG - A mixed language development system.
Poplog is available on VAX and DEC 8600 computers.
It includes Prolog (compiled to machine code), Common Lisp (large
subset ready now, remainder available early 1986), POP-11
(comparable in power to Common Lisp, but uses a PASCAL-like syntax),
VED an integrated multi-window multi-buffer screen editor, which can
be used for all interactions with programs, operating system
utilities, online help, program libraries, teaching libraries, etc.
VED includes 'compile this procedure' 'compile from here to here'
'splice output into current file' etc.)
Incremental compilers are provided for Prolog, Lisp, and
POP-11. All the languages compile to the same intermediate
POPLOG 'Virtual machine' language, which is then compiled
to machine code. The 'syscompile' facilities make it easy
to add new front end compilers for additional languages,
which all share the same back-end compiler, editor and
environmental facilities. Mixed language facilities allow
sharing of libraries without re-coding and also allow
portions of a program to be written in the language which
is most suitable.
Approximate recent Prolog benchmarks, for naive reverse test,
without mode declarations:
VAX/780 + VMS 4.2 KLIPS
VAX/750 + Unix 4.2 2.4 KLIPS (750+Systime accelerator)
DEC 8600 13.0 KLIPS
SUN2 + Unix 4.2 2.5 KLIPS (also HP 9000/200)
GEC-63 + Unix V approx 6 KLIPS
The Prolog is being substantially re-written, for greater
modularity and improved efficiency. Mode declarations should
be available late 1985, giving substantial speed increase.
POP-11 and Common Lisp include both dynamic and lexical scoping,
a wide range of data-types, strings, arrays, infinite precision
arithmetic, hashed 'properties', etc. (Not yet packages, rationals
or complex numbers.) POP-11 includes a pattern-matcher (one-way
unification) with segment variables and pattern-restrictors.
External_load now allows 'external' modules to be linked in and
unlinked dynamically (e.g. programs written in C, Fortran, Pascal,
etc.). This almost amounts to a 'rapid prototyping' incremental
compiler for such languages.
A considerable number of AI-projects funded by the UK Alvey
Programme in universities and industry now use a mixture of
Prolog and POP-11, within Poplog.
Enquiries:
UK Educational institutions:
Alison Mudd,
Cognitive Studies Programme,
Sussex University,
Brighton, England. 0273 606755
-- Aaron Sloman
------------------------------
Date: Thu 25 Jul 85 14:34:21-CDT
From: Bill Murray <ATP.Murray@UTEXAS-20.ARPA>
Subject: Shapiro's Prolog debugging system
The next message contains the code from Ehud Shapiro's book
Algorithmic Program Debugging for a Prolog debugging system and for a
model inference system which can synthesize small Prolog programs from
examples. Instructions on how to run the scenarios are also included.
The instructions are in the file EXAMPLES..0. Caveats are that the
code runs on PROLOG on the DEC 2060, version number 3.3, but that it
won't necessarily run on other Prologs without some modifications
to account for dialectal differences [e.g. it doesn't run immediately
in Quintus PROLOG].
Regards,
-- Bill
[ the debugger is available as
SCORE:<Prolog>Shapiro_Debugger.pl -ed ]
------------------------------
End of PROLOG Digest
********************