ordinal number programming challenge
Mark Tarver
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 (see www.lambdassociates.org) 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. Can you reproduce or better the 3 line solution that Willi
says he has in your chosen language?
2. For curiousity, what would the definition of the type of
ordinal numbers look like in your chosen language?
RobertSzefler
> 1. Can you reproduce or better the 3 line solution that Willi
> says he has in your chosen language?
The one-liner in Python is:
def vonneumann(n): return map(lambda x: vonneumann(x), range(n))
which maps integers to lists with zero encoded as an empty list, eg.
0 -> []
1 -> [[]]
2 -> [[], [[]]]
3 -> [[], [[]], [[], [[]]]]
I am pretty sure (too busy to verify) that an equally simple and elegant
solution can be given in Ruby and Haskell - anyone?
> 2. For curiousity, what would the definition of the type of
> ordinal numbers look like in your chosen language?
Well, that question makes little or no sense in Python or any other
dynamically-typed language.
Mark Tarver
> def vonneumann(n): return map(lambda x: vonneumann(x), range(n))
I'm not a Python programmer, but thats impressive, if as the problem
requires - you print the solution without computing it as a list.
> 2. For curiousity, what would the definition of the type of
> ordinal numbers look like in your chosen language?
> Well, that question makes little or no sense in Python or any other
> dynamically-typed language.
Yes, well - of course if you don't have types you should skip this part
of the problem. Sorry, I thought that this was taken as read.
Mark
Mark Tarver
Here is the text of Willi's letter.
"Hi Mark,
the problem has really inspired me!
I have done some timings, and found that it takes 0.05 secs to assemble
n = 20. As time (and space) roughly double each time, it takes 1.50
secs for n = 25, the string is more than 67 MBs long. After that, I
run out of RAM, and the computation takes much too long , presumably
because of the swapping , in and out, of auxiliary RAM.
I have therefore had a new idea. Let us agree that the main objective
of this exercise is to display the result ....
For n = 3 it should produce something like
{O {O} {O {O}}} "
Apologies if this was not clear.
Mark
RobertSzefler
>>The one-liner in Python is:
>
>
>>def vonneumann(n): return map(lambda x: vonneumann(x), range(n))
>
> I'm not a Python programmer, but thats impressive, if as the problem
> requires - you print the solution without computing it as a list.
then you should add an additional line: print vonneumann(777)
I don't get the "without computing it as a list" part. Beg to specify
the problem more clearly?
>>2. For curiousity, what would the definition of the type of
>> ordinal numbers look like in your chosen language?
>
>
>>Well, that question makes little or no sense in Python or any other
>>dynamically-typed language.
>
>
> Yes, well - of course if you don't have types you should skip this part
> of the problem. Sorry, I thought that this was taken as read.
It's not that you don't have types - certainly you do in Python and
other dynamically typed languages (that's why the "typed" word is
there). They are just not enforced semantically in full (or enforced in
a way unfamiliar to most static language theories - duck typing) and
certainly not at the compile time.
Mark Tarver
cope with his memory problems
by *printing* the answer piecemeal rather
than computing it as a list structure
or a string. In that way the answer
is printed but the memory consumption
is probably minimal (maybe constant)
rather than exponential.
If you haven't got the capacity to
do static typing then ignore the second
part of the problem. My experience of
ducks is limited. If you can find input
from a friendly one then by all means
have a go.
Mark
RobertSzefler
> Mark Tarver wrote:
>
>>> The one-liner in Python is:
>>
>>
>>
>>> def vonneumann(n): return map(lambda x: vonneumann(x), range(n))
>>
>>
>> I'm not a Python programmer, but thats impressive, if as the problem
>> requires - you print the solution without computing it as a list.
>
>
> then you should add an additional line: print vonneumann(777)
>
> I don't get the "without computing it as a list" part. Beg to specify
> the problem more clearly?
OK, grok that. How about:
def v(n): return '['+ ','.join(['O']+map(lambda x:v(x), range(n))) +']'
print v(2)
--> [O,[O],[O,[O]]]
now v:int->str :)
Ketil Malde
Haskell?
Prelude> let vn 0 = "0"; vn x = concat [" {",concatMap vn [0..(x-1)],"}"]
Testing it:
Prelude> vn 3
" {0 {0} {0 {0}}}"
Prelude> vn 4
" {0 {0} {0 {0}} {0 {0} {0 {0}}}}"
Prelude> vn 5
" {0 {0} {0 {0}} {0 {0} {0 {0}}} {0 {0} {0 {0}} {0 {0} {0 {0}}}}}"
-k
--
If I haven't seen further, it is by standing in the footprints of giants
Tomasz Zielonka
> 1. Can you reproduce or better the 3 line solution that Willi
> says he has in your chosen language?
ord 0 cont = '0' : cont
ord n cont = '{' : foldr (\i c -> ord i (',' : ' ' : c)) (ord (n-1) ('}' : cont)) [0 .. n-2]
main = putStrLn (ord 25 "")
This Haskell program prints the result for n=25 (which has about 81MB)
using only 2MB of memory (the RTS allocates some memory in advance,
the actual maximum residency is only 26712 bytes).
Check for n <= 5:
0: 0
1: {0}
2: {0, {0}}
3: {0, {0}, {0, {0}}}
4: {0, {0}, {0, {0}}, {0, {0}, {0, {0}}}}
5: {0, {0}, {0, {0}}, {0, {0}, {0, {0}}}, {0, {0}, {0, {0}}, {0, {0}, {0, {0}}}}}
> 2. For curiousity, what would the definition of the type of
> ordinal numbers look like in your chosen language?
Well, I could use (Tree ()) from Data.Tree as a nested list type, which
is defined as
data Tree a = Node a [Tree a]
but I guess it would not give type safety. Could you elaborate on
that? How safe is your definition? Does it accept only valid ordinal
numbers?
I could also use some ordinary Natural type to represent those
ordinal numbers, but I guess it doesn't count?
Best regards
Tomasz
Tomasz Zielonka
> Mark Tarver wrote:
>> 1. Can you reproduce or better the 3 line solution that Willi
>> says he has in your chosen language?
>
> ord 0 cont = '0' : cont
> ord n cont = '{' : foldr (\i c -> ord i (',' : ' ' : c)) (ord (n-1) ('}' : cont)) [0 .. n-2]
> main = putStrLn (ord 25 "")
>
> This Haskell program prints the result for n=25 (which has about 81MB)
> using only 2MB of memory (the RTS allocates some memory in advance,
> the actual maximum residency is only 26712 bytes).
Actually, it builds the results, but in a lazy way, allowing the garbage
collector to reclaim the parts that have been already printed. So it is
a two-in-one solution, because (ord n "") is a normal Haskell list.
Best regards
Tomasz
Mark Tarver
> numbers?
I think so. But I'm open to counterexamples!
But if you follow my approach then you have to
enter ordinal numbers either via the ord function
or by using append.
You can also define ordinal addition etc. Here is
successor and predecessor for ordinals. Not fast.
(1+) (datatype ordinal
_________
[ ] : ordinal;
O : ordinal;
______________________
(append O [O]) : ordinal;)
ordinal : unit
(2+) (define ord
{number --> ordinal}
0 -> []
N -> (let O (ord (- N 1)) (append O [O])))
ord : (number --> ordinal)
(3+) (define succ
{ordinal --> ordinal}
O -> (append O [O]))
succ : (ordinal --> ordinal)
(4+) (define pred*
{ordinal --> ordinal --> ordinal --> ordinal}
O O PO -> PO
O O$ PO$ -> (pred* O (succ O$) O$))
pred* : (ordinal --> (ordinal --> (ordinal --> ordinal)))
(5+) (define pred
{ordinal --> ordinal}
O -> (pred* O (succ []) []))
pred : (ordinal --> ordinal)
Mark Tarver
The definitions of succ, pred* and pred use capital O not zero.
Mark
Ben Rudiak-Gould
> Damn. I see Google prints capital O the same as 0. Great.
Not for me. It uses whatever fonts you have configured in your browser.
-- Ben
w.r...@ntlworld.com
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
Tomasz Zielonka
> We think there's some confusion about this challenge.
> So we'll try to make it clear.
I think there is less confusion than you think ;-)
> 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?
Please note that both Haskell programs presented - my and Ketil's -
don't have that defect. The only difference between those programs is
that mine is faster and less readable ;-)
> Note that building strings is not a solution since the
> growth is still exponential.
Those programs build strings :-)
> 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.
Linear memory here.
Best regards
Tomasz
Mark Tarver
> don't have that defect.
Linear is very good. Have you checked timings for
your solution? The Qi one starts to degrade over
N = 1000.
(10-) (time (length (ord 1000)))
Real time: 0.0200288 sec.
Run time: 0.0200288 sec.
Space: 4004000 Bytes1000
(11-) (time (length (ord 2000)))
Real time: 0.3104464 sec.
Run time: 0.300432 sec.
Space: 16008000 Bytes
GC: 1, GC time: 0.200288 sec.2000
(12-) (time (length (ord 4000)))
Real time: 3.7554 sec.
Run time: 3.7253568 sec.
Space: 64016000 Bytes
GC: 4, GC time: 3.3347952 sec.4000
8000 kills it.
Willi has now shown me his C++ version, which is
quite neat, and which is also linear, but which builds
no structures - either lists or strings. I'll post it in 48 hours.
In Qi its 6 lines.
Mark
Mark
Tomasz Zielonka
>> Please note that both Haskell programs presented - my and Ketil's -
>> don't have that defect.
>
> Linear is very good. Have you checked timings for
> your solution? The Qi one starts to degrade over
> N = 1000.
>
> (10-) (time (length (ord 1000)))
>
> Real time: 0.0200288 sec.
> Run time: 0.0200288 sec.
> Space: 4004000 Bytes1000
You don't expect me to believe that you can print (write to stdout)
the whole result for 1000 in 0.02 seconds? Does your program solve
the same task that we were asked to solve?
Best regards
Tomasz
Matthias Blume
This question makes little or no sense in most statically typed
languages because types are usually not defined by explicitly carving
out a sub-domain of a given (universal) domain.
In ML (or any other language with algebraic datatypes) one could write
datatype ord = ZERO | SUCC of ord;
where ZERO corresponds to the empty list and SUCC(O) corresponds to
your (append O [O]).
> 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.
I doubt one can do better than linear in the value of the ordinal.
Here is a solution in ML. It's obvious and should be easy in any
language:
fun p n = let fun h 0 = () | h 1 = print "{}" | h n = (h(n-1);print",";p(n-1))
in print "{"; h n; print "}" end
If one does not insist on printing commas between elements one can further
simplify this to the following one-liner:
fun p n=let fun h 0=()|h n=(h(n-1);p(n-1))in print"{";h n;print"}"end
Matthias
Matthias Blume
Actually, I don't think that there would be a problem. I don't know
how Qi works, but with the right representation (which gives you the
best possible internal sharing), construction can be very fast (linear
in n). In ML, if I may take the liberty of representing sets "in
reverse order", I get the following code:
datatype ord = O of ord list
fun ord 0 = O []
| ord n = let val x as O l = ord (n-1) in O (x :: l) end
With this I can, e.g., say
ord 1000000
and it takes maybe a second to get the result. Measuring the length
of the top-level list is also fast, since it is just equal to n.
If you insist on using the "usual" order, you have to do
fun ord 0 = O []
| ord n = let val x as O l = ord (n-1) in O (l @ [x]) end
This version performs much worse, since the append operation (@)
loses useful sharing opportunities.
Of course, if you wanted to print the entire thing, you get
exponential behavior because the linearized size of the output is
actually exponential.
Matthias
Tomasz Zielonka
> Actually, I don't think that there would be a problem.
The (refined) task explicitly talks about using "print" statements,
so there is little room for ambiguity. If we agree to play tricks with
the representation and omit printing, I can represent ordinal numbers
using a plain Integer. The times would be much better.
> I don't know how Qi works, but with the right representation (which
> gives you the best possible internal sharing), construction can be
> very fast (linear in n).
Yes, I know that.
> Of course, if you wanted to print the entire thing, you get
> exponential behavior because the linearized size of the output is
> actually exponential.
The task said to print the result, so I did. Now I am asked to compare
efficiency to a program that doesn't print. That's unfair.
Best regards
Tomasz
Mark Tarver
> the whole result for 1000 in 0.02 seconds?
No, I cannot print the result in 0.02 seconds, but I can compute it.
Willi was also in doubt about that, so we printed some results and
ran some tests. The program works according to all tests I can
run.
Willi's string based C++ version cannot compute much over N = 20.
Does your Haskell version have the same problem? If so can you
rewrite it in the style of Matthias?
Here is one test I ran on the program that measures the size of
the output in keystrokes. The program is:
(define ord
0 -> []
N -> (let O (ord (- N 1)) (append O [O])))
(define c
[] -> 2
[X | Y] -> (+ 2 (total (map c [X | Y]))))
(define total
[] -> 0
[X | Y] -> (+ X (total Y)))
Here is a script
(13-) (c (ord 0))
2
(14-) (c (ord 1))
4
(15-) (c (ord 2))
8
(16-) (c (ord 3))
16
Mark
Tomasz Zielonka
>> You don't expect me to believe that you can print (write to stdout)
>> the whole result for 1000 in 0.02 seconds?
>
> No, I cannot print the result in 0.02 seconds, but I can compute it.
There is nothing extrordinary about it (unless there is something more
to it, that I am missing now). Perhaps you could define what does it
mean to compute *it*? To have some intermediate representation that can
be directly printed as the final result or any intermediate
representation that can be turned to an ordinal - if the latter, the
an Integer will do.
For the former, here are two Haskell programs that build something
that quite directly represent the string representation of ordinals.
import Data.Sequence as Seq
ord 0 acc = singleton '{' >< acc >< singleton '}'
ord n acc = ord (n-1) (acc >< comma >< singleton '{' >< acc >< singleton '}')
where
comma = if Seq.null acc then Seq.empty else Seq.fromList ", "
Computing (Seq.length (ord 29)) -> 1610612734 is instanteous.
Unfortunately, the Data.Sequence library keeps sequence length
as a machine integer, so it overlaps for bigger n. It shouldn't be to
hard to fix that, but may result in worse performance for usual
uses of Sequence.
The other program defines an infinite list of rose trees with Char
nodes that flatten to ordinal number representations.
ords =
Node "{}" [] :
[ Node "" $! ([Node "{" []] ++ intersperse (Node ", " []) xs ++ [Node "}" []])
| xs <- inits' ords ]
inits' l = [ take i l | i <- [1..] ]
Again, defining what you mean be *computing the result* in this case
would be helpful.
> Willi's string based C++ version cannot compute much over N = 20.
This is for my first Haskell version, which builds the whole string
without sharing:
N = 25: 12 seconds, 83886079 bytes of output, 2 MB of memory used
N = 30: 610.28 seconds, 2684354559 bytes of output, 2 MB of memory used
> Does your Haskell version have the same problem?
No, I already said that.
> If so can you rewrite it in the style of Matthias?
I don't have to. Haskell string based solution is better than C++ string
based solution.
Best regards
Tomasz
Matthias Blume
Sorry, yes, you are right. Obviously I was not disputing that
printing will take exponential time. (I even said so myself.) I was
merely commenting on whether or not the timing results that were shown
are believable. They are, although they do not measure a program that
prints the external representation.
Matthias
Matthias Blume
>> You don't expect me to believe that you can print (write to stdout)
>> the whole result for 1000 in 0.02 seconds?
>
> No, I cannot print the result in 0.02 seconds, but I can compute it.
No, you cannot, if you take as "the result" the string to be printed.
What you did was build an internal representation of the output, and
that can be built fast.
Mark Tarver
post the solution here I got from Willi.
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.
(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
Albert Lai
> Perhaps you could define what does it mean to compute *it*?
I see the problem as that we are presently over-defining things. A
programmer of eager languages will tend to define computation with an
eager bias, rendering the definition irrelevant to lazy languages.
Case in point: such a programmer does not want space to grow and cause
slowness, and he could achieve that by defining no more than a memory
bound and a time bound; but he imposed requirements on the program
text too, namely that the program text should not mention a large data
structure. This definition disregards two tools absent in C++, namely
lazy execution and automatic garbage collection. This definition says
too much, not too little.
--
NewsGuy.Com 30Gb $9.95 Carry Forward and On Demand Bandwidth
Kyle
> Tomasz Zielonka <tomasz....@gmail.com> writes:
>
>> Perhaps you could define what does it mean to compute *it*?
>
[snip]
> This definition disregards two tools absent in C++, namely
> lazy execution and automatic garbage collection.
clarification:
garbage collection is available in C++, see
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
> This definition says
> too much, not too little.
hmmm ... if no full definition of 'compute *it*' is given, the whole
competition misses its point ... (it should be reasonable for both lazy
and eager languages however)
Dr.Ruud
> Albert Lai:
>> Tomasz Zielonka:
>>> Perhaps you could define what does it mean to compute *it*?
>>
>> This definition disregards two tools absent in C++, namely
>> lazy execution and automatic garbage collection.
>
> clarification:
> garbage collection is available in C++, see
> http://www.hpl.hp.com/personal/Hans_Boehm/gc/
Lazy evaluation in C++ can be "just another way of programming"
http://www.xum99.dial.pipex.com/comp/tech/lazycalc.shtml
http://www.xum99.dial.pipex.com/comp/tech/lazyinit.shtml
Concepts, Techniques, and Models of Computer Programming
http://www.ulb.ac.be/di/rwuyts/INFO020_2003/vanRoyHaridi2003-book.pdf
http://www.ulb.ac.be/di/rwuyts/INFO020_2003/
A Functional Pattern System for Object-Oriented Design
http://www.mm.informatik.tu-darmstadt.de/~kuehne/tfps/fps-sans-escher.pdf
http://www.mm.informatik.tu-darmstadt.de/staff/kuehne/fps/
With Perl5, use Memoize for the caching.
--
Affijn, Ruud
"Gewoon is een tijger."
Steve Harris
Looks to me more like just another way of taking your mind off the
application domain where it belongs.
>From the article:
"
In order to convert a calculation into a lazy calculation you need to
perform the following steps:
* If the result of the calculation is currently not stored anywhere
then introduce an appropriate member variable to hold the results of
the calculation.
* If there is not one already, introduce a getter method for
accessing the result of the calculation, scoping it appropriately. For
example, if the value was never accessed outside of the class then this
should be a private method.
* Ensure that all access to the value, including access within the
class, is via the getter method.
* Introduce a boolean variable that indicates whether or not the
calculation is up-to-date.
* Initialise the boolean to false to indicate that the calculation
still needs to be performed.
* If the calculation is currently performed every time one of the
parameters to the calculation is changed, remove this recalculation.
* Add code to set the boolean to false any time one of the
parameters to the calculation changes.
* Modify, or implement, the getter method so that it performs the
following steps:
1. Test the value of the boolean member variable.
2. If the value is false then perform the calculation, storing
the result in the member variable that is to hold the result, and set
the value of the boolean to true.
3. Return the value held in the member variable that holds the
result of the calculation.
[snip]
Obvious, but worth stating... This example is not thread safe!
"
Dr.Ruud
>> Lazy evaluation in C++ can be "just another way of programming"
>
> Looks to me more like just another way of taking your mind off the
> application domain where it belongs.
Tsk.
I suggest you read the whole article. And grok templates.
Steve Harris
I did read the first two articles before my patience ran out, but they
say nothing about templates that I could tell, with no obvious
navigation to further pages. If the other articles talk about a lazy
evaluation strategy using templates or whatever then maybe you could
give more specific links, e.g. 3rd link is an entire book (which I do
own, but I don't recall it touching on lazy eval in C++).
Anyway I submit that templates won't save you the work of adding the
accesssors and boilerplate code he talks of adding for lazy evaluation,
you'd need a real preprocessor for that I would wager, but I might be
wrong : maybe you could give an example?
Is there something about lazy evaluation in the third pair of links?
Dr.Ruud
> I submit that templates won't save you the work of adding the
> accesssors and boilerplate code he talks of adding for lazy
> evaluation, you'd need a real preprocessor for that I would wager,
> but I might be wrong : maybe you could give an example?
http://www.boost.org/libs/spirit/phoenix/doc/introduction.html
> Is there something about lazy evaluation in the third pair of links?
Yes, a lot.
It's moving:
Lambda expressions and closures for C++
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1968.pdf