preliminary eiffel implementation

[johnperry-math]

This is a preliminary Eiffel implementation. I'm not sure I'll ever improve it, so I'll go ahead & create the pull request. One of the gurus I spoke with suggested a slightly different approach (still recursive) and while I tried that without success I'll give it another go in due course.

[frol]

Thank you for the contribution! I will merge this as soon as I have a timeframe to install the compiler and run the benchmark.

[johnperry-math]

If I do update it before you get to that point, I can just push the changes & it will automatically come into this pull request, right?

[frol]

Right

[johnperry-math]

I just pushed a commit that reduces execution time by about 33% while preserving the algorithm's nature. I also added a bunch of contracts, which are Eiffel's claim to development reliability fame. Barring something really unexpected, that's all I plan to do for this one.

[frol]

Well, technically, once you start measuring the performance, you violate the definition of "naive solution" that we gave in the README:

We define the "naive" implementations as those which a developer with enough experience in a given language would implement as a baseline "good enough" solution where correctness is more important than performance.

[johnperry-math]

This is a bit long, but you make a very good point, so I want to give a thorough explanation as to why I think this is "naive".

Perhaps the clearest evidence that it is naive is that the current Eiffel version runs in ~1.0s on my old MacBook Pro, while even the "naive" C++, Modula, Nim, and Oberon versions run in ~0.3s.

Another is that my initial approach is, quite arguably, that of someone who doesn't have "enough experience" in Eiffel. While I did use Eiffel 15 years ago, it was not enough even to remember that Eiffel doesn't allow one to modify arguments to a function. After seeing this compiler error I spent about 30 minutes scouring the internet looking for a keyword similar to Ada's out or Pascal's VAR -- and I gave up on this only after about 30 minutes. Most Eiffel references don't breathe a word about this.

So I had to find a solution that, as you say, a developer with "enough experience" would use. While I did find a solution on my own after a while, I already thought my initial submit was wayyyyy too cumbersome with constant copying of data, and the timings seemed to reflect this, so I asked on an Eiffel users' list. Nearly the unanimous response was, "you don't use this technique." One wrote,

An Eiffel programmer would not implement split with recursive calls (probably because Eiffel does not support in/out arguments). Instead of that, he or she would implement split using a loop.

As that isn't an option, he suggested passing parent nodes instead of the nodes themselves. I interpret that as meaning that this is what a regular Eiffel developer would do just to make it work. Even then, I had to modify his suggested pseudocode significantly.

By contrast, the tuned implementations I've seen use tricks like turning off the garbage collector (Nim), or implement a memory pool (C++, Object Pascal, Modula-3), turn off array bounds checking (Nim), etc. The Eiffel code I submitted does none of that.