Prompted by a post on Catalan numbers in Qilang,
I got into looking at ordinal numbers as defined by
John von Neumann - see http://en.wikipedia.org/wiki/Ordinal_numbers
0 = {}
1 = {0} = {{}}
2 = {0,1} = {{}, {{}}}
3 = {0,1,2} = {{}, {{}}, {{}, {{}}}}
The Qi definition is
(define ord
{number --> ordinal}
0 -> []
N -> (let O (ord (- N 1)) (append O [O])))
which uses [] for {} and maps any natural number to its
ordinal representation.
(1-) (ord 0)
[]
(2-) (ord 1)
[[]]
(3-) (ord 2)
[[] [[]]]
(4-) (ord 3)
[[] [[]] [[] [[]]]]
The datatype definition of ordinal needed is
(datatype ordinal
_________
[ ] : ordinal;
O : ordinal;
______________________
(append O [O]) : ordinal;)
This makes ord type secure.
Now my friend Willi is a C++ programmer and he wrote the program
in C++. Here it is.
// cardtst.cpp - Von Neumann Numbers
// W.O. Riha - 09/05/06
// edited - 10/05/06 00:41
#include "leda.h"
string card1(int n) // auxiliary function to avoid unnecessary
recomputation
{
if (n<=1) return "O";
string s = card1(n-1);
return s + ", {" + s + "}";
}
string card(int n)
{
if (n==0) return "O";
return "{"+ card1(n) + "}";
}
int main()
{
cout << "\nVon Neumann Numbers ...\n\n";
for (;;) {
int n = read_int("\nEnter n: ");
cout << card(n)<< endl;
}
}
We found that the Qi program was much faster at computing
solutions than the C++ program. Hence Willi came back with
a counter challenge.
"I have therefore written a function in C++ which will print
the result for any n, without actually computing it. ....
For n = 3 it should produce something like {O {O} {O {O}}}
.... In C++ it is only three lines."
Well, the old dog! I wonder what his solution is?
Some challenges
1. If you're a C++ programmer can you rewrite Willi's original
program to compute faster than the original Qi program?
Ignore the time taken to print the result. Here is result
2.6Ghz & 500Mb main memory.
(define test
N -> (time (do (ord N) ok!)))
(53-) (test 1000)
Real time: 0.1702448 sec.
Run time: 0.1702448 sec.
Space: 4004000 Bytes
GC: 6, GC time: 0.150216 sec.ok!
2. Can you reproduce or better the 3 line solution in C++ or Lisp?
Mark
We think there's some confusion about this challenge.
So we'll try to make it clear.
There are two parts to it and a preamble.
Preamble
========
Von Neumann's definition of the ordinal numbers
follows the pattern
0 = {}
1 = {0} = {{}}
2 = {0,1} = {{}, {{}}}
3 = {0,1,2} = {{}, {{}}, {{}, {{}}}}
etc.
In Qi we can define a function that maps natural
numbers to ordinals treated as lists ({} is []). Here is
the definition.
(define ord
{number --> ordinal}
0 -> []
N -> (let O (ord (- N 1)) (append O [O])))
Here is the definition of the type ordinal.
(datatype ordinal
_________
[ ] : ordinal;
O : ordinal;
______________________
(append O [O]) : ordinal;)
So here is the first challenge.
CHALLENGE 1
Define ordinal numbers as a type using whatever
analogue to the set notation you find convenient.
Obviously if your language is not statically typed then you
can skip this challenge.
CHALLENGE 2
The second challenge arises from the memory
consumption of the ord function which builds
a gigantic list in memory. Can you write a program
that *prints* the solution without this defect?
Note that building strings is not a solution since the
growth is still exponential. The program will use
print functions to display the structure without actually
building it. Hence, at a guess, the correct solution
should use constant or at worst linear memory.
Note we are not competent to adjudicate every answer
in every possible language, so your efforts may
have to be refereed by others. If you succeed by
your own lights - well done.
Mark & Willi
······@ntlworld.com writes:
> CHALLENGE 2
>
> The second challenge arises from the memory
> consumption of the ord function which builds
> a gigantic list in memory. Can you write a program
> that *prints* the solution without this defect?
> Note that building strings is not a solution since the
> growth is still exponential. The program will use
> print functions to display the structure without actually
> building it. Hence, at a guess, the correct solution
> should use constant or at worst linear memory.
This probably does fulfill the memory constraints. However, it does have a
certain aesthetic quality:
(defun ord (stream n &optional colonp atp)
(format stream "~[O~:;{~{~/ord/~^ ~}}~]" n (loop for x below n collect x)))
--
Lasse Rasinen
········@iki.fi
Lasse Rasinen <········@iki.fi> writes:
> This probably does fulfill the memory constraints. However, it does have a
> certain aesthetic quality:
>
> (defun ord (stream n &optional colonp atp)
> (format stream "~[O~:;{~{~/ord/~^ ~}}~]" n (loop for x below n collect x)))
*ahem*
What I meant was of course "does not fulfill the memory constraints" ;-)
--
Lasse Rasinen
········@iki.fi
Here is Willi's solution transcribed out of C++.
He uses a for loop which I have simulated recursively.
For this reason his C++ version is actually shorter.
For the same reason a Lisp version should be shorter
here too.
(define willi
0 -> (output "O")
1 -> (output "{O}")
N -> (do (output " {O ") (loop 1 N willi) (output "}") ))
(define loop
N N _ -> ok
M N F -> (do (F M) (loop (+ M 1) N F)))
Mark
the qi people wrote:
>CHALLENGE 2
>
>The second challenge arises from the memory
>consumption of the ord function which builds
>a gigantic list in memory. Can you write a program
>that *prints* the solution without this defect?
I'm not 100% sure what an ordinal number is because the wikipedia entry
was far longer than I'm willing to endure for a usenet post, but this
mirrors the patterns of your example
(defun print-as-ordinal (number &optional (stream t) depth)
(declare (ignore depth))
(macrolet ((with-parens (n &body body)
"wraps ,@body in n sets of parens written to stream"
(let ((g (gensym)))
`(let ((,g ,n))
(dotimes (,g ,g)
(write-char #\( stream))
,@body
(dotimes (,g ,g)
(write-char #\) stream))))))
(with-parens 1
(dotimes (n number)
(with-parens 1
(do ((n1 1 (incf n1)))
((> n1 n))
(with-parens n1)))))))
;but first they wrote:
>CHALLENGE 1
>
>Define ordinal numbers as a type using whatever
>analogue to the set notation you find convenient.
>Obviously if your language is not statically typed then you
>can skip this challenge.
(defstruct (ordinal-number (:constructor ord (number))
(:conc-name ordinal-))
(number 0 :type number))
(defmethod print-object ((object ordinal-number) stream)
(print-as-ordinal (ordinal-number object) stream))
;;;;;;;;;;;;;;;;;;
CL-USER> (ord 3)
(()(())(()(())))
nick
······@ntlworld.com writes:
> CHALLENGE 1
>
> Define ordinal numbers as a type using whatever
> analogue to the set notation you find convenient.
> Obviously if your language is not statically typed then you
> can skip this challenge.
There's something disgusting with the whole idea of defining a type
here... the ida of ordinal-numbers-as-sets is part of the extreme
reductionism of axiomatic set theory: The beauty and technical
simplicity of defining "everything" from the empty set, set formation
and a few basic additional axioms.
> CHALLENGE 2
>
> The second challenge arises from the memory
> consumption of the ord function which builds
> a gigantic list in memory. Can you write a program
> that *prints* the solution without this defect?
> Note that building strings is not a solution since the
> growth is still exponential. The program will use
> print functions to display the structure without actually
> building it. Hence, at a guess, the correct solution
> should use constant or at worst linear memory.
But my version uses only linear memory, although it constructs the
whole list in memory! This is because the loop reuses all sub-
structures.
A recursive definition would not reuse conses:
(defun ord-rec (n)
(when (> n 0)
(loop for i below n
collect (ord-rec i))))
However, by memoizing this function you also get a linear version
- and you can reuse results between function calls ;-)
--
(espen)
Mark Tarver wrote:
> Prompted by a post on Catalan numbers in Qilang,
> I got into looking at ordinal numbers as defined by
> John von Neumann - see http://en.wikipedia.org/wiki/Ordinal_numbers
>
> 0 = {}
> 1 = {0} = {{}}
> 2 = {0,1} = {{}, {{}}}
> 3 = {0,1,2} = {{}, {{}}, {{}, {{}}}}
>
> The Qi definition is
>
> (define ord
> {number --> ordinal}
> 0 -> []
> N -> (let O (ord (- N 1)) (append O [O])))
>
> which uses [] for {} and maps any natural number to its
> ordinal representation.
>
> (1-) (ord 0)
> []
>
> (2-) (ord 1)
> [[]]
>
> (3-) (ord 2)
> [[] [[]]]
>
> (4-) (ord 3)
> [[] [[]] [[] [[]]]]
>
> The datatype definition of ordinal needed is
>
> (datatype ordinal
> _________
> [ ] : ordinal;
>
> O : ordinal;
> ______________________
> (append O [O]) : ordinal;)
>
> This makes ord type secure.
>
> Now my friend Willi is a C++ programmer and he wrote the program
> in C++. Here it is.
>
> // cardtst.cpp - Von Neumann Numbers
> // W.O. Riha - 09/05/06
> // edited - 10/05/06 00:41
>
> #include "leda.h"
>
> string card1(int n) // auxiliary function to avoid unnecessary
> recomputation
> {
> if (n<=1) return "O";
> string s = card1(n-1);
> return s + ", {" + s + "}";
> }
>
> string card(int n)
> {
> if (n==0) return "O";
> return "{"+ card1(n) + "}";
> }
>
> int main()
> {
> cout << "\nVon Neumann Numbers ...\n\n";
> for (;;) {
> int n = read_int("\nEnter n: ");
> cout << card(n)<< endl;
> }
> }
>
> We found that the Qi program was much faster at computing
> solutions than the C++ program. Hence Willi came back with
> a counter challenge.
>
> "I have therefore written a function in C++ which will print
> the result for any n, without actually computing it. ....
> For n = 3 it should produce something like {O {O} {O {O}}}
> .... In C++ it is only three lines."
>
> Well, the old dog! I wonder what his solution is?
>
> Some challenges
>
> 1. If you're a C++ programmer can you rewrite Willi's original
> program to compute faster than the original Qi program?
> Ignore the time taken to print the result. Here is result
> 2.6Ghz & 500Mb main memory.
>
> (define test
> N -> (time (do (ord N) ok!)))
>
> (53-) (test 1000)
>
> Real time: 0.1702448 sec.
> Run time: 0.1702448 sec.
> Space: 4004000 Bytes
> GC: 6, GC time: 0.150216 sec.ok!
>
> 2. Can you reproduce or better the 3 line solution in C++ or Lisp?
Wasn't so hard:
(defun ord (n &optional prev)
(if (= n 0)
prev
(ord (1- n) (append prev (list prev)))))
CL-USER> (ord 3 '(0))
(0 (0) (0 (0)) (0 (0) (0 (0))))
CL-USER> (time (progn (setf *result* (ord 1000)) (values)))
Evaluation took:
0.006 seconds of real time
0.005 seconds of user run time
0.0 seconds of system run time
0 page faults and
4,022,424 bytes consed.
; No value
CL-USER> (length *result*)
1000
I can't really think of a 3 line in-place version, since I can't just
use nconc instead of append. Test was run using sbcl 0.9.12 under linux
with a p4 3 Ghz and 1 gig or ram.
-Yves
>
> Mark
>
The test should be (ord n), without the 0's. In Allegro 7.0:
CL-USER(2): (ord 3)
(NIL (NIL) (NIL (NIL)))
It looks more like von Neumann's version if we replace NIL with its
equivalent, ():
(() (()) (() (())))
···············@yahoo.com writes:
> It looks more like von Neumann's version if we replace NIL with its
> equivalent, ():
>
> (() (()) (() (())))
If you want to mathematically pretty-print it, you should use the
empty set sympbol, which I will fake with the norwegian capital
letter � here:
0 = �
1 = {�}
2 = {{�}, �}
and so on.
e.g. using
(defun pretty-print-set (x &optional (stream t))
(if (not x)
(format stream "�")
(format stream "{~{~a~^, ~}}"
(mapcar (lambda(x)(pretty-print-set x nil)) x))))
(next exercise: A smarter version of pretty-print-set :-))
--
(espen)
···············@yahoo.com wrote:
> The test should be (ord n), without the 0's. In Allegro 7.0:
>
> CL-USER(2): (ord 3)
> (NIL (NIL) (NIL (NIL)))
>
> It looks more like von Neumann's version if we replace NIL with its
> equivalent, ():
>
> (() (()) (() (())))
>
I omitted the second argument in the test, the (list 0) was just added
for clarity. Espen fixed that in a nicer way though :P
Espen's version is faster, O(n) rather than O(n^2), because there is no
append. The interesting thing is that the result is backwards from
Yves' version.
CL-USER(4): (ord 3) ;; Espen's
(((NIL) NIL) (NIL) NIL)
or equivalently
(((()) ()) (()) ())
You might wonder whether doing it backwards is legal, but it is,
because these are *sets*. The order of the elements doesn't matter.
···············@yahoo.com wrote:
> Espen's version is faster, O(n) rather than O(n^2), because there is no
> append. The interesting thing is that the result is backwards from
> Yves' version.
>
> CL-USER(4): (ord 3) ;; Espen's
> (((NIL) NIL) (NIL) NIL)
>
> or equivalently
>
> (((()) ()) (()) ())
>
> You might wonder whether doing it backwards is legal, but it is,
> because these are *sets*. The order of the elements doesn't matter.
>
Argh and I avoided doing it backwards.
(a little time-waster ascii diagram of an ordinal number)
___ ___ ___ ___ ___ ___
3 | | |-> | | |-> | | \ |
| | |
| | _v_ ___ ___ ___
2 | | | | |-> | | \ |
| | | |
| | | _v_ ___
1 | \----------|-------> | | \ |
| | |
| | _v_ ___
0 \-----------------------\-------> | \ | \ |