So, Lua optimizes tail recursion calls.

At first glance, this is no big deal. Very few recursive functions are tail recursive, that is, have the recursive call as the very last thing in the function, at first glance.

Consider the recursive factorial, for a real easy example.

function fact_1(num)
   if num <= 1 then
      return 1
   else
      return num * fact_1 (num - 1)
   end
end

While it looks like the recursive call is the last thing in the function, it really isn’t. The multiplication of num and the result of the result of the recursive call is the last thing done in the function, so this isn’t tail recursion.

But it can be “easily” turned into a function that is tail recursive. I quote “easily” since the first two or three or ten times you see the “easy” translation, you may not believe it, or at least may not believe it’s really easier. (I had students who figured it out the first time and others who took a lot more tries.  A lot more.)

What you have to do is carry the result with you down into the recursion. You’ll update the solution as you go, so that when you finally get to the base case, you’ll have the result ready to return. As the last step of the function. Thus, tail recursion. Code to do this is:

function fact_2 (num, result)
   if num <= 1 then
      return result
   else
      return fact_2 (num - 1, result * num)
   end
end

The only thing left to do is to rewrite the main factorial function to use this tail recursive version:

function factorial (num)
   return fact_2(num, 1)
end

Does it really matter? Does Lua really optimize tail recursion?

I tried the following non-tail recursive code and could compute up to 19,997 before getting a stack overflow error.

function sum_badly(max)
   if max <= 1 then
      return max
   end
   local other_sum = sum_badly(max - 1)
   return other_sum + max
end

And sure enough, the tail recursive version below allowed me to go to at least 100,000,000, so I’m convinced Lua does optimize tail recursion.

function sum_well_helper(max, current)
   if max < 1 then
      return current
   else
      return sum_well_helper(max -1, current + max)
   end
end

function sum_well(max)
   return sum_well_helper(max, 0)
end

The code is in my GitHub account if you want to see for yourself. The solutions to the Day 1 problems are also there.

That’s enough of Day 1 for now. Onto to tables.

So, sorry profs who might use this book as a text. I’m going to post my solutions to the book’s problems here and/or on GitHub. (Of course, that might just be an empty set, now that I’m no longer teaching, so I’m probably not bothering many people. It’s a pity; this is an excellent book for students to work through.)

First, so I don’t have to look it up again…one of the things I asked students to do in their “Get Acquainted” assignments for each language was to figure out how to enter code in a file and then use it in the REPL. Since I’m doing functions now and it’s a pain to retype functions each time I change them, now is the time to figure that out. And Lua continues to be different from other languages. To read the file samples.lua into the REPL, use the line:

assert(loadfile('sample.lua'))()

Okay. Good thing the REPL lets me arrow up to repeat commands. That’s a bunch of typing (more than any of the Seven Languages, I think).

Function Basics

Function syntax is unsurprising and makes me happy once again I know Pascal. The first exercise asks us to write a function that will return whether or not the last digit of a number (when expressed in base 10) is 3. If I take negative values into account, a solution looks like:

function ends_in_3(num)
   return math.abs(num) % 10 == 3
end

You can return two values (or more) as shown in the function that computes the roots of ax^2 + bx + c:

function get_roots (a, b, c)
	if b^2 - 4 * a * c < 0 then
		return
	elseif b^2 - 4 * a * c > 0 then
		local root1 = (-b + math.sqrt(b^2 - 4 * a * c)) / (2 * a)
		local root2 = (-b - math.sqrt(b^2 - 4 * a * c)) / (2 * a)
		return root1, root2
	else
		return (-b + math.sqrt(b^2 - 4 * a * c)) / (2 * a)
	end
end

Along with showing how to return 0, 1, or 2 values, the code above illustrates how to create local variables. By default, variables “declared” in functions in Lua are global. If you don’t want to type this all in yourself, take a look at the function set_some_stuff in my GitHub account.

Closures

Since functions are first class items, they can be returned by other functions. So you can build a function to multiply by a given value with:

function build_multiplier(factor)
	f = function (val)
		return val * factor
	end
	return f
end

Then create a couple of functions that do multiplication:

times_3 = build_multiplier (3)
times_8 = build_multiplier (8)

And, sure enough, that non-local variable factor in the function that’s built gets assigned the correct thing, each time. So

print ("4 times 3 is "..times_3(4))

prints

4 times 3 is 12

and

print ("4 times 8 is "..times_8(4))

prints

4 times 8 is 32

Finishing Day 1

There’s a bit more in the book about functions at this point, including how you can “fake” named parameter passing and have variable number of parameters. Both of these take tables, which is the big area of focus for Day 2, so I’ll skip them for now.

I’ve got a big example working that convinces me that there really is optimization of tail recursion in Lua. Convincing anyone else will take a bit more space than I’m willing to use now, so, like the author, I’ll make it a side bar and give it its own post. (If you’re really anxious, it’s in my GitHub repo now.)

For my final words on Day 1, let me quote Bruce Tate, the author, since he did a pretty good job of reading my mind at this point:

At this point, you’re probably thinking Lua is an easy-to-use scripting language, but with nothing particular to make it stand out in a crowd. That was certainly my first reaction when I encountered the language.

Yep. I definitely agree with this. Let’s hope I can agree with his next line as well:

Then I ran into Lua’s killer feature that makes its expressiveness possible: tables.

The Call to Adventure

So, it’s good I played a little with Lua as I was installing it, because the first day’s material is just not that inspiring. The big problem presented is that CSV files have some problems. Specifically, there’s no way in CSV to indicate constraints or collections. Okay, fine. That’s not really what CSV is all about. But apparently this should be enough to motivate me to keep going. Meh. It’s good I was motivated to begin with. (Like, what about XML?)

The description of Lua as a table-based language that can easily adjust to different paradigms holds lots of promise. That one of these paradigms can be the prototype paradigm is even more interesting. In Seven Languages, the only prototype language was Io and it’s fallen from popularity. When I last taught it, students poked around and realized there had been no activity on the Io community for months. (JavaScript is also a prototype language, but there’s a lot of other baggage with JavaScript.) The book doesn’t get to tables until the second day though, so enough said, for now.

From the first day, the most I can say is that Lua is a fairly typical scripting language so far. The REPL (Read-Eval-Print Loop) is a bit unusual in that you can’t just type:

2015

and get the result

2015

Instead, you need to explicitly indicate you want Lua to evaluate an expression, as in:

=2015

or you need to indicate you want that value to be returned, as in:

return 2015

I’ve also been doing a lot of Python recently, so the fact that Lua is not at all line-based is a nice change. You want to enter two commands over three lines like:

print
"Hello" print
" world"

Yeah, sure, go for it.

Lua is implemented using a “strict subset of ANSI C” (umm, quotes, yeah, they come from “Seven More Languages in Seven Weeks” unless otherwise indicated). It just uses floating point for all numbers, but does allow for the % operator. And it does something sorta reasonable when you use % and floating point numbers. 13.2 % 4 is 1.2 and 14 % 3.3 is 0.8 . (Let’s not think about negative numbers now, okay?)

There’s also exponentiation and it uses the correct precedence: 2 ^ 3 ^ 2 is 512, not 64. Expressions are otherwise unremarkable.

Booleans have the literals true and false and use real words instead of symbols (and, or, not). As I fussed about before, not equals is ~= . Only numbers and strings can be compared (and strings can only be compared to strings, numbers to numbers, not of this 42 < “43” stuff.) Strings can use single or double quotes. Use # before a string (or variable containing a string) to get its length. Use .. for concatenation. (And no, you can’t get the length of a number; I tried.)

Lua’s quite laid back about uninitialized variables and parameters. Try to print a variable that has no value and you get nil. Of course, it’s pickier if you try to use uninitialized variables in expressions. Combining this with multiple assignment leads to some interesting results:

x, y, z = 1, 2, 3

behaves as expected (if you expect x to get 1, y to get 2, and z to get 3). And

x, y, z = 1, 2

doesn’t complain, just sets z to nil (even if it had a value before). Finally,

x, y, z = 1, 2, 3, 4

just ignores that pesky extra 4 at the end.

Control structures are also fairly routine. They’re ended with end, so there’s no problem with dangling elses. The for loop makes the Pascal programmer in me happy:

for i = 1, 5 do
   print("i = " ..i)
end

And the loop control variable behaves nicely–it is reset to the “correct” value at the beginning of each loop. You can change it, but it gets changed back:

for i = 1, 5 do
   print("Before increment, i = " ..i)
   i = i + 1
   print("After increment, i = " ..i)
end

results in:

Before increment, i = 1
After increment, i = 2
Before increment, i = 2
After increment, i = 3
Before increment, i = 3
After increment, i = 4
Before increment, i = 4
After increment, i = 5
Before increment, i = 5
After increment, i = 6

Yay!

And i is nil after the loop. (Since I want to practice more with GitHub, I’ll be putting programs in the repository https://github.com/Annie29/7MoreLanguages . This is the first one out there.)

There’s also while and repeat loops (yes, repeat, like Wirth and God intended it, none of this do silliness!).

The author tosses off what I think is an important feature: Lua optimizes tail recursion. Now, tail recursion optimization was covered in detail in Seven Languages in Prolog, Clojure, Erlang, and Haskell, so maybe it’s just not that exciting. Maybe I’m prejudiced since I remember how hard it was for students to understand the benefits of tail recursion removal. But since I want to play with functions more before going on, especially since they’re first-class values and I’ve only recently grokked closure, and this has gotten long enough, so let’s hold that off until the next posting.

Before ever starting, y’all can hate me because I installed Lua for Windows. From a binary. Yes, I should build it for myself. And my computer does dual boot into Linux. Well, tough. That’s not what we’re here to do today. (Maybe when there’s “Seven Operating Systems in Seven Weeks?”)

(For those who don’t automatically think a binary build of Lua for Windows is a bad idea, you can find it at https://github.com/rjpcomputing/luaforwindows/releases .)

One nice thing about Lua for Windows is it comes with a really quick “tutorial.” Okay, it’s more like a bunch of examples, but it’s a fast way to see what Lua looks like.

Anyway, there are (at least) three syntax things that drive me crazy about programming languages:

• how to mark comments
• how to indicate “not equal”
• how to handle else if

So far, Lua does not disappoint. It does have single line double hyphen comments. Good, fine, I’ve seen those before in Ada. But ah, the multiline comment is a thing of Lua beauty.

--[[
Here's that multiline comment,
folks! ]]

Yeah. Hyphen, hyphen, square bracket, square bracket. Ended of course with two close square brackets. And no hyphens.

And the not equal is almost as much fun.

a ~= b

Tilde! And it doesn’t mean match. Dammit.

It makes the else if, elseif, downright disappointing.

But if I’d wanted more of the C/C++/Java/C# family, I wouldn’t be working through this book!

Along with the Seven More Languages book, the first edition of Programming in Lua is available on line (at http://www.lua.org/pil/contents.html), so I figured I’d read that as well. There’s a sample factorial program in the first chapter:

-- defines a factorial function
function fact (n)
   if n == 0 then
      return 1
   else
      return n * fact(n-1)
   end
end

print("enter a number:")
a = io.read("*number") -- read a number
print(fact(a))

I figured I’d try it out, so I entered it (okay, cut and pasted it) and ran it from the iExecutor that comes with the Windows version of Lua. And it failed. Damn, had the language changed so much since the first edition that this program no longer worked?

Poking around a bit, I realized that the problem was that the input line was not working. My first impulse was there had to be a typo. a = io.read("*number") ? Really? Surely the quotes didn’t belong there; it should be more C scanf-ish line: io.read(*number) and then we’ll use number in the next line.

Wrongo. The input line is in fact correct (and I realized again that Lua is going to be fun). The problem was iExecutor. While it did run code with no input just fine, there seem to be problems in reading input. As soon as I ran the program from the command line, it was just fine. Fortunately, Notepad++ does recognize Lua and it’s easy to run programs edited in Notepad++, so all is well.

I guess I should read more about iExecutor. But Lua seems like more fun for now.

or Laurie Lists Lotsa Languages Like Lua

So, when faced with a book like “Seven More Languages,” an obvious first question is “What are the seven more languages?” I was dismayed or delighted to realize I had no idea what any of them were:

• Lua
• Factor
• Elm
• Elixir
• Julia
• miniKanren
• Idris

This promises to be a fun adventure.

Of course, knowing a little about a language doesn’t take all of the adventure out of it. The first “Seven Languages” used the languages:

• Ruby
• Io
• Prolog
• Scala
• Erlang
• Clojure
• Haskell

At least there I had taught both Lisp (aka Clojure) and Prolog in AI classes, had taught lots of Java, so some of Scala wasn’t foreign, and had played with Ruby and Rails. Yeah, Io was, and remains, highly esoteric, but I’d heard of Haskell and Erlang and knew they’d be worth playing with. There is plenty of adventure to be had in these languages and the More Languages promises even more adventure.

There’s something in me that likes lists (Lisp and I are about the same age). So, I figured I’d pause before jumping into to Lua to make a couple more lists. Let’s start with the languages I learned first, as embarrassing as that may be since it starts with BASIC (and none of that Visual stuff either).

• BASIC, FORTRAN, and COBOL as an undergraduate
• Pascal in night school while in the Army (as a purely theoretical exercise, since the instructor never figured out the compiler for the TRS 80)
• IBM 380 Assembly, Lisp, Ada, and Modula-2 in grad school

Then I started teaching and added:

• C++
• 68000 Assembly
• Java
• Visual Basic
• C#
• Perl
• Python
• Tcl/Tk

Presenting in GDG meetings added

• Go
• Dart
• JavaScript and HTML

Working with K12 programs included

• Greenfoot
• Jeroo (a personal favorite)
• Scratch and Squeak (and BYOB, Snap, and Blockly)
• Alice
• Karel
• Lightbot
• Robocode
• Pivot
• Processing

I did a little Smalltalk with the programming contest one year and some R as part of exploring big data. Should I count things like Bash, Awk, SQL, etc.? Nope, I don’t think so.

Yes, C is missing. I can probably fake my way through C, but I decided it was too ugly to learn in my grad school programming language survey class. There were a bunch of us who each had a language and during a typical class, we’d hear from the C guy, the COBOL guy, the Pascal guy, the PL/I professor and the Ada gal. That was enough C for me. (But after teaching “C++” for engineering freshmen, I’d be hard pressed to tell you why I wasn’t teaching C.) I had a friend who majored in comparative lit in college and he decided to never read Hamlet. I’ve used him as inspiration any time I’ve thought I should know more C.

Instead, I should learn Lua, I do believe.

So, five years ago (really! that long ago?), I got tired of teaching the Programming Languages class out of Sebesta and decided to try something new. So, I used the book “Seven Languages in Seven Weeks” (https://pragprog.com/book/btlang/seven-languages-in-seven-weeks) as the course text.

It was, well, an experience.

Nevermind that the book that was due to be published on August 15 finally showed up in November. In fact, I counted that as a positive (in an “if life gives you lemons” way) since students got to experience how many professionals get their books on new topics with programs like Beta books, Early Release, and MEAPs. And we all liked the much lower price than traditional text books and PDF version that students could carry around easily.

But for years, I’ve been lectured about how lecture is the wrong way to teach classes (trust me, the irony was not lost on my, but seemed to be on the people lecturing me on not lecturing). You should be “the guide on the side” not the “sage on the stage.” And, despite my desire to learn as much as I could about these languages, all seven of them, I soon realized that the student questions and errors would far outstrip my knowledge of the languages. So, I really did become the guide and soon added an assignment where the class would get points for figuring out things I couldn’t. That made us all happy too–they got points and I didn’t have to figure things out.

What was particularly great about the book is that the languages were not your typically Java, C++, C#, C, blah, blah, but included some that really required new ways of thinking. Yes, some students still growl at me about Prolog 5 years later, but once you get it, Prolog is a bunch of fun. Really. Trust me.

And even better, the book didn’t just do “Hello World” in each of the languages. It focused on examples that demonstrated the different features of each language. When we were adding functions to the built in integer class in Ruby in the first week, students knew to hold on tight, it was gonna be an interesting ride. (Especially when you consider most of the class had never had any experience with scripting languages, so just simple Ruby and the REPL was a bit of a shock to the system.)

It was much like a white water rafting trip. I felt battered at the end, they were certainly battered, but if you like that kind of thing, it was a lot of fun. Still I rushed back to the safety (and cruise ship stability) of Sebesta the next year. Turns out, I shouldn’t have rushed for safety quite so fast.

In listening to the students who took the course at their exit interview much later, it was a great experience and the favorite class in the curriculum for a lot of them. They really appreciated the skills they developed in the class and the exposure to so many new ideas. They realized it would be sorta useful in their futures. (It doesn’t hurt that I had some fabulous students in that class either-yes, you Travis and Levi! And yes, you others who don’t live within 10 miles of me.) So I did it again (with a bit more guidance) in 2013 and had planned on doing it with the follow-up book (titled, duh, “Seven More Languages in Seven Weeks”, https://pragprog.com/book/7lang/seven-more-languages-in-seven-weeks). While I may have fooled some students into thinking working with a language that was not supported was a way to appreciate the support languages other than Io received, it was time to try something new.

But instead of teaching this fall, I’ll be doing something else. (Please don’t ask what or why without planning on offering a job interview or adult beverages.) And one of the many things I’ll miss is not having the chance to do seven more languages.

Still, as I was teaching from Seven Languages, I found the experience of others who blogged it) to be very useful. The work of Yevgeniy Brikman at http://www.ybrikman.com/writing/tags/#Seven%20Languages%20in%20Seven%20Weeks was especially useful. And since I still haven’t figured out what something else is going to be, it seemed like a good time for me to work through Seven More Languages on my own and record the experience here. It won’t be as useful an experience without students to ask questions I never would think of, but I do still carry a lot of student questions with me, so we’ll see what kind of trouble I can get into on my own.