Data dependencies

We can associate an input place and an output place with every operation in order to model data dependencies. Bernstein's condition describes when two operations are independent and can therefore be executed in parallel.

Monoid action

Given a set $S$ of elements the monoid action on that set is defined by a collection of functions $S \to S$ that are closed under iteration and composition. Places form their own monoid actions on a set because there is a set of endofunctions that we can apply to a place using the zap function that is closed under composition and that includes the identity which doesn't effect that place at all.

Every single place on a set has $n^n$ transformations of the place where $n$ is the size of the place. The full transformation monoid on a set is defined by the operations on the top level place of the set and the trivial monoid is the set of transformations on the empty place.

It is often useful to use group actions on a set rather then monoid actions because the group actions partition the set into a set of orbits. This can be used to enumerate all the group actions on a set which is an invaluable technique in numerous combinatorial problems. We can use this to enumerate permutations, multiset permutations, permutations of a certain cycle type, equivalence relations, and many other combinatorial structures.

Mereological placehood relations

Common Lisp place forms are extended to become first class read-write (RW) parts and mereological methods are used as a method of reasoning about these place forms. Associations are introduced as data structures that explicity relate a set of independent places with a set of corresponding values.

https://github.com/jhuni/Placehood-relations/blob/master/Report.pdf?raw=true

Place form operations

Parallel operations are based upon mapping over non-overlapping collections of places, because the order of applications of functions in such mapping operations is irrelevant. This is implemented in the clojure pmap function:

(pmap inc [1 2 3 4 5])

Fine grained versioning is based upon enriching a log with a granularity relation such that log elements are sink nodes and all other elements are places.

The zap function in arc lisp

Arc provides the zap function which is a function that applies a transformation to some place form. The following examples of the zap function are provided by the arc documentation:

(let s "abc" (zap upcase (s 0)) s)
(let x '(10 10) (zap mod (car x) 3) x)

This provides a more general means of handling memory management operations then setf. Most memory management operations can be described in terms of zap.

Place forms

Common Lisp supports place forms with the setf function:

(setf (first coll) 10)
(setf (rest coll) '(20 30))

Place forms provide an elegant mechanism for handling parts of structures. This is arguably the most important distinguish feature of Common Lisp. Since Common Lisp is a Lisp-2, symbols have a symbol-function and a symbol-value part, which can be handled using setf:

(setf (symbol-function 'inc)
  (lambda (n)
    (+ n 1)))

(setf (symbol-value 'inc) 10)

An argument can be made in favor of Lisp-1's such as Clojure and Scheme, however, whatever the disadvantages of being a Lisp-2 are the use of place forms in Common Lisp make handling the parts of a symbol easy.