Iterating bits in Lua

2007-10-22T16:40:00.000-05:00

Today's question on #lua was (roughly speaking): How do you make a truth table in Lua?

OK, Lua has no bit operators, and it may not be the best language for intensive bit manipulation. Still, you can go a long way with the % operator:


function bit(p)
  return 2 ^ (p - 1)  -- 1-based indexing
end

-- Typical call:  if hasbit(x, bit(3)) then ...
function hasbit(x, p)
  return x % (p + p) >= p       
end

function setbit(x, p)
  return hasbit(x, p) and x or x + p
end

function clearbit(x, p)
  return hasbit(x, p) and x - p or x
end

As a digression, we could trivially use hasbit to iterate over a number and implement bitwise functions:


function bitor(x, y)
  local p = 1; local z = 0; local limit = x > y and x or y
  while p <= limit do
    if hasbit(x, p) or hasbit(y, p) then
      z = z + p
    end
    p = p + p
  end
  return z
end

We can improve on that by working across the numbers from the high-order end:


function bitor(x, y)
  local p = 1
  while p < x do p = p + p end
  while p < y do p = p + p end
  local z = 0
  repeat
    if p <= x or p <= y then
      z = z + p
      if p <= x then x = x - p end
      if p <= y then y = y - p end
    end
    p = p * 0.5
  until p < 1
  return z
end

Now, let's consider what a truth table function might look like. We want to compute (and display) the value of some boolean function f of n parameters for every combination of parameters (i.e. 2^n values). So our first pass might be something like this, where explode explodes a number into booleans, and TF prints its boolean arguments as "T" or "F".


function truth(n, f)
  for i = 0, 2^n - 1 do
    TF(explode(i, n)); io.write" = "; TF(f(explode(i, n))); io.write"\n"
  end
end

We already know how to explode a number into bits; we've done the iteration above in bitor. Here, we'll use a cute technique for recursively constructing a result list. (Unfortunately, the stack manipulation done by the Lua VM makes this technique quadratic in the number of return values even though it's a tail recursion, but for small lists it's fine.)


do
  -- The helper function assumes that x < 2*p
  local function explode_aux(x, p)
    if p >= 1 then
      if p <= x then
        return true, explode_aux(x - p, p * .5)
      else
        return false, explode_aux(x, p * .5)
      end
    end
  end

  function explode(x, n)
    local p = bit(n)
    return explode_aux(x % (p + p), p)
  end
end

The function TF just outputs its arguments, but it uses a similar vararg recursion. We check the second argument first, since we need to know whether we'll need to output a space or not.


-- Output boolean values as "T" or "F"
function TF(b1, b2, ...)
  if b2 ~= nil then
    io.write(b1 and "T " or "F ")
    return TF(b2, ...)
  elseif b1 ~= nil then
    return io.write(b1 and "T" or "F")
  end
end

And this does work as expected:


> truth(2, function(a, b) return a or b end)
F F = F
F T = T
T F = T
T T = T

But perhaps all this bit manipulation was a distraction. After all, there is a perfectly simple recursive solution to the problem of generating all combinations of n boolean values: generate false prepended to all the combinations of n-1 values, and then generate true prepended to all the combinations of n-1 values. (Moreover, this technique is easily extensible to enumerations other than booleans.)

The usual way of doing this in Lua involves creating a temporary table for the list of values, but it can be done in a purely functional style, which is more fun.

We want to call some function f with all combinations of n boolean variables. The recursion will therefore need to call some functions g0 and g1 with all combinations of n-1 boolean variables, where g0 ends up prepending false to the eventual arguments, and g1 does similarly with true. That's just a partial evaluation of f, so we can write it like this:


local function g0(f) return function(...) return f(false, ...) end end
local function g1(f) return function(...) return f(true, ...) end end
local function do_each_boolean(n, f)
  if n == 0 then
    return f()
  else
    do_each_boolean(n-1, g0(f))
    do_each_boolean(n-1, g1(f))
  end
end

In Lua, it's often convenient to use iterators rather than mapping functions like the above. The beauty of Lua is that it is trivial to turn that function into an iterator; we just wrap it in a coroutine and provide coroutine.yield as the second argument:


function all_booleans(n)
  return coroutine.wrap(do_each_boolean), n, coroutine.yield
end

> for a, b, c in all_booleans(3) do print(a, b, c) end
false   false   false
false   false   true
false   true    false
false   true    true
true    false   false
true    false   true
true    true    false
true    true    true

I put all of that together as a little cgi program, so you can try it out at http://segundo.ricilake.net/apps/truth. The full code is just under 100 lines; for your viewing pleasure, here it is:


local function g1(f) return function(...) return f(true, ...) end end
local function g0(f) return function(...) return f(false, ...) end end
local function bits(n, f)
  if n == 0 then
    return f()
  else
    bits(n-1, g0(f))
    bits(n-1, g1(f))
  end
end

local tc = table.concat
local function cc(h, ...) return tc({...}, h) end
local function tablerow(h, ...)
  return cc(h, "  <tr><"," class='col1'>")
         ..cc(cc(h, "</","><"," class='colx'>"), ...)
         ..cc(h, "</", "></tr>")   
end

local bool2char = {[true] = "T", [false] = "F"}
local function TF(x, ...)
  if x ~= nil then return bool2char[x], TF(...) end
end

local ok = {["and"] = true, ["or"] = true, ["not"] = true}
function ttable(expr)
  local seen = {}
  expr:gsub("%a%w*", function(w)
    if not ok[w] then
      if #w == 1 then
        if not seen[w] then
          seen[#seen+1] = w; seen[w] = true
        end
      else
        error "Invalid expression"
      end
    end
  end)
  if #seen > 6 then error "Invalid expression" end
  local f = assert(
              loadstring(
                "return function("..tc(seen, ", ")..") return "..expr.." end"),
              "Invalid expression")()
  local out = {"<table>", tablerow("th", expr, unpack(seen))}
  bits(#seen, function(...)
                  out[#out+1] = tablerow("td", TF(f(...), ...))
              end
  )
  out[#out+1] = "</table>"
  return tc(out, "\n")
end

local function form(me, e)
  return "<form action='"..me.."'>"
         .."<input type='submit' value='New expression'/>"
         .."<input type='text' size='40' name='expr' value='"..(e or "").."' />"
         .."</form>"
end

local explain = [[
<p>Enter a boolean formula in the text box. You may use up to six
variables, which may only be a single letter, and the operators
<code>and</code>, <code>or</code>, and <code>not</code>. You may
also use comparison operators <code>==</code> and <code>~=</code>;
the latter is equivalent to exclusive or.</p>
<p>Note that the variables are iterated in the order they appear
in the formula</p>
]]

local function doit(me, e)
  if e then
    e = e:gsub("%+", " "):gsub("%%20", " ")
    if e:match"<>&" then e = nil end
  end
  local frm = form(me, e)
  local table = e and ttable(e) or ""
  local title = e and "Truth table for '"..e.."'" or "Truth table generator"
  return cc("\n",'<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"',
                 '"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">',
                 "<html>",
                 "<head>",
                 "<title>"..title.."</title>",
                 "<style type='text/css'>",
                 "table {margin-bottom:1em; table-layout:auto; border:inset 2px}",
                 "th {width:3em; border:solid 1px}",
                 "th.col1 {width:8em; border:solid 1px}",
                 "td {text-align:center; border:solid 1px}",
                 "td.col1 {font-weight: bold}",
                 "</style>",
                 "</head>",
                 "<body>", table, explain, frm, "</body>",
                 "</html>"
  )
end
local me = os.getenv"SCRIPT_NAME"
local e = os.getenv"QUERY_STRING":match("expr=([^&]*)")
                                 :gsub("%%(%x%x)",
                                       function(xx)
                                         return string.char(tonumber(xx, 16))
                                       end)
local ok, rv = pcall(doit, me, e)
if not ok then ok, rv = pcall(doit, me) end
io.write("Status: 200\r\nContent-type: text/html\r\n\r\n", rv)