Re: [9fans] dataflow programming from shell interpreter
On Mon, Jan 18, 2010 at 10:58:30AM +, 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
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 9...@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
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 kameo76...@gmail.com: On Jan 20, 2010, at 4:13 PM, Eris Discordia eris.discor...@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 + Steve Simon st...@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
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
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
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 + Steve Simon st...@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
On Jan 20, 2010, at 4:13 PM, Eris Discordia eris.discor...@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 + Steve Simon st...@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
The PBM utilities (now net pbm) did something similar for bitmaps. I think V10 also had some pipeline utils for manipulating images. In article 89568f5cfeef17d6b1a79f12daeea...@quintile.net, Steve Simon st...@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 354Home 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
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
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. pgp1kjkoWnN4B.pgp Description: PGP signature
Re: [9fans] dataflow programming from shell interpreter
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 pgpiLRQ3Tejlk.pgp Description: PGP signature
[9fans] dataflow programming from shell interpreter
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
On Mon Jan 18 06:08:05 EST 2010, climber@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
Re: [9fans] dataflow programming from shell interpreter
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
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@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
In article c563b2f7-92ac-463a-864c-267721ddb...@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 354Home 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
On Mon, Jan 18, 2010 at 11:34 AM, Steve Simon st...@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=1582780dl=GUIDEcoll=GUIDECFID=64334509CFTOKEN=48344220 If you don't have a subscription to the ACM Library, you can grab a copy here: https://docs.google.com/fileview?id=0B857VbDiq8hOMmY4ZjVkNGQtYmQwZi00NzI5LWJjMTQtYzYxYzBkYTc0ZTJkhl=en -eric
Re: [9fans] 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'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