PROLOG-REQUEST@SCORE.STANFORD.EDU (Chuck Restivo, The Moderator) (01/17/87)
PROLOG Digest Monday, 19 Jan 1987 Volume 5 : Issue 3
Today's Topics:
Programming - Bug Stories,
Announcement - Math Logic Seminar & Thesis Defense
----------------------------------------------------------------------
Date: Mon, 12 Jan 87 10:53 EST
From: Stephen G. Rowley <SGR@STONY-BROOK.SCRC.Symbolics.COM>
Subject: Collecting favorite bug stories
Once, as a consultant, I was developing a demonstration of expert
system programming techniques for a client. The program was the usual
monkey-and-bananas example of planning systems. Since I had visions
of adding more animals to that world, such as carnivores, I made both
the monkey and the bananas edible. The monkey's reasoning went like
this:
[1] I'm hungry.
[2] I have to write a plan that ends up in my becoming non-hungry.
[3] In order to become non-hungry, I have to eat something.
[4] What's edible? The monkey is, and the bananas are.
[5] In order to eat one of those foods, I have to first get co-located with it.
[6] Which food is easier to get co-located with? I (the monkey) am at the same
place as the monkey, so that makes step [5] trivial, and hence I will
prefer to eat the monkey instead of the bananas.
The monkey then disappeared in a shocking act of auto-cannibalism.
I've remembered the bug for several years because it's a wonderful
illustration of what makes some AI systems hard to write, namely, that
humans know too much. There's always a crucial fact you take for
granted and forget to tell your system. It later crops up like this,
usually at the most embarassing moment possible. (For example, you're
demonstrating a blocks-world planner to your boss, and he mis-clicks
the mouse and tells it to put a block on top of itself. Your system
doesn't know that's unreasonable, and goes quietly crazy. That
happened to me, too.)
The solution, of course, is to insert a constraint that forbids any
plans involving entities that eat themselves. You can have a lot of
fun explaining to people how you "discovered" the necessity of that
rule.
Here's an example, in apocryphal Prolog (i.e., I wrote it in some
other language):
is_heuristic_plan_for(Plan, Initial_situation, ~hungry(Initial_situation)) :-
good_to_eat(Food),
different_objects(Food, monkey), %% this clause added to prevent
auto-cannibalism
at(Food, Place, Initial_situation),
is_plan_for(At_Plan, Initial_situation, at(monkey, Place, At_plan)),
Plan = [handle Food eat [handle Food take At_plan]].
------------------------------
Date: Fri, 16 Jan 87 20:28 EST
From: Tim Finin <Tim@cis.upenn.edu>
Subject: Mid-Atlantic Math Logic Seminar
MID-ATLANTIC MATHEMATICAL LOGIC SEMINAR
PHILADELPHIA, FEBRUARY 21-22, 1987
This meeting will be held at the University of Pennsylvania, Alumni Room,
Towne Building. Please use ground level entrance on the west side just off
Smith Walk,between 33rd and 34th Streets, south of Walnut Street.
SATURDAY, FEBRUARY 21
12 noon Coffee and snacks
1:00 - 2:00 Dana S. Scott, Carnegie-Mellon University
HOW DESIRABLE IS THE REALIZABILITY UNIVERSE?
2:10 - 3:10 Albert R. Meyer, Massachusetts Institute of Technology
FIXED POINT AND LOOPING COMBINATORS IN POLYMORPHIC LAMBDA
CALCULUS
3:40 - 4:40 Peter J. Freyd, University of Pennsylvania
CATEGORIES AND POLYMORPHIC LAMBDA CALCULUS
4:50 - 5:50 John C. Mitchell, A.T.&T. Bell Laboratories
KRIPKE STRUCTURES AND TYPED LAMBDA CALCULUS
SUNDAY, FEBRUARY 22
8:30 Coffee and doughnuts
9:00 - 10:00 Speaker T.B.A., Cornell University
RECURSIVE TYPES IN THE NUPRL PROOF DEVELOPMENT SYSTEM
10:10 - 11:10 Garrel Pottinger, Odyssey Research Associates, Inc.
STRONG NORMALIZATION FOR TERMS OF THE COQUAND-HUET THEORY
OF CONSTRUCTIONS
11:25 - 12:25 Gaisi Takeuti, University of Illinois at Urbana-Champaign
BOUNDED ARITHMETIC AND A WEAK CONSISTENCY
12:35 - 1:35 Scott Weinstein, University of Pennsylvania
SOME RECENT RESULTS IN THE THEORY OF MACHINE INDUCTIVE
INFERENCE
ACCOMMODATIONS
A block of 10 rooms has been set aside at the Sheraton Inn University City,
Chestnut and 36th Streets (215/387-8000) for the participants of the "Logic
Meeting", Saturday night, February 21. The price per room is $64 if you make
your reservation by February 7. Private accommodations will be available for
up to 10 people with sleeping bags. Please call at least 3 days in advance
215/898-8475 or 215/545-5443.
-- Andre Scedrov
------------------------------
Date: Thu, 15 Jan 87 12:09:15 PST
From: Evan Tick <evan@umunhum.stanford.edu>
Subject: thesis defense
STUDIES IN PROLOG ARCHITECTURES
Evan Tick, Ph.D.
Stanford University, 1987
Tuesday, January 20 1987
12:15 PM, AEL 109
This dissertation addresses the problem of how logic programs can be made to
execute at high speeds. Prolog, chosen as a representative logic
programming language, differs from procedural languages in that it is
applicative, nondeterminate and uses pattern matching as its primary
operation. Program performance is directly related to memory performance
because high speed processors are ultimately limited by memory bandwidth and
architectures that require less bandwidth have greater potential for high
performance.
A derivation of a family of canonical Prolog architectures is given
from the first principles of ideal machine architectures. The Warren
Abstract Machine (WAM) architecture is shown to be a member of this
family. Measurements of the Prolog Canonical Interpretive Form
indicate upper memory-performance bounds afforded by ideal attributes.
Analysis of high-level architecture statistics indicate the cost of
attributes such as nondeterminacy and point to efficient memory
designs.
High speed uniprocessor performance is necessary, even within a
multiprocessor, because not all types of parallelism exist or can be
exploited in all applications. Within a shared memory multiprocessor,
local processor memories are necessary to reduce bandwidth and allow
undegraded execution of sequential code. Two-level hierarchies for
both sequential and parallel Prolog architectures are modeled. Local
memories are measured with trace driven simulations. Main memories
are measured with queueing models. For sequential Prolog, various
hierarchies are analyzed with the WAM architecture. For parallel
Prolog, various shared memory multiprocessors are analyzed with the
Restricted AND-Parallelism (RAP) architecture of Hermenegildo. Local
memory consistency protocols for RAP are designed and measured.
------------------------------
End of PROLOG Digest
********************