Re: DAML-S formal semantics

   [Massimo Paolucci & the other CMU people]

   As a general comment we wonder about the value of a denotational
   semantics as opposed to an operational semantics as it is used to
   describe the semantics of distributed programming languages, which faces
   the same types of problems that we have.  This has been the guiding
   principle of the semantics for DAML-S that we proposed in [1].  

For some reason when I think "semantics" I think "denotational
semantics."  It's more of a habit than anything else.  I believe I
read Ankolekar et al. before, but I'll take a look.  (I had forgotten
that they propose a surface syntax for DAML-S; I think choosing the
syntax is probably more urgent right now than getting the semantics
right). 

   The semantics of concurrent executions (both of different
   agents/web services and processes within the same process model) is
   difficult to represent in a denotational semantics because the
   domain can be modified in unpredictable ways.  Indeed, your
   semantics is based on atree like representation that forces you to
   represent every case, which becomes virtually impossible when we
   need to represent the inherent non-determinism of concurrently
   running processes.  For example, you are forced to make the
   assumption that parallel processes are "comparable and inertial.'
   This assumption holds for channels because only one process can
   write in them, but it does not hold for the complete situation
   which is part of the VS (valuated situation) since multiple
   processes may change the domain and there is no restriction on who
   can do what.  The other problem is the representation of loops
   where you are presumably forced to represent every single loop as a
   different banch of the tree.

It seems to me that these problems are intrinsic to the problem area,
and not a particular problem with denotational semantics.  I proposed
a semantics for autonomous processes in [1], and I sure hope it can be
made compatible with my DAML-S proposal.

What's the problem with a "tree-like representation"?  Well, there's a
problem with the word "representation."  I'd rather say "tree-like
denotation."  And it doesn't have to literally be tree-like; I'd
actually rather have separate timelines with various
alternative-worlds relationships among them.  But, yes, things are
tree-like in the sense that once you jump to an alternative world you
don't come back to this one.

"...forces you to represent every case": Again with the word
"represent."  I have to _say_ there are a lot of cases, but there are,
aren't there?  I mean, suppose I am making a binary decision, and
meanwhile 9 other autonomous agents are making indepedent binary
decisions.  Aren't there going to be at least 1024 possible worlds?

I didn't say parallel processes are comparable and inertial.  I said
that in any given possible world they were.  Comparability just means
that all the situations in a given scenario come from the _same_
possible world, which is a minimal requirement.  Inertia means that
nothing happens without a cause; it's much trickier to formalize, but
the intuition seems right.  I mentioned that in classical planning
"nothing happens without a cause" reduces to "nothing happens," but I
immediately pointed out how inappropriate that framework is for web
services. 

   Aside from the genral comments we have the following questions about the
   semantics.

   1.  The concept of Tag Tree was very difficult to grasp, but it seems to
   be equivalent to a parse tree where each node is annontated with a VSI.

No.  Consider a statement of the form "if a then b else c" (taking a
much simplified syntax).  In each possible world the tag tree either
has an occurrence of 'b' or an occurrence of 'c', not both.  

Loops, which I didn't talk about, would show another divergence.  In
each possible world, the tag tree for a loop has one subtree per
iteration.  

    Also, does a Tag Tree represents one particular trace or a set of
   traces?   

One trace.

   This is also related to the semantics of Sequences and other
   constructs;  why do they generate set of trees rather than one tree?

Because even a sequence can be executed in an infinite number of
different situations.

   2.  There is no concept of "open VSI" which does not specify what the
   end state is.  This seems to be useful to describe processes that
   have not terminated yet.

Yes.  I ducked that issue so I didn't have to commit to a particular
ontology for, say, the situation infinitely far in the future.  
I have a preference for how it should be done, but there is a
divergence of opinion.  (One reason for why DAML-Time kind of chugged
to a halt.)

   3.  Why the definition of meaning (p 11) is a couple <channel,
   denotation>, why is it not just denotation?  Why can't channels be just
   part of the environment?

They could, but they have enough special properties that I split them
off. 

   4.  In the semantics of call (p. 12), you seem to mix the values and
   structure, because you have a set of trees that depend on the values of
   an atomic process, but this could be infinitly large.

The denotation of an atomic process is an infinitely large set of
execution traces.

   5.  Related to the general comment above,  how strong of an assumption
   are you making on the inertia of parallel processes?

Hopefully not strong at all.  Two VSIs can be consecutive in the tag
tree (i.e., from the point of view of the target agent), but an
arbitrary amount of other stuff can be going on.

   6.  On page 8, why does piece(m,l) resets to x?

I had to have some convention for the meaning of $m + l\mapsto x$ in the
case where $m$ already has $l$ mapping to something.

   7.  What are the advanages of using channels for data flow as opposed to
   owl:sameAs?

I don't know.  The first step in answering the question is for me to
show a mapping from surface syntax to the Martin-Paolucci PAI-in-RDF
syntax.  Maybe channels will turn out to be expressible in terms of
owl:sameAs.  

[1] <a href="http://cs-www.cs.yale.edu/homes/dvm/papers/pddl-proc-sem.pdf">
The Formal Semantics of Processes in PDDL. Proc. ICAPS Workshop on PDDL</a>

                                             -- Drew

Received on Wednesday, 17 September 2003 13:20:34 UTC