Libraries

Looking to contribute to the Fortress library effort, but don't know where to start? Look no further! Any library coding you do for Fortress will of course be appreciated, but we're particularly keen to solicit contributions in these areas:

Collection Classes

There are two basic versions of the collections hierarchy: an immutable one, which must be implemented by every single Collections type, and a mutable one, which is not supported by every collection type. Note that every collection operation must appear to be atomic from the perspective of client code. For completely immutable collections this will not be an issue. For collections which make use of mutation, either because they provide the mutable collection interface or because they make use of mutation internally, this requires a certain amount of care. It is simplest to declare all the methods on these objects to be atomic. In practice, of course, there are more efficient (but much trickier) ways of writing collection types to provide the appearance of atomicity.

Some collection data structures we would love to see

• Red-Black trees (important: must include a merge / union operation)
• Digital tries
• Hash tables
• BDDs, as sets, maps, and relations.
• B-Trees
• Sets based on sorted lists
• Any other good set or map data structure. See trunk/ProjectFortress/test_library/Set.fss and trunk/ProjectFortress/test_library/Map.fss for appropriate pure apis; these use weight-balanced trees.
• Prefix and suffix trees
• Queues (pure queues supported by PureList.fss and ArrayList.fss)
• Deques (pure deques supported by PureList.fss and ArrayList.fss)
• Finger trees (see PureList.fss)
• Array-based lists (see ArrayList.fss)
• Priority queues (see Heap.fss, though better implementations welcome)
• Catenable deques (again see PureList.fss and ArrayList.fss)
• Pure Skip Lists (see SkipList.fss courtesy of Michael Spiegel)
• Simple bindings to give a mutable interface to an immutable collection of a particular type, and vice versa (the latter should be easy).
• Simple binding to turn a map implementation into a bag implementation by storing counts of occurrences of elements.
• Simple binding to turn a map into a set using void values.
• Simple binding to turn a map and a set into a relation.

The collection hierarchy (current proposal)

Collection
    Multiset
        List
            Tree
                SortedTree
            SortedList
                SortedTree
                SortedListWithNoDuplicates
            ListWithNoDuplicates
                SortedListWithNoDuplicates
            Array1D
        Set = MultisetWithNoDuplicates
            SetWithComplements
                SetOverFiniteDomain
        SortedMultiset
            SortedList
        Histogram
        Array
            Array1D
            Array2D
            Array3D
            ...
    RelationCollection
        Relation
            Map
            SortedRelation
                SortedMap
        MapCollection
            Map
                SortedMap
                    Array1D
                Array
            SortedMapCollection
                SortedMap
        SortedRelationCollection
            SortedRelation
            SortedMapCollection
    SortedCollection
        SortedList
        SortedRelationCollection

A collection API

We haven't yet fixed a base class for collections, but here is some of the basic functionality a collection might contain. These are all written in method style; since the interpreter doesn't currently support functional methods, operators will be defined to call through to methods. Note that many of these will have default implementations, and usually want to be specialized for arguments of the same collection type rather than for generic collections.

Immutable:

• Must extend Generator as appropriate, and provide a generate method.
• A vararg factory, and another factory which takes a generator as an argument. These should probably be overloadings of the same function (a braketing operator where appropriate).
• An empty collection of appropriate name and type (and eventually with a coercion from Empty). This could be a 0-argument invocation of the factory.
• opr =, in terms of opr = on elements (all mentions of !"equal!" here mean !"according to opr =!").
• toString()
• add(x) to add a single element x and return a new collection; by default it adds to the front of an ordered collection.
• addEnd(x) to add a single element x and return a new collection; by default it adds to the end of an ordered collection.
• adjoin(c) returns a new collection containing the elements of this collection and the elements of c; this collection comes first if they are ordered. This corresponds to opr UNION on sets. For parallelism it is important to make this efficient.
• adjoinDisjoint(c) works as adjoin but requires that c be nonoverlapping with the present collection.
• remove(x) returns a new collection in which all occurrences of x (in the sense of opr =) have been removed.
• removeFirst(x) returns a new collection in which one occence of x (the first, if ordered) has been removed.
• disjoin(c) returns a new collection containing the elements of this collection, with any elements opr = to those in c removed. This is equivalent to set difference on sets. If order matters, it is preserved in the new collection.
• intersect(c) returns a new collection containing the elements of this collection which also occur in c. This is equivalent to intersection on sets. Again, if order matters it is preserved in the new collection.
• contains(x) returns true if the collection contains an element opr = to x. This is equivalent to opr ELEM
• isEmpty() returns true if the collection is empty.
• overlaps(c) returns true if the collection has any elements in common with c.
• size() returns the number of elements in the collection.
• occurrencesOf(x) returns the number of occurrences of element x in the collection.
• first() returns the first element of the collection (which can be arbitrary if the collection is unordered).
• firstRest() returns a pair of the first element and the remainder of the collection with the first element removed.
• last() returns the last element of the collection (again arbitrary if the collection is unordered).
• initLast() returns a pair of the collection without the last element, and the last element.
• opr [i:ZZ32] and indices generator for ordered collections (0-indexed access).
• opr [k:K] and indices generator for maps.
• indexOf(x), index of first occurrence of x in an ordered collection.
• values() collection for a map.
• inverse() convert a map or relation to a relation

For maps and relations, most of the above methods are in terms of keys. Insertion should take a (key,value) pair.

The mutable interface is much the same, but adds "To" to adders, so we get addTo and addToEnd and adjoinTo, and adds "From" to removers, so we get removeFrom and firstFrom. In both cases the return type is () to avoid confusion with the non-mutable functionality.

Numeric libraries and solvers

• Useful transcendental functions currently lacking: hyperbolics, Gaussian error functions, Bessel functions, etc.
• Complex numbers
• Rational numbers
• Polynomials
• Quaternions
• Infinite-precision real arithmetic
• Implicit numeric differentiation (in which derivatives are computed alongside point data)
• Root finding of various sorts (Newton's method, binary decomposition, etc.)
• FFT
• Cholesky factorization
• Anything in BLAS, LAPACK, and LINPACK
• Realistic conjugate gradient implementations with preconditioners
• Eigenvalue methods of all kinds
• Linear programming, dense and sparse
• Integer linear programming

Sparse grid representations

• Mesh representations and DeLaunay triangulation
• Multigrid representations, with refinement methods
• Space-partitioning representations such as quad- and oct-trees

Bindings to existing Java functionality

• Binary input and output
• Efficient numeric arrays
• Bindings to existing libraries such as ATLAS and FFTW (requires JNI + implementation hacking, but well worth it)

Input and Output

• A printf or Fortran format equivalent
• Pretty printing library
• Combinator-based parser library