* * * * *

              99 ways to program a hex, Part 16: Lua, recursion

I'm continuing with Lua [1], 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: [email protected]
> --
> -- ********************************************************************
>
> -- 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 [2].” In this case, you can think of the tail
call as a form of goto [3], 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 (Trivial File Transfer Protocol) [4] 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 [5] 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.

* Part 15: Lua [6]
* Part 17: Lua, recursion, runtime checking [7]

[1] http://www.lua.org/
[2] http://en.wikipedia.org/wiki/Tail_call
[3] http://en.wikipedia.org/wiki/Goto
[4] http://en.wikipedia.org/wiki/Trivial_File_Transfer_Protocol
[5] gopher://gopher.conman.org/0Phlog:2007/10/19.1
[6] gopher://gopher.conman.org/0Phlog:2012/01/23.2
[7] gopher://gopher.conman.org/0Phlog:2012/01/25.1

Email author at [email protected]

You are viewing proxied material from gopher.conman.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.