RESTIVO@SU-SCORE.ARPA (05/23/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Thursday, 23 May 1985 Volume 3 : Issue 24
Today's Topics:
Query - Common Lisp Prologs & External calls,
Implementation - CP,
Announcement - 1985 LP Symposium & Wiezmann Workshop
----------------------------------------------------------------------
Date: Mon 20 May 85 13:07:48-EDT
From: Vijay <Vijay.Saraswat@CMU-CS-C.ARPA>
Subject: Common Lisp Prologs.
I am interested in finding out if there are any
commercially available Prolog programming
environments (compiler/interpreter/debugger/editor)
written in CommonLisp.
Also, I am interested in comments from anyone who has
worked with Symbolics Prolog (I am not referring to Ken
Kahn's implementation) with regard to speed.
Cheers,
-- Vijay.
------------------------------
Date: Mon, 20 May 85 14:06:59 pdt
From: Allen VanGelder <AVG@Diablo>
Subject: External calls
We are in a similar situation at Stanford, and
would appreciate copies of any code that does
external calls.
Thank you.
------------------------------
Date: Sun, 19 May 85 03:22:37 cdt
From: (Raghunath Ramakrishnan) Raghu@UT-sally.ARPA
Subject: The Annotation '%'
This is a continuation of the discussion of the read-only annotation
in CP. While the current definition (disallowing '?' in guards)
eliminates some of the ambiguities in the definition of
'?', it is still difficult to undertand in programs because
it can be passed on at runtime, and further, the unification
is order-dependent.
The '%' annotation is an attempt to provide the same power (i.e. any
programming techniques in CP should be available) but with a semantic
that is static and independent of the order of unification.
The following is a definition and brief description of '%'.
A more complete description can be found in a forthcoming UT
Austin Tech Report. If anyone is interested in a copy,
please send me your address (Mail it to Raghu@UT-Sally.
Responses may be delayed since I'll be absent for about a month).
The clauses in a program are viewed as templates which can be used
to create processes. A call is a specification for a
required process and we attempt to create such a process by
matching the call with some clause head and satisfying the
corresponding guard.
The annotation '%' has the same semantics whether it
annotates a variable in a call or in a clause head. It is
a guarantee that the process in which it appears (it
may appear either in the call which specifies the required
process or a clause head being matched in an attempt to
spawn such a process) will not instantiate it to a
non-variable. In other words, such an instantiation
must be due to some other process (a sibling of the
call or a sibling of an ancestor), and this fact can be
used to make the process wait for input (which may in fact
decide the nature of this process since attempts to match
the call against a clause head may be delayed until the
input is available). These semantics are guaranteed
regardless of the order of unification.
The unification rules are defined by this table:
| HEAD
--|---------------------------------------------------------------
| TERM VAR TERM% VAR%
|
G |TERM Unify(GL,HD) HD = Ref(GL) Fail Fail
O |
A |VAR GL = Ref(HD) HD = Ref(GL) Fail Fail
L |
|TERM% Fail Fail Unify(GL,HD) HD = Ref(GL)
|
|VAR% Fail Fail Suspend HD = Ref(GL)
Note that the '%' annotation is never passed on due to unification.
Also, like CP's read-only annotation, it is not inherited.
'%' annotations in the call are used when the corresponding
arguments in the target clause head are annotated, and thus
ensure that a clause is being used correctly (with respect
to its annotations).
The intended semantics for '%' can be achieved with these
rules only if some syntactic restrictions are met. The
idea behind these restrictions is to prevent this process
from instantiating a %-annotated variable during the process
of matching the call against the head. Compile time
checking can be used to enforce all these restrictions. We
summarise them below:
1. Each variable occurrence in a clause head is unique.
2. A %-annotated variable in a clause head is only used
as a %-annotated variable throughout that clause.
3. All superior terms of a %-annotated term or variable in
a clause head are %-annotated. (Given the rule that only
annotated variables or terms unify, this in
effect requires superior terms of all annotated
terms or variables - in both calls and clause
heads - to be annotated.)
4. Each %-annotated variable on the right hand side of a
clause that does not appear in the clause head is:
a. Used consistently in each call (ie. it is always
%-annotated or always unannotated).
b. Appears in at least one call without being annotated.
If a given program passes these checks, the unification algorithm
described above ensures the intended semantics. If a process
suspends, it is waiting for some other process to instantiate a
%-variable. Incidentally, 4.b above detects one obvious instance
where such a wait could be futile. The problems involved in detecting
such failures are the familiar starvation and deadlock problems of
traditional process models since we have eliminated the side effects
of unification which enable a process to unexpectedly 'feed' itself!
The only other way in which the annotations intrude (in the
sense that they sometimes lead to unexpected situations) is
that a call may fail because no clause head matching the
annotations is found. We view this as being in the same
class of errors as there not being a clause head with the
same functor as the call or the same number of arguments
since the annotations are as much a part of the static
description of a clause as the functor name or number of
arguments.
The Programming Techniques Supported by '%'
The %-annotation supports all the programming techniques
that the read-only annotation in Concurrent Prolog does. It
does not allow us to create protected channel variables
(ie. specify that a process always expects to find a
given argument to be a variable), and it is not intended
to do so. We note that the current definition of the
read-only annotion in CP, as opposed to the original
definition, does not permit this either.
The unification algorithm described here will be
implemented shortly in Prolog, along with a compile-time
checking routine.
Several examples are included in a separate posting. These
discuss the decisions made in the definition of '%', the
syntactic restrictions required to guarantee its semantics,
and the programming techniques it supports.
-- Raghu
------------------------------
Date: Mon, 20 May 85 18:38:04 -0200
From: Ehud Shapiro <Udi%Wisdom@WISCVM.ARPA>
Subject: Announcement
The Second Weizmann Institute Workshop
on
Logic Programming and Parallel Processing
The Weizmann Institute of Science
June 4-5, 1985
(preliminary program)
Tuesday, June 4:
Morning Welcome
The Flat Concurrnt Prolog compiler and system:
A Status Report.
Ehud Shapiro, Weizmann Institute of Science
ICOT's project: a trip report and critical evaluation.
Marc Snir, Hebrew University
Adapting Warren's abstarct machine to Flat Concurrent
Prolog. Avshalom Houri, Weizmann Institute of Science
High Level Characteristics and Specification
of a Logic Computer System.
Toni Kusalik, University of British Columbia
Afternoon
MOS: Unix on a multiprocessor.
Amnon Barak, Hebrew University
Quadtrees in Concurrent Prolog.
Shimon Edelman, Weizmann Institute of Science
TBA
Mats Carlson, Uppsala University
Solution-stream based semantics for Prolog.
Nissim Francez, Technion, and
Amir Pnueli, Weizmann Institute of Science
Concurrent Prolog for VLSI design simulation
David Veinbaum, Tel Aviv University
Wednesday, June 4:
Morning
Meta-interpreters for real, or the magic of
partial evaluation.
Ehud Shapiro, Weizmann Institute of Science
An FCP partial evaluator.
Shmuel Safra, Weizmann Institute of Science
TBA
Ran Ginosar, Technion
DARPA's strategic computing project.
Robert Kahn, DARPA
Afternoon
A Concurrent Prolog based region finding algorithm.
Lisa Hellerstein, UC Berkeley
Compiling Or-parallelism into And-parallelism.
Michael Codish, Weizmann Institute of Science
TBA
Oded Shmueli, Technion
An abstract machine for Ueda's language of
Guarded Horn Clauses.
Jacob Levi, Weizmann Institute of Science
------------------------------
Date: 17 May 1985 11:54:34-PDT
From: Conery%UOregon@csnet-relay.arpa
Subject: 1985 Symposium
-- Preliminary Schedule --
-- 1985 Symposium on Logic Program --
For more information, contact:
John Conery (JC@UOregon.csnet) 503-686-4408
Jacques Cohen (JC@Brandeis.csnet) 617-647-3370
MONDAY, July 15
Tutorials (Two parallel sessions, 9:00 - 4:30)
(Two more tutorials on Friday)
Expert Systems Using Prolog, Bob Kowalski, Imperial College
Parallel Logic Programming, Gary Lindstrom, Univerity of Utah
8:00 p.m. - 10:00 p.m. Early Registration and Reception
TUESDAY, July 16, 1985
8:00 a.m. - 9:00 a.m. Registration
9:00 a.m. - 10:30 a.m. KEYNOTE SPEAKER: Robert Kowalski,
Imperial College London, England
11:00 a.m. - 12:30 p.m. PARALLELISM
Semi-intelligent Backtracking of Prolog
Based on a Static Data Dependency
Analysis, Jung-Herng Chang and
Alvin M. Despain, University of California,
Berkeley
User-defined Parallel Control Strategies,
J. I. Glasgow, M. A. Jenkins, and C. D.
McCrosky,Queen's University, Canada
AND-parallelism with Intelligent
Backtracking for Annotated Logic
Programs, J. Maluszynski, Linkoping
University and P. Dembinski, Chalmbers
University of Technology, Sweden
12:30 p.m. - 2:00 p.m. Lunch
2:00 p.m. - 3:30 p.m. EXTENSIONS
An experiment in Programming with Full
First-Order Logic, Zerkis D.
Umigar and Vijay Pitchumani,
Syracuse University
A Meta-Level Extension of Prolog,
Kenneth A. Bowen, Syracuse
University, and Tobias Weinberg, Digital
Equipment Corporation
Logic Programming Cum Applicative
Programming, Nachum Swjodershowitz and
David Plaisted, University of
Illinois at Urbana Champaign
3:30 p.m. - 4:00 p.m. Coffee Break
4:00 p.m. - 5:30 p.m. LANGUAGE ISSUES
On the Treatment of Cuts in Prolog Source-Level
Tools, R. A. O'Keefe, University of Edinburgh,
United Kingdom
All Solutions Predicates in Prolog, Lee Naish,
University of Melbourne, Australia
Unification-free Execution of Logic Programs,
Jan Komorowski, Aiken Computation Laboratory,
Harvard University and Jan Maluszynski,
Linkoping University, Sweden
Wednesday, July 17, 1985
9:00 a.m. - 10:30 a.m. INVITED SPEAKER
Dr. Herve Gallaire, European Computer Research
Center, Munich, West Germany
10:30 a.m. - 11:00 a.m. Coffee break
11:00 a.m. - 12:30 p.m. CONCURRENT PROLOG
Concurrent Prolog in a Multi-process Environment,
Rosanna Lee and Randy Goebel, University of
Waterloo, Canada
A sequential Implementation of Concurrent Prolog
Based on the Shallow Binding Scheme, Toshihiko
Miyazaki, Akikazu Takeuchi and Takashi Chikayama,
ICOT, Japan
12:30 p.m. - 2:00 p.m. Lunch
2:00 p.m. - 3:30 p.m. SEMANTICS
The Declarative Semantics of Logical Read-only
Variables, G. Levi and C. Palamidessi,
Universita'di Pisa, Italy
Narrowing as the Operational Semantics of Functional
Languages, Uday Reddy, University of Utah
Towards an Algebra for Constructing Logic Programs,
R.A. O'Keefe, University of Edinburgh, United
Kingdom
3:30 p.m. - 4:00 p.m. Coffee Break
4:00 p.m. - 5:30 p.m. IMPLEMENTATION ISSUES
A Microcoded Unifier for Lisp Machine Prolog, Mats
Carlssn, Uppsala University, Sweden
SLOG: A Logic Programming Language Interpreter Based
on Clausal Superposition and Rewriting, Laurent
Fribourg, Laboratoires de Marcoussis, France
A Real Time Garbage Collector for Prolog, Edwin
Pittombils and Maurice Bruynooghe, K.U. Leuven,
Belgium
Evening Banquet Speaker
Dr. Maurice Wilkes, Digital Equipment Corporation
Thursday, July 19, 1985
9:00 a.m. - 10:30 a.m. THEORY
recursive Unsolvability of Determinacy, Solvable
Cases of Determinacy, and Their Applications to
Prolog Optimization, Jajime Sawamura and Taku
Takeshima, International Institute for Advanced
Study of Social Information Science, Japan
Graph-based Logic Programming Interpreters, Jean
Gallier and Stan Raatz, University of Pennsylvania
Surface Deduction: A Uniform Mechanism for Logic
Programming, P. T. Cox and T. Pietrzykowski,
Technical University of Nova Scotia, Canada
10:30 a.m. - 11:00 a.m. Coffee Break
11:00 a.m. - 1:00 p.m. SPECIAL TOPICS
Towards a Programming Environment for Large
Prolog Programs, Jan Chomicki and Naftaly H.
Minsky, Rutgers University
Modular Logic Programming of Compilers, Harald
Ganzinger and Michael Hanus, University Dortmund,
West Germany
An(other) Integration of Logic and Functional
Programming, Amitabh Srivastava, Don Oxley and
Aditya Srivastava, Central Research Laboratories,
Texas Instruments, Inc.
A Technique for Doing Lazy Evaluation in Logic,
Sanjai Narain, Rand Corp.
FRIDAY July 19
Tutorials: (Two concurrent sessions, 9:00 - 4:30)
"Concurrent Logic Programming Techniques",
Ehud Shapiro, Weizmann Institute
"Prolog and Software Engineering",
Susan Gerhart, Wang Institute.
------------------------------
End of PROLOG Digest
********************