SICP 1.1.6 (Ruby) A look back

In my post on SICP 1.1.6, there were a couple of questions raised about my Ruby code.

Fabio Akita Your first example would be better written off as:

def abs(num)
num < 0 ? -num : num
end

Personally, I really hate the ternary if, I’ve always thought that it makes code harder to read. It’s probably still worth looking at though, since my biases are just that.

Peter Cooper ... I was just intrigued as to why you wouldn’t use idiomatic Ruby, when SICP tends to use Scheme very idiomatically.

This is another one of my failings, I’ve been doing enough non-Ruby stuff lately that I wasn’t thinking in it. Couple that with sitting down to ‘translate’ the code in separation from reading the text, and I was set to really mess up. Hopefully I can correct this going forward.

In any case, it’s worth looking at how well the various versions of abs perform in Ruby, so here’s a simple benchmarking script to try

def tern_abs (a)
  a < 0 ? -a : a
end

def explicit_abs (a)
  if a < 0
    a = -a
  end
  a
end

def implied_abs (a)
  if a < 0
    -a
  else
    a
  end
end

require 'benchmark'

n = 1_000_000

Benchmark.bm(15) do |x|
  x.report("ternary:")  { n.times do ;tern_abs(-5);tern_abs(5); end }
  x.report("explicit:") { n.times do ;explicit_abs(-5);explicit_abs(5); end }
  x.report("implied:")  { n.times do ;implied_abs(-5);implied_abs(5); end }
  x.report("system:")   { n.times do ;-5.abs;5.abs; end }
end

And here are the results of running it:

ruby benchmarking_abs.rb 
                     user     system      total        real
ternary:         0.550000   0.000000   0.550000 (  0.558707)
explicit:        0.330000   0.000000   0.330000 (  0.324859)
implied:         0.320000   0.000000   0.320000 (  0.322541)
system:          0.240000   0.000000   0.240000 (  0.241916)

It turns out that (at least in this case) the ternary form is the least performant. It’s probably no surprise that the built in version is the fastest. From now on, I’ll stick to using the built in abs.

Just for grins, here’s the result of the benchmark when I run it on JRuby:

$ jruby -v
ruby 1.8.5 (2007-08-23 rev 4201) [i386-jruby1.0.1]
$ jruby benchmarking_abs.rb
                    user     system      total        real
ternary:         1.768000   0.000000   1.768000 (  1.767000)
explicit:        1.734000   0.000000   1.734000 (  1.734000)
implied:         1.729000   0.000000   1.729000 (  1.730000)
system:          0.716000   0.000000   0.716000 (  0.716000)

It looks like the system is an even better deal compared to the ‘roll your own’ versions, though there appears to be less of a difference between them. (Any JRubyists out there care to venture a guess as to why that might be?)

SICP 1.1.7 (Factor)

I’m going back to the idea of treating each langauge in a separate post. Hopefully this will make the comments a bit more manageable (especially since I cross posted the last one onto my erlang blog as well).

Housekeeping

There were several factor related comments on the last post that I wanted to address before I moved on to section 1.1.7.

Anonymous Is Factor “done”? Seems like it’s still very much a work in progress.

Can you comment on your choice of Factor and what has made it enjoyable for you?

Anonymous is right, Factor isn’t done yet. It is getting close though, and for what I’m doing, it seems to be “done enough”. I’m using it because I’ve been thinking about learning a stack based language for a while, just to learn to think a little bit differently. So far, it’s fun because it’s doing just that.

And the related:

Ed Borasky Factor? What does Factor have that Forth doesn’t have? At least Forth has an ANS standard and some vendors and a few thousand person-decades of programmer experience.

Ed, I think the big thing that drew me to Factor over Forth was an active Factor community that I sort of tripped over. Sometimes, it’s the squeaky wheel that draws a user.

The last two weren’t specifically related to Factor, but did show better ways of solving exercise 1.3 (without resorting to lists), so I worked up a factor solution in their vein:

: min ( a b -- a b ) 2dup <
  [ swap ] when ;
: top-two ( a b c -- d e ) min rot min -rot ;
: sum-of-squares ( a b -- c ) sq swap sq + ;
: sum-squares-of-larger ( x,y,z -- x ) top-two sum-of-squares ;

I agree that this is a much better way of solving the problem.

SICP 1.1.7

Okay, on to some code. I’m going to use the built-in sq and abs words from now on. There’s no sense in continuing to use mine when there’s a perfectly good version of the word already there. SICP built a series of procedures to find square roots using Newton’s method: sqrt, sqrt-iter, improve, average, and good-enough?. I rewrote these into the following Factor:

: average ( a b  -- c ) + 2 /f ;
: improve-guess ( num guess -- guess ) dup swapd /f average ;
: good-enough? ( num guess -- ? ) sq - abs 0.001 < ;
: sqrt-iter ( num guess -- guess ) 
  2dup good-enough? 
  [ ]
  [ swap dup swapd swap improve-guess sqrt-iter ] if ;
: sqrt ( num -- root ) 1.0 sqrt-iter ;

These are nice and fairly concise, but sqrt-iter seems pretty ugly. I checked back in with the good folks on #concatenative (who have been immensely helpful) and they agreed, saying “swap dup swapd swap is a code smell”. They pointed out the dupd word, which does the same thing. so a better version of sqrt-iter would be:

: sqrt-iter ( num guess -- guess )
   2dup good-enough? 
   [ ]
   [ dupd improve-guess sqrt-iter ] if ;

Which can be improved still further into:

: sqrt-iter ( num guess -- guess )
   2dup good-enough? 
   [ dupd improve-guess sqrt-iter ] unless ;

I’m sure there are ways this could be improved yet further. Leave me a comment with your ideas. I’ll try to post my Ruby version tomorrow and Erlang on Thursday.

Reading SICP 1.1.6

This time around, I’ve decided to toss the translations for Ruby, Factor, and Erlang into the same post instead of trying to juggle multiple posts and point them all at one another. So, without further ado …

Section 1.1.6

Let’s take a look at section 1.1.6, the goal of this section is to look at conditional expressions through implementing an absolute value procedure. the book iterates through a couple of versions, trimming away fat. In each of my examples below, I’ve only shown the final product.

In Ruby, the code should look something like this:

def abs(num)   
  if num < 0
    num = -num
  end
  return num
end

In Factor it looks like this:

: abs ( n -- n ) dup 0 < [ -1 * ] [ ] if ;

And in Erlang it looks like this (I’ve left out the administrative bits from the top of the file):

abs(A) ->
    case ( A < 0) of
    true -> -1 * A;
    false -> A
    end.

Exercise 1.3

Esercise 1.3 asks the reader to write a procedure that takes three numbers and returns the sum of the squares of the largest two of them. In each case below, I rely on the previously defined square and sum-of-squares (sum_of_squares) procedures.

Ruby was pretty easy:

def sum_squares_of_larger(a, b, c)
  sorted_nums = [a, b, c].sort.reverse
  sum_of_squares(sorted_nums[0], sorted_nums[1])
end

Factor took me a while to figure out (mostly in trying to figure out how to build the array):

: top-two ( x,y,z -- x,y ) 3array natural-sort reverse first2 ;
: sum-squares-of-larger ( x,y,z -- x ) top-two sum-of-squares ;

I’m least sure of my Erlang code. I couldn’t find a good function for sorting the array, so I borrowed the qsort function from Programming Erlang. In any case, here’s my cut at it:

qsort([]) ->
     [];
qsort([Pivot|T]) ->
    qsort([X || X <- T, X < Pivot])
    ++ [Pivot] ++
    qsort([X || X <- T, X >= Pivot]).

last_two([H|T]) -> 
    T.

sum_of_squares_of_list(L) ->
    lists:sum([square(A) || A <- L]). 

sum_squares_of_larger(A, B, C) ->
    sum_of_squares_of_list(last_two(qsort([A,B,C]))).

What I learned

The biggest thing I’ve taken away from this exercise so far is that I really need a good Factor book that covers both the language and the vocabulary. Along similar lines, Programming Erlang is a good book, but it could have spent some more time on basic programming (especially covering the provided functions in something other than an appendix).

Factor has been the language that’s been hardest to wrap my mind around so far. At the same time, it’s the one that I’ve enjoyed the most—I also think the word definitions have a sort of terse beauty. I think Ruby is probably the one that most programmers could just pick up and maintain though.

Next up, Section 1.1.7 “Square Roots By Newton’s Method”.

Reading SICP in Factor: Section 1.1.4

Here’s my cut at SICP 1.1.4 in Factor. I’m a lot less sure of this than I am of the Ruby translation since I’m learning Factor as I go along. I’d appreciate comments from the Factor community as I go along, especially about Factor idioms.

In my Ruby translation, I failed to talk about some things, like procedures in SICP being methods in Ruby, and changing the method names to match the snake_case style favored by Rubyists. In the factor translation, procedures would be referred to as words, but I’ll be keeping the lispy-lowercase-divided-by-hyphens look.

There’s already a sq word in Factor, and I based my definition on that one.

> : square dup * ;
> 5 square .
25

The first line defines the word square and the second line tests it by excution. Lets see if I can explain the second line:

word or literal	stack	explanation
5	5	puts 5 on the stack
square	5	(I’ll explain this below)
dup	5 5	duplicates the top value on the stack
*	25	multiplies the top two values on the stack and replaces them with the result
.	{}	returns and removes prettyprints (and consumes) the top value on the stack

To create¹ and execute the sum-of-squares word we can do the following:

> : sum-of-squares ( a b -- c ) square swap square + ;
> 3 4 sum-of-squares .
25

Again, my attempt at explaining the second line:

word or literal	stack	explanation
3	3	put 3 on the stack
4	3 4	puts 4 on the stack
sum-of-squares	3 4	(explained below)
square	3 16	squares the top value on the stack
swap	16 3	swaps the top two values on the stack
sqare	16 9	squares the top value on the stack
+	25	adds the top two values on the stack and replaces them with the result
.	{}	returns and removes prettyprints (and consumes) the top value of the stack

(By the way, big thanks to Wilson Bilkovich for his editorial work on this post … he improved it immensely.)

1 In trying to create sum-of-squares, I ran into an initial problem understanding word definition. Thanks to gnomon in #concatenative for his help in straightening me out. Further updates are a result of the kind folks on #concatenative reading this and correcting me.

Reading SICP in Ruby: 1.1.4

Recently, I posted about reading and working through SICP in languages other than scheme. Today is the day that I start. I don’t know how quickly I’ll work through things, but we’ll see what I can do. In addition to Ruby, I’m also hoping to work with Factor and Erlang in parallel.

My first SICP post is nice and easy, I’m skipping up to Section 1.1.4 of SICP which covers compound procedures (procedures made up of other procedures). This is really the heart of concatenative programming (like forth and factor) and of the style of short method OO espoused be Martin Fowler in Refactoring.

Sussman starts out by defining a procedure to square a number, then another that uses the new square procedure to create a sum-of-squares procdure. In Ruby, this would look something like this:

def square(num)
  num * num
end

def sum_of_squares(num1, num2)
  square(num1) + square(num2)
end

If I type these definitions into irb and then try running them, I get the following:

 sum_of_squares(3,4)
 => 25
 sum_of_squares(3.0,4.0)
 => 25.0
 sum_of_squares(3.0,4)
 => 25.0

Just what you’d expect.

Next up, section 1.1.6 (Conditional Expressions and Predicates)

Reading SICP

I’ve had a long standing goal to read SICP, but it keeps conflicting with other goals, like mastering Ruby or learning Erlang (to name a couple of geeky ones). Recently I learned of a project to ‘translate’ SICP into Erlang (and other languages).

“Great! I can use this to help with both learning Erlang and reading SICP”, I thought and went to take a look at it. It turns out they also have a Ruby translation underway, so I went to look at that first. It turns out that the first couple of examples make me think that they either don’t understand Ruby or don’t understand SICP.

Page 5 of SICP shows that you can start up a LISP or scheme interpreter and type in an expression and it will return that expression, like this:

 > 486
 486
 >

The site recommends the following Ruby puts 486, which is not quite right:

irb(main):001:0> puts 486
486
=> nil
irb(main):002:0>

You see, this prints 486, but returns nil. A much better answer looks a lot more like scheme:

irb(main):002:0> 486
=> 486
irb(main):003:0>

With a problem like this early on, I’m not sure that I trust the Erlang or other translations. I do like the idea though, so I should probably stick with my idea of combining the ideas, and just post my own translations (and let everyone else find my mistakes).