[fonc] Nile/Gezira (was: Re: +1 FTW)

Discussion:

Dan Amelang

2011-11-09 07:13:00 UTC

Hi David,

The high-level model of computation is a variation of Kahn process
networks. The low-level part is a single-assignment,
mathematics-oriented language for specifying the internal behavior of
a process.

I've been reading through Nile and Gezira code and understand the model
better at this point. It's basically pure functional stream processing,
consuming and generating streams. I understand that `>>` generates one
output, and `<<` seems to push something back onto the input stream for
re-processing.

Yes, you are correct. The spacial metaphor here is that streams flow
from left to right, so ">> x" pushes x to the right, onto the tail of
the output stream. "<< x" pushes (pulls? :) x to the left, onto the
head of the input stream. Pipeline construction works this way too,
e.g., ClipBeziers → Rasterize → ApplyTexture → WriteToImage . A bit
silly, perhaps, but it works.

"Input prefixing" is what I call this pushing of data onto the input
stream, though I'm not set on that term. You used the term "pushback",
which I like, but the problem is that we're pushing onto the _front_
of the input stream, and "pushfront" just doesn't have the same ring
:)

Whatever the name, this feature is vital to writing expressive
programs in Nile. It provides a recursion-like capability. For
example, the DecomposeBeziers process successively decomposes Beziers
until they are small enough to process. This is done by splitting the
Bezier into two parts (à la De Casteljau), and pushing each sub-Bezier
onto the input stream.

I have never seen input prefixing in a stream-processing/dataflow
language before. I could only find one passing reference in the
literature, so unless someone points me to previous art, I'll be
playing this up as an original contribution in my dissertation :)

Which Nile operators do you anticipate would translate poorly to shaders? I
guess `zip` might be a problem. SortBy and pushback operators - at least if
finite - could be modeled using shader global state, but that would be a bit
of a hack (e.g. receive some sort of EOF indicator to emit final elements).
Hmmm....

Yes, this is the beginning of the difficulties. Just taking the input
prefixing issue, it's problematic to model the unbounded input stream
as global state. You have issues because of the finiteness of the
global state, and because of the inefficiency of global write/read
access in the shader (see GPU docs).

And as I brought up before, even if one can get something to run on
the GPU, that's very different from getting something to run much
faster than on the CPU.

Regarding your question about which processes would map poorly: the
built-in Nile processes DupZip, SortBy, and Reverse (maybe DupCat,
too). Many Gezira processes are a problem, such as ExpandSpans,
CombineEdgeSamples, ClipBeziers, DecomposeBeziers, pretty much all of
the processes in the file stroke.nl (pen stroking). There's probably
more, these are off the top of my head.

I think I'd be in trouble actually writing Nile code... I don't have a text
editor with easy Unicode macros. Which do you use?

I use vim. So I hit "ctrl-v u2200" for ∀.

Ideally, we'd have a Nile IDE with keyboard macros in addition to a
little char map to click on (Bert built one for Frank).

The theory behind using Unicode in Nile is that source code is read a
lot more than it is written. So I'm willing to make code a bit harder
to write for a payoff in readability. And if Nile becomes what it
should be, one shouldn't have to write much code anyway.

I agree that Conal Elliott's focus has certainly been on composable,
morphable, zoomable graphics models

I'm glad we agree...wait a second...when did I say the above?

- primarily, everything that happens
before rasterization.

Ah, well, now I don't agree that his focus has been on "everything
that happens before rasterization." He's left out a lot. He's never
taken on pen stroke approximation (which is vital for 2D vector
graphics). I had to struggle a bit to come up with my functional
approach to pen stroking (if I missed prior art, let me know!). He's
never taken on, say, analytical geometry clipping. On top of that,
there's a lot _after_ rasterization, and he doesn't addresses that
territory much either.

I like Conal's work, really. I read all his papers on functional
graphics several years ago, and it probably subconsciously influenced
my research. I'm just objecting to the idea that he covered very much
functionality in the computer graphics space. I think he took on the
easiest niche to model in a purely functional language.

Anti-aliased rasterization can certainly be modeled in
a purely functional system,

Easier said than done, I think. Again, I struggled quite a bit to come
up with the Gezira rasterizer (which is basically purely functional).
I don't know of any previous anti-aliased rasterizer done in a purely
functional style, do you? Pointers appreciated.

You could just reproduce Foley et. al, but that's such an imperative
algorithm, I would think you'd end up with C-in-Haskell looking code.
If so, I wouldn't count that.

Are you trying anything like sub-pixel AA? (seems a bit too system dependent
for me, but it's an interesting subject.)

I also find it interesting, but I haven't tried it, yet. Just thought
through what the pipeline would look like and how to do the fitering.
Definitely worth doing at some point.

My own interest in this: I've been seeking a good graphics model for
reactive systems, i.e. rendering not just one frame, but managing
incremental computations and state or resource maintenance for future
frames. I don't think Gezira is the right answer for my goals,

I think you're probably right. Gezira is fundamentally about the
ephemeral process of rendering. Managing state and resources is a
whole other ball game. At Viewpoints, I think the Lesserphic project
is closer to what you're looking for.

Thanks for the engaging questions,

Dan

David Barbour

2011-11-09 09:31:51 UTC

Permalink

Post by Dan Amelang
I have never seen input prefixing in a stream-processing/dataflow
language before. I could only find one passing reference in the
literature, so unless someone points me to previous art, I'll be
playing this up as an original contribution in my dissertation :)

It's old, old art. Even C file streams and C++ iostreams allow get, put,
putback - where `putback` means put something back onto a stream you just
`get` from. I've seen this pattern many times - often in lexers and
parsers, Iteratees, and various other stream-processing models.

Post by Dan Amelang
Regarding your question about which processes would map poorly: the
built-in Nile processes DupZip, SortBy, and Reverse (maybe DupCat,
too). Many Gezira processes are a problem, such as ExpandSpans,
CombineEdgeSamples, ClipBeziers, DecomposeBeziers, pretty much all of
the processes in the file stroke.nl (pen stroking). There's probably
more, these are off the top of my head.

Thanks. I'll peruse these.

Post by Dan Amelang
The theory behind using Unicode in Nile is that source code is read a
lot more than it is written. So I'm willing to make code a bit harder
to write for a payoff in readability. And if Nile becomes what it
should be, one shouldn't have to write much code anyway.

With that philosophy, maybe we should be writing markup. That way we can
read code in a comfortable `document` format. I think Fortress takes that
approach.

Post by Dan Amelang
He's never taken on pen stroke approximation (which is vital for

2D vector graphics).

Why is this vital? I think there are different understandings of the
`image` abstraction here. One can understand images in terms of drawing
arcs then filling between edges - and such a model is commonly seen in
PostScript and Cairo and apparently Gezira. But it is not an authoritative
abstraction. Pen-strokes with fill is a very imperative approach to
graphics modeling.

Elliott favors modeling lines in terms of areas. So do I. This seems to
shift pen stroke approximation to a utility role - valuable, but not vital.

Areas seem an effective basis for scalable scene-graph maintenance,
declarative models, occlusion, and level-of-detail indexing compared to a
line/fill approach. With the assumption that a pen stroke is modeled as an
area - perhaps defined by a cubic bezier path, a width, and a brush (e.g.
for dashes and colors and flair) - one is still left with a challenge of
building a useful library of glyphs and brushes.

He's never taken on, say, analytical geometry clipping.

Granted. Elliott focuses on the rather generic (Real,Real)->PixelData
abstractions, and doesn't bother with a static ontology of geometries
subject to easy analysis. Clipping is certainly achieved, though.

One could work with geometry based analyses, bounding boxes, and the like.
The diagrams package certainly does so.

there's a lot _after_ rasterization

True. And your ability to squeeze all this stuff into a few hundred lines
of Nile code is certainly a valuable contribution to the Steps project.

Post by Dan Amelang

Anti-aliased rasterization can certainly be modeled in
a purely functional system,

I think the challenge you are imagining is a technical one, not a logical
one. Modeling anti-aliased rasterization in a purely functional system is
quite straightforward, at least if you aren't composing images in
rasterized form. The best anti-aliasing is very much mathematical (cf.
claims by Morphic 3 project,
http://www.jvuletich.org/Morphic3/Morphic3-201006.html). The trick is to
make such a model high performance. At the moment, one will still
ultimately compile down to an imperative machine.

Post by Dan Amelang
You could just reproduce Foley et. al, but that's such an imperative
algorithm, I would think you'd end up with C-in-Haskell looking code.
If so, I wouldn't count that.

It is true that there may be some imperative algorithms to implement pure
functions. Haskell offers facilities for doing this (ST monad, State
monad). But, while writing the algorithms may be imperative, using them can
still be pure functional. So I guess the question is whether you'll be
spending more time writing them or using them. ;)

Post by Dan Amelang

Thanks for the suggestion.

One of the `features` that interests me for reactive systems is properly
modeling motion-blur per frame, possibly in a shader. According to the
studies I've read, framerates must be a lot higher to avoid perceptual
`jerkiness` unless motion blur is included.

Regards,

Dave

Dan Amelang

2011-11-09 23:34:24 UTC

Permalink

Post by David Barbour

It's old, old art. Even C file streams and C++ iostreams allow get, put,
putback - where `putback` means put something back onto a stream you just
`get` from. I've seen this pattern many times - often in lexers and parsers,
Iteratees, and various other stream-processing models.

Of course I'm aware of these :) There's a Nile parser written in
OMeta, and there's one in Maru now. Both put objects on their input.
And I'm familiar with C++ streams, notice how I based the Nile ">>"
and "<<" syntax on them.

Notice the first sentence of the paragraph that you quoted. I'm
pointing out that, as useful as input prefixing is, it doesn't appear
at all in stream processing languages. Furthermore, it doesn't appear
in stream processing models of computation.

Here's a bit of background. Take the early research, such as Duane
Adams' "A Computation Model with Data Flow Sequencing" in 1968.
(Strachey used streams to model I/O before that, like UNIX uses file
handles). Around this time, you also had Seror's DCPL, and Scott's
"Outline of a Mathematical Theory of Computation".

If you start there, and go through Karp and Miller "Properties of a
Model for Parallel Computations", Kahn's process network papers,
Dennis' dataflow work (esp. Id and VAL), Wadge and Ashcroft's dataflow
(particularly GLU), McGraw's SISAL, Lee's Dataflow Process Networks,
up to recent work like Streamit and GRAMPS, you won't find a single
one that even proposes input prefixing (corrections welcome).

My point is that introducing this feature into a stream processing
language and demonstrating its utility might be a research
contribution.

I do appreciate your interest in Nile/Gezira, and you've brought up
interesting questions. Due to time constraints, though, I'm going to
have to put less effort into comments like the above that strike me as
somewhat glib. I hope not to offend anyone or dismiss truly informed
comments, though. I just have a lot on my plate right now.

Post by David Barbour

Thanks. I'll peruse these.

As you look those over, it might help to know that the double arrow
"⇒" is for "process substitution", which is analogous to Kahn's
"reconfiguration" (see Kahn and MacQueen, 1976). That is, the effect
of the statement is to dynamically replace the current process with
the newly created sub-network following the arrow.

Post by David Barbour

With that philosophy, maybe we should be writing markup. That way we can
read code in a comfortable `document` format. I think Fortress takes that
approach.

Yes, similar idea. Though as Alan points out, markup is very weak, and
we can do better with interactive, graphical environments. Thus, I've
always felt that my games with Nile syntax are somewhat futile.

Post by David Barbour

Post by Dan Amelang
He's never taken on pen stroke approximation (which is vital for
2D vector graphics).

Why is this vital? I think there are different understandings of the `image`
abstraction here. One can understand images in terms of drawing arcs then
filling between edges - and such a model is commonly seen in PostScript and
Cairo and apparently Gezira. But it is not an authoritative abstraction.
Pen-strokes with fill is a very imperative approach to graphics modeling.
Elliott favors modeling lines in terms of areas. So do I. This seems to
shift pen stroke approximation to a utility role - valuable, but not vital.

Is this conclusion really important enough to argue for? That
rendering lines should be considered valuable but not vital? I think
graphic designers would generally disagree. Regardless, just replace
all instances of "vital" with "valuable" in my original argument, and
I still stand by it.

I'm sorry but at this point, I think you're grasping at straws. I can

Post by David Barbour
Pen-strokes with fill is a very imperative approach...

This is just too much. Let's go over the details. In Gezira, I use the
"stroke-to-path" approach to pen stroking. This means that the
stroking pipeline takes a stream of Beziers that define the path of
the pen, and emits a stream of Beziers that define the outline of a
shape approximating the stroked path. Yes, I am aware that there are
other ways to do this, but let's focus on the "very imperative" claim
for now.

The output of the stroking pipeline, being just another Bezier
outlined shape, is fed to the same rasterize pipeline I use for, say,
glyph shapes. The output of the rasterize pipeline is then (typically)
sent to the ApplyTexture pipeline ("texture" here is any mapping of
(x,y) to colors, like a "brush" or "fill" in other frameworks), then
to the WriteToImage process.

In Nile, it looks pretty close to this:

StrokeBeziers → Rasterizer → ApplyTexture → WriteToImage

(I'm eliding the likely-used ClipBeziers and TransformBeziers in the
pipeline for simplicity's sake)

Given your description, Gezira uses the "pen-strokes with fill"
approach that is "very imperative." And yet, every Nile process (and
sub-process) from StrokeBeziers down to WriteToImage is implemented in
a purely functional way (not even fancy stuff imperative-ish
constructs like monads). And they are composed with just plain old
function composition.

So I don't get how a purely functional program, with no imperative-ish
constructs can be the embodiment of a "very imperative"
algorithm/approach.

OK, I cannot give any more detailed responses to comments like this.
My employer, my PhD advisor, probably members of this list, and of
course myself, need me to spend my time elsewhere.

Post by David Barbour
Areas seem an effective basis for scalable scene-graph maintenance,
declarative models, occlusion, and level-of-detail indexing compared to a
line/fill approach.
With the assumption that a pen stroke is modeled as an
area - perhaps defined by a cubic bezier path, a width, and a brush (e.g.
for dashes and colors and flair)
- one is still left with a challenge of
building a useful library of glyphs and brushes.

You are apparently partial to implicit surfaces. OK, why not give your
ideas a shot and show us how it turned out? Maybe try rendering
something similar to VPRI's Frank as a benchmark of functionality?

Post by David Barbour

Post by Dan Amelang
He's never taken on, say, analytical geometry clipping.

Granted.
Elliott focuses on the rather generic (Real,Real)->PixelData
abstractions, and doesn't bother with a static ontology of geometries
subject to easy analysis. Clipping is certainly achieved, though.
One could work with geometry based analyses, bounding boxes, and the like.
The diagrams package certainly does so.

Could seem that way. I'd be interested in how it works out for you.

Post by David Barbour

Post by Dan Amelang
there's a lot _after_ rasterization

True. And your ability to squeeze all this stuff into a few hundred lines of
Nile code is certainly a valuable contribution to the Steps project.

Thank you.

Post by David Barbour

Post by Dan Amelang

Anti-aliased rasterization can certainly be modeled in
a purely functional system,

I think the challenge you are imagining is a technical one, not a logical
one.

Fine, call it a technical challenge instead of a logical one. I still
stand by my point.

Post by David Barbour
Modeling anti-aliased rasterization in a purely functional system is
quite straightforward, at least if you aren't composing images in rasterized
form.

My challenge to find a previous anti-aliased rasterizer done in a
purely functional style still stands. I issued it to counter what I
felt were unsubstantiated claims. You just gave me more claims :)

With more time, I'd dive into the "...at least if you aren't composing
images in rasterized form" part.

Post by David Barbour
The best anti-aliasing is very much mathematical (cf. claims by
Morphic 3 project, http://www.jvuletich.org/Morphic3/Morphic3-201006.html).

Juan's anti-aliasing approach, though better than Gezira's in certain
ways, isn't any more mathematical than Gezira's in terms of form (see
the published Gezira anti-aliasing coverage formula). In terms of
signal processing theory, though, his is more interesting. But this
doesn't relate to the main point.

Post by David Barbour
One of the `features` that interests me for reactive systems is properly
modeling motion-blur per frame, possibly in a shader. According to the
studies I've read, framerates must be a lot higher to avoid perceptual
`jerkiness` unless motion blur is included.

Sounds interesting, I would give it a go and see what happens.

Beware of brain crack (a bit of fun pop philosophy)

.

Dan

David Barbour

2011-11-10 03:18:11 UTC

Permalink

I'm pointing out that, as useful as input prefixing is, it doesn't appear
at all in stream processing languages. Furthermore, it doesn't appear
in stream processing models of computation.

Old wine, new ontology.

Elevating common design patterns and library abstractions to language
primitives does not, IMO, qualify as any sort of `original
contribution`. It's up to you to decide whether to claim forty year old
technology as an original contribution. (You won't be the first to do so,
nor the last.) Personally, I would choose the more humble route. I would
note the utility of having input prefixing uniformly across types with low
syntactic overhead, but not claim it.

Is this conclusion really important enough to argue for? That
rendering lines should be considered valuable but not vital?

It important to recognize an application of the Inventor's
Paradox<http://en.wikipedia.org/wiki/Inventor%27s_paradox>.
You attempt to solve a specific problem - rendering lines. This problem is
solved more easily, more naturally, by rendering areas. The rendering of
lines then becomes a simple, special case of the more general problem.

It is also important to recognize that, by rendering areas, the modeling of
pen-strokes is, essentially, already solved. Sure, it may be useful to fill
out the library with some support for bezier paths. But it is not
essential. That's the difference between valuable and vital.

Post by David Barbour
Pen-strokes with fill is a very imperative approach...

This is just too much. Let's go over the details.

Here are the relevant details to my conclusion:
1) You move a logical pen above a logical canvas by a sequence of move and
stroke commands.
2) The move and stroke commands themselves are not commutative, not
idempotent, and not referentially transparent - they depend on implicit
state of the pen.
3) Filling a shape requires extracting shape from an unstructured history
of lines. You effectively cannot extract shapes without executing the
program and filling at the right points in history.

Imperative isn't about impurity or indeterminism. Imperative is about
updating and querying state, implicit time, dependence on history and order
of expression. Pen-stroke and fill is the classic example of imperative
draw models.

You argue that your algorithm is pure (from an external perspective), and
your pipeline as a whole is pure. And I agree. Nile is a fine example of
`imperative in-the-small, functional in-the-large`, much like using local
State or ST monads to implement functions in Haskell.

I did not intend for you to take offense. Imperative does not mean
`slaughters puppies`. Stroke and fill is certainly a well proven model.

I plan to do so, once I get around to developing the zoomable UI
abstractions.

Post by David Barbour
Modeling anti-aliased rasterization in a purely functional system is
quite straightforward, at least if you aren't composing images in

rasterized

Post by David Barbour
form.

My challenge to find a previous anti-aliased rasterizer done in a
purely functional style still stands. I issued it to counter what I

felt were unsubstantiated claims.

I do not need an algorithm written in a functional style to model
anti-aliased rasterization in a purely functional system. What I do need is
an algorithm that is pure and deterministic up to input. I understand that
most rasterization algorithms qualify. I assume you have misread my claim
to mean something less obvious.

That said, I have no doubts that anti-aliased rasterization can be achieved
in a functional style - I've read a few simple functional ray-tracing
engines, for example, and I understand that raycast per pixel results in
images of a quality on par with many anti-aliasing techniques even without
super-sampling or sub-pixel sampling. I would only express some concerns
about their efficiency.

Anyhow, thanks for answering my earlier queries, and keep up the good work.

Regards,

Dave

David Barbour

2011-11-10 15:35:19 UTC

Permalink

Post by David Barbour
That said, I have no doubts that anti-aliased rasterization can be
achieved in a functional style - I've read a few simple functional
ray-tracing engines, for example, and I understand that raycast per pixel
results in images of a quality on par with many anti-aliasing techniques
even without super-sampling or sub-pixel sampling. I would only
express some concerns about their efficiency.

Ah yes, it seems the anti-aliased quality images really depends on the
content of those images (e.g. a bunch of big spheres) and something about
image frequencies that I haven't really studied. But I still expect that
ray tracing is the most likely option for finding anti-aliased
rasterization in a pure functional `style`.

Whatever. Need to get back to useful work.

Regards,

Dave

K. K. Subramaniam

2011-11-09 16:25:22 UTC

Permalink

Post by Dan Amelang
"Input prefixing" is what I call this pushing of data onto the input
stream, though I'm not set on that term. You used the term "pushback",
which I like, but the problem is that we're pushing onto the front
of the input stream, and "pushfront" just doesn't have the same ring

I thought 'pushback' means 'push back into', so if you have a input stream,
abcdefgh ---->
and you read in 'h' and then 'g', you could push 'g' back into the input
stream for later processing. I suppose one could also 'putback' g into the
input stream.

But then many computer terms border on the weird :-). I can understand
'output' and something that one 'puts out' but then what is 'input'? If it is
something one 'gets in', shouldn't it have been 'inget' ;-) ?

Subbu

Ondřej Bílka

2011-11-09 18:05:48 UTC

Permalink

Post by K. K. Subramaniam

I thought 'pushback' means 'push back into', so if you have a input stream,
abcdefgh ---->
and you read in 'h' and then 'g', you could push 'g' back into the input
stream for later processing. I suppose one could also 'putback' g into the
input stream.
But then many computer terms border on the weird :-). I can understand
'output' and something that one 'puts out' but then what is 'input'? If it is
something one 'gets in', shouldn't it have been 'inget' ;-) ?

You should use russian terminology. They use words Putin and getout.

Post by K. K. Subramaniam
Subbu
_______________________________________________
fonc mailing list
http://vpri.org/mailman/listinfo/fonc

--
clock speed