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

[David Barbour]

On Wed, Nov 9, 2011 at 3:34 PM, Dan Amelang wrote:

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


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


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

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


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


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
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Fibonacci Machine

[Dan Amelang]

My original reply had a mistake in it, please disregard it. The
following completely replaces it:

Hi Dale,

You are right, that's a mistake in the paper. You should switch
start-0 and start-1 on the top branch. Believe it or not, I did not
write this section :) It's not really about Nile, but about a
particular approach to dataflow in Nothing.

In fact, beware of the sentences:

"The way the Nile runtime works was generalized. Instead of expecting
each kernel to run only when all of its input is ready, then run to
completion and die, the Nothing version keeps running any kernel that
has anything to do until they have all stopped"

The above makes it sound like Nile runtimes in general wait for all
the input to be ready before running a process. This is only true of
the Squeak and Javascript versions of the Nile runtime. The C-based
multithreaded one does not. Sorry I didn't catch this before
publication.

Regardless, the Nothing work strayed a bit from the Nile model of
computation, and not in directions I would take it, so don't take too
much about Nile from that section. Also, I wouldn't advocate writing
Fibonacci like this in Nile. Nile was designed for coarse-grained
dataflow, not fine-grained dataflow. The main reason for this was my
opinion that 1) mathematical statements are often more readable than
their visual, fine-grained dataflow equivalents* and 2) coarse-grained
dataflow can be quite readable due to fewer communication paths, and
thus easier composition, and in many cases they contain only a simple
left-to-right flow.

On top of that, is it easier to efficiently parallelize coarse-grained
dataflow because the communication between components is much less,
allowing parallel hardware to operate more independently.

* For very simple statements, this may not be so true, but when
scaling up to more practical examples, I think fine-grained dataflow
gets messy fast.

Regards,

Dan

___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] Fibonacci Machine

[Dan Amelang]

Hi Dale,

You are right, that's a mistake in the paper. You should switch
start-0 and start-1 on the top branch. Believe it or not, I did not
write this section :) It's not really about Nile, but about dataflow
in Nothing.

In fact, beware of the sentences "The way the Nile runtime works was
generalized. Instead of expecting each kernel to run only when all of
its input is ready, then run to completion and die, the Nothing
version keeps running any kernel that has anything to do until they
have all stopped [1]. It makes it sound like Nile runtimes in general
wait for all the input to be ready before running a process. This is
only true of the Squeak and Javascript versions of the Nile runtime.
The C-based multithreaded one does not. Sorry I didn't catch this
before publication.

Regardless, the Nothing work strayed a bit from the Nile model of
computation, and not in directions I would take it, so don't take too
much about Nile from that section. Also, I wouldn't advocate writing
Fibonacci like this in Nile. Nile was designed for coarse-grained
dataflow, not fine-grained dataflow.

The main reason for this was my opinion that 1) mathematical
statements are often more readable than their visual, fine-grained
dataflow equivalents* and 2) coarse-grained dataflow can be quite
readable due to fewer communication paths, and thus easier
composition, and in many cases they contain only a simple
left-to-right flow.

On top of that, is it easier to efficiently parallelize coarse-grained
dataflow because the communication between components is much less,
allowing parallel hardware to operate more independently.

[1] For very simple statements, this may not be so true, but when
scaling up to more practical examples, I think fine-grained dataflow
gets messy fast.

Regards,

Dan

On Wed, Nov 9, 2011 at 6:45 AM, Dale Schumacher
 wrote:
> Thanks for disseminating the latest report.  It is, as always, an
> inspiration to see all the fine work being done.  I can hardly wait to
> play with the "final" system, and perhaps extend and build on it.
>
> One of the first things I did was re-create (in Humus) the Fibonacci
> Machine from the Nile data-flow model.  I think that the "start-0" and
> "start-1" processes in the upper branch ("b1", "b2", "b3") should be
> reversed.  It seems that the "add" process should first receive 0
> (from "b3") and 1 (from "b5"), then the 1 from "b2" can be forwarded
> and combined with the 1 from the feedback loop ("b7").  I like how the
> pair of forwarders in the upper branch form a kind of delay-line
> effect to stagger the previous and next results.
>
> I appreciate the opportunity to explore and experiment with the ideas
> here.  It will be even better when I can do it in the same environment
> that you do, rather than translating into my own system.
>
> On Mon, Nov 7, 2011 at 5:08 PM, karl ramberg  wrote:
>> http://www.vpri.org/pdf/tr2011004_steps11.pdf
>>
>> Karl
>>
>> ___
>> fonc mailing list
>> fonc@vpri.org
>> http://vpri.org/mailman/listinfo/fonc
>>
>
> ___
> fonc mailing list
> fonc@vpri.org
> http://vpri.org/mailman/listinfo/fonc
>

___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

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

[Dan Amelang]

On Wed, Nov 9, 2011 at 1:31 AM, David Barbour  wrote:
>
> On Tue, Nov 8, 2011 at 11:13 PM, Dan Amelang 
> wrote:
>>
>> 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.

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.

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

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.

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

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.

>> 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
address one more comment, then I have to move on:

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

Re: [fonc] new document

[karl ramberg]

On Tue, Nov 8, 2011 at 5:49 PM, DeNigris Sean  wrote:
> On Nov 7, 2011, at 6:08 PM, karl ramberg wrote:
>> http://www.vpri.org/pdf/tr2011004_steps11.pdf
>
> It's so exciting to watch the project come along. I can't wait to eventually 
> play with it!
>
> With every annual report, I think what a shame it is that there are so many 
> talks given about it (~20 this year) and so few (~3) are recorded. Given the 
> vital importance of this project, and all the work that must go into 
> preparing the talks, it seems like a great waste to share this knowledge with 
> only the few academics who happen to be at the various conferences. I attend 
> about 6 conferences a year and still feel like I'm missing all the fun. Why 
> doesn't VPRI just take the bull by the horns and record them even if the 
> conferences don't? Consumer video equipment is so good now, it probably 
> wouldn't cost anything but a few conversations - even an iPhone video could 
> work!

I really enjoy the presentation on sites like http://www.infoq.com/
where the slides and the presenter get their separate space. I would
very much like to have the VPRI talks available in such a format. I
also think the presentations deserve it as they often are long the
making and can give better understanding than a paper can.

Most of the software from VPRI is available but it is often hard to
get a grasp without the whole context. And much of the systems I'm not
familiar with so it's very a steep learning curve. A few videos from
presentations could really enlighten here :-)

Best regards
Karl

___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] new document

[Benoît Fleury]

Unless I missed it, there is no mention of Dynabook Junior in the last
report.

Has it been abandoned? replaced?

On Wed, Nov 9, 2011 at 3:27 AM, Steve Taylor  wrote:

> -1
>
>
> David Barbour wrote:
>
>> `+1`? Really? I seriously do not appreciate having my mail spammed in
>> this manner.
>>
>> If you're offering an opinion on the article, try to say something
>> specific and relevant to those who might have skimmed it. Which parts
>> interested you?
>>
>> If you're referring to Sean's comment for recording the outreach events,
>> please consider moving it to another topic.
>>
>
> __**_
> fonc mailing list
> fonc@vpri.org
> http://vpri.org/mailman/**listinfo/fonc
>
___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

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

[Ondřej Bílka]

On Wed, Nov 09, 2011 at 09:55:22PM +0530, K. K. Subramaniam wrote:
> On Wednesday 09 Nov 2011 12:43:00 PM Dan Amelang wrote:
> > "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' ;-) ?
You should use russian terminology. They use words Putin and getout.
> 
> Subbu
> 
> ___
> fonc mailing list
> fonc@vpri.org
> http://vpri.org/mailman/listinfo/fonc

-- 

clock speed

___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

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

[K. K. Subramaniam]

On Wednesday 09 Nov 2011 12:43:00 PM Dan Amelang wrote:
> "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

___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

[fonc] Fibonacci Machine

[Dale Schumacher]

Thanks for disseminating the latest report.  It is, as always, an
inspiration to see all the fine work being done.  I can hardly wait to
play with the "final" system, and perhaps extend and build on it.

One of the first things I did was re-create (in Humus) the Fibonacci
Machine from the Nile data-flow model.  I think that the "start-0" and
"start-1" processes in the upper branch ("b1", "b2", "b3") should be
reversed.  It seems that the "add" process should first receive 0
(from "b3") and 1 (from "b5"), then the 1 from "b2" can be forwarded
and combined with the 1 from the feedback loop ("b7").  I like how the
pair of forwarders in the upper branch form a kind of delay-line
effect to stagger the previous and next results.

I appreciate the opportunity to explore and experiment with the ideas
here.  It will be even better when I can do it in the same environment
that you do, rather than translating into my own system.

On Mon, Nov 7, 2011 at 5:08 PM, karl ramberg  wrote:
> http://www.vpri.org/pdf/tr2011004_steps11.pdf
>
> Karl
>
> ___
> fonc mailing list
> fonc@vpri.org
> http://vpri.org/mailman/listinfo/fonc
>

___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

Re: [fonc] new document

[Steve Taylor]

-1

David Barbour wrote:
`+1`? Really? I seriously do not appreciate having my mail spammed in 
this manner.


If you're offering an opinion on the article, try to say something 
specific and relevant to those who might have skimmed it. Which parts 
interested you?


If you're referring to Sean's comment for recording the outreach events, 
please consider moving it to another topic.


___
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc

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

[David Barbour]

On Tue, Nov 8, 2011 at 11:13 PM, Dan Amelang wrote:

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


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


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


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


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

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.


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


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