The magic tricks may be simple, but that's not to say they're easy to perform

Tuesday, July 07, 2020

Bunny and I watch “Fool Us,” a show where Penn & Teller showcase a number of magicians and try to figure out how the trick was performed. It's a cool show and we will often rewind bits (and again, and again) to see if we can spot the trick.

On the recent show we saw Wes Iseli whose trick with a single 50¢ piece fooled Penn & Teller. He walked out on stage, handed Alyson Hannigan (the hostess) a “prediction” for her to hold on to. He then had the entire audience stand up and had them call heads or tails as he flipped the 50¢ piece. After about ten flips, there was a single audience member left standing. Wes then asked Alyson to read the “prediction” he made, and it described the audience member left standing.

I think I know how it was done, and the only reason it fooled Penn & Teller was due to a bad guess on Penn's part (if they know of several ways a trick can be done, and they guess the wrong one, they're fooled). The thing about magic is that often times, the “trick” is so simple that once you know how it's done, it's like “that's it? That's how it was done?”

For instance, way back in the second season, Wes Barker did a trick where he speared a page from a phone book with a sword which fooled Penn & Teller. He recently revealed how he did the trick (because, as he stated, phone books don't exist anymore). The trick was stupidly simple and by overthinking the trick, Penn was fooled. Oh, and it was interesting to learn yet another method of tearing up a phone book (as if we'll ever have a phone book to rip up).

Another instance of a very simple method tricking Penn & Teller is a recent trick by Eric Leclerc. He did the “needle in a haystack” trick, but this time finding a marked packing peanut by Teller in a huge box of packing peanuts. And again, it was a very simple trick. It's amazing how simple these tricks really are. It's almost likey they're cheating. And in a way, I guess they are.

Saturday, July 04, 2020

A relatively quiet Fourth of July

This has been one of the quietest Fourth of July I've experienced. It's been completely overcast with the roll of thunder off in the distance, the city of Boca Raton cancelled their fireworks show, and our neighbor across the street decided to celebrate with his backyard neighbor on the next street over.

Yes, there's the occasional burst of fireworks here and there, but it sounds nowhere near the levels of a war zone as it has in the past.

Happy Fourth of July! And keep safe out there!

Spending cache like its going out of style

I wrote an HTML parser. It works (for me—I tested it on all 5,082 posts I've made so far). But it came with one large surprise—it bloated up my gopher server something fierce—something like eight times larger than it used to be.

Yikes!

At first I thought it might be due the huge list of HTML entities (required to convert them to UTF-8).

A quick test revealed that not to be the case.

The rest of the code didn't seem all that outrageous, so fearing the worst, I commented out the HTML parser.

It was the HTML parser that bloated the code.

Sigh.

Now, there is a lot of code there to do case-insensitive matching of tags and attributes, so thinking that was the culpret, I converted the code to not do that (instead of looking for <P> and <p>, just check for <p>). And while that show a measurable decrease, it wasn't enough to lose the case-insentive nature of the parser.

I didn't check to see if doing a generic parse of the attributes (accept anything) would help, because again, it did find some typos in some older posts (mostly TILTE instead of TITLE).

I did try loading the parsing module only when required, instead of upfront, but:

it caused a massive spike in memory utilization when a post was requested;
it also caused a noticible delay in generating the output as the HTML parser had to be compiled per request.

So, the question came down to—increase latency to lower overall memory usage, or consume memory to decrease a noticible latency?

Wait? I could just pre-render all entries as text and skip the rendering phase entirely, at the cost of yet more disk space …

So, increase time, increase memory usage, or increase disk usage?

As much as it pains me, I think I'll take the memory hit. I'm not even close to hitting swap on the server and what I have now works. If I fix the rendering (and there are still some corner cases I want to look into) I would have to remember to re-render all the entries if I do the pre-render strategy.

Adventures in Formatting

If you are reading this via Gopher and it looks a bit different, that's because I spent the past few hours (months?) working on a new method to render HTML into plain text. When I first set this up I used Lynx because it was easy and I didn't feel like writing the code to do so at the time. But I've never been fully satisfied at the results [Yeah, I was never a fan of that either –Editor]. So I finally took the time to tackle the issue (and is one of the reasons I was timing LPEG expressions ~~the other day~~ [Nope. –Editor] ~~… um … the other week~~ [Still nope. –Editor] … um … a few years ago? [Last month. –Editor] [Last month? –Sean] [Last month. –Editor] [XXXX this timeless time of COVID-19 –Sean] last month).

The first attempt sank in the swamp. I wrote some code to parse the next bit of HTML (it would return either a string, or a Lua table containing the tag information). And that was fine for recent posts where I bother to close all the tags (taking into account only the tags that can appear in the body of the document, <P>, <DT>, <DD>, <LI>, <THEAD>, <TFOOT>, <TBODY>, <TR>. <TH>, and <TD> do not require a closing tag), but in earlier posts, say, 1999 through 2002, don't follow that convention. So I was faced with two choices—fix the code to recognize when an optional closing tag was missing, or fixing over a thousand posts.

It says something about the code that I started fixing the posts first …

I then decided to change my approach and try rewriting the HTML parser over. Starting from the DTD for HTML 4.01 strict I used the re module to write the parser, but I hit some form of internal limit I'm guessing, because that one burned down, fell over, and then sank into the swamp.

I decided to go back to straight LPEG, again following the DTD to write the parser, and this time, it stayed up.

It ended up being a bit under 500 lines of LPEG code, but it does a wonderful job of being correct (for the most part—there are three posts I've made that aren't HTML 4.01 strict, so I made some allowances for those). It not only handles optional ending tags, but the one optional opening tag I have to deal with—<TBODY> (yup—both the opening and closing tag are optional). And <PRE> tags cannot contain <IMG> tags while preserving whitespace (it's not in other tags). And check for the proper attributes for each tag.

Great! I can now parse something like this:

<p>This is my <a href="http://boston.conman.org/">blog</a>.
Is this not <em>nifty?</em>

<p>Yeah, I thought so.

into this:

tag =
{
  [1] =
  {
    tag = "p",
    attributes =
    {
    },
    block = true,
    [1] = "This is my ",
    [2] =
    {
      tag = "a",
      attributes =
      {
        href = "http://boston.conman.org/",
      },
      inline = true,
      [1] = "blog",
    },
    [3] = ". Is it not ",
    [4] =
    {
      tag = "em",
      attributes =
      {
      },
      inline = true,
      [1] = "nifty?",
    },
  },

  [2] =
  {
    tag = "p",
    attributes =
    {
    },
    block = true,
    [1] = "Yeah, I thought so.",
  },
}

I then began the process of writing the code to render the resulting data into plain text. I took the classifications that the HTML 4.01 strict DTD uses for each tag (you can see the <P> tag above is of type block and the <EM> and <A> tags are type inline) and used those to write functions to handle the approriate type of content—<P> can only have inline tags, <BLOCKQUOTE> only allows block type tags, and <LI> can have both; the rendering for inline and block types are a bit different, and handling both types is a bit more complex yet.

The hard part here is ensuring that the leading characters of <BLOCKQUOTE> (wherein the rendered text each line starts with a “| ”) and of the various types of lists (dictionary, unordered and ordered lists) are handled correctly—I think there are still a few spots where it isn't quite correct.

But overall, I'm happy with the text rendering I did, but I was left with one big surprise …

Saturday, June 27, 2020

Yet another repair job, this time involving solder!

“Are you ever going to finish repairing the clock?”

“Oh! I was waiting to see if you had any solder.”

“I thought I already told you I didn't have any, and that you were going to check your tool box.”

“Ah. Okay, let me do that.”

And so I found myself repairing an old-style alarm clock with the bells on top. It's not actually that old, having been manufactured in China some time in the last decade. The battery had died and leaked, causing some corrosion around the batter terminals. The corrosion wasn't coming off that easy, so last week (month? Day? Year? I HAVE NO CONCEPT OF TIME ANYMORE!) I soaked the back of the clock, which hosed the battery compartment, in vinegar overnight to clean up the corrosion. That worked beautifully, but some wires had come loose and needed to be resoldered.

The hard part of doing the repair? Finding a pair of wire strippers that wouldn't just cut the wire. The second hardest part? The actual soldering job. It had been way too long since I last used a soldering iron [Nothing worse than a programmer with a soldering iron. –Editor.] [Shut up, you! –Sean] but I managed to only burn one finger and resolder everything only twice. Not bad [If you say so yourself. –Editor] if I say so—[Shut up! –Sean].

Anyway, the clock has been repaired, it works, and we saved ourselves having to buy a new one.

Monday, June 15, 2020

Dear Apple

You must really not want my money. I know, I know, you aren't discrimiting against my race, or sex, or religion, or the fact that I'm voting for Velma Owen for President. But I find it puzzling that this is the third time you rejected my attempt to drunkenly spend money to fix a problem. The first time I was ready to buy the K2 of Mac computers only to learn I had to buy one online—I wasted my time in coming to the store. The second time I was going to buy an iPad (long stupid story there, not worth going into) only to be shoved towards Best Buy where it was cheaper.

And then today. I've walked into your Apple Store looking to buy a new monitor. Earlier, when I went to turn on the monitor on my Mac, it briefly lit up, decided it had enough of life and immediately shut off, never to turn back on again. Granted, the monitor was from 2005, and I bought it used around ten years ago so I'm not terribly upset over it dying an inglorious dimming death.

But alas, Apple no longer supports that monitor, so fixing it was out of the question. The interface on the Mac mini it's attached to is, itself, obsolete, and Apple no longer carries the appropriate adaptors. And the other interface on the Mac mini, the HDMI port, is not supported by any new Apple monitor. So I was told my best bet was to head of to … Best Buy.

Why did I even bother coming to your store, Apple? Why do you even bother to have a store in the first place?

Wednesday, June 10, 2020

The email situation has been solved

I finally solved the email issue on my server—the physical host was NATing connections from my virtual server. There's no need for that. Once the bypass for the NAT was added, outgoing packets were finally coming from my server's IP address.

Monday, June 08, 2020

I can code that FizzBuzz function with only two tests

My favorite implementation of FizzBuzz is the Ruby version based upon nothing more than lambda calculus and Church numbers, i.e. nothing but functions all the way down.

Then I saw an interesting version of it in the presentation “Clean Coders Hate What Happens to Your Code When You Use These Enterprise Programming Tricks.” The normal implementation usually involves thee tests, one for divisibility by 3, one for divisibility by 5, and an annoyingly extra one for both or for divisibility by 15. But the version given in the presentation only had two tests. Here's a version of that in Lua:

function fizzbuzz(n)
  local test = function(d,s,x)
    return n % d == 0 
       and function(_) return s .. x('') end
        or x
  end
  
  local fizz = function(x) return test(3,'Fizz',x) end
  local buzz = function(x) return test(5,'Buzz',x) end
  
  return fizz(buzz(function(x) return x end))(tostring(n))
end
  	 
for i = 1 , 100 do
  print(i,fizzbuzz(i))
end

The function test() will return a new function that returns a string, or whatever was passed in x. fizz() and buzz() are functions that return what test() returns. The last line can be broken down into the following statements:

_0 = function(x) return x end
_1 = buzz(_0)
_2 = fizz(_1)
_3 = _2(tostring(n))	
return _3

And we can see how this works by following a few runs through the code. Let's first start with a number that is not divisible by 3 or 5, say, 1.

_0 = function(x) return x end
_1 = buzz(_0) = function(x) return x end
_2 = fizz(_1) = function(x) return x end
_3 = _2("1") == "1"
return _3

_0 is the identity function—just return whatever it is given. buzz() is called, which calls test(), but since the number is not divisible by 5, test() returns the passed in identity function, which in turn is returned by buzz(). fizz() is then called, and again, since the number is not divisible by 3, _test() returns the identity function, which is returned by fizz(). _3 is the result of the identity function called with “1”, which results in the string “1”.

Next, the number 3 is passed in.

_0 = function(x) return x end
_1 = buzz(_0) = function(x) return x end
_2 = fizz(_1) = function(_) return 'Fizz' .. _1('') end
_3 = _2("3") == 'Fizz'
return _3

_0 is the identify function. buzz() just returns it since 3 isn't divisible by 5. fizz(), however, returns a new function, one that returns the string “Fizz” concatenated with the empty string as returned by the identify function. This function is then called, which results in the string “Fizz”.

The number 5 works similarly:

_0 = function(x) return x end
_1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end
_2 = fizz(_1) = function(_) return 'Buzz' .. _0('') end
_3 = _2("5") == 'Buzz'
return _3

Here, buzz() returns a new function which returns the string “Buzz” concatenated with the empty string returned by the identify function. fizz() returns the function generated by buzz() since 5 isn't divisible by 3, and thus we end up with the string “Buzz”.

It's the case with 15 where all this mucking about with the identify function is clarified.

_0 = function(x) return x end
_1 = buzz(_0) = function(_) return 'Buzz' .. _0('') end
_2 =_fizz(_1) = function(_) return 'Fizz' .. _1('') end
_3 = _2("15") = 'FizzBuzz'
return _3

Again, _0 is the identify function. buzz() returns a new function because 15 is divisible by 5, and this function returns the string “Buzz” concatenated by the empty string returned by the identity function. fizz() also returns a new function, because 15 is also divisible by 3. This function returns the string “Fizz”, concatenated by the passed in function, which in this case is not the identity function, but the function returned from buzz(). This final function returns “Fizz” concatenated with the string of the function that returns “Buzz” concatenated with the empty string returned by the identity function, resulting in the string “FizzBuzz”.

Yes, it's quite a bit of work just to avoid an extra test, but fear not! Here's a way to do FizzBuzz with just two tests that is vastly simpler:

function fizzbuzz(n)
  local list = { 'Fizz' , 'Buzz' , 'FizzBuzz' }
  list[0]    = tostring(n)
  
  local m = (n % 3 == 0 and 1 or 0)
          + (n % 5 == 0 and 2 or 0)
  return list[m]
end

for i = 1 , 100 do
  print(i,fizzbuzz(i))
end

Here we generate an index into an array of four possible responses, the original number as a string, “Fizz”, “Buzz” and “FizzBuzz”. If the number isn't divisible by either 3 or 5, the index is 0; if it's divisible by 3, the index is 1, if divisible by 5, the index is 2, and if both, the index ends up as 3. It's not quite as mind blowing as the first version, but it is easier to translate to a language that lacks closures, like C.

Friday, June 05, 2020

A Lua module in assembly, why not?

I've been known to dabble in assembly language from time to time, and there's been this one instruction on the Intel Pentium that I've wanted to play around with—RDTSC. It's used to read the internal time-stamp counter which is incremented every clock cycle. On my system, this counter is incremented 2,660,000,000 times per second (the computer is running at 2.66GHz) and this makes for a nice way to time code, as the instruction is available in userspace (at least on Linux).

I wanted to use this to time some Lua code, which means I need to wrap this instruction into a function that can be called. I could have used some inline assembly in C to do this, but

the code is non-portable anyway;
I wanted to avoid as much C overhead as possible;
and I thought it would be amusing to write an entire Lua module in assembly.

It wasn't hard:

;***************************************************************************
;
; Copyright 2020 by Sean Conner.
;
; This library is free software; you can redistribute it and/or modify it
; under the terms of the GNU Lesser General Public License as published by
; the Free Software Foundation; either version 3 of the License, or (at your
; option) any later version.
;
; This library 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 Lesser General Public
; License for more details.
;
; You should have received a copy of the GNU Lesser General Public License
; along with this library; if not, see <http://www.gnu.org/licenses/>.
;
; Comments, questions and criticisms can be sent to: sean@conman.org
;
;***************************************************************************

                bits    32
                global  luaopen_rdtsc
                extern  lua_pushinteger
                extern  lua_pushcclosure

;***************************************************************************
                section .text

ldl_rdtsc:      rdtsc
                push    edx
                push    eax
                push    dword [esp + 12]
                call    lua_pushinteger	; lua_pushinteger(L,rdtsc);
                xor     eax,eax		; return 1
                inc     eax
                lea     esp,[esp + 12]
                ret

;---------------------------------------------------------------------------

luaopen_rdtsc:
                xor     eax,eax
                push    eax
                push    ldl_rdtsc
                push    dword [esp + 12]
                call    lua_pushcclosure ; lua_pushcclosure(L,ldl_rdtsc,0);
                xor     eax,eax		 ; return 1
                inc     eax
                lea     esp,[esp + 12]
                ret

I'll leave it up to the reader to convert this to 64-bit code.

Timing LPEG expressions

One pattern that is seemingly missing from LPEG is a case-insensitive match, a pattern where you can specify a pattern to match “foo”, “FOO”, “Foo” or “fOo”. I have to think this was intentional, as doing case insensitive matching on non-English words is … a complex topic (for a long time, the German letter “ß” upper case form was “SS” but not all “SS” were an upper case “ß”). So it doesn't surprise me there's no pattern for it in LPEG. But I wish it did, as a lot of Internet text-based protocols require case-insensitive matching.

There are two ways around the issue. One way is this:

local lpeg = require "lpeg"
lcoal P    = lepg.P

local patt = (P"S" + P"s")
           * (P"A" + P"a")
           * (P"M" + P"m")
           * P"-"
           * (P"I" + P"i")
           * P"-"
           * (P"A" + P"a")
           * (P"M" + P"m")

But this would seem to produce a lot of branching code that would be slow (LPEG has its own parsing-specific VM). Of course, there's this solution:

local lpeg = require "lpeg"
local P    = lpeg.P
local S    = lpeg.S

local impS = S"Ss" * S"Aa" * S"Mm"
           * P"-"
           * S"Ii"
           * P"-"
           * S"Aa" * S"Mm"

But each lpeg.S() uses 32 bytes to store the set of characters it matches, and that seems like a large waste of memory for just two characters. A third way occured to me:

local lpeg = require "lpeg"
local Cmt  = lpeg.Cmt
local R    = lpeg.R

local impC = Cmt(
                  S"SsAaMmIi-"^1,
                  function(subject,position,capture)
                    if capture:lower() == 'sam-i-am" then
                      return position
                    end
                  end
                )

This just looks for all the characters in “Sam-I-am” and then calls a function to do an actual case-insensitive comparison, but at the cost of doing it at the actual match time, instead of potentially doing it lazily (as the manual puts it, “this one is evaluated immediately when a match occurs (even if it is part of a larger pattern that fails later)”). And it might be a bit faster than the one that just uses lpeg.P(), and with less memory than the one using lpeg.S().

So before going to work on a custom case-insensitive pattern for LPEG (where lpeg.P() is pretty much the case-sensitive pattern), I thought I might want to profile the existing approaches first just to get a feeling for how long each approach takes.

local lpeg  = require "lpeg"
local rdtsc = require "rdtsc" -- this is another post

local Cmt = lpeg.Cmt
local Cf  = lpeg.Cf
local P   = lpeg.P
local R   = lpeg.R
local S   = lpeg.S

local test = "Sam-I-Am"

local base = P"Sam-I-Am"
local impP = (P"S" + P"s")
           * (P"A" + P"a")
           * (P"M" + P"m")
           * P"-"
           * (P"I" + P"i")
           * P"-"
           * (P"A" + P"a")
           * (P"M" + P"m")
local impS = S"Ss" * S"Aa" * S"Mm"
           * P"-"
           * S"Ii"
           * P"-"
           * S"Aa" * S"Mm"
local impC = Cmt(
                  S"SsAaMmIi-"^1,
                  function(subject,position,capture)
                    if capture:lower() == "sam-i-am" then
                      return position
                    end
                  end
                )

local function testf(patt)
  local res = {}
  for i = 1 , 10000 do
    local zen = rdtsc()
    patt:match(test)
    local tao = rdtsc()
    table.insert(res,tao - zen)
  end
  table.sort(res)
  return res[1]
end

print('base',testf(base))
print('impP',testf(impP))
print('impS',testf(impS))
print('impC',testf(impC))

I'm testing the normal case-sensitive pattern, and the three case-insensitive patterns. I run each test 10,000 times and return the lowest value (“lowest” means “fastest”). The rdtsc() function … that's another post (but a pre-summary—it represents the number of clock cycles the CPU has been running and on the test system there are 2,660,000,000 cycles per second).

Anyway, on to the results:

Timing some LPEG patters
base	2800
impP	3020
impS	3020
impC	5190

I'm honestly surprised. First, I thought the last method would do better than it did, but it's nearly twice as slow. The other two are pretty much the same, time wise (which leads me to wonder if the pattern lpeg.P(single_letter) + lpeg.P(single_letter) is internally converted to lpeg.S(letters)—it could very well be). And they aren't that much slower than the case-sensitive pattern. Well, not enough for me to worry about it. Even a much longer string, like “Access-Control-Allow-Credentials” gave similar results.

And no, I did not write out by hand the expression to match “Access-Control-Allow-Credentials” case-insensitively, but wrote an LPEG expression to generate the LPEG expression to do the match:

local lpeg = require "lua"
local Cf   = lpeg.Cf -- a folding capture
local P    = lpeg.P
local R    = lpeg.R

local char = R("AZ","az")
           / function(c)
               return P(c:lower()) + P(c:upper())
             end
           + P(1)
           / function(c)
               return P(c)
             end
Hp = Cf(char^1,function(a,b) return a * b end)

It's a powerful technique, but one that can take a while to wrap your brain around. It's just one of the reasons why I like using LPEG.

The Boston Diaries

Tuesday, July 07, 2020