I want to describe a simple experiment Ive just done, a direct way to write code with medium level verbs in a semi-functional style in pure C.

All of this can be done in C++ and theres certainly more syntactic sugar there, but I wanted to explore the idea in C… C is close to the metal [but not too close, like assembler], compilers generate fairly good machine code, while the language supports a minimalist way to define functions [without lambdas, but we can use function pointers and context pointers to get that, if not in a type safe way].

Another approach would be to do it in C++ with operators and templates, much of it is reusable from STL and boost… yet another way would be to do it in ansi C and use MACROS heavily… but my experiment is to make simple, readable C code thats fairly quick.

In the K (terse) and Q (less terse) languages of KDB+, one can express something like this –

drawfrom:{[spec; vals; n]
mon: 0, sums nmlz spec; idx: mon bin n?1.0; vals[idx] }

Basically this reads –

function drawfrom(spec, vals, n)
mon = partial sums of spec (the cdf after normalizing to 1.0)
generate n random numbers uniformly in [0,1]
idx = array of indexes of each random sample into mon
return the values indexed by idx

So basically, this semi-functional zen kaon simply generates n random samples from the spectrum supplied.  Think of spec as the weights that determine how often each of vals appears – spec is a histogram or discrete pdf.  Actually this is the readable version, closer to Q than K, as Ive defined nmlz and used the verbose style – in K it can be much more ‘terse’ [proponents would say succinct].

At first this style of programming is annoying if your from a C++ background, but once you get used to it, you begin to think directly in terms of verbs working on vectors – In the same way that std::vector allows you to think at a higher level and avoid many for() loops by using accumulate and other languages the foreach construct…

So how does this look in C?  Try this –

V val = vnewseq(0.0, 1.0, n);
V pas = vnmlz(vpasc(vnew(n+1),n));
V draws = vnewspecdraw(pas, val, n);

Where vpasc makes a pascals triangle and vnmlz makes sure the array sums to 1.0.  Hmm.. we’ve kind of cheated though – we really need to build the last function from verbs also…

Expanding vnewspecdraw() we have the following C code –

V mon=vsums(vnmlz(vpasc(vnew(ns+1),ns)));
V draws=vnewrand(n);
I ix=inewbin(draws, mon);
vidx(draws, ix, vals);

Thats more in the spirit of constructing a useful script from simpler building block verbs… This is actually compilable once the simpler vfuncs are defined, and its a reasonably close translation of the K kaon we saw above.

Other useful vfuncs are vavg, vdev, vwavg [for mean, deviation, weighted average etc].  Its nice to build these from smaller blocks such as each(v, lambda_func) but they are common, and Ive coded them outright for the moment.

Ill upload an implementation of the vfuncs and sample source code soon… its fairly quick, sub-second to generate and do stats on 4million doubles… although the above code does create an extra copy of the array.  In fact I re-implemented it after looking at the memory allocations – but thats a valid development paradigm… get it working, test it, then optimize.

At some stage well look at doing a convolution filter using similar primitives… until  then happy quant coding!