Lambda the Ultimate

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"). :-)

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

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

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.

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

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

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.

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.

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

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

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