Reversible Lisp reader

The REPL loop that defines traditional list development is described by intertwining an eval operation between read and print operations, where read and print are inverses of one another. Unfortunately, most Lisp implentations do not take into account the reversibility of read and print, because their read implementations lose the whitespace around terms whenever they are called. We can rectify this by storing whitespace as representation metadata:

(with-meta '(1 2 3) {:ws ["  " "," "," "  "]})

Using this method we can convert from that sequence data structure to and from its corresponding string value:

"(  1,2,3  )"

This could be used to improve structured programming, for example you could reverse the list in place without losing the corresponding whitespace:

"(  3,2,1  )"

The whitespace was left unchanged by the rearrangement of elements. Mrging these two collections will just involve concatenating the strings in between the parenthesis of each of these structures:

"(  1,2,3    3,2,1  )"

This could also be used to switch between a visual interface to Lisp code and a textual interface, which hopefully will be an important part of Lisp development at some point in the future.

Iteration classes

The relation between iterates is an equivalence relation. The equivalence classes of this relation are called iteration classes. Non-iterable functions, involutions, and reductions all have a single distinct iteration element so their iteration classes are trivial.

Cycles can be reduced to iterations of an element whose first two elements are minimal. On the other hand, finite automorphisms that have different orders are iterates of one another if the element with the larger order can be iterated by its own order divided by the order of the other element to get the other element.

Iteration properties

Every monoid element has two sets associated with it that define the properties of its iteration:

• Iteration set: this define the set of numbers with which this function can be iterated over. Injective functions include -1 as in their iteration set.
• Iteration equivalence relation: this defines equivalent iteration numbers, for example, all iterations other then zero are equal to one with idempotent elements.

These sets can be described as a single partition of the real numbers that includes a specially flagged set of invalid values. The iteration properties of an element form a distributive lattice, and the meet operation in this lattice describes the iteration properties of the composition of several elements.

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).

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.

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.

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.