Play With Lua!

Or, how to annihilate an interview question. I was asked this a little over a year ago in an interview, and I'd been asked it a few times before then too; it's pretty common.

"Write a function that takes a parameter n and returns the nth Fibonacci number." The Fibonacci sequence, if you don't already know, is defined like this: f(1) and f(2) are both 1. After that, each number in the sequence is the sum of the previous two, so, f(3) is 2 (because 1+1), then f(4) is 3, then f(5) is 5, and so on.

This is part four of my series on writing a toy programming language using LPeg. You should start with part one here.

Last time, we used the new AST generation to make conditionals and loops. Now, we're going to add the ability to define functions, complete with lexical scoping.

This is part three of my series on writing a toy programming language using LPeg. You should start with part one here.

Last time, we added variables and arrays to the language. Assigning to arrays was starting to strain our design some, so this time we'll refactor it a lot, and add two features that would be impossible without that refactoring: conditional statements and loops.

This is part two of my series on writing a toy programming language using LPeg. You should first read part one here.

Last time, we made an interpreter for a simple calculator: it would read in mathematical expressions and evaluate them, printing the result. This time, we're going to add two new features: variables and arrays. First though, we'll refactor our parser some.

In this post, and the following posts in this series, I aim to fix something that's bothered me for a while: writing a parser in Lua isn't very approachable. In C you have the excellent chapter in The Unix Programming Environment (probably the best book on programming ever written) about how to use Lex and Yacc. For Ruby there's the excellent Dhaka gem, as well as Racc, both of which work a lot like Yacc / Bison. There's also Antlr, which seems to speak to every language except Lua.

Meanwhile Lua has LPeg, which is used nothing like Yacc, and tutorials are thin on the ground. So, I want to change that. This is going to be about how to make a toy programming language in Lua, in three parts. I'm going to loosely follow what the Lex / Yacc chapters of The Unix Programming Environment do, and we'll end up with the same language.

Let's begin.

I don't think it'll surprise anyone when I say that I think Lua is a great language. But, it does have a very small standard library. So, there are a few other utilities that I end up including or writing in almost everything I do. Luckily, Lua has a facility for loading them automatically when I open up the REPL.

Lua doesn't have a lot of control structures. There's the obvious if statement, the while loop and repeat/until loop, and the for loop. Mostly, the for gets used to iterate over tables:

t = {'a','b','c','d','e'}

for i, v in ipairs(t) do
  print(i,t)
end

It's annoying to have to remember to type ipairs every time. I've forgotten more than once. But, that minor annoyance is a good trade for the benefit of what the for statement actually does: generic iteration.

A few days ago at work, a friend of mine came up with this problem. I call it the "telegram" problem: you get a string consisting of words run together without spaces, and figure out where spaces can go to separate out the words. For example, a famous misunderstanding:

parse_telegram("turkeytrotstowaterwhereistaskforcethirtyfourtheworldwonders")
-- turkey trots to water where is task force thirty four the world wonders

I wrote a solution last night.

Player movement is really hard to get right. It seems like it wouldn't be, like it's just as simple as "if the left arrow key is down, move to the left", but it's actually surprisingly difficult. Feel is really important. Try playing Mario 2: each character plays the same levels with the same enemies and the same rules, but because they have their movement tweaked differently they play totally differently. Luigi can jump the farthest but has a lot of inertia for changing direction mid-jump, for example. It's something you can tweak indefinitely.

In this post, and probably the next one, I'm going to walk through one way to do it for a top-down (Zelda-like) game in Löve, that feels "right" to me. This isn't going to touch on code organization at all, or how to start using Löve (there are other posts about that already), it's just going to be an explanation of what I have figured out over the past couple weeks of poking at this. So, let's start with some basics:

I've been doing a lot of writing games in Löve. Writing games usually involves a lot of code that deals with positions and directions and velocities. To make this easier to write, I made a little library to represent a point in a two-dimensional coordinate space.

This is a little different for posts here because I'm not going to go into the code too much; I'm just going to show some examples of how to use it. Really, the motivation here is that I want to make other posts with code examples that use this, and so I should document it. Next up, my "map" class.

If you just want the code, the canonical repository is here.

Another short post. It's because I'm working on something.

A lot of languages have a ternary operator, that lets you do this:

int x = foo ? 1 : 2;

It's an easy way to pack a conditional on to one line, especially useful when giving things default values. Another way is if the if statement returns a value, like in Ruby:

x = if foo
        1
    else
        2
    end

Short one this time:

print( string.char( 0xe2, 0x98, 0x83 ) )

If you have a console that supports UTF-8, you'll see a barely recognizable glyph of a snowman. If you don't, here's what you're missing.

(happens to be my second-favorite website of all time, behind this one)

The handiness of this for roguelike development is plain. There's a good character list (with hex codes) here.

If you, like me, are writing a text-mode Roguelike game in Lua, you'll probably be interested in the thing I just published: a small Lua library for coloring text output to the console.

It lets you do things like this:

print(color.bg.green .. color.fg.RED .. "This is bright red on green")

Couldn't be simpler. Enjoy!

I've wanted to do a small case study of making an extension for a long time now. I'm writing a Roguelike game in Lua, so I had a need for one, and knocked it together last night: a C extension to provide Lua with a function to read one key from the keyboard.

In a few hours, on the 18th of January, a lot of sites are going to "go dark" to protest SOPA, the latest in a series of draconian, badly-thought-out laws to regulate the internet and computing in general. This is probably old news to you, and I'm going to spare you another explanation of why this particular bill is so bad. Instead, I want to talk about in general, why programming knowledge is so strongly correlated with getting upset about things like this. It's kind of a long story, and it starts in ancient Greece.

For what it's worth, this site won't go dark. I think it's more important to leave it up so you can read this post.

So you have made a program in Lua. You want to give it to people to run. You run into two problems right away: one, you don't want to require people to install Lua to run your program, and two, you may not want them to have your source code (if it's a commercial program). So, what to do?

If we were in a language like C, we could precompile our program into a binary and distribute that. So, since Lua can very closely integrate with C, can we do that with Lua? The answer turns out to be "yes".

I am spending the time making a presentation on ZeroMQ for the Lone Star Ruby Conference.

I thought of this today, and I thought it might make an interesting short post. One of the small annoyances of Lua is that it doesn't have a lot of convenient support for arrays. You can implement arrays with tables, of course, but they're still tables: they don't have default metatables (so you can't do things like join), they don't pretty-print (so it's a hassle to see what you have), and there's still only one iterator (using ipairs with a for loop). You can do it but it's not exactly convenient. So I started thinking about how exactly I'd add all that stuff.

I'm not an expert on Lua. I've been using it for less than a year; most of the time before that I wrote Ruby, JavaScript, Scheme, etc. It's not a terribly large language. I usually tell people that if they know JavaScript they can learn Lua in a weekend, and that's true as far as the syntax goes. But, there are several Lua idioms that are either complicated or just not explained well, and one of those is modules. You can get a long way coding in Lua without ever using a module, but eventually you'll want to know how they work.

I'm going to explain what modules are for, how to use them, and most importantly why they work that way, and I'm going to do that by implementing Lua's module system myself. Let's begin:

This is an adaptation of a chapter from The New Turing Omnibus, a great little tour of a few dozen areas of CS. This is about a way to compress a bitmap, to store it without storing each individual pixel.

The technique is called a quadtree. We're going to split a bitmap up into four equally-sized chunks, then compress and store those. The savings comes from the fact that we aren't going to store equivalent chunks twice.

When we left off last week, we had part of a game. It would display a board, and we could rotate it left or right. It would even animate, which was cool, but already our code was starting to get complex, so we were probably going about things the wrong way.

The issue is that we need to start an animation, then return from the function so that Löve can actually show the animation. But, the animation isn't the entire turn; we have more game logic that needs to run after it finishes.

Currently, the only way to find out when something finishes is by checking for it in love.update, right? So we can make this game by making something like this:

In part one of this post, I walked through the logic and game rules of a puzzle game, written in functional style. This time I'm going to turn that into a real game, that you can give to people to play: it will have graphics, animations, and run without installing Lua or any other dependencies.

I'm going to do this by using a game framework called Löve. I don't want this blog to turn into library-of-the-week, but it's impossible to do this stuff in a blog entry without using some framework, and Löve is a good one: it's free and open-source, works on all three platforms, and its "Hello, World" is under five lines. So let's download it and put some game rules into it!

You know how if you have a box of little square things, and you rotate it, all the pieces thunk to the bottom and it's kinda satisfying? Even more so if all the pieces are (say) dice, and they make a neat stack when they hit. That was my inspiration when I decided to make a puzzle game the other day. In this game, you have a square board partially full of colored pieces, and each turn you can rotate it ninety degrees either left or right, and all the pieces fall to the bottom. The pieces are four different colors, and there are four special pieces (one of each color) that are crushers. A crusher landing on top of a piece of its color will crush that piece and shift down one square.

What I'm going to do is talk about the design of the game and how I implemented the rules in this post, and then how I wrote the graphics and interface code in the next post. The post after that will have the final version of the game, with some explanation about how to organize code like this. But first, let's write the game rules.

There's a book I have, Beautiful Code, which is a bunch of essays about programming by various famous programmers. It's a great book. The chapters are on all different topics; the only thing they have in common is a piece of code that makes you think "wow, that's really clever". This post is about chapter one of that book, which is about a regular expression matcher.

Regular expressions are a domain-specific language for describing finite state machines. Specifically, finite state machines where the state transitions are successive characters in a string: you can use them to check if input strings match certain formats, like, a phone number: three digits followed by a dash followed by four digits. Kernighan's matcher, which I'm going to translate to Lua and then extend a little bit, is really compact and beautiful. It's about thirty lines, and recognizes these tokens:

• A dot (".") matches any single character

• A caret ("^") matches the beginning of the string

• A dollar sign ("$") matches the end of the string

• A star ("*") matches zero or more repetitions of the previous token

• Any other character (like "a") matches itself.

My plan is first to duplicate Kernighan's matcher in Lua and then extend it to also handle character sets, like "[abc]" would match a single "a", "b", or "c". Because of this, I'm not going to port his code across directly, but rather make some changes for extensibility.

I decided to clean up and refactor the code some from part one, although it still works the same way: we still have behaviors that various objects can become. I'm not going to go through every part of the code, but I will talk about how behaviors are designed, explain the parser, how commands are handled, and how a prop (the lamp) is implemented.

Behaviors

First, here's how you create a behavior:

Something = behavior()
function Something.methods.whatever(self) ... end

Like it or hate it, and there are plenty of reasons to do both, object-oriented programming is an idea that you can't escape. Practically every language and every library uses it. Every CS curriculum teaches it. Every learn-to-program tutorial explains it. And so, people have some funny ideas about what it exactly is. If your first language supports it (like Java or Ruby, say) then it becomes very hard to distinguish between object-oriented programming and how your language does object-oriented programming.

Unless you're using Lua. Because OO in Lua is whatever you write for it. The language doesn't offer any of what a Java programmer would consider essential features, like classes, instance variables, even types. What it offers is a way to make those things. So that's what I'm going to do over the next couple posts, in the process of writing a miniature interactive fiction engine. At the end it'll look a little bit like this except that I'm going to make a bunch of compromises that Zarf never would, because he's smarter than I am and can foresee how it'll mess everything up. Also because he intends to use his for longer than a blog post.

This is a problem in The Art of Computer Programming volume 4A, which only came out a few months ago. My solution isn't Knuth's solution, mostly because I don't understand Knuth's solution, but it works and it's fairly easy to explain.

The problem is this: given a number of nodes (like, say, 4), generate every possible arrangement of those nodes into a tree. So this is one:

() () () ()

This is another one:

() () (())

And so on. For n nodes there are 2^n-1 possible trees. And it's not immediately obvious how to generate them.

Lua is a pretty much ideal language for playing around with map generating functions. I made a cute one today, combining linear noise with a couple other things.

To start off with, here's how I create a Lua map class: I start by making a "Map" table that contains a "methods" table. Anything class-level (what Java would call "static") goes in Map; anything instance-level goes is Map.methods. I make a Map.new function that creates a new Map of a certain size, filling it with either a constant value or linear noise (I'm using 16 elevation levels):

Map = {methods={}}

-- Make a grid of random values 0..15, or a fill value
function Map.new(width, height, fill)
   local map = {width=width, height=height}
   setmetatable(map,{__index=Map.methods})

   for n = 1, (width * height) do
      map[n] = fill or (math.random(16) - 1)
   end

   return map
end

Pretty basic so far. I'll add a few methods like at and set that change values based on x and y coordinates.

Lua is designed for embedding into larger host programs. Last time I talked about how to make C functions available to Lua, now I want to talk about how to bundle Lua libraries in with your host program.

First, we have to understand what it means to load a library. Most Lua libraries are packaged into modules (which I'll get into later), one module per file. You call require and pass it a module name, and it returns the module (usually as a table containing some functions).

Notably, you're not passing a file name to require, you're passing a module name. The fact that these modules map to files is just sort of coincidence. In actuality, require looks in several different places (locations on package.path, C libraries on package.cpath, and so on) for a function that will evaluate to the module.

A function that evaluates to a module is called a loader. Searchers try to find loaders, so there's a searcher that looks in files and returns functions that call dofile on them, for example. Each searcher that Lua uses is stored in the confusingly-named package.loaders, so one way to find this would be to add a searcher that will look for a particularly-named function (exposed from C) and call it, like if I try to load "foo" that means try to call "load_foo_from_c()".

But, even before it starts calling searchers, it checks if you've provided a loader for that module by hand. You can do that by putting it in a table, package.preload. If you only want one module this is much easier to do.

I wanted to write something about Lua's C interface, but I couldn't think of anything good and self-contained with my Cocoa Lua stuff (part of the point of using notifications is that I don't have to do much C interface stuff) so I figured, I'll write a tiny tile-based map thing.

Let's say you want to write a game in Lua, and you want to have a really gigantic map. Storing it as a Lua table would be a little unwieldy, especially if you want to do things like run functions over it for map generation (fractal map generation, smoothing, whatever). It would be really nice to write that in C and have some basic functions in Lua to access it. So, we're going to write a function that creates a map of a certain size, and another one that returns (as a table) a rectangular "slice" of the map:

map = Map.create(256, 256)
Map.slice(map, 256, 100, 100, 15, 15) -- map_width, x, y, width, height

Last week I talked about how to use Cocoa notifications to connect a Lua environment to a Cocoa UI. This is great for things like this:

When the user clicks a space on the map containing a unit, update the status panel with the specs for that unit

But terrible for things like this:

When the user clicks OK, load the next level out of the level file and send it to a Lua function for pre-processing

Things like that are even more common than the first type, but result in terrible code. What to do?

This is less a "cool Lua trick" and more a "cool way to use Lua". What I'm doing is using Lua to write a Cocoa application. There are a couple tools to do this (Wax and LuaCore spring to mind) but they work on a different paradigm: they're like RubyCocoa in that they have a bridge where you can write Lua code that makes Cocoa objects, and write your whole app in Lua. I don't want to do that because I don't want to get in a race with Apple. Cocoa has a pretty good Objective C interface, including stuff like blocks and Interface Builder and CoreAnimation, and I'm perfectly happy to use it. I would just prefer to write the parts of my program that aren't tied to Cocoa objects in something a little more terse.

Lua, like most languages, has some object-oriented pieces. But, it doesn't have classes and modules and objects: it takes the Scheme approach and gives you the tools you need to build the OO paradigm you want to use. In particular, the only data structure it gives you is called a table and is essentially a hashtable married to an array (it's a hashtable, but it has accelerated access for integer keys, so it's efficient to use for either one). Tables can be assigned metatables which define special behavior for the table: if you try to access a key that doesn't exist, it looks in the metatable for "__index" and uses that to find what the value should be.

But if all that was intended was to make it easy to duplicate class-based OO, Lua would just have put in class-based OO, right? Let's try something different, that uses this same trick to do something cool. Let's make Lua look like Prolog.