Thursday, September 27, 2012

Artificial sentience

Where as knowledge based systems like cyc passively describe the world, sentient agents actively change the world to suit their preferences. Selecting a preferred object amongst a group of equal objects in an equivalence class is called canonization, this can be implemented mathematically without mentioning time. On the other hand, selecting a sequences of actions to undertake under temporal constraints is known as planning.

Most modern programming languages already come equipped with a natural ordering relation which is a sort of preferences with respect to mathematical structures. In clojure the natural ordering relation extends compare and it can be accessed by printing a hash set:
(= (set (list 1 10 [1 2] (list 5 6) #{8}))
   #{1 '(5 6) [1 2] #{8} 10}) 
By maximizing with respect to a preference relation such as clojure's natural ordering relation we can convert any object into canonical form. Furthermore, since code is just another type of data structure in Lisp we can canonize code with respect to its equivalence relations:
(= (* 2 (+ 1 3 (inc (dec x))))
   (+ (* 2 x) 8))
The above canonization uses the equivalence relations of invertibility, associativity, and additivity (see the maxima operator properties). There are multiple ways to canonize code, so the canonical form corresponds to certain preferences such as that addition is preferred over multiplication. Computer algebra systems such as maxima can be described as systems of equivalence relations, well a separate component can be used to convert equivalent data structures to canonical form.

Planning domains:
PDDL (planing domain definition language) comes with the means to completely describe any planning domain, by describing the actions that can be taken in the planning domain and preferable actions that may have an associated metric for describing their utility:
  (and (preference pref1 (always (clean truck1)))
       (preference pref2 (and (at end (at package2 paris))
                              (sometime (clean track1))))))

(:metric (+ (* 8  (is-violated pref1))
            (* 16 (is-violated pref2)))
Sometimes our only way of evaluating the utility of any action is to measure how much closer it makes us to achieving our goals. In such a case we need to use a meta-heuristic evaluation function to decide upon an action. For example, in chess are only way of determining which move is the best is determine which one is most likely to allow us to checkmate the opponent at some point in the future. A sentient agent should have a variety of heuristics and AI optimization techniques at its disposal for achieving its goals.

Sunday, September 23, 2012

Extensional functions

When a function is defined extensionally, the partition that function induces on its domain (the kernel of the function) can be explicitly specified. For example, the partition that the or function induces is:
#{#{[false false]}
  #{[false true]
    [true false]
    [true true]}}
In order to use the kernel in the implementation of the function, we need some way to select preferred elements of each equivalence class. In this case, we can use the natural ordering as a selector. Finally, we need a injective part that reversibly modifies arguments:
{[false false] false
 [true true] true}
These components combined together can be used to define the and function or any other extensional function. On the other hand, explicitly defining the kernel of an intensional function causes problems under function composition.

Tuesday, September 18, 2012

Purely functional term rewriting

Unlike the usually side effect inducing operation eval, term reduction is an idempotent and purely functional operation that reduces a set of terms to canonical form. Macroexpansion is essentially the first phase in term reduction:
 '(-> [4 3 2 1] rest reverse))
The macroexpansion described in the above expression yields:
(reverse (rest [4 3 2 1]))
The next stage of term reduction is to apply the pure functions first and reverse to get the list (1 2 3). However, Clojure doesn't have any advanced facilities of term reduction to achieve that effect and even macroexpand-all has to be brought in from a separate module outside of the core.

Monday, September 10, 2012

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.

Sunday, September 9, 2012

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.

Monday, September 3, 2012

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.