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.

No comments:

Post a Comment