Here is a major elaboration on generators (I post this as is, I have no one
else whom I can ask for a proofread in any case):
'One concern with lazy evaluation is that errors may not be encountered'
Yes, exactly this is an excellent point: generators must be able to guarantee
their ability to generate the entire list without error,
which leads us to a key point, which I feel is being overlooked here:
Generators are absolutely not a replacement for evaluating all temporary
arrays, they are a situatuational improvement ! There are naturally plenty of
cases where holding off evaluation is detrimental:
i.3 : the physical array is clearly simpler and faster than a generator
u&.> : this generator has information about the whole array, but not
(necessarily) about individual boxes, so perhaps this is a case where we should
give up and create the array. illustration: u@v y: u asks for a cell, v
produces it, and u fails on it for some reason => perhaps we overlooked an
earlier error where v would have failed on a different cell.
Very importantly, there is nothing lost from holding off evaluation until one
is certain it is necessary: at worst, we lose a handful of processor ticks
trying to hold off the inevitable, and at best, we avoid building a temporary
array and open possiblities for simplifications down the line.
The obstacle posed by accurate error reporting is a significant one however.
For finite arrays, we can fall back to spawning arrays whenever a generator
combination is unable to guarantee success. For the infinite case, perhaps the
best we can do is print the error and additionally print a warning wherever a
generator link was compiled that cannot guarantee correctness. However,
theoretically it should be possible to predict any possible error down the line
when creating a generator link. Generators are not really verbs.. they are
nouns to the JFE after all, and thus have all the information necessary to be
produced in their entirety, although some complications arise for subsequent
generators when verifying correctness after someone asks to box parts of a
generator. Again, my canonical example where I feel one must break a generator
chain is when working under boxes of an existing physical array containing
boxed elements. Fortunately, in this case the array is finite and we can simply
create a physical array and terminate the generator train in progress, in order
to check the entire noun's validity before proceeding.
Let's take a look at Roger Hui's examples and his challenge (the fact the array
examples are infinite force a generator approach (or at least prevent the use
of physical arrays)):
>a. A few interesting examples of infinite arrays:
>
> odd =: 1+2*i._
> even=: 2*i._
> odd e. even
>0 0 0 0 0 ...
>
> fib0=: 0,{:"1 ]2 x: (+%)/\ _$1x
> fib1=: {."1 +/\@|.^:(i._) 0 1x
> *./ fib0 -: fib1
> An implementation that can do the last three sentences would be quite an
> accomplishment.
The first example is a good example of what generators would be exceptionally
good at handling.
The second however, I believe clearly exposes Raul's main concern: we cannot
fallback to creating physical infinite arrays, so we must, come what may, keep
working with generator chains. Generator chains then, need to be studied in
depth. (his second concern: whether the time I spend implementing this could be
better spent elsewhere is of absolutely no concern to me; I have the immense
luxury of still being a student).
So... Our generator is infinite, and we cannot fall back to conjuring it up
physically. Does this mean that some operatoions are impossible, and must
return a domain error? Operations must in any event be stored symbolically, so
some errors may go undetected for some time (pending a rigorous proof of the
following conjecture: 'we are able to either guarantee correctness for all
generator links based on i._, or bail out immediately with an error'). Here is
perhaps our biggest problem then: Are there any errors that cannot be predicted
by a generator link on i._ ? Well, boxes aside, we should be able to see coming
all syntax, rank and length errors should be predictable for any generator
link, since we can analyze the complete information we have for generating the
array. As a result then, we need this axiom (for a valid generator): it must
guarantee it's ability to generate an array (short of system limits)). Should
my conjecture about guaranteeing correctness on i._, prove false, then the
offending operations on infinite generators must trigger a domain error.
Let's be more concrete though, and examine the generator chain for Roger's
fib0. Noting that Generators are a natural way of representing conjunctions,
the process I am about to describe can be thought of as 'compiling a J sentence
to a generator chain'. I write 'Gn' to designate the nth generator, counting
from the right.
_$1x : G1 is the constant function 1:, for any y (note it is absolutely not
equivalent to 1:, the generator should be thought of as a noun (is a noun to
the JFE)).
\ G2 returns (i.y) {. G1 (here we could even think of simplifying
directly to y$1, since G1 knows it is constant)
/ y { G3 is (y, 1+y) { G2
(+ %) y { G4 is given by (+%)/ y {G3 (y { G3 returns 2 Values here, and G4
is a dyadic generator)
2 x: y { G5 returns 2 x: y { G4
{:"1 y { G6 returns {:"1 y { G5 NB. Here is potentially a win, as G6
won't ask for all of G1-5
0, y { G7 is represented as a concatenation of a physical list and a
generator.
The last generator would usually be forced into a physical array.. this array
being infinite though, I suggest eitheir laconically printing a prefix, as J
usually does, or even entering an infinite loop printing loop if one uses ,.
may be a valid reaction. Naturally some operations on an infinite generator
must trigger a domain error: attempting to print the thing to a file comes to
mind. Now we see also the dream take shape: result argument cells can be built
directly from the rightmost argument! Those generators that intend to reuse
argument cells can be expected to remember them, in order to avoid asking for a
recalculation. (or perhaps such a generator link should force an array).
'fib1' and 'fb0 -: fb1' can be built similarly (u^:(i._) even maps very nicely
to generators, the one representing ^: can readily reuse it's preceeding
result) . Now the key to the 'accomplishment' lies in the pattern '*/
(generator)'. This attempt to collapse an infinite generator could of course
just bail out with a domain error, but more interestingly, is there any
conceivable way that this reqeust could be met ? In the specific case of
boolean *./, one must somehow prove that the generator is in fact equivalent to
the constant generator _$1. This suggests we need to be able to simplify
generator chains. The good news is that there are no precedence issues in
generator chains and J is free to rearrange commutative generators and
hopefully remove those that cancel each other out. The actual problems
associated with this depend on generator implementation details. If such 'J
symbolic algebra' is possible, then at least a subset of such problems can be
solved.
J4
________________________________
From: Source <[email protected]> on behalf of Don Guinn
<[email protected]>
Sent: Wednesday, February 28, 2018 5:41:51 PM
To: Source forum
Subject: Re: [Jsource] Propositions
One concern with lazy evaluation is that errors may not be encountered
until something happens to make the evaluation go beyond what has been
encountered before. Particularly during development and testing. Is there a
way to turn off lazy evaluation in python during development and testing?
On Feb 28, 2018 8:43 AM, "Raul Miller" <[email protected]> wrote:
> On Wed, Feb 28, 2018 at 10:21 AM, james faure <[email protected]>
> wrote:
> > For J, where so much more is happening per statement, we could
> transparently replace all intermediate results by generators, except where
> a full noun is required.
>
> Worth considering in this context:
>
> $
> {
> |.
> %.
>
> > To translate the python statement to j, one would write (<./ 1 2 3 4 , 0
> 10 0 10), however we lose lots of time to python here due to calculating
> the intermediate catenation (unless we are fortunate enough that the
> interpreter has a Special Combination (SC) for this)
>
> How much is "a lot"?
>
> > For everyone who may be of the opinion that this is not worth it, I
> would like to direct your attention to the existing jsources, where vast
> amounts of effort for far smaller optimizations are apparent.
>
> As a general rule, J only accepts optimizations where there's a useful
> problem where that optimization produces at least a factor of 2
> improvement. (Often enough it's more like factor of 1000.)
>
> > for example p.c, where the parser itself tries to emplace arrays and
> avoid unnecessary copying. It is still unable to do this consistently
> however, as simple memory tests like 7!:2 'i.1000x' ,: '>: i.1000x' prove.
> (and yes I like using x for my benchmarks due to how much slower they are)
>
> I am not sure what you're talking about here - I took a quick look at
> p.c but most of what I saw was implicit in the definitions. I'm not
> comfortable calling that "optimizations".
>
> > another example is. jt.h, where a JFE's state information structure has
> been lovingly crafted to optimize it's use of cpu cache
> > or again the countless optimizations in the primitives, like n&i. hash
> tables, the immensely flexible /: etc..
>
> The hash tables aren't so good on large arrays, unfortunately - so
> that's something that could maybe use some good insights.
>
> But the thing that worries me is how many things would break if you
> tried to throw generators at them. That winds up being cases where
> generators would slow things down (because you have the work of
> building the generator and then interpreting the generator and you pay
> in both code bloat and cache pressure and in cpu pipeline breakage and
> of course any extra tests to keep things from breaking.)
>
> Put different: arrays are not "an optimization" in J. They are J's
> fundamental data structure.
>
> Or, for a similar perspective:
>
> gnu gmp's bignum library looks like a nice-to-have
>
> the lapack library is a nice-to-have
>
> But integrating both of them would not solve the hard issues
> associated with using them together.
>
> Also, thinking back to infinities: one useful tactic for implementing
> math which involves infinities is to work in the reciprocal domain.
> But - hypothetically speaking - there are potentially an infinite
> number of different ways to work with infinities.
>
> Thanks,
>
> --
> Raul
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
J Forums<http://www.jsoftware.com/forums.htm>
www.jsoftware.com
Forums. The J forum mailing lists give life to the J community. They are the
best way to get help, help others, report bugs, and share your interest in J.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
J Forums<http://www.jsoftware.com/forums.htm>
www.jsoftware.com
Forums. The J forum mailing lists give life to the J community. They are the
best way to get help, help others, report bugs, and share your interest in J.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
