Tuesday, August 29, 2006

Multisets and structure

I am now trying to revise the structure of the wiki page and make it a much more formal document. Flow structure has been improved and I have added multisets / bags as a feature of the language. From the document itself.

These are lsets with the added feature of multiplicity. This means that an element in an multiset can occur more than once but when you bons (bag cons) the value to the set it increases the occurance of that element by one.

This was spurred on by a discussion from #scheme on irc.freenode.net with bpt. I give thanks to all of the people who have read the document and have offered constructive criticism.

Monday, August 28, 2006

Starting an implementation / new features

If you check the blog page I have added many new features and started to implement some of the features. So far I have implemented part of the set theory features. rel? and fun? predicates allow for the definition of finite functions. At this time the operations assume a finite set of values. Also I have started to specify the language in EBNF. For those who haven't been reading the blog the actual informal specification of the language is at Beyond lisp .

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 http://community.schemewiki.org/?beyond-lisp

Monday, August 07, 2006

Collatz Collector Program and M91 Program

I haven't posted in awhile so here is some from my code archive that I have written.
CollatzProblem and the

(define (collatz n)
(and (display n))
(cond ((and (odd? n) (> n 1))
(collatz (+ 1 (* 3 n))))
((even? n) (collatz (/ n 2)))))

(define (optimized-collatz n)
(begin (and (display n))
(let (n (modulo 4 x))
(define (f x)
((= n 0) => (/ n 4))
((= n 1) => (* (/ 3 4) (+ 1 (g (- n 1)))))
((= n 2) => (/ n 2))
((= n 3) => (* (/ 1 2) (+ 1 (* 3 n)))))))
(define (g x)
((not (= n 0)) => n)
((= n 1) => (/ 1 4 (g (- n 1))))))))

(define (collatz-range n)
(if (= n 0)
(display "Finished")
(and (display #\newline)
(collatz n)
(collatz-range (- n 1)))))
(define (m91 n)
(begin (and (display n))
(cond ((and (<= n 100) (> n 0))
(m91 (m91 (+ n 11))))
((and (> n 0) (- n 10))))))
(define (mc91 n)
(display n)
(cond ((< n 1) (display "Function only defined for positive values of n"))
((<= n 100) (mc91 (mc91 (+ n 11))))
(else (- n 10))))