# OWL-S Surface Syntax, Version 0.4

From: Drew McDermott <drew.mcdermott@yale.edu>
Date: Sat, 11 Oct 2003 00:36:01 -0400
Message-ID: <3F8788B1.3000809@yale.edu>

This is a substantial revision of the previous edition.

Changes:

Formal semantics has been omitted.  The focus is entirely on surface and
RDF syntax.

The document reflects a consensus in the OWL-S coalition about how many
hitherto unresolved issues should be settled.  Perhaps "consensus" is
too strong a word, in which case think of it as a "surprisingly elegant
compromise."

-- Drew McDermott
Yale Computer Science Department

\documentclass[11pt]{article}
\usepackage{helvet}
\usepackage{alltt}

\def\la{\langle}
\def\ra{\rangle}
\def\inp{\ensuremath\downarrow\!}
\def\outp{\ensuremath\uparrow\!}
\def\inoutp{\ensuremath\downarrow\!\uparrow\!}
\def\thisproc{}
%%%% \def\thisproc{\texttt{@}}
\def\env{\mbox{\it env}}
\def\omap{\mbox{\it outmap}}
\def\muni{\,\backslash\! +}
\newcommand\txtt[1]{\texttt{#1}}
\newcommand\txrm[1]{\textrm{#1}}
\newcommand\txit[1]{\textit{#1}}
\newcommand\txrmit[1]{\textrm{\textit{#1}}}
\newcommand\itm[1]{\mbox{\textit{#1}}}
\newcommand\rmm[1]{\mbox{\textrm{#1}}}
\newcommand\ttm[1]{\mbox{\texttt{#1}}}

\def\noteme#1{}%{}
\def\notecoauth#1{[[#1]]}

\begin{document}

\begin{center}
Surface Syntax  for OWL-S-PAI \\
**  DRAFT 0.4 ** \\
The OWL-S coalition \\
Edited by Drew McDermott \\
October 10, 2003 \\
\end{center}

\section{Goals}
\label{sec:intro}

This is a proposal for a surface syntax for the emerging
processes as instances'' (PAI) notation for OWL-S.
The formal semantics that was formerly conjoined has been split off,
and will be dealt with in a separate document.

The goals of this exercise are to
\begin{enumerate}

\item Explain how it relates to the usual RDF syntax

\end{enumerate}

\section{Syntax and Informal Semantics}
\label{sec:surface}

The syntax we propose is somewhat Lisp-based, but not entirely.  The
main reason to go this route is that Lisp's concrete syntax is
essentially isomorphic to its abstract syntax, so you can view this as
a placeholder for a syntax with more infix operators and fewer parentheses.

The key concept in OWL-S is the \emph{process}, which is an
activity carried out by an agent, typically a web service or a client.

A \emph{process definition} is a description of a process.  Processes
come in several flavors, atomic, simple, and various sorts of
composite, distinguished by their control constructs (conditional,
choice, parallel, loop, etc.).

We will assume that a process starts with its control construct, or the
reserved words {\tt Atomic} or {\tt Simple}.  So an if-then-else might
look like
\begin{center}
\texttt{(If-Then-Else \ldots)}
\end{center}
By convention,
reserved control constructs have names starting with a capital letter.

\subsection{Args, Results, Preconditions, Effects}
\label{sec:IOPE}

Every process can have input and output parameters, described using fields
\texttt{:args} and \texttt{:results}.  Input and output parameters
may have optional types, the OWL classes they belong to.  So a simple
sequence might be described
thus:
\begin{alltt}
(Sequence :args (a - Integer)
\textit{---steps---}
:results (b - String))
\end{alltt}
We also capitalize the name of classes used in type declarations.
Multiple args and results can be expressed by putting more pieces into
a single \txtt{:args} or \txtt{:results}, or by having multiple
\txtt{:args} and \txtt{:results} specs, or by any convenient
combination.  A variant of \txtt{:results} is
\txtt{:conditional-results}, as in
\begin{alltt}
(Sequence ...
:conditionalResults
(:coCondition (or (expired card1)
((balance card1) > (limit card1)))
fail-message - String))
\end{alltt}
The general format of a conditional result is \\
\txtt{(:coCondition $P$ \txrmit{---params---})}.

Besides \texttt{:args} and \texttt{:results}, there can be
a \texttt{:locals} declaration.

Processes can also have preconditions, which must be true before the
process can be started:
\begin{alltt}
(Sequence :args (customer - Person)
:precondition (exists (x - Credit-card)
(and (credit-card-of x customer)
(not (maxed-out x))))
...)
\end{alltt}
If the precondition is not true when the process begins, then some
sort of failure should occur.  \notereader{This is an area that still needs
elaboration in the OWL-S context.}  An outside observer looking at
this process description can assume that the process executor ensures
that the precondition is true at the appropriate time.  The process
executor itself might employ a planner of some kind to elaborate the
process with steps that make the precondition true.

Processes can also have effects, which are represented using
\txtt{Effect} and \txtt{ConditionalEffect} expressions:
\begin{tabbing}
\hspace{2em}\=\txtt{(Con}\=\txtt{ditionaEffect}  \+\+\\
\txtt{:ceCondition $P$} \\
\txtt{:ceEffect $E$)}
\end{tabbing}
Example:
\begin{tabbing}
\hspace{2em}\=\txtt{(Ato}\=\txtt{mic \ldots} \+\+\\
\txtt{:args (cd - Credit-card newcharge - Number)} \\
\txtt{:effect (Con}\=\txtt{ditionalEffect} \+\\
\txtt{:ceCondition (not (maxed-out cd))} \\
\txtt{:ceCondition (not (stolen cd))} \\
\end{tabbing}
Note that a \txtt{ConditionalEffect} can have multiple conditions.
The intent is that if all are true, the effect will be imposed.''
(Please note that our examples, which all seem to be talking about
credit cards, do \emph{not} reflect any coherent theory of credit-card
transactions!  Think of them as a nonexhaustive sampler of good and bad ideas for
representing actions involving credit cards.)

An unconditional effect is one that has no \txtt{ceCondition}s.  These
can be written using the same notation as for
\txtt{ConditionalEffect}, but with \txtt{Un\-Conditional\-Effect}
substituted.  Alternatively, one can just specify the effect.  So the
following are equivalent:
\begin{tabbing}
\hspace{2em}\=\txtt{(Ato}\=\txtt{mic \ldots}  \+\+\\
\txtt{:results (x - Number)} \\
\txtt{:effect (UnC}\=\txtt{onditionalEffect} \+\\
\txtt{:ceEffect (know ((bal card) = x))))} \-\-\-\\
and \+\\
\txtt{(Ato}\=\txtt{mic \ldots} \+\\
\txtt{:results (x - Number)} \\
\txtt{:effect (know ((bal card) = x)))}
\end{tabbing}

\subsection{Process Instances, Tags, and Dataflow}

There is a crucial distinction between a process and a \emph{process
instance}.  The distinction is obvious in a case like this:

\begin{alltt}
(Sequence
(toggle-the-switch)
(toggle-the-switch))
\end{alltt}
\noindent which contains two instances of the process
\texttt{toggle-the-switch}.
In keeping with RDF style, the description of a process may accompany
one of its instances, or may be placed elsewhere.  In the example
above, \texttt{toggle-the-switch} must obviously be defined somewhere
else.  Instead, we could have written this:
\begin{alltt}
(Sequence
(Atomic-process :ID toggle-the-switch)
(toggle-the-switch))
\end{alltt}

If we want to give a name to a process instance, we use the
\texttt{tag} construct:
\begin{alltt}
(tag-scope (tog1 tog2)
(sequence
(tag tog1 (simple-process :ID toggle-the-switch))
(tag tog2 (toggle-the-switch))))
\end{alltt}
The \texttt{tag-scope} construct is necessarily to indicate the scope
of the names.  However, there is an obvious rule for filling in the
scope if left implicit: The scope of a tag is as wide as possible
but no wider than the innermost iteration or process definition (that
is, with an \texttt{:ID} attribute).  OWL-S syntax checkers should use
this rule to fill in the scope of tags when left implicit.

We can use \texttt{tag} names to describe dataflows between steps.
Suppose we have a process for authorizing uses of  credit card.
Because it must communicate with some computer in a central location,
it sometimes times out if traffic to that computer is heavy.  So the
process has three possible outputs: \texttt{authorized},
\texttt{not-authorized}, and \texttt{timeout}.  The process used by a
retailer might be to try the subprocess one or two times and then
give the customer the benefit of the doubt.  First, some definitions:
\begin{alltt}
(owl:Class CC-check-res
(owl:oneOf (owl:Thing :ID authorized)
(owl:Thing :ID not-authorized)
(owl:Thing :ID timeout)))

(owl:Class CC-acc-status
(owl:oneOf (owl:Thing accepted)
(owl:Thing not-accepted)))

(Simple-process :ID check-auth
:args (cc - Credit-card-data)
:results (res - CC-check-res))
\end{alltt}

Now, a process using the entities defined:
\begin{alltt}
(Sequence :args (cc - Credit-card-data)
:results (final-res - CC-acc-status)
(check-auth cc <= cc
res => (ch1res($$\inp$$ check1)))
(tag check1
(If-Then-Else :args (ch1res - CC-check-res)
:ifCondition (ch1res = timeout)
:then
(Sequence :results (ch2res - CC-acc-status)
(check-auth cc <= cc
res => (ch2res($$\inp$$ check2)))
(tag check2
(If-Then-Else :args (ch2res - CC-check-res)
:results (res - CC-acc-status)
:ifCondition (ch2res = not-authorized)
:then (Value not-accepted => final-res)
:else (Value accepted => final-res))))
:else
(If-Then-Else
:ifCondition (ch1res = authorized)
:then (Value accepted => final-res)
:else (Value not-accepted
=> final-res)))))
\end{alltt}
An expression of the form $e_1 \ \ttm{=>}\ e_2$ may be embedded in any
process expression.  Here $e_i$ is a \emph{tagged parameter
expression,} an unambiguous specification of a parameter of a
particular step.  The meaning of $e_1 \ \ttm{=>}\ e_2$ is that the
value of parameter $e_1$, when it becomes available, also becomes the
value of $e_2$.  It is called a \emph{dataflow expression}.

The format of the $e_i$'s in a dataflow expression is
$p(\ttm{[}\inp\, |\, \outp \ttm{]} \ttm{[}s\ttm{]})$, where $s$ is an optional step tag.
%%%% or the special symbol \texttt{@}
The presence of $\inp$ vs{.} $\outp$
tells us whether we are referring to an input or output parameter, and
$p$ tells us its name.  So \texttt{ch2res($\inp$check2)} means the
input parameter  \texttt{ch2res}  of \texttt{check2}, the second
attempt to check the credit card.  If the $s$ part is omitted, it
means the innermost process that the \texttt{=>}'' expression is
found in that has an input or output parameter $p$.

An expression of the form $\itm{param}\ttm{(}\outp\thisproc{}\ttm{)}$ on the left of
an \texttt{=>}'' may be abbreviated as simply \textit{param}.
Similarly, an expression $e \ttm{=>} \itm{param}\ttm{(}\inp\ \thisproc\ttm{)}$
may be abbreviated as $\itm{param} \ttm{<=} e$.

There is an issue about what an OWL-S execution engine should do if a
step has an unfilled input parameter but is otherwise ready to be
executed.  Our current position is that the engine should pause until
the value of the parameter is available.  It would probably be wise to
avoid making this the \emph{only} determinant of control flow.  That
is, if data flows from step 1 to step 2, it's a good idea to make sure
that step 2 follows step 1 in a \txtt{Sequence}.  However, this is not
always possible; there are control patterns that can be expressed
through dataflow and no other way (so far).

Another issue is whether a parameter of a step can get a value more
than once.  The (current) answer is No.  The intent is to allow
reasoners to make strong inferences about what exactly is flowing from
one step to another without detailed analysis of how the channel
between them is set.  One consequence of this design decision is that
nontrivial dataflow in loops can't really be represented with the
tools at hand.

There is a built-in control contruct  \txtt{Compute} that takes arbitrary
inputs (including none) and outputs, \txtt{val}.  For instance,
it could take numerical data from two predecessor steps and sum them, thus:
\begin{tabbing}
\hspace{2em} \=     \txtt{(Compute}\=\txtt{:args (n1 n2 - Number) } \+\+\\
\txtt{:results ((val (n1 + n2)) - Number))} \-\-\\

The form  \+\\
\txtt{(Compute :args (\ldots) :results ((val $E$) - $t$) (val => $e$))} \-\\
can be abbreviated \+\\
\txtt{(Value :args (\ldots) $E$ => $e$)}
\end{tabbing}

\subsection{Calling Processes}

There are two ways to call'' a process: write
\texttt{([Call] \txrmit{process-name} \ldots)},
or \texttt{(Invoke  :service $S$ \txrmit{process-name) \ldots})}.
The former notation (in which \txtt{Call} is optional)
means that the process with the given name is to be created
and run as
a subroutine of the current process.  The second is more general, and
means that a process with the given name is to be found or created,
and the arguments are to be passed to it.  The process might be run as
a subroutine, but it might also be found on another host somewhere,
and the arguments might be transmitted to it using (e.g.) SOAP
messages.  Which of these possibilities (among others) obtains depends
on the service argument $S$, which might be the URL of a service
description.  Exactly what $S$ consists of, and how the information
there interacts with the \emph{grounding} of the current process, are
matters outside the scope of this document.

Two constructs exist to make it possible to write web services that
may be invoked from another process:
\begin{alltt}
(Accept :service $$S$$ :ID \txrmit{process-name} :followWith \textit{process})
\end{alltt}
declares that this process \emph{implements} the service described by
$S$.  When some \texttt{Invoke} from another host finds this
implementation, the \textit{process} is executed.

To provide more flexibility, several alternative \txtt{Accept}s can be
wrapped inside a \txtt{Select}:
\begin{tabbing}
\hspace{2em}\=\txtt{(Sel}\=\txtt{ect }  \+\+\\
\txtt{(Accept \ldots)} \\
\txtt{(Accept \ldots)} \\
\ldots \\
\txtt{(Accept \ldots))}
\end{tabbing}
This construct allows a single host to implement several services.

\notecoauth{We need to be clear about whether \txtt{Invoke} is
nonblocking, or can be declared to be nonblocking; and under what
circumstances  an

\subsection{Miscellaneous Control Constructs}

All that remains is to sketch the various control constructs and their
meanings.

\noindent * \txtt{(Choice \txrmit{List-of-processes})} chooses
an element from the \txit{List-of-processes} and executes it.  Which
one is chosen is unspecified; it is either chosen by machinery that is
not revealed, or is the result of some planning process.

\noindent * \txtt{(Split \txrmit{List-of-processes})} spawns
execution of
all of
the processes, in separate threads, as it were.  The
\txtt{Split} finishes immediately.

\noindent * \txtt{(Split+Join \txrmit{List-of-processes})}
executes all the processes in the txrmit{List-of-processes} in
parallel, then waits until all complete before proceeding.

\noindent * \txtt{(Repeat-While :whileCondition $P$ :whileProcess
$Q$)} executes $Q$ until $P$ is false, possibly zero times.

\noindent * \txtt{(Repeat-Until :untilCondition $P$ :untilProcess
$Q$)} executes $Q$ until $P$ is true, possibly zero times.

\notereader{A BNF syntax will go here when the notation is a bit more
stable.}

\section{Relationship to Deep'' Syntax (RDF)}

The original syntax for OWL-S was based on RDF and OWL, for the good
reason that it provides a declarative description of a process as a set of
assertions (triples'').   In this section we explain how the new
surface syntax relates to the RDF/OWL syntax.

A process specification corresponds to a
\emph{description} of a process.  So \txtt{(\txrmit{Construct} \ldots
)} corresponds to the RDF
\begin{tabbing}
\hspace{2em}\=\txtt{<\txrmit{Cons}}\=\txtt{\txrmit{truct}>} \+\+\\
\ldots -\\
\txtt{</\txrmit{Construct}>}
\end{tabbing}
The class \txit{Construct} we refer to as a \txtt{control class}; it
is that class of process whose construct is \txit{Construct}.
The fields of a control construct then become properties of the object
being described.  This applies in a straightforward way to fields like
\txtt{:then} and \txtt{:else} whose values are themselves processes.
The constructs \txtt{Sequence}, \txtt{Split}, and \txtt{Split+Join}
have an indefinite number of subprocesses.  In the deep syntax, we
use the property \txtt{components} to
specify a property of the process whose values are bags of processes.
So
\txtt{(Sequence $p_1$ $p_2$ \ldots $p_n$)} is translated into
\begin{tabbing}
\hspace{2em}\= \txtt{<Seq}\=\txtt{uence>} \+\+\\
\txtt{<com}\=\txtt{ponents rdf:parseType="Collection">} \+\\
$p_1*$ \\
$p_2*$ \\
\ldots \\
$p_n*$ \-\\
\txtt{</components>} \-\\
\txtt{</Sequence>}
\end{tabbing}
(where $p_i*$ is the RDF form of $p_i$).
Similarly for \txtt{Split} and \txtt{Split+Join}.

Processes have zero or more \txtt{arg} properties and zero or more
\txtt{result} properties.  \notecoauth{Formerly known as inputs and
outputs.}  The value of each is an object of the class
\txtt{Parameter}, or, more likely, one of its subclasses,
\txtt{InParameter} or \txtt{OutParameter}.  We need a way to declare
the type of the values of the parameter, which is not the same as the
type of the parameter itself (which is always \txtt{InParameter} or
\txtt{OutParameter}).  To avoid having to use OWL-Full, we do this
with a property \txtt{parameterValue} suitably restricted.  Example:
\begin{alltt}
<Atomic>
<arg>
<InputParameter :name="cd1">
<rdf:type>
<owl:Restriction>
<owl:onProperty rdf:resource="&owl-s;parameterValue"/>
<owl:allValuesFrom rdf:resource="&cc;CreditCard"/>
</owl:Restriction>
</rdf:type>
</InputParameter>
</arg>
</Atomic>
\end{alltt}
The property \txtt{parameterValue} should be read as has as possible
value.''  (We can't refer to the \emph{actual} value of a parameter
without an ontology of execution traces, which does not yet exist.)
So the example above says that the \txtt{cd1} input parameter must be
a \txtt{CreditCard}.

The hard part of describing
preconditions and effects in RDF is, as always, the fact these objects
are formulas and terms obeying a recursive grammar.  Here we take an
agnostic view on which gimmick to use in representing such
expressions, and just assume there is a class \txtt{Condition} and a
class \txtt{Effect}.  (We have put forth proposals for representing
these things in the past, so this is not exactly an omission in OWL-S, just
a hole among whose unappetizing fillers we are still reluctant to
choose.)   In some domains, \txtt{Effects} are just \txtt{Conditions},
but we reserve the right to use expressions like \txtt{(add (bal cd1)
(cost mercedes-benz-2))}, which says to increase the balance on
\txtt{cd1} by some (huge) amount of money.

We still need the classes \txtt{ConditionalOutput} and
\txtt{ConditionalEffect}, with properties \txtt{coCondition},
\txtt{coOutput}, \txtt{ceCondition}, and \txtt{ceEffect}.  The class
\txtt{UnconditionalEffect} is a subclass of \txtt{ConditionalEffect}
restricted to having zero \txtt{ceConditions}.

Tags must be handled with some care in RDF.  The \txtt{tag-scope}
construct behaves like a variable binder.  We can have a
\txtt{TagBind} control class with two properties: \txtt{tagBound} and
\txtt{process}.  The \txtt{tagBound} is an object of class
\txtt{tagSpec}, with two important properties: the \txtt{rdf:ID} and
\txtt{tagName}.  The former is an identifier with document scope, just
like all \txtt{ID}s.  The latter is a string thrown in for mnemonic
value.

The tag is actually declared by giving a process a \txtt{tag}
property, whose value is a \txtt{tagSpec}.  Here is an example.  The
surface process spec
\begin{alltt}
(tag-scope (toot foof)
(If-Then-Else
:ifCondition \ldots
:then (tag (A) \ldots)
:else (tag (B) \ldots)))
\end{alltt}
would be represented by the RDF
\begin{alltt}
<TagBind>
<tagBound>
<TagSpec rdf:ID="g33" tagName="toot"/>
</tagBound>
<tagBound>
<TagSpec rdf:ID="g34" tagName="foof"/>
</tagBound>
<process>
<If-Then-Else>
<ifCondition> \ldots </ifCondition>
<then>
<Call>
<tag rdf:resource="#g33"/>
<callee ref:resource="#A"/>
</Call>
</then>
<else>
<Call>
<tag rdf:resource="#g34"/>
<callee ref:resource="#B"/>
</Call>
</else>
</If-Then-Else>
</process>
</TagBind>
\end{alltt}

Dataflows are objects of class \txtt{DataFlow}, which has two
properties \txtt{source} and \txtt{destination}, each of which is an
object of type \txtt{ParameterSpec}.  A \txtt{ParameterSpec} is
defined by its \txtt{psParam}, \txtt{i-or-o}, and \txtt{psStep}
properties.  The property \txtt{flow} connects a process to the
dataflows involving it.

So, for instance, the surface example
\begin{alltt}
(Sequence
(tag step1 (A pen => ult($$\inp$$step2)))
(tag step2 (B)))
\end{alltt}
would look thus in RDF:
\begin{alltt}
<TagBind>
<tagBound>
<tagSpec rdf:ID="proc67" tagName="step1"/>
</tagBound>
<tagBound>
<tagSpec rdf:ID="proc72" tagName="step2"/>
</tagBound>
<process>
<Sequence>
<components rdf:parsetype="Collection">
<Call>
<tag rdf:resource="#proc67"/>
<callee rdf:resource="#A"/>
</Call>
<Call>
<tag rdf:resource="#proc72"/>
<callee rdf:resource="#B"/>
</Call>
</components>
<flow>
<DataFlow>
<source>
<ParameterSpec psParam="pen"
i-or-o="&owl-s;outputP"
psStep="#proc67"/>
</source>
<destination>
<ParameterSpec psParam="ult"
i-or-o="&owl-s;inputP"
psStep="#proc68"/>
</destination>
</DataFlow>
</flow>
</Sequence>
</process>
</TagBind>
\end{alltt}
Unfortunately, most of the abbreviating conventions we can exploit in
the surface syntax do not apply in the deep syntax.   The RDF version
is fairly readable, but difficult for humans to write without error.

\notereader{Compute is not yet mapped to a deep construct.}

\section{Ontology for Deep Syntax}

\notereader{To be released any day now.}

\label{sec:conclusions}

The wealth of new material we have introduced here may make some users
of OWL-S (and DAML-S) uneasy.  Just how stable is this language?
Actually, almost all the changes we have made are \emph{augmentations}
to the notation, not incompatible changes.  The decision to represent
processes as instances instead of classes has made it much easier to
fill in gaps that had stood empty for a long time.

Although we provide the iterative constructs \txtt{Repeat-While} and
\txtt{Repeat\--Until}, we provide no way for them to (say) add up the
values received from some source.  The only reason for this
omission is that it would require generalizing channels a bit.  A loop
requires the idea of an \emph{accumulator}, which changes in a clearly
specified way on each iteration.
At most once per
iteration a value is sent to the accumulator, and combined with the
value that's already there.  Probably the best way to model
accumulators is as parameters that contain a history list of the values
accumulated to date.

\end{document}


Received on Saturday, 11 October 2003 00:36:12 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 3 July 2007 12:25:44 GMT