% File: locality2.tex
% Status: Last modification by Florian on 26-DEC-90
%
\section{Modeling Objects in a Partitioned Store}
\label{sec:objects}

As argued in \cite{OBBT89}, major properties of objects (without
locality control) can be represented by references when they are
combined with a rich set of value constructors. In a functional
language, references can be introduced by the following set of
primitives: 
\begin{program}\kwd{new}($v$) \=\kill
\kwd{new}($v$) \>{\it reference creation,}\\
!$r$  \>{\it de-referencing,}\\
$r$:=$v$ \>{\it assignment.}
\end{program}%
{\tt \kwd{new}($v$)} creates a new reference and assigns the value $v$
to it. {\tt !$r$} returns the value previously assigned to the
reference $r$.   {\tt $r$:=$v$} assigns a new value $v$ to a given
reference $r$ (discarding the value previously assigned to $r$). In a
database context, these operations correspond respectively to the
creation of  an object with identity, retrieving the value of an
object, and changing the associated value ({\em attribute\/} or {\em
state\/}) of an object without affecting its identity. See
\cite{Ohor90} for a more detailed discussion of their relevance for
database programming and a formal account of these primitives in a
purely functional framework.
 
The following examples (taken from \cite{Ohor90}) illustrate the
(standard) semantics of references in our model that are formally
captured by the reduction rules in section~\ref{sec:sound}. The
invocation of \kwd{new} such as 
\begin{program} 
David = \kwd{new}([Name="David", Age= 25]);
\end{program}%
will create a reference whose associated value is the record {\tt
[Name="David", Age=25]} and can naturally be regarded as an object with 
identity which has a {\tt Name} and an {\tt Age} attribute. 
Sharing and mutability are also represented by references. 
If we define the following two person objects from {\tt David}:
\begin{program}
Jessica = \kwd{new}([Name="Jessica", Age = 2, Father = David]);\\
Frederick = \kwd{new}([Name="Frederick", Age = 3, Father = David]);
\end{program}%
then {\tt Jessica} and {\tt Frederick} {\em share\/} the same person
{\tt David} as the value of the {\tt Father} field and the expression {\tt
\kwd{eq}((!Jessica).Father,(!Frederic).Father)} is {\tt true}. An
update to the object {\tt David} as 
\begin{program}
  David := \kwd{modify}(!David, Age, (!David).Age + 1);
\end{program}%
is reflected in the {\tt Father} as seen from both {\tt Jessica} and {\tt
Frederick}, where {\tt \kwd{modify}($r$,$f$,$v$)} is the operation that
creates a new record form the record $r$
by modifying the field $f$ with the value $v$. After the above
statement, both {\tt (!((!Jessica).Father)).Age} and {\tt
(!((!Frederick).Father)).Age} are evaluated to {\tt 26}.

By virtue of these properties references capture the central features of
objects but they also introduce strong explicit data dependencies among
objects. In the above examples, the objects {\tt Jessica} and {\tt
Frederick} {\em depend\/} on the object {\tt David} and are meaningless
unless {\tt David} exists. Furthermore, it is possible to introduce new
dependencies by creating copies of the {\tt Father} attribute of {\tt
Frederick} or {\tt Jessica}.  Additional complications arise if we want
to include functions (methods) within objects, since functions induce
implicit dependencies to objects through their variable binding
mechanism. It should be clear that in the context of large, shared and
long lived data structures the control of such dynamic dependencies
becomes crucial, e.g.\ to support optimized data placement and efficient
garbage collection.

The challenge is now to introduce a mechanism to partition the space of
objects into suitably selected subspaces and to control the generation
and propagation of cross-references between these subspaces.  For this
purpose, we introduce the notion of {\em repositories\/} with a
predefined dependency constraint. Our primary intuition behind
repositories is that they correspond to partitions of a persistent
store.  Here, we simply assume that they are abstract named entities. 
It is not hard to add persistence to our system by using the techniques
developed in persistent programming languages \cite{ABCCM83,NapierRep}
(reachability-based) or in modular database programming languages
\cite{Schm77,SEM88,MaSc89} (statically declared).

We assume that there is a fixed set ${\cal R}$ of repository names
(ranged over by $R$).  We require that references are bound at
creation-time to a repository as in:
\begin{program}
  \kwd{new}($R$,$M$)
\end{program}%
where $R$ is the repository name to which the reference is bound.  This
binding between a reference and its repository is immutable, i.e.\
objects possess no mobility. To model the intended constraint on the
dependencies among repositories, we associate to each repository $R$ a
set $\mu(R)$ of repositories, called the {\em reachability set\/} of $R$.
This is to impose the constraint that if a reference in a repository $R$
refers to a value containing other references then they must be in some
repositories in the reachability set $\mu(R)$. This restriction on
cross-references is deliberately chosen to be ``shallow'', i.e.\ there
is no explicit restriction on the set of repositories that can be
reached transitively via several references. This decision is in the
spirit of modular systems where every component should only introduce
local constraints on the overall system structure. With this mechanism
at hand, we are able to abstract from the multiplicity of dynamic
reference creation and propagation operations in a persistent system
and to view the database at the granularity of repositories and their
reachability sets. Section~\ref{sec:example} will elaborate on the
impact of this kind of compile-time information on databases with
a structured object store.

As a very simple example, suppose we have repositories {\tt Permanent}
and {\tt Temporary} with the reachability sets $\mu(\code{Permanent}) =
\emptyset$ and $\mu(\code{Temporary}) = \{\code{Permanent}\}$. This
imposes the constraint that references in the repository {\tt Temporary}
can refer to references in {\tt Permanent} as well as {\tt Temporary}
while references in {\tt Permanent} can only refer to references in {\tt
Permanent}. Then 
\begin{program}
helen = \kwd{new}(Permanent, [Name = "Helen", Age = 35]);\\
john = \kwd{new}(Temporary, [Name = "John", Age = 41]);\\
joe = \kwd{new}(Permanent, [Name = "Joe", Age = 29, Boss = helen]);\\
susan = \kwd{new}(Temporary, [Name = "Susan", Age = 18, Boss = helen]);
\end{program}%
are all legal but
\begin{program}
mary = \kwd{new}(Permanent, [Name = "Joe", Age = 29, Boss = john]);
\end{program}%
violates the constraint and we expect the type system to detect the
violation and to reject this statement.

We integrate these operations for references in a typed functional
language with labeled records and lists as defined by the following
syntax: 
\begin{program}
$M$ \=$::=$ ($c$:$\tau$)\vbar$x$\vbar$\lambda x:\tau$.$M$\vbar$M$($M$)\\
\>\vbar\record{$l$=$M$,$\ldots$,$l$=$M$}\vbar$M$.$l$\vbar\kwd{modify}($M$,$l$,$M$)\\
\>\vbar(nil:$\tau$)\vbar\kwd{insert}($M$,$M$)%
\vbar\kwd{head}($M$)\vbar\kwd{tail}($M$)\\
\>\vbar\kwd{new}($R$,$M$:$\tau$)\vbar\asgn{$M$}{$M$}\vbar\deref{$M$}
\end{program}%
where $\tau$ stands for types which will be discussed in the next
section. {\tt ($c$:$\tau$)} stands for typed constants, {\tt
\record{$l$=$M$,$\ldots$,$l$=$M$}} is the syntax for labeled records as
we have already seen in the above examples. $M$.$l$ is field selection
from a record, {\tt \kwd{modify}($M_1$,$l$,$M_2$)} is field
modification (or field update) as already explained. {\tt (nil:$\tau$)}
is the empty list of type $\tau$. \kwd{head} and \kwd{tail} are
standard primitives for lists (coresponding, respectively, to $car$ and
$cdr$ in Lisp). The type specification in {\tt
\kwd{new}($R$,$M$:$\tau$)} is needed to show the soundness of the type
system.  Since $\tau$ is always the same as the type of $M$, this can
be automatically inserted by the type system and can therefore be
safely omitted.

With appropriate syntactic shorthand, this language can serve as a
language to define and manipulate objects. We write {\tt
$x_1$=$M_1$;$M_2$} as a shorthand for {\tt ($\lambda
x_1$:$\tau_1$.$M_2$)($M_1$)} where $\tau$ is the type of $M_1$ and write
{\tt $x_1$=$M_1$;$\cdots$;$x_n$=$M_n$} as a shorthand for {\tt
$x_1$=$M_1$; ($x_2$=$M_2$; ($\cdots$; $x_n$=$M_n$)$\cdots$)}. Under a
call-by-value evaluation strategy, this provides a mechanism for value
bindings and sequential evaluation. 
