MyNixOS website logo
Description

A library for GTA programming.

This package provides the core functionalities of the GTA (Generate, Test, and Aggregate) programming framework on Haskell (c.f., Kento Emoto, Sebastian Fischer, Zhenjiang Hu: Generate, Test, and Aggregate - A Calculation-based Framework for Systematic Parallel Programming with MapReduce. ESOP 2012: 254-273. The authors' version is available at http://www.ipl-lab.org/~emoto/ESOP2012.pdf).

Example

The following code is a GTA program to solve the 0-1 Knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem). It appears to be an exponential cost proram in the number of input items, because it appears to generate all item selections by subsP items (Generate), discard those with total weight heavier than the knapsack's capacity by filterBy weightlimit capacity (Test), and take the most valuable selection by aggregateBy maxsumsolutionWith getValue (Aggregate). However, it actually runs in a linear time owing to our proposed program transformation 'Filter-embedding Semiring Fusion' implemented in the library. In addition, it runs in parallel so that you can get linear speedup.

knapsack capacity items =
 subsP items
 `filterBy` weightlimit capacity
 `aggregateBy` maxsumsolutionWith getValue

getValue (_, v) = v
getWeight (w, _) = w

weightlimit w = (<=w) <.> weightsum where
  weightsum = homJ' times single nil
  x1 `times` x2  = (   x1 +    x2) `min` (w+1)
  single i  = getWeight i `min` (w+1)
  nil = 0

Several examples of GTA programming are found in examples directory at https://bitbucket.org/emoto/gtalib/src.

Metadata

Version

0.0.6

Platforms (75)

    Darwin
    FreeBSD
    Genode
    GHCJS
    Linux
    MMIXware
    NetBSD
    none
    OpenBSD
    Redox
    Solaris
    WASI
    Windows
Show all
  • aarch64-darwin
  • aarch64-genode
  • aarch64-linux
  • aarch64-netbsd
  • aarch64-none
  • aarch64_be-none
  • arm-none
  • armv5tel-linux
  • armv6l-linux
  • armv6l-netbsd
  • armv6l-none
  • armv7a-darwin
  • armv7a-linux
  • armv7a-netbsd
  • armv7l-linux
  • armv7l-netbsd
  • avr-none
  • i686-cygwin
  • i686-darwin
  • i686-freebsd
  • i686-genode
  • i686-linux
  • i686-netbsd
  • i686-none
  • i686-openbsd
  • i686-windows
  • javascript-ghcjs
  • loongarch64-linux
  • m68k-linux
  • m68k-netbsd
  • m68k-none
  • microblaze-linux
  • microblaze-none
  • microblazeel-linux
  • microblazeel-none
  • mips-linux
  • mips-none
  • mips64-linux
  • mips64-none
  • mips64el-linux
  • mipsel-linux
  • mipsel-netbsd
  • mmix-mmixware
  • msp430-none
  • or1k-none
  • powerpc-netbsd
  • powerpc-none
  • powerpc64-linux
  • powerpc64le-linux
  • powerpcle-none
  • riscv32-linux
  • riscv32-netbsd
  • riscv32-none
  • riscv64-linux
  • riscv64-netbsd
  • riscv64-none
  • rx-none
  • s390-linux
  • s390-none
  • s390x-linux
  • s390x-none
  • vc4-none
  • wasm32-wasi
  • wasm64-wasi
  • x86_64-cygwin
  • x86_64-darwin
  • x86_64-freebsd
  • x86_64-genode
  • x86_64-linux
  • x86_64-netbsd
  • x86_64-none
  • x86_64-openbsd
  • x86_64-redox
  • x86_64-solaris
  • x86_64-windows