Gabriel%ANL-MCS@sri-unix.UUCP (11/07/83)
From: Gabriel@ANL-MCS (John Gabriel)
A very brief comment on the remark in Digest #48 that not only must
useful programs do I/O, but also many useful programs are more than
simply functions. First of all "Hear Hear" from my English heritage,
or "Right On" from my American experience.
The distinction being made is the distinction between a function,
simply mapping points from one space to another, and a functional
(see for example T. Levi Civita, The Absolute Differential Calculus,
Blackie and Son, London & Glasgow 1926,1929,1946,1947,1950) which
is an object computed by passage along a path between two points
in a space. A functional differs from a function because its value
depends not only on the end points of the path, but on the path,
I.e. the history.
Many of the interesting objects of physics (I.e. the real
world) are functionals, not functions, simply because they depend
on the paths I.e. the histories. Here is an example:- Suppose we
are dealing with a collection of NAND logic gates wired together
without feedback paths I.e. the graph of information flow is
Directed and Acyclic. This system may be modelled in Prolog by
a single generic definition of a NAND gate, predicates defining
the Dataflow graph, and a little recursion.
But the moment several J-K flip-flops are placed in the
circuit, a generic definition of J-K flip flop is not sufficient,
information must be carried about the state of each instance of
J-K flip flop, a clock added to the system, and the computation
of the state at time T done from the state at time T-1.
Now, I think this can be done in "pure" Prolog without
assert and retract, by recursion on T, but even relatively small
T values such as T=100 seem likely to lead to stack overflows
and other such embarrassments, simply because the recursion
keeps ALL the history, not just the immediately previous state.
So for my purposes, assert and retract are important
capabilities, not because they cannot be replaced by recursion,
but because the recursive replacement is harder to think about,
gives me less flexibility, and exposes me to shortages of
computing resources in doing practical problems of interest.
I take some risks in deleting old unit clauses for T
values believed to be no longer of interest, because if I make
a mistake and delete something too early, I will reach incorrect
conclusions.
Perhaps I gain relative to recursion even if I keep all
state history as unit clauses, because I get to pop all stacks
fairly often, and so the problems of the global stack filling up
with "holes" go away. That's a question about implementation.
Other comments seem close to my concerns. I would like
to partition the clause space somehow, to give my knowledge base
perspective (W.A. Woods IEEE Computer Society Oct or Nov 1983 -
the issue about Knowledge Bases), so that the things of immediate
interest are close to the program's attention span, and all else
is temporarily forgotten. Something like Bill Woods' comments
elsewhere about being able to push the current environment onto
a stack, delve deeper into a specialised knowledge base, develop
a unit clause from that detail, pop the stacked environment and
add to it the new unit clause.
All of the questions about distributed databases arise
in this context - consistency, synchronisation, etc. etc. But
on the other hand a solution to some of the problems of dataflow
in Prolog by a "perspective" mechanism might generate programming
styles having extensive high level parallelism and suitable for
use on wide parallel architectures. Incidentally even this insight
is not really my own, there is a BBN internal report by Bill
Woods some five years old exploring these issues.