[FoRK] taxonomy of composition and coordination (thinking out loud...)

Stephen D. Williams sdw at lig.net
Mon Dec 14 18:43:56 PST 2009

Jeff Bone wrote:
> ...
> Really, the difficulty here is in really rounding out e.g. Rohit's 
> work on similar issues to capture all the critical dimensions of 
> composition and coordination.  Such a taxonomic set of features would 
> be useful (academically, and perhaps practically) in its own right, 
> but my goal is really more along the lines of understanding how to 
> make composition as easy as e.g. pipes but more general and flexible, 
> for use in my own pet project and for my own understanding.

I've thought and talked about working on an "upgrade" for the Unixen 
shell also.  On a completely different level, I did an architecture and 
design solving the composition problem a few years ago  - something like 
a confluence of grid/HPC, map/reduce, P2P, SOA, etc.  The goal of that 
system was very loose coupling, i.e. fully decoupled "tools" as 
contrasted with half-decoupled SOA/SOAP and most other systems.  Among 
other things, I combined the ideas of Unix filter tools with a 
macro-level rule engine that controlled flow via message (data blob) 
metadata pattern matching and a distributed pull work queue with 
bidding, timeout, and resilient re-execution, operating on an immutable 
temporal distributed datastore.  Each compute node was normally also a 
storage node.
> I.e., what *is* it that makes reuse in e.g. the shell so easy, and so 
> hard everywhere else, and how can we generalize that and make it even 
> stronger?
Shell programs generally don't know about each other and are not 
integrated with each other.  They are input+args+algorithm = output(s).  
I see these next steps: structured interchange (typed graphs, 
OGDL+types, etc.), option for complex communication connections (managed 
by the shell, just like piping is, not the tool/process, should include 
both pipeline, bidirectional pipeline, and more complex options - 
mux/demux, etc.), option for complex communication architecture in 
addition to pipelines (arbitrary networks, map/reduce, services), option 
to be either a process or thread or method (pseudo-thread in a message 
architecture), and various kinds of efficient context.  Memcached is one 
kind of context.  Databases of various kinds are another.  There should 
also be one or more flexible event / metadata matching, filtering, and 
mapping capabilities.  It should be possible to do zero copy as much as 
possible.  It should be possible to avoid serialization and parsing to a 
large extent (esXML/esDOM etc).  Perhaps swizzling should be integral.  
Scoping should be pervasive.  Transactions should be possible at a 
number of levels, or globally, or scoped in various ways (esXML/esDOM 
for the memory/process, etc.).  This is not the same as fully-general 
transactional memory, but rather a generational / delta data structure 
that is directly modifiable.

My preferences:
> It seems that there are several potential dimensions of composition:
> (1)  is there some kind of reified "connection" or channel between 
> communicating components?  (Vs. "just" messaging.)
Most components shouldn't know about anything more than the data needed 
to complete some operation, i.e. grep etc. Communication channels should 
generally be async, pipelined, message oriented, multi-channel 
underneath, reliable but fail-fast best effort unless otherwise 
indicated (i.e. a "tee"-like component might create a persistent queue 
that could support auto-recovery).  The "shell" should normally do all 
communication addressing and handling.  The tool/component should have 
even less I/O handling than Unixen tools.
> (2)  do all components support the same set of interfaces?
There should be a few standard types and then the ability to have 
specialized / arbitrary connector interfaces for 'external' use.
> (3)  is communication synchronous (blocking, implying return value) or 
> async (non-blocking, no rv per se)
Async should be preferred, sync for simplicity.  Return value / result 
processing should normally be by another step, with context as needed.  
It could be the same tool/thread or another (bidirectional messages, etc.)
> (4)  is there flow control, and how is it handled?
The "shell", which handles most "normal" communication, should enforce 
various policies, buffering, flushes, memory management, etc.
> (5)  do components know each other by name?  What kinds of names are 
> used?
Normally they don't know each other at all!  Fully decoupled if and when 
possible.  Coupling is the job of the shell, just like Unix.  RPC-like 
"side" communication should be handled in one or more 
pattern/filter/type ways which can be mapped efficiently (and 
semi-statically) by the shell.  Exceptions of course, just like popen() 
now.  At least that is the goal.

For real world, that doesn't solve much. 
> (6)  if not name-based coupling, what?  (channels;  generative 
> dispatch;  ...?)
The shell (and sometimes the tool) does deal in names / handles of some 
kind.  URL/URIs, etc.  There are several reasonable alternatives.
> (7)  what's the relationship between the transport-level metaphors and 
> the higher-level ones?
> (8)  sharing of state, mutability of data, etc.
Shared nested context in scopes, transactions, and mutable / immutable 
modes perhaps.
> etc.  (Again, not presenting this as a complete set, or consistent.  
> Just thinking out loud...)
> BTW, thanks to Sean for reminding me about QNX.  Thinking about 
> explicit element-wise node addressing has generated some interesting 
> questions / ideas over the last 24 hours...
> In particular, one of the things I've wrestled with for a while now is 
> formalizing the notion of a UNIX-like process.  What is it, exactly?  
> The sort of rough definition I've been working from is that it's a 
> partial function from streams, args, etc. (i.e. tuple of (stdio, fds, 
> env, args)) to same (sans args, plus return value).  The curried 
> function is reified by providing e.g. args and env, then yields a 
> function from streams to streams + argv.  That's not really 
> satisfactory.  In particular return values are a problem.  I'm sure 
> it's in the more general literature, but (aha moment!) pure functions 
> with return values can be modeled in the pi-calculus with uniqueness 
> types as processes that have a one-shot return value channel.
Since a "UNIX-like process" can mean anything, I try to think in terms 
of prototypical tool-types.  A "Unix filter" is a pretty clear choice.  
In "UFng" (above), it should support bidirectional (and more) 
communication paradigms.  In a large set of those cases, the key to 
modeling the interaction is context.  Whether it is a thread waiting on 
a synchronous RPC or a pseudo-thread (i.e. some data structure 
representing a logical context that will be materialized in a thread 
later), the state of that part of a program is the context of the 
communication.  So, a web application communication stack could be:

Bidirectional pipeline: (|| could indicate bidir, or it could be 
inferred by the tool, or command line...  Here, it would make sense for 
tcp to indicate to the shell that it needed a new real or session 
context (which could be a pipeline channel) fork of the rest of the 
pipeline. -C is context ID.)
tcp -L -h lig.net -p 80 || tls server.key || supertee -t http -o 
http.log || apachetool -C lig.net -p /date -c "date" -p "/urlshortener" 
-c "urlshort -C lig.net"

Or unwrapped and paired via context:
tcp -C lig.net -L -h lig.net -p 80 | tls -C lig.net server.key | 
supertee -t http -o httpin.log | apachetool -C lig.net -p /date -c 
"date" -p "/urlshortener" -c "urlshort -C lig.net" | supertee -t http -o 
httpout.log | tls -C lig.net server.key | tcp -C lig.net -L -h lig.net -p 80

The first is clearly nicer most of the time, however the latter allows 
more complex relationships in process / data flow.  One other major 
option is to simply name each endpoint with each command as a discrete 
definition, allowing the shell to stitch them together arbitrarily.

tcp --ID TCP -O TLS

Ideally, you use the first style for much of the time, only resorting to 
the other two (or more) options for the outlier cases.  And you allow 
use of all methods in the same "command line".

However, this only solves simple situations where components are already 
mostly pipeline ready because of their inputs/outputs.  You can get 
pretty far by supporting various levels of metadata tagging of the 
stream, interaction between tools once they have been connected (content 
and encoding negotiation, etc.), and data scoping.  A la esXML/esDOM, 
the idea is to create a writable view (via a copy on write layer when 
transactional) into a larger object / graph space.  In pipelines like 
above, it could be done via a scope operator.

More of a language is needed to handle the rest.

Note in all of the above, the data need not be constantly copied, 
parsed, or serialized.  Likewise, each tool can be a process, thread, or 
function call, both local and remote in various senses, where network 
remote requires some already-present service perhaps.
> More thinking out loud...
I hear you.

> jb

More information about the FoRK mailing list