Other Language Tutorials

Welcome to Dream.In.Code
	Become an Expert! Join 307,089 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 2,072 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a Expert

Advanced Lua - Part I

Advanced Lua - Part I, Closures and Tail Calls

Options

KYA

19 Aug, 2009 - 03:12 PM

Post #1

Advanced Lua - Part I

Prerequisites:

This tutorial assumes you have some basic programming knoweldge (i.e. I won't explain what a variable/function is) and have a solid understanding of the fundamentals of Lua. If you need a brush up see The Introduction to Lua series (Parts I, II, III, and IV). Let's get started!

Closures

As noted in a previous tutorial, a function inside of another function has full access to the local variables of the enclosing function. As you may remember this is called lexical scoping. Also, functions are first class values, meaning that they have the same abilities, features, and possible behavior of variables (i.e. numbers and strings). With these two combined, we (the programmers) are allowed powerful access to features many other programming languages do not support. In a manner, we are transcending between traditional programming languages and functional programming languages. Example:

CODE

--a lead in example
--sort function
function sortGrades(names, grades)
table.sort(names,
    function(n1, n2)
        return grades[n1] > grades[n2]
    end)
end

--data
names = {"Knowles", "Joe", "Mary"}
grades = {Knowles = 100, Joe = 87, Mary = 96}

--unsorted table
for i,v in ipairs(names) do
    print(v)
end

sortGrades(names, grades)
print()
print()

--sorted table
for i,v in ipairs(names) do
    print(v)
end

The sort function (from the table ) is given an anonymous function.In this context, grades (when being accessed by the anonymous function) is neither a local, nor a global variable. Lua refers to these as non local variables (or upvalues). A snippet that will illustrate the point is one from an earlier tutorial when I briefly touched on closures:

CODE

function newCounter()
    local i = 0
    return function ()    -->anonymous function
        i = i + 1
        return i
    end
end

c1 = newCounter()
print(c1())                --1
print(c1())                --2
c2 = newCounter()
print(c2())                --1

Those with prior programming background will notice that the variable 'i' goes out of scope after the object is created. However, the anon function keeps to 'i' as a non local variable which is accessed later on when the object is called. A closure is essentially a function that keeps all the information it needs to function. Imagine putting a piece of paper into a briefcase. You may put the briefcase down, but the paper is still there. When you pick it up again, you can put another piece of paper in. Hopefully the metaphor looks as good in text as it sounded in my head.Keep in mind that closures and anonymous function are not the same. They are often used together (as in the above example), but are distinctly different.

Tail Calls

Another neat feature Lua has is tail-call elimination. A tail-call occurs when a function calls another as its last action:

CODE

function foo(x) return goo(x) end --tail call returning goo(x)

After calling function goo(), foo() has nothing left to do. It is evident that the program does not "have" to return to foo after executing goo() because there is nothing left except returning from foo(). The Lua interpreter takes advantage of this ability and will return control to right after where foo() was called once goo() finishes up. No extra stack space is needed, so a program can make as many tail calls as it wants:

CODE

--tail calling
function foo(n)
    if n > 1 then
        return foo(n-1)
    end
end

--This will never overflow the stack
print(foo(100000000))

Note that the program doesn't do anything, except return the function with the parameter-1. If anything is to be done with the results, it won't be a tail call. Examples:

CODE

function foo(n)
    if n > 1then
        return foo(n-1) +1   --addition, no tail call
    end
end

function foo(n)
    if n > 1 then
        return foo(n-1) * 5  --multiplication, no tail call
    end
end

function foo(n)
    if n > 1 then
        foo(n-1)  --no return statement, must discard results before returning
    end
end

As noted above, if there is anything that could require additional processing after the return, it will not be a tail call. Therefore, if not implemented correctly, one could overflow the stack with a large recursive function that does not utilize tail calls. A tail call is a "goto" statement, don't cringe though because it is acceptable to use in this context. As a final example, let us consider a maze game (great example reference from Programming in Lua). The user is put into the initial room, each room has four doors, north, south, east, and west. Each call would add a layer onto the stack, eventually leading to a stack overflow. However, if we use tail calls the players can "move" around forever:

CODE

--maze example

function roomOne()
    local move = io.read()
    if move == "south" then return roomThree()
    elseif move == "east" then return roomTwo()
    else
        print("invalid move")
        return roomOne()
    end
end

function roomTwo()
    local move = io.read()
    if move == "south" then return roomFour()
    elseif move == "west" then return roomOne()
    else
        print("invalid move")
        return roomTwo()
    end
end

function roomThree()
    local move = io.read()
    if move == "north" then return roomOne()
    elseif move == "east" then return roomFour()
    else
        print("invalid move")
        return roomThree()
    end
end

function roomFour()
    print("Congratulations!")
end

--start the user in room one
roomOne()

The "game" is a little bare, since there is no indication, without looking at the source, what room you're in based on your movement, but notice how many times you can enter directions before a stack overflow. Forever! Tail calls eliminate the need to return to a calling function if there is nothing left.

Hopefully you found this tutorial both interesting and helpful. Look out for Part II coming soon! Happy coding!