The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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.

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2019 by Sean Conner. All Rights Reserved.