Undefined behaviour in J
Roger Hui
References: <4n88hc$o...@capehenry.cs.unc.edu> <8720knf...@rdm.legislate.com>
Re: Articles from Henry Rich and Raul Miller.
Regarding the interaction between order of evaluation within
an operator and functions with side effects: It would be unwise
to depend on a particular order of evaluation. If the dictionary
were really pedantic, it might say something to the effect that
(for example) in f"r, function f is applied to the cells in a random
order (to preserve maximum flexibility for the implementation to
exploit the underlying hardware). Moreover, having such an explicit
statement could be interpreted to _require_ a randomization in
the cell application order, and thereby penalizing side-effectless
functions just to prevent side-effectful functions from fixating
on a particular order.
Regarding performance characteristics: No APL interpreter
or C compiler or other programming language that I have ever
used provide the sort of information requested by Rich and Miller.
In the case of J, performance can be quite difficult to
characterize and would take a large amount of effort to describe,
and the information changes from one release to the next.
(And the information may not be available because the interpreter
is written in C and C does not provide the information.)
For example, the dyad i. has special code for many subcases.
Likewise, /: and \: use different algorithms depending not
only on the internal type of the data, but also on the shape
and on the value. Special code are added all the time as
reports are received from J users on particularly useful subcases.
A detailed description of exactly which subcases are handled gives
important insights into the algorithms used, information that I
prefer to keep secret from our competitors. On the other hand,
J provides tools for monitoring the time and space characteristics
of computations, so that it is quite easy for the user to obtain
answers to performance questions in specific cases.
p.s. The monad f/\. was speed-up in J3.01, as noted in status.txt.
Henry Rich
In article <1996051506...@smtp1.sympatico.ca>,
Roger Hui <Roge...@Sympatico.CA> wrote:
>References: <4n88hc$o...@capehenry.cs.unc.edu>
> <8720knf...@rdm.legislate.com>
>
>Re: Articles from Henry Rich and Raul Miller.
>
>Regarding the interaction between order of evaluation within
>an operator and functions with side effects: It would be unwise
>to depend on a particular order of evaluation. If the dictionary
>were really pedantic, it might say something to the effect that
>(for example) in f"r, function f is applied to the cells in a random
>order (to preserve maximum flexibility for the implementation to
No, that would not be pedantic, it would be untrue. The Dictionary
should simply say that the order of evaluation is undefined, just
as the C language specification tells you that the result of (x + ++x) is
unpredictable (if I may slip in related example, the C language also
tells me how to parse x+++y, while the Dictionary does not discuss
how ::. should parse, except by the Delphic 'one or more').
Similarly, if the number of times a function is
evaluated is unpredictable, you should say so. In the absence of such
a statement, I would hold that the new faster u/\. (which applies
u to suffixes of increasing length) does not conform to the
Dictionary, which says "u\.y has #y items resulting from applying
u to suffixes of y, beginning with one of length #y and continuing
through a suffix of length 1".
I'm not just trying to be a jerk - of course we are all happy when
you speed up something. The question is whether you are describing
a language or an implementation. I hope to see a J compiler someday:
how will it differ from the interpreter? (Raul, this distinction
is why some things belong in the Dictionary and some in an
interpreter Release Guide).
Regardless of side effects, I say that you must make explicit
what happens in so common a case as
(i. 2) 0 0} (i. 2)
either by saying the results are unpredictable or
by revealing the evaluation order.
I harbor a hope that I can make J the language
for department-size projects at work, but it will not happen
if I have to say that ISI's policy for specifying what statements do
is to try them on the current release of the interpreter
(I think J would be worthwhile anyway, but I can't convince
management and colleagues - I've tried).
>Regarding performance characteristics: No APL interpreter
>or C compiler or other programming language that I have ever
>used provide the sort of information requested by Rich and Miller.
With C compilers, the source for the libraries is often distributed.
>In the case of J, performance can be quite difficult to
>characterize and would take a large amount of effort to describe,
>and the information changes from one release to the next.
It's like the performance description of a microprocessor. Even
though a precise description is impossible, the manufacturer
provides a rough-and-ready guide of cycles per instruction,
execution latency, and pipeline interactions. I consult this
guide as the first step to writing any performance-critical code.
Similarly, a three-column chart giving O(n) performance,
amount of memory used, any special paging characteristics, or
whatever, for each verb and adverb, would keep the performance
of J programs from being a continual surprise. If there
are special cases, you can ignore them, or mention them
briefly (wouldn't you like us to know what idioms to use?).
>On the other hand,
>J provides tools for monitoring the time and space characteristics
>of computations, so that it is quite easy for the user to obtain
>answers to performance questions in specific cases.
That seems to me like saying that Toronto has helpful police,
so I will not need a map if I come to the Users' Conference.
What I personally need most is an understanding of interpreter
overhead, and I haven't been able to get it even though
I try. I write everything I can with tacit definitions,
and the few times I have had to use explicit definitions
the results have been bad - I don't know what I'm doing
wrong, or whether perhaps the things that require explicit
definition are exactly those things that are non-vectorizable
and therefore just naturally slow in J. I do know that
when I write an explicit definition I feel like a man going to
the gallows.
I need to know in advance, if I write an image-processing suite,
whether to write it in 1 day using J and spend a week waiting
for the computation to finish, or spend 3 days writing it
in C and wait two hours for the computation. (That was a real-life
example. The program used all tacit definitions, but there was a lot of
reshaping of the data, just the sort of thing that better
understanding of the interpreter innards might have helped.
I considered it a success for J, but the others who were sharing our
compute server were less pleased).
In the hope that someone will answer these questions, I append
another one:
If a tacit function includes a reference to an explicitly-defined
conjunction, how often is the conjunction interpreted?
Henry Rich
Henry Rich
Two points:
1. I don't do this kind of thing, but I would think that order
of evaluation is important for people who deal with very large
dynamic range of data, such that they worry about floating-point
effects when large and small are added.
2. You could see if a function has side effects by looking for
=: and ". , and perform those in the simple-minded order, leaving
optimizations for functions known to be well-behaved. (Honestly,
this is what I guessed you would be doing before I started
checking).
Of course, you still would need to tell us what the simple-minded
order is!
Henry Rich
Henry Rich
Suppose I have a file that I am trying to break into atoms,
but the file format is such that I can't find atom delimiters
except by parsing the file in sequential order. (Maybe it's
a MIDI file or a compressed data stream). Assume for simplicity
that I know the number of atoms.
I write some function nextatom that boxes up one atom and
alters global variables to move up to the next atom. Then
to create my desired list I will code something like
atoms =. 0 $ a: [ atomct =. >: atomct
while. atomct =. <: atomct do.
atoms =. atoms , nextatom fileinfo
end.
but this has the dreaded quadratic performance as the ,
takes longer and longer as atoms are added. (If there
is any way to improve this sort of thing to linear performance
I'd love to hear it - the only way I know is to write the atoms
out to a file).
I might be tempted - nay, I am tempted - to code
(i. atomct) nextatom"0 _ fileinfo
in the hope that the interpreter will do a more efficient job
of memory management and data movement if I do. But look at
the problems this causes in the long run:
1. My program may break if you change order of evaluation in
the interpreter, or if I get a compiler.
2. I may have just been wasting my time - the changed version may
not be any faster than the original.
3. Suppose I had tried
(atomct $ 0) nextatom"0 _ fileinfo
as my stab at improvement. You may, much later, (or even
now, who knows?) choose to detect equal arguments and convert
my line to a single call to nextatom, breaking my program that
way.
4. Worst of all, if I am a big enough customer I will threaten
you with penury if you make such changes, and stultify
development.
Henry Rich
Raul Miller
Henry Rich:
No, that would not be pedantic, it would be untrue. The Dictionary
should simply say that the order of evaluation is undefined, just
as the C language specification tells you that the result of (x +
++x) is unpredictable (if I may slip in related example, the C
language also tells me how to parse x+++y, while the Dictionary
does not discuss how ::. should parse, except by the Delphic 'one
or more').
Pendatically: if the dictionary doesn't define something it is
undefined.
The problem, of course, is that this covers a lot of ground -- ground
which must be covered to write useful programs. Then again, Pendants
aren't all that great at writing useful programs.
I'm not just trying to be a jerk - of course we are all happy when
you speed up something. The question is whether you are describing
a language or an implementation. I hope to see a J compiler
someday: how will it differ from the interpreter? (Raul, this
distinction is why some things belong in the Dictionary and some in
an interpreter Release Guide).
Sure, but the things you were asking for specs on are things that have
traditionally varied from one implementation of APL to another. This
implies that there would be problems with fixing this in the language.
Of course, I recognize that real world programs require that you have
order to apply to your results. I'm just not sure that specifying
time of evaluation is the best way to get what you want.
The *real* problem is that J's rank mechanism for iteration doesn't
work all that well when dealing with some sequence of data. It only
works when the sequence is internal to J. When the sequence is some
large external object you have to start explicitly partitioning the
problem.
One solution might be to give J an internally consistent way of
characterizing such external objects.
I'm curious what some of the various implementation people (including
Arthur Whitney, Alan Graham, Bob Bernecky and of course Roger Hui)
think about this issue (ordering, efficient notation, and large
sequences). But, at some large-scale point it becomes difficult to
ignore the nature of the application (e.g. database, gui, valuation,
...) from language properties.
--
Raul
Raul Miller
Roger Hui:
Regarding performance characteristics: No APL interpreter or C
provide the sort of information requested by Rich and Miller.
J does a lot of things that aren't common practice, so "no one else
has done it" doesn't strike me as a particularly strong objection.
In the case of J, performance can be quite difficult to
characterize and would take a large amount of effort to describe,
and the information changes from one release to the next.
Performance data at that level might be useful, but I was thinking
more along the lines of simplified upper bounds. (e.g. "These
operations are O(ny) where ny is the number of atoms in y").
For cases where the worst case bound is completely inadequate for
predicting performance, a best case or average case might be a useful
supplement.
(And the information may not be available because the interpreter
is written in C and C does not provide the information.)
Sure, and then there's hardware variations and complicated memory
architectures. This could be simplified by making the explicit
assumption that most C instructions have a reasonable constant upper
bound on execution time. [Then, a loop which executes its body n
times contributes a factor of n to the computation time.]
For example, the dyad i. has special code for many subcases.
Likewise, /: and \: use different algorithms depending not only on
the internal type of the data, but also on the shape and on the
value. Special code are added all the time as reports are received
from J users on particularly useful subcases.
So i. might be O(n *^.n) where n is the number of atoms in x plus the
number of atoms in y, but time might be proportional to n for many
typical cases...
I see this as a tool to get people off the ground designing J
programs. System speed is a very practical constraint on program
design, and a little intelligence on what a person can expect seems
like a useful thing. If done right, it might alert people to
important program design issues.
--
Raul