search

conal / ftree

Depth-typed functor-based trees, both top-down and bottom-up
Other
3 stars 1 forks source link

Abandon this library? #3

Open conal opened 5 years ago

conal commented 5 years ago

I had forgotten about this library until @jrp2014 reminded me in issue #1, followed by pull request #1. I think I replaced the library with shaped-types, which also includes generic scan. Both are described in the paper Generic Functional Parallel Algorithms: Scan and FFT. I'm afraid there are also versions in the compiling-to-categories (CtC) repo examples (in Shaped, FFT, and Scan), which are almost certainly the versions I used in that same paper, since I used CtC to make the figures and to compile to massively parallel hardware (via Verilog).

Relative to ftree, I tried out a different approach to these data types in shaped-types and then stuck with it in CtC, which is to use closed type families instead of GADTs. See section 2.3 ("Statically Shaped Variations") of the Generic Parallel Functional paper for a comparison.

conal commented 5 years ago

I think my comment applies to generic-fft (see #1 there) as well as ftree.

Sorry about leaving these obsolete libraries behind.

jrp2014 commented 5 years ago

Thanks, Conal. I've had a look at the concat FFT version and will look at it in further depth. For example, if I do -DTESTING it tries to pull in the ApproxEq modules from the ShapedTypes library, so maybe that needs to be copied across into the concat Examples, and I'd like to get some simple dft / fft to run and try parallelising, since I take that to be the benefit of this approach.

I wouldn't do much more to these 'obsolete' libraries than update the README to point to the current frontier. They do have the advantage of seeming to be a bit tidier and easier to grok for the new reader.

I should also thank you for your generosity in making all this work available.

conal commented 5 years ago

Thanks for the suggestions. You may find ShapedTypes easier to follow, as it involves much less context. Ideally, one could use something like ShapedTypes independently from concat as well as with concat. The latter would enable one to visualize computations as graphs (including implicit parallelism), compile to Verilog for execution on FPGA etc, to something like OpenCL for GPU execution, or for use with automatic differentiation for machine learning etc. The shaped types are all suitable for auto-diff & ML in that they all give rise to vector spaces, giving a compelling alternative to the popular choice of multidimensional arrays (so-called "tensors").

jrp2014 commented 5 years ago

Thanks. My initial goal in exploring this is to be able to convolve a 1D complex / real Haskell List [] / Array or Vector and work up from there to ShapedTypes, parallelization, etc. I haven't managed to figure out how to (successfully) add the necessary instances to Sized in concat, eg. It should be almost trivial as all the machinery seems to be in place, but there is clearly something that I am not getting.

conal commented 5 years ago

I appreciate your persistence!

First, [] is not statically shaped (not a representable functor), so it doesn't suit FFT (but is fine for scan). Neither are the usual, dynamically sized Array and Vector types. You could instead use statically sized vectors from vector-sized as I do occasionally and experimentally in concat, but I doubt you'd learn much from doing so. The point of the generic parallel functional approach is to use the fundamental, compositional building blocks of data structures instead of the nearly pervasive choice of arrays, thus defining infinite families of correct parallel algorithms all at once (all possible combinations of these fundamental building blocks).

I have a paper in progress about how to automatically convert these lovely compositional parallel algorithms back into guaranteed-correct array algorithms suitable for GPU execution.

A main message of the "generic functional parallel" paper is that arrays (one- or multi-dimensional) are neither natural nor necessary, and they create unnecessary difficulties. Since arrays are a habitual, nearly universal choice in current practice of parallel programming, it may take a while for that message to spread.

jrp2014 commented 5 years ago

Thanks, Conal. That makes sense. I had passed over the representable part and was sort of hoping that you could start with a fixed array / list and then upgrade to feeding slices or views into the algorithm. For some uses, you will be given a list / vector / array (perhaps of fixed size). It will be interesting to understand the cost of converting from a conventional data structure to / from a Shape for use with the algorithm.

conal commented 5 years ago

I have a couple of schemes in mind to avoid paying any cost for data type conversion. More details when my data parallel programming paper is ready.

jrp2014 commented 5 years ago

Thanks, Conal. In the meantime I've come across a library https://github.com/ChrisPenner/grids that uses type programming to generate representable grids / lists with a bunch of comonad machinery, etc, to pull out slices and even do a bit of convolution. I'll have a look, to see whether, combining it with your ideas, yields any insights, pending your paper.