On the Evaluation of Space-Time FunctionsJacob BealBBN TechnologiesCambridge, MA, USA, 02138Email: [email protected] UsbeckBBN TechnologiesCambridge, MA, USA, 02138Email: [email protected]—The Proto spatial programming language abstractsthe distributed execution of programs as evaluation of space-time functions over dynamically defined subspaces on a manifold.Previously, however, function evaluation has always been definedin terms of a complete inlining of expressions during compilation.This simplified the definition of programs, at the cost of limitingexpressiveness and duplicating code in compiled binaries. Inthis paper, we address these shortcomings, producing a modelof in-place function evaluation and analysis of its implicationsfor Proto. We have extended the MIT Proto compiler andProtoKernel virtual machine to implement this model, andempirically verified the reduction of compiled binary size.I. INTRODUCTIONEvery distributed programming framework must addressthe question of how to control where (and when) a processexecutes. One way of controlling process execution is to viewthe distributed system as a spatial computer—a collection ofinter-connected devices where the difficulty in communicatingbetween devices is strongly-dependent on the distance betweenthem. Proto [1] uses a continuous space abstraction to view thenetwork of devices as a discrete approximation of continuousspace. Paired with a dataflow model of computation, thisallows Proto to describe distributed algorithms in terms ofoperators evaluated over continuous regions of space-time.Previously, Proto implemented calls to user-defined func-tions with syntactic inlining during compilation, in order tosimplify the global-to-local compilation process. Syntacticinlining caused duplicate code in compiled binaries and pre-vented desirable language features such as function bindingand recursive function calls. This paper addresses these short-comings, resulting in a model of in-place function evaluationand a reference implementation. The key contributions are:• Formal substitution and in-place models for evaluatingfunctions over space-time manifolds (Section III).• Criteria for well-defined evaluation of space-time oper-ators, with analysis of implications for Proto, includingfunction evaluation (Section IV and V).• Description of a reference implementation for space-time function calls, along with empirical validation ofdecreased binary size (Section VI).Work partially sponsored by DARPA DSO under contract W91CRB-11-C-0052; the views and conclusions contained in this document are those of theauthors and not DARPA or the U.S. Government.II. BACKGROUND: PROTOProto [1], [2] is one of a number of programming modelsthat have recently been developed for spatial computers. InProto, programs are described in terms of dataflow fieldoperators and information flow over regions of continuousspace-time. Closely related to Proto are MGS [3], whichperforms computation and topological surgery on the cells of ak-dimensional CW-complex, and Regiment [4], which operateson data streams collected from space-time regions. A numberof “pattern languages”, such as Growing Point Language [5]and Origami Shape Language [6], also use continuous-spaceabstractions, but have limited expressiveness. There are alsoa number of discrete-model languages, such as TOTA [7],which uses a viral tuple-passing model, or LDP [8] andMELD [9], which implement a distributed logic programmingmodel. These discrete languages are typically more tightly tiedto particular assumptions about scale and communication thanlanguages that use a continuous abstraction.In Proto, programs are described in terms of operators overregions of continuous space, using the amorphous mediumabstraction. An amorphous medium [1] is a manifold witha computational device at every point, where each devicecan access the recent past state of a neighborhood of othernearby devices. Computations are structured as a dataflowgraph of operators on fields (functions assigning a value toeach point in space). Careful selection of operators allowsthese programs to be automatically transformed for discreteapproximation on a network of communicating devices—typically as a ProtoKernel virtual machine [10] binary.Proto uses four families of operators: pointwise, restriction,feedback, and neighborhood. Pointwise operators (e.g., +,sqrt, 3) involve neither space nor time. Restriction operators(e.g., if) limit program execution to a subspace. Feedback op-erators (e.g., rep) remember state and specify how it changesover time. Neighborhood operators (e.g., nbr, int-hood)encapsulate all interaction between devices, computing space-time measures over neighbor state. For a full explanationsee [1] or the MIT Proto documentation and tutorial [2].A. Formal NotationProto dataflow programs can be formally represented inan equivalent manner using either mathematical notation ordataflow diagrams. In this paper, we will use both: diagramsfor intuition and mathematical notation for analysis and proofs.!(a) Field!"#"$"%!&!(b) Operator Instance!"#$%&'($(c) Manifold!""(d) Sub-manifoldFig. 1. Proto programs contain manifolds (spaces), fields that assign valuesto every point in a manifold and operator instances that compute fields.In either case, a Proto program may be represented asa collection of manifolds (M ), fields (F ), and operator in-stances (O), and return value associations between fields andmanifolds (R). The manifolds are the space-time region andsub-regions1over which the program executes. The fields arethe variables and values of the program, each field (f ∈ F )assigning a value to every point in some region of space-time(f : m → V , where m ∈ M and V is any data value). Theoperator instances are the computations being done to producethe fields, with each operator instance (o ∈ O) taking zeroor more input fields and producing precisely one output field(o : i0× i1× ... × ik→ fo, where i∗, fo∈ F ). Fields can alsobe selectors for subspaces: given manifold m0and a Boolean-valued field sm∈ F with m as its domain, we can define sub-manifold m as {p ∈ m0|s(p) = true}, the part of m0wheresmis true. Return values are pairs r = (m, f), associating aroot manifold m (the entire space associated with a functionor program), with some field that has m as its domain.Figure 1 illustrates symbols for manifolds, fields, and op-erator instances. A field is an arrow going from the