The Little Schemer Book Review

This book is an introduction to thinking about computation and consequently the scheme programming language. The only prerequisites needed for the book is arithmetic. It is written in a series of dialogues and has humor interspersed. Also it introduces the idea of recursion in lisp and this ends with the y combinator being fully introduced in scheme. The book introduces a subset of scheme with an atomic environment by creating the atom? function. The book ends with a full interpreter of the subset of scheme written in scheme.

I really enjoyed this book because it is very simple to understand. When I read this book I had little knowledge of programming and this book was a great introduction to scheme. I would recommend this book for a person who has no prior experience with programming or scheme in general.

R6RS preliminary report !

There is a preliminary report on R6RS.org in PDF format at R6RS PDF. It is a draft version and is currently incomplete but it reflects what the committee has decided so far. There is a public review process which allows you to suggest features or other changes available on the main page.

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.

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 .

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.

WARNING HEAVY UNICODE

LSEL

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
 (generate
  ((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

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
McCarthy91-Function.

(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)
    (cond
     ((= 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)
    (cond
     ((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))))

Current Surreal-numbers code

;;; -*- mode: scheme surreal-numbers -*-
;;;; Surreal Numbers Datatype

;;; This code is written by Joshua Herman and placed in the Public
;;; Domain.  All warranties are disclaimed.

;;; For more information about surreal numbers see
;;; http://en.wikipedia.org/wiki/Surreal_Numbers
;;; Note: some of the comments are in unicode
;;; Requires SRFI-9

;;;Some Helper functions

                                        ;(quote 0) is 0used for nullset

(define (nullset? x)
  (equal? x '(0)))

;;This tests if a given list has a specific element

(define (set? lat)
 (letrec
     ((S (cond
          ((null? lat) #t)
          ((member? (car lat) (cdr lat)) #f)
          (else (set? (cdr lat)))))
      (member? (cond
                ((null? lat) #f)
                (else (or (equal? (car lat) a)
                          (member? a (cdr lat)))))))))

                                        ;This takes a set and a function
                                        ;and a function which can
                                        ;compair two sets
(define (setcmp-f? test? lat1 lat2)
  (cond
   ((or (null? lat1)
        (null? lat2)) #t)
  ((or (not (null? (car lat1)))
      (not (null? (car lat1))))
        (test? (car lat1)
               (car lat2)))
    (else (set-cmp-f? test? (cdr lat1) (cdr lat2)))))
                                        ;This adds up all of the values
                                        ;in a given set (list of numbers)

(define (member>=? xl xr)
  (setcmp-f? >= xl xr))
                                        ;This compairs if each member of XL is
                                        ;greater than or equal to XR
(define (union set1 set2)
  (cond
   ((null? set1) set2)
   ((member? (car set1)
             set2)
    (union (cdr set1)
           set2)
    (else (cons (car set1)
                (union (cdr set1)
                       set2))))))
                                        ;This creates the union of two sets
(define first$ car)

(define (build s1 s2)
  (cons s1
        (cons s2 '())))

(define second$ (lambda (str) ((second str))))

(define str-maker
  (lambda (next n)
    (build n (lambda ()
               (str-maker next (next n))))))

(define frontier
  (lambda (str n)
    (cond
     ((zero? n) '())
     (else (cons (first$ str)
                 (frontier (second$ str)
                           (- n 1)))))))
;;;Surreal Number Code Starts Here 

                                        ;Surreal numbers are defined as follows.
                                        ;Given a Surreal Number X = (xl, xr)
                                        ;where XL and XR are sets.
                                        ;∀ xl ∈ L ∀ xr ∈ R : ¬(xl ≤ xr).
                                        ;For exlample {(0) |(0)} == 0 == { | } |#
                                       
(define-record-type :surreal-number
 (make-surreal l r)
  surreal-number?
  (l left-side)
  (r right-side))
                                        ;This defines the surreal number datatype
                                        ;as a record

(define (well-formed? surreal-number)
  (and
   (set? (l surreal-number))
   (set? (x surreal-number))
   (not (member=>? (l surreal-number)
                   (r surreal-number)))))
                                        ;Check for a well formed surreal number
                                      
(define (create-surreal-number l r)
  (if (well-formed? l r)
      (make-surreal l r)
      (display "Error in XL/XR Check Input")))
                                        ;This uses the well-formed as a
                                        ;sanity check and creates a surreal

(define zero (create-surreal-number '(0) '(0))) 
                                        ;Example (Zero)

(define (pretty-print-surreal surreal-number)
 (display "(") (display (l surreal-number))
 (display ",") (display (r surreal-number)) (display ")"))
(define (display x)
  (if (surreal? x)
      (pretty-print-surreal x)
      (display x)))

                                        ;Uses Knuth's method for displaying
                                        ;surreals
(define (surreal-dydactic-function a b)
  (/ a (expt 2 b)))
(define (Surreal+1 surreal-number)
  (make-surreal
   (surreal-dydactic-function (xl surreal-number)
                              (xr surreal-number))))

(define (+/-one? side)
  (and (nullset? (car side)) (nullset? (cadr side))))

(define (value surreal-number)
  (+ (addvec (xl surreal-number))
     (addvec (xr surreal-number))))
(define (add-surreal surreal-number1 surreal-number2)
  (make-surreal
   (union (xl surreal-number1)
          (xl surreal-number2))
   (union (xr surreal-number1)
          (xr surreal-number 2))))
;;;Finite enumeration is done by streams
(define surreal-number-set+
  (str-maker surreal+1 zero))
(define surreal-number-set-
  (str-maker surreal-1 zero))
(define surreal+1)
;;Stream Definitions

;;Example
;;(define int (str-maker add1 0))
;; (define (add1 n)
;;   (+ 1 n))
;; (define odd
;;   (str-maker (lambda (n)
;;                (+ 2 n)) -1))
;; (define Q
;;   (lambda (str n)
;;     (cond
;;      ((zero? (remainder (first$ str)  n))
;;      (Q (second$ str) n))
;;      (else (build
;;             (first$ str)
;;             (lambda ()
;;               (Q (second$ str) n)))))))
;; (define P
;;   (lambda (str)
;;     (build (first$ str)
;;            (lambda ()
;;              P (Q str (first$ str))))))

Reasoned Schemer Short overview

Fans of prolog and other logical programming languages will not be disappointed in this new book that just came. It deals with the extension of functional programming to include logic programming. It is presented in a dialogue manner that is easy to understand for beginners and advanced people. Reading the little or seasoned schemer books helps but is not required. All you need to know is functions can be passed as arguments to other functions and the syntax for let . The book is intended for beginners in logic programming and no prerequisites are needed. I highly recommend this book.

Siscweb

Lately I have been working on a website using siscweb. It is a really great framework that allows you to use scheme in a continuation web based framework. The resulting website can also be deployed in a J2EE application server which is different from other frameworks based in scheme which require their own server. For more information see SISCweb website

Zobrist Hashing

Okay, this is a new post in awhile. Currently I have read through the little schemer and done most of the exercises. I have also moved on and am currently reading the the seasoned schemer. I will put the Beyond Lisp idea on hold until I can get to the the reasoned schemer . Lately I have been programming parts of a Go AI. I am planning for this AI eventually to use (warning PDF) Termite so that it is able to distribute the AI across many systems as possibly a multi agent system.

Currently the part that I have programmed is a zobrist hashing program at zobirist hashing program As you can see it stores the Goban as a list. And requires SRFI's 27 and 60 .