LAWS@SRI-AI.ARPA (02/21/85)
From: AIList Moderator Kenneth Laws <AIList-REQUEST@SRI-AI.ARPA>
AIList Digest Thursday, 21 Feb 1985 Volume 3 : Issue 24
Today's Topics:
Request - Seminar Tapes,
Functional and Logic Programming,
Correction - Bertrand Constraint Language,
Seminars - Inductive Theorem Proving in Prolog (GE) &
Knowledge-Based Software Development (SU) &
Cooperation Among Intelligent Agents (SU) &
Programming in Concurrent Prolog (CMU) &
Self-Organizing Retrieval for Graphs (UT)
----------------------------------------------------------------------
Date: Wed, 20 Feb 85 20:46:40 cst
From: Raj Doshi <doshi%umn.csnet@csnet-relay.arpa>
Subject: Slightly Depressed....
I always see notices on the AIList digest about fantastic seminars
all over the country (especially at BBN, Stanford, etc.) and get
depressed because :
(1) I can't attend them,
(2) The transcript/recording is never published, nor accessible
(3) So there is no way for an interested person to learn.
I was wondering if somebody/anybody/any organization {BBN/or any
university libraries (Stanford libraries)} would keep recordings
on tape/cassette ??.
(1) Either record any & all public seminars advertised over the net
(Tapes/Video ?).
(2) Or, if some number of people show interest (say 50) within a
specified period of time (2 weeks?) of the first (or last)
time of announcement (on AIList Digest?) then, record the
requested seminar.
(3) Charge some reasonable fee for it (please keep the poor
grad-student in mind; Tapes for grads; Videotapes for industry folks).
I think I should probably be writing this to the respective ad-
mintrative departments and/or to the Librarians.
But, I think :
[1] I don't have the time to write to these administrative
departments.
[2] I don't even have the names of the persons who might be able to
make these (expensive) decisions.
[3] I don't have any clout; It will take more than one person to
voice the need.
Do the Stanford or BBN librarians read this AIList digest?? Can
somebody send this messsage over to a net where this message will
be read by administrators and/or librarians ??
Does anybody else feel so deprived ??
Any other Issues or Ideas or Pros or Cons or Problems ??
--Raj Doshi
Graduate Student,
University of Minnesota
csnet: doshi.umn-cs@csnet-relay
[While seminars are rarely recorded, they usually spring from or lead
to a conference paper or dissertation. Sending a message to the author
(perhaps via the seminar host) will often get you some interesting
pre/reprints or literature citations.
I don't know whether administrators respond to net messages, but you
can often get a lead on the proper address for an administrative
request by writing to "postmaster" at any site. The various postmasters
have been a great help to me in distributing the AIList. -- KIL]
------------------------------
Date: Thu 7 Feb 85 11:09:03-PST
From: Joseph A. Goguen <GOGUEN@SRI-AI.ARPA>
Subject: Functional and Logic Programming (long message)
[Forwarded from the Prolog Digest by Laws@SRI-AI.]
Here's a little more for those who have been eagerly
following recent discussions in the Digest about the
relationship between logic and functional programming.
This appears to be a very exciting field just now, with
a rapidly expanding literature, much of it not yet even
published. First, I want to add some bits of information
to the very helpful classification that Reddy recently
sketched for the Digest. Barbutti, Belia, Levi and their
gang in Pisa, Italy may have been the first workers in
this field, with papers going back to the late 70s; their
latest work is on embedding logic programming into
functional programming. Drosten and Ehrich from Braunschweig,
Germany have recently given a fully rigorous translation from
algebraic specifications to logic programs. There are several
functional languages that use unification or narrowing.
Qute by Sato (of Tokyo, Japan) really is cute, and is notable
for its higher order functions. Fribourg in France has done
some really elegant work; and so has Kanamori in Japan; and
Dershowitz and Plaisted are thinking along similar lines at
Illinois; all of these have some interesting ideas about how
to make things more efficient. I also like the work of Haridi
and Tarnlund (Uppsala, Sweden), Lindstrom at Utah (in the
latest POPL), and of course the LOGLISP system of Alan Robinson
at Syracuse.
Uday Reddy was kind enough to send me copies of the unpublished
papers that he mentioned in a recent Digest. I enjoyed reading
them, especially his ideas on how to control control. Reddy's
approach views logic programs as functional programs by viewing
predicates as functions. Unfortunately, his approach is
constructor-based, so you can't give Append an associative syntax
(with which you could write things like [1,2] [3,4] [5,6] to append
three lists (using an "empty" infix syntax). Also, as Reddy notes,
his approach cannot treat all logic programs as functional programs
without somehow extending the basic framework, for example with ad
hoc mechanisms to support set-valued functions. This seems an
interesting area for further research.
Our Eqlog system (see vol.1, No.2, Logic Programming Jnl.) is
misleadingly characterized in Reddy's papers and Prolog Digest
note, and also in Lindstrom's paper and Malachi's Digest note on
Tablog. Eqlog has an equational sublanguage with logical variables,
and uses narrowing to solve equations for values of the logical
variables (this sublanguage has the syntax of OBJ2, for which see
POPL85). However, Eqlog is not purely functional, or even
"equational"; it is a logic programming language, whose logic is
first order Horn clause logic *with equality*. Since this equality
is real *semantic* equality (as opposed to Prolog's syntactic
equality), i.e., it is interpreted as *identity* in models, and the
logic of this equality is the usual equational logic; this is what
gives the semantics of the equational sublanguage. However, Eqlog
also allows real predicates; its Horn clauses can have both
predicates and equations in their heads and tails. The operational
semantics of Eqlog integrates unification with term rewriting; the
result is that Prolog-like clauses (without real equality) are
solved in the usual way with standard unification, while terms are
automatically simplified by term rewriting, and narrowing is used
to solve equations for the values of logical variables, which can
yield "partially resolved expressions". A fair-interleaving
version of the usual Prolog-like backtracking not only takes
care of predicates, but also handles conditional equations
correctly, both forsimplification and for solving; thus, a number
of computational methods appear as special cases. Also, it avoids
the infinite descents that can cause non-termination in Prolog.
This is not just universal unification. It is perhaps worth
emphasizing that these features are not just hacked together, but
are the natural outcome of taking Horn clause logic with equality
as the semantic basis: interleaved unification and rewriting then
give the right operational semantics.
Termination plus confluence of the equations viewed as rewrite
rules is a sufficient conditition for completeness of narrowing.
Since equational goals can contain logical variables, this gives
a powerful "constraint language like" facility for solving over
user defined data abstractions. Our operational semantics (fair
interleaving of unification and rewriting) seems to work reasonably
even without the termination condition; but we no longer have a
*theorem* that guarantees completeness. It would be nice to have a
formal semantics for the non-terminating case, including infinite
(lazy) data structures, but of course equality (in the theory) of
terms won't generally be decidable in such a scheme. Moreover,
some pretty hard math is needed to do it right. So it is very
comforting that we understand the case where the rewrite rules
terminate, even though it's not the end of the story. My objection
to Tablog is just that it is not complete. Without a completeness
theorem, the programmer has no idea which programs are going to
terminate and which are not. This seems like another interesting
area for further research.
By the way, it's worth mentioning that when you program
for a parallel machine, you should probably give preference
to straight term rewriting over unification and narrowing,
since no general implementation of unification can really
exploit the parallelism (by a theorem of Dwork, Kanellakis
& Mitchell, and also Yasuura).
Finally, I would like to mention that if anyone out there
is really turned on by this sort of thing [...], we
would really like to hear from you.
------------------------------
Date: Tuesday, 19 Feb 85 14:31:30 PST
From: wm@tekchips
Subject: Correction - Bertrand Constraint Language
The seminar on the Bertrand constraint language at the
Oregon Graduate Center will begin at 3:00 pm, not 3:30
as announced in the AIList digest.
Wm Leler
------------------------------
Date: Fri, 15 Feb 85 09:12:08 EST
From: coopercc@GE-CRD
Subject: Seminar - Inductive Theorem Proving in Prolog (GE)
Computer Science Seminar
General Electric R & D Center
Schenectady, N. Y.
Inductive Theorem Proving in Prolog
Prof. Jieh Hsiang
SUNY at Stoney Brook
Tuesday, February 26
1:30 PM, Building K1, Conf. Rm. 3
(Refreshments at 1:15)
ABSTRACT: Prolog is a logic programming language based
on theorem proving techniques such as unification and
resolution. It has gained considerable popularity in
recent years as an alternative approach to programming.
In this talk we introduce the use of Prolog as a deduc-
tive theorem prover for the first order inductive
theory. In addition to the backward chaining and back-
tracking facilities of Prolog, we introduce three new
mechanisms -- Skolemization by need, suspended evalua-
tion, and limited forward chaining. The features of
the method include the ability to automatically parti-
tion the domain of variables according to the manner in
which the predicate symbols are defined, and automatic
generation of lemmas (or inductive hypothesis) under
which the proposition is true. The method also does
not explicitly employ any inductive inference rule.
These new mechanisms are simple enough to be imple-
mented in Prolog without too much difficulty. The
theorem prover has been used in the verification phase
of a Prolog environment for developing data types
currently being developed at Stony Brook.
Notice to Non-GE attendees:
It is necessary that we ask you to notify Marion White
(518-385-8370 or WHITEMM@GE-CRD) at least two days in
advance of the seminar.
------------------------------
Date: Wed 20 Feb 85 00:05:00-PST
From: Gio Wiederhold <WIEDERHOLD@SU-SCORE.ARPA>
Subject: Seminar - Knowledge-Based Software Development (SU)
[Forwarded from the Stanford BBoard by Laws@SRI-AI.]
CS 300 -- Computer Science Department Colloquium -- Winter 1984-1985.
Our eigth meeting will be on Februray 26th, 4:15 in Terman Auditorium:
KNOWLEDGE BASED SOFTWARE DEVELOPMENT IN FSD
by
Dr. Robert BALZER
USC Information Sciences Institute
Our group is pursuing the goal of an automation based software development
paradigm. While this goal is still distant, we have embedded our current
perceptions and capabilities in a prototype (FSD) of such a software
development environment. Although this prototype was built primarily as a
testbed for our ideas, we decided to gain insight by using it, and have added
some administrative services to expand it from a programming system to a
computing environment currently being used by a few ISI researchers for all
their computing activities. This "AI operating System" provides specification
capabilities for Search, Coordination, Automation, Evolution, and Inter-User
Interaction.
Particularly important is evolution, as we recognize that useful systems can
only arise, and remain viable, through continued evolution. Much of our
research is focused on this issue and several examples will be used to
characterize where we are today and where we are headed. Naturally, we have
started to use these facilities to evolve our system itself.
( After the presentation Bob will show a Video tape in )
( the Auditorium to show all that, and how it works. )
------------------------------
Date: Wed 20 Feb 85 11:19:46-PST
From: Carol Wright <WRIGHT@SUMEX-AIM.ARPA>
Subject: Seminar - Cooperation Among Intelligent Agents (SU)
[Forwarded from the Stanford SIGLUNCH distribution by Laws@SRI-AI.]
DATE: Friday, February 22, 1985
LOCATION: Chemistry Gazebo, between Physical & Organic Chemistry
TIME: 12:05
SPEAKER: Jeffrey S. Rosenschein
Stanford University
TITLE: Rational Interaction: Cooperation among Intelligent
Agents
The development of intelligent agents presents opportunities to
exploit intelligent cooperation. Before this can occur, however, a
framework must be built for reasoning about interactions. This work
describes such a framework, and explores strategies of interaction
among intelligent agents.
The formalism that has been developed removes some serious
restrictions that underlie previous research in distributed artificial
intelligence, particularly the assumption that the interacting agents
have identical or non-conflicting goals. The formalism allows each
agent to make various assumptions about both the goals and the
rationality of other agents. In addition, it allows the modeling of
restrictions on communication and the modeling of binding promises
among agents.
This talk describes work done in conjunction with Matthew L. Ginsberg
and Michael R. Genesereth.
------------------------------
Date: 19 February 1985 1134-EST
From: Staci Quackenbush@CMU-CS-A
Subject: Seminar - Programming in Concurrent Prolog (CMU)
[Forwarded from the CMU bboard by Laws@SRI-AI.]
Name: Vijay Saraswat
Date: Friday, February 22
Time: 3:30 - 4:30
Place: WeH 4605
Title: "Programming in Concurrent Prolog"
The talk will briefly introduce Horn logic programming and will then
examine Concurrent Prolog as a concurrent and as a logic programming language.
I will compare CP to CSP and highlight various semantic and operational
difficulties with CP-like `concurrent' languages based on Horn logic. My
thesis is that CP is best thought of as a set of control features designed to
select a very few of the many possible execution paths for programs in a
non-deterministic language. It is perhaps not a coherent set of control and
data-structures for the ideal concurrent programming language. It is certainly
even less a logic programing language than Prolog.
Some of these languages have been proposed as systems programming languages. In
the second half of the talk, I will focus on the difficulty in efficiently
programming such data-structures as arrays, dequeues, heaps etc and propose
the use of associative, commutative and idempotent logic functions (data
structures) as a partial remedy. This also naturally leads to (a slightly
generalised form of) a synchronous WRAM model of computation.
------------------------------
Date: Wed, 20 Feb 85 09:41:20 cst
From: briggs@ut-sally.ARPA (Ted Briggs)
Subject: Seminar - Self-Organizing Retrieval for Graphs (UT)
[Forwarded from the UTexas-20 bboard by Laws@SRI-AI.]
Graduate Brown Bag Seminar
A Self-Organizing Retrieval System for Graphs
by
Bob Levinson
noon Friday Feb. 22
PAI 5.60
We present the theory, design, and application of a self-organizing
intelligent knowledge base in which all concepts are
represented as graphs. The system is designed to support the
expert problem solving tasks of recall, design, and discovery. It
is being applied successfully in organic chemistry to store and
retrieve molecular structures and to reason with organic
reactions. We believe that the system will also be useful in oth-
er domains.
At the basis of the system's design is the production and mainte-
nance of a partial ordering of graphs by the relation
"subgraph-of". We will discuss how this relation can be
considered to be equivalent to "more-general-than", and we
will present a simple, yet powerful retrieval algorithm for
data ordered in this way.
The system exploits a set of concepts that are common sub-
graphs of previously stored concepts (graphs). We will show how
these concepts serve multiple purposes that improve the effi-
ciency and flexibility of the system. Since these concepts can
be "discovered" by the system itself, we say that it is
"self-organizing".
------------------------------
End of AIList Digest
********************