Monday, August 21, 2006

Beyond Lisp

I have started to rethink lisp from the bottom up for the past year. Lists are still important part of the language John McCarthy believes in attempting to rethink lisp's core into a new thing. I have been thinking about this idea for awhile and have recently had a deeper insight into not just processing lists. Instead we replace lists with a important abstraction in mathematics.



Instead of the LiSt Processing language we replace lists with a hybrid datatype called an lset. This is a set that is both a list and a set. It has the functionality of a set but the abilitys of the list. Here is an example.

Working with LSET's

(define X
((in x R) (> x 0))))

(set? X) ;-> #t
(sar X) ;-> (1)
(sdr X) ;-> (2 3 4 ...)

Mu expressions (First Order Formal Logic Operators)

And , or, not are extended over first order logic but they can only be relevant to first order logic in mu expressions. These new operators can occur inside of a mu expression. A mu expression is similar to a lambda expression except instead of describing a function you describe a first order logic expression. For example.
Axiom of Extensionality

(mu (u X Y) (-> (== (∈ u X) (∈ u Y)) (= X Y)))

Also we have a let-mu which allows you to compose multiple mu statements into a single statement.
(let-mu (xl xr)
(∀ (∈ xl L))
(∀ (∈ xr R))
(¬ (≤ xl xr)))

would describe the surreal numbers in unicode.
Anyways that is what I have so far. Comments are appreciated!

A much more involved version of this document is currently being drafted on community scheme wiki. It is available at

No comments: