AD0SK Project Log

Basic requirements

For those who aren't clear what I'm talking about, what we're going for here is something like this:

An old-school hitcounter, mined from the bowels of archive.org and used without proper attribution like I'm the British Museum or something.

I'm not sure how these actually worked, I'd imagine just a cgi script that used ImageMagick to glue the digit assets together into a final image, although if you had cgi rendering yourself you could probably just stuff the img tags for the correct individual digits and do it that way. The former technique sounds better for our present purposes, for reasons that should become apparent.

It's 2020, so let's assume the visiting browser can display SVG. Let's try and write an endpoint that will keep an internal count, increment it on each GET request, and return that as an SVG that shows the current number. We can then just put that into an img tag and it should just work with no AJAXy complications or client-side anything.

Note, though, we don't currently have any server-side anything either (this site, for instance, being statically-hosted). To make anything work at all, then, let's put our new endpoint up on Google Cloud Functions. This is google's version of lambda/serverless, and should allow us to (1) write a function to service the GET request, (2) communicate with one of the various datastores that google provides to maintain the counter state, and (3) render the SVG code for return as the response payload.

Let's take these tasks in 3, 1, 2 order:

Implementation: the display

For this, we want something that takes an arbitrary integer and returns an SVG document that draws it like we want.

Let's use the drawSvg module for the SVG manipulation. First nail the basic geometry by assuming (very optimistically) six digits to display, which we'll zero-pad from the left. Make each digit 40 pixels wide by 60 pixels tall.

import drawSvg as draw

N_DIGITS = 6
DIGIT_WIDTH = 40
DIGIT_HEIGHT = 60

def get_counter(n):
    """Given integer n, returns a drawSVG.Drawing representing n"""

    d = draw.Drawing(
        width = N_DIGITS * DIGIT_WIDTH,
        height = DIGIT_HEIGHT
    )

    return d

This will give us an SVG with the correct geometry, although there's nothing in it yet. We'll want some digits in there, which we'll presumably want to draw individually, so let's write a helper that breaks those out:

def get_digits(n):
    """return list of single-character strings, left-to-right the digits of n,
    zero-padded to N_DIGITS.
    Raise AssertionError if n exceeds representable digits"""

    fmtstr = f'{{:0{N_DIGITS}d}}'
    digits = list(fmtstr.format(n))
    assert len(digits) == N_DIGITS, f'Overflow trying to fit {n}' \
                                    f'into {N_DIGITS} digits'

    return digits

Since we want the result to pad out to N_DIGITS, and since this might conceivably change, we double-bag it on the format string. Given the default value above, fmtstr ends up being '{:06d}', and thus get_digits(69) returns ['0', '0', '0', '0', '6', '9'] (Note: there are many, many other ways of accomplishing what we're doing, some of them a lot more fun. Quick reminder that "fun" is not necessarily an admirable objective when developing software in a a pedagogical or team environment).

Although perhaps not in keeping with the spirit of the geocities inspiration, we also aggresively trap for an argument that's not representable in the given width (instead of silently overflowing, trying to paste ancillary characters outside the bounds of the SVG draw area, throwing a weird internal exception, or other unexpected behaviors). Thus, get_digits(1234567) will raise AssertionError. To be totally rigorous, we should also check to make sure the argument is an integer and positive-definite. In a professional environment, we'd probably (hopefully?) have unit tests to ensure that exceptional cases like these are handled with a minimum of surprise.

Now that we have these digits, we can apply them as text elements to our Drawing. We add these to the d object within the scope of get_counter above like so:

for digit, x in zip(get_digits(n), range(N_DIGITS)):
    d.draw(
        draw.Text(
            digit,
            fontSize=DIGIT_HEIGHT,
            x=(x+.5)*DIGIT_WIDTH,
            y=DIGIT_HEIGHT*.65,
            fill='white',
            font_family='courier, MONOSPACE',
            center=True
        ))

There's some munging going on to get the characters to align, the details of which I'll spare you (protip: just monkey with it between some combination of code tweaks and devtools with liberal use of the refresh button until it looks right). We will, however, bow in the general direction of cross-platform visual consistency by specifying a font, and go ahead and make the numbers white, to show up against the dark background.

Except, we don't have a dark background yet. The following needs to be specified farther up in the procedure so as to end up on a lower z-layer, but we can use an SVG gradient to get the awesome drum counter visual effect:

g = draw.LinearGradient(0, 0, 0, DIGIT_HEIGHT)
g.addStop(0, 'black')
g.addStop(0.5, '#666')
g.addStop(1, 'black')

d.draw(draw.Rectangle(
    0,
    0,
    width=N_DIGITS * DIGIT_WIDTH,
    height=DIGIT_HEIGHT,
    fill=g
))

And maybe some vertical lines between the digits, while we're at it:

for x in range(-1, N_DIGITS+1):
    d.draw(
        draw.Line(
            x*DIGIT_WIDTH,
            0,
            x*DIGIT_WIDTH,
            DIGIT_HEIGHT,
            stroke_width=8,
            stroke='#222'
        )
    )

Put all together, get_digits(31337) then returns an SVG document that looks something like the following:

Not bad for 55 lines of (mostly whitespace) code with no static assets!

Implementation: the deployment

To catch up, we now have a thing that, given a number n, will provide a fancy SVG graphic depicting that number n in the most awesome 90s-tastic fashion possible. It remains to host this someplace that will allow for retrieval of those graphics over the public internet, and which will hopefully take care of incrementing n once per such request, thereby making it a proper hit counter.

First, let's test that our svg generation works in a deployed environment. Define a function test_counter of one argument, the flask.Request object representing the request, but which we'll then ignore. Have this return the svg data from a static n:

def test_counter(request):
    return draw_counter(69).asSvg()

and, for convenience, a Makefile to deploy it:

deploy-test:
    gcloud functions deploy test-counter --entry-point test_counter \
           --runtime python37 --trigger-http

We also need a requirements.txt telling GCF that our execution environment needs drawSVG.

Getting that to actually work will require a bit of configuration in the Google Cloud Console, and I'm going to consider that out-of-scope for this treatment. For one, there are a million blog posts out there about "how to get started with Google Cloud Functions" that go through all that in detail, for two they're all also probably out-of-date because google seems to change the minutiae of the configuration pages quite frequently. Google's own documentation is kept current and also surprisingly good, and I'd refer any readers actually playing the home game to that.

Anyway, (waves hands), given the configuration of my project, this endpoint is now available at https://us-central1-geocities-counter.cloudfunctions.net/test-counter. Amazingly it just works, with the xmlns presumably saving us from having to futz about with MIME types or anything. Now, to make it tick...

Implementation: data persistence

The GCF execution environment is ephemeral, so obviously we can't just use a global variable to retain the counter state, or anything else that's tied to the interpreter lifecycle. So, although it seems like overkill, we're going to need to set up an external datastore to retain this state. GCP is absolutely resplendent with options for doing this: we could use google's Bigtable or Spanner, a hosted instance of MongoDB or Postgres, even a flat file in Google Cloud Store. For this walk-through I'm going to use firestore, which is a NoSQL/document database that google took over with their acquisition of Firebase and that's easy to get started with for projects like this.

As above, I'm going to skip the details of actually setting this up on the Cloud Console side. Suffice to say we've set up firebase for the project and defined a collection called counter. Now, we add a second function:

from google.cloud import firestore

def get_counter(request):
    """GCF entrypoint: retrieves counter state from firestore, initializing if
    necessary.
    Increments this and persists to firestore, returning svg payload of counter
    displaying new count"""

    db = firestore.Client()
    doc_ref = db.collection(u'counter').document(u'count')
    doc = doc_ref.get()
    old_n = doc.get(u'n') if doc.exists else 0

    n = old_n + 1
    doc_ref.set({u'n': n})

    return draw_counter(n).asSvg()

and a make target for same:

deploy:
    gcloud functions deploy counter --entry-point get_counter \
           --runtime python37 --trigger-http

We need the firestore module from the google.cloud package for anything to work, and this must be added to requirements.txt also. Despite being a google product, the Cloud Functions execution environment doesn't inject every possible dependency into the runtime, which we may assume is a Good Thing.

When we instantiate a database client via firestore.Client(), it does know, somewhat magically, that we want to connect to the project's firestore, and it handles this connection, including authentication. This is actually totally awesome since anyone who's done work like this knows getting things to talk like that usually takes at least an hour, along with a large repertoire of curse words to get working properly.

Even though the value we're trying to store is scalar, firebase makes us go through a couple layers of abstraction to get there (being, of course, designed to operate on much larger collections of data, the value of which we'll see in the conclusion). First, we must identify a collection (here called counter), which must be created either through the Cloud Console or via calls to an API we won't treat here. The unit over which these collect is called a document, and these are identified by unique keys. We use the magic key count to identify our single document of concern. The documents are (potentially heterogeneous) associative arrays, which are not yet retrieved at this point. This allows us to check for existence and apply default data if necessary, allowing document lifecycle to be managed at the application level even after relegating that of the collection to the infrastructure. Finally, our scalar value of interest lives on a field of the document we call n, which we then retrieve if the document exists and default to 0 otherwise. We then increment this value, overwrite the document with the new value of n, and pass it to draw_counter to generate our response.

Although it worked above when directly loaded, it turns out that browsers don't seem to render svg in an img tag without either a .svg file extension (which GCF doesn't allow) or the correct mimetype set, so we force that on the response. We then should be able to use this as the src value of an img tag, like so:

Sit there and jam on the refresh button for a minute to prove to yourself it works.

Conclusion

So that was fun, we've accomplished our goal of implementing a server-side-rendered graphical hit counter I feel is very aligned with the spirit of those we saw on geocities and other sites in the early days of the public web (even if "server" has become a much more nebulous concept since then). Project files may be found at https://github.com/drewhutchison/geocities-counter.

From here, there's a few places we could obviously go:

• If we don't trust our clients to render SVG, we could use drawSVG's .rasterize() method to return it as a PNG or whatever. Maybe even predicate this on the contents of the request's Accept header.
• A lot of hit counters back then used a different visual presentation: 7-segment displays, plaintext, or whatever. My feeling is, if we're going old-school skeumorphic, go old-school skeumorphic and stick with the drum counter, but since this is encapsulated in the draw_counter method, we can really do whatever we want. For instance, a bit of signed random added to the y argument of the draw.Text constructor would give us a bit of jitter to the drums for a more authentic 90s feel.
• There's a classic race condition, in that two simultaneous requests might retrieve the same n and both overwrite with their n+1, resulting in a count being "lost". Obviously this would be unacceptable in certain applications, and there are well-known ways of preventing this, but I think for a simple hitcounter we're OK.
• This is really the dumbest thing possible and, except for the concern just noted, will advance the count on each discrete GET request. Most things like this are minimally interested in unique visitors. Since we have access to the entire Request object, we could tamp this down by IP, set a browser-side cookie, or employ some more-sophisticated type of client fingerprinting to account for non-unique views (this need not be invasive, in fact, GoatCounter employs a rather ingenious mechanism to track unique visitors in a GDPR-compliant way. See https://www.goatcounter.com/gdpr for details).

The latter would entail a modification of our use of the datastore: instead of just incrementing a scalar n we would keep a set of identifiers (the IP, some uniquely-identifying hash, or whatever) and return the cardinality of this set. The use of a document-store database like firestore makes this a very easy change. At that point, we could also do away with the magic key n entirely and instead use the URL as determined from the request, and we're well on our way to a full-featured analytics system, despite not changing the public-facing API (of a GET to the function endpoint) at all.

But, that would have the effect of reducing the total count, and I think I get more internet points the higher that thing goes. Did you refesh the page to prove to yourself it's working yet?

Notes

Design

Design requirements were pretty straightforward, the fixture needed to provide three things:

1. Some means of retaining the spool and allowing it to unreel in slightly more elegant fashion than just flopping around on the work surface. If this can help prevent its getting scratched, so much the better.
2. Some form of stop, square to the axial dimension of the reel and against which the working end of the material can be abutted and made fast.
3. Some sort of guide, rigidly fixed at the desired distance of ten inches from the stop, along which a cutting tool may be worked.

While this allowed a lot of flexibility in implementation, a challenge was the timing. This was late March, when Amazon was still quoting lead times of 4-6 weeks on "nonessential" items, hardware and home improvement stores were basically closed and I myself was trying not to leave the house. Here's what I made do with parts (mostly) on hand:

Assembly

The finished fixture

The base is cut from some 3/4" subfloor plywood I had lying around. This was plenty rigid but a little more warped than was reasonable for the application, so I counterbored from the top and tied into a couple lengths of steel strut-channel, which got it straightened enough. With the limited materials I had to work with, this construction is going to be a bit rough.

The reel is stood-off on plywood that the innovation center was kind enough to laser for me, sandwiching some scrap 1x1 for rigidity and tie-in to the base. This plywood is slotted to accommodate a length² of 3/8" all-thread, on which the ID of the spool sits.

The cutting guide is formed by the T-slot aluminum frame you see swung up toward the image foreground. This is corner-braced internally but also tied to more plates of laser-cut plywood you see up top. Edge-to-edge the frame is 10" wide,³ and serves to measure this dimension in the direction toward the spool from the plywood seen screwed into the base, to which the hinges are affixed⁴ and which serves as the material stop. When the frame swings down, it then defines a transverse line 10" from the stop. It can be toggle-clamped to hold the material in place, allowing the operator both hands free to manage the cutting tool.

Lessons learned

Altogether this was a very edifying experience, for a couple of different reasons.

From a systems perspective, this was a great object lesson in limiting features to scope of project. The engineer in me looks at requirement (1) above and immediately starts picturing endcaps that mate the ID of the spool and ride on sleeve bearings about the axial shaft such that the spool is balanced around its CoG and spins freely and etc. etc. That part of me is absolutely horrified at the thought of the spool just rough-riding over a threaded rod like a roll of toilet paper⁵. Yet, it turns out, that works just fine. Any attempt to build a more elaborate mechinism would have taken longer to design and fabricate, imperiled ourselves of a re-roll if something didn't fit or otherwise work, and been more likely to fail "in the field."

Not the most elegant way to hold a spool, but it works.

Similarly, I spent a lot of time thinking about requirement (3) and whether it would be easiest to build a hot-wire cutter versus a straight, hook, or rotary blade, what type of guide would best support same, what kind of clearance or cut-out might be required to accomodate the tool in the bed, etc. etc. before shelving all of that and just building a straight-edge. I figured that, if a captive tool were that important, I'd hear about it. In point of fact, the operators have made do with a manual knife just fine; the straight-edge was all that was required.

There's a lot of talk in engineering circles about the perils of overengineering, YAGNI, project scope, etc. For all that talk, actually being able to define and hit targets is still largely a matter of good judgement and experience and something even seasoned engineers often fail at. Being able to take something from concept to delivery and see that it succesfully meets a need is a rare pleasure and one that keeps me in these fields.

From a personal perspective, it was also very gratifying to be able to execute with the limited parts and supplies I had on hand. For years (at least when it comes to small parts like fasteners and toggle clamps), my policy has been to buy 25-100% more than I need for the current project "in case I need 'em for something else later." This doesn't always feel like the right thing to do, what with the additional clutter it brings and the alternative convenience of modern supply chains. Most of my personal projects spend a long time in what we'll call the "concept/pre-procurement phase." Being forced by circumstance out of that and directly into execution with just the stock I'd accumulated "in case I need it" was, again, a very gratifying and singular experience.

Notes

Brute-forcing the solution

To begin with, the exercise states on faith that our problem space comprises 16 matrices. Do we know that number is correct? Let's write our matricies in the form

with \(a\), \(b\), \(c\), and \(d\) each taking on one of the values \([0, 1]\). This leads to \(2^4 = 16\) possiblities, the indicated number.

Again, we suspect there's some common property among the subset of these that are invertible, but that begs the question. We'll think through what these may be in a moment, but first let's try the brute force approach. 16 isn't many cases to try, especially with a computer's help.

We know of a matrix of the above form that it's invertible iff \(ad-bc \neq 0\). It's easy enough to enumerate the possible combinations and count:

λ: isSingular (a, b, c, d) = a*d - b*c == 0
λ: let s = [0, 1]
λ: let searchSpace = [(a, b, c, d) | a <- s, b <- s, c <- s, d <- s]
λ: length searchSpace
16
λ: length $ filter (not . isSingular) searchSpace
6

We see that indeed we're looking at 16 matricies and that, of these, 6 are nonsingular. This figure is all the exercise asked for, but we'd expect there's some structure of interest regarding exactly which six of the sixteen have this property. We could display the results of the filter instead of counting them, but let's see if we can reason through what they may be instead.

Reasoning the solution

The problem of finding which six matrices fit our criterion is that of finding a particular subset of the 16 candidates. Since each cadidate is either included or excluded from a given subset, there are \(2^{16} = 65536\) subsets possible.¹ With the blessing of foresight, we know we're only interested in those subsets having cardinality 6. There are \(_{16}C_{6} = 8008\) of these: we're looking for exactly one, and don't currently know of any meaningful higher-level concepts to guide us. This idea of cardinality is an interesting one, though. Not having any better ideas, let's define \(N=a+b+c+d\), the number of nonzero elements in each matrix, and see if that helps us break down the problem.

There's one matrix with \(N=0\), which is clearly singular. There's also one matrix for \(N=4\), which is also singular. Any matrix with \(N=1\) is going to be singular, by virtue of necessarily having a zero row.² There are four such matrices. The \(N=2\) case is the most interesting: two of these six matrices have a zero row and are thus singular, likewise the two having a zero column. The other two matrices (the \(2\times2\) identity \(I_2\) and the \(2\times2\) exchange matrix \(J_2\)) are invertible. Finally, there are four \(N=3\) matrices (distinguished by the position of the single zero element), and each is nonsingular. This brings our total to the desired 6.

We've thus answered the question left open in the previous section, and we know which six matricies satisfy our criterion, and have some sense of their underlying structure. As before, we may be satisfied, but let's look deeper into what algebraic structure(s) that might evidence from taking these together.

Investigating further

Under matrix multiplication, it's clear that any identity matrix \(I\) forms the trivial group, and that \(\{I_2, J_2\} \cong \mathbf{Z_2}\). Let us define \(B_a\) as the (\(N=3\)) matrix having \(a=0\) (\(b=c=d=1\)), and \(B_b\), \(B_c\), and \(B_d\) analogously. We see that any one of these along with \(J_2\) serves to generate the others:

Prelude> import Data.Matrix
Prelude Data.Matrix> let i = identity 2
Prelude Data.Matrix> let j = permMatrix 2 1 2
Prelude Data.Matrix> let ba = fromLists [[0,1],[1,1]]
Prelude Data.Matrix> ba
┌     ┐
│ 0 1 │
│ 1 1 │
└     ┘
Prelude Data.Matrix> let bb = ba*j
Prelude Data.Matrix> bb
┌     ┐
│ 1 0 │
│ 1 1 │
└     ┘
Prelude Data.Matrix> let bc = j*ba
Prelude Data.Matrix> bc
┌     ┐
│ 1 1 │
│ 0 1 │
└     ┘
Prelude Data.Matrix> let bd = j*ba*j
Prelude Data.Matrix> bd
┌     ┐
│ 1 1 │
│ 1 0 │
└     ┘

This is starting to look like an interesting algebraic structure, but note that we don't have closedness:

Prelude Data.Matrix> ba*ba
┌     ┐
│ 1 1 │
│ 1 2 │
└     ┘
Prelude Data.Matrix> ba*bb
┌     ┐
│ 1 1 │
│ 2 1 │
└     ┘
Prelude Data.Matrix> ba*bc
┌     ┐
│ 0 1 │
│ 1 2 │
└     ┘
Prelude Data.Matrix> ba*bd
┌     ┐
│ 1 0 │
│ 2 1 │
└     ┘

Nor do we have the inverses (which we'd already have encountered otherwise). Let's calculate those:

Prelude Data.Matrix> inverse ba
Right ┌           ┐
│ -1.0  1.0 │
│  1.0  0.0 │
└           ┘

ghci has muddied that up a little for us with the Either and converting our elements to Fractional, but it's clearly \([[-1,1],[1,0]]\), as we can verify. Since we know the other \(B_{\mu}\)'s (\(\mu \in \{a, b, c, d\}\)) can be generated by left- and right- multiplication by \(J_2\) and since \(J_2^\intercal=J_2\), we know we can find the other inverses likewise.

This explains why we haven't encountered the inverses: the elements of any member of our monoid \(\mathbf{\{I_2, J_2, B_\mu\}}\) are nonnegitive. What would happen if we were to allow -1 as a value, in addition to 0 and 1? This increases the problem space from 16 matrices to \(3^4=81\), of which we know at least 10, but no more than 71 to be invertible. We can find the actual number by a slight modification of our first snippet:

Prelude Data.Matrix> let s = [-1..1]
Prelude Data.Matrix> length $ filter (not . isSingular) [(a, b, c, d) | a <- s, b <- s, c <- s, d <- s]
48

That's more than I might have thought! It's curious that \(16/27\ \ (\approx 0.593)\) of the \([-1,0,1]\) matricies are invertible compared to only \(3/8\ \ (=0.375)\) of the \([0,1]\)'s. One must wonder what that function is like for other sets of integers. It's about time to put a bow on this blog post, but there are some other questions that seem to me obvious from this line of inquiry:

1. Of the 38 "new" invertible matrices, which, if any, are generated from our initial set \(\mathbf{\{I_2, J_2, B_\mu\, B_\mu^{-1}\}}\)?

   What other characteristics lead to this determination? Does this reasoning extend to other invertible matricies with integral entries?

2. What about the \(3\times3\) case, the \(4\times4\) case, and on up? It was cool running into \(\mathbf{Z_2}\), even if that's a somewhat degenerate structure. We'd expect the permutation matrices to form group structures in higher-dimensioned matricies, but are there others? Checking \(2^n\) matrices gets prohibitive very quickly, even if those checks themselves were \(\mathcal{O}(1)\) (which, in point of fact, they're very much not). What deeper relationships exist to help us out?

Conclusion

Strang is very explicit in his preface that the book is to be used as I am using it: that exercises are meant to fill a dual role of providing practice while anticipating and foreshadowing concepts to come. I find this characteristic of MIT OpenCourseWare: that the pedagogy makes even lower-division undergraduate materials exciting and challenging, even in fields in which I feel myself relatively accomplished. This speaks (unsurprisingly) highly of the quality of the institution and the faith they're able to place in their undergraduates.

So, on the one hand, it's cool to be able to jump into a simple-but-interesting problem like this and run it to some conclusion. On the other, I can't help feeling a bit foolish, like the answers to the questions I'm inventing would be answered if I'd just pressed on with the next chapter or two instead of digressing down this tack.

Back to the first hand, we have shown something in the way of how useful the tools of Modern Algebra are at investigating different domains, even if Linear Algebra is customarily taught first.

Notes