Streaming component combinators

1.1 Related work

The importance of streaming transformations of markup has long been recognized. There has been ongoing work on creating streaming implementations of standardized markup-processing and querying languages, XPath [ Peng 2005 ][ Olteanu 2004 ], XSLT and XQuery [ Florescu 2004 ] [ Fegaras 2002 ] among them. However, the design of these languages is such that no implementation can guarantee streaming behaviour. Other efforts have been focused on defining streaming subsets of the aforementioned languages, as well as specially-designed languages that fully support streaming processing, like OmniMark [ OmniMark 2006 ], Sequential XPath [ Desai 2001 ] and Streaming Transformations for XML [ Becker 2003 ].

Streaming component frameworks seem to have been reinvented several times. Most of these frameworks, however, are designed to work on coarse-grained filter components. Some examples are XPipe [ XPipe 2002 ], XML Pipeline [ XML Pipeline 2002 ], Cocoon [ Apache 2006 ], and iFlow [ Lui 2000 ]. Possible exceptions are STnG [ Krupnikov 2003 ], as well as THREADS [ Morrison 1994 ] which can apply components to arbitrary parts of the framework input. However, none of the listed frameworks seem to try to formally classify the components into abstract classes, nor define any generic component combinators that would operate on instances of component classes.

On the other hand, plenty of work has been done on combinator frameworks in general, especially in the functional programming language community. The parser component combinators [ Hutton 1996 ] are closely related to this work. A nice implementation of a parser combinator library is Parsec [ Leijen 2001 ]. The main difference between a parser combinator framework and a streaming component combinator framework, such as the one presented here, is that parser frameworks are streaming only on their input side. On the output side, they produce a well-defined and structured result from the input source, typically a parse tree. This is possible only because a parser deals with highly structured and constrained input. Once some input is parsed and the result constructed, the input is no longer necessary. In contrast, a streaming component combinator framework has to deal with input that is only weakly structured; in many cases the only meaningful result of processing any single component is just a rearrangement of the component's input.

There are also combinator frameworks for XML document processing, HaXML [ Wallace 1999 ] for example. While many of the combinators defined by HaXML resemble ours, there are two important differences: HaXML combinators operate exclusively on filters and ad hoc Haskell function types, and HaXML operates on a parsed document tree and therefore is not streaming. The latter constraint appears to be shared by all XML combinator frameworks implemented in Haskell today. The XPath implementation in Scheme, SXPath [ Lisovsky 2003 ], provides combinators that operate on nodeset-transforming functions, which are also not designed for streaming.

The most recent work [ Shivers 2006 ] finally applies the combinator approach to streaming components by using continuation passing to transfer control. The early results are promising, but most attention is still devoted to simple linear pipelines of filter components.

2.1 Filters

A filter is a streaming component with one data source and one data sink. The concept of streaming filter components has been recognized for some time, and is a part of programmers' vocabulary in many areas. A filter component takes a data stream as its input, transforms it, and produces another data stream as its output. The best-known example of filters is probably the Unix piping model [ Raymond 2003 ].

A filter component has a responsibility to consume its whole input. It is not allowed to simply terminate in the middle of processing of its input. If one filter in a pipeline terminates, the whole pipeline dies with it.

In OmniMark, a filter component can be represented as an abstract data type with a single operation apply-filter, illustrated below in figure 1:

   export record filter

   export dynamic overloaded function
      apply-filter value filter        filter
              from value string source filter-source
              into value string sink   filter-sink
   as
      not-reached message "The base function apply-filter must be overridden!" 

A concrete filter implementation must extend the abstract filter type and override its apply-filter method. Several concrete filter examples are given next.

2.2 Splitters

A splitter is a streaming component with one data source and two sinks. A pure splitter component is not supposed to modify its input in any way; instead, it streams portions of its input stream to either of its two outputs. Every bit from the input stream has to be present in one or the other of the output streams. Secondly, the outputs have to be properly interleaved. Another way of stating the invariants is to say that if the two sinks of any pure splitter are connected together, the component acts as an identity transform.

The concept of splitters, together with the operations that can be applied to them, is the only new technical contribution this paper has to offer. The streaming component frameworks have been researched and built before, but the emphasis has mostly been on filters. That is not to say that no framework contained splitter components before. The previous work on streaming pipeline frameworks has mostly seen splitters as large, ad hoc components that must be provided by the user.

In OmniMark, a splitter component can be represented as an abstract data type with a single operation split that takes one data source and two sinks as arguments:

   export record splitter

   export dynamic string sink function
      split (value splitter    sp,
             value string sink true,
             value string sink false)
   as
      not-reached message "The base method split must be overridden!" 

The concrete splitter instances must extend the base splitter type and override the method split. In the examples that follow, the OmniMark code will be elided for brevity.

3.1 Filter combinators

• >> The most obvious and well-known combinator of streaming components is the pipe operator. It takes two filters and combines them together into a single filter component. The resulting component acts as a composition of the two argument filters: it passes the input to one filter, the output of that filter is passed to the other filter, and its output becomes the output of the combined component.
• join combinator also combines two filters into a single filter. However, this combinator arranges the two filters in parallel. The input of the resulting filter is replicated to both component filters in parallel, and the output of the resulting filter is a concatenation of the two component filters' outputs.
  To do its job, the join combinator uses two non-standard components. The tee component, known from the Unix environment, replicates its input into two parallel streams. This component is neither a filter nor a splitter, so no generic component combinator can use it. Another non-standard Unix-style component is cat taking two (or more) inputs and concatenating them in order. Again, this component cannot be used by generic component combinators. However, in place of these two components we can provide the join combinator that combines two filters into another filter component. The combined component internally uses tee to replicate its input to both of the filters it contains and then cat to concatenate the filters' outputs. The result behaves as an ordinary filter and can be used by other combinators. Notice, however, that the result filter of join is not completely streaming, as it has to buffer the output of the second component filter until the end of the input.

3.2 Pseudo-logical splitter combinators

A pure splitter component can be thought of as a representation of a logic predicate. The portion of the input that the splitter sends to one of its two sinks is taken to satisfy the predicate, and the input that goes to its other sink does not. Having this picture in mind, the following splitter combinators become obvious.

• The ! (not) operator simply reverses the outputs of the argument splitter. In other words, data that the argument splitter sends to its true sink goes to the false sink, and vice versa.
• The >& operator sends the true sink output of its left operand to the input of its right operand for further splitting. Both operands' false sinks are connected to the false sink of the combined splitter, but any piece of input to get into the true sink of the combined component data must pass both splitters. Figure 3 illustrates this.

   ; record declaration
   declare record and-splitter extends splitter
      field splitter left
      field splitter right

   ; constructor definition
   export overloaded splitter infix-function
         value splitter left
      >&
         value splitter right
   as
      local and-splitter result

      set result:left to left
      set result:right to right
      return result

   ; split method overriding
   define overriding string sink function
      split (value and-splitter s,
             value string sink  true,
             value string sink  false)
   as
      using output as split (s:left, split (s:right, true, false), false)
         output #current-input 

• The >| splitter combinator is a mirror image of >& combinator, as illustrated by figure 4. Its input can get to its false sink only by going through both argument splitters' false sinks.

   ; ... skipping the record and constructor declaration
   ; split method overriding
   define overriding string sink function
      split (value or-splitter s,
             value string sink true,
             value string sink false)
   as
      using output as split (s:left, true, split (s:right, true, false))
         output #current-input 

Note that the >& and >| operators are not exact equivalents of the corresponding Boolean and/or operators. In particular, they are commutative only when their two argument splitters agree on what forms a unit of input, i.e., when the input stream is a uniform sequence of records. Most markup splitters do not satisfy this property. For example, the expression xml-element-named "A" >& xml-element-content >& xml-element-named "B" is an equivalent of the XPath expression A/B, which is obviously not commutative.

3.3 Flow-control combinators

Since approximating a splitter as a logic predicate ( i.e., a boolean expression) turned out to be productive, we can try digging deeper into our intuition for useful metaphors. For example, we can see a filter component as an imperative statement. A filter modifies the stream that flows through it, much like an imperative statement that modifies the state surrounding it. The piping operator >> would then be an equivalent of a statement sequencing operator. Having both imperative statements and Boolean expressions, the natural thing to look for next would be an equivalent of the flow-control statements.

• The if combinator takes a splitter and two filters and combines them into a single filter component, as shown in figure 5. The resulting filter applies one argument filter to one portion of the input and the other filter to the other portion of input, depending on where the splitter routes the data.

   ; apply-filter method overriding
   define overriding function
      apply-filter value if-filter     filter
              from value string source filter-source
              into value string sink   filter-sink
   as
      using output as split (filter:splitter,
                             filter:left >> filter-sink,
                             filter:right >> filter-sink)
         output filter-source 

The combinators where and unless are simpler versions of the if combinator, having one of the two filters be as-is. The select combinator uses the as-is and suppress filters as the true and false sinks, respectively. In effect, the select combinator converts a splitter into a filter which retains only the true portion of the input. The three combinators can be more formally defined as follows:

• splitter where filter → if splitter then filter else as-is
• splitter unless filter → if splitter then as-is else filter
• select splitter → suppress unless splitter

A combinator language is point-free by definition, so we cannot use component names or labels to achieve looping and recursion. If we want our component networks to be able to form loops, we need more flow-control combinators.

• The recursive combinator while, illustrated in figure 6, feeds the true sink of the argument splitter back to itself, filtered by the argument filter. The false sink of the splitter is passed on unmodified. The combinator until is the mirror image of while.

   ; apply-filter method overriding
   define overriding function
      apply-filter value while-filter  self
              from value string source filter-source
              into value string sink   filter-sink
   as
      do scan filter-source
      match lookahead any
         using output as split (self:splitter,
                                self:filter >> self >> filter-sink,
                                filter-sink)
            output #current-input
      done 

• The recursive combinator nested combines two splitters into a mutually recursive loop acting as a single splitter. The true sink of one of the argument splitters and false sink of the other become the true and false sinks of the loop. The other two sinks are bound to the other splitter's source. This particular combinator does not have a corresponding flow-control equivalent in the world of programming languages. The reason for this is that the use of nested only makes sense on hierarchically structured streams. If we gave it some input containing a flat sequence of records, and assuming both component splitters are deterministic and stateless, a record would either not loop at all or it would loop forever.

   ; split method overriding
   define overriding string sink function
      split (value nested-splitter self,
             value string sink     true,
             value string sink     false)
   as
      do when #current-input matches (lookahead any)
         using output as split (self:upper-splitter,
                                true,
                                split (self:lower-splitter,
                                       split (self, true, false),
                                       false))
         repeat scan #current-input
         match any => one
            output one
         again
      done  

3.4 Active combinators

Each of the combinators defined so far builds a streaming network out of its argument components, and then lets the network do its job. The combinator itself plays no role after the initial configuration. This property guarantees that the combinator is completely generic: the type of input that can be processed by the network is constrained only by its components, not by the combinators applied to them.

The combinators defined next are different; they are still generic enough to be used on any kind of input, but they also actively process the input stream. They achieve these seemingly contradictory goals by using their splitter argument to determine the structure of the input. Every contiguous portion of the input that gets passed to one or the other sink of the splitter is treated as one section in the logical structure of the input stream. What is done with the section depends on the combinator, but the sections, and therefore the logical structure of the stream, are determined by the argument splitter alone.

• The combinator first takes a splitter as an argument and returns another splitter. The result behaves the same as the argument splitter up to and including the first portion of the input which goes into the argument's true sink. All input following the first true portion goes into the false sink.
• The result of the combinator last is a splitter which directs all input to its false sink, up to the last portion of the input which goes to its argument's true sink. That portion of the input is the only one that goes to the resulting component's true sink.
  The splitter returned by the combinator last has to buffer the previous two portions of its input, because it cannot know if a true portion of the input is the last one until it sees the end of the input or another portion succeeding the previous one.

• The foreach combinator is similar to the combinator if in that it combines a splitter and two filters into another filter. However, in this case the filters are re-instantiated for each consecutive portion of the input as the splitter chunks it up. Each contiguous portion of the input that the splitter sends to one of its two sinks gets filtered through the appropriate argument filter as that filter's whole input. As soon as the contiguous portion is finished, the filter gets terminated.
• The having combinator combines two pure splitters into a pure splitter. Again, one splitter is used to chunk the input into contiguous portions. Its false sink is routed directly to the false sink of the combined splitter. The second splitter is instantiated and run on each portion of the input that goes to first splitter's true sink. If the second splitter sends any output at all to its true sink, the whole input portion is passed on to the true sink of the combined splitter, otherwise it goes to its false sink.
• The having-only combinator is analogous to the having combinator, but it succeeds and passes each chunk of the input to its true sink only if the second splitter sends no part of it to its false sink.

Note that the combinators having and having-only must buffer each complete chunk of input until the second splitter tests it.

One reason buffering matters is that flow-control combinators require their argument components to agree on which parts of the stream get buffered and at which point they get flushed. If one of the subcomponents buffers a part of its input and the other does not, the output of the combined component may be improperly interleaved. The following filter expression is one such example:

if xml-element-content then as-is else select last all-true

Both branches of the expression produce identical output, so the whole expression may seem equivalent to as-is, but because all the element tags get buffered by last all-true they will be output after the element content. We can synchronize the two branches by using the foreach combinator instead of if.