



	   ################################################
	   #                                              #
	   # ##   ## ###### ####### ##    ## ## ##     ## #
	   # ##   ## ##  ## ##      ###   ## ##  ##   ##  #
	   # ##   ## ##     ##      ####  ## ##   ## ##   #
	   # ##   ## ###### ######  ## ## ## ##    ###    #
	   # ##   ##     ## ##      ##  #### ##   ## ##   #
	   # ##   ## ##  ## ##      ##   ### ##  ##   ##  #
	   # ####### ###### ####### ##    ## ## ##     ## #
	   #                                              #
	   ################################################






 
 
 
	 The following paper was originally presented at the

		     Third Annual Tcl/Tk Workshop
		 Toronto, Ontario, Canada, July 1995

	   sponsored by Unisys, Inc. and USENIX Association



	    It was published by USENIX Association in the
		  1995 Tcl/Tk Workshop Proceedings.
 
 
 
 
        For more information about USENIX Association contact:
 
                   1. Phone:    510 528-8649
                   2. FAX:      510 548-5738
                   3. Email:    office@usenix.org
                   4. WWW URL:  http://www.usenix.org
 
 
 
 
 
^L
               Multiple Trace Composition and Its Uses


                               Adam Sah*

                        Computer Science Division
                Electrical Engineering and Computer Sciences
                         University of California
                          Berkeley, CA 94720-1776
                          asah@cs.Berkeley.EDU

                              May 23, 1995



                                Abstract

       Traces are code attachments to variables that cause designated blocks
    of code to be executed on reads or writes to the given variable. Traces
    have numerous uses, including rules (\on<condition> do<action>"
    statements), autoloading and initialization based on data access, trans-
    parent remote data access, paging and swapping, and persistence.  Traces
    are usually limited to ad-hoc, hard-coded composition, making it difficult
    to place multiple traces on the same variable.  Multiple traces are useful
    for putting a rule on a persistent variable, or several rules on a
    variable.

       This paper presents a design for a low-level mechanism for reasoning
    about and configuring multiple traces ona single variable.  Although the
    work is based on a prototype using a modified version of Tcl's trace
    command, this mechanism easily applies to any language or library capable
    of implementing traps.  This includes systems such as data
    breakpoints[WLG93] in C and overloadable get() and set() methods in
    prototype-based object-oriented systems.  The specifics of the
    prototype are presented, including a facility for writing persistent Tcl
    scripts.  The prototype requires Tcl7.x with Tk3.x or later and may be
    downloaded from
    ftp://ginsberg.cs.berkeley.edu/pub/asah/dmt/tcl-proto.tar.gz

*supported by agrant from the National Science Foundation #NSF-IRI9107455

1   Introduction

   Variable traces are code attachments to variables. When a program reads or
writes a traced variable, the code is executed.  The Tcl[Ous94] trace
commandis typical oflanguage support and will serve as the example throughout
the paper, although memory access traps are commonplace in operating systems
(ie.  virtual memory fault handling). Traces are also described as \hooked
values" in a surveypaper by Gudeman[Gud93].

   Few accesstrapping systems supportthe composition ofmultiple code
attachmentson asingle tracedvariable; in othercases, programmers of thelast
trapmust explicitly callany previously-defined trap handler ashard
code. Ideally, a systemsupporting composition would allow handlers to be
closures (anonymous, nested, lexically scoped procedures) and automatically
replace the trace handler with the next one to fire for the duration of the
current handler. Such compositionallows the abstractionof these \resends" so
thatprogrammers can laterreorder the composition, inspect thecurrent
composition (debug it),or perform other operations on thecomposition, from
code externalto any particular trace handler.

   Access trapsare a powerfulabstraction for library andextension writers,
especially in managing data structures with constraints or in gathering
disparate data into avirtualized structure similar to one already in the
language (ie. Tcl array variables).  Inthis context, tracescan hide
arbitrarycomplexity (ie.  caching, remote access, encryption, etc.) behind an
apparently simple interface. For example, it is possibleto gather local and
remote data into a single \virtual array".  Since caching and prefetching are
shown to be identically availablein this model, performance does not suffer.

   Thekey semantic drawbackis thattraces cannot takean arbitrary number of
parameters: theread trace takes none,and the write trace takes exactly one
(the value assigned). In practice, this abstraction only models store
andretrieve; if get() doesn't return what set() stored, it is likely to
confuse users.  Even so, there are numerous uses for composable traces,
including: read-only and uninitialized variables (section3), rules and con-
straints (section 4), language support for dynamic loadingand paging (sections
5 and 6), pagingand transparent remote data access (sections 6 and 7), and
logging andpersistent computation (section 8).

   This paper presents a low-level design allowing composition of traces.
Section 2 introduces the semantics of tracing and composition and offers a low
level mechanism for composing traces.  Rather thanattempt to motivate the need
for multiple traces on a singledata variable, I willinstead present a number
of useful examples, any combination of which should serve as ample
motivation. Sections 3-8 are devoted to these examples.  Section 9 considers
efficiency as compared to offering methodbased access to data structures.
Section 10 discusses related work and section 11 suggests futurework.

2   The Semantics of Traces

Tcl's trace command allowsvariables or named slotsin an array (associative
array) tobe trapped on reads,writes or unsets.  On a trap, a named procedure
is called and passed arguments corresponding to the variable name accessed and
index (if an array access) andthe operation performed: read,write or unset.

   The semantics of the trace facility presented in this paper differ from
that of Tcl's trace command, with the intention of offering composability.
The following are the functional requirements of the new facility:

  1.traces need to be given unique identifiers (instead of being named by the
    procedure name andaccess method), removing ambiguity between two traces
    calling the same procedure.  I propose havingtrace variable return a
    handle, which can thenbe used torefer to thattrace.  Foradditional
    flexibility, trace scripts should be parameterized blocksof code (ie.
    closures of some kind), not names of procedures.  This would all variables
    localto the setting procedureto be accessed by the trace code (forTcl,
    substituted by value at the time the trace is created).

  2.The trace handler for writes should perform the write, not the system. On
    writes, Tcleagerly performs the assignment before the trace is fired,
    makingit difficult to, for example, discard the write, or otherwise effect
    different behavior on write calls.  Instead, the body of a trace should
    have to explicitly set the variable on writes.

  3.Traces on a variable should remain active during their execution,
    allowing composition; the current semantics ofTcl turn off all traces on
    the variable while the first trace executes.  Accessingthe
    currently-traced variable triggerswhat I call a \resend" (after the
    object-oriented programming concept of calling one'sparent method
    duringthe execution of the same method inthe child). By default atrace
    should turn itself off for theduration of its own execution;without this
    safety measure, themost common tracehandlers would have to becarefully
    written tomanually turn themselvesoff, lest they go into infinite
    loopsresending. There should also be a way to manually turn traceson and
    off.

  4.It should bepossible to specifyan ordering forresending (ie.  which trace
    fires when a given one resends), both as each trace is added andafter some
    orall traces arealready setup.  In addition, traces shouldbe taggable as
    \mustfire first" or \must fire last",since some traceswon't make muchsense
    in other cases.  For example, read-only variables' write traces probably
    ought to be \must fire first", since they generate an error.  For example,
    a trace that ultimately results in network messages will probably want to
    be fired last, both to improve performance should the call be unnecessary,
    as well as because controlflow is logicallymoved to the remote machine.
    For -first and -last, only one trace can fire first and only one
    last. Other traces happen in between based on their currently defined
    order.

   For thepurposes of this paper,we define a new setof semantics as
theymight be boundinto Tcl commands. Aprototype of these semantics hasbeen
added toTcl using the existingtrace command.  This prototype, while complete,
is sufficiently slow as to notconstitute auseful systemfor mostapplications
(4ms + 12ms per trace ona 100+ MIPSDEC Alpha 21064!) Rewriting this facility
in C wouldbe straightforward, but requiresmodification of the Tcl core. The
new trace semantics are definedas a set of Tcl commands:

  1.A command newtrace is added to the language and like the current facility,
    trace, it takes an option selector and option-specific additional
    arguments.

  2.So that thecode to runon atrap doesn't haveto bea named procedure, the
    variable option now takes a script (block of code). In this script,
    thestrings %name1 and %name2are substituted to being the nameof the
    variable andthe index into the array (or\" if scalar),
    respectively. %varname substitutes the full variable name.  In the
    caseof write traces, the string %newval is substituted to beingthe value
    about to be assigned.  For convenience, this block of codewill be called
    the trace code. The return from the trace code becomes the result of the
    get() orset() call that triggered the trace.

    The  return of a call to newtrace  variable is a handle
    (string  name) of the given trace.   This handle is used in
    future newtrace calls to referto this trace. This solvesthe
    ambiguity problem Tcl currently faces when referring to a
    trace  by its {type, script} tuple; this arises,  for example,
    when trying to deletea trace. In thebody of the tracecode,
    %tracehandle  is substituted to being the handle for the
    current trace being set.

  3.In order to deal with infinite loops, within thecontext of a given trace,
    the trace itself is disabled. The trace is reenabled at thecompletion
    ofthe call, evenif thecall terminates by throwing an \error" (which might
    otherwise skip past this re-enabling code). For notational convenience,
    readsor writes to the trace variable during the execution of trace code
    are called resends, since they tend to trigger other traces set on this
    variable.  In order to allow usersto override this behaviorand to gen-
    eralize this control to other situations, newtrace allows a user to
    manipulate theenabled status with theenable and disable options. Each
    takes a trace handleor list of trace handles, and enables or disables the
    giventraces.

  4.In order tointrospect and modifythe current stateof traces, newtrace vinfo
    returns a similar listof traces as trace vinfo, only the procedure names
    are handles.  The trace code text is also present in eachentry.  newtrace
    offers an option, change, whichis used to set the trace code to a new
    script.  It takes two arguments: the

-first    this trace should thatis run when the trace fires.
-last    this trace should fire last.  ie.  only if all  other traces

    resend (trigger thesame read or write trace)does this trace

    fire.

-early    this trace  should run before  any others, except  the

    first.
-late    thistrace should run after all others,except the last.
-before  <trace handles>           this trace should fire  sometime

    before the specifiedtrace handles (can be a singlehandle or

    a list of handles).
-after  <trace handles>           sameas before, butrequests after

    status.

Figure 1: Optionsto newtrace order.Although anycombination oforderings canbe
made,many don't make sense. Forthe purposesof this description,it issufficient
to treatthese asimperative statements -these arenot constraints andare
notmaintained betweenmodification tothe ordering or presenceof traces.Each
argumentset withinthe samenewtrace orderstatement canbe treated as a
separatecall.  Itis convenient tothink of allvariables having abeyond-last
write traceset, which stores awaythe newvalue in aplace accessibleonly toa
beyond-last readtrace, alsoset on all variables.

    trace handle of the trace to changeand the code to replace it with.

    newtrace offers an option, order, which is used to specify the firing
    order of variable traces. newtrace order takes a trace handle andan
    ordering argument,as shown infigure 1.

  5.Some changes arerequired ofTcl tracing: First,it is required that traces
    canbe placed overentire Tcl arrayvariables, not just on specific slots. To
    getaround this, the prototypecreates a new version of set that is aware
    of full-array traces (set2).  Second, Tcl's trace facility performs
    assignment before write traces fire; to undo this, the prototype main-
    tains the previous value explicitly.  Third, Tcl turns off all traces for
    a given variable during trace processing.  To get around this
    restriction,the prototype substitutes%varname in rules with a new, unique
    variable that for which it can turn tracing on and %realname is
    substituted if the user needs the textual name thatthe original trace was
    firedon.  These syntax make someof the examples inthe paper differ
    trivially from the code in the demo. Again, the implementation is a
    prototype: a serious effort will require changes to the Tcl core.  The
    syntax hacks would not be needed in an in-core implementation and would
    also dramatically improve performance.

   Having defined thenew facility, we can nowdemonstrate examples of its
usage.  Note that some of the codeexamples are from the demo, and some are
pseudo-code; each are labeled accordingly.

3   Read-only Variables and Uninitialized Variables

Read-only variables generate an error onwrite attempts, modeling a specific
constraint useful in debugging programs and maintaining consistency of
internal library data.  Write traces can be usedto implement
read-onlyvariables, asshown in figure 2.

   Uninitialized variables,by contrast, generatean error onread

proc  make-read-only {var}  {             #  this code from  the demo

           upvar $var  $var

           newtrace variable  $var write  {

               error  "can't write  \"%varname\": variable is  read-only"

           }

      }


                  Figure 2: Implementationof read-onlyvariables.  attempts
unless the language is supposed to automaticallyinitialize variables. This
is useful in ensuringthat programs don't depend on the quirks in one language
implementation or last value in main memory. Thistrace should removeitself
after the first write.

4   Rules

Rules are statements of the form \on <condition> do <action>" and are like
ifstatements that are alwayswatching. Rules can be implemented with traces.
For example, one rule semantic might treat (eg. compile):


     on {$a<7}  do {puts  "hi"}

as

     newtrace variable  a write  {

         if  {%newval <  7} {puts  "hi"}

         set  %varname %newval

     }


   Rules cannow be composedand havetheir composition modified on the fly.
For example, let's supposethe above example were augmented by a second rule:

     on {$a<5}  do {  puts "there"  }

We would liketo know(and control)whether [set a 3]causes \hi" to be
printedbefore \there" or viceversa{ we need tonow know which rule will fire
first.  Given the aboveinterpretation of rules, this question exactly maps
ontothe question of which order the traces will fire in. Of course, the
semantics of multiple rule composition are more complicated than this; a
future paper will outline their semantics in greater detail. The demo does not
include rule support.

5   Data Autoloading


   A data autoload is the dynamic loading of a library based on data access,
as opposed to procedure execution, the usual method for triggering an
autoload.  The advantage is that if the library primarily provides a data
structure (as opposed to a set of methods)or could otherwise be accessedfirst
by a data structure access, adata autoloadobviates the needfor aninitial-
ization routine. Whenever either the provided data orroutines are accessed,
the system autoloads themodule.

   Figure 3 shows a trace-based implementation of data autoload.  If we say
[data-autoload people people.tcl] and people.tcl contains a setof set commands
toconfigure a global array variable people, then we can tell users that a
variable named people exists, even though it doesn't really.


      #  this code  from the  demo

      proc  data-autoload {var  filename} {

            upvar  $var $var                   #  pass arg  1 by  reference

            set  readhandle   [newtrace variable  $var\(_) read   ""]

            set  writehandle [newtrace  variable $var\(_)  write ""]

            newtrace  change $readhandle  "

        newtrace vdelete  $readhandle $writehandle

                  puts  {autoloading $filename...}

                  uplevel  2 source $filename

                  return  \[uplevel 1 set2  %realname\]

            "

            newtrace  change $writehandle  "

        newtrace vdelete  $readhandle $writehandle

                  puts  {autoloading $filename...}

                  uplevel  2 source $filename

                  return  \[uplevel 1 set2  %realname %newval\]

            "

      }


                   Figure3: An implementationof data-autoload.

This provides dynamic loading for data items, obviating the need for library
initializationroutines (ie. require inLisp and Scheme) and allowing users
topretend that all extensions have already been initialized.

6   Paging

Paging is the incremental loading and saving of data from a larger secondary
store.  This allows us to manage memory on a finer granularity than whole
modules and to automatically discard or write-back data that won't be accessed
in a while.  While most operating systems support this, application-level
paging is more powerful because:

  o data-specific compression techniques can be employed. For example, a smart
    image cache cancompress least recently used (LRU) images whenspace is
    needed. Compresseddata can then be paged to a secondary store when all
    images have been compressed. Someapplications can evenuse lossy
    compression, allowing 10:1 or more compression ratios.

  o different types ofdata can becached differently. The typical example is a
    data setis usually scanned sequentially bythe given application, a
    situationbest handled by usinga most-recently-used (MRU) caching policy
    for that data (ie. turn off caching).

  o smarter prefetching is possible.  The application can pass precise
    information tothe prefetch routines,because it specifies exactly what to
    fetch early.

   We can extenddata autoloading to support paging withtwo modifications.
First, we need to call an externally provided reader/writer routine.  Second,
we need to flush the cache periodically and/or when memory runs low.  In
order to prove the concept, the prototype flushes all cached values every five
seconds.

7   Remote Data Access

Transparent remote data access is similar to paging,only with the additional
requirementof cachecoherence amonglocal copies.  For simplicity, wemodel only
non-shareddata; efficiently implementing cache coherence indistributed
shared memorysystems is an active area of research.

   Currently, systems such as Tk and Tcl-DP are based on an RPC-like model. In
this example the people database is distributed, with parts of the database
cached locally and parts stored remotely.  Using composable traces, we can
make this distributed storage seamlessly provided to the user.  On reads and
writes to theremote variable, we firstcheck the local store, and if not
present, we redirect the request overthe network to the remote store.

   This also demonstrates the need for composability.  For example, let's
nowsuppose that we additionallywant to constrain access to the people database
(eg.  \the database cannot contain a member `Smith' "). Then, wewant to take
advantage of this constraint on the client side, in order to save the network
message, which could be arbitrarily expensive. Thus, we want to ensure that
the constraint trace fires before the distributed storage call.

   Furthermore, if the array were completely virtualized and there was no
local cache of the people database,then it would probably be anerror to
settraces to fireafter the remoteaccess, since they would never be
called. This is one example where the -last option might be useful.

8   Logging and Persistent Computation

   Telescript[Whi94] supportsagents that cansurvive ahost failure.
Suchpersistence requires that agentsperiodically log their state to disk or to
a remote host.  Logging can be achieved by placing traps on persistentdata
variables[Sat93], noting updates, and removing thetraps after thefirst
update. At theend of a transaction (a unit of atomic, persistent work), we
could copy the state of all modified data items to a disk or remote host,
restoring the original traps. Transactions arerequired for reasonable
performance; the alternative is to log every single data store to a persistent
variable, which isextraordinarily expensive.

   Here is anexample interface:

persistent   Declare a variable (orset of variables) to be persistent, with
    certainbacking storeparameters (suchas which storage manager to use, the
    variable's name in the storage manager's namespace, etc.)

checkpoint   Checkpoint modified variable(s) listed (or all of them if none
    listed) to their respectivepersistent stores.


   The implementationsets traceson all persistentvariables. As each persistent
variable is modified, the modification is noted as part of thetransaction and
thewrite trace disabled untilend of transaction (checkpoint).  At each
checkpoint, the current values of each modified persistent variable is written
back to permanent storage.

   Reading back the persistent variable happens lazily: a read trace on the
persistent variableat the time ofthe persistent command call triggers acall to
the storagemanager on thefirst read.  Thistrace is disabled by writes
thathappen first.

   Concurrency control can be handled by acquiring locks for each persistent
variableas itis touched. Lockswould bedropped at checkpoint time as per
two-phase commit semantics. Deadlock would behandled by having
theacquire-lock routine throw a deadlock error, which the caller can catch.
If uncaught, the system could catch this error and release other locks held by
this program.

   Note thatthis doesn't perform thetwo phase commit needed for true atomicity
in the previous example or deal with other issues typically handled by real
DBMSs.  It is expected that such a facilitywould be glued ontop of amore
complete objectoriented DBMS backend,such asExodus[Car86] orSHORE[Car94].
Relational databases would be harder toglue, since this model doesn't handle
joins; the right way to model this might be to represent each desired joinas a
view inthe RDBMS and attach the Tcl interface to that view. In addition, the
prototype only supports unlocked writes to variables backed by other Tcl in-
terpreters.  Adding support for locking and secondary storage should prove
straightforward given the widespread availability of multiuser storage
managers such asExodus and Postgres.

9   Efficiency Concerns and Tradeoffs

One of the advantages of procedural access methods to data (\methods") is that
theyallow users to createhigher-level data access methods, which this
technique disallows because traces only trigger on generic reads and writes to
single variables (or slots in collection variables).  For example, without
modification, this proposal would have an array version of a foreach loop on
anarray variable takeone trap perelement in thetable.

   The real difference (anda disadvantage of this proposal, admittedly) is
that the use of procedures makes it easy to pass hints and other arguments to
the methods.  By comparison, read/write data access gives you precisely two
\methods" and one of them may take a single argument.  Since that single
argument can be of any type, this is aspowerful as any multiargument scheme
because we can accept either an aggregated argument (set with a list as the
assigned value) or return a closure which itself takes anargument. The real
limit is inhow easy the facility is to use,which neither alternative
maintains.

10    Related Work

The SL5 languagecontains filters[Han78], whichare remarkably similar to the
composable traces \invented"in this paper. The filters work even points out
many of the same uses mentioned here, although its model of I/O and
persistence is less sophisticated (probably due to the \newness"
ofrelational databases in 1978; object databases hadn't even been
inventedyet!)  SL5 was also influencedby notionsof failureand backtracking,
which puts it ina different designspace than thispaper, which focuses on a
more mainstream host language.

   Many of theissues in using traces have been explored inthe database and AI
literature, which call them \rules". From our standpoint, many of the semantic
issues are similar, although the context is quite different.

  o Unlike DBMSs, languagesare designedto befully programmable and user
    extensible.  DBMS rules are designed to enforce constraints[HW93],to
    providesimple triggeringmechanisms, or to provide different views of
    data[Sto90]. Language use encompasses a strict superset: for example,
    none of the DBMS papers consider rules that modify themselves,modify
    other rules or add extensions to the DBMS.  Likewise, DBMS rule systems
    research is concerned with confluence and termination[AWH92] whichare
    extremelyhard to prove for even simpleprograms in generalpurpose languages
    (and, of course, impossible to prove in thegeneral case).

  o Unlike AI systems, we are not trying to provide automatic reasoning about
    uncertainor complexsituations.  Language- based rules are meant to be
    programmed manually, where AI rule systems have typically investigated
    automaticresolution of rule conflicts[For81].


   Someobject-oriented systems allowprototypes, which areobjects that
differ(dynamically) from thetemplates usedto create them (eg.  Self has
prototypes, ScriptX has singletons).  If all objects have get() and
set()methods used to accessthem, then the overloading of get() and set()
methods is precisely equivalent to composable traces, although overloaded
methods on prototypes are a more general mechanism. Overloadable get-
ter/setters can still benefit inasmuch as this work presents a higher level
interface for dynamically assigning a resend order between them.

   Comparedwith operating systemvirtual memorytraps, traces are an instance of
user-level virtual memory support (software fault isolation (SFI) [WLAG93]):
when you touch a tainted piece of memory, yourprogram jumps somewhere elseand
runs some code, then (possibly) returns to the caller.  The primary
differences are that language-level traps are orders of magnitude faster and
offer facilities for composition and introspection. Compared with currentSFI
work,composable tracesmake traps a first-class language mechanism.

   Finally, there has been some recent work on composition of OS services.
Examples include composable file systems such as Spring[KN93] and
Interposition Agents[Jon93].  The chief difference in this workis its focuson
memory accesses andtheir interaction with the target programming language.

11    Future Work

Future work could take (at least) four directions.  First, this work presents
a low-level mechanism when higher level mechanisms are probably needed. Such
constructs are likely to be language-dependent since, by definition,
high-levelmechanisms interact tightly with existing language features. Even
this proposal attempts to fake the presence of closures in Tcl, which
doesn't support them.

   Second, this work doesnot flesh out how traces work on aggregate data
structures (ie. arrays).  This is because collection access and memory
managementsemantics depend a loton the target language, which would likely
affect how traces are handled.  This hunch was confirmed in the design of
Rush, a language similar to Tcl.  Among other differences,Rush supports
references and first-class collections[SBD94].

   Third, itwould be interesting to explore whetherconstraints made from traps
(\rules") could be used to allow untrusted scripts to run safely (\safe
execution",a la Safe-Tcl).

   Finally, the demois intentionally prototypical and still quite brittle.  If
features such as persistence and transparentremote data access are important,
then composable traces need to be implemented in the Tcl core. Since it
interacts with how variables are assigned and traces fired, such changes
cannot be added as a third party extension.

12    Acknowledgements

The author wishes tothank Jon Blowfor helping develop many of these ideas over
the past few years and Tom Lord, Sanford Barr, Raph Levien, Brian Dennis and
Allison Woodruff commented on earlier drafts of this work.  Thanks to Michael
Stonebraker for his many flavors of support. Thanks to David Gudeman and Ralph
Griswold for pointing me to SL5.  The Postgres95 update to Postgres is the
work of Andrew Yu and Jolly Chen.

   Thanks, of course, go to John Ousterhout, whose Tcl tool proved once again
to be insanely flexible: the entire prototype and demo (1300 lines) was
written in a week!  In other languages, this would have required substantial
hacking.  Specifically, Tcl's introspection capabilities proved helpful for
debugging the necessarily twisty code involved.


     #  declare that  the variable  x be  made recoverable,  that it's  name in
     # the  persistent storage  manager's world  is "somename"  and to  use the
     # storage  manager named  "wish #2"  which is  a Tcl  interpreter.
     persistent x  -name "somename"  -type "Tcl"         -place "wish  #2"
     persistent z  -name "x"  -type "pg95"  \
                        -place "eden.cs.berkeley.edu  5432 MYDB  PERSIST"

     # change  the value  of 'x'  to 1.
     # It  is *not*  recoverable until  checkpointed.
     set x  1

     # sends the value of 'x' to 'wish #2'.
     checkpoint x

     # modify  'y'.
     set y  1

     # saves  the value  of 'y'  in postgres  ('x' wasn't  modified).
     checkpoint

Figure 4: Persistentcomputation example.Note thatonly Tcland Postgres95(pg95)
bindingshave been written. Inthe Postgres95binding, theplace refersto ahost, a
portnumber, adatabase, and a specific DBMStable, inthat order.

      #  this code  from the  demo...
      persistent  ip1 -name  stored_ip1 -place  fred1 -type  tcl
      persistent  ip1 -name  stored_ip2 -place  fred2 -type  tcl
      set  ip1 1
      checkpoint

               Figure5: Composed persistence(persistence asa service).  As
with the other examples,persistence demonstrates the need for
composability. In this case,the checkpoint shouldwrite ip1 back to two places.


References

[AWH92]    Alexander Aiken, JenniferWidom, andJoseph Heller-
           stein.  \Behavior of  Database Production Rules:
           Termination, Confluence, and Observable Deter-
           minism" Proc. ACM SIGMOD'92Conf. on Manage-
           ment of Data.

[BS94]     Jon  Blow and  Adam Sah. \Rule  Semantics and
           Their  Use in More Precise  Aliasing" UC Berke-
           ley Technical Report #94/59.

[Car94]    Michael Carey, et. al. \Shoring Up Persistent Ap-
           plications" Proc. ACM SIGMOD'94 Conf. on Man-
           agement of Data.

[Car86]    Michael Carey, et. al.\The Architecture of the EX-
           ODUS  Extensible DBMS"  1986 Proc.  Symp. on
           Very Large Database Systems. (VLDB'86)

[For81]    C.L. Forgy. \OPS5 User'sManual" Dept. ofComp.
           Sci., Cargenie-Mellon Univ. 1980.

[Gud93]    David Gudeman. \Representing Type Information
           in  Dynamically Typed  Languages" Univ. of Ari-
           zona Technical Report #93-27.

[Han78]    Hanson, David R. \Filters  in SL5" The Computer
           Journal. v.21,No.2. pp.134-43. May 1978.

[HW93]     Eric Hanson and Jennifer Widom.\An Overview of
           Production  Rules in  Database Systems" Knowl-

           edge and EngineeringReview. vol.8, no.2,pp.121-143.
           June 1993.

[Jon93]    Michael  B. Jones. \Interposition  Agents:  Trans-
           parently  Interposing  User Code  at  the System
           Interface"  Proc. 14th Symp. on Operating System
           Principles (SOSP'93).

[KN93]     Yousef Khalidi andMichael Nelson. \Extensible File
           Systems in Spring" Proc. 14th Symp.on Operating
           System Principles (SOSP'93).

[Ous94]    John  Ousterhout. An Introduction  to Tcl and Tk.
           Addison-Wesley. 1994.

[SBD94]    Adam Sah, Jon Blow and Brian Dennis. \An Intro-
           duction to the Rush Language" Proc.Tcl'94 Work-
           shop. New Orleans, LA. June, 1994.

[Sat93]    M.  Satyanarayanan, et. al. \Lightweight  Recover-
           able  Virtual Memory" Proc. 14th Symp. on Oper-
           ating System Principles (SOSP'93).

[Sto90]    Michael   Stonebraker.  \On   Rules,  Procedures,
           Caching,  and Views in Database Systems" Proc.
           ACM SIGMOD'90 Conf. on Management of Data.

[WLG93]     Robert Wahbe, Steven  Lucco and Susan  Graham.
           \Practical  Data Breakpoints: Design and Imple-
           mentation" Proc. ACMSIGPLAN'93 Symp. onPro-
           gramming Language Design andImplementation. Al-
           buquerque, NM. 1993.

[WLAG93]     Robert  Wahbe, Steven Lucco, Thomas E. Ander-
           son and Susan Graham. \Efficient Software-Based
           Fault  Isolation" Proc.  ACM SIGOPS'93 Symp. on
           Operating System Principles. Asheville, NC. 1993.

[Whi94]    J.E.  White. \Telescript Technology:  the founda-
           tion  of the electronic marketplace" White Paper.
           General Magic, Inc. 1994.

