[Shootout-list] Re: Re: [Shootout-list] Binary trees

[simon@whiteowl.co.uk]

Jon Harrop <jon@ffconsultancy.com> wrote on 20.06.2005, 01:41:43:
> On Sunday 19 June 2005 18:47, Einar Karttunen wrote:
> > Jon Harrop  writes:
> > > This is not totally unlike a real program. In particular, this tree can
> > > be empty (containing only one T object, Empty). The other implementations
> > > (e.g. OCaml, MLton, Haskell) can't represent an empty tree. Does this
> > > make them invalid?
> >
> > The Haskell implementation which is currently the fastest has:
> 
> It says Clean, D and MLton are faster ATM.
> 
> > data Tree = Node  Int Tree Tree | Nil
> > which is perfectly capable of representing an empty tree. If the other
> > ones are not they should be fixed.
> 
> You are quite right. This is putting Haskell at a disadvantage. But what can 
> we do about it?
> 
> > >   type int_tree = Empty of int | Node of int_tree * int * int_tree
> >
> > Seems unfair to me.
> 
> Yes, it is arbitrarily "unfair" but unavoidable with the current approach, 
> i.e. there is no clear C equivalent to either of those - the underlying 
> representation is up to GHC, ocamlopt, MLton etc.
> 
> Some people have said that we are trying to measure the compilers' efficiency 
> at optimising. This is a perfectly valid point but doesn't get around the 
> fact that this type of benchmark is totally subjective.
> 
> Also, I haven't found anyone who knows how to code a Fortran equivalent to the 
> tree in my ray tracer. Consequently, the current Fortran entry implements 
> quite a different data structure which is simpler and substantially less 
> powerful than that found in most other languages. I don't object to this, of 
> course, because the program still works but other people should object 
> strongly (if they are self-consistent).
> 
I'd appreciate some clarification of this point. When I wrote the
fortran version I did my best to translate the c++ code you had
provided. At that point I used a tree data-structure and as far as I
can see the existing implementations also use a tree data-structure.
Whilst the implementation may well not be identical to the others now I
don't see any justification for the assertion that 'the current Fortran
entry implements quite a different data structure which is simpler and
substantially less powerful than that found in most other languages'
It is no doubt true that Fortran lacks some of the facilities found in
other languages - this is true for all languages. Part of my enthusiasm
for contributing the fortran implementations is that I'd like people to
be able to judge the language for what it provides today rather than
many peoples perception of it as it was (in f77/66 days). One of the
many improvements to the language is the ability to code trees, lists
etc. naturally rather than shoe-horning arrays into the task.

If the current implementation really is deficient as you describe it
would be useful to have a specification so that it can be implemented
as you intend. A commented reference implementation should be good
enough for this - as long as it is in what I would call a normal
language (java, c++, c#, python, tcl, fortran).

Simon