PaperlayerView exact revision on arXiv

Source-linked AI summary

Organizing the Aggregate: Languages for Spatial Computing

Jacob Beal, Stefan Dulman, Kyle Usbeck, Mirko Viroli, Nikolaus Correll

arXiv:1202.5509v2cs.PLcs.DCcs.MA

TL;DR

Users increasingly need to control aggregates of devices while existing interfaces expose complex individual-device technology. The chapter develops a layered framework and survey for comparing spatial DSLs, then identifies research directions and scope boundaries for future language development.

  • Problem

    Users often specify collective behavior, but available programming interfaces require reasoning about individual devices and their interactions.

  • Method

    The chapter builds a layered aggregate-programming framework, surveys spatial DSLs across domains, compares their properties, and proposes a roadmap.

  • Results

    The survey organizes DSLs by abstraction layers, language properties, spatial operations, and device and communication characteristics, revealing distinct priorities and trade-offs across languages.

  • Takeaways & Limitations

    Future work should develop general-purpose spatial languages while retaining specialized DSLs and exploring implementations of specialized languages on general-purpose foundations.

  • Takeaways & Limitations

    No surveyed system spans the full range of considerations, and modular-robotics languages remain uncertain for dynamic shape reconfiguration and locomotion under sensing, actuation, and communication uncertainty.

Abstract

from arXiv · show

As the number of computing devices embedded into engineered systems continues to rise, there is a widening gap between the needs of the user to control aggregates of devices and the complex technology of individual devices. Spatial computing attempts to bridge this gap for systems with local communication by exploiting the connection between physical locality and device connectivity. A large number of spatial computing domain specific languages (DSLs) have emerged across diverse domains, from biology and reconfigurable computing, to sensor networks and agent-based systems. In this chapter, we develop a framework for analyzing and comparing spatial computing DSLs, survey the current state of the art, and provide a roadmap for future spatial computing DSL investigation.

1 Introduction

Spatial computing addresses the gap between users who specify aggregate behavior and systems implemented through individual devices. The chapter frames spatial locality as a bridge and develops a comparative framework, survey, and roadmap for spatial DSLs.

  • Motivation: Embedded systems increasingly expose users to complex individual-device programming despite users’ aggregate-level goals.Examples span wildlife sensing, responsive buildings, robot teams, reconfigurable chips, and synthetic biology.
  • Spatial Computing: Spatial computers connect computation with physical arrangement, making geometry and topology useful abstractions for programming aggregates.Regions, neighborhoods, and flows can be mapped to individual-device behavior.
  • Existing DSLs: Spatial DSLs across many communities use diverse combinations of general spatial concepts and domain-specific requirements, with varying success.The shared ideas across currently chaotic DSLs motivate more powerful and generally applicable languages.
  • Chapter Contributions: The chapter develops a framework for analyzing and comparing spatial computing DSLs, surveys the state of the art, and proposes a future research roadmap.The investigation defines an analytic framework, surveys languages across domains, compares representative reference examples, and identifies gaps.

2 Analytic Framework

The analytic framework defines spatial DSLs and organizes them through a layered aggregate-programming architecture. It separates spatial and aggregate concerns from device-level details while comparing language scope, design, operations, and communication abstractions.

  • Scope: The framework defines spatial DSLs as mechanisms targeting spatial computers with geometric or topological aggregate constructs and unbounded system composition.The chapter also includes selected aggregate languages without explicit spatial constructs for comparison.
  • Generic Aggregate Programming Architecture: The five-layer architecture ranges from physical platforms and system management through abstract devices and spatial computing to aggregate-oriented users and applications.The lower three layers concern individual devices and local interactions, while the upper interface addresses aggregate behavior.
  • DSL Properties: The framework analyzes each DSL by its focused layers, programming type, design pattern, target platform, and intermediate abstraction layers.Design patterns include restrictions, extensions, piggyback languages, and inventions from scratch.
  • Spatial and Device Properties: Spatial and abstract-device analysis covers space-spanning abstractions, device relationships to space, and information movement through the system.The framework organizes these concerns around the relation between space-time and information.
  • Scope Boundary: The framework does not directly address system management because current system-management decisions are largely disconnected from spatial considerations.Existing agent-system reference models are identified as possible tools for analyzing those pragmatic concerns.
  • Types of Space-Time Operations: Compute-pattern operations describe informational patterns over space-time, including stripes, timers, propagating waves, communication, and pointwise sensing or actuation.This is one of the operation classes derived from the space-time and information duality.

3 Survey of Existing Spatial DSLs

The survey organizes spatial DSLs across domains and compares representative languages using tables derived from the analytic framework. The comparison covers general language properties, spatial operators, and device and communication abstractions.

  • Survey Scope: The survey spans amorphous computing, biological modeling, agent-based systems, wireless sensor networks, pervasive systems, robotics, parallel and reconfigurable computing, cellular automata, and formal calculi.Domain boundaries are fuzzy, and some language placements are necessarily arbitrary.
  • Comparative Organization: Three tables provide a cross-language view of general DSL properties, space-time operators, and abstract device and communication characteristics.Only languages needed to represent the current range and capabilities are included for clarity.

3.1 Amorphous Computing

Amorphous computing DSLs address the challenge of producing predictable aggregate behavior from locally communicating devices, spanning pattern-specific languages and more general spatial languages. Proto extends this approach with functional aggregate operations, library abstractions, and compilation to portable local programs.

  • Language families: Amorphous computing languages target irregular arrangements of unreliable, locally communicating devices and divide broadly into pattern and manifold programming languages.The field seeks engineering principles inspired by natural systems.
  • Pattern languages: GPL, OSL, and MCL express spatial patterns through botanical growth, origami folds, or diffusing chemical signals, respectively.Their abstractions range from topological and geometric pattern specification to biologically realizable propagation rules.
  • Proto: Proto provides a more general functional language based on a continuous amorphous-medium abstraction, with applications including vector-field control in swarm robotics.Proto programs interact with environments through sensors and actuators that measure and manipulate occupied space.
  • Proto: Proto compiles high-level programs into local programs executed by a portable virtual machine across platforms, including a simulator.A reference example selects an origin, constructs a coordinate system, moves devices into a T shape, and computes its center of mass.
  • Analysis: Proto runs in both two- and three-dimensional space without additional code, while aggregate-level library operators compensate for primitives defined over local space-time neighborhoods.These operators include functions such as distance-to and broadcast, supporting Proto’s general applicability across biological and robotic domains.
  • Pattern languages: Pattern languages support robust formation of spatial structures, but different pattern types are difficult to mix and generally cannot be cleanly composed.This limits their scope despite their varied high-level representations.

3.2 Biological Modeling and Design

Biological spatial DSLs range from reaction and compartment models to languages that manipulate geometric and topological structures. The MGS reference example demonstrates cellular-complex modeling, staged growth transformations, mechanics, and aggregate computation.

  • Existing biological DSLs: Biological modeling languages describe molecular reactions with spatial compartments, while more spatial systems model growth, topology, diffusion, and cell development.Examples include Antimony, ProMoT, iBioSim, little b, L-systems, MGS, and Gro.
  • Synthetic biology: Synthetic-biology design languages remain sparsely spatial: GEC models compartment-to-compartment molecular motion, Proto BioCompiler maps spatial programs to genetic regulatory designs, and Eugene and GenoCAD lack spatial constructs.The passage states that only two of the few emerging high-level synthetic-biology languages include spatial operations.
  • MGS model: MGS performs general rule-based computation over topological complexes, using cellular complexes composed of vertices, edges, and parallelogram surfaces.Collections associate values with cells, and recursive cell definitions establish spatial relationships.
  • MGS reference example: The MGS reference example grows a T shape in two phases: apical-side growth first, followed by lateral-side growth.Edges are labeled Apical, Basal, and Lateral; each evolution rule creates a new parallelogram and updates neighborhood relationships.
  • MGS reference example: MGS models mechanics with a mass-spring system, computes forces from neighboring vertices, and updates positions using a speed-proportional-to-force rule.The implementation uses edge rest length L0, spring strength k, and a timestep dt.
  • MGS reference example: MGS computes the T shape’s center of mass directly with a fold over its collection, averaging vertex coordinates.The example also includes a basic growth model with separate FGP and SGP state records and decrementing phase counters.
  • Analysis: Biological DSLs that raise abstraction toward aggregates provide varied space-time operations, with MGS offering especially powerful geometric and topological manipulation.The survey characterizes MGS as a particularly expressive biological modeling language.

3.3 Agent-Based Models

Agent-based DSLs model agents, their interactions, and environments, with frameworks ranging from graphical modeling languages to programming-language extensions and simulation toolkits. Among these, multi-agent modeling and simulation toolkits are the only class identified as exhibiting spatial properties.

  • Agent-based models describe agents with attributes and behaviors, relationships and interaction methods, and the environments in which agents interact.
  • Agent-oriented DSLs are categorized as graphical agent modeling languages, agent frameworks, or multi-agent modeling and simulation toolkits.
  • Representative systems include UML-based graphical languages, Java-based agent frameworks, Logo extensions such as NetLogo, and simulation platforms such as Repast and Swarm.
  • Reference Example: The NetLogo reference implementation uses shared global state, agent-local coordinates, and an origin agent to represent the reference example’s local coordinate system.
  • Analysis: Multi-agent modeling and simulation toolkits are the only agent-based DSL class with spatial properties, likely because tight language–simulation integration exposes features such as distance and movement.
  • Analysis: Agent-based DSLs usually abstract networks and support discrete agent interaction, while some multi-agent toolkits additionally provide topology, links, and unicast or multicast communication.

3.4 Wireless Sensor Networks

Wireless sensor network DSLs address resource-constrained sensing platforms through abstractions for hardware, communication, processing, and energy management. The survey finds that their data-collection focus leaves most languages poorly suited to the spatial computing requirements of the reference example.

  • Wireless sensor networks use autonomous sensing devices with limited energy, making communication–local-processing trade-offs and runtime quality-of-service estimation central concerns.
  • Network topology, communication patterns, local algorithm execution, hardware abstraction, scheduling, and event-driven component control motivate wireless sensor network DSLs.
  • The surveyed DSLs include multiple classes and approaches, with Regimental-style translation-based functional programming identified as closest to spatial computing in this domain.
  • Several wireless sensor network DSL classes lack common spatial-programming characteristics, instead focusing on software-component composition, discrete device addressing, or event/data-driven agent functionality.
  • Reference Example: Most wireless sensor network DSLs cannot implement the reference T-Program because they generally lack actuation and spatial measurement, although aggregate properties such as center of gravity are typically supported.
  • Analysis: The survey concludes that wireless sensor network DSLs are poorly suited to bridging designers and embedded platforms because data dissemination, static topologies, and single gateways constrain spatial functionality.

3.5 Pervasive Computing

Pervasive computing DSLs coordinate mobile and wireless devices in environments where users interact with distributed sensors and actuators. The surveyed approaches range from network abstraction and tuple diffusion to chemical reactions and explicit spatial scoping, but their spatial support varies substantially.

  • Pervasive computing applications connect people with distributed sensors and actuators, typically over wireless networks containing mobile nodes.
  • Relatively few pervasive computing DSLs provide spatial operators, since tuple-space languages such as LINDA generally abstract the network from programmers.
  • TOTA: TOTA provides field-based coordination by diffusing tuples through neighboring devices, but natively supports only the neighbor spatial operator.
  • Chemical Reaction Model: The chemical reaction model manages tuple interaction rather than agent behavior, using stochastic concentration updates and probabilistic diffusion through neighboring devices.
  • Chemical Reaction Model: Chemical-reaction extensions use neighbor patterns and estimated distance to propagate gradients, retain the shortest-distance gradient, and support spatially informed local processing.
  • Spatially Scoped Tuples: Spatially scoped tuple systems encode relative or global coordinates and address tuples through geometric regions such as boxes, spheres, cylinders, and cones.
  • Analysis: The surveyed pervasive DSLs use discrete devices with stationary programs, while their communication models range from global multicast and neighborhood propagation to spatially scoped interaction.

3.6 Swarm and Modular Robotics

Swarm and modular robotics expose the gap between specifying aggregate behavior and programming individual devices. Their DSLs use spatial abstractions for formations, localization, communication, and reconfiguration, but generality and scalability remain unresolved.

  • Swarm robotics: Swarm robotics emphasizes many simple agents with local interactions, supporting scalable coverage for monitoring, rescue, and cleanup.These applications exploit the swarm’s ability to cover large areas in parallel.
  • Swarm robotics: Controlling swarm shapes requires localization, state communication, and unique identifiers for interpreting messages.Without these capabilities, some swarms instead rely on gradients or crude global bearing estimates.
  • Swarm robotics: Swarm systems can be programmed with multi-agent or manifold languages, but implementation performance depends strongly on language constructs and scaling behavior.For example, NetLogo’s ask turtles construct scales linearly with the number of robots.
  • Modular robotics: Graph grammars specify self-assembly as labeled graph transformations, while reversal rules can make or break robot connections when their left-hand-side conditions hold.These rules replace matched subgraphs and can be executed by the environment or by modules exchanging state.
  • Modular robotics: Modular-robot DSLs include Meld for declarative logic programming and abstractions for movement, path planning, and spatial algorithms.Desired shapes can act as declarative specifications whose compilers generate event-driven module actuations.
  • Modular robotics: After a T-shape is assembled, multi-hop coordinates let Proto compute a center of gravity and produce a ring pattern, but few works address spatial computing beyond pattern formation.Modular robots otherwise promise reconfiguration and self-repair through autonomous attachment and detachment.
  • Analysis: The survey finds robotics DSLs focused largely on manipulating space, while ASE’s scalability remains unestablished because it has been tested only on small device populations.Meld supports correctness proofs, but sensing, actuation, and communication uncertainties leave its practical translation unclear.

3.7 Parallel and Reconfigurable Computing

Parallel and reconfigurable-computing DSLs exploit spatial hardware mainly through dataflow, topology, or fields. Their strongest contribution is distributed control-flow models, while explicit spatial operations and supported spatial behaviors remain limited.

  • Overview: Parallel and reconfigurable computing prioritize fast execution, making communication delays dominant as processor and configurable-element counts increase.These systems include processor grids, tiled architectures, reconfigurable fabrics, and massively multicore systems.
  • Dataflow languages: Dataflow languages identify dependencies so independent operations execute in parallel, representing computation as a partial order of parallelism and time.Many extend C, FORTRAN, or MATLAB, or use circuit-specification languages such as VHDL.
  • Topological languages: Unlike dataflow languages, topological languages model information exchange among processes while abstracting locality from hardware dimensions.MPI and related systems specify interacting processes through message passing and explicit locality constructs such as places, locales, and regions.
  • Topological languages: GraphStep trades generality for efficiency by repeatedly receiving neighbor messages, computing updates, and sending them along graph edges.It maps the computation and dataset onto available hardware by decomposing and arranging graph nodes.
  • Field languages: Field languages explicitly connect space-filling hardware with multidimensional arrays and are consequently the most spatial class in this domain.They are motivated by applications whose physical phenomena are spatial, including atmospheric simulation, machine vision, VLSI, and tissue simulation.
  • Field languages: StarLisp mapped multidimensional parallel variables onto Connection Machine processors, while later systems exposed grid chunks, neighbor communication, and spatial types.Field languages nevertheless remain niche, supported primarily through libraries such as FLIC and RSL.
  • Analysis: Cellular-automata languages provide succinct specifications, but this domain lacks DSLs that measure or manipulate space, aside from pattern creation by cellular automata.The section therefore provides no reference example suitable for parallel or reconfigurable-computing languages.
  • Analysis: Dataflow and topological languages predominate but have minimal spatial operations, whereas field languages support only narrow operations on rectilinear grids.Across the classes, distributed program-control models offer the main resource for future spatial-DSL development.

3.8 Formal calculi for concurrency and distribution

Formal calculi model spatial computation through process interaction, geometric state, or nested compartments. The survey contrasts 3π’s geometric process model with ambient calculi’s container-based model and identifies their different communication ranges and limitations.

  • 3.8 Formal calculi for concurrency and distribution: Formal calculi describe system features and behaviors abstractly to support reasoning about properties and guide compliant implementations.The reviewed spatial calculi are mostly extensions of π-calculus, which abstracts network topology into named communicating processes.
  • 3.8.1 3π Process Algebra: 3π extends π-calculus with three-dimensional geometric space, giving each process a position and orientation that can be exchanged or changed through movement.The reference implementation uses a concrete variation of 3π to construct a T-shape through a force-field process.
  • 3.8.1 3π Process Algebra: 3π has no embedded time or proximity-based communication: synchronization uses blocking messages, and processes address others by unique names regardless of position.Geometrically local communication must therefore be encoded on top of the model.
  • 3.8.2 Ambient Calculus: Ambient calculus and related systems place processes in hierarchically nested compartments with operations for entering, exiting, creating, or destroying compartments.Communication is implemented through interactions such as messenger-process diffusion rather than as a primitive.
  • 3.8.3 Reference Example: 3π: The 3π T-shape example sends device positions to a force process, which returns affine transformations placing devices on the x- or y-axis.An affine map is represented by a 3x3 matrix and translation vector; center-of-gravity and ring computations are omitted because local communication must also be represented.
  • 3.8.3 Reference Example: 3π: Figure 12 depicts creation of the T-shape with 3π.The example’s shape construction is based on the force-field process described in the surrounding text.
  • 3.8.4 Analysis: Both 3π and Mobile Ambients extend π-calculus with independent communicating processes, but 3π processes know geometric positions whereas ambient processes know spatial containers.Thus, 3π manipulates location and orientation, while Mobile Ambients manipulate container structure and neighborhood diffusion.
  • 3.8.4 Analysis: 3π addresses named processes globally, whereas ambient processes communicate near their current container.Both calculi focus on mobile processes operating on discrete devices, but their communication ranges differ.

4 Analysis

Spatial computing DSLs cluster into four broad groups that trade off abstraction, generality, and system-management support. The analysis identifies shared limitations and proposes capabilities needed in future languages.

  • Language groups: Spatial computing DSLs cluster into device abstraction, pattern, information movement, and general-purpose spatial languages.The groups differ in the aspects of aggregate programming they emphasize.
  • Language groups: Device abstraction languages simplify local communication and system management but provide little spatial abstraction over aggregates.They are used across domains including agents, sensor networks, robotics, parallel computing, and reconfigurable computing.
  • Language groups: Pattern languages construct spatial patterns, while information movement languages gather data from one space-time region and deliver it to another.Pattern languages include bitmap, geometric, and topological varieties; information movement languages may use push or pull models.
  • Comparative findings: General-purpose spatial languages combine aggregate abstractions with composability and configurability, but specialized capabilities often require unavailable libraries.Their generality distinguishes them from narrower pattern and information movement languages.
  • Comparative findings: Spatial DSLs trade off parallelism, speed, and coherence, and existing languages make different choices without supporting elegant mixtures of strategies.Proto, MDL2ϵ, and OSL weaken coherence or speed in distinct ways.
  • Open needs: Current DSLs generally lack formal verification, hardware-capability warnings, and combined generation of platform executables and verification models.The proposed roadmap also calls for combining aggregate and state-based programming schemes.

5 Conclusions and Future Research Directions

The chapter concludes that increasing system complexity will favor general-purpose spatial languages while preserving a role for specialized DSLs. It identifies unresolved needs in robustness, system management, language expressiveness, and integration across DSL types.

  • Conclusions: Increasing engineered-system complexity is likely to favor general-purpose spatial languages because other DSL groups are either insufficiently aggregate-oriented or too specialized.Device abstraction languages lack aggregate leverage, while pattern and information movement languages are often too specialized for large-scale systems.
  • Future research directions: Current general-purpose spatial languages do not expose error handling or quality-of-service information to programmers.Scalable treatment of these concerns for distributed aggregates remains an open research question.
  • Future research directions: System-management concerns such as security and logging remain largely unaddressed by current general-purpose spatial languages, limiting their usability in deployed systems.The chapter points toward building on device abstraction languages to expose these concerns through aggregate abstractions.
  • Future research directions: No general-purpose spatial language currently offers full support for first-class functions, partly because distributed runtime identity and scope remain unresolved.The cited fundamental problems concern functions defined at run time.
  • Future research directions: Publish/subscribe, observer/controller, and first-order logical inference are difficult or impossible to implement on current general-purpose spatial languages.Future work must determine how these paradigms can be adapted to aggregate environments.
  • Future research directions: Specialized spatial DSLs will remain useful for domain-specific issues, while implementing them atop general-purpose languages could reuse existing theory, software, and management resources.This relationship could also push general-purpose languages to support the needs of hosted DSLs.

6 Key Terms and Definitions

The chapter defines spatial computing through aggregate abstractions, device-level execution, and the physical and management layers that connect them. It also distinguishes device abstraction, pattern, information movement, and general-purpose spatial languages.

  • Core concepts: A spatial computer is a collection of local devices distributed through physical space, with communication difficulty dependent on distance and goals defined by spatial structure.This definition links physical arrangement, communication, and functional goals.
  • Core concepts: Global-to-local compilation transforms an aggregate-device program into a program executable on individual devices.It connects aggregate specifications to device-level execution.
  • Core concepts: Space-time operations are aggregate abstractions for measuring, computing patterns over, manipulating, and physically evolving space-time, plus meta-operations.The definition divides these operations into five categories.
  • Architectural layers: The abstract device layer hides execution-device details, while the system management layer supplies low-level operating-system services.Examples include process management, sensor and actuator drivers, and low-level networking.
  • DSL categories: Device abstraction languages hide implementation details with limited spatial power; pattern and information movement languages focus respectively on spatial patterns and cross-region data delivery.General-purpose spatial languages instead provide broad spatial abstractions for aggregate programming, typically requiring more domain-specific work.

7 Additional Reading

The additional reading list spans foundational work on amorphous computing, agent systems, biomolecular languages, sensor networks, reconfigurable processors, embedded systems, and parallel computing.

  • Foundations: The list includes foundational work on amorphous computing and reference architectures for agent-based systems.These entries include Abelson et al. (2000), Regli et al. (2009), and Nguyen et al. (2010).
  • Application domains: Additional readings address high-level programming for biomolecular systems and programming wireless sensor networks.The listed works are by Beal et al. (2011b) and Mottola and Picco (2011).
  • Computing platforms: The list also covers programming tools for reconfigurable processors, development methods for embedded reconfigurable systems, and an introduction to parallel computing.These entries span hardware-oriented and parallel-computing perspectives.
Loading 1202.5509v2…