Thursday, August 30, 2012

Default values of data types

Given default values for record data types like cons cells, then each place in the cons cell is optional, for example:
{} ;-> '(nil)
{first 10} ;-> (10)
{rest '(1 2)} ;-> (nil 1 2)
The constructor for the data type can be implemented by modifying places of the original cons cell. Consider colors as another example, we could declare that the default color value will be black. Now colors can be constructed using RGB or HSL:
{saturation 1, luminosity 0.5} ; red 
{blue 255} ; blue 
Another advantage of having default values for a data type, is that reducing any place becomes as simple as setting the value of that place to its corresponding default value, so for example, a butrest function could set the rest of a cons cell to the empty list. If a data type forms a lattice, the default value could just be the bottom element (e.g zero in positive total orders).

Tuesday, August 28, 2012

Shape dependent paralellism

Map, reverse, and transpose are paralell operations whose targeting scheme is dependent upon the shape of their argument. For example, here is the targeting scheme generated by the map operation on a list whose shape (or size) is 3 with respect to func:
{(nth 0) func
 (nth 1) func
 (nth 2) func}
On the other hand, reverse operation runs swap operations in parallel. With respect to a list of size five, the reverse operation runs two shape operations leaving the middle unchanged
{(list-places (nth 0) (nth 4)) swap
 (list-places (nth 1) (nth 3)) swap}
Here is the transpose operation on a matrix that is shaped like [[0 1 2] [3 4 5]]:
{(list-places (nth 1) (nth 3) (nth 4) (nth 2)) (shift 4)
 (list-places (compose first dimensions) 
              (compose second dimensions)) swap}}
The transpose operation is much more complicated then the others because it also reverses the dimensions of the grid.

Saturday, August 25, 2012

Association structures

A variety of data structures can be described as associations of values to places:
  • Records: have a finite collection of places. For example, colors have :red, :green, and :blue places.
  • Lists: have an infinite and enumerated set of places. The places in lists and vectors are enumerated by the nth function.
  • Hashes: may have anything, even other hashes, as places.
Lists and hashes can both be generalized to container types because unlike records they contain an infinite number of places.

Friday, August 24, 2012

Partitions in lattice theory

Sets are 0-partitions, using the lattice of sets under union and intersection, we can further create a lattice of 1-partitions, a lattice of 2-partitions, and so on.

Saturday, August 11, 2012

The lattice of multisets

The join operation in the multiset lattice is provided by taking the maximum value of each key present in any of the multisets and the meet operation is provided by taking the corresponding minimum value.
(defn join-multisets-by
 [func]
 
 (fn 
  ([] {})
  ([a] a)
  ([a b]
    (apply merge
      (map
        (fn [key]
          (func 
            (if (contains? a key) (get a key) 0)
            (if (contains? b key) (get b key) 0)))
        (clojure.set/union (keys a) (keys b))))
  ([a b & more] (reduce func (func a b) more))))
  
(def join-multisets (join-multisets-by max))
(def meet-multisets (join-multisets-by min))
Sets can be defined as a particular type of multisets whose values are all equal to one, as such the set lattice is a sublattice of the multiset lattice dealing with just sets. On the other hand, multisets can be represented as sets by replacing the value for each key with an interval set from the minimal value to that number. All distributive lattices can be represented in terms of the multiset lattice.