[9fans] dataflow programming from shell interpreter

[9fans] dataflow programming from shell interpreter

[Tim Climber]

Is this possible for UNIX philosophy to develop further? Let's say,
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?

Re: [9fans] dataflow programming from shell interpreter

[Steve Simon]

> Building environment for dataflow
> 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

Re: [9fans] dataflow programming from shell interpreter

[Eric Van Hensbergen]

Have a look at PUSH (PODC 2009)
Details still developing but the PODC paper gives you an idea of
direction.

     -Eric

Sent from my iPhone

On Jan 18, 2010, at 10:58 AM, Tim Climber <climber.tim@gmail.com> wrote:

> Is this possible for UNIX philosophy to develop further? Let's say,
> 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?
>

Re: [9fans] dataflow programming from shell interpreter

[Aharon Robbins]

In article <c563b2f7-92ac-463a-864c-267721ddb30a@k35g2000yqb.googlegroups.com> you write:
>Is this possible for UNIX philosophy to develop further? Let's say,
>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?

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

Re: [9fans] dataflow programming from shell interpreter

[Tim Newsham]

> 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'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

Re: [9fans] dataflow programming from shell interpreter

[Aharon Robbins]

The PBM utilities (now net pbm) did something similar for bitmaps.

I think V10 also had some pipeline utils for manipulating images.

In article <89568f5cfeef17d6b1a79f12daeea5c6@quintile.net>,
Steve Simon <steve@quintile.net> wrote:
>> Building environment for dataflow
>> 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
>


--
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

Re: [9fans] dataflow programming from shell interpreter

[Steve Simon]

> The PBM utilities (now net pbm) did something similar for bitmaps.
> 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

Re: [9fans] dataflow programming from shell interpreter

[Andy Spencer]

[-- Attachment #1: Type: text/plain, Size: 554 bytes --]

> 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).

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.

[-- Attachment #2: Type: application/pgp-signature, Size: 205 bytes --]

Re: [9fans] dataflow programming from shell interpreter

[Andy Spencer]

[-- Attachment #1: Type: text/plain, Size: 1275 bytes --]

> Is this possible for UNIX philosophy to develop further? Let's say,
> 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?

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

[-- Attachment #2: Type: application/pgp-signature, Size: 205 bytes --]

Re: [9fans] dataflow programming from shell interpreter

[Eris Discordia]

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.

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 <steve@quintile.net>
wrote:

>> The PBM utilities (now net pbm) did something similar for bitmaps.
>> 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
>

Re: [9fans] dataflow programming from shell interpreter

[Patrick Kelly]

On Jan 20, 2010, at 4:13 PM, Eris Discordia <eris.discordia@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.
>
> 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 <steve@quintile.net
> > wrote:
>
>>> The PBM utilities (now net pbm) did something similar for bitmaps.
>>> 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
>>
>
>
>
>
>

Re: [9fans] dataflow programming from shell interpreter

[roger peppe]

i had some ideas along these sorts of lines which i
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 <kameo76890@gmail.com>:
>
>
> On Jan 20, 2010, at 4:13 PM, Eris Discordia <eris.discordia@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.
>>
>> 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
>> <steve@quintile.net> wrote:
>>
>>>> The PBM utilities (now net pbm) did something similar for bitmaps.
>>>> 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
>>>
>>
>>
>>
>>
>>
>
>

Re: [9fans] dataflow programming from shell interpreter

[maht]

On 20/01/2010 21:13, Eris Discordia 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.
I don't know much about those but video processing sometimes needs two
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

http://x264dev.multimedia.cx/?p=249

Re: [9fans] dataflow programming from shell interpreter

[Skip Tavakkolian]

> 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.

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.

Re: [9fans] dataflow programming from shell interpreter

[Eris Discordia]

> 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.

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
<9nut@9netics.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.
>
> 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.
>
>

Re: [9fans] dataflow programming from shell interpreter

[Sam Watkins]

On Mon, Jan 18, 2010 at 10:58:30AM +0000, Tim Climber wrote:
> Is this possible for UNIX philosophy to develop further? Let's say,
> 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?

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

Re: [9fans] dataflow programming from shell interpreter

[Eric Van Hensbergen]

On Mon, Jan 18, 2010 at 11:34 AM, Steve Simon <steve@quintile.net> wrote:
>> Have a look at PUSH (PODC 2009)
>
> I had a google but couldn't find it,
> 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

Re: [9fans] dataflow programming from shell interpreter

[erik quanstrom]

On Mon Jan 18 06:08:05 EST 2010, climber.tim@gmail.com wrote:
> Is this possible for UNIX philosophy to develop further? Let's say,
> 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?

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