Iterating bits in Lua

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)