Tuesday, January 24, 2012
99 ways to program a hex, Part 16: Lua, recursion
I'm continuing with Lua, with today's version using recursion.
#!/usr/bin/env lua
-- ***************************************************************
--
-- Copyright 2012 by Sean Conner. All Rights Reserved.
--
-- This program is free software: you can redistribute it and/or modify
-- it under the terms of the GNU General Public License as published by
-- the Free Software Foundation, either version 3 of the License, or
-- (at your option) any later version.
--
-- This program is distributed in the hope that it will be useful,
-- but WITHOUT ANY WARRANTY; without even the implied warranty of
-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-- GNU General Public License for more details.
--
-- You should have received a copy of the GNU General Public License
-- along with this program. If not, see <http://www.gnu.org/licenses/>.
--
-- Comments, questions and criticisms can be sent to: sean@conman.org
--
-- ********************************************************************
-- Style: Lua 5.1, recursion
function do_dump(fpin,fpout,offset)
local line = fpin:read(16)
if line == nil then return end
fpout:write(
string.format("%08X: ",offset),
line:gsub(".",function(c) return string.format("%02X ",c:byte()) end),
string.rep(" ",3 * (16 - line:len())),
line:gsub("%c","."),
"\n"
)
return do_dump(fpin,fpout,offset + 16)
end
-- **********************************************************************
if #arg == 0 then
print("-----stdin-----")
do_dump(io.stdin,io.stdout,0)
else
for i = 1 , #arg do
local f = io.open(arg[1],"r")
io.stdout:write("-----",arg[1],"-----","\n")
do_dump(f,io.stdout,0)
f:close()
end
end
os.exit(0)
Here, we have the do_dump() function calling itself for each
lines worth of data. If you don't have experience with recursion, this is a
common technique of solving certain programming problems by having a
function call itself with either a simpler case to solve, or, like in this
example, by calling itself with more data. And it just works.
If you are familiar with recursion, you might be horrified at such a solution, since a very large file might cause the program to crash since with recursion, the program (behind the scenes) keeps track of everything it's already done and thus, could run out of memory.
But in this case, we don't have to worry. Lua takes advantage of what's
called “tail call optmization.”
In this case, you can think of the tail call as a form of goto,
but this type of goto can also goto other
functions, which is useful in implementing state machines. For example, a
pseudocode version of the TFTP protocol, in Lua:
function server(conn)
remote,request = conn:read()
if request.opcode == 'read' then
info = open_read(request.file)
READ_DATA(remote,info)
elseif request.opcode == 'write' then
info = open_write(request.file)
SEND_ACK(remote,info)
end
return server(conn)
end
-- *******************************************************
function READ_DATA(remote,info)
remote:send(DATA,readblock(info.file,info.blocknum))
return RECEIVE_ACK(remote,info)
end
-- *******************************************************
function RECEIVE_ACK(remote,info)
ack = remote:read_ack()
if info.blocknum > 0 and ack.blocknum < info.blocknum then
return RECEIVE_ACK(remote,info)
end
if #info.data < 512 then
return --we're done
end
info.blocknum = info.blocknum + 1
return READ_DATA(remote,info)
end
-- *******************************************************
function SEND_ACK(remote,info)
remote:send(ACK,info.blocknum)
if info.blocknum > 0 and #info.data < 512 then
return -- we're done
else
return RECEIVE_DATA(remote,info)
end
end
-- *******************************************************
function RECEIVE_DATA(remote,info)
data = remote:read_data()
if data.blocknum < info.blocknum then
return SEND_ACK(remote,info)
end
info.blocknum = data.blocknum
writeblock(info.file,info.blocknum,data.data)
return SEND_ACK(remote,info)
end
I earlier said I wasn't a fan of tail call optimization but then, I didn't see a use for it. Here I do, at least for state machines. But for a hex dump program, not so much, but it doesn't hurt all that much either—it's still a loop in this case.
