dataflow programming from shell interpreter
Tim Climber
XML-coded trees or graphs instead of one-line strings in stdin/
stdout.Or LISP S-expressions. New set of utilities for filtering such
streams, grep for XML trees, etc. Building environment for dataflow
programming from shell interpreter.
Any interesting papers exist on this topic?
erik quanstrom
not on xml per se. but rob did some work with structured
regular expressions that sound a lot like what you describe,
except there is no xml.
Rob Pike, Structural regular expressions.
Proceedings of the European UNIX User's Group Conference. EUUG, Helsinki, Finland.
doc.cat-v.org/bell_labs/structural_regexps/se.pdf
- erik
Steve Simon
> programming from shell interpreter.
This is always somthing I have wanted to do for video stream
processing, writeing a limited proceedural language which can
be refactored as a dataflow graph for efficent implementation
(of video processing).
I always imagined it as a shell-like language rather than actually
using an existing shell.
Sadly this never got further than ideas and a few email exchanges with Byron.
If you find any papers describing such things I would be interested
in any references - I think I found some stuff from Berkley in the
early 1990s from their work on a reconfigurable FPGA based image
processing engine.
-Steve
Eric Van Hensbergen
Details still developing but the PODC paper gives you an idea of
direction.
-Eric
Sent from my iPhone
Aharon Robbins
See the xmlgawk project, xgawk.sourceforge.net, for modifications to gawk that
add xml parsing and allow you to work XML nodes instead of records.
Arnold
--
Aharon (Arnold) Robbins arnold AT skeeve DOT com
P.O. Box 354 Home Phone: +972 8 979-0381
Nof Ayalon Cell Phone: +972 50 729-7545
D.N. Shimshon 99785 ISRAEL
Eric Van Hensbergen
>> Have a look at PUSH (PODC 2009)
>
> could you send me a link to the paper
>
http://portal.acm.org/citation.cfm?id=1582780&dl=GUIDE&coll=GUIDE&CFID=64334509&CFTOKEN=48344220
If you don't have a subscription to the ACM Library, you can grab a copy here:
https://docs.google.com/fileview?id=0B857VbDiq8hOMmY4ZjVkNGQtYmQwZi00NzI5LWJjMTQtYzYxYzBkYTc0ZTJk&hl=en
-eric
Tim Newsham
> processing, writeing a limited proceedural language which can
> be refactored as a dataflow graph for efficent implementation
> (of video processing).
I'm sure you could do some stuff, but lots of interesting
video and audio processing involves a graph thats not
linear, sometimes even with cycles in it. There are lots of
systems out there that let you hook up arbitrary graphs of
video or audio processing modules. Many of em are gui based,
but some are command language based.
> -Steve
Tim Newsham | www.thenewsh.com/~newsham | thenewsh.blogspot.com
Aharon Robbins
I think V10 also had some pipeline utils for manipulating images.
In article <89568f5cfeef17d6...@quintile.net>,
Steve Simon
> I think V10 also had some pipeline utils for manipulating images.
Indeed, however I make a firsm distinction between image proccessing (2d)
and video processing (3d).
In Video processing the image sequences can be of arbitary length, the
processing is often across several fields, and, because we want our
results ASAP tools should present the minimum delay possible (e.g. a
gain control only needs a one pixel buffer).
Aditionally image processing pipelines often have nasty things like feedback
loops and mixing different paths with differing delays which all need special
care.
We have a package of good old unix tools developed jointly by us and the BBC
which works as you might expect
cat video-stream | interpolate -x 0.7 -y 0.3 | rpnc - 0.5 '*' | display
however this can get quite ugly when the algorithm gets complex.
We need to cache intermediate results - processing HD (let alone 2k 3d) can
get time consuming so we want an environment which tee's off intermediate results
automagicially and uses them if possible - sort of mk(1) combined with rc(1).
It is also a pain that its not easy to work at different scales i.e. writing
expressions to operate at the pixel level and using large blocks like interpolate,
the rpnc is an attempt to do this but its interpreted (slow).
a restricted rc(1)-like language which supports pipelines,
and scalar (configuration) variables combined with a JIT compiler
(in the vein of popi) looks like a solution but I have never go further
than wishful thinking.
-Steve
Andy Spencer
> processing, writeing a limited proceedural language which can be
> refactored as a dataflow graph for efficent implementation (of video
> processing).
This sounds a lot like how GStreamer operates. An example from the
gst-launch manpage:
gst-launch filesrc location=music.mp3 ! mad ! audioconvert ! vorbisenc ! oggmux ! filesink location=music.ogg
I'm not sure they've done as much work on a procedural language, but
they have a good set of 'plugins', as they call them.
Andy Spencer
I worked on an undergraduate thesis last year about dataflow
programming. The syntax for our language was similar to UNIX shells, but
it was intended to be compiled language.
For more complex datatypes, I don't think the serialization format
matters very much. You could store the data in XML, S-expressions, YAML,
etc. As long as you have a program/function to read each of these
formats into a nested data structure you can use the same set of
utilities to process any of them.
For parallelism, you'll need to be able to begin outputting the data
structure while the original data it is still being read in. With
complex data, I'm not sure if it would be better to use a common format
through a character pipe, or to use some other form of IPC where the
nesting is maintained during transmission.
For reference, here's a copy of my thesis:
http://andy753421.ath.cx/linked/curin.pdf
Eris Discordia
possible answer to the video processing question? Filter graphs can be
generated by any program, GUI or CLI, and fed to DirectShow provided one
learns the in and out of generating them.
The OP's question, too, finds one answer in MS PowerShell where instead of
byte streams .NET objects are passed between various tools and a C#-like
shell language is used for manipulating them. .NET objects can at any point
be serialized/deserialized to/from XML using stock classes and routines in
System.Xml.Serialization namespace.
Just a note that at least some implementations of both ideas exist in
production settings.
--On Tuesday, January 19, 2010 15:40 +0000 Steve Simon <st...@quintile.net>
wrote:
Patrick Kelly
On Jan 20, 2010, at 4:13 PM, Eris Discordia <eris.di...@gmail.com>
wrote:
> Aren't DirectShow filter graphs and programs like GraphStudio/
> GraphEdit one possible answer to the video processing question?
> Filter graphs can be generated by any program, GUI or CLI, and fed
> to DirectShow provided one learns the in and out of generating them.
>
> The OP's question, too, finds one answer in MS PowerShell where
> instead of byte streams .NET objects are passed between various
> tools and a C#-like shell language is used for manipulating
> them. .NET objects can at any point be serialized/deserialized to/
> from XML using stock classes and routines in
> System.Xml.Serialization namespace.
Why XML? Surely there are better options.
roger peppe
put into a tool in inferno that i called "alphabet".
it works (with a few rough edges).
http://www.vitanuova.com/inferno/man/1/sh-alphabet.html
for an example of something it can do that's not possible
with a conventional shell pipeline, see
http://www.vitanuova.com/inferno/man/1/alphabet-fs.html
one of these days i intend to dust it off and take
it to the next level - i've had a few ideas in the meantime.
don't hold your breath though.
2010/1/20 Patrick Kelly <kameo...@gmail.com>:
>
>
> On Jan 20, 2010, at 4:13 PM, Eris Discordia <eris.di...@gmail.com>
> wrote:
>
>> Aren't DirectShow filter graphs and programs like GraphStudio/GraphEdit
>> one possible answer to the video processing question? Filter graphs can be
>> generated by any program, GUI or CLI, and fed to DirectShow provided one
>> learns the in and out of generating them.
>>
>> The OP's question, too, finds one answer in MS PowerShell where instead of
>> byte streams .NET objects are passed between various tools and a C#-like
>> shell language is used for manipulating them. .NET objects can at any point
>> be serialized/deserialized to/from XML using stock classes and routines in
maht
> Aren't DirectShow filter graphs and programs like
> GraphStudio/GraphEdit one possible answer to the video processing
> question? Filter graphs can be generated by any program, GUI or CLI,
> and fed to DirectShow provided one learns the in and out of generating
> them.
passes, one to decompose and one to compose at the required bitrate, DVD
mpeg I'm looking at you.
Straying off the topic a bit wrt plan9 but here's an interesting read
Skip Tavakkolian
> possible answer to the video processing question? Filter graphs can be
> generated by any program, GUI or CLI, and fed to DirectShow provided one
> learns the in and out of generating them.
DirectShow is COM; source/mux/transform/sink filters must provide a
number of interfaces (e.g. IFileSinkFilter); other components
(e.g. GraphBuilder) are there to make it easier to hook them
together.
i don't think a direct mapping of COM to Plan 9 fs model is
unnecessary. for example, instead of mapping every control or
configuration interface and method to synthetic directories and files,
a single ctl file will do. something like this seems sufficient:
/ctl # e.g. accepts run, stop, etc. returns: paused, #outputs, config, etc.
/event # instead of callback notification
/ipin/clone
/ipin/n/ctl
/ipin/n/event
/ipin/n/data
/opin/clone
/opin/n/ctl
/opin/n/event
/opin/n/data
for a special purpose kernel one could add a driver and a fancy new
hook syscall (similar to pushssl and '#D') that would hook two fd's
together to eliminate the need for a user proc to transfer between
ipin/?/data and opin/?/data.
Eris Discordia
> unnecessary. for example, instead of mapping every control or
> configuration interface and method to synthetic directories and files,
> a single ctl file will do.
It didn't occur to me at all that anyone would want to implement DirectShow
or anything like that on Plan 9. Anyhow, I suppose if anyone's going to do
that they should probably first work on fast display drivers that leverage
modern cards' overlay capabilities and a facilitating media infrastructure
equivalent to DirectX. On run-of-the-mill PCs good video works depends a
lot on software support of video hardware, of course.
The logic inside most DirectShow filters either is open source (like
ffdshow) or has good open source equivalents. The interfacing (COM), as you
have noted, and input/output, which is hardware-dependent and therefore
probably weakly developed in Plan 9 (I don't really have an idea, just
guessing), are the missing bits from a DirectShow-like (multi-pipe) video
processing pipeline on Plan 9.
--On Thursday, January 21, 2010 13:36 -0800 Skip Tavakkolian
Sam Watkins
This is interesting. I'm not keen on XML (except for actual markup of
documents) but dataflow programming is interesting and worthwhile.
I like graphical programming (with nodes and arcs) for this, but programs can
also be represented as plain text. I haven't implemented much to do with this
yet, but I have thought about it at length, determined what basic operators and
forms can be used for lambda, math, sets, lists etc.
I'm interested in relational / logic / dataflow programming where for example:
a + b c
expresses a relationship.
If b and c are known, a can be calculated: a = b + c
If a and b are known, c can be calculated: c = b - a
This can lead to much shorter code. Immediately you can see there is no need
for a separate subtraction operator, it is just a different mode of addition.
Likewise / is only a mode of *. Raising to the power, taking a root,
exponentiation and logarithms are different modes of a single operator.
+ - * / ^ log becomes + * ^
One basic operator is needed for sets: the discrete union, which is like a sum:
A B # C
means A OR B = C, A AND B = empty
Various list relationships such as reversal, membership, head, tail, sublist,
etc. can be represented simply with a single list symbol.
Operators can be defined using lambda closure (a box). An operator over
paramters A, B, C, D is effectively (from some point of view) a set of all
tuples satisfying the contained relationships { (A,B,C,D) }
So the "lambda" box thing creates a set of possible values from a free
variable. It can be used in reverse to produce a free variable that is a
member of a set. (also, an instance of an operator). Lambda, application, set
definition, and set membership are the same thing (expressed by a box).
A single processor might perform both splitting and joining of text, depending
which direction you feed the data to it, etc. Or parsing and formatting, maybe
encoding and decoding video, etc. There will be some components of the program
used only for encoding, some only for decoding, but much can be shared between
them.
I am not fully sure how to integrate the dataflow system with the relational
system, but it seems like these models would go very well together. Perhaps an
abstract model of a stream (like in Haskell) would be the way, perhaps a lazy
list achieves this already. I need to think more about this.
Sam