Any way to do prefix sums?

[eleses]

I can do postfix ones easily

postsum(1,    x  ) = x;
postsum(2, (x,y) ) = x+y, y;
postsum(n, (x,xs)) = x + (postxs : ba.selector(0, n-1)), postxs with {
    postxs = postsum(n-1,xs);
}; 

Test e.g. with

durs = (2, 1, 0.1);
M = outputs(durs);
plot = par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _;
process = _ <: attach(_, postsum(M, durs) : plot);

But if I try to pass a reversed 'list' in, that fails due to structural matching on the reversor itself!

presum(n, x) = postsum(n, xr) with {
    xr = x : ro.cross(n);
}; 

process = _ <: attach(_, presum(M, durs) : plot);

gives

ERROR : pattern matching failed, no rule of case {(<x>,<xs>,<n>) => (x,(postxs : ba.selector(n,1 : -,0)) : +),postxs with { {cons[cons[BoxIdent[postxs],BoxAppl[BoxIdent[postsum],cons[BoxIdent[xs],cons[BoxSeq[BoxPar[BoxIdent[n],1],BoxPrim2[ptr:0xc]],nil]]]],nil]} }; (<x>,<y>,2) => (x,y : +),y; (<x>,1) => x; } matches argument list (3,2,1,0.1 : route(3,3,1,3,2,2,3,1))

And I don't know how to do prefix sums (more) directly, since I can't pattern match the last element of a 'list', can I?

(Prefix rather postfix sums are musically more relevant, since that's what's needed to get the start times of events/notes from their durations, e.g. in a sequencer. So prefix sums computation should probably be part of some Faust library.)

[sletz]

Something like:

import("stdfaust.lib");

presum(1, x) = x;
presum(2, (x, y)) = x, x + y;
presum(n, (x, xs)) = x, postxs with {
  postxs = presum(n-1, xs) : par(i, n-1, +(x));
};

durs = (2, 1, 0.1);
M = outputs(durs);  // Gives 3
plot = par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _;

// Use prefix sums to get note start times
process = _ <: attach(_, presum(M, durs) : plot);

[eleses]

I think that's O(n^2) isn't it?

The matching problem is that a simple def of tail like

tail((x,xs)) = xs;

only works for literal lists like

t = tail((1,2,3));

but not for something like

t3 = (1,2,3);
t2 = tail(t3 : ro.cross(3)) ;

To work around that, we can use route though.

tailn(n) = route(n, n-1, par(i, n-1, (i+2, i+1)));

This works for everything, e.g.

t3 : ro.cross(3) : tailn(3);

but is inefficient I think because tailn is O(n) not O(1).

[eleses]

To avoid giving the compiler too much advantage, I tried the version where it gets input from sliders...

import("stdfaust.lib");

presum(1, x) = x;
presum(2, (x, y)) = x, x + y;
presum(n, (x, xs)) = x, postxs with {
  postxs = presum(n-1, xs) : par(i, n-1, +(x));
};

M = 3;

durs = par(i, M, hslider("Dur%2i", M - i - 1, 0, M - 1, .001));
// ^^ err in vgroup("[0]Durations", ... though!

plot = vgroup("[1]Times ", 
    par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _);

// Use prefix sums to get note start times
process = _ <: attach(_, presum(M, durs) : plot);

That one compiles to something that repeats some sums, i.e. fSlow1 + fSlow0 are computed twice in the C code. So, unless the C compiler itself optimizes that out, in general, this an O(n^2) solution even at runtime, but at least it works... (A 64-step seq will have 2048 additions or something like that.)

	float fSlow0 = (float)(dsp->fHslider0);
	float fSlow1 = (float)(dsp->fHslider2);
	dsp->fVbargraph0 = (FAUSTFLOAT)(fSlow1 + (float)(dsp->fHslider1) + fSlow0);
	dsp->fVbargraph1 = (FAUSTFLOAT)(fSlow1);
	dsp->fVbargraph2 = (FAUSTFLOAT)(fSlow0 + fSlow1);
	float fSlow2 = dsp->fVbargraph2 + dsp->fVbargraph1 + dsp->fVbargraph0;

[eleses]

Alternative version with broken down steps (one addition each) that alas turned out to be a waste of time.

sumstep(N, K, x) = par (i, N, Sx(i, K)) with {
    xprev = x : ba.selector(K-1, N);
    xcrt  = x : ba.selector(K, N);
    Sx(j,j) = xcrt + xprev;
    Sx(j,z) = x : ba.selector(j, N);
};

presumN(N, 1, x) = x;
presumN(N, K, x) = sumstep(N, K-1, presumN(N, K-1, x));

presumAll(N, x) = presumN(N, N, x);

M = 4;
durs = par(i, M, hslider("Dur%2i", M - i - 1, 0, M - 1, .001));
ehh = presumAll(M, durs);
plot = hgroup("[1]Times ", 
    par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _);
process = _ <: attach(_, ehh : plot);

Oddly enough, the Faust compiler still generates O(N^2) additions from this code too:

	float fSlow0 = (float)(dsp->fHslider0);
	float fSlow1 = (float)(dsp->fHslider2);
	float fSlow2 = (float)(dsp->fHslider3);
	dsp->fVbargraph0 = (FAUSTFLOAT)(fSlow2 + fSlow1 + (float)(dsp->fHslider1) + fSlow0);
	dsp->fVbargraph1 = (FAUSTFLOAT)(fSlow2 + fSlow0 + fSlow1);
	dsp->fVbargraph2 = (FAUSTFLOAT)(fSlow2);
	dsp->fVbargraph3 = (FAUSTFLOAT)(fSlow1 + fSlow2);
	float fSlow3 = dsp->fVbargraph3 + dsp->fVbargraph2 + dsp->fVbargraph1 + dsp->fVbargraph0;

I'm guessing it's because the Faust compiler tries to write in SSA form everything based directly on inputs. But there's probably more I don't understand (relating to those local variables?) because the postfix sums (initia code I posted) don't exhibit that problem.

	float fSlow0 = (float)(dsp->fHslider1);
	float fSlow1 = fSlow0 + (float)(dsp->fHslider0);
	float fSlow2 = (float)(dsp->fHslider2) + fSlow1;
	dsp->fVbargraph0 = (FAUSTFLOAT)((float)(dsp->fHslider3) + fSlow2);
	dsp->fVbargraph1 = (FAUSTFLOAT)(fSlow0);
	dsp->fVbargraph2 = (FAUSTFLOAT)(fSlow2);
	dsp->fVbargraph3 = (FAUSTFLOAT)(fSlow1);
	float fSlow3 = dsp->fVbargraph3 + dsp->fVbargraph2 + dsp->fVbargraph1 + dsp->fVbargraph0;

So the Faust compiler was happy to use intermediate results in that case!

[eleses]

I used the method I self-discovered here to turn the above into a clear sequential circuit:

import("stdfaust.lib");

M = 4;
durs = par(i, M, hslider("Dur%2i", M - i, 0, M, .001));
plot = hgroup("[1]Times ", 
    par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _);

sumstepA(K, x) = par (i, N, Sx(i, K)) with {
    N = outputs(x);
    Sx(j,j) = (x : ba.selector(j-1, N)) + (x : ba.selector(j, N));
    Sx(j,z) = x : ba.selector(j, N);
};

busAdapter(N, someAbstr) = si.bus(N) <: someAbstr(si.bus(N));

sumstepAbus(K) = busAdapter(M, sumstepA(K));

magic = seq(i, M, sumstepAbus(i+1)); // can just sequence stages now

hmm = durs : magic;

process = _ <: attach(_, hmm : plot);

But that doesn't fix the O(n^2) additions generation alas. And while the diagram is a single page now in the relevant portion, I don't understand the merge nodes. Where do they come from and what do they signify? I can't be addition because then the formulas would be wrong, but the UI is working properly. I don't get these merge nodes in postfix sum program, so they probably related to the O(n^2) additions though.