if { 0 } { Warning: this is very much WORK IN PROGRESS - the scripts do not work yet ;) for instance
Arjen Markus (17 may 2004) Miguel Sofer introduced me to a booklet by the famous Donald Knuth, Surreal Numbers - a mathematical novelette. Though I have only read a few chapters sofar, it is rather intriguing: it describes how two ex-students discover a number system due to James Conway. This number system, called the surreal numbers, has two rules for constructing such a number:
Now this immediately brings up a problem: how to start? This is the clever bit: take the empty set as the left set and the right set of the first number to be defined and call it "0":
0 = < {} : {} >
where {} is the empty set (a very convenient notation for a Tcler ...).
From this you can define two other numbers:
1 = < 0 : {} > -1 = < {} : 0 >
and you can derive all the classical properties of the ordinary numbers, such as:
x <= x if x <= y and y <= z, then x <= z
Complicated? Abstract? Yes, but the story as told by Knuth is very readable.
It also brought back a different approach to elementary arithmetic: you start with the empty set and build the natural numbers from that. (I agree: mathematics can be weird at times :). But have a look:
succ 0 = 1, succ 1 = 2, ...
Here is a little Tcl proc to do that: }
proc succ { x } { lappend x [list [lindex $x end]] }
if { 0 } { From this function we can define integer addition and a predecessor function: }
proc add { x y {res {}} } { if { $x != $res } { return [add $x [succ $y] [succ $x]] } else { return $y } } proc pred { x {res {}} } { if { $x == $res } { error "No predecessor for the empty list!" } if { $x != [succ $res] } { return [pred $x [succ $res]] } else { return $res } } # # Simple tests # set 0 {} puts "Successor to 0: [succ $0]" puts "Successor to 1: [succ [succ $0]]" set 1 [succ $0] set 2 [succ $1] set 3 [succ $2] puts "Add 2 and 3: [add $2 $3]" puts "Predecessor 3: [pred $3]"
if { 0 } { So far, so good. Tcl is ideal (IMHO) for this sort of things: computationally it will not be very efficient (with all these recursions), but the code can hardly get shorter and cleaner, can it? }
if { 0 } { Back to the story of the two ex-students. Can we turn the two rules into Tcl code? Sure enough:
So, here we go! }
set 0 [list {} {}] set 1 [list $0 {}] set -1 [list {} $0] proc CheckNumber {number} { # # Rudimentary check # foreach set $number { set noelems [lindex $set] if { $noelems > 2 } { error "Not a valid number" } if { $noelems == 2 } { CheckNumber $number } } return 1 ;# All okay } proc newNumber {leftset rightset} { # # Check the numbers in both sets # foreach l $leftset { CheckNumber $l } foreach r $rightset { CheckNumber $r } list $leftset $rightset } proc _LE {x y} { puts "_LE: $x -- $y" if { [lindex $x] == 1 } { if { [lindex $y] == 1 } { expr {$x <= $y } } else { set result 1 foreach r $y { if { ! [_LE $x $r] } { set result 0 break } } } } else { set result 1 foreach l $x { if { ! [_LE $l $y] } { set result 0 break } } } return $result } proc LE {x y} { set left [lindex $x] set right [lindex $y] if { [_LE $left $y] && ! [_LE $right $x] } { return 1 } else { return 0 } }
if { 0 } { With these procedures, we ought to be able to check simple arithmetical properties (this is mainly a sanity check for the moment): }
puts " 0 <= 0? [LE $0 $0]" puts " 0 <= 1? [LE $0 $1]" puts "-1 <= 1? [LE ${-1} $1]"
if { 0 } {
For a quick overview of what you can do with them: http://en.wikipedia.org/wiki/Surreal_number
Another source of information is http://mathworld.wolfram.com and look for surreal numbers
[ Category Mathematics ] }