%% More examples of in-place array updates.
\documentstyle[twoside]{article}
\onecolumn
\makeatletter
{\@definecounter{MetaNote}\@addtoreset{MetaNote}{section}%
\expandafter\xdef\csname theMetaNote\endcsname{\expandafter\noexpand
  \csname thesection\endcsname \@thmcountersep \@thmcounter{MetaNote}}%
\global\long\def\MetaNote#1{{\@thm{MetaNote}{MetaNote} #1\@endtheorem}}}
%%  \long\def\MetaNote#1{\relax}

{\@definecounter{TechComm}\@addtoreset{TechComm}{section}%
\expandafter\xdef\csname theTechComm\endcsname{\expandafter\noexpand
  \csname thesection\endcsname \@thmcountersep \@thmcounter{TechComm}}%
\global\long\def\TechComm#1{{\@thm{TechComm}{Note to Reviewer:} #1\@endtheorem}}}
\def\TT{\tt\char`\^}
\def\fcpid{{\ccfont FCP(\withmath{\downarrow}, {\tt |})}}
\def\asker{\mbox{\tt <}}
\def\teller{\mbox{\tt >}}
\def\fcpcolon{{FCP(:)}}
\def\sal{{SAL}}
\def\doc{{\bf Doc}}
\def\janus{{\sf Janus}}
\def\Janus{{\sf Janus}}
\def\herbrandid{\fcpid}
\def\askt#1#2{#1 \ask #2}
\def\strand{{\em Strand}}
\def\seal{{\tt seal}}
\def\unseal{{\tt unseal}}
\def\junk{{\tt junk}}
\def\inv{{\tt inv}}
\def\mA{\mbox{\bf J}}
\def\union{\mbox{\em union}}
\def\SIZE#1{\withmath{{\tt\char`\|}#1{\tt\char`\|}}}
\begin{document}
\title{Programming in Janus}
\author{Vijay A. Saraswat, Xerox PARC \\ \and
Ken Kahn, Xerox PARC \\ \and
Jacob Levy, Technion, Haifa}
\date{(Extended Abstract, December 1989)}
\maketitle
\input{vijay-macros}
\def\dc{{\ccfont dc}}

\begin{abstract}
In an accompanying paper we present the design and definition of \janus, a
performance-efficient distributed constraint programming
language \cite{janus}. \janus\ is based on an algebra of infinite trees and
hyper-multisets and enjoys the {\em failure-free property}: 
\janus\ computations cannot abort because the store is
inconsistent. This is achieved by imposing syntactic restrictions
which ensure that a variable may occur at most twice in a
run-time configurations, and by implementing an annotation scheme
which ensures that only  one of these occurrences can be used to
generate constraints on the variable.
%%<<Was: which ensures that one of these occurrences only can be used to
%%generate constraints on the variable. >{}>

Prima facie, \janus\ syntactic restrictions appear quite severe.
In this paper we show that a large variety of programming idioms
supported by eventual publication \herbrand\ languages such as
\parlog\ and \fghc\ can be directly and naturally supported in
\janus. Furthermore, because of \janus\ properties, it is
possible for a \janus\ compiler to generate code to recycle memory when
it becomes garbage. Because of these properties, it is
possible for a \janus\ compiler to generate very efficient code.
Indeed, in some cases, we argue that a \janus\ compiler for a
sequential target machine can generate code comparable in
efficiency to code generated from similar programs written in
conventional imperative languages. 
\end{abstract}

%%\input{intro}  % max 3 pages
%% What can get put in.
%% More examples of many-to-one communication.
%% Work out the list intersection program in more detail. 
%% Listener access is an emergent property.
%% Perhaps work out how encryption and decryption work in this setting.
%% Perhaps use function syntax.

\section{Introduction}
Concurrent logic programming languages, have been thoroughly
studied in the last few years.  Many programming
idioms for these languages have been discovered, which deal, for
example, with data flow computations, producer-consumer
synchronization, short circuits (used for the detection of stable
properties of networks \cite{dist-term}), recursive doubling
(technique for path shortening, using the ``transparent
forwarding'' facility provided by the ability to transmit askers
and tellers as messages), incomplete messages (messages whose responses can
automatically---and efficiently---be routed back to the receiver),
many-to-one communication using bags,
techniques for modelling agents with mutable local state, etc.
Many of these idioms are discussed in the literature in such places as
\cite{CP}, \cite{kahn-ecoop}, \cite{strand-book}, \cite{my-thesis-book},
\cite{parlog-book}, \cite{ueda}, etc. Surprisingly, {\em all} of these
idioms can be directly used in \janus. Some others, such as
``producer  protection'' which were hitherto unavailable in the
\cc\ languages are also, quite surprisingly, obtained in
\janus.\footnote{Producer protection is also unavoidable---that is
the essence of the ``constraint programming without constraint-solving'' 
slogan.}

In the rest of this section we summarize the main features of the
constraint system $\cal J$ underlying \janus, and the syntactic
restrictions enforced by the \janus\ system. \cite{janus}
discusses the underlying motivations in more detail; the discussion here
is adapted from that paper. In the rest of this paper we assume a
familiarity with the programming techniques discussed in the concurrent
constraint (logic) programming literature.  Here we focus on differences
which result from the syntactic restrictions which Janus imposes, as
well as the additional functionality which arrays and bags provide.  We
also point out where an implementation could take special advantage of
\janus\ restrictions to produce particularly 
efficient code.

\subsection{A review of \janus}
The important ways in which \janus\ programs differ from those in other eventual publication \herbrand\ languages
(e.g. FGHC, Strand) are
\begin{itemize}

\item {\em Syntactic restrictions on variables.}  These restrictions are designed 
to be strong enough to ensure {\em at compile time} that no conflicting
constraints can occur at runtime.\footnote{In logic programming
terminology we ensure that unification cannot fail.}

\item {\em Introduction of bags and arrays.}  Rather than the usual 
domain of Herbrand terms, the domain of \janus\ objects are bags and
arrays.  Because of our desire to maintain the failure-freeness property
of \janus\ programs we need to permit cycles in these bags and arrays.
Hence, we define bags as infinitary ``hyper-multisets'' and arrays as
infinite, finite-width tree.  Bags are introduced to properly handle
many-to-1 communication.  Arrays are a generalization of terms (or
tuples) which enable \janus\ programs to be competitive with convential
imperative programs.
\end{itemize}

$\cal J$ is defined over a domain of objects that, roughly, corresponds
to infinite, finite-width trees (called {\em arrays} since their sons
can be accessed via arithmetic indexing) and infinitary
``hyper-multisets''. Two multisets are considered the same if there
exists a bijection between the index sets of their immediate sons such
that corresponding sons are recursively ``bisimilar''. This
complication is necessary in order to be able to solve equations such as
$X=\{X\}$.  However, we have shown in \cite{janus} that even if
such ``cyclic'' bags or arrays are created, they cannot be accessed at
run-time by any agent so that in practice the user does not have to be
concerned with writing programs that manipulate such objects. Nor need
a \janus\ implementation be concerned with deciding whether two
multisets are the same, since the syntactic restrictions of \janus\
ensure that this cannot be asked.  As summarized in
Table~\ref{constraint-table}, $\cal J$ allows constraints for creating
and accessing arrays and bags. It also allows ``naive arithmetic'', the
sort of arithmetic allowed in the overwhelming majority of programming
languages, namely, calculations.

\begin{table}
\begin{tabular}{|l|l|l|l|}
\hline
Constraint & Description & Status & Restrictions \\
\hline\hline 
Arithmetic && \\ 
&&&\\
$\tt Y*Z$ & multiplication & Tell-only & number(Y), number(Z) \\
$\tt Y+Z$ & addition & Tell-only & number(Y), number(Z) \\ \hline 
Arrays \\
&&&  \\
array(X) & predicate & Ask-only & \\
$|X|$  & cardinality & Ask-only & array(X) \\
\tuple{X_1,\ldots, X_n} & array constructor & & \\
array(N,B) & constructor & Tell-only & $\tt N \geq 0 \wedge$ fixed(B) \\
\tuple{X_1,\ldots, X_n \alt X} & array concatenation & & array(X) \\
array(N,A,T) & \hbox{matched array of askers \& tellers} & Tell-only & $\tt N \geq 0$ \\
$\tt X \circ Y$ & array concatenation (constructor) & Tell-only & array(X), array(Y) \\
A.I & element selection & Tell-only  &  $\tt 0 \leq I, I < |A|$ \\
A[I..J] & subsequence selection (constructor) & Tell-only & 
$0 \leq I, I \leq J, J < |A|$ \\
$\tt A[I_1  \to t_1, \ldots, I_n \to t_n]$ & Updating (constructor) & Tell-only 
& $\tt  0 \leq I_1, I_1 < |A|$ \\ 
&&&  $\ldots,$\\
&&& $\tt 0 \leq I_n, I_n < |A|$ \\ \hline 
Bags & &   \\ 
&&&\\
bag(X) & predicate & Ask-only & \\
bag(X,Y) & constructor & Tell-only & \\
element(X,Y) & selector & Ask-only & $\neg bag(X) \wedge$ bag(Y) \\
\hline 
\end{tabular}
\caption{Some basic constraints in $\cal J$}\label{constraint-table}
\end{table}

Briefly, arrays of size {\tt N} initialized to contain {\tt B} (which is
forced) may be created by {\tt array(N,B)}.  This is is equivalent to
${\tt <B,B,\ldots,B>}$ with {\tt N} occurrences of {\tt B}.  An array of
askers and tellers of size {\tt N} is created by ${\tt
array(N,\TT A,\TT T)}$ which is equivalent to the conjunction of ${\tt A =
<X_1,\ldots,X_n>}$ and ${\tt T = <\TT X_1,\ldots,\TT X_n>}$.  ${\tt A.I}$
selects the {\tt I}th element of {\tt A} (using zero indexing).  ${\tt
A[I..J]}$ returns the portion of {\tt A} between {\tt I} and {\tt J}
inclusive. $\tt A[I_1 \to t_1, \ldots, I_n \to t_n]$ returns an array of
the same dimension as {\tt A} and whose elements are the same except for
the indices ${\tt I_i}$ which are associated with the corresponding
${\tt t_i}$.

Bags are constructed by {\tt bag(X,Y)} which makes the bag of X (or its
elements if X is a bag) and Y (or its elements if Y is a bag).  {\tt
element(X,Y)} matches a bag which has at least one element which is
either a value or a teller.  The match binds {\tt X} to one such element
and {\tt Y} to the remainder of the bag.

A \janus\ program is an unordered collection of clauses of the form
\begin{ccprogram}
\agent p(t_1,\ldots, t_n)\leftarrow C \alt C_1, B..
\end{ccprogram}
\noindent where the $\tt t_1,\ldots,
t_n$ are $\cal J$-terms, {\tt B} is a possibly empty conjunction of goals, 
$\tt C_1$ and $\tt C$ are $\cal J$-permissible Tell- and Ask-constraints respectively
such that $\tt C \wedge C_1$ is $\cal J$-satisfiable.
In such a rule $\tt p(t_1,\ldots, t_n)$ is said to be
the {\em head}, {\tt C} the {\em guard}, and $\tt C_1,B $ the {\em
body}.\footnote{As usual, we allow the notation $\tt p\leftarrow C_1,B.$ to
abbreviate a rule with an empty guard, and the notation $\tt p.$ to
abbreviate a rule with an empty guard and body.}

Rules in \janus\ also satisfy certain syntactic conditions, involving
the number of occurrences of variables, and the function ``{\tt \TT }''.
Let $K$ be the clause $\tt h \leftarrow C \alt G$.  Say that $\tt C$
{\em forces} {\tt X} if for some parameter $\alpha$, $\tt {\cal J}
\models (C \entails X=\alpha)$.  Say that
{\tt X} is {\em present} in a term {\tt s} if it occurs in {\tt s} even
if occurrences of {\tt \TT X} are not considered. Say that a
variable {\tt X} {\em occurs actively} in {\tt G} if the occurrence is
in the first argument of an ``$=$'' goal or a ``{\tt \TT }'' term, 
and {\em occurs passively} in {\tt G} if it has a non-active occurrence in
{\tt G}. 

The intuitive idea of the following conditions is to ensure that at
run-time a variable {\tt X} ``occurs'' in at most two goals. Further
exactly one of these occurrences (the {\em teller} for {\tt X}) is as
the first argument of a ``{\tt \TT }'' term. (No other restrictions are placed
on the second occurrence, which is called the {\em asker} for {\tt X}.)
The conditions will ensure that only the goal with access to the teller
for a variable can impose constraints on this variable.  The two
variable occurence limit is relaxed when the variable is forced (since
its ground).  When the variable is an array, the conditions permit
multiple occurences which refer to different portions of the array.

The conditions are as follows. 
\begin{enumerate}
\item If any of {\tt \TT t} or {\tt t=s} occur in {\tt G}, then {\tt t}
must be a variable. For technical convenience, we also require that if
any of $\tt t.i, |t|, t[i_1 \to t_1, \ldots, i_n \to
t_n], t[i..j]$ occur in $K$, then $\tt t$ must be a variable.  
If {\tt array(N, s,t)} occurs in $K$, then there must be variables $\tt
A$ and $\tt B$ such  that $\tt s\equiv${\tt  \TT A} and $\tt t\equiv${\tt \TT B}. 
Finally, for efficiency reasons, we require that if {\tt element(t, u)}
occurs in {\tt h}, then {\tt t} and {\tt u} must be variables
unconstrained by {\tt C}. 

\item For every variable ${\tt X} \in \var(K)$, unless $\tt C$ forces $\tt X$
or $\tt {\cal J} \models C \entails array(X)$, {\tt X} must occur at most
twice in  $\tt p \leftarrow G$, and the following conditions must be
satisfied:
\begin{enumerate}
\item {\tt X} occurs actively in {\tt G} only if it
occurs passively in {\tt G}, or {\tt  \TT X} occurs in {\tt h}; 

{\em\small The intuition is: the active occurrence will ``produce''
information which must ``go'' somewhere---either out to the environment
through a teller in the head, or to an asker in the body.}

\item  {\tt X} occurs passively in {\tt G} only if it occurs actively in {\tt G} or is 
present in {\tt h}, and,

{\em\small The intuition is: information ``coming in'' must come from
somewhere, either from a producer in the body, in the case of a ``local
variable'', or from the asker in the head.}

\item {\tt X} does not occur twice in {\tt h}.

{\em\small This just for efficiency reasons.}
\end{enumerate}

\item If $\tt {\cal J} \models C \entails array(A)$, for some variable 
$A$, then $\tt\TT A$ must not occur in {\tt h}, and {\tt A} may not occur
actively in {\tt G}. $\tt A$ may occur passively in {\tt G} 
any number of times, provided that $K$ satisfies the
{\em reference  partition condition} for $A$. 
\end{enumerate}

With each variable $A$ such that $\tt C \entails array(A)$, we
associate a constraint $\phi$, the reference partition condition, over
$\var(K)$ and a new variable $X$. For the clause to be acceptable it
must be the case that $\tt {\cal J}\models C \entails \exists X.\phi$.
(Intuitively, the condition being enforced is that no two occurrences
of $A$ ``reference'' a common element in the array, so that at run-time
the two reference property is maintained---note that one occurrence is
``taken up'' by the occurrence in the head which is necessary if {\tt C}
is to be satisfied.) 
Let $A$ occur $m$ times in the body of the clause. Say that an occurrence
of $A$ is {\em outer} if it is not in the $i$th argument of an {\tt 
update} ($\_[\_\to\_,\ldots, \_\to\_]$) term, for $i>1$.  Say that an
occurrence is {\em stand-alone} if at that  occurrence $A$ is not the first argument of a 
$|\_|, \_[\_..\_]$ or {\tt update} term. 
Then $\phi$ is the 
conjunction of the constraints $\phi_q$, obtained from the following table,
for each outer occurrence $q$:
$$\begin{array}{|l|l|}
\hline
\mbox{Expression} & \mbox{Constraint} \\ \hline \hline
A.I & X.I=q \\
A[I..J] &  \forall K. (I \leq K, K \leq J \entails X.K=q)\\
|A| & true \\
A[I_1 \to t_1, \ldots, I_n \to t_n] &
\begin{array}[t]{l}
\forall K (0 \leq K, K < |A|, \wedge_{j=1}^n (K\not=I_j) \entails X.K=q) \\
\wedge \wedge_{j=1}^n ((\wedge_{l=j+1}^n I_j \not= I_l) \entails \phi_j)\\
\mbox{where $\phi_i$ is the conjunction of the conditions}\\
\mbox{associated with each occurrence of $A$ in $t_i$.}\\
\end{array}\\
A\; \mbox{standalone} & \forall K. (0 \leq K, K < |A| \entails X.K=q)
\\ \hline
\end{array}
$$
Note again that variables present in the clause may occur in $\phi$. For
example, if the only passive occurrences of $\tt A$ in the body of a
clause are in the term $\tt A[I \to A.J, J \to A.I]$ (this is the {\em
swapping} idiom for arrays in \janus), then 
$$\phi\equiv 
\begin{array}[t]{l}
\forall K. (0 \leq K, K < |A|,  (K\not=I), K \not=J) \entails X.K=1 \\
\wedge ((I \not= J) \entails X.J= 2) \wedge X.I=3
\end{array}$$
Note that $\tt {\cal J}\models \exists X.\phi$, hence the reference
partition condition is satisfied for this clause, regardless of the ask
condition for the clause.\footnote{The array reference partition condition can be relaxed if it can
be inferred that certain references are to forced values.  An array consisting completely of ground
values can be referred to without any of these restrictions.}

The dynamic semantics of \janus\
programs is that of \cc\ programs, which is discussed in detail in
\cite{my-thesis-book,popl90}.  The only noteworthy point is that the
Ask-and-Fix operator \cite[Chapter~8.4]{my-thesis-book} is used instead
of the Ask operator.  This implies that at run-time {\em one} (of
possibly many) most general matchers is chosen for the goal and head of
a clause.  It is the use of {\tt element(X,B)} which can introduce multiple general matches.

More precisely, the operational semantics of a \janus\ program can be
described in terms of a transition system over configurations of the form
\tuple{\tt G, \sigma:V}, for {\tt G}  a conjunction of goals and 
$\sigma$ a constraint such that $\tt \var(G) \cup \var(\sigma)\subseteq
V$. 
The single transition rule is:
$$\from{\begin{array}{l}
(1)\; K\equiv (p(t_1,\ldots,t_n) \leftarrow C \alt C_1, B) \in P, \\
\quad\quad\var(K)\cap V=\emptyset, \var(p(t_1,\ldots, t_n))=\{Y_1,\ldots,Y_k\} \\
(2)\; {\cal J} \models \sigma \entails \theta(C) \wedge (\wedge_{i=1}^n s_i=\theta(t_i))
\end{array}}
\infer{\begin{array}{l}
P \vdash\tuple{G_1 \wedge p(s_1,\ldots, s_n) \wedge G_2, \sigma:V} \derives \\
\tuple{G_1 \wedge B \wedge G_2, (\sigma \wedge \theta(C_1)):(V\cup \var(K))}
\end{array}}
$$ 
where $\theta$ is some substitution on $\var(K)$. 
(Here we presume that
the program $P$ is obtained by closing the set of input clauses $P_0$
under all possible renamings of clauses. This is only for technical
convenience.) 

As a result of the above definitions we can show that \janus\ computations 
satisfy a number of run-time properties. Perhaps the most crucial is that no
\janus\ computation can result in a store which is inconsistent. Note that this 
property is achieved even though constraints are being added to the
store {\em without} checking for consistency at run-time.  This follows
from the interesting property that in any configuration obtained from
the execution of a \janus\ program, if a goal $g$ has as subterm a term
$\TT t$, then $t$ is a variable, say $X$, and no other goal contains $\TT X$
as a subterm, and $X$ occurs in at most one goal in the configuration,
ignoring occurrences of $\TT X$. Thus, at run-time, variables work as
point-to-point communication channels, and only the agent which
possesses the ``teller end'' can produce constraints on the variable
(can send messages down the channel).


\section{Standard data-flow programs}
It should be apparent to the reader how conventional data-flow programs
in the style of \cite{kahn} can be written in this style.  Indeed,
\janus\ can be thought of as being an
indeterministic ``data-flow'' language in which receive and send rights
for channels can be passed as (parts of) messages.  
Most systolic computations \cite{systol} are just particular
kinds of dataflow programs and can hence be expressed directly in
\janus.  

%\MetaNote{Say something about how the two occurrence restriction has a bit of 
%functional programming flavor---in fact programs can often be nested, etc.}

\paragraph{Producer-consumer interactions}
We show how to set up a bounded buffer producer-consumer interaction between two
agents. When the two agents are created, a new channel is
generated, and the producer is given the teller for the channel,
and the consumer, the asker. Subsequently, the producer chooses
to generate messages on the channel through the teller in the
usual stream-oriented way, and the consumer ``receives'' these
messages through the asker. 

\begin{ccprogram}
\agent goal:- producer(\TT B, [demand, demand, \ldots, demand | Ds]), consumer(B, \TT Ds)..

\agent producer(\TT B, [demand | Ds]) :- B = [produced | Bs], producer(\TT Bs, Ds)..
\agent producer(\TT B, []) :- B = []..

\agent consumer([produced | Bs], \TT Ds) :- Ds = [demand | MoreDs], consumer(Bs, \TT MoreDs)..
\agent consumer([], \TT Ds) :- Ds = []..
\end{ccprogram}

{\small\em In a \janus\ implementation that reuses structures, if both
goals reside in the same address space, the above program would run {\em
in constant space}, very much in the same way as a concurrent shared
memory program with atomic reads and writes. When the goal is executed,
a buffer of length $n$ is created.  The {\em same} buffer gets reused
over and over again, to represent two lists, the demand list, and the
list of values produced that have not yet been consumed. This
sophisticated behavior follows merely from the normal per-clause
compilation process which recycles a cons that has been read (since it
is the only reader and the writer after writing no longer has a
reference) to be the cons that is being told.  When, in this paper, we
claim that a program runs in constant space we mean that for each clause
of the program the same number and size data structures are constructed
in the body as are read in the head.

In general, wherever possible, it is usually valuable to write programs
whose clauses are ``memory balanced'', that is, 
they construct data structures using as many words of memory as used by
the data structures read. In a structure-reusing implementation, 
the implementation of such a program proceeds by
side-effecting the memory locations read. For example, the 
usual program for {\tt append/3} can be compiled in such an implementation
essentially to code that does a destructive {\tt nconc} of the input lists.
}

\subsubsection{Short circuits}
The standard short-circuit programming technique can be expressed
in \janus\ by imposing a consistent directionality of information
flow.  Consider the following program sketch where information flows
from left to right:
\begin{ccprogram}
\agent p(\ldots,L,R) :- p(\ldots,L,\TT M), p(\ldots,M,R)..
\agent p(\ldots,L,\TT R) :-  R = L..
\end{ccprogram}

An initial query may be {\tt p(done,\TT D),q(D)}.  ``{\tt q}'' can
wait until {\tt D=done} succeeds, before proceeding. 
A good implementation of \janus\ can exploit the directionality of
these short-circuits so that it is never the case that {\tt D} is
bound to {\tt done} via a long dereference chain.

In \cite{dist-term}, streams of switches, a programming technique for
repeated use of a short-circuit, was presented in the context of
\herbrand\ programming. 
\begin{ccprogram}
\agent p(\ldots,L,R) :- p(\ldots,L, M), p(\ldots,M,R)..
\agent p(\ldots, L, R) :- L=[M | L'], R = [M|R'], p(L',R')..
\agent p(\ldots,L,R) :- R = L..
\end{ccprogram}
When an agent desires to close a switch {\em for the current
phase}, it merely equates its left channel to a cons and its
right channel to a cons, and equates their cars, recurring with
the cdrs. This appears to be an instance where run-time
unification is required, though it is guaranteed that 
the unification will succeed.  Unification in this case provides
a degree of decoupling between successive {\tt p} agents: a {\tt
p} agent can decide to close a switch in the current phase
without having to synchronize with any other agent. It records
its decision in the store through the constraints it has imposed
on its left and right channels. When all agents have imposed
similar constraints, the end of the current phase can be detected
by the agent holding both ends of the chain. 
Thus the bidirectionality of unification is put to good use. 
Note that the third rule in one step closes
a switch for all future rounds. 

This technique can be adapted to \janus\
in two interesting ways.  The first adaptation
serializes the technique but is very efficient and requires no
consing:
\begin{ccprogram}
\agent p(\ldots,L,R) :- p(\ldots,L, \TT M), p(\ldots,M,R)..
\agent p(\ldots,[M|L],\TT R) :- R = [M|R'], p(L,\TT R')..
\agent p(\ldots,L,\TT R) :- R = L..
\end{ccprogram}
The second rule makes the agent wait for its leftmost neighbor to
close its switch for this phase before closing its own and
thereby informing its rightmost neighbor.  The incoming cons
{\tt [M|L]} can be immediately recycled to construct 
{\tt [M|R']}: effectively the {\em same} cons is passed around
from the first agent to the last (and in fact may even be cycled
for further rounds).

The version which does not serialize introduces {\tt s} agents
between every pair of agents on a short circuit.  These 
agents act like buffers enabling the {\tt p} agents to close their
switches independently:
\begin{ccprogram}
\agent p(\ldots,L,R) :- p(\ldots,L,\TT M1),s(M1,M2),p(\ldots,\TT M2,R)..
\agent p(\ldots,\TT L,\TT R) :- L = [M|L'], R = [\TT M|R'], p(\ldots,\TT L',\TT R')..
\agent p(\ldots,L, \TT R) :- R = L..

\agent s([\TT M1|L],[M2|R]) :- M1 = M2, s(L,R)..
\agent s(\TT L,R) :- L = R..
\end{ccprogram}
Note that when a {\tt p} agent terminates, the {\tt s} agent
to its right discovers a teller on its left input channel. It
uses this teller to communicate the channel connecting it to the
{\tt p} agent to its right, and then terminates. As a result,
termination of a {\tt p} agent causes termination of the {\tt
s} agent to its right, but leaves the chain intact. 


A common use of streams of switches is for phased computations where agents
can proceed to the next phase only if the other agents have finished this
phase.  In \herbrand\ languages, each agent can read the rightmost end of
the stream before proceeding.  In \janus\ other means of one to many
communication are necessary as discussed later.

\subsubsection{Incomplete messages}
A major source of simplicity and elegance in \janus\--like
languages is that servers can respond directly to service
requests by communicating on ports embedded in the service
request. This technique is illustrated by the following ``queue-server''
program: 
\begin{ccprogram}
\agent queue(Input):- split(Input, \TT Enq, \TT Deq), match(Enq, Deq)..
\agent split([enqueue(X) | Rest], \TT En, De):- En = [X | En1], split(Rest, \TT En1, De)..
\agent split([dequeue(\TT X) | Rest], En, \TT De):- De = [\TT X | De1], split(Rest, En, \TT De1).. 
\agent match([X | Enq], [\TT Y | Deq]):- Y=X, match(Enq, Deq)..
\end{ccprogram}
These rules purport to define a predicate {\tt queue/1}, which
will receive a sequence of {\tt enqueue} and {\tt dequeue} messages over
time and will be able to respond as if these operations were being
performed on a queue.\footnote{Typically the input stream is obtained by merging
one stream  from each client---the handling of many-to-one communication
schemes is discussed in more detail below.}  Operationally, 
a {\tt queue} agent splits into two agents. One monitors the
input queue and distributes it into two queues, one consisting of
the enqueue requests received (preserving order of arrival) and
the other consisting of dequeue requests received. Each enqueue
request contains the value to be enqueued.
Each dequeue request contains a {\em teller} for a variable, the
asker for which is retained by the agent sending the request.
When an enqueue request arrives, it is communicated via the tell capability directly to
the agent which requested that the dequeue operation be performed.
(Note that the length of the dequeue list can be greater
than the length of the enqueue list, so that the queue may be 
``negative'' for a while.)  If we wish to give clients separate ``enqueue'' and ``dequeue''
capabilities then only the {\tt match/2} program is needed.

{\small\em Implementation-wise, an input list to {\tt queue/1} is split
up into two lists using half of the memory of the input list and freeing
the other half.  As soon as corresponding elements are matched up, pairs
of conses are deallocated.  No consing needs to be done internally since
the messages from the clients provide more than enough memory to
implement the queue.}


\subsection{Recursive doubling}
The parallel  prefix problem is of substantial interest in the area of 
concurrent algorithms (see {e.g.} \cite{kruskal-par-prefix}). We
use it here to  demonstrate how to achieve recursive
doubling by sending askers and tellers as messages, thus
achieving ``transparent forwarding''. 

Given $n$ numbers $a_1, \ldots, a_n$, the problem is to compute the $n$
numbers $b_1, \ldots, b_n$ such that $b_j = a_1 \oplus \ldots
\oplus a_j$ where $\oplus$ is a binary, associative operation.
To be concrete, we shall assume that ``$\oplus$'' is ``$+$'' in
the following. 

To solve the problem, a  chain of $n$ agents is generated at
run-time. That is, each agent ${\tt pp}_i$ shares a variable with
the $(i-1)$st agent (the {\em left}
link for the $i$th agent and the {\em right} link for the $(i-1)$st
agent) and with the $(i+1)$st agent. Each agent ${\tt pp}_i$ also
has access to $a_i$. 

In what follows it is useful to think of computation as proceeding in
cycles---in each ``cycle'' an agent receives one message and sends
another---even though, in reality, there is no central clock and all
agents are executing asynchronously.  Each message is of one of two
types.  First, it may be the constant {\tt <>}.  Alternately, it may be
a three-element array: the {\em value}, the {\em left} connection and
the {\em left2} connection. 

An agent ${\tt pp}_i$ stores locally the following pieces of
information: it stores $a_i$, its  left and 
right connections on the chain, a variable that will be equated to the 
{\em final} value of the number at this agent, and another variable,
which will represent a connection to the agent ``two steps to its right''.
The role of the last variable---which is critical to the
algorithm---is explained below.  

When an agent is enabled initially, it sends a message to the agent
on its right.  In this message, the value component field contains the
number at the agent, and the  left component is a variable that may be
used to receive the messages the agent will send subsequently.
The  left2 component contains a variable which will be constrained
{\em in the next cycle} to a variable that may be used to receive the
messages that the agent {\it to the left} of the agent sending
this message, will send in future.

In each cycle, every agent reads the variable that connects it to
the agent to its left.  Each such variable will be instantiated to a
message of the above type.  The agent computes its new local value
by performing the given operation ($\oplus$) on the value it receives
from the left, and its local value.  It also equates the variable in
the  left field in the message with the variable in the 
left2 field {\em in the message it sent out in the previous cycle}.
It recurs with its new left connection being the variable in the 
left2 component field in the message it just read.  

If the agent reads a {\tt <>} message then it sends {\tt <>} 
on the other two connections that it has locally, declares that
the value it was  supposed to compute is its current value and terminates.  

\begin{ccprogram}
\agent pp(In, Out):- spawn(In, <0,<>,<>{}>, \TT Right, Out), sink(Right)..

\agent spawn([N | Rest], Left, Right, \TT Out):- number(N) | 
       pp(N, Left, \TT Right1, \TT Right2, \TT Final), 
       Out = [Final | Out1],
       spawn(Rest, <N, Right1, Right2>, Right, \TT Out1)..
\agent spawn(<>, Left, \TT Right, \TT Out):- Right = Left, Out = <>..

\agent pp(N, <>, \TT Right, \TT Right2, \TT Final):- Final = N, Right = <>, Right2 = <>..
\agent pp(N, <M, Left2, Left>, \TT Right, \TT Right2, Final):- 
    pp(M + N, Left, \TT Right1, \TT Right21, Final), 
    Right = <M + N, Right1, Right21>, Right2 = Left2..
\end{ccprogram}

Note that an agent does not {\em use} the value of the variables {\tt
Left} and {\tt Right2}: it merely serves to equate them so that {\em
some other agents} can directly communicate in the next round.
This simple connection pattern achieves recursive doubling: in the
$i$th cycle an agent receives messages from another agent $2^i$
steps away in the initial chain.  Transparent forwarding is used
to obtain the desired effect. 

\MetaNote{Point out that \cite{hillis-data} has a number of algorithms which
utilize recursive doubling and which can be used in this setting. However, to do so we
may need listeners.}

\section{Computing with arrays} \label{arrays}
We now demonstrate the flexibility of the richer  \janus\ array constraints. 

A major use of arrays is as a random-access data-structure
internal to a process, which can be updated sequentially. This is
illustrated by the following program for the ``Dutch National
Flag'' problem \cite{Dijkstra}:\footnote{The problem is:
given an array of colors red, white and blue rearrange it in one
pass so that all the red tokens occur first, and are followed by
all the white tokens, followed by the blue ones.}
\begin{ccprogram}
\agent dnf(Cols, Sorted):- dnf(Cols, 0, \SIZE{Cols}-1, \SIZE{Cols}-1, Sorted)..
\agent dnf(In, R, W, B, \TT Out):-  R > W |  Out=In..
\agent dnf(In, R, W, B, Out):-  R \leq W, In.W=red | %
	 dnf(In[R \to In.W, W \to In.R], R+1, W, B, Out)..
\agent dnf(In, R, W, B, Out):-  R \leq W, In.W=white | %  
	 dnf(In, R, W-1, B, Out)..
\agent dnf(In, R, W, B, Out):-  R \leq W, In.W=blue | %
	 dnf(In[B \to In.W, W \to In.B], R, W-1, B-1, Out)..
\end{ccprogram}
The above program is almost a direct translation of the
sequential program in \cite{Dijkstra}. 
Note the idiom for swapping two elements of the array, and recall
that assignments can be done in place. The code produced by a
\janus\ compiler for this program should not be very different
from code produced for the corresponding program in an
imperative, sequential language.

In some cases the implementation can even update disjoint
portions of the array in parallel. This is illustrated by quicksort:
\begin{ccprogram}
\agent	q(A, \TT B):- \SIZE{A} \le 1 | B=A..
\agent	q(A, \TT B):- \SIZE{A} \gt 1 | split(A, \TT K, \TT E), sort(E, K, \TT B)..
 
\agent	sort(E, K, B):-   {\em \%\ Suspends\ until\ E\ is\ an\ array.}
	0 \lt K, K \lt \SIZE{E}-1 | {\em \%\ and\ it\ is\ not\ already\ sorted.}
		q(E[0{..}K], \TT C), q(E[(K+1){..}(\SIZE{E}-1)], \TT D), %
		concatenate(C,D,B)..
\agent sort(E, 0, \TT B) :- B = E..
\agent sort(E, K, \TT B) :- \SIZE{E}-1 = K | B = E..
 
\agent concatenate(C, D, \TT B):- {\em \%\ Suspends\ until\ C\ and\ D\ are\ arrays.}
		B=C \circ D..

\agent split(A, K, Result):- split(A, 1, \SIZE{A}-1, K, Result)..
\agent split(A, I, Big, K, Result):- A.0 \leq A.I, I \lt Big | 
		split(A, I+1, Big, K, Result)..
\agent	split(A, I, Big, K, Result):- A.0 \geq A.I, I \lt Big | 
		split(A[Big \to A.I, I \to A.Big ], I, Big-1, K, Result)..
\agent	split(A, I, Big, \TT K, \TT Result):- A.0 \leq A.I, I = Big | 
		Result=A[0 \to A.I, I \to A.0], K=I..
\agent	split(A, I, Big, \TT K, \TT Result):- A.0 \geq A.I, I = Big | 
		Result=A[0 \to A.(I-1), (I-1) \to A.0], K=I-1..
\end{ccprogram}
Essentially, {\tt split} pivots its input array {\tt A} around
{\tt A.0}, in place. The two halves of the array can then be
sorted recursively in place, and the results combined.

{\tt sort} and {\tt concatenate} are introduced as agents rather than coding
them inline because they read arrays that are produced concurrently with
their spawning.  If, for example, {\tt sort} were opened in the second rule
of {\tt q} then the array subsequence expressions would be correct only if
{\tt split} always produces an array of the right size as its third argument.
Rather than relying upon a sophisticated compiler analysis to discover that
this is indeed the case, we fold the consumer of the array into a {\tt sort}
agent which suspends until it receives an array.  

{\small\em Using the above techniques for representing arrays, a
compiler can generate code which will sort the input array in
place: {\tt split} will take its input array and do its updates
in place to produce the pivoted array; this array is split into
two smaller pieces (within {\tt sort}) in constant time, these
two pieces are recursively sorted independently, in place, and
then the resulting pieces are joined together (in constant time
since the pieces are contiguous) to create the final result.  }

%%(Actually we may define parallel updates, too, using bounded universal quantification,
%%provided that the parallel updates can be shown to be non-interfering, at compile-time.)

%Another use is in mapping over an array to produce another array.
%Actually this is  done better using array/3 to create pairs of
%asker/teller arrays.  
%\MetaNote{Discuss the above.}
%Mapping over an array of channels, sending a message on each and generating
%a new tuple which contains the tails.
%Generating an array of a length known at run-time and sharing it between 
%two agents. 

\section{Many to one communication using bags}

The communication mechanism discussed in \janus\ hitherto has focussed
on point-to-point directional communication channels.  An agent may have
a fixed number of such channels.  Such communication schemes are too
simplistic, however, to deal elegantly with many to one communication. 
Consider for example a situation in which an a priori unbounded number
of clients may seek service from a server. 

The server will have read access to a bag.  It will wait for requests by
asking if its bag is {\tt element(Request,Bag')}.  It then responds to
the {\tt Request} and recurs with the {\tt Bag'}.  A client has a teller
to an element of the bag, say {\tt X}.  It sends a request by telling
{\tt X=bag(Request,X')} and using {\tt \TT X'} for subsequent requests. 
It can split its access {\tt X} to the server by telling {\tt
X=bag(X1,X2)} thereby creating the two accesses {\tt X1} and {\tt X2}. 
A client drops bag reference by posting constraint {\tt X=\{\}}. 

Consider the simple bank account as an example of how to instantiate
this communication scheme:
\begin{ccprogram}
\agent	account\_receptionist(\{\}, State)..
\agent	account\_receptionist(element(Req, Rest), State):- 
	    account(Req, State, \TT State1), 
	    account\_receptionist(Rest, State1)..

\agent	account(balance(\TT Value), Bal, \TT NewBal):-  integer(Bal) | 
	NewBal = Bal, Value = Bal..
\agent	account(withdraw(Amt, \TT Ok), Bal, \TT NewBal):- Amt \leq Bal | 
	Ok=ok, NewBal=Bal-Amt..
\agent	account(withdraw(Amt, \TT Ok), Bal, \TT NewBal):- Amt > Bal | 
	Ok=nope, NewBal=Bal..
\agent	account(deposit(Amt), Bal, \TT NewBal):- NewBal=Bal+Amt..
\end{ccprogram}

The guard {\tt integer(Bal)} was added to the first rule of {\tt
account} to indicate that {\tt Bal} is forced and can therefore occur
multiple times.  We expect a good compiler based upon abstract
interpretation can compile away this test. 

\begin{note}

We are considering relaxing our syntactic restrictions to allow Asks of
the form $\tt element(t_1, Y)$, where $\tt t_1$ can be a term.  Some interesting
programs can be written clearly and concisely using these more general
ask constraints, in a fashion reminescent of {\em conditional critical regions} in 
languages based on imperative concurrency \cite{ben-ari}.


For example, {\tt account} can be written to suspend a withdrawal until
such time as, if ever, there is enough money in the account to service
it:
\begin{ccprogram}
\agent	account(element(balance(\TT Value), Rest), Balance):- integer(Balance) | 
	Value = Balance, account(Rest, Balance)..
\agent	account(element(withdraw(Amt), Rest), Balance):- Amt \leq Balance | 
	account(Rest, Balance-Amt)..
\agent	account(element(deposit(Amt), Rest), Balance):-  
		account(Rest, Balance+Amt)..
\agent	account(\{\}, Balance)..
\end{ccprogram}
The point to note is that a {\em withdrawal} message is not even
``accepted'' (removed from the input bag) until it is possible to
service it.  However note that the above code does not enforce first
come first served policy on debits.

Similarly, one can implement stacks which block excessive pop requests
until someo agent does a push:
\begin{ccprogram}
\agent	stack(\{\}, Value)..
\agent	stack(element(pop(\TT Value), Rest), [V | State]):- Value=V, stack(Rest, State)..
\agent	stack(element(push(Value), Rest), State):- stack(Rest, [Value | State])..
\end{ccprogram}

While quite convenient, allowing Asks of the form 
$\tt element(t_1,Y)$, where $t_1$ is a non-variable term, introduces
complexities in the implementations of bags.  The restricted use of bags
(where $\tt t_1$ is a variable whose other occurrence is in the body) can be
implemented efficiently as a distributed queue.  We are uncertain
whether the added clarity and conciseness of some programs due to
relaxing this restriction is worth the apparent implementational
complexity.  This is a topic of ongoing research. 
\end{note}

%\MetaNote{Fairness is not required by the language, since it is not
%finitely observable. However, for an implementation to be useful, it
%should make an attempt to ensure bag-fairness and and-fairness.}

\subsection{Merging techniques}
\MetaNote{May say something about how to implement various sorts of 
merges using bags.}

\subsection{Mutual exclusion}
\MetaNote{Work out various schemes. Many communicating with one, 
essentially tokens with answer variables. Serializing access.
After accepting a message <request, Req, Return>, Req is equated 
with a structure which contains the resource, and a variable for its 
return.  When the value is returned by the agent using the resource, 
the serializer goes back to accepting messages from others. It may be
possible to build in some prioritization schemes which ``delay'' this 
process till later. 

This also illustrates a randezvous style of communication. 

As an illustration, deal with dining philosophers.
}

\subsection{Single exclusion}
\MetaNote{First illustrate single round, and then extend it for multiple
rounds. Also, first illustrate how it can be done for the atomic languages,
and then how it can be done here. Hence, this is part of another general
theme which points out how particular atomic Herbrand idioms can be 
re-expressed in Janus. 

Remember that this is dynamic single-exclusion.  Can use the various
merge-tree ideas that we developed for example when Ueda was here. 

Investigate tradeoffs in expressiveness/implementation 
efficiency of splay merge-trees vs. bags on a multi-threaded 
single-node.
}

\section{One to many communication: distribute and copy}
Consider the problem of broadcasting information received down
one channel to a number of other agents.  This can be dealt with
quite straightforwardly by defining a predicate {\tt
distribute/3}.  The first argument is the channel on which
communication is received, the second receives the messages
received on the first argument, and the third is an array of
channels which receive {\em copies} (without embedded tell
capabilities) of the messages.  We call these channels which
receive copies {\em listeners} of the channel being copied.
Elsewhere we shall discuss the possibility of elevating listeners
to become a part of the language.

Intuitively, the idea is clear. For every possible message that
an agent can receive on its input channel, it should have a
clause which suspends until that message is received and then
copies it to the output streams.

\begin{ccprogram}
\agent distribute(X,Y,Z) :- distribute1(X,Y,\TT Z1),distribute(Z1,Z)..
\agent distribute(X,<\TT Y>) :- Y = X..
\agent distribute(X,Z) :- \SIZE{Z} \gt 1 |
	distribute1(X,\TT X1,\TT X2),distribute(X1,Z[0{..}(\SIZE{Z}/2-1)]),distribute(X1,Z[\SIZE{Z}/2{..}(\SIZE{Z}-1)])..
\agent distribute1(X,\TT Y,\TT Z) :- scalar(X) | Y = X, Z = X.. {\em \%\ X\ is\ a\ constant,\ number,\ or\ char,\ etc.}
\agent distribute1(X,\TT Y,\TT Z) :- array(X) | %
	array(\SIZE{X},\TT Y1,\TT Y), array(\SIZE{X},\TT Z1,\TT Z), distribute\_array(X,Y1,Z1)..
\agent distribute1(element(X1,X),\TT Y,\TT Z) :- 
	Y = bag(Y1,Y2), Z = bag(Z1,Z2), %
	distribute1(X1,\TT Y1,\TT Z1),distribute1(X,\TT Y2,\TT Z2)..
\agent distribute1(\TT X,\TT Y,Z) :- Y = \TT X0, distribute1(X0,\TT X,Z)..

\agent distribute\_array(<X>,<Y>,<Z>) :- distribute(X,Y,Z)..
\agent distribute\_array(X,Y,Z) :- \SIZE{X} \gt 1 |
	distribute\_array(X[0{..}(\SIZE{X}/2-1)],Y[0{..}(\SIZE{X}/2-1)],Z[0{..}(\SIZE{X}/2-1)]),
	distribute\_array(X[\SIZE{X}/2{..}(\SIZE{X}-1)],Y[\SIZE{X}/2{..}(\SIZE{X}-1)],Z[\SIZE{X}/2{..}(\SIZE{X}-1)])..
\end{ccprogram}

Note that if a teller arrives on the first argument it is forwarded to
the second and the third argument will get copies of any value the
teller later receives.  To achieve this, in the last {\tt distribute1/3
rule} we send the teller for a {\em new} communication channel {\tt \TT Z}
to the selected stream, and then recur with {\tt Z} as the new ``input''
stream for the distributor. In this way the role of the asker and teller
may ping-pong between the first two arguments of the distributor.

Note that this program is syntactically determinate. At run-time,
for any call, at most one clause will be applicable. In
\cite{janus} we discuss how the idiom represented by the above
program may often be used in-line in various algorithms. 

The {\tt distribute1} rule for arrays is an example of {\em array
mapping}.  The result of the mapping is returned immediately as the
third argument of an {\tt array/3} constraint.  The second argument is
then an array of tellers for the corresponding positions in the array of
askers.  The array of tellers is then ``filled in'' in parallel.

\subsection{Techniques to circumvent sharing}
At the same time, it is important to be aware that there are some
programming idioms in (atomic and eventual) \cc\ languages which
cannot directly be achieved in \janus.  For example, it is not
possible in \janus\ to share  a data-structure (e.g.,
symbol-table)  between multiple agents in such a way that all
of them cooperate in filling it out.  The basic problem is that there
does not seem to be a simple way to guarantee that multiple agents
having access to the same variable will produce consistent information
about that variable.  On the other hand, it is possible to
encapsulate the data-structure in an agent and have all other
agents communicate with this ``guardian''. If the data-structure
is recursive, a corresponding tree of agents may be generated,
thus mitigating some of the serializing aspect of guardians.
This is indeed the way computations are organized in conventional
programming languages---the point is merely that within \cc\
languages it is sometimes possible to give very elegant
presentations which do not require explicit  synchronization
conditions at the language level. However, by going to \janus\
this flexibility is lost.

%\MetaNote{May give example here of the bcp code that will
%annoyingly not work. But we can use a ``variable  monitor'' to
%make it work.} 

Sometimes the straightforward way of writing a  dataflow program
does not yield a syntactically legal \janus\ program; however with a little
tweaking it may be possible to get such a program.  For example
the straightforward program for generating the first {\tt (Count+2)}
Fibonacci numbers has three occurrences of {\tt Rest} in the second rule.

\begin{ccprogram}
\agent fib(Seq, Count) :- fibb([0,1 |Seq], Count)..

\agent fibb([X1, X2 | \TT Rest], Count) :- %
 Count \gt 0 | Rest= [X1+X2 | \TT Rest1], fibb([X2 | Rest], Count-1)..
\agent fibb([X1, X2 | \TT Rest], 0) :- Rest = []..
\end{ccprogram}

On the other hand, the following trivial variation is acceptable
\janus: 
\begin{ccprogram}
\agent fib(Seq, Count) :- fibb([0,1 |Seq], Count)..

\agent fibb([X1, X2 | \TT Rest], Count) :- Count > 0 | fibb([X2, X1+X2 | \TT Rest1], Count-1), Rest= [X1+X2 | Rest1]..
\agent fibb([X1, X2 | \TT Rest], 0) :- Rest = []..
\end{ccprogram}

The rule will implicitly suspend until
{\tt X1} and {\tt X2} are forced to be numbers; hence they can occur more than twice.

%The ``demand-driven'' version of the program is:
%
%\begin{ccprogram}
%\agent fib([\TT Zero | Rest]) :- Zero = 0, fib0(Rest)..
%\agent fib0([\TT One | Rest]) :- One = 1, fib1([0, 1 | Rest])..
%\agent fib1([X1, X2, \TT X3 | Rest]) :- X3 = X1 + X2, fib1([X2, X3 | Rest])..
%\end{ccprogram}
%
%Various other, more cons-efficient versions of this program can
%be written, though it is not clear that a reasonable compiler
%will not be able to compile this into cons-free code. (Only the
%producer of the ``demands'' would need to cons to produce the stream.)

The following is how list intersection can be written as a \herbrand\ program using 
difference-lists. 

\begin{ccprogram}
\agent intersect(L1, L2, L) :- intersect1(L1, L2, L, [])..

\agent intersect1([X |L1], L2, F, T) :- %
	member\_add(X, L2, F, M), %
        intersect1(L1, L2, M, T)..
\agent intersect1([], L2, F, T) :- F = T..

\agent member\_add(X, [], F, T) :- %
	F = T..
\agent member\_add(X, [X1|L], F, T) :- %
               X \neq X1 | %
               member\_add(X, L, F, T).. 
\agent member\_add(X, [X|L], F, T) :- %
               F = [X|T]..
\end{ccprogram}

The difficulty with converting this program to \janus\ is that {\tt L2}
is shared by the {\tt member\_add} and recursive {\tt intersect1} agents
in the first rule of {\tt intersect1}.  One \janus\ programming
technique is to pipeline the computation, so that the shared list is
copied as it is being read:
\begin{ccprogram}
\agent intersect(L1, L2, L) :- intersect1(L1, L2, L, [])..

\agent intersect1([X |L1], L2, F, T) :- %
	member\_add(X, L2, F, M, \TT L2'), %
        intersect1(L1, L2', \TT M, T)..
\agent intersect1([], L2, \TT F, T) :- F = T..

\agent member\_add(X, [], \TT F, T, \TT Out) :- %
	F = T, Out = []..
\agent member\_add(X, [X1|L], F, T, \TT Out) :- %
               X \neq X1 | Out = [X1 | Out'], %
               member\_add(X, L, F, T, \TT Out').. 
\agent member\_add(X, [X|L], \TT F, T, \TT Out) :- %
               F = [X|T], Out = [X | L]..
\end{ccprogram}
{\small\em The implementation need not do any copying if the {\tt
member\_add} and {\tt intersect1} agents are executing in same address
space.  Essentially the data structure is being shared over time but
only a single agent has access to any component at any one time. This
serialization of access to a data structure is quite general, and the
structure can contain tellers, unlike solutions which require copying.
}

As we have seen, \herbrand\ programs naturally written with shared data
structures can be rewritten in \janus\ either by explicitly copying the
data (e.g.\ using {\tt distribute/3}), by encapsulating the data in
recurrent agents, or by pipelining or serializing the access.  

%%Two
%%programming techniques in the atomic \cc\ languages: duplex channels and
%%single exclusion are not available in \janus\ as is the case for all the
%%languages based upon eventual publication (e.g.\ Parlog, FGHC, Strand).

%%\MetaNote{Be a bit more explicit in the above.}

\subsection{Implementing balanced search trees}
Binary search trees (bst) \cite{AHU} are a fundamental data-structure
which can be
used to implement many kinds of operations in a simple way.  
One of the major problems with this data-structure is how to keep
the tree balanced.  Various more or less complicated schemes,
such as  $(2:3)$ trees, AVL trees, etc.\ have been proposed
\cite{AHU}.  However, a very interesting result was obtained
recently by \cite{splay} (see \cite{tarjan-turing} for an
overview). It was shown that by performing local
``splay'' operations on a bst, it was possible to guarantee that
the amortized cost over a sequence of $N$ operations on the tree 
would be $O(N\ \log(N))$.  These trees are an example of an
interesting class of data-structures called ``self-adjusting
data-structures''. 

Here we present a program fragment which implements accessing an item in
a bst and adjusting the tree in the process.  We use the notion of {\em
difference-bsts}. There are two types of difference-bsts, a left one and
a right one. The left one is a pair {\tt T-L} where {\tt T} is a bst and
{\tt L} is the {\em right} son of the node with the largest value in
{\tt T}. The right one is of the form {\tt T-R} where {\tt T} is a bst
and {\tt R} is the {\em left} son of the node with the smallest value in
{\tt T}. An empty bst is represented by a variable. Hence {\tt L-L}
denotes the empty left (as well as right) difference bst.

As discussed in \cite{splay}, we start with a notion of a
left {\em fragment} and a right  fragment of the new bst to be
constructed. Initially, the two fragments are empty. 
\begin{ccprogram}
\agent bst(Op, Item, Tree, NewTree):-  bst(Op, Item, L-\TT L, Tree, R-\TT R, NewTree)..
\end{ccprogram}

We now consider the base cases. We represent the empty tree as a teller;
and every other tree as a three-element array . Hence, it is possible
for a clause to match a bst with an asker for a variable X, and in the
body bind the teller for X with {\tt null} just in case the bst is
empty. On the other hand, if the {\tt Item} is found at the root, then
the call terminates, with the new tree being set up appropriately.

Thus the base clauses are:
\begin{ccprogram}
\agent  bst(access(\TT Val), Item, L, nil, R, \TT New):-  New = nil, Val = null..
\agent  bst(access(\TT Val), Item, Left-\TT LT, <Item, A, B>, Right-\TT RT, \TT New):-
       Val  = true, LT = A, RT = B, New = <Item, Left, Right>..
\end{ccprogram}

We now consider the zig case, namely that we have reached a
node such that the required {\tt Item} is either to the left of
the current node and the current node is a leaf, or the
required item is the left son of the current node. Depending
upon  the operation requested, the appropriate action is taken: 
\begin{ccprogram}
\agent  bst(access(\TT Val), Item, Left-\TT LT, <X, null, B>, Right-\TT RT, \TT New):-Item < X | 
   LT = null, RT = B, New = <X, Left, Right>, Val = null..
\agent  bst(Op, Item, Left, <X, <Item, A1, A2>, B>, R-\TT RT, New):- Item < X | 
      RT = <X, NR, B>,  bst(Op, Item, Left, <Item, A1, A2>, R-\TT NR, New)..
\end{ccprogram}
The recursive cases are straightforward. First the Zig-Zig case:
\begin{ccprogram}
\agent   bst(Op, Item, Left, <X, <Y, Z, B>, C>,  R-\TT RT, New):- Item < X, Item < Y | 
     RT = <Y, NR, <X, B, C>{}>, bst(Op, Item, Left, Z, R-\TT NR, New)..
\end{ccprogram}
Now the Zig-Zag case:
\begin{ccprogram}
\agent   bst(Op, Item, L-\TT LT, <X, <Y, A, Z>, C>,  R-\TT RT, New):- Item < X, Y < Item | 
    LT = <Y, A, NL>, RT = <X, NR, C>, bst(Op,Item, L-\TT NL, Z, R-NR, New)..
\end{ccprogram}

The symmetric cases for the right sons of the current node
are straightforward too. The first two are base cases, 
the third is the zag-zag case and the last the zag-zig case. 
\begin{ccprogram}
\agent   bst(access(Value), Item, Left-\TT LT, <X, B, nil>, Right-\TT RT,  \TT New):- X < Item | 
     New = <X, Left, Right>, LT = B, RT = nil..
\agent  bst(Op, Item, L-\TT LT, <X, B, <Item, A1, A2>{}>, Right, New):- X < Item | 
    LT = <X, B, NL>,  bst(Op, Item, L-\TT NL, <Item, A1, A2>, Right, New)..
\agent bst(Op, Item, L-\TT LT, <X, C, <Y, B, Z>{}>, Right, New):- X < Item, Y < Item | 
     LT = <Y, <X, C, B>, NL>,   bst(Op, Item, L-\TT NL, Z, Right, New)..
\agent bst(Op, Item, L-\TT LT, <X, A, <Y, Z, C>{}>, R-\TT RT, New):- X < Item , Item < Y | 
    LT = <X, A, NL>, RT = <Y, NR, C>,    bst(Op, Item, L-\TT NL, Z, R-\TT NR, New)..
\end{ccprogram}

{\small\em A very important property of the above program is that
all the assignments can be done in place, and no consing needs to
be done.  In other words, each rule is memory conservative.}

\begin{hist-note}
A complete version of this program in Prolog first appeared in a note
that one of us (Vijay) sent to the Prolog Digest in 1987. It is rather
remarkable that that program, even then, was more or less a \janus\
program.
\end{hist-note}

\section{Additional remarks}

Note that while it is possible for a group of \janus\ agents to create
cyclic structures at run-time (e.g. {\tt X=<X>}),
such structures once created can never be
referenced from the outside. This is an advantage that \janus\ holds
over a language such as \strand\ which would allow the creation of such
loops, causing the system to enter an infinite loop when it attempts to
read such a structure. (Indeed, Strand may even loop if a user happens to 
write code that executes {\tt X=X} at run-time!)

It turns out that within a single address space Janus already
encapsulates memory and allows the communication of memory. For example,
if {\tt b} requires a block of 8 words to service a particular request,
then that memory can be provided by a client {\tt a} as part of the
request.

\begin{ccprogram}
\agent a(\TT X),b(X)..

\agent a(\TT B) :- %
	B = please\_perform\_service\_x(array(8,0),\TT
Reply,NextB),a1(Reply),a(\TT  NextB)..

\agent b(please\_perform\_service\_x(Memory,Reply,Next)) :- \SIZE{Memory} \gt 7 | %
	compute(Memory,Reply), b(Next)..
\end{ccprogram}

We are exploring a class of \janus\ programs in which no memory is
allocated at run time.\footnote{In general, this may require the ability
to reuse the memory of data structures as process/agent records.} Rather
memory gets passed around from the initial query. These computations
start with some hunk of memory and pass it around to get work down.
This could be useful inside embedded systems (toys, missiles, watches,
whatever) where you want the program to run for years without a risk
that it'll ``run out of memory''.

\section{Summary}

The \janus\ restriction to two variable occurrences rarely interferes
with the common concurrent logic programming techniques.  The benefits
of failure-freeness and more efficient implementation typically outweigh
the relatively minor difficulties in fitting one's programs to the
syntactic restrictions of \janus.  We present various programming
techniques for dealing with the inability in \janus\ to directly share
data structures.  We have found that many programs are ``memory
conservative'' in \janus, and many more can be re-written to be so.

\janus\ introduces arrays to the distributed constraint framework.  In this paper
we have illustrated common uses of these data structures.  Many array
programs can be compiled to work ``in-place'' and should be as efficient
as those written in conventional imperative languages.  In many cases,
the array can be modified in place in parallel.  Unlike conventional
imperative programming such programs run in \janus\ with an assurance
that there are no synchronization bugs in these ``simultaneous''
accesses.

\janus\ also introduces bags which provide a principled and efficient 
means of programming many-to-one communication that avoids much of the
clumsiness and ad hocness of previous solutions.  A less restricted use
of bags provides excellent support for object-oriented programming.

\paragraph{Acknowledgements.}
The research underlying this paper has benefitted tremendously from
many, many discussions with Mark Miller and Eric Dean Tribble. We also
thank Danny Bobrow, Seif Haridi, Fernando Pereira, Saumya Debray, Udi
Shapiro, Bill Kornfeld and Julie Basu for discussions and comments.

\newpage
{\footnotesize
\bibliography{/net/tigger/tigger/saraswat/bib/master-0}}
\bibliographystyle{alpha}

\end{document}

