The Pebble in the Ruby Shoe

[Robert Dober]

There's a big difference between an explicit stack with iterative code
and recursion with an implicit stack. I've done a lot of explicit stack
coding for walking data structures -- indeed, the last time I did so was
a recent piece of code that generates the state space of a large finite
Markov chain. But the only time I've written recursive functions as a
*preferred* modus operandi has been in Lisp, Scheme and the Lisp-based
symbolic math package Derive. And there, I've always aimed for tail
recursion.

I see recursion as a useful tool of abstraction I remember having
implemented quick sort on a Sharp PC [forgot the name] in its
primitive Basic dialect. There were 13 cells left to be sorted LOL.
Never ever has a program given me more satisfaction, but nowadays I
would rather not waste my time on doing it manually, well I remember a
fascinating post of James explaining that unwinding the stack has
become second nature to him.
But who else will be able and/or willing to read your program?

Just my 2 nickels.

R.

 

[Chad Perrin]

(taken off-list since wandering way OT
Understandable.

News to me. Would you point me at more information on the topic,
please?

In the perl world we have the $[ variable (see perldoc perlvar for
gory details) that resets the index of the first element. As the
documentation says "Its use is highly discouraged.". I'd imagine that
it's primary motivation for inclusion was to make compatability with
awk easier in early perl's (which also has 1 indexing).

I didn't know about the likely awk connection in the existence of $[, and
didn't know early Perl used 1-indexing. I guess I learn something new
every day.

When I said something was news to me, however, I meant specifically your
statement that the "fix" was global rather than per-array. I somehow
read that as "it applies globally, and you can't make it apply per
array", rather than how I now realize you meant it. When you first
mentioned that, I thought you were saying there was something like
perhaps a pragma that changed the way Perl handled arrays, or something
like that.

. . but yeah, I see now you were just referring to the fact that $[ is
a global variable. Of course, there's always the local hack:

{
local $[ = 1;
# do stuff
}

For example:

my @array = ( 1 .. 10 );

$[ = 0;
print @array[5], "\n";

$[ = 1;
print @array[5], "\n";

$[ = 2;
print @array[5], "\n";

would produce

6
5
4

Spooky action at a distance. Scary.

A little weird, to be sure -- but awfully flexible if you need it, I
suppose. Probably the most disturbing thing about it for me is the fact
that, for each of the changes to $[ in your code snippet, that changes
the behavior of *all* arrays. Downright terrifying.

Fortran (or those versions that support it anyway) allow you to
specify the indices of a particular array - so for example you could
have

real temperature(-100:100)

to make an array of real values with indices from -100 to 100. So you
can make the indices of your array match the indices of your domain -
if that would make your life easier

I don't know any Fortran, so the talk of Fortran and arbitrary array
ranges is entirely new to me -- and fascinating. The various differences
of feature sets between languages really teaches some interesting
principles, I find.

See <http://www.stanford.edu/class/me200c/tutorial_77/10_arrays.html>
for some examples.

Thanks.

 

[Chad Perrin]

(taken off-list since wandering way OT

[snip]

Or it would have been if I'd had more coffee this morning - sigh -
apologies all.

. . and I replied without checking the address. Heh. I guess I helped
propagate the mistake. Ouch.

 

[John Joyce]

I stand by my claim in spite of a pair of anecdotal reports. Don't
make me survey your papers. (Actually, I can't find many, if any,
publications for either of you. I'm not saying that means anything.)

Steve

P.S. If this is you then I suspect we may have mutual acquaintances:
http://www.google.com/patents?hl=en&lr=&vid=USPAT5885158

This whole business about 1 or 0 based indexing is not important.
It's a moot point.
If you want it added to the language, ask at Ruby Core, Matz does
read this stuff and does care what users think.
But if it doesn't change, don't waste time or electrons complaining
and arguing about it.
I'd like a lot of languages to change (CSS is one) but if you really
want it, make it.
That's what Matz did!
Larry Wall made Perl, Guido Van Rossum made Python, and that guy who
made PHP.
Many of the more advanced, more esoteric languages were started as
the efforts of a single person.

 

[Chad Perrin]

Not only did I not mean to imply that, but I'm not sure I can even
parse "bad practical decision". If I knew the evidence I had implied
in support of my implied claim then maybe I could.

But I even explicitly said that "It's a good and safe decision
supported by decades of computing convention and habit..."

That would be why I used terms like "seem" and so on in that email -- I
wasn't 100% certain of your intent, based on what you said.

I'm just sick of hearing that Ruby does such and such because
mathematicians like it.

Fair enough. I agree with you on that score, actually -- that it gets
kind of old seeing people try to equate everything in computer science
with the will of mathematicians. That's the sort of thinking that leads
to CS students wasting time on trigonometry when they could be spending
it on something useful to computer science, like linear algebra.

 

[Ken Bloom]

Ruby aims to be a human friendly programming language that embodies the
principle of least surprise. However, there is an important feature of
the language that, despite being a glaring exception to this laudable
goal, seems to have crept unquestioned into the Ruby core. It is a
rebarbative and truly medieval practice which everyone knows causes
endless confusion, countless unnecessary errors, and a great deal of
wasted programming time in all languages that incorporate it, e.g., C,
Java. In violation of Ruby's ethos, this feature is present purely to
suit the compiler/interpreter at the expense of the person.

The pebble in the Ruby shoe is the counter-intuitive use of indexing of
elements of arrays, strings, etc., from 0 to n-1 instead of the more
natural 1 to n. Like prisoners who have got used to their chains, the
Ruby community seems to have meekly accepted this impediment to clear
thinking. It is particularly puzzling that Ruby should hobble its
users in this way, because it is manifestly unnecessary (e.g., Fortran
and Pascal don't do it).

If you were going to argue for arbitrarily indexed arrays e.g. those
ranging from 47 thru 300 or from -26 thru 68, you might have a point that
there's something more natural in your proposal. (Although it would break
other features of arrays that we hold very dear to our hearts.)

Arguing 1-based arrays to replace 0-based arrays is arbitrary at best,
and unnatural at worst.

 

[John W. Kennedy]

Well ... they *are* talking seriously about dumping Call/CC. How many
Ruby programmers, or, for that matter, C programmers, actually use
recursion, even tail recursion? Recursion has been mainstream in
programming languages since Algol 60, but how many people actually use
it outside of Lisp/Scheme and other functional languages?

I used it just the other day in a Ruby solver for
<URL:http://xkcd.com/c287.html> (I should add that the last time I even
/thought/ about a packing problem was 1967, so my approach was brute force.)

 

[Robert Dober]

Interesting. This is wild speculation of course, but I imagine you are
probably atypical as far as always using explicit stacks. (Since I get the
impression from your post history that you are heavily focused on
performance.). I would guess (more speculation ) that if someone were to
grab a set of programs that for instance walked an XML DOM (or a similar day
to day tree structure, like a nested directory) that the vast majority of
those programs would use recursion with implicit stacks. Now that I've
contributed that bit of unsubstantiated nonsense, I'll resume eating my
dinner.

I remember a funny use case of explicit stack handling now.
About 4 years ago I was writing an XML wrapper around the Python tupleparser.
I started recursively, of course and very soon got completely lost, I
tried to undo the recursion so that I had full control over some
details on the call stack (things like cheating by examining the call
stack) never got anywhere but I have to admit it was good to have that
technique at my disposal.
If I recall correctly I would probably have used a recursive approach
with yield in Ruby...

But I agree these are rare exceptions and no reason at all not to use
recursion, a better design might have allowed for a recursive solution
too

Cheers
Robert

 

[Ken Bloom]

Lets not forget also that doing things for the sake of being different
help no one. I for one must work in multiple languages. I still haven't
forgiven Matz for the whole, "0 is true" thing. ;-)

But in the shell, zero is the ONLY return code which is true.

--Ken

 

[M. Edward (Ed) Borasky]

That would be why I used terms like "seem" and so on in that email -- I
wasn't 100% certain of your intent, based on what you said.



Fair enough. I agree with you on that score, actually -- that it gets
kind of old seeing people try to equate everything in computer science
with the will of mathematicians. That's the sort of thinking that leads
to CS students wasting time on trigonometry when they could be spending
it on something useful to computer science, like linear algebra.

Well ... maybe "Computer Science" students don't need to know
trigonometry, but I doubt very seriously a trig-impaired person could
get an Electrical Engineering degree. Hell, if they didn't have trig and
calculus and analytic geometry under their belts on the SAT, they
couldn't get *into* a EE program!

I was actually one of the first students in the USA to get calculus and
analytic geometry in high school. This was right after Sputnik and I
lived in a town full of scientists and engineers. I was also fortunate
to have graduated before the "New Math", which was mostly set theory.

So ... would you say queuing theory is useful to computer science? I
certainly would. Well, it turns out, as we mathematicians like to say,
that you can use a Fast Fourier Transform to solve some queuing theory
problems that are more or less intractable otherwise. Can you do a Fast
Fourier Transform without sines and cosines?

 

[M. Edward (Ed) Borasky]

Interesting. This is wild speculation of course, but I imagine you are
probably atypical as far as always using explicit stacks. (Since I get the
impression from your post history that you are heavily focused on
performance.). I would guess (more speculation ) that if someone were to
grab a set of programs that for instance walked an XML DOM (or a similar
day to day tree structure, like a nested directory) that the vast majority of
those programs would use recursion with implicit stacks. Now that I've
contributed that bit of unsubstantiated nonsense, I'll resume eating my
dinner.

1. I am the very model of premature optimization. Unless the underlying
run-time has made a great effort to make (tail) recursion efficient,
like most Lisps, Schemes, and the core of Derive, it's usually less
efficient than iteration and harder for other programmers to understand.

2. I've been quite fortunate in avoiding XML so far. I like *my* trees
with squirrels and blue jays in them, thankyouverymuch.

3. Perhaps Charles Nutter would comment on how efficient jRuby on the
JVM is at recursive code compared to MRI Ruby. I'd expect it to be
better, given that some Schemers were involved in the creation of Java.

 

[Chad Perrin]

Well ... maybe "Computer Science" students don't need to know
trigonometry, but I doubt very seriously a trig-impaired person could
get an Electrical Engineering degree. Hell, if they didn't have trig and
calculus and analytic geometry under their belts on the SAT, they
couldn't get *into* a EE program!

There's a pretty big difference between "electrical engineering" and
"computer science".

I was actually one of the first students in the USA to get calculus and
analytic geometry in high school. This was right after Sputnik and I
lived in a town full of scientists and engineers. I was also fortunate
to have graduated before the "New Math", which was mostly set theory.

So ... would you say queuing theory is useful to computer science? I
certainly would. Well, it turns out, as we mathematicians like to say,
that you can use a Fast Fourier Transform to solve some queuing theory
problems that are more or less intractable otherwise. Can you do a Fast
Fourier Transform without sines and cosines?

Maybe not -- but my objection is more to the saddling of CS students with
several years of trig and calculus *classes* than with the imparting of
any of the basics that are related to those subjects. The basics of
trigonometry as taught in a trig class, in fact, can be imparted to a
student quite thoroughly in about two class sessions -- and it usually
is, in a preceding geometry or algebra course. Meanwhile, the rest of
what's "taught" in typical college trig courses can be easily derived
from the basics, and is just rote memorization for the purpose of passing
tests, to be forgotten immediately after the test in time to memorize for
the next exam.

Meh. I have traumatic experiences of almost being entirely turned off of
"higher education" by the stupidities of a computer science curriculum.
Your mileage may vary.

 

[Wayne E. Seguin]

I stand by my claim in spite of a pair of anecdotal reports. Don't
make me survey your papers. (Actually, I can't find many, if any,
publications for either of you. I'm not saying that means anything.)

http://en.wikipedia.org/wiki/Mathematician

 

[Kaldrenon]

Well ... they *are* talking seriously about dumping Call/CC. How many
Ruby programmers, or, for that matter, C programmers, actually use
recursion, even tail recursion? Recursion has been mainstream in
programming languages since Algol 60, but how many people actually use
it outside of Lisp/Scheme and other functional languages?

I haven't had /that many/ opportunities to use recursion, but I tend
to use it wherever it is both applicable and not prohibitively
resource intensive. The latter is a valid concern when choosing how to
solve a given problem, but for cases in which recursion won't blow the
stack or drastically affect performance, I like to use it. Not because
it's /better/, per se...just because it's more fun and often a bit
more challenging.

Granted, I'm still a student in the early part of my education, so I
don't know how viable recursion will be for me in "the real world", in
consumer apps and the like, but I'll still use it when I see an
opportunity.