SICP Translations

Being a slow news week (Ehud busy, chance for shameless plug, etc...), thought I'd take the opportunity to elevate the translation of SICP to the front page. Chapter 1 is mostly complete for Alice ML/SML-NJ, Oz, Haskell, O'Caml and Scala. Still a long way from done, though portions of Chapter 2 and 3 are there for Alice ML / SML-NJ.

Actually, the more interesting item I came across this week was in a visit to the Scala list. Seems that Martin Odersky has used many examples from SICP for a course on FP - specifically the Scala by Examples document. I knew I should've made Scala a higher priority - at minimum I can borrow ideas and learn Scala along the way.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Good job - long live diversity!

It's very good to see efforts like SICP translation and LiteratePrograms. Having equivalent code rendered in different programming languages will help people annoyed by language proliferation see through the syntactic differences. It can be hoped that it proves to be a useful step to understanding and teaching the essential code-structuring ideas these languages are based upon.

LiteratePrograms

Eventually, I'd like to get invoved in the LiteratePrograms project, which is novel in its approach to be an algorithm repository, language reference, and teaching/learning platform. Unfortunately, I'm much too terse (and lazy) to give a decent background explanation for the code. (or to put it differently, coding is easy - explaining what the code does and why is the hard part). :-)

There are a number of sites that give us a single problem solved in multiple languages (Hello World, 99 bottles, ROT13, Quine, OO Shapes, etc...). And there are sites that try to compare Syntax Across Languages. And there are sites that have multiple problems across multiple languages (PLEAC, PL Shootout, LiteratePrograms, etc...). I figure we could always use more of these for those that are interested in looking at expanding their PL range.

If I ever do get done with the SICP translations, I figure it will create a new category of "One Book, Many Languages". But that's a long way off (currently qualifying as "One Chapter, Many Languages"). :-)

hmm, i thought it was

hmm, i thought it was translation to other (human) languages. I myself began one to portuguese, a few months ago, based on the html version. I don't know if it would be much popular, but such a classic deserves it. I had almost completed chapter one, but it's halted as of now for lack of time. Eventually, i get there.

Can always use a wider audience

Lack of time always seems to be the fundamental constraint to getting anything useful done. :-)

A JavaScript question

Python, Ruby and JavaScript translations of chapter #1 were added. I have a question about JavaScript though. The compiler seems to go through a 2 stage process, first compiling the functions and then sequentially going through the code. The following produces the anamoly:

// The following will print "second" two times
function fg() { return "first"; }
print(fg());
function fg() { return "second"; }
print(fg());

I'm wondering why JavaScript has this behavior? And what name/terminology one would use to describe it? And whether this is just unique to the script being embedded in the browser?

Not unique

Perl does this too, because "sub f {...}" assigns to "f" at compile time:

sub f { 1 }
BEGIN { print "begin ", f }
print "1 ", f;
sub f { 2 }
print "2 ", f;

sub g;
*g = sub { 1 };
# "Undefined subroutine 'g'":
BEGIN { eval { print "begin ", g } }
print "3 ", g;
*g = sub { 2 };
print "4 ", g

Evaluating definitions first

It's not unique to being embedded in the browser. The Spidermonkey Javascript interpreter does the same thing if you feed it a file containing that code.

You can get the results you want with:

function fg() { return "first"; }
print(fg());
fg = function () { return "second"; }
print(fg());

(You could use "var fg = ..." to define the first instance of the function, too.)

The advantage of treating named function definitions specially is that you don't need forward declarations. This allows you to e.g. write top-level code followed by the functions it depends on. This can be useful in typical scripting environments, where code reuse may be being done by file inclusion, which can create messy dependency problems otherwise.

Lua?

BTW, an interesting alternative to the quirky implementations in Python and Ruby might be Lua, which from what I've seen should be more Right Thingish when it comes to lambdas, lexical scoping and so on. I'm not volunteering, though. :)

Lua added

Is much cleaner, though I couldn't figure out how to do a simple let binding (that is an expression) along. Faked by wrapping it in a function. Also haven't quite figured out when variables need to be declared local - though on the surface it seems sensible.

[Edit Note: meant as reply to Anton]

Your Lua code lacks local declarations

In Lua, any unbound variable is implicitly global, which means that it is a key in the current function environment.

Also, the function statement is simply syntactic sugar for an assignment statement:

function square(x) return x^2 end

is the same as:

square = function(x) return x^2 end

and

local function square(x) return x^2 end

is the same as:

local square; square = function(x) return x^2 end

There is no let construct, so the idiom of wrapping the thunk in a function of no arguments and calling it is correct idiomatic Lua, although it's uncommon; a more usual way of doing it is to put the interior scope inside a do ... end block.

Since all unbound variables are global, many of your examples pollute the global namespace (that is, in the current function environment). So, for example, it would be better to write the following:


-- Block-structured
function sqrt(x)
   local function good_enough(guess, x)
      return abs(square(guess) - x) < 0.001
   end

   local function improve(guess, x)
      return average(guess, x / guess)
   end

   local function sqrt_iter(guess, x)
      if (good_enough(guess, x)) then
         return guess
      else
         return sqrt_iter(improve(guess, x), x)
      end
   end

   return sqrt_iter(1.0, x)
end

I think I've got it cleaned up now

Thanks for the explanations and corrections.

[Edit Note]

I guess I should add that it was nice having the example of:

print (integral(cube, 0.0, 1.0, 0.001))

work after having seen the "too much recursion" errors in Python, Ruby and JavaScript. Of course, this is owing to the fact that Lua has TCO and the others don't (at least not on the versions I'm working with).

A question on lists in Lua

Well, I ain't gonna get very far into chapter 2 in Lua if I can't figure out how Lua does lists: [1,4,5] etc... The Table dictionaries are lookup based. I'm guessing I could use arrays, and build up cons, car, and cdr routines around them. But before doing that, thought I'd ask what the idiomatic version would be in Lua? Perhaps I'm missing something even more obvious?

Thanks.

Lua uses tables instead of lists

Of course, that changes the way you write programs. For example, the most efficient way of extending a list is at the front, while the most efficient way of extending an array is at the end. Furthermore, immutable pairs offer possibilities that mutable tables don't (and vice versa). Nonetheless, it is common to represent lists as arrays (that is, tables whose keys are consecutive positive integers).

If you want to simply reproduce Scheme examples, it is trivial to define a cons type as a table:

function cons(h, t) return {head = h, tail = t} end

You could use car and cdr instead of head and tail although I'm not sure what the pedagogical value is.

To make the construction of lists a little easier, we need a list constructor function; the following uses Lua 5.1 varargs, which are a bit different from previous versions, and constructs a temporary table which is then converted into a cons-list:


function list(...)
  local t = {...}
  local c = nil
  for i = #t, 1, -1 do
    c = cons(t[i], c)
  end
  return c
end

Another way of making cons cells is with functional closures, as per section 2.1.3. Since Lua allows multiple return values, an even simpler implementation is possible, where the cons cell returns both head and tail:


function cons(h, t)
  return function() return h, t end
end

function flip(x, y) return y, x end

-- The redundant () forces the return to be one value
function head(cell) return (cell()) end

function tail(cell) return (flip(cell())) end

On the whole, I don't think this is a very natural way to program in Lua. It would be more natural to implement make-rat (and friends) directly as tables:


function Rational(n, d) return {numer = n, denom = d} end

function addrat(x, y)
  return Rational(x.numer*y.denom + y.numer*x.denom, x.denom*y.denom)
end

-- etc.

I didn't define a functional interface to get the numerator and denominator, because I normally wouldn't in Lua. It is possible to use metamethods to create tables with what are now, I believe, commonly referred to as "properties" -- i.e. computed field accessors and mutators -- and the field access syntax seems more natural to me. Obviously, it would be trivial to define the functions if desired.

The challenge...

...is to make the code not look too much like Scheme embedded inside the Lua code. I'll probably go with a naive translation first (much as I did with Python and Ruby), and worry about an efficient solution afterwards.

Thanks for the help.

Thanks

Thanks for the Lua. It's interesting to see the issues that come up in these languages, especially since I lean towards the "I can write lambda calculus in any language" school of thought, and am constantly disappointed by the seemingly silly little things that get in the way of that.

Erlang addition of chapter #1.

Alice ML is the main language I'm trying to translate. I got stuck on section 2.5 (generic operations) a while back, and now I'm stuck on Section 3.3.5 (constraints). Alice has a nice constraint system (Gecode), but I really need to figure out the Scheme code there.

Anyhow, when I get stuck on Alice ML, I have the bad habit of branching out into another language, hoping to find some insight. Latest addition is Erlang which some might find of interest.

(William Neumann has also done some work on chapter 3 in O'Caml that has helped me along on the Alice side).

E Tu

Managed a bit more work on the sicp translation. E was added to the mix. And the Python and Ruby translations for chapter 2 were modified with a more efficient use of lists (using chains rather than the built in vector list type).

Translation updates

Just a status update to say that a little more work has been done on the SICP Translations. I managed to work through most of the first three chapters in Oz, while Anthony Borla has graciously donated translations for Dylan.

In addition to the SICP translations, I also worked through major parts of the five books in the Little Series of Friedman and Felleisen - "The Little Schemer", "The Seasoned Schemer", "A Little Java, A Few Patterns", "The Little MLer" and "The Reasoned Schemer". I've still not posted the bulk of the Oz code to the wiki, but the TRS Translation has a link to a zip file of the translated Oz code near the bottom for anyone interested in the results.

Thanks

for all your work, it has been very helpful whenever i get the gumption to try to learn new langs!