## Thursday, November 24, 2011

### Logic and binary trees

Lisp uses parenthesis notation to build tree structures. These trees are represented internally as binary trees that consist of cons cells with a car and cdr pointer:

Since all of our logic operations are based off of binary values, we can relate binary trees to boolean logic by associating the car node with false and the cdr node with tree. For example, here are the four unary logic operations:
(def contradiction    '())
(def logical-identity '(nil true)
(def logical-not      '(true))
(def tautology        '(true true))

With these four logic operations in place, binary logic operations can be defined:
(def logical-and (list contradiction identity))
(def logical-xor (list logical-identity logical-not))
(def logical-or  (list logical-identity tautology))

The correspondence between binary computers and binary trees is one thing in favor of current implementations of Lisp. Of course, Lisp is not implementation dependent so other representations of tree structures may be considered.

## Monday, November 21, 2011

### Computer graph system

My next programming project is to construct an effective computer graph system. Here are some examples of graphs this system might implement:
• Dataflow graphs which model computation using arrows between components.
• Molecular graphs which model physical structures in terms of chemical elements.
• Categories which model many abstract structures.
This system will be based upon nodes which contain links to one another. For example, Lisp cons cells are one type of node that have a unique next link. This sort of cell is powerful enough to effectively model all data structures, which is a fact most Lispers are familiar with.

Functions are one type of node with an $I \to O$ interface which generates some new output value for any input value. The implementation of the node can be freely modified so long as its interface remains in tact.

Morphisms are functions which contain another arrow $X \to Y$ representing a source set and a target set for the function. From there more complicated metadata can be used to describe functions, such as commutativity, associativity, invertibility, etc.