Algorithm books for Ruby (was Re: Object-oriented solution t

Ruby
1

On 5/12/07, Martin DeMello [email protected] wrote:

On 5/12/07, Rich M. [email protected] wrote:

Robert K. wrote:

I suggest you also read a decent book on data structures and algorithms
(Knut, Sedgewick or the like).

I find Sedgewick to be a lot more useful than Knuth, because
he uses high-level (well, higher than assembly) code. I’d
love to see a good book on algorithms for Ruby (hint!).

give brpreiss.com a look.

Thanks for that pointer Martin.

I’ve started reading it, and I have to say that I’m feeling the need
for a salt shaker for liberal use.

My first hint that this might not be the best approach for Ruby was
the large number of versions for other languages. I’m afraid that
this looks like YAPB (yet another ported book). It seems to treat
Ruby as if it were C.

In the algorithm analysis section he describes various axioms, which
appear to be more beleivable for a C program than for Ruby. Constant
variable access? constant method call overhead? array access
equivalent to a certain number of ruby operations? These appear to be
based on thought experiments rather than actual measurements of the
ruby implementation.

'm a little suspicious that this might be a case of using the axioms
of plane geometry when the subject is spherical geometry.

For example, I’m pretty sure that these two snippets will have
different timing profiles

a = Array.new(300)
a[200] = 1

and

a = Array.new(190)
a[200] = 1

Since Ruby arrays are dynamically sized, the second needs to
reallocate and copy the contents.

So in these cases certain array stores might actually be O(n) where n
is the length of the array rather than O(1).

Also the analysis of the space taken up by an array is suspect. In
general Ruby arrays have a heuristically sized storage area which
grows and shrinks automatically. The size is not always a function of
the length of the array, the implementation keeps both a length, which
is what the Ruby programmer sees, and a capacity which is the actual
size of the currently allocated storage area.

When we get to the fundamental data structures part, we see him
monkeypatching Array, to provide for different index origins.

The main portion of the book seems to be building an alternative to
the ruby library.

I’m not sure I’d recommend this to someone as a way to improve their
skills with Ruby.

I think that a more useful work would do some analysis of the
implementation of the core ruby classes like Array and Hash.

But that’s just my opinion.

I was amused by some of the google ads I saw while browsing the book.
One was for arborists in my vicinity. I guess it had something to do
with the book talking about trees.

–
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

2

On 5/13/07, Rick DeNatale [email protected] wrote:

this looks like YAPB (yet another ported book). It seems to treat
Ruby as if it were C.

I’ll admit, I haven’t read the book - I looked at the table of
contents and it seemed like it had decent coverage. Shame about the
actual development. I’d be all for an effort to create a similar book
for ruby. What would be a nice approach is a tour of the fundamental
data structures, each one accompanied by an algorithm that it forms
the core of, and a full implementation in ruby. If this were aimed at
working programmers looking at going back and catching up on CS
fundamentals, the examples could be one level above the usual toys -
for instance:

stack → infix arithmetic expression parser
queue → bitmap floodfill
linked list → trivial memory allocator and compactor
heap → priority queue
etc.

martin

3

quoth the Martin DeMello:

What would be a nice approach is a tour of the fundamental
data structures, each one accompanied by an algorithm that it forms
the core of, and a full implementation in ruby.

He does include code in Ruby, though oddly, it is not presented inline,
nor
even linked inline:

http://www.brpreiss.com/books/opus8/programs/index.html

martin

-d

4

Rick DeNatale schrieb:

And this
brpreiss.com

by just

a.max

A random sampling of the code looks like it’s mostly C-code
transliterated into Ruby.
I have stumbled over this book some years ago and read a few pages to
figure out if it was worth reading. I encountered a sentence that
contained something like “ruby virtual machine creates an object”. This
was before Ruby 1.9. included YARV and when YARV didn’t yet exist (or
was in its early infancy like all the other VM implementations back
then), and the author didn’t mention which virtual machine he meant at
all. I figured he didn’t know that Ruby was an AST interpreter and just
made shit up. I decided not to invest more time in reading the book,
because if the author cannot be bothered to research some basic facts
about Ruby and instead spreads untruth about it, what quality will the
rest of the book have?

Your transliteration theory reminded me of that, so I searched for “ruby
virtual machine creates an object” on google:

http://www.google.com/search?hl=en&safe=off&q=site%3Abrpreiss.com+"ruby+virtual+machine+creates+an+object"&btnG=Search

Result was:
“Garbage Collection and the Other Kind of Heap
When the Ruby virtual machine creates an object, it performs the
following steps:. An unused region of memory large enough to hold an
instance of the …
brpreiss.com - 6k - Cached - Similar
pages”

Now, I changed “ruby” to “python”:

http://www.google.com/search?hl=en&safe=off&q=site%3Abrpreiss.com+"python+virtual+machine+creates+an+object"&btnG=Search

Result was:
“Garbage Collection and the Other Kind of Heap
When the Python virtual machine creates an object, it performs the
following steps:. An unused region of memory large enough to hold an
instance of the …
brpreiss.com - 7k - Cached - Similar
pages”

What a surprise! Writing books doesn’t seem to be so difficult after
all.

5

On 5/14/07, Florian F. [email protected] wrote:

Rick DeNatale schrieb:
.max

A random sampling of the code looks like it’s mostly C-code
transliterated into Ruby.
I have stumbled over this book some years ago and read a few pages to
figure out if it was worth reading. I encountered a sentence that
contained something like “ruby virtual machine creates an object”. This
was before Ruby 1.9. included YARV and when YARV didn’t yet exist (or
was in its early infancy like all the other VM implementations back
then), and the author didn’t mention which virtual machine he meant at
all.

Well, to be fair he actually does describe the VM as working on an
AST. VM is a general term which actually could be used to describe
the Ruby 1.x implementation even if x < 9. In fact doesn’t YARV stand
for Yet Another Ruby Vm?

brpreiss.com - 6k - Cached - Similar
instance of the …
brpreiss.com - 7k - Cached - Similar
pages"

What a surprise! Writing books doesn’t seem to be so difficult after all.

At least rewriting them isn’t as hard as writing them.

–
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

6

Florian F. wrote:

even linked inline:
(1…n).inject {|sum, e| sum + e)
I have stumbled over this book some years ago and read a few pages to

instance of the …
When the Python virtual machine creates an object, it performs the
following steps:. An unused region of memory large enough to hold an
instance of the …
brpreiss.com - 7k - Cached - Similar
pages"

What a surprise! Writing books doesn’t seem to be so difficult after all.

I am totally underwhelmed by that book. The print versions are
horrendously expensive, given the elementary nature of the subject
matter. I’d definitely echo the sentiments of those who recommend
Sedgewick, and I’ll also throw in a plug for “The Structure And
Interpretation of Computer Programs” and “The Little Schemer” should you
happen to want a Scheme foundation.

7

Does anyone have experience installing bdb-0.5.9 on a mac - I can not
get it to install, despite the fact that I’ve made sure to install
berkeley db on the system. When I try to run extconf.rb, I get:

extconf.rb: Entering directory `src’
checking for db_version() in -ldb-4.4… no
checking for db_version_4004() in -ldb-4.4… no
checking for db_version() in -ldb44… no
checking for db_version_4004() in -ldb44… no
checking for db_version() in -ldb-4.3… no
checking for db_version_4003() in -ldb-4.3… no
checking for db_version() in -ldb43… no
checking for db_version_4003() in -ldb43… no
checking for db_version() in -ldb-4.2… no
checking for db_version_4002() in -ldb-4.2… no
checking for db_version() in -ldb42… no
checking for db_version_4002() in -ldb42… no
checking for db_version() in -ldb-4.1… no
checking for db_version_4001() in -ldb-4.1… no
checking for db_version() in -ldb41… no
checking for db_version_4001() in -ldb41… no
checking for db_version() in -ldb-4.0… no
checking for db_version_4000() in -ldb-4.0… no
checking for db_version() in -ldb-4… no
checking for db_version_4000() in -ldb-4… no
checking for db_version() in -ldb40… no
checking for db_version_4000() in -ldb40… no
checking for db_version() in -ldb4… no
checking for db_version_4000() in -ldb4… no
checking for db_version() in -ldb3… no
checking for db_version_3000() in -ldb3… no
checking for db_version() in -ldb2… no
checking for db_version_2000() in -ldb2… no
checking for db_version() in -ldb… no
*** extconf.rb failed ***
Could not create Makefile due to some reason, probably lack of
necessary libraries and/or headers. Check the mkmf.log file for more
details. You may need configuration options.

Provided configuration options:
–with-opt-dir
–without-opt-dir
–with-opt-include
–without-opt-include=${opt-dir}/include
–with-opt-lib
–without-opt-lib=${opt-dir}/lib
–with-make-prog
–without-make-prog
–srcdir=.
–curdir
–ruby=/usr/local/bin/ruby
–enable-unknown
–disable-unknown
–with-db-dir
–without-db-dir
–with-db-include
–without-db-include=${db-dir}/include
–with-db-lib
–without-db-lib=${db-dir}/lib
–enable-thread
–disable-thread
–with-db-uniquename
–without-db-uniquename
–with-db-version
–without-db-version
–with-db-4.4lib
–without-db-4.4lib
–with-db-4.4lib
–without-db-4.4lib
–with-db44lib
–without-db44lib
–with-db44lib
–without-db44lib
–with-db-4.3lib
–without-db-4.3lib
–with-db-4.3lib
–without-db-4.3lib
–with-db43lib
–without-db43lib
–with-db43lib
–without-db43lib
–with-db-4.2lib
–without-db-4.2lib
–with-db-4.2lib
–without-db-4.2lib
–with-db42lib
–without-db42lib
–with-db42lib
–without-db42lib
–with-db-4.1lib
–without-db-4.1lib
–with-db-4.1lib
–without-db-4.1lib
–with-db41lib
–without-db41lib
–with-db41lib
–without-db41lib
–with-db-4.0lib
–without-db-4.0lib
–with-db-4.0lib
–without-db-4.0lib
–with-db-4lib
–without-db-4lib
–with-db-4lib
–without-db-4lib
–with-db40lib
–without-db40lib
–with-db40lib
–without-db40lib
–with-db4lib
–without-db4lib
–with-db4lib
–without-db4lib
–with-db3lib
–without-db3lib
–with-db3lib
–without-db3lib
–with-db2lib
–without-db2lib
–with-db2lib
–without-db2lib
–with-dblib
–without-dblib
extconf.rb: Leaving directory `src’
Link-Dans-Powerbook:~/Desktop/bdb-0.5.9 Dan$

8

On 5/15/07, M. Edward (Ed) Borasky [email protected] wrote:

matter. I’d definitely echo the sentiments of those who recommend
Sedgewick, and I’ll also throw in a plug for “The Structure And
Interpretation of Computer Programs” and “The Little Schemer” should you
happen to want a Scheme foundation.

I’ll toss in another plug for Corman et al, which I found an excellent
textbook back when my algorithms course used it.

martin

9

Rick DeNatale schrieb:

Well, to be fair he actually does describe the VM as working on an
AST. VM is a general term which actually could be used to describe
the Ruby 1.x implementation even if x < 9. In fact doesn’t YARV stand
for Yet Another Ruby Vm?

But where’s the “machine” in an AST walker? If the term should make any
sense the higher language code has to be compiled into an intermediary
language. The virtual machine instructions will then be executed on a
simulated processor like the P-Code machine
(p-code machine - Wikipedia). If these compile and
execution steps don’t happen, I would call the resulting program only a
Ruby interpreter - not a Ruby virtual machine.

I think that YARV was named YARV because there were other efforts to
create a Ruby VM besides Matz’s RITE vapor ware, when ko1 started to
implement YARV. I remember him mentioning something like this in one of
his talks.

At least rewriting them isn’t as hard as writing them.

Maybe the author deliberately confused AST interpreters and VMs in order
to cut down on the transliteration work?

10

On 5/13/07, darren kirby [email protected] wrote:

quoth the Martin DeMello:

What would be a nice approach is a tour of the fundamental
data structures, each one accompanied by an algorithm that it forms
the core of, and a full implementation in ruby.

He does include code in Ruby, though oddly, it is not presented inline, nor
even linked inline:

brpreiss.com

Not the best examples of ruby code though.

For example this:
http://www.brpreiss.com/books/opus8/programs/pgm02_01.txt

Would be done idiomatically in Ruby as

(1…n).inject {|sum, e| sum + e)

And this
http://www.brpreiss.com/books/opus8/programs/pgm02_04.txt

by just

a.max

A random sampling of the code looks like it’s mostly C-code
transliterated into Ruby.

Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

11

On 5/15/07, Florian F. [email protected] wrote:

(p-code machine - Wikipedia). If these compile and
execution steps don’t happen, I would call the resulting program only a
Ruby interpreter - not a Ruby virtual machine.

I think that this is too strict a definition. To my mind, a Virtual
Machine simply provides some form of virtual execution environments.
There seem to be two main branches of VMs, language VMs and VMs for
hosting multiple operating systems, or instances of operating systems
on one set of hardware.

A language VM in general, provides an execution environment which is
higher-level than the hardware. There is more to this than just
program representation, it also includes, for example GC where the
language requires it. The implementation of GC and execution are
co-dependent.

In most language VM implementations program execution is implemented
by some form of interpretation. The difference between bytecode and
AST representation of the “object code” is really just an
implementation choice. Other VMs use threaded code representations,
and there are probably others.

And if we are talking about VMs in the operating system sense,
virtualization is the isolation of process groups into virtual
hardware machines, the program execution is done by the hardware
itself, which is the other end of the spectrum.

While bytecode/p-code interpretation is a common feature of many
virtual machines, I don’t consider it to be the sine-qua-non of
VMness.

At least rewriting them isn’t as hard as writing them.

Maybe the author deliberately confused AST interpreters and VMs in order
to cut down on the transliteration work?

Well he does actually make the distinction. Compare this page from
the Ruby version:
http://www.brpreiss.com/books/opus8/html/page36.html

which actually shows the AST interpreter (called parse tree
interpreter) as part of the Ruby VM, with the equivalent page from the
python version:
http://www.brpreiss.com/books/opus7/html/page37.html

which shows byte code interpretation.

Not that this makes the rest of the books valuable as resources for
the different languages it’s been adapted to.

–
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/

12

On 5/15/07, Rob B. [email protected] wrote:

And let me add that Leiserson was a great professor and Corman an
excellent TA when I took the course at MIT before there was a book!

I’d be envious except I already used up my quota on the friend who
studied under Feynman. :slight_smile:

m.

13

On May 15, 2007, at 2:28 AM, Martin DeMello wrote:

martin
And let me add that Leiserson was a great professor and Corman an
excellent TA when I took the course at MIT before there was a book!

-Rob

Rob B. http://agileconsultingllc.com
[email protected]