built minipov2, ideas on

[Dave Long]

> PDM (pulse displacement modulation?  Is that what this is called?)

pulse density modulation

>> Economically, if actors in markets are too responsive, this
>> translates into boom-bust cycles.
>
> I see that it's sort of analogous in that the market is, in theory,
> seeking an equilibrium price; but are there other components to the
> analogy?  Does the positive feedback of "momentum investors" map to
> something in a digital output driver?  Does the Bresenham error
> counter map to some economic construct?

I think the error counter maps to expected profit.  If one looks at 
markets on a long-enough timescale (in the long run...) one hopes to 
find that they track an equilibrium price.  Similarly, a PWM/PDM looks 
like AM on a long enough timescale.  But at very short timescales, the 
PDM value is always either much too high or much too low.  The 
Bresenham error counter says "well, 1 is certainly a high value, but 
things are going up, so output another 1 ... no, too high, output 0 
next time instead", and the momentum investor alternates between 
irrational exuberance and depression, with the call of bull or bear 
market being the sign of the error counter comparison.

>> On a finer scale, one can look at the patterns of substitutions and
>> reductions over the course of a computation -- it is theoretically
>> possible to follow the PWM style, and do all of the substitutions,
>> followed by all of the reductions, but the exponential blow ups
>> involved mean that we usually compute more in the PDM style, and
>> interleave substitutions with reductions.[2]
>
> What do you mean by "reductions"?  Beta-reductions and eta-reductions
> are substitutions, aren't they?  Whether a particular lambda makes
> things bigger or smaller when you beta-reduce it depends on how many
> occurrences of its parameter it contains.

By "reductions", I mean there are three basic computational maps:
- quasiquote-like, substitute
   (pick out an element from a larger state space: S)
- forget aspects of something we have
   (yielding something in a smaller state space: K)
- map something to an isomorphic equivalent
   (the state space remains the same size: I)

So for reduction, maybe read forgetting, to avoid confusion with lambda 
terms.

>> I think Knuth argues that as long as we're throwing silicon at
>> things, might as well use 64-bit registers to do arbitrary 8x8
>> boolean matrix multiplies, of which shuffles are special cases.
>
> That's an interesting idea --- is it in MMIX?

MOR and MXOR on page 9 of the opcode fascicle.  They'll do byteswaps, 
but are much more general.  Maximal flows are MORs, and they yield 
minimum cuts -- hotspots worth optimizing.  There are many problems 
which involve the transitive closure of a single step reduction (just 
about any code with unbounded for(;;)-style loops?) but if one can 
precompute a closure relation with a matrix multiply it's possible to 
perform (or at least express, such as with K's converge operator) the 
calculation in a non-looping format.  Consider how we are willing to 
learn 55 entries (as opposed to 3) in a multiplication table so as to 
make fewer passes over the input figures.

What's a good MXOR problem?  (If I knew of any, I might be able to make 
some use of the '|' operator in dc)  Stuff involving groups instead of 
algebras, maybe?

How about rotation operations in a scene graph?  Instead of applying 
each transformation in a scene graph level by level, which is a 
tree-like operation best done in software, one can compose all the 
transformations into a single matrix for each leaf, yielding a flat 
list suitable for crunching with hardware.

> This puzzled me for a while, but I have an old welding textbook from
> Project Gutenberg that explains that arc welding must use DC --- AC
> welding would be completely impractical, because the majority of the
> energy of the spark is dissipated at the point where electrons hit
> metal, i.e. the anode.  I assume the arc welding of the time was TIG.
> No doubt the authors of the book were startled when MIG and stick
> welding became popular, which I guess was in part because they didn't
> need such fancy power supplies.

As long as the molten metal all winds up in the weld pool, we don't 
necessarily care which side of the arc it started from.

There's a computing analogy here: if one can get the same result with 
two different computation paths, it may be possible to take advantage 
of the option.  For instance, suppose we are interested in a derived 
property of a quickly changing input (for a functional spreadsheet, 
say).  One path is to track the changes, and for each change, 
incrementally update the output.  The other path is to apply all the 
changes to the input, and recalculate the output from scratch.  
Generally the first is better for simple changes, but the second for 
complex ones, so if one has an oracle (like the original curses for 
slow terminals) that can decide which path to take, one may get a 
performance improvement without necessarily exposing any complexity 
outside the subsystem.

The associativity of pipelines for things like MapReduce is another 
example: in a|b|c, as long as b gets done, we don't care if it breaks 
down operationally as (a|b)|c or as a|(b|c) (or even (a|b)|(b|c), for 
suitable kinds of b).  There should be an analogy here with bra-ket 
quantum calculations <a|b|c> = <ab|c> = <a|b*c> (if I haven't reversed 
the star) but, apart from a matrix-mechanics-like formulation of 
tuples/projection vs. labels/cases, it's been eluding me.

>> [2] in this model, one can compute (bresenham: move horizontally) or
>> output (bresenham: move vertically).  Would a transaction system, 
>> where
>> one can output UNDOes as well as DOes, then be somewhat like a
>> second-order delta-sigma?
>
> I still don't understand second-order delta-sigma conversion ...

And neither do I.  But at this point I think not, as the second-order 
delta-sigma seems to be about controlling the rate of change, rather 
than level, of the output.  (approximating pi by continued fractions 
does seem to be a good analogy for transaction processing, as there are 
enough representations available that one can produce output after 
narrowing the possibilities down to a pair of digits, rather than a 
single digit, and the subsequent output still has the option of finally 
producing the lower or the upper -- so there can be a finer 
interleaving of output and computation)

-Dave