> CBG Badger Pushlogic Runtime: An Embedded Platform for Pushlogic and Tuple Space Computing

DJ Greaves.               First Draft, November 2004. Slightly updated June 2005.       Up To Parent Page.

CBG Pushlogic System.

Part of An Embedded Platform for Pushlogic and Tuple Space Computing

Abstract

Pushlogic is our name for a style of error-resilient programming that operates on Passive Tuples. In Pushlogic Object Code, everything is declarative and no unbounded looping constructs are allowed, except where the loop passes through a device with known minimum delay, such as a timer. In Simple Pushlogic, no tuple creation, list operations or other dynamic storage allocation is allowed, instead these facilities are provided by a special loader process. Pushlogic Source is a high-level language that compiles to Pushlogic Object Code. Push Logic is suitable for implementing the embedded applications in many ubiquitous devices, with small fixed memories, such as a DVD player or burglar alarm. It is also suitable for safe control of a domain of sensors and actuators with dynamic membership both in terms of device population and the number of controlling applications.

This research investigates the boundaries between synchronous and asynchronous notification and between declarative and imperative programming. The first boundary is investigated in that both styles of commanding can be freely mixed in a common language. The second boundary is investigated in that all programs are coded in a declarative style with no unbounded loops, but operate on fields of tuples using imperative assignments.

High Level and Runtime

The runtime system for Pushlogic is designed to be used with other high-level languages apart from Pushlogic source code. Pushlogic Source has a somewhat novel error recovery procedure. We wish to also explore what can be done using other HLLs that can generate our declarative object form.

Overview

There are many forms of declarative logic programming languages. One distinction between them is whether the underlying execution engine must perform hyperlinear searching in order to find the first solution. Pushlogic is a logic programming language where the response to any data value change can be found in time that is proportional only to network delays and the number of rules stored. We call it push logic for a number of reasons:

  • because a nominal mechanical execution engine can be constructed where events at inputs can be pushed through to all necessary outputs without any additional energy being provided by the evaluator mechanism,
  • because when an output action fails, the error can be pushed backward though the flow of events that caused it so that user notification or alternative action can take place, and
  • because every rule is given a level and the introduction of a new rule can push down the level of other rules, globally, using a distributed insertion sort.
The push logic evaluator is only allowed to perform hyperlinear work when new rules are added. The same push down protocol used for rule levels is used for tuples themselves, that are maintained as a global DAG.

Application execution in ubiquitous computing will frequently fail because necessary resources are unreachable or not available. Therefore, applications coded in push logic are designed to be highly tolerant of errors. Pushlogic allows alternative actions to be taken to handle failure: a succession of these may also lead to hyperlinear evaluation time.

Asynchronous eventing has been recognised as a way of disseminating information to a number of destinations without regard to their number or whether all destinations are ready to properly receive the event. On the other hand, many applications benefit from feedback in the form of return codes from their subordinate components and can handle this with alternative behaviour or reporting it to their parent.

The major goal in the design of Pushlogic is to handle failure appropriately by balancing the intrinsic trade off between compile time error detection using advanced static/automated formal analysis methods and run-time tolerance to evolving scenarios.

We use the term 'event' to denote a nominal attempted change in value of a field of any tuple. The change is nominal in that, owing to the presence and behaviour of other Pushlogic rules, certain desired consequences of the current change may fail to execute or otherwise be banned and result in the value change not actually taking place. We term such an event a failed change. The originator (or parent) of the event may be classed as sensitive or insensitive. A sensitive parent will in turn report failure from a failed change whereas an insensitive parent proceeds unaffected.

Pushlogic uses three concepts to support in error resilience:

  • knowledge of default or failsafe values for fields
  • provision of automated undo for failed operations (like rollback in a database)
  • automated notification of event sources about consequential failures

Active Tuple Computing is a model of computation where code is contained in the Tuples. With Pushlogic, we operate on Passive Tuples: no running code is held inside Tuples and Pushlogic is not intended to be a process algebra.

Pushlogic is defined to operate in a 'domain of participation'. Pushlogic rules are stored in bundles and must be re-hydrated and checked before loading into a domain. Re-hydrating provides binding of field names to new objects that have entered the domain. Checking consists of model checking a number of constraints. If checking fails, the bundle is not loaded. In the future, a pair of domains can be merged provided automated checks are successful. This would be useful for mobile domains, such as a train carriage.

Tool Flow

Pushlogic is defined at a bytecode object level and at a block-structured HLL source level.

The source level gives the illusion of having threads and other features commonly found in imperative languages. It is compiled into object-level bytecode. Bundles of bytecode may be stored in various sorts of file system. Bundles may be re-hydrated before being executed. Re-hydration involves rewriting field names in the bundle to refer to specific fields in the target environment. Typically, when a new device enters the environment, a copy of its associated bytecode needs re-hydrating for that environment. Before execution, a number of constraints are checked and the levels of fields already present in the environment may need to be pushed down (lowered) to provide sufficient height for the new code. If either the constraints or level setting fails, the bundle is not loaded. For instance, the bundle might be incompatible with an existing bundle.

As an alternative to re-hydration, a Pushlogic program may be stored in the ROM of an embedded device (canned), or even compiled to machine code for an embedded controller. In these cases, the program achieves binding by using tuple references that are local to the current device root.

Reliable Scripting Project Flow

We have recently applied for funding for study in the area of Reliable Scripting. The architecture envissaged is shown in more detail in this figure. Pushlogic is a strawman that conforms to this flow. However, the use of existing, general purpose languages can also be explored in this framework.

Pushlogic Execution Semantics

This section is now slightly out of date w.r.t. the semantics report, so if really interested, please read the above PDF file.

For every successful assignment made, the previous value of the left hand side is noted for possible use in an undo. This is not a significant network overhead because a response packet must be sent in any case.

This diagram shows that a loaded command is in one of three states: idle, active or failed.

The push logic interpreter is started without any rules loaded. It registers itself as a part in the local root tuple. As rules are loaded, they are inserted into the global rule DAG by pushing down rules and tuples on the local and other interpreters as needed. When the levels are all stable, the interpreter registers an interest in all newly sensitive fields: that is, fields of tuples that can cause a rule to fire. Each rule is starts with an activity status of IDLE, but may immediately start to proceed to ACTIVE because its guard holds:

As notification of changes in fields is received, the interpreter updates the evaluation status of guard expressions. As guard expressions change from holding or not holding, movement of the between states in the above flow diagram occurs.

When a rule's guard starts to hold, the rule's push block is activated. On success, the state becomes ACTIVE. On the other hand, if execution of the block fails (though timeout or notification), then the undo process is commenced.

When in the ACTIVE state, the rule is waiting for its guard condition to stop holding. When the guard de-asserts, the pull block is executed. Stores in the pull block can either be of fresh constant values, default values, or values remembered from fields updated in the push block. The bytecode representation for Pushlogic allows concise representation of the pull block, based on the assumption it will essentially be the reverse of the push block.

Undo Blocks

The undo operation creates and dispatches new assignments to each of the previously successful or currently outstanding assignments so that the previous values are stored back. We refer to this behaviour as the undo phase. Where these undo operations are caused by conditions on the local host, no changes are detected that might trigger other rules that may be sensitive to the transient condition. This property, known as the nominality of commit, cannot be guaranteed for failures resulting from rules or other programs running on peer Tuple Cores, and instead there might well be an actual do/undo cycle on tuple fields, sufficient to trigger consequential rules, rather than a nominal one. This is an aspect of the system that programmers must be aware of when creating application code and which we investigate later using formal methods.

Whenever a field is set to a new value by a network push, the previous value is returned in the acknowledgement. These values are denoted as N and P in the drawing. If an undo is required, both N and P are included in the undo message. Where there has been a race, and another rule has meanwhile changed the field to a third value, V, the undo will be ignored and the value left at V. This is detected by simply checking whether the field is still at its N value when the undo is received.

Pushlogic Interpreter

The current interpreter for pushlogic is a simple C program that is linked against the embedded tuple core. Canned applications are also compiled to initialised C arrays of byte code and linked to the ROM image. The interpreter run on Unix and on our Pebbles Molly processor cards.

The current interpreter is rather verbose in terms of memory use. It holds the compiled push logic AST as a memory structure that it has inflated from the push logic byte code stored in ROM or loaded over the network interface. Given that ROM is far cheaper than RAM in mass production, this is the wrong direction of movement. A better approach is likely to be use an embedded compiler, held in ROM, to compile the push logic byte code to native code for the processor. We can look at this in the future.

Examples

For examples, please see the DVD player and heating controller page.

We are actively seeking examples from industry using embedded, networked processors in reliable applications.

Debugging Port

A telnet stub that may be diverted to a physical serial port is implemented inside the interpreter for debugging. The telnet stub is visible on port n+1 where n is the port for ETC datagrams. A variety of low-level commands may be issued, and tracing may be turned on to obtain real-time vision of events. In the future, an html or similar graphic mimic display using SVG might be made available.

Public Pages

These 'ao' web pages contain design sketches. Publishable work will be placed on the main Pushlogic Page.

Power Point Presentation

Summary slides: PPT.

(C) 2004 DJ Greaves.       Up To Parent Page.