Monday, May 30, 2011

The flare programming language

One of the earliest contributions of our friends at the Singularity Institute for Artificial Intelligence (SIAI) was the flare programming language. When I first saw this language, I was quite impressed. It has strong support for annotations and metadata and some other relatively impressive features.

However as an educated Lisper I now know better. Flare uses XML rather then sexps and its purported advantages are derived from this. This is explained in detail on the site for the language:

LISP, of course, is the traditional king of self-modifying languages, because LISP uses the same representation for program code and program data. Flare also uses the same representation for code and data, except that the common representation is extensible tree structures (XML) rather than lists. The difference is a major one; in a list structure, an object's role is determined by where it is. In Flare, an object's role is determined by its name and its metadata. Extensible tree structures are thus less breakable; in LISP lists, meaning is often conveyed by position, and inserting new elements can change the position of other elements in a list. Adding another Flare subelement, by contrast, does not at all change the behavior or appearance of the other elements.

In Lisp you cannot insert elements into a lists order, without breaking that lists order. However you can instead insert a special kind of node that does not effect the list's order. Lets call this sort of node an attribute and lets express it as (:name value).

(html
  (head
    (title "Main Page"))
  (body
    (a (:href "home.html") "Welcome")))

And now, with this new construct you have XML in Lisp. Actually what you have is better then XML, because attributes in XML are almost entirely unstructured and they instantiate the attribute/element false dichotomy.

The other alleged advantage of flare is its use of metadata, however, XML leads to a distorted view and improper usage of metadata.

If you want to develop a programming language don't base it upon XML when Lisp is such a better alternative. Even the developers of flare knew that XML is painful, which is why they created flare speak to be used instead. However, the flarespeak language offers nothing over existing languages such as python, it is just another camel-case using, infix ridden, heteroiconic programming language.

Ultimately the flare programming language was abandoned and the SIAI went on to address more important problems like AI morality. For further reading, Erik Naggum provided some interesting insights on XML and flare:

http://genius.cat-v.org/erik-naggum/sgml-attributes-metadata
http://www.xach.com/naggum/articles/3206985430398054@naggum.net.html

Thursday, May 26, 2011

Solving 4Clojure Problems

I have been solving problems on the 4clojure website. In order to solve the problems on this site I used clojure.walk/macroexpand-all and I defined all my functions as macros in order to get past the def problem.

(require 'clojure.walk)

(clojure.walk/macroexpand-all (quote (func)))

This seems to work quite well. Another option is to use let to define everything.

Wednesday, May 25, 2011

Emacs user interface

In my opinion Emacs represents the state of the art in user interface design. When Emacs was invented in the 70s, most computers used text based user interfaces. Later graphical WIMP interfaces were developed as a "successor" to textual user interfaces, however, I don't believe they are a true successor as they are deeply flawed and in many cases they actually reduce my productivity. Zooming user interfaces (ZUIs) are the true successor.

The main problem with traditional GUIs is that they are full of pop-ups, such as alerts, prompts, confirmation dialogs, menus, and tooltips. These things cause more problems then they solve. Dialogs break the users focus, and menus are hard to navigate and they have to be fit into the screen when you go near the corners.

Pop-ups are also a security problem, as they essentially mean that a program is drawing outside of the space secured for it. This is why most modern web browsers come with pop-up blockers. To move into the web age we should completely abolish pop-ups.

To disable pop-ups in emacs add this to your .emacs file:

(setq use-dialog-box nil)
(menu-bar-mode -1)

ZUIs solve this problem by placing content in place rather then hiding it in a pop-up, and they make more efficiently use of the users spatial memory, which is why I think they are the true successor to textual user interfaces, unfortunately there is no practical ZUI available right now.

The problem we have to address now is creating a synergy between textual user interfaces like emacs and the ZUI paradigm, then we will have the humane interface that Jef Raskins envisioned decades ago.

Wednesday, May 18, 2011

Embedding XML trees in Lisp

Like Lisp expressions XML documents are essentially just trees:
However, since traditional XML notation is verbose and inefficient it makes sense to embed XML in Lisp:
[:html
 [:head
  [:title "Main Page"]]
 [:body
  [:p "Welcome"]]]

This new notation also us to integrate Lisp with many XML based data formats such as HTML and SVG.

Sunday, May 15, 2011

Converting finite functions into discrete maps

Maps are the extensional analogue of functions. For example, here is the nand function expressed as a map:
(defn unapplify
  [func]

  (fn [& args]
    (apply func args)))

(def nand
  (unapplify
   '{(false false) true
     (false true)  true
     (true  false) true
     (true  true)  false}))

Now if a function is finite and we have a complete description of its domain, then we can turn it into a map:
(defn function-to-map
  [func domain]

  (zipmap
   domain
   (map (partial apply func) domain)))

Now we have the machinery necessary to prove De Morgan's Laws:

(def boolean-pairs
 '((false false)
   (false true )
   (true  false)
   (true  true )))

(= (function-to-map
     (fn [a b] 
       (not (and a b)))
     boolean-pairs)
  
   (function-to-map
     (fn [a b]
       (or (not a) (not b)))
     boolean-pairs))

(= (function-to-map
     (fn [a b] 
       (not (or a b)))
     boolean-pairs)
  
   (function-to-map
     (fn [a b]
       (and (not a) (not b)))
     boolean-pairs))

This method works for all finite functions. On the other hand, infinite functions require more sophisticated mathematically machinery.

Friday, May 13, 2011

Factorials and triangular numbers

These two functions are:

$$T_n = \sum_{i=1}^n {i}$$
$$n! = \prod_{i=1}^n {i}$$

There are also raising and falling versions of the factorial:

$$x^{\overline n} = \prod_{i=0}^n {x+i}$$
$$x^{\underline n} = \prod_{i=0}^n {x-i}$$

Here is the corresponding code:

(def triangular-number 
  (let [sum (partial apply +)]
    (comp sum range inc)))

(def factorial
  (let [product (partial apply *)
        upto (comp (partial map inc) range)]
    (comp product upto)))

(defn rising-factorial
  [x n]
  (apply * (map (partial + x) (range 0 n))))

(defn falling-factorial 
  [x n]
  (apply * (map (partial - x) (range 0 n))))

(defn choose
  [n k]
  (/ (falling-factorial n k)
     (factorial k)))

(defn multichoose 
  [n k]
  (/ (rising-factorial n k)
     (factorial k)))

The multichoose function is incredibly important because all polytopic numbers, including triangular-numbers and tetrahedral numbers can be expressed with it.

(def triangular-number
  #(multichoose % 2))

(def tetrahedral-number
  #(multichoose % 3))

(def pentatope-number
  #(multichoose % 4))

This is the relationship between factorials and triangular-numbers. Triangular-numbers can be expressed in terms of factorials probably because the higher hyper operator, multiplication, encodes more information then addition.

Sunday, May 8, 2011

Properties of zero

In mathematics zero is considered to be unsigned and therefore neither positive or negative. However, some floating point representations have signed zero.

(= (pos? 0) false)
(= (neg? 0) false)

Zero is also the first counting number, a concept introduced in Lisp. Earlier programming languages used one as the first counting number.

(= (nth ["a" "b" "c"] 0) "a")

Perhaps the most interesting property of zero is zero to the power of zero. My hyper-operator implementation in my last blog post leads me to the empty product:

(= (hyper-operation 3 0 0)
   (apply (partial hyper-operation 2) (repeat 0 0))
   (hyper-operation 2)
   (*))

The JVM seems to agree with me on this:

(= (Math/pow 0 0) 1)

However, some people considered zero to the power of zero to be an indefinite form, however, I think it is better to define it as zero rather then raising a disruptive error. It also just so happens that the value of one is necessary for various formulas to work, most notably, the series expansion for Math/exp.

Saturday, May 7, 2011

Hyper-operations

Hyper-operations are an infinite sequence of arithmetic operations, which may be implemented on lists of unsigned integers with the following algorithm:

(defmulti hyper-operation
  (fn [n & nums] (zero? n)))

(defmethod hyper-operation true
  [n & nums] (+ (first nums) (count nums)))

(defmethod hyper-operation false
  ([n] (if (<= n 1) 0 1))
  ([n a] a)
  ([n a b]
    (if (and (= n 1) (zero? b)) 
      a
      (apply hyper-operation (dec n) (repeat b a))))
  ([n a b & args]
    (reduce (partial hyper-operation n) (hyper-operation n a b) args)))
The first five hyper-operations have names of their own, which can be specified by calling the partial function:
(def zeration (partial hyper-operation 0))
(def addition (partial hyper-operation 1))
(def multiplication (partial hyper-operation 2))
(def exponentation (partial hyper-operation 3))
(def tetration (partial hyper-operation 4))

Friday, May 6, 2011

Open Computer Science Problems

I found this new problems site. The first problem is simple:

(apply + 
  (map
    (fn [i]
      (Math/pow 3 (dec i)))
    (range 1 16)))

The second problem isn't so simple. I implemented the procedure the site described, however, it doesn't work because the range is way too large:

(let [n (fn [i]
          (count (filter #(= \1 %) (Integer/toString i 2))))]
  (map n (range 1 (inc (Math/pow 2 50)))))

Instead I solved this problem using mathematical simplification which lead me to:

(inc (* 50 (Math/pow 2 49)))

Then I got to the third problem. Apparently they want me parse some expression! I am a Lisp programmer for a reason: I don't like to parse. So instead I made a macro based upon this problem:

(defmacro ternary-expression 
  [if-true expr if-false]
  `(if ~expr
     ~if-true
     ~if-false))