Monday, October 08, 2007

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”.

12 comments:

Anonymous said...

I think I'd approach the Erlang slightly differently. Particularly, while finding the greatest two values from a list *can* be done via sorting, it doesn't *need* sorting. Try the following definition of last_two/1:

last_two([], A, B) ->
[A, B];

last_two([H|T], nil, _) ->
last_two(T, H, A);

last_two([H|T], A, _) when H > A ->
last_two(T, H, A);

last_two([H|T], A, nil) ->
last_two(T, A, H);

last_two([H|T], A, B) when H > B ->
last_two(T, A, H);

last_two([_|T], A, B) ->
last_two(T, A, B).

last_two(A) ->
last_two(A, nil, nil).

(sorry about the formatting; couldn't figure out how to make <pre> style formatting)

Anonymous said...

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 said...

I'm just getting started with Erlang myself, but how about:

sq(X) -> X*X.

max(X,Y) when X > Y -> X;
max(_X,Y) -> Y.

sumsq(A,B,C) when A > B -> sq(A) + sq(max(B,C));
sumsq(A,B,C) -> sq(B) + sq(max(A,C)).

AkitaOnRails said...

Your first example would be better written off as:

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

Boyd Adamson said...

I'm just learning Erlang too, but wouldn't this be more idiomatic?:

abs(A) when (A<0) -> -A;
abs(A) -> A.

Anonymous said...

In Erlang, how about:

f(A,B,C) when A>B; B>C -> A*A + B*B;
f(A,B,C) -> f(B,C,A).

Anonymous said...

I made a mistake, I meant:

f(A,B,C) when A>C, B>C -> A*A + B*B;
f(A,B,C) -> f(B,C,A).

Anonymous said...

Anonymous, that looks like a clever way of doing it, but what happens in the case when A == B == C? That will cause it to recurse for a while, no? :-)

Anonymous said...

Hehe, I just wrote exactly the same code as Fabio Akita and was about to post. I was just intrigued as to why you wouldn't use idiomatic Ruby, when SICP tends to use Scheme very idiomatically.

Anonymous said...

You're missing the point of exercise 1.3. You can solve it very simply without lists or sorting:

(define (largest-two a b c)
(if (and (>= c a) (>= b a))
(+ (* b b) (* c c))
(largest-two b c a)))

I won't bother to translate it in to any other languages, because it would be basically the same.

Anonymous said...

(define (sq a) (* a a))
(define (min a b) (if (< a b) a b))
(define (sumsq a b c)
  (- (+ (sq a) (sq b) (sq c))
    (sq (min (min a b) c))))

Anonymous said...

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.