Skip to content

itdaniher/ratpak

Repository files navigation

Rust Version

rustc 0.13.0-dev (52c3fe953 2014-10-30 17:57:09 +0000)

Introduction

RatPak is a declarative language for defining graphs of interconnected processes, interacting according to the Kahn Process Network paradigm. Such graphs are invaluable when describing manipulations on streams of information, like those produced by sampling analog values in the real world. Directed graphs are capable of concisely describing discrete time signal processing algorithms and the successive transformations associated with demodulating and decoding mixed-domain communication protocols. As RatPak compiles to Rust source code (example here), which benefits from LLVM's extensive optimizations and Rust's excellent concurrency primitives, a RatPak flowgraph definition can directly produce a corresponding Linux executable. RatPak has been routinely used to describe flowgraphs spanning dozens of OS threads performing complex signal manipulations on millions of samples per second, with milliseconds of latency.

A RatPak flowgraph builds off of an ASCII representation of a directed tree to include syntax for describing connections, as well as syntax for describing processes. RatPak offers a set of useful stream manipulations as builtins (defined in boilerplate.rs,) and is well complemented by the array of functionality of LibRedio.

Semantics

The trivial case of a flowgraph contains two elements, a source (process producing a stream) and a sink (process accepting a stream.) This can be extended to yield arbitrarily long one-dimensional sequences starting with a source, ending with a sink, with a number of processing nodes each accepting and transmitting exactly one stream.

In RatPak, this looks like:

main
	source
	procA
	procB
	procY
	procZ
	sink

alt text

Each process has its own line, and is implicitly connected to the output of the process above and input of the process below.

Unfortunately, the descriptive power of 1D signal processing chains leaves a bit to be desired.

To begin to render the complexity of a flowgraph easily describeable, RatPak uses a small set of symbols to represent forks, merges, and arbitrary point-to-point connections.

Forks

Forks are demarkated using the carrot '^' character - all processes in an expression prefaced by the carrot accept the same input source. Forks are implemented as a task accepting a single receiver and a list of senders. When the read completes, the token is copied and sent for each member in the list of senders.

main
	source
	^ (procA) printSink
	printSink

alt text

Joins

Joins offer more semantic variety - while forks are explicitly synchronous, there may come times when it is necessary to merge multiple streams presenting data at different rates. A process semantically equivalent to the 'select' function typically offered for managing multiple socket connections is provided as an extension to KPN semantics. This process accepts an arbitrary number of inputs of the same type and has a single output that returns any token on any input at any time. This out-of-order merge is represented using the percent sign '%' character.

main
	source
	^ (procA) procB
	%
	printSink

alt text

The other common variety of joining multiple streams of information is a reduce-across operator, folding a function across the sequence generated by concat'ing a token received from each stream. Addition and multiplication are commonly used reducing operators. Assuming all inputs are synchronous with respect to eachother, an output token is produced synchronous to the input tokens. This fold-across operator is represented using the forward slash '/' character prefacing a process identifier. The process is provided a list of stream inputs to reduce across and a stream output on which to send the results.

main
	source
	^ (procA) procB
	@xa @xb
	/* @oa @ob
	printSink

alt text

Arbitrary Connections

RatPak also offers arbitrary named stream connections. A stream must have exactly two references, an input, and an output. The connection input is positioned downstream of the process from which it accepts tokens. The connection output is provided as an argument to a process. A connection name is prefaced by the at-sign '@' character and either 'x' for an input connection or 'o' for an output connection.

main
	source
	/+ @oa @ob
	Z
	^ (*-1e-3) (@xa) (@xc)
	@xb
	printSink @oc

alt text

Reduction Across Streams

In the previous sections, the forward slash / was used to preface the summation and multiplication operators to indicate that the application reduces the dimensionality from two (or more) input stream to exactly one output stream. This syntax allows the concise definition of arbitrarily complex summation and multiplication nodes.

Processes

Processes used in RatPak are defined in Rust, either as public functions in an included library, or using RatPak to inline a Rust anonymous expression as a stream manipulation. Rust functions used in RatPak should have a camelCase name starting with a lower case letter. The file 'boilerplate.rs' imports a majority of LibRedio into scope, providing basic DSP and decoding utilities. Rust functions can have any number of inputs, outputs, and arguments, but they must be in that order. Multiple inputs or outputs are passed as a Vec<Receiver> or Vec<Sender> respectively. Processes should not terminate in normal operation, and should rely on blocking calls to recv() for synchronization purposes.

Externally Defined

pub fn printSink<T: std::fmt::Show+Send>(u: Receiver<T>) {
        loop {
                println!("{}", u.recv())
        }
}

This is a sample function from ratpak's standard library that accepts an infinite stream of tokens of arbitrary type implementing the fmt::Show trait in Rust. It has the following invocation:

main
	source
	printSink

where source is any process producing a stream of tokens - hardware abstraction, oscillator, etc.

Inlined

Process in RatPak can also be inlined as Rust lambda expressions of an appropriate format. The following two terminating and two nonterminating cases have syntax defined.

|T| -> T
|T| -> U
|Messages<T>, Sender<U>|
|Sender<T>|

These options allow a developer to specify terse transformations of homogenous and heterogenous type, as well as terse relationships between an object representing the infinite list of input tokens and an output stream. Of these three options and their variants, only the third allows local state between successive tokens, making it of significant use in parsing. Note that the third structure should never terminate. This third option is often used in conjunction with Rust iterator-style manipulations. Inlined Rust expressions are surrounded in single quotes ' and prefaced by an exclaimation mark ! for the homogenously typed case, an ampersand & for the heterogenously typed case, a left curly bracket { for the nonterminating SISO process definition, or a tilde ~ for the definition of a source block.

The terminating expressions can be modified by a prepended comma , to indicate the application of the method across a vector.

Built-Ins

There are also a set of builtin processes useful for common activities in RatPak.

The unit delay Z first sends a zero 0 then passes input to output. In feedback this acts as a unit delay shifting a stream against itself, and can be used to build filters and oscillators. It accepts an optional argument for the first value, facilitating nontrivial cases and allowing the concise implementation of well-definied initial conditions.

A binary converter B accepts a list of field widths and a stream of sequences of binary values and returns a sequence of integer values, each composed of its respective number of bits.

The shaper function $ accepts an integer argument l and a stream of T, returning a stream of Vec<T>, each token of length l. Tokens are accumulated until there are l sequential tokens of T. The resulting sequence Vec<T> is sent and reset. The shaper function can be modified by a prepended comma , to translate from Vec<T> to T. It can be prepended by the question mark ? to operate upon an input stream of Option<T>, accumulating until it has a vec of l tokens followed by a None.

About

Discrete Time Process Networks

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published