Question about tprint function and recursion

XRei Wed 20 Aug 2014 04:04 AM #0

Hello. I have a question about the tprint function included with MUSH Client. I am a super novice at programming in general. I've been casually toying around in Lua for a few weeks now, and I've been using my understanding of the tprint function to gauge how far my understanding of Lua is coming along. I finally feel like I can follow and understand everything going on with it now.. EXCEPT one part which has me confused. Let met set up an example:

Here is the tprint() function from the forum for clarity sake:



function tprint (t, indent, done)
  done = done or {}
  indent = indent or 0
  for key, value in pairs (t) do
    Tell (string.rep (" ", indent)) -- indent it
    if type (value) == "table" and not done [value] then
      done [value] = true
      Note (tostring (key), ":");
      tprint (value, indent + 2, done)
    else
      Tell (tostring (key), "=")
      print (value)
    end
  end
end

Here is the table I want to recursively print.


t = { 
keyOne = "This is the first key.",
keyTwo = { "This", "is", "the", "second", "key." },
keyThree = { "This", "is", "the", "third", "key." },
keyFour = { { "This", { "is", { "the", { "fourth", { "key." }}}}} }
}

If I run it through the tprint(t) function like normal, I get the expected result, where each key and value is indented to the correct depth like so:



keyThree:
  1=This
  2=is
  3=the
  4=third
  5=key.
keyFour:
  1:
    1=This
    2:
      1=is
      2:
        1=the
        2:
          1=fourth
          2:
            1=key.
keyTwo:
  1=This
  2=is
  3=the
  4=second
  5=key.
keyOne=This is the first key.

So where I get confused is this.. What is the purpose of the 'done' table in the code? As far I can see, each iteration of the key/value pairs in the table(or in a sub table) checks to see if that particular value(or table in this case) has been set to 'true' in the 'done' table. At first I thought this was to make sure that when the function calls itself again that the new function block which is passed the 'done' table would see that the value in the 'done' table has already been previously iterated and would skip it to go to the next one.. But I later found out that the way function call stacks work that each instance of a function is 'stored' in the stack until the algorithm works it's way back down to the bottom of the stack in sequence.. but that also means that the iteration of each table is only ever traversed once?

(Not sure if I'm even making sense)

Anyways, as a test I tried making a copy of the tprint() function and removed all instances and references to 'done'. I ran the program on my table and.. it produced the exact same output. It seems like 'done' isn't even required. What am I missing?

Thanks.

Nick Gammon Australia Forum Administrator Wed 20 Aug 2014 05:35 AM #1

It's a good question, and there is a simple answer:

It's to prevent infinite loops for tables with self-references.

Here's an example:


foo = { }

foo.bar = foo

tprint (foo)

With the supplied tprint that prints:


"bar":
  "bar"=table: 00D0C5F0

Note that it doesn't expand "bar" again. If it did, it would have to expand bar.bar, and then bar.bar.bar and so on.

If you comment-out the line:


      done [value] = true

Then (in this case) the client goes into an infinite loop and you have to force-quit it.

Now you might say "well no-one would do that", but there is one big example of exactly that. The "global" table, which you can reference with the _G variable.

If you do this:


tprint (_G)

You will see _G listed in there somewhere. Without that "done" code everyone that did a tprint of _G would have to force-quit their client.

XRei Wed 20 Aug 2014 05:55 AM #2

Ah ha! That actually makes perfect sense now. Thanks for clearing that up.

Oh, and also thanks for MUSHClient being so awesome. *thumbsup*