Wednesday, December 26, 2012

Enumerative combinatorics

I have successfully enumerated a variety of mathematical structures by establishing a bijection between them and the natural numbers. Here are the first few sets and multisets:
(#{} #{0} #{1} #{0 1} #{2} #{0 2} #{1 2} #{0 1 2})
({} {0 1} {0 2} {1 1} {0 3} {1 2} {1 1, 0 1} {2 1})
The integers can be enumerated by defining the sign place as the first bit in a number and the absolute value as the value defined by the other bits:
(0 -0.0 1 -1 2 -2 3 -3 4 -4 5 -5)
The positive rational numbers can be enumerated by mapping over the enumeration of the multisets with an enumeration of the prime numbers and the enumeration of the integers.
(1 2 1/2 3 4 1/3 6 5 1/4 9)
All rational numbers can enumerated by using three places: a sign place with cardinality two, a natural part, and a fractional part. The fractional part is enumerated using eulers totient function.

Friday, December 14, 2012

Finite lattices

I have implemented the means to get the greatest upper bound and lowest upper bound of elements of a finite partial ordering relation. This can be used to completely define finite lattices such as the boolean lattice:
 (enum false true)
  [[0 1]
   [1 1]]))
The partial ordering relation of a set is described by its adjacency matrix. This implies that the lattices module requires the adjacency matrices library as a dependency.

Thursday, November 29, 2012

Representations of monoid elements

Using place forms data structures may have different representations with respect to different monoids, for example, with respect to or the false value is equal to nil and the true value is a collection with a single element. Exclusive disjunction uses the same representation except its single generator is an involution rather then an idempotent element:
{false {}
 true {1 1}}
Logical conjunction uses the negation of logical disjunction because these are the two elements of the boolean algebra with two distinct elements. Integers may be represented as the multiplicity of a single generator in an additive monoid, but in a multiplicative monoid they are a multiset with prime numbers as keys and exponents as values:
{1 12}
{2 2, 3 1}
Polynomials also have their on additive and multiplicative representations based upon factorization. The essential point here is that there may be many different representations of a single data structure depending upon the monoid that it is currently being handled by and these representations can be described by place forms.

Monday, November 26, 2012

Collections of monoid elements

All collections can be produced by monoids, for example, the concat operation produces ordered collections:
(= (concat '(1 2 3) '(4 5))
   '(1 2 3 4 5))
Although monoids describe how to build these collections, places are needed in order to describe how to represent them. The nth place is used to describe ordered collections:
(= '(1 2 3)
   {(nth 0) 1
    (nth 1) 2
    (nth 2) 3})
Multisets are produced by commutative monoids, and sets are produced by idempotent commutative monoids. Unordered collections are described by multiplicities. Furthermore, nil represents the empty collection.
(= (list-to-multiset '(1 1 2 3))
   {1 2, 2 1, 3 1})
In partially commutative monoids unordered collections and ordered collections can be combined together to form a partially commutative collection.

Thursday, November 15, 2012

Logical operations

The values true and false form a boolean lattice with logical disjunction and logical conjuction as meet and join operators and not as complement: (lattice. #{false true} or and not). This lattice induces the total ordering relation false < true which corresponds to logical implication. There is a dual lattice based upon the ordering relation true < false which uses converse implication.

The disjunction and conjunction operators are commutative monoids with a single non-trivial idempotent element. We can also form abelian groups with a single non-trivial involution element: logical biconditional and exclusive disjunction.

These abelian groups can be extended with a multiplication operation to form the finite field. The logical biconditional uses disjunction as multiplication and the exclusive disjunction uses conjunction as multiplication.

Exponentation has no effect in this finite field, so all polynomials can be reduced to binomials. Using zero as false and one as true all the polynomials in this field can be expressed as 0, 1, x, and x+1.

Friday, November 2, 2012

Local extrema of continuous functions

Reversible continuous functions such as the increment function and the cube function have no extrema and therefore they are either monotone increasing or monotone decreasing on their entire domain. The square function has a single extrema at the origin because it is monotone increasing on the positive numbers and monotone decreasing on the negative numbers.

Local extrema can be determined by the first derivative of a function. For example, polynomials with positive coefficients always have derivative with positive coefficients so they can never have any positive extrema. For example, the exp function we has coefficients that are all positive reciprocals of the factorial numbers, is always reversible on the positive real numbers by the ln function.

Wednesday, October 31, 2012

Monotone increasing sequences

Monotone increasing functions preserve some ordering relation. In this case, we will consider functions and sequences that are increasing in quantity such as those produced by range:
(= (range 4) '(0 1 2 3))
Ranges are all increasing by one. However, some values may be increasing to an increasing extent. This can be determined by the antireduce function:
(= (antireduce - '(0 1 3 6 10))
   '(0 1 2 3 4))
The triangular numbers are produced by additively reducing over the range and tetrahedral numbers are produced by using the same process on the triangular numbers. The fibonanci numbers are the additive reductions of themselves. Furthermore, the factorial function is produced by the multiplication reduction over the range.

Thursday, October 25, 2012

Ordering relations

The nodes a preorder can be partitioned into sets of equivalence classes such that for any ordered pair of nodes in an equivalence class there is a path between the two nodes. Every preorder is determined up to isomorphism by a partial ordering of its equivalence classes. Here are several types of preorder relations:
  • Equivance relation: the partial ordering relation is empty
  • Partial order: every equivalence class is trivial
If the partial ordering relation doesn't contain any undirected cycles that are greater then size two then it forms a tree. It is relatively easy to canonize directed trees and equivalence relations up to isomorphism by describing their shape. However, canonizing ordering relations that contain oriented cycles like the reachability partial order on {A -> B, A -> C, B -> D, C -> D} is a relatively complicated process.

Every relation has a reachability relation associated with it that preorders all nodes in terms of rather or not there is a path between them. Functions have a reachability relation between elements that is a tree of equivalence classes, and since permutations are the union of disjoint cycles their reachability relation is an equivalence relation.

Wednesday, October 24, 2012

Physical computing

My understanding of computing is largely based upon physical principles such as orthogonal persistence and the conservation of information:
  • Orthogonal persistence: state is represented with directly modifiable objects that don't require specific save / load actions.
  • Conservation of information: information cannot be created or destroyed, it can only be transferred and transformed.
Conversation of information is the basis of universal undo, which along with orthogonal persistence is a principle of good user interfaces. Parallelism is also a physical property, as there are always many things happening simultaneously at different places in the universe.

I believe that 21th century advances in self-configuring modular robotics will lead to programmable matter. Advancements in this area will unite physics and computing.

Friday, October 19, 2012

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.

Tuesday, October 2, 2012

The shape of an equivalence relation

Every equivalence relation has a multiset of equivalence class sizes associated with it that completely describes that equivalence relation up to relation isomorphism. For example,
(= (shape #{#{1,2,3} #{4 5}, #{6 7} #{8}})
   {3 1, 2 2, 1 1})
Divisions are precisely those equivalence relations that have only one distinct element in their multiset, so they evenly divide a set into parts:
(= (shape #{#{1,2}, #{3,4}, #{5,6}, #{7,8}})
   {2 4})
The division shapes {∞ 1} and {1 ∞} are the bottom and top level shapes, because {∞ 1} has no parts and {1 ∞} is the universal element that contains everything as a part. Place forms have divisions as their equivalence relation, such that the top place form is the identity function.

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.

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
  ([] {})
  ([a] a)
  ([a b]
    (apply merge
        (fn [key]
            (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.

Saturday, July 21, 2012

Grid dimensions

The dimensions of a grid are mutable, but the area of the grid is not. As such, in my computer algebra system the dimensions relation is implemented as a place:
(setf [dimensions [[1 2 3] [4 5 6]]] [3 2])
The transpose operation on matrices can be implemented as an automorphism that rearranges the elements of the collection and that reverses the dimensions of the grid.
(zap reverse [dimensions coll])
Any permutation operation, including reverse, can be applied to the dimensions place without every producing an error because permutations do not change the area part of the underlying grid structure.

Sunday, July 1, 2012

Reversible functional programming

In the current reversible functional programming framework implementation, all functions will have a set of places that that they effect in their argument. Functions that do not effect the :trash place are bijections. By default all functions trash their entire input and return their output, and they effect the top level place.

In our reversible FP framework, our interest is to deviate from the default setup by establishing bijections and zap functions whenever possible. Parallelism occurs when functions that effect separate places are composed together.

Friday, June 29, 2012

Linear ordinary differential operators

Linear ordinary differential operators are endomorphisms of differentiable vector spaces, and they can be decomposed into separate functions that handle the complementary solution $y_c$ and the particular solution $y_p$ of a differential vector space.

Linear differential operators are inverted by linear integral operators, for example, the diff operator is inverted by antidiff. A variety of methods can be used to make linear differential operators invertible including laplace transforms and series methods.

Monday, June 25, 2012

Commutative decomposition of endofunctions

All endofunctions can be described as the composition of zap operations. If two different places are disjoint, then zap operations involving them commute. For example, the cube function only effects the magnitude of a number and - only effects its sign so these functions commute:
(= (compose (polynomial. [0 0 0 1]) (polynomial. [0 -1]))
   (compose (polynomial. [0 -1]) (polynomial. [0 0 0 1])))
Doubling a number can be described as incrementing the multiplicity of the prime number factor 2 of the number, so multiplication commutes and $\mathbb{Q}+$ forms an abelian group. In general, two polynomials commute if they are either powers of x or chebyshev polynomials. First order homogeneous linear ordinary differential operators also commute under composition:
(= (compose (lodo. [0 1 1]) (lodo. [0 2 1]))
   (compose (lodo. [0 2 1]) (lodo. [0 1 1])))
The behavior of the composition of linear ordinary differential operators corresponds to polynomial multiplication. These operators can be described as endomorphisms of vector spaces of differentiable functions.

Thursday, June 14, 2012

Arithmetic module

The arithmetic module deals with functions that are built out of the of addition, multiplication, and composition. All of these higher order operations have derivative laws associated with them: the sum rule, the product rule, and the chain rule. As such, this module includes derivative operations.

Entire functions are described entirely using power series. The functions exp, sin, cos, sinh, cosh, erfi, the reciprocal of gamma, all polynomials, and all addition, multiplication, and compositions of entire functions are entire. However, entire functions are not closed under inversion or division so ln, sqrt, and tan are not entire.

Linear ordinary differential operators receive functions as arguments and then they output new functions using higher order operations and differentiation. Linear ordinary differential operators are closed under composition, so they form their compositional monoid. The derivative function itself is a differential operator that uses a hidden multimethod internally that dispatches on the type of its arguments.

Thursday, June 7, 2012

The regularity of relations

The regularity of relations first leads us to functions which are relations with a out degree regularity of one. Functions that also have an in degree regularity are place forms, and if the in degree regularity of a function is one then the function is one-to-one. Since bijections are just special cases of place forms you can apply all place form functions to them:
(setf [reverse coll] '(3 2 1))
;=> (1 2 3)
Functions that cannot be expressed as place forms are in degree irregular. Count is an example of such a function, because there is only one type of empty collection, and there are many other possible collections for the other sizes. Monoids are also irregular functions because there is a different number of partitions for different objects in most monoids, unless you consider the identity.

Sunday, May 27, 2012

Injective polynomials and linear maps

Injective polynomials have a single root of odd multiplicity, for example, here is an injective polynomial function:
(polynomial-exponentation (polynomial. [1 1]) 3)
Furthermore, injective linear maps have a non-zero determinant.

Tuesday, May 22, 2012

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.

Saturday, May 19, 2012

Clojure uninvoke

I have created a clojure library for reversible computing, by defining an uninvoke method that represents the inverse of the standard invoke method. This library is now available on github:

Monday, May 14, 2012

Lisp all the way down

Mathematics describes objects that have all their implementation and representation details abstracted away. For example, there are numerous numeral systems for representing the natural numbers, all of them equivalent. In category theory all objects are considered up to isomorphism and representations can be described as isomorphisms.

An important part of any computer algebra system is the system for selecting canonical representations for equivalence classes. In a Lisp all the way down system, representations can be described directly in terms of the physical hardware, for example, the exact bit layout of a number could be described.

Lisp all the way down systems allow you to convert abstract to the concrete, ideally using the related areas of decision making, optimisation, planning, and goal seeking along the way.

Wednesday, May 2, 2012

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.

Tuesday, May 1, 2012

Rational decision theory

In the perception action cycle (PAC) all actions that an agent takes must be selecting some part of a possibility space. Rational agents have preferences which order the possibility space, and they maximize the satisfication of those preferences in their selection process.

Two general areas of mathematical study: mereology and order theory are particularily relevant to choice theory. Mereology studies the parts of general structures, which can be applied to study the parts of the possibility space and order theory studies ordering relations which can be applied to studying preferences.

Monday, April 30, 2012

Maxima operator properties

Maxima provides a variety of operator properties to developers including linear, additive, multiplicative, outative, evenfun, oddfun, commutative, symmetric, antisymmetric, nary, lassociative, rassociative.

Linearity and distribution:
A function is additive or multiplicative if the use of addition or multiplication in the function can be distributed out into separate calls. A function is outative if constants can be distributed out, and a function is an oddfun if its sign can be distributed out. Finally, a function is linear if it is both additive and outative.

Input properties:
The operator properties commutative, symmetric, antisymmetric, evenfun, nary, lassociative, and rassociative describe the input properties of a function.

Saturday, April 28, 2012

Divisibility operations

Divide, undivide, factorize, and unfactorize are partition relations. Division takes a natural number and it splits it into quotient and remainder parts and the gcd function splits an unordered pair of numbers into the gcd and a fractional part. Fractional parts are useful in dealing with gunk mereology and the field of rational numbers.
(defn divide
  (fn [a]
    {:q (quot a n), 
     :r (rem a n)}))

(defn undivide 
  (fn [a]
    (+ (* n (:q a)) (:r a)))

(defn divides?
  [a b]

  (zero? (:r ((divide b) a))))

(defn divisors
  (filter (partial divides? n) (range 1 (inc n))))

(defn common-divisors
  [& nums]

  (apply clojure.set/intersection (map (comp set divisors) nums)))

(defn factorize-pair

  (let [gcd (apply max (apply common-divisors a))]
    {:gcd gcd,
     :fp (sort < (map (partial * (/ gcd)) a))}))

(defn unfactorize-pair
  (map (partial * (:gcd a)) (:fp a)))

Wednesday, April 25, 2012

Category of equivalence relations

The functions square and abs are equivalence relation isomorphic to one another because they both partitioned the set of all real numbers into positive and negative segments. If there is a one to one correspondence between all equivalence classes induced by an equivalence relation then that equivalence relation also induces a partition of members.

The category of equivalence relations is partially ordered by a coarseness relation that determines rather or not an equivalence relation is coarser, finer, or equal to another equivalence relation.

Tuesday, April 24, 2012

Modeling time with identities

An identity represents a series of values over time. Each identity can be associated with an equivalence class which describes the properties of the object that are conserved through transformations over time. If the equivalence class has only one element, then an identity represents a constant value.

I would like to propose that the conservative transformations model is more efficient then the write-once model that is common to the functional programming community. An identity is associated with an object that undergoes a series of property conserving transformations over time. For example, in physical systems mass and energy are conserved through transformations.

Sunday, April 22, 2012

Types of transformations

Reversible transformations change the form of an object but they do not create or destroy objects. Motion is effectively a reversible process of reconfiguring some object with respect to a reference frame. Mereological transformations include the composition of parts into wholes and the decomposition of wholes into parts:

Parts: pieces, components, fragments, sections, segments

Decomposition: break up, disintegrate, disunite, divide, divorce, segregate, separate, shatter, split, uncouple

Composition: amalgamate, coalesce, collect, compound, come together, combine, integrate, fuse, join, merge, mix, synthesize, unite

In a non-conservative system the act of destruction can be described as decomposing the system into parts and sending away a part to some other location such as a garbage dump and the act of creation can be described as fusion involving an object on the heap.

Wednesday, April 18, 2012

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.

Sunday, April 15, 2012

Progression of categories

Categories can be progressively enhanced by introducing new forms of relations:

(Objects, Edges)
(Sets, Functions)
(Categories, Funtors, Natural Transformations)

Saturday, April 7, 2012

Binary relations

The reachability condition on a directed graph is reflexive and transitive so it produces a preorder. Symmetric preorders are equivalence relations and antisymmetric preorders are partial orders. Equivalence relations are partially ordered in terms of fineness and coarseness.

Parthood relations form a partial order. In particular, parthood relations are often hierarchical in nature so they can be modelled by undirected trees or polytrees.

Many to one relations:
Many to one relations induce an equivalence relation whose equivalence classes are the many part of the relation. Many to one relations are strong simplification rules for equivalence relations.

Friday, March 30, 2012

Partitions and unions

A collection can be described as a whole that consists of several parts. Partition functions go from the whole to the parts and union functions go from the parts to the whole. Partitions and unions can be encoded in a single bijection that goes from the whole to the parts and back again. For example, here is a seqify function that goes from a whole object to first and rest parts:
(defn seqify

  {:first (first coll)
   :rest  (rest coll)})

(defn unseqify

  (vec (cons (:first coll) (:rest coll))))
All one-way functions operate on selected parts of a partition such that the returned whole cannot be reconstructed from the selected parts. For example, you can't reconstruct a list from its first element alone, so the first function is one-way. Monoids are union functions that join together several parts into a new whole and that have a notion of an empty part. Monoids are one-way functions because each object is the product of several different types of partitions.

Tuesday, March 27, 2012

Mathematical invariance

The no-effect? predicate returns true if the specified function doesn't apply to some value. The no-effect? predicate can be used to establish many other predicates, for example each part function can establish a predicate:
(def int? (partial no-effect? int))
(def unit-vector? (partial no-effect? unit-vector-part))
(def non-negative? (partial no-effect? (fn [i] (Math/abs i)))
An understanding of the no-effect? predicate can be used to eliminate unnecessary calls to one-way functions.

Sunday, March 25, 2012

Simplifying function calls

Argument equivalence:
A function is symmetric if arguments with different orders are all equivalent to one another:
(= (+ 1 2 3) 
   (apply + #{1 2 3}))
Monoids are variadic functions such that two adjacent constant arguments can be reduced by their application and other calls to the monoid can be reduced in place:
(= (* 1 2 3 (* 4 5) (+ x y))
   (* 120 (+ x y)))
Constant reduction and combiner rewriting
After reducing a function's input argument we can reduce the call to the function itself. If the argument given to the function is constant then we can replace the call to the function with its result:
(= (apply + #{1 2 3}) 6)
In certain conditions the call to the function can be replaced with the call to another function:
(= (* 120 (+ x y))
   (+ (* 120 x) (* 120 y)))
In this case, we can replace the multiplication operation with an addition operation using the distributive law.

Iteration equvialence:
Each function has an iteration equivalence relation associated with it that represents rather or not the function is equal when iterated to different numbers. This includes the order of the function which states a number which you can mod out of any iteration number without effecting it. Functions that have an order of two are involutions:
(comp reverse reverse)
(comp - -)
(comp / /)
(comp inc dec) 
If every value in the iteration equivalence relation is either equal to the identity or one then that function is idempotent:
(= (comp abs abs) abs)
(= (comp int int) int)
In order to use the iteration properties of a function it is important to know when two functions are of the same iteration class.

The reflexivity of a function describes an equivalence relation which states that certain parts of a data structure are uneffected by this function. For example, additive negation doesn't effect the absolute value of a number:
(= (comp abs -) abs)
The complemented of the targeted place of the function is included in the reflexivity because it isn't effected by applying the function.

Friday, March 23, 2012

Implementation of monoids

Monoids are functions that have the property that calls to the monoid within the monoid can be replaced with the arguments of the call. In other words, the order and amount of calls to the operation is irrelevant. Addition, concatenation, composition, and other related operations are all monoidal.
(+ 1 2 3)
(concat [1 2] [3 4])
(comp (partial apply +) range inc)
The set of quantities under multiplication forms a monoid. Furthermore, with respect to booleans there are two commutative monoids corresponding to the two possible identities. The function or? corresponds to a monoid with an identity of false and the function and? corresponds to a monoid with an identity of true. The computer algebra system can simplify the call to any monoid:
(defn simplify-monoid-call

   (first expr)
   (apply concat
           (fn [current-expr]
             (if (and (seq? current-expr)
                      (= (first expr) (first current-expr)))
               (rest (simplify-monoid-call current-expr))
               (list current-expr)))
           (rest expr)))))
Here is an example of how this function might work:
(= (simplify-monoid-call '(+ 1 2 (+ 3 4) 5 (+))
  '(+ 1 2 3 4 5))
This is one small step towards building an effective Lisp based computer algebra system.

Sunday, March 18, 2012

Multiply perfect numbers

The first three multiply perfect numbers are 1, 6, and 120. These three numbers are both factorials and triangular. They also appear to be the only numbers that exhibit that property.

The numbers 1 and 6 are the only numbers that are triangular and factorial with respect to the same argument because 1 is both the sum and the product of the first one numbers and 6 is both the sum and product of the first three numbers.

The only number that appears to be factorial and triangular to a different argument is 120 which is the product of the first five numbers and the sum of the first fifteen. Interestingly, 120 is also a tetrahedral number.

Friday, March 2, 2012

Artificial systems thinking

In the future, strong AI should be able to see the connections between diverse groups of subjects through the creation of graph structures. Humans have never been able to achieve such an effect because human natural intelligence was not engineered to create an optimal understanding relations, interactions, and connections.

The process of artificial systems thinking unites the areas of AI and systems thinking. In this process, we will create all the fundamental substrates for effective systems thinking in the machine.

The most important tool for systems thinking is the understanding of relations using graph theory, so this sort of AI will be based upon the management of graph theoretic structures in the machine.

Wednesday, January 25, 2012

Semantic web OS

In order to construct a semantic web OS we will have to forgo our dependence upon plain text files as a means of representing programs. Instead, in a semantic web OS, programs and data will be first class objects that are represented as interconnected graph structures.

In my opinion, the key to creating weak AI is to eliminate all arbitrary restrictions we place on our databases and to then transform them into sophisticated graph-theoretic knowledge representations. These representations can be unified into a singular semantic web, and that semantic web should in turn form the basis of all operating systems.

Today, the web is based upon HTML, CSS, and JavaScript which are immanently deficient, so they are not a suitable basis for an operating system. This is demonstrated by my own GoldOS project and all other "web OS" projects. Where all web OS projects have failed, perhaps a semantic web OS may someday succeed.

Tuesday, January 3, 2012

JVM libraries

Structured graphical user interfaces: At the moment, I have no particular interest in using an unstructured graphics library or constructing a structured graphics library of my own, so I have elected to use an existing library. After searching around, I have decided to use Piccolo2D since it has a particular emphasis on zooming and it has a solid and mature code base.

On 2D monitors a 2D graphics toolkit should generally be sufficient. However, sometimes it is interesting to play around with 3D graphics. As such, I may choose to play around with 3D graphics toolkits such as Java3D or Xiph3D.

Monday, January 2, 2012

S-expression syntax for associations

I have created a syntax for map structures compatible with Lisp. This notation treats the first element of a list as its key and the rest of the list as its value.
(% (np 2)
   (fp (numerator 10)
       (denominator 20)))
In order to evaluate a expression in the map you will need to use the unquote function.

Sunday, January 1, 2012

2011 year in review

This year I officially ended my search for a programming language by settling on the use of Lisp dialects like Scheme, Clojure, and Common Lisp for all of my development needs. It wasn't to hard for me to then chose to use Emacs as my editor of choice as Emacs remains the best editor for Lisp developers. I likewise chose to completely abandon the QWERTY keyboard layout in favour of Dvorak to make typing easier. By abandoning my old programming languages, editors, and keyboard layout this year has had a transformative effect on me.