%% 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. %%<{}> 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 }$ 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 = }$ 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, , 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, , \TT Right, \TT Right2, Final):- pp(M + N, Left, \TT Right1, \TT Right21, Final), Right = , 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 , 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(,,) :- 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, , Right-\TT RT, \TT New):- Val = true, LT = A, RT = B, New = .. \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, , Right-\TT RT, \TT New):-Item < X | LT = null, RT = B, New = , Val = null.. \agent bst(Op, Item, Left, , B>, R-\TT RT, New):- Item < X | RT = , bst(Op, Item, Left, , R-\TT NR, New).. \end{ccprogram} The recursive cases are straightforward. First the Zig-Zig case: \begin{ccprogram} \agent bst(Op, Item, Left, , C>, R-\TT RT, New):- Item < X, Item < Y | RT = {}>, 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, , C>, R-\TT RT, New):- Item < X, Y < Item | LT = , RT = , 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, , Right-\TT RT, \TT New):- X < Item | New = , LT = B, RT = nil.. \agent bst(Op, Item, L-\TT LT, {}>, Right, New):- X < Item | LT = , bst(Op, Item, L-\TT NL, , Right, New).. \agent bst(Op, Item, L-\TT LT, {}>, Right, New):- X < Item, Y < Item | LT = , NL>, bst(Op, Item, L-\TT NL, Z, Right, New).. \agent bst(Op, Item, L-\TT LT, {}>, R-\TT RT, New):- X < Item , Item < Y | LT = , RT = , 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=}), 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}