RESTIVO@SU-SCORE.ARPA (06/25/85)
From: Chuck Restivo (The Moderator) <PROLOG-REQUEST@SU-SCORE.ARPA>
PROLOG Digest Tuesday, 25 Jun 1985 Volume 3 : Issue 28
Today's Topics:
Announcement - 1985 Symposium on LP & Call for Papers,
LP Library - Book Review
----------------------------------------------------------------------
Date: Thu, 13 Jun 85 14:59:02 EDT
From: Doug DeGroot <Degroot.yktvmv%ibm-sj@csnet-relay>
Subject: 1985 Symposium on Logic Programming
It has been brought to our attention that we failed to mention
in the SLP 85 registration forms appearing in a previous Digest
issue that registrants should note on their registration forms
which tutorials, if any, they plan on attending. If you have
already mailed in your registration form, please mail a notice
to the IEEE Computer Society in care of Mrs. Gerry Katz indicating
to her your choice of tutorials. If you have not yet registered
but intend to do so, please indicate on your registration form
your choice of tutorials.
Thank you, and our apologies for the inconvenience.
-- Doug DeGroot
------------------------------
Date: Tue, 11 Jun 85 10:04:20 edt
From: (Larry Kerschberg) allegra!usceast!kersch@Berkeley
Subject: Call for Papers
Call for Papers and Participation
FIRST INTERNATIONAL CONFERENCE ON EXPERT DATABASE SYSTEMS
April 1-4, 1986, Charleston, South Carolina
Sponsored by:
--------- --
The Institute of Information Management, Technology and
Policy College of Business Administration,
University of South Carolina
In Cooperation With:
-- ----------- ----
American Association for Artificial Intelligence
Association for Computing Machinery -- SIGMOD,
SIGART and SIGPLAN IEEE Technical Committee on
Data Base Engineering Agence de l'Informatique,
France
Conference Objectives
---------- ----------
The goal of this conference is to explore both the
theoretical and practical issues of Expert Database
Systems. These systems represent the confluence of
R&D activities in Artificial Intelligence, Logic,
and Database Management.
Expert Database Systems will play an ever-increasing
role in scientific, governmental and business
applications by:
o providing intelligent, knowledge-based access to
large shared databases through novel
user-interfaces and natural-language question-answering
facilities,
o endowing database systems with reasoning, planning, and
justification capabilities,
o creating knowledge base management tools and techniques
to support the creation, manipulation, indexing, and
evolution of large knowledge bases, and
o integrating AI & DB functional requirements into new
hardware and software environments for the specification,
prototyping, testing and debugging of knowledge-based
applications.
In order to foster the cross-fertilization of ideas from
AI, Logic, and Databases the Conference will be
composed of tutorial sessions, paper sessions, and panel
discussions.
Topics of Interest
------ -- --------
The Program Committee invites original papers (of
approximately 5000 words) addressing (but not limited to)
the following areas:
Theory of Knowledge Bases (including knowledge
representation, knowledge models, recursive data models,
object-oriented models, knowledge indexing and
transformation),
Knowledge Engineering (including acquisition, maintenance,
learning, knowledge-directed database specification and
design methodologies, and case studies),
Knowledge Base Management (including architectures and
languages, constraint and rule management, metadata
management, and extensible data dictionaries),
Reasoning on Large Data/Knowledge Bases (including inexact
and fuzzy reasoning, non-monotonic reasoning, deductive
databases, logic based query languages, semantic
query optimization, and constraint-directed reasoning),
Natural Language Interaction (including question-answering,
extended responses, cooperative behavior, explanation and
justification),
Intelligent Database Interfaces (including expert system
-- database communication, knowledge gateways,
knowledgeable user agents, browsers, and videotex),
Knowledge-Based Environments (including Decision Support
Systems, CAD/CAM, and VLSI Design),
Organizational Issues (including technology transfer,
procurement of expert database systems, and knowledge
certification).
Please send five (5) copies of papers by September 12,
1985 to:
Larry Kerschberg, Program Chairman
College of Business Administration
University of South Carolina
Columbia, SC, 29208
Program Committee
------- ---------
Hideo Aiso Sham Navathe
Keio University University of Florida
---- ---------- ---------- -- -------
Antonio Albano Erich Neuhold
University of Pisa Technical University of Vienna
---------- -- ---- --------- ---------- -- ------
Robert Balzer S. Ohsuga
USC/Information Sciences Institute University of Tokyo
--- ----------- -------- --------- ---------- -- -----
James Bezdek D. Stott Parker, Jr.
University of South Carolina UCLA and Silogic
---------- -- ----- -------- ---- --- -------
Ronald J. Brachman Alain Pirotte
Schlumberger Palo Alto Research Philips Research Lab, Brussels
------------ ---- ---- -------- ------- -------- --- --------
Michael Brodie Harry Pople
Computer Corporation of America University of Pittsburgh
-------- ----------- -- ------- ---------- -- ----------
Peter Buneman Erik Sandewall
University of Pennsylvania Linkoping University
---------- -- ------------ --------- ----------
Mark Fox Edgar H. Sibley
Robotics Institute, Carnegie-Mellon George Mason University
-------- --------- -------- ------ ------ ----- ----------
Antonio L. Furtado John Miles Smith
PUC -- Rio de Janeiro Computer Corp. of America
--- --- -- ------- -------- ----- -- -------
Herve Gallaire Reid Smith
ECRC, Munich Schlumberger-Doll Research
---- ------ ------------ ---- --------
Georges Gardarin Michael Stonebraker
Univ. of Paris 6 and INRIA UC -- Berkeley
---- -- ----- - --- ----- -- --------
Matthias Jarke Jeffrey Ullman
New York University Stanford University
--- ---- ---------- -------- ----------
Jonathan King Bonnie L. Webber
Teknowledge University of Pennsylvania
----------- ---------- -- ------------
Robert Kowalski Andrew B. Whinston
Imperial College Purdue University
-------- ------- ------ ----------
Jack Minker Gio Wiederhold
University of Maryland Stanford University
---------- -- -------- -------- ----------
Michele Missikoff Carlo Zaniolo
IASI-CNR, Rome MCC Corporation
---- --- ---- --- -----------
John Mylopoulos
University of Toronto
---------- -- -------
Important Dates
-----------------------------------------------
| Submission Deadline: September 12, 1985|
| Acceptance Notification: November 25, 1985 |
| Final Version Due: January 10, 1986 |
| Conference: April 1-4, 1986 |
-----------------------------------------------
Conference proceedings will be available at the conference,
and subsequently will appear in book form.
Conference General Chairman Conference Coordinator
---------- ------- -------- ---------- -----------
Donald A. Marchand Cathie L. Hughes
Institute of Information Management, Technology and Policy
Panel Coordinator Conference Treasurer
----- ----------- ---------- ---------
Arun Sen Libby Shropshier
Dept. of Management Science Institute of Information
College of Business Administration Technology and Policy
Univ. of South Carolina Univ. of South Carolina
Columbia, SC 29208 Columbia, SC 29208
Publicity Chairman Tutorial Chairman
--------- -------- -------- --------
John Weitzel Jonathan King
Dept. of Management Science Teknowledge, Inc.
College of Business Administration 525 University Avenue
Univ. of South Carolina Palo Alto, CA 94301
Columbia, SC 29208
International Representatives
Latin America Europe Far East
----- ------- ------ --- ----
Claudio M.O. Moura Jean-Claude Rault Masahiro Nakazawa
Independent Consultant Agence de l'InformatiqueNihon Digital Equip.
Rua R. Eduardo Guinle 60 Tour Fiat-Cedex 16 Sunlight Bldg.
Botafogo Paris-La Defense 5-29-1, Toyotamakita,
22.260 Rio de Janeiro, RJParis Nerima-ku Tokyo, 176
Brazil France Japan
--------------------------------------------------------------------
Response Card (To be on our mailing list, please detach, fill out,
and mail to address below)
Name Telephone
------------------------------------------- --------
Organization
-----------------------------------------------------
Address
----------------------------------------------------------
City, State,
ZIP, and Country
--------------------------------------------------
Please check all that apply:
I intend to submit a paper.
-----
Subject of paper
----------------------------------------------
---------------------------------------------------------------
I intend to attend the Conference.
-----
I would be interested in tutorial(s) on.
-----
Artificial Intelligence.
-----
Expert Systems.
-----
Database Management.
-----
Logic and Databases.
-----
Not sure I can participate, but please keep me informed.
-----
Cathie Hughes
EDS Conference Coordinator
Institute of Information Management
Technology and Policy
College of Business Administration
University of South Carolina
Columbia, SC 29208
------------------------------
Date: 22 Jun 85 1842 PDT
From: Yoni Malachi <YM@SU-AI.ARPA>
LOGIC PROGRAMMING: RELATIONS, FUNCTIONS, AND EQUATIONS
Doug DeGroot
Gary Lindstrom
Editors
Prentice-Hall, Inc.
Publication date: Summer 1985
June 14, 1985
1. Concept
This book addresses the topical and rapidly developing
areas of logic, functional, and equational programming, with
special emphasis on their relationships and prospects for
fruitful amalgamation. A distinguished set of researchers
have contributed fourteen articles addressing this field
from a wide variety of perspectives. The book will be
approximately 500 pages, published in hard cover form, with
foreword by the editors and combined index.
2. Table of Contents
2.1. Setting the Stage
- Uday Reddy: On the Relationship between Logic and
Functional Languages (34 pp.).
An essential distinction between logic and functional
languages is drawn based on input-output directionality.
Functional languages are directional in that programs
written in them make an explicit commitment about which
quantities are inputs and which are outputs. Logic
programs to do not make such a commitment. However, the
non-directionality makes the operational behavior of
logic programs hard to understand and poses problems in
developing parallel implementations of logic languages.
We present here a notation for introducing
directionality information in logic programs and show
that directional logic programs are equivalent to
first-order functional programs. Finally, we discuss
how the syntax and semantics of functional languages can
be extended to capture the additional expressive power
of logic languages.
- J. Darlington, A.J. Field, and H. Pull: The Unification
of Functional and Logic Languages (34 pp.).
Certain aspects of logic programs give them greater
expressive power than functional programs. In
particular, the presence of logical variables enable
relations to be used in arbitrary modes and allow
components of data structure templates to be bound by
unification. However, functional programs can also be
more expressive than logic programs because of their
cleaner syntax, which is devoid of output variables, and
because of their higher-order capabilities. The run
time behaviour of functional programs is much simpler to
control than that of logic programs, particularly in a
parallel context. Techniques, such as graph reduction
and data flow, have been evolved for the parallel
evaluation of functional languages taking advantage of
their simplicity of execution and it would be
advantageous if these techniques could also be used to
support languages with the extra expressive capability
of logic. This paper discusses the differences between
the two styles and proposes an extended functional
language (HOPE with unification) which provides all the
expressive power of logic programs whilst retaining most
of the underlying functional simplicity. This is
achieved by the introduction of absolute set abstraction
which allows logical variables to be introduced within
set expressions on the right hand sides of
function-defining equations.
We proposes a technique for compiling certain types
of functions defined implicitly within set expressions
into explicit functions. This effectively involves
synthesising function inverses using the processes of
symbolic unification and program transformation. When
this can be achieved, logical variables can be
eliminated altogether and replaced by function
composition.
2.2. Unification and Functional Programming
- Harvey Abramson: A Prological Definition of HASL, a
Purely Functional Language with Unification Based
Conditional Binding Expressions (57 pp.).
We present a definition in Prolog of a new purely
functional (applicative) language HASL (HArvey's Static
Language). HASL is a descendant of Turner's SASL, but,
among other features, introduces a one-way unification
based conditional binding expression, one-way in the
sense that of the two expressions being unified, only
one may contain variables. This one-way unification
based conditional binding construct is used to structure
the design of the compilation of HASL clausal
definitions to combinators which may then be reduced.
The specification of HASL and its reduction machine is
entirely in Prolog, thus providing an executable
specification - implementation - of the language. Since
HASL programs may be considered a syntactic sugaring of
combinator code, we adapt techniques derived from
compiling practice to specify the language and its
reduction machine. The definition is divided into four
parts. The first part defines the lexical structure of
the language by means of a simple Definite Clause
Grammar which relates character strings to "token"
strings. The second part defines the syntactic
structure of the language by means of a more complex
Definite Clause Grammar and relates token strings to a
parse tree. The third part is semantic in nature and
translates the parse tree definitions and expressions to
a variable-free string of combinators and global names.
The fourth part of the definition consists of a set of
Prolog predicates which specify how strings of
combinators and global names are reduced to "values",
i.e. integers, truth values, characters, lists,
functions, fail, and has an operational flavour: one can
think of this fourth part as the definition of a normal
order reduction machine.
- M. Sato and T. Sakurai: QUTE: a Functional Language
Based on Unification (24 pp.).
A new programming language called Qute is introduced.
Qute is a functional programming language which permits
parallel evaluation. While most functional programming
languages use pattern matching as basic variable-value
binding mechanism, Qute uses unification as its binding
mechanism. Since unification is bidirectional, as
opposed to pattern match which is unidirectional, Qute
becomes a more powerful functional programming language
than most of existing functional languages. This
approach enables the natural unification of logic
programming language and functional programming
language. In Qute it is possible to write a program
which is very much like one written in conventional
logic programming language, say, Prolog. At the same
time, it is possible to write a Qute program which looks
like an ML (which is a functional language) program. A
Qute program can be evaluated in parallel
(and-parallelism) and the same result is obtained
irrespective of the particular order of evaluation.
This is guaranteed by the Church-Rosser property enjoyed
by the evaluation algorithm. A completely formal
semantics of Qute is given in this paper.
- P.A. Subrahmanyam and J.-H. You: FUNLOG: a
Computational Model Integrating Logic Programming and
Functional Programming (42 pp.).
Funlog involves a computational model which integrate
functional programming and logic programming. This
model is described, along with evaluation strategies to
support the execution of programs based upon it. A lazy
mechanism, pattern-driven reduction, is developed for
the underlying functional model and cleanly and
naturally achieves reduction by need. The notion of
semantic unification is discussed. Semantic unification
serves as a basis for achieving the desired integration
of functions and logic, and can be used to replace the
conventional unification procedure in logic programming
systems. The resulting model supports computations with
infinite data structures while avoiding the introduction
of complicated control issues at the user level. In
addition, it provides the programmer the flexibility of
choosing between a backtracking free computation
framework and a conventional logic computation
framework, i.e., a nondeterministic one involving
backtracking. The use of this facility is illustrated
via examples. The model can be extended to include the
notion of equality when complete E-unification
algorithms are used.
2.3. Symmetric Combinations
- R. Barbuti, M. Bellia, G. Levi, and M. Martelli:
LEAF: a Language which Integrates Logic, Equations and
Functions (33 pp.).
The paper describes a language which integrates a
declarative language, consisting of Horn clauses and
equational theories with constructors, and a first order
functional language. Both language components will
eventually be directly supported by a hardware machine.
The declarative component permits the definition of both
relations and functions, possibly dealing with infinite
data structures. A formal semantics, coping with the
novel language features, is given in the standard style
(operational, model-theoretic and fixpoint). The
functional (procedural) component is essentially the
functional (deterministic) sublanguage of the
declarative one. It has a lazy evaluation based
parallel interpreter and allows efficient programming of
system software, tools and algorithms. The technique
for integrating these two language components is based
on using the procedural component as the metalanguage of
the declarative component, thus allowing procedural
programs to act on meta-objects such as declarative
theories and (possibly infinite) sets of solutions of
declarative programs. Examples are given of tools for
the declarative component and of integrated
procedural-declarative applications.
- Shimon Cohen: The APPLOG Language (38 pp.).
The virtues of PROLOG and LISP are discussed, and the
conclusion is reached that a mixture of these two
languages is desirable. Toward that end, APPLOG, a
combination of LISP and PROLOG, is described. APPLOG is
embedded within the PROLOG language with the facilities
of PROLOG made available through a simple goal function.
APPLOG is an applicative language, i.e. one whose
primary composition method is the application of
functions to arguments. Variables in APPLOG are
compatible with PROLOG variables, and serve as means for
data transfer between APPLOG and PROLOG. APPLOG
supports lambda and nlambda function definitions and
one-to-one, one-to-many and mixed binding mechanisms, in
the manner of INTERLISP. The main advantage of APPLOG
is the simple integration of LISP and PROLOG into one
powerful language which incorporates, in our judgment,
the best features of both languages. In particular,
APPLOG has the following advantages over traditional
LISP languages: (i) pattern directed invocation; (ii)
call by reference; (iii) an interface to PROLOG as a
database query language; (iv) functions as operators
(infix, prefix and postfix); (v) backtracking, and (vi)
generators. APPLOG includes aggregates and grouping
constructs, and has been extended to a simple relational
database query language similar to Query-By-Example. An
appendix includes a listing of the principal functions
of the APPLOG interpreter.
2.4. Programming with Equality
- Wm. Kornfeld: Equality for Prolog (15 pp.).
An extension of the language Prolog, called
"Prolog-with- Equality", is presented which allows the
inclusion of assertions about equality. When an attempt
is made to unify two terms that do not unify
syntactically, an equality theorem may be used to prove
the two terms equal. If it is possible to prove that
the two terms are equal, the unification succeeds with
the variable bindings introduced by the equality proof.
It is shown that this mechanism significantly improves
the power of Prolog. Sophisticated data abstraction
with the advantages of object-oriented programming
becomes available. Techniques for passing partially
instantiated data are described that extend the
"multi-use" capabilities of the language, improve the
efficiency of some programs, and allow the
implementation of arithmetic relations that are both
general and efficient. The modification to standard
Prolog are simple and straightforward and in addition
the computational overhead for the extra linguistic
power is believed to not be significant. Equality
theorems will probably play an important role in future
logic programming systems.
- Joseph Goguen and Jose Meseguer: EQLOG: Equality,
Types, and Generic Modules for Logic Programming (69 pp).
This paper presents Eqlog, a logic programming
language that unifies (predicate-based) Horn clause
relational programming with (equality-based) functional
programming. The unification seems quite natural, since
it is based on the smallest logic having both Horn
clauses and equality, namely Horn clause logic with
equality. Rather than force functions to be viewed as
predicates, or predicates to be viewed as functions,
Eqlog allows using both functions and predicates as
convenient. Furthermore, Eqlog computes differently
with functions than with predicates: functions are
computed by term rewriting, while queries to predicates
are computed in the usual Prolog-like fashion with
unification and backtracking (but with unification
modulo equations, implemented by narrowing in general,
and by more efficient methods for built-in types). In
fact, narrowing does much more than this, since it
allows solving for the values of logical variables that
occur in equations. This gives Eqlog very powerful
capabilities as a "constraint language", using narrowing
and Prolog-style backtracking to solve constraints over
user-defined abstract data types, and using efficient
built-in algorithms for solving constraints over
built-in types (such as numbers). With the usual
Church-Rosser assumptions, Eqlog's operational semantics
is logically complete. In effect, this paper shows how
to expand the paradigm of logic programming with a
number of features that are prominent in current
programming methodology, without any sacrifice of
logical rigor. Beyond simple functional programming,
Eqlog also provides strong typing, user definable
abstract data types, and generic (i.e., "parameterized")
modules, using methods developed for the specification
language Clear. A very useful refinement is "subsorts,"
which provide polymorphic operators and an inheritance
relation on types of data. We show that our logic
admits "initial models" having properties that
generalize those of minimal Herbrand models for ordinary
Horn clause logic. All of these features are given a
rigorous semantics in terms of the underlying logic, and
illustrated with a number of examples, including the
well-known Missionaries and Cannibals problem and some
natural language processing problems.
- Y. Malachi, Z. Manna and R. Waldinger: TABLOG: a New
Approach to Logic Programming (30 pp.).
TABLOG is a logic programming language based on
first-order predicate logic with equality that combines
relational and functional programming. In addition to
featuring both the advantages of functional notation and
the power of unification as a binding mechanism, TABLOG
also supports a more general subset of standard
first-order logic than do PROLOG and most other logic
programming languages.
The Manna-Waldinger deductive tableau proof system is
employed as an interpreter for TABLOG in the same way
that PROLOG uses an SLD resolution proof system.
Unification is used by TABLOG to match a call with a
line in the program and to bind arguments. The basic
rules of deduction used for computing are nonclausal
resolution and an equality rule that can be viewed as a
generalization of narrowing and paramodulation.
In this article we describe the basic features of
TABLOG and its (implemented) sequential interpreter and
we discuss some of its properties. We give examples of
programs for which TABLOG is better than a functional
language like LISP and others for which it is better
than a relational language like PROLOG.
2.5. Augmented Unification
- Robert G. Bandes (deceased): Constraining-Unification
and the Programming Language Unicorn (14 pp.).
Up to this point, direct implementations of axiomatic
or equational specifications have been limited because
the implementation mechanisms are incapable of capturing
the full semantics of the specifications. The
programming language Unicorn was designed and
implemented with the intention of exploring the full
potential of programming with equations. Unicorn
introduces a new language mechanism, called
constraining-unification. When coupled with semantic
unification, constraining-unification closely models the
semantics of equational specifications thereby allowing
for the implementation of a wider class of
specifications. Unlike the language mechanisms of
rewrite-rule and logic programming,
constraining-unification is free of order dependencies.
The same results are produced regardless of the order in
which the axioms are stated. The use of viewpoints
contributes to the flexibility of the Unicorn language.
Preconditions for partial operations can be specified
without added machinery.
- Ken Kahn: Uniform -- A Language Based upon Unification
which Unfies (much of) Lisp, Prolog, and Act 1 (28 pp.).
Uniform is an AI programming language based upon
augmented unification. It is an attempt to combine, in
a simple coherent framework, the most important features
of Lisp, actor languages such as Act 1 and SmallTalk,
and logic programming languages such as Prolog. Among
the unusual abilities of the language is its ability to
use the same program as a function, an inverse function,
a predicate, a pattern, or a generator. All of these
uses can be performed upon concrete, symbolic, and
partially instantiated data. Uniform features automatic
inheritance from multiple super classes, facilities for
the manipulation of programs, and a unification-oriented
database.
2.6. Semantic Foundations
- Joxan Jaffar, Jean-Louis Lassez and Michael J. Maher:
A Logic Programming Language Scheme (27 pp.).
Numerous extended versions of PROLOG are now
emerging. In order to provide greater versatility and
expressive power, some versions allow functional
programming features; others allow infinite data
structres. However, there is concern that such
languages may have little connection left with logic.
In some instances, various logic frameworks have been
proposed to solve this problem. Nevertheless, the
crucial point has not been addressed: the preservation
of the unique semantic properties of logic programs.
The significance of our effort here is twofold: (1)
There is a natural logic programming language scheme
wherein these properties hold. (2) Formal foundations
for extended versions of traditional PROLOG can be
obtained as instances of this scheme. They
automatically enjoy its properties.
- Gert Smolka: Fresh: A Higher-Order Language with
Unification and Multiple Results (56 pp.).
This paper presents Fresh, a language that integrates
logic programming features into higher-order functional
programming. The language incorporates unification,
multiple results and a collection construct. Many
examples illustrate that these extensions of functional
programming are useful. We define an operational
semantics along the lines of Plotkin's structural
approach. The semantics is of intrinsic interest since
it covers backtracking and the collection construct. To
illustrate the conceptual similarities and differences
between logic and functional programming, we begin with
a purely functional core language and add first
unification and then backtracking. With each addition
we discuss the enhanced eloquence of the language and
the concomitant modifications to the semantics.
------------------------------
End of PROLOG Digest
********************