Thursday, August 25, 2011

Cauchy sequences and intervals

The counting numbers are fundamental to all of computation. Using collections of counting numbers we can construct more complex objects, for example, the rational numbers can be constructed with three counting numbers: a numerator, a denominator, and a sign.

The rational numbers allow us to effectively confront most challenges; however, there are some numbers, known as the irrational numbers, in which can never be expressed as rational numbers. Just as you can never express infinity because there is always a greater number, there is always a greater rational approximation for any irrational number. Such values that can never be expressed because they always have another step that can always bring them closer to a target point are the convergence value of a cauchy sequence.

For example, one of the first irrational numbers discovered was the square root of two, which can be expressed in terms of the following cauchy sequence:

$$\sqrt{2} = \sum _{n = 0}^{\infty} {(-1)^{n + 1} \frac{(2n-3)!!}{(2n)!!}}$$

Most other popular irrational numbers like e, pi, or the golden ratio can be expressed in terms of cauchy sequences:

$$e = \sum _{n=0}^{\infty} {\frac{1}{n!}}$$
$$\pi = 4 \sum _{n=0}^{\infty} {\frac{(-1)^n}{2n+1}}$$
$$\varphi = [1; \overline{1}]$$

Although we can never acquire any of these values, we can approximate them in terms of intervals. For example, we know pi is in the interval between 3 and 4, and as we use our cauchy sequence we progressively narrow that range. Once we have constructed intervals, we are going to want to perform some operations on them, leading to interval arithmetic. These same methods approximation can be used for physical measurements.

Tuesday, August 23, 2011

Properties of operations

Some binary operations are either commutative or associative, as defined by a properties on their domain:

(defn commutative?
  [op]
  
  (∀ [a b]
    (= (op a b) 
       (op b a))))

(defn associative? 
  [op]
  
  (∀ [a b c]
    (= (op (op a b) c) 
       (op a (op b c)))))

An example binary operation is nand:

(defn nand
  [& nums]
  
  (case nums
    [false false] true
    [false true ] true
    [true  false] true
    [true  true ] false))

From its truth table you can immediately see that it is commutative. However, it is not associative because it applies to the following lists of length three:

[[false false false] 
 [false true  false] 
 [true  false false] 
 [true  true  false] 
 [true  true  true ]]

Which implies that the following case doesn't hold.

(/= (nand (nand false true) false))
    (nand false (nand true false)))

Many functions are both associative and commutative, such as addition and multiplication. If both of these properties apply then the functions arguments are orderless.

If the function's arguments are orderless then they can be thought of as a multiset. Multiple instances of the same member can be replaced using a higher hyper-operation:

(= (+ x y z x x y)
   (+ (* x 3)
      (* y 2)
      (* z 1)))

Other properties of binary operations are the identity element and the inverse element. If an operation has all these properties over a set, then it forms a group. If it is also commutative it is an abelian group.

Thursday, August 18, 2011

Latex DSL

As far as I am able to understand, Latex commands take the form:

\command[option1,option2]{arg1}{arg2}

This can easily be translated into Lisp:

(command [option1 option2] arg1 arg2)

That way I can use Lisp to produce Latex.

Tuesday, August 16, 2011

JavaScript DSL

I have created a DSL that directly translates to JavaScript.

(function factorial [n]
  (return
    (ternary-operator (== n 0)
      1
      (* n (factorial (- n 1))))))

The above code directly translates into the JavaScript factorial function. Along with prxml, this allows me to create entire web pages entirely in Lisp:

[:html
  [:head
    [:title "Welcome"]]
  [:body
    [:script {:type "text/javascript"}
      [:raw! (to-js '(alert "Hello World"))]]]]

I look forward to being able to use this to develop lots of webpages.

Monday, August 15, 2011

Numeral systems

Here is a function that can be used to evaluate any numeral:

(defn evaluate-numeral
  [numerals radix]

  (apply +
  (map-indexed
   (fn [i v]
     (* v (Math/pow radix (- (dec (count numerals)) i))))
   numerals)))

(= (evaluate-numeral '(1 0 1 0 1) 2)
   21)

You can also evaluate the amount of digits needed for a number in any numeral system:

(defn digits-in-number
  [num radix]

  (inc (Math/floor (/ (Math/log num) (Math/log radix)))))

(= (digits-in-number 255 2)
   8)

Basic predicate functions

After discussing sets and predicates in my previous post I have come up with some basic predicate functions:

(def every-true? (partial every? true?))
(def some-true? (comp not nil? (partial some #{true})))

(defn union
  [& predicates]

  (fn [& obj]
    (every-true? (map (fn [predicate] (apply predicate obj)) predicates))))

(defn intersection
  [& predicates]

  (fn [& obj]
    (some-true? (map (fn [predicate] (apply predicate obj)) predicates))))

(defn cartesian-product
  [& predicates]

  (fn [& obj]
    (and
     (= (count obj) (count predicates))
     (every-true?
      (map
       (fn [i]
         (apply (nth predicates i) (nth obj i)))
       (range 0 (count obj)))))))

Saturday, August 13, 2011

Sets and predicates

Set theory doesn't make any distinction between sets defined extensionally (sets) or sets defined intensionally (predicates). Here are some sets:

#{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
#{0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

Here are the same things as predicates:

(fn [n] (<= 0 n 10))
(fn [n] (and (even? n) (<= 0 n 20)))

Some means must be developed to deal with these two different presentations of classes.

Thursday, August 11, 2011

Mathematical universe hypothesis

Not only am I a mathematical realist, I go one step further by stating that mathematical structures are all that exist (mathematical monism). This is epitomised by Max Tegmarks mathematical universe hypothesis (MUH).


For me, this belief arose from constantly thinking in terms of immutability, which eventually lead me to think of spacetime as an immutable object with time as another dimension.

Additionally, we keep discovering mathematical regularities in spacetime, so it would seem that spacetime isn't just some randomly configured object - but rather a mathematical structure. Max Tegmark has described this really elegantly.

This philosophy has gotten me interested in physics again, however, if I do get into physics it would have to be timeless physics just as when I when I do programming it has to be declarative programming. Mathematics will definitely continue to be my primary area of study because it is intrinsically declarative.

Counting number representations

We can define the counting numbers based upon successive calls to the inc function:

(defn expand-number*
  [n]

  (if (zero? n)
    0
    (cons inc (list (expand-number* (dec n))))))

(defmacro expand-number
  [n]

  (expand-number* n))

We can also define them in terms of the unary numeral system:

(defmacro tally-marks
  [n]

  (cons + (map (constantly 1) (range 0 n))))

Here is how these functions work:

(= (macroexpand-1 '(expand-number 5))
   `(inc (inc (inc (inc (inc 0))))))

(= (macroexpand-1 '(tally-marks 5))
   `(+ 1 1 1 1 1))