The Mandelbear's Musings

1: The Turing Machine

So, Wednesday I looked at Wikipedia's front page and saw, under the "On this day" heading:

1936 – English mathematician Alan Turing published the first details of the Turing machine (model pictured), an abstract device that can simulate the logic of any computer algorithm by manipulating symbols.

It was the ""model pictured" that grabbed me. The caption was/is "A physical Turing machine model. A true Turing machine would have unlimited tape on both sides, however, physical models can only have a finite amount of tape."

I knew that -- everyone who studies computer science knows that, and a few have dreamed, as I had, of building a physical model. I even figured out how to build one out of wood, minus a few details. But there it was.

(If you're not interested in the details, you can skip this and the other indented blocks. But I digress...)

A Turing Machine is a remarkably simple device. It has a read head, a write head, a strip of tape that they operate on, and a controller with a finite number of states. It can read what's on the tape -- the classic machine uses blank, "0", and "1". (Some versions use "X" instead of "1", and some dispense with "0" and just have 1 and blank. That makes programming them a little more complicated, but not by much. Some have more symbols. It doesn't matter -- you can program around it.) The machine can move the tape backward and forward. Numbers are usually represented in Unary, so you count "1", "11", "111", ..., although with both 1 and 0 you could use binary, and some versions do.

The machine has a "state", which selects a line in the machine's program that tells it what to write, which direction to move the tape, and which state to go to next, depending on what symbol the read head is looking at. (Think of the table as a drum with pegs on it, like a music box.)

That's it. That's all you need to compute any function that can be computed by any kind of mechanical or digital computer. Of course you may need a lot of tape -- so you need to attach it to a tape factory -- and a lot of time.

The critical thing is that it's possible to design a universal Turing machine: it takes a tape, and the state table of a Turing machine (in 1's, 0's and blanks), and it uses that description to do exactly what that machine is programmed to do. Turing's big accomplishment was using the universal Turing machine to prove that there some things that a computer can't do, no matter how much time and tape you give it.

But of course I was much more fascinated by the machines, starting at the website of the model that first grabbed my attention., and proceeding to a Turing machine made of legos. I spent some time in the Turing machine gallery. But the rabbit hole went deeper than that.

2: The Universal Constructor

At about that point it ocurred to me to look at the Wikipedia page for the Von Neumann universal constructor. Because once you have a kind of machine that can simulate itself, the natural question is whether you can have a machine that can build a copy of itself.

The trivial answer to this question is "Yes, of course. Cells have been reproducing themselves for billions of years." But in the 1940s when von Neumann was thinking about this, the structure of DNA had not yet been determined -- that was 1953 -- and although it had been known since the late 1920s that DNA had something to do with heredity, nobody knew how it worked. So his insight into the machinery of reproduction was pretty remarkable.

Like Turing's insight into the machinery of computation, von Neumann's insight into the machinery of reproduction was to separate the machine -- the Universal Constructor -- from the description of what it was to construct, stored on something simple -- a tape.

Von Neumann's machine was/is a cellular automaton; it "lived" (if you can call it that) on a grid of squares, where each square can be in one of 29 different states, with rules that tell it what to do depending on the states of its neighbors. A completely working machine wasn't simulated until 1995. Its constructor had 6329 32-state cells, and a tape with a length of 145,315. It took it over 63 billion timesteps to copy itself. (Smaller and faster versions have been constructed since then).

At, say, 1000 steps/second, that would have taken over two years. It wasn't until 2008 that a program, Golly, became able to simulate it using the hashlife algorithm; it now takes only a few minutes.

Which led me even further down the rabbit hole. Because no discussion of cellular automata would be complete without Conway's Game of Life.

3: The Game of Life

It's not really a game, of course, it's a cellular automaton. Each cell in the square grid is either dead or alive. You start with an arrangement of live cells, and turn them loose according to four simple rules:

1. If a live cell has fewer than two live neighbors (out of the 8 cells surrounding it), it dies of loneliness.
2. A live cell with two or three live neighbors, stays alive.
3. A live cell with more than three live neighbors dies of overpopulation.
4. A dead cell with exactly three live neighbors becomes live.

I first encountered the game in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column. The Wikipedia article gives a good introduction.

Patterns in Life evolve in a bewildering variety of ways. Many of them die out quickly -- an isolated cell, for example. Some patterns sit there and do nothing -- they're called "still lifes". A 2x2 block of cells for an example. Some blow up unpredictably, and may or may not leave a pile of random still lifes behind. Some patterns oscillate: a horizontal row of three cells will become a vertical row in the next turn, and vice versa -- it's called a "blinker".

And some patterns move. The simplest, called a "glider", appears in this post's icon. You can crash gliders into blocks or gliders into gliders, and depending on the timing they will do different interesting things. It didn't take people long to figure out that you can build computers, including a universal Turing machine. Or a machine that prints out the digits of Pi.

Or a universal constructor.

4: The universal constructor

While I was falling into this rabbit hole, I happened to remember a passing mention of a universal constructor that can build anything at all out of exactly 15 gliders. (Strictly speaking, anything that can be constructed by crashing gliders together. Some patterns can't be made that way. But almost all the complicated and interesting ones that people are building these days can.) If this intrigues you, go read the article. Or wait until the next section, where I finally get to the bottom of the rabbit hole.

On the way down I encountered lots of weird things -- the aforementioned universal Turing machine and Pi printer, and a variety of "spaceships" that travel by, in effect, repeatedly constructing a new copy of themselves, then cleaning up the old copy. It took a while for me to get my head around that.

Then, sometime Wednesday evening, I found the book.

5: The Book of Life

It's not called "The Book of Life", of course, it's called Conway's Game of Life: Mathematics and Construction. But you get the idea. You can download the PDF.

The book ends with a pattern that simulates a Life cell. There are several different versions of this; this is the latest. It works by making copies of itself in any neighboring cells that are coming alive, then destroying itself if it's about to die. Wild.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

According to this article posted yesterday on Ars Technica, there is a major security hole in Zoom for the Mac. Zoom issued a security bulletin on Saturday. The article suggests that you should download the update directly from Zoom or click on your menu bar options to "Check for updates" rather than waiting for the auto-update, although if you've already updated since Saturday you're probably ok.

The article goes into more detail; tl;dr is that Zoom's installer is owned by and runs as root, and has a major bug that allows unsigned updates to be installed.

Resources

• Download Center - Zoom
• Zoom security bulletin ZSB-22018 08/13/2022
• Update Zoom for Mac now to avoid root-access vulnerability | Ars Technica

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

This post in Krebs on Security describes an unusual and potentially very dangerous attack technique that can be used to sneak evil code past code reviews and into the supply chain. Briefly, it allows evildoers to write code that looks very different to a human and a compiler. It should probably come as no surprise that it involves Unicode, the same coding standard that lets you make blog posts that include inline emoji, or mix text in English and Arabic.

In particular, it's the latter ability that the vulnerability targets, specifically Unicode's "Bidi" algorithm for presenting a mix of left-to-right and right-to-left text. (Read the Bidi article for details and examples -- I'm not going to try plopping random text in languages I don't know into the middle of a blog post.)

Now go read the "Trojan Source Attacks" website, and the associated paper [PDF] and GitHub repo. Observe, in particular, the Warning about bidirectional Unicode text that GitHub now attaches to files like this one in C++. Observe also that GitHub does not flag files that, for example, mix homoglyphs like "H" (the usual ASCII version) and "Н" (the similar-looking Cyrillic letter that sounds like "N"; how similar it looks depends on what font your browser is using). If you're unlucky, you might have clicked on a URL containing one or more of these, that took you someplace unexpected and almost certainly malicious.

The Trojan Source attack works by making use of the control characters U+202B RIGHT-TO-LEFT EMBEDDING (RLE) and U+202A LEFT-TO-RIGHT EMBEDDING (LRE), which change the base direction explicitly.

And remember: ШYSINAШYG - What You See Is Not Always What You've Got!

Resources

• Trojan Source Attacks
• here [PDF] ( BibTex )
• ‘Trojan Source’ Bug Threatens the Security of All Code – Krebs on Security
• nickboucher/trojan-source: Trojan Source: Invisible Vulnerabilities
• Warning about bidirectional Unicode text | GitHub Changelog
• Unicode Bidirectional Algorithm basics
• but... research!rsc: On “Trojan Source” Attacks

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

A rather mixed bag of things that, arguably, I should have written about a week ago.

1: the Let's Encrypt root certificate.

Hopefully this won't affect you, but if your browser starts complaining about websites suddenly being untrusted, you need to upgrade. The problem is that Let's Encrypt's root certificate is expiring, and will be replaced by a new one (see the link above for details). Starting October 1^st, browsers and other programs that rely on the old cert will have problems if they haven't been upgraded in the last year.

You keep your OS and your browser up to date, right? There are some old apps and operating systems that are no longer receiving upgrades, and so won't know about the new root cert. Specifically, if you're using one of these products:

OpenSSL <= 1.0.2, Windows < XP SP3, macOS < 10.12.1, iOS < 10 (iPhone 5 is the lowest model that can get to iOS 10), Android < 7.1.1 (but >= 2.3.6 will still mostly work), Mozilla Firefox < 50, Ubuntu < 16.04, Debian < 8, Java 8 < 8u141, Java 7 < 7u151, NSS < 3.26, Amazon FireOS (Silk Browser).

Possibly, Cyanogen > v10, Jolla Sailfish OS > v1.1.2.16, Kindle > v3.4.1, Blackberry >= 10.3.3, PS4 game console with firmware >= 5.00, IIS

(You can probably uptrade to the newest Firefox or switch to a recent version of Chrome, which will restore your ability to browse the web, but a few other things might still fail. (For example, Firefox will keep working on my ancient Mac Mini, but Safari probably won't.)

The following articles go into a lot more detail; you can get a good overview from the first two:

Smart TVs, fridges and light bulbs may stop working next year: Here's why An Internet of Trouble lies ahead as root certificates begin to expire en masse, warns security researcher • The Register The Impending Doom of Expiring Root CAs and Legacy Clients Let's Encrypt's Root Certificate is expiring! Certificate Compatibility - Let's Encrypt

2. Phillips Respironics CPAP recall:

If you're using a CPAP made by Phillips Respironics, hopefully you've already seen the Recall Notification [PDF]. I missed it, through my habit of ignoring notifications in the Dreamstation app and website. The email I got from Medicare says:

If you own or rent one of the Philips products that was recalled, talk to your doctor as soon as possible about whether to continue using your recalled equipment. If you would like to replace or repair your equipment, the supplier you bought the equipment from is responsible for replacing or repairing rental equipment at no cost to you when the equipment is less than 5 years old.

If, like me, you insist on continuing to use your facehugger, install an antibacterial filter, which will keep little bits of soundproofing foam out of your lungs. This is probably only necessary if you've been using ozone to clean your device, but I decided not to take chances.

3. Chevrolet Bolt EV recall:

If you own a Bolt, you should have received several letters about this recall. Hopefully you haven't been throwing them away unread, but if you have, you'll want to enable "hilltop reserve" to limit your charging to 90%, don't run your battery down below about 70 miles, park outside immediately after charging, and don't leave your Bolt charging indoors overnight. "Experts from GM and LG have identified the simultaneous presence of two rare manufacturing defects in the same battery cell as the root cause of battery fires in certain Chevrolet Bolt EVs." You don't want to take chances with battery fires. They're nasty; lithium is perfectly capable of burning under water.

Be safe out there.

On a more hopeful(? helpful, at least) note, dialecticdreamer has posted Demifiction: Breaking Omaha!, which despite being set in a fictional universe contains a lot of practical advice for disaster preparedness.

If you happen to be the administrator of a Microsoft Exchange Server that can be accessed from the internet, you need to immediately

1. Apply the patches that Microsoft released on Tuesday: Multiple Security Updates Released for Exchange Server – updated March 5, 2021 – Microsoft Security Response Center
2. Use this script (on GitHub) to scan your logs, as described in HAFNIUM targeting Exchange Servers with 0-day exploits - Microsoft Security to determine whether you are one of the at least 30,000 organizations that have been hacked via the holes you just patched (see Step 1). (You did patch them, right?) If you are,...
3. Figure out what it means to your organization that all of your organization's internal email is now sitting on a disk somewhere in China. If that sounds like A Very Bad Thing,...
4. Panic.

Resources

• At Least 30,000 U.S. Organizations Newly Hacked Via Holes in Microsoft’s Email Software — Krebs on Security
• Microsoft: Chinese Cyberspies Used 4 Exchange Server Flaws to Plunder Emails
• HAFNIUM targeting Exchange Servers with 0-day exploits - Microsoft Security
• Multiple Security Updates Released for Exchange Server – updated March 5, 2021 – Microsoft Security Response Center
• Operation Exchange Marauder: Active Exploitation of Multiple Zero-Day Microsoft Exchange Vulnerabilities | Volexity

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

I've always been a little uncomfortable about build systems and languages that start the build by going out to a package repository and pulling down the most recent (minor or patch) version of every one of the package's dependencies. Followed by all of their dependencies. The best-known of these are probably Python's pip package manager, Javascript's npm (node package manager), and Ruby's gems. They're quite impressive to watch, as they fetch package after package from their repository and include it in the program or web page being built. What could possibly go wrong?

Plenty, as it turns out.

The best-known technique for taking advantage of a package manager is typosquatting -- picking a name for a malware package that's a plausible misspelling of a real one, and waiting for someone to make a typo. (It's an adaptation of the same technique from DNS - picking a domain name close to that of some popular site in hopes of siphoning off some of the legitimate site's traffic. These days it's common for companies to typosquat their own domains before somebody else does -- facbook.com redirects to FB, for example.)

A few days ago, Alex Birsan published "Dependency Confusion: How I Hacked Into Apple, Microsoft and Dozens of Other Companies", describing a new attack that relies on the way package managers like npm resolve dependencies, by looking for and fetching the most recent compatible version (i.e. with the same major version) of every package, and the fact that they can be made to look in more than one repository.

Fetching the most recent minor version of a package is usually perfectly safe; packages have owners, and only the owner can upload a new version to the repository. (There have been a few cases where somebody has gotten tired of maintaining a popular package, and transferred ownership to someone who turned out to be, shall we say, less than reliable.)

The problem comes if, like most large companies and many small ones, you have a private repository that some of your packages come from. The package manager looks in both places, public and private, for the most recent version. If an attacker somehow gets the name and version number of a private package that doesn't exist in the public repository, they can upload a bogus package with the same name and a later version.

It turns out that the names and versions of private packages can be leaked in a wide variety of ways. The simplest turns out to be looking in your target's web apps -- apparently it's not uncommon to find a copy of a `package.json` left in the app's JavaScript by the build process. Birsan goes into detail on this and other sources of information.

Microsoft has published 3 Ways to Mitigate Risk When Using Private Package Feeds, so that's a good place to look if you have this problem and want to fix it. (Hint: you really want to fix it.) Tl;dr: by far the simplest fix is to have one private repo that includes both your private packages, and all of the public packages your software depends on. Point your package manager at that. Updating the repo to get the most recent public versions is left as an exercise for the reader; if I was doing it I'd just make a set of dummy package that depend on them.

Happy hacking!

Resources

• Dependency Confusion: How I Hacked Into Apple, Microsoft and Dozens of Other Companies | by Alex Birsan | Feb, 2021 | Medium
• Researcher hacks over 35 tech firms in novel supply chain attack
• 3 Ways to Mitigate Risk When Using Private Package Feeds
• CVE-2021-24105 - Security Update Guide - Microsoft - Package Managers Configurations Remote Code Execution Vulnerability
• incolumitas.com – Typosquatting programming language package managers
• Semantic Versioning 2.0.0

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

You may remember this post about renaming the default branch in Git repositories. Since then I've done some script writing -- they say you don't really understand a process until you can write a program that does it, and this was no exception. (There are lots of exceptions, actually, but that's rather beside the point of this post...)

Anyway, here's what I think is the best way to rename master to main in a clone of a repository where that rename has already been done. (That's a common case anywhere you have multiple developers, each with their own clone, or one developer like me who works on a different laptop depending on the time of day and where the cats are sitting.)

     git fetch
     git branch -m master main
     git branch -u origin/main main
     git remote set-head origin main
     git remote prune origin

The interesting part is why this is the best way I've found of doing it: 1. It works even if master isn't the current branch, or if it's out of date or diverged from upstream. 2. It doesn't print extraneous warnings or fail with an error. Neither of those is a problem if you're doing everything manually, but it can be annoying or fatal in a script. So here it is again, with commentary:

git fetch -- you have to do this first, or the git branch -u ... line will fail because git will think you're setting upstream to a branch that doesn't exist on the origin.

git branch -m master main -- note that the renamed branch will still be tracking master. We fix that with...

git branch -u origin/main main -- many of the pages I've seen use git push -u..., but the push isn't necessary and has several different ways it can fail, for example if the current branch isn't main or if it isn't up to date.

git remote set-head origin main -- This sets main as the default branch, so things like git push will work without naming the branch. You can use -a for "automatic" instead of the branch name, but why make git do extra work? Many of the posts I've seen use the following low-level command, which works but isn't very clear and relies on implementation details you shouldn't have to bother with:

    git symbolic-ref refs/remotes/origin/HEAD refs/remotes/origin/main

git remote prune origin -- I've seen people suggesting git fetch --prune, but we already did the fetch way back in step 1. Alternatively, we could use --prune on that first fetch, but then git will complain about master tracking a branch that doesn't exist. It still works, but it's annoying in a script.

Just as an aside because I think it's amusing: my former employer (a large online retailer) used and probably still uses "mainline" for the default branch, and I've seen people suggesting as an alternative to "main". It is, if anything, more jarring than "master" for someone who has previously encountered "mainlining" only in the context of self-administered street drugs.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

If you've been paying attention to the software-development world, you may have noticed a movement to [remove] racist terms in tech contexts. The most obvious such terms are "master" and "slave", and there are plenty of good alternatives: primary/secondary, main/replica, leader/follower, etc. The one that almost every software developer sees every day is Git's "master" default branch. This issue on GitLab includes some good discussion of what makes "main" the best choice for git. (I've also seen "mainline" used.)

Renaming your master branch is easy. If you have a local repo that isn't a clone of anything (so it doesn't have any remotes), it's a one-liner:

   git branch -m master main

Renaming the default branch on an existing repo is trivial. If it has no remotes, for example if it's purely local or a shared repo on a server you have an ssh account on, it's a one-liner:

   git branch -m master main

It's a little more complicated for a clone, but not much more complicated:

   git branch -m master main
   git push -u origin main
   git symbolic-ref refs/remotes/origin/HEAD refs/remotes/origin/main
   git pull

What you need to do at this point depends on where your origin repo is located. If you've already renamed its default branch, you're done. If you haven't, the git push -u created it. At this point if your origin repo is on GitHub, need to log in and change its default branch from master to main because it won't let you delete its default branch.

Then, delete the old master branch with

   git push --delete master

This works for simple cases. It gets a little more complicated on GitHub because you might have web hooks, pull requests, and so on that still refer to master. GitHub says that renaming master will be a one-step process later in the year, so you may want to wait until then. For less complicated situations, any URLs that reference master will get automatically redirected to main. See this page for details.

I had a slightly different problem: my shared repositories are on my web host, and there are hook scripts that pull from the shared repo into the web directory. My version of the post-update only looks for changes in the master branch. Fortunately that's a one-liner, too:

   ssh HOST sed -i -e s/master/main/g REPO/hooks/post-update

The next problem is creating a new repo with main as the default branch. GitHub already does this, so if you are starting your project there you're good to go. Otherwise, read on:

The Git project has also added a configuration variable, init.defaultBranch, to specify the default branch for new repositories, but it's probably not in many distributions yet. Fortunately, there's a workaround, so if you don't want to wait for your distribution to catch up, you can take advantage of the way git init works, as described in this article by Leigh Brenecki:

1. Find out where Git keeps the template that git init copies to initialize a new repo. On Ubuntu, that's /usr/share/git-core/templates, but if it isn't there look at the man page for git-init.
2. Copy it to someplace under your control; I used .config/git/init-template.
3. cd to the (new) template and create a file called HEAD, containing ref: refs/heads/main.
4. Set the init.templateDir config variable to point to the new template.

Now when git wants to create a new repo, it will use HEAD to tell it which branch to create. Putting all that together, it looks like:

   cp -a /usr/share/git-core/templates/ ~/.config/git/init-template
   echo ref: refs/heads/main > ~/.config/git/init-template/HEAD
   git config --global init.templateDir ~/.config/git/init-template

You can actually replace that initial copy with mkdir; git is able to fill in the missing pieces. Alternatively, you can add things like a default config file, hooks, and so on.

(I've already updated my configuration repository, Honu, to set up the modified template along with all the other config files it creates. But that probably doesn't help anyone but me.)

Resources

• Removing racist terms in tech | Go Make Things
• How to rename your default GitHub branch to main | Go Make Things
• web tool: Rename GitHub Default Branches
• 5 steps to change GitHub default branch from master to main | Steven M. Mortimer
• github: Guidance for changing the default branch name for GitHub repositories -> there will be a seamless 1-step process later this year.
• Links to deleted branches now redirect to the default branch - GitHub Changelog
• Easily rename your Git default branch from master to main - Scott Hanselman
• Git: Renaming the "master" branch - DEV -> instructions for github and gitlab
• Change the default initial branch name for new projects on GitLab (#221164)
• Changing the default branch for new Git repositories — Leigh Brenecki
• Change Default branch in gitlab - Stack Overflow

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

NaBloPoMo stats:
   2146 words in 4 posts this month (average 536/post)
    814 words in 1 post today

I really need to write my memoirs, preferably before my memory deteriorates to the point where I can't. (I am inspired by my mom, who published the third edition of hers last year.) I have, however, given up on the idea of following the King of Hearts' advice to "begin at the beginning, [...] and go on till you come to the end: then stop". (I note in passing that I haven't come to the end yet.) So I'm just going to dive in at whatever point seems interesting at the moment. I'll tag these by year, so that anyone interested (possibly as many as two of you) can sort them out later.

This particular point was suggested by somebody's mention of their Erdős number, so I suppose I ought to explain that first. Content Warning: contains math, which you can safely skip over if you're math-phobic. Deciding which parts to skip is left as an exrcise for the reader.

You have perhaps heard of the parlor game called "Six Degrees of Kevin Bacon", based on the concept of "six degrees of separation". The idea is to start with an actor, and figure out the shortest possible list of movies that links them with Kevin Bacon. The length of that list is the actor's "Bacon number", with Bacon himself having the number zero, anyone who acted in a movie with him having the number one, and so on. As far as I know I don't have a finite Bacon number, but it's not outside the realm of possibility if, as most people do, you include TV shows and so on. I think I've been in at least one brief local TV news item.

But sometime during my senior year at Carleton College, I co-authored a paper with one of my math professors, Ken Wegner, which gave me an Erdős number of 7. The paper, published in 1970 in The American Mathematical Monthly, was "Solutions of Φ(x) = n , Where Φ is Euler's Φ-Function" [Wegner, K., & Savitzky, S. (1970), The American Mathematical Monthly, 77(3), 287-287. doi:10.2307/2317715].

So now I have three things to explain: What is an Erdős number? What is Euler's Φ function? And finally, What was my contribution to the paper?

Erdős number: As you might expect from the introduction about the Bacon Number, a mathematician's Erdős number is the smallest number of co-authored papers connecting them to Paul Erdős (1913–1996), an amazingly prolific (at least 1,525 papers) 20th Century mathematician. He spent the latter part of his life living out of a suitcase, visiting his over 500 collaborators (who thus acquired an Erdős number of 1. The Erdős number was first defined in print in 1969, so about the time I was collaborating with Wegner on Euler's Φ function.

Euler's Φ function, Φ(n), also called the Totient function, is defined as the number of positive integers less or equal to n that are relatively prime to n; or in other words the numbers in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n,k) = 1. (You will also see it written in lower-case as "φ", or in Latin as "phi".)

The totient function is pretty easy to compute, at least for sufficiently small numbers. The inverse is rather less straightforward, and has been the subject of a considerable number of StackExchange queries. (This answer includes a good set of links.) I was thinking of including some detail about that, and was barely able to keep myself from falling down the usual rabbit-hole, which almost always ends up somewhere in group theory. For example, φ(n) is the order of the multiplicative group of integers modulo n. See what I mean?

My contribution to the paper was not very closely related to the actual mathematics of the problem; what I did was write the computer program that computed and printed out the table of results. That involved a hack. A couple of hacks, actually.

In 1969, Carleton College's computer lab contained an IBM 1620 and a couple of keypunches. The 1620 was fairly primitive even by 1960s standards; its memory consisted of 20,000 6-bit words, with a cycle time of 20 microseconds. Each word contained one BCD-coded decimal digit, a "flag" bit, and a parity check bit. It did arithmetic digit-by-digit using lookup tables for addition and multiplication. It was not particularly fast -- about a million times slower than the CPU in your phone. But it was a lot of fun. Unlike a mainframe, it could sit in one corner of a classroom (if it was air-conditioned), it was (comparatively) inexpensive, and it could stand up to students actually getting their hands on it.

A lot of the fun came from the fact that the 1620's "operating system" was the human operator sitting at the console, which consisted mainly of an electric typewriter and a row of buttons and four "sense switches" that the program could read. If you wanted to run a program, you put a stack of punched cards into the reader and pushed the "load" button, which read a single 80-column card into the first 80 characters of memory, set the program counter to zero, and started running. My program was written in FORTRAN. Not even FORTRAN II. Just FORTRAN.

Computing the table that occupied most of the paper took about a week.

Here's where it gets interesting, because obviously I wasn't the only student who wanted to use the 1620 that week. So I wrote an operating system -- a foreground/background system with my program running in the background, with everyone else's jobs running in the "foreground". That would have been easy except that the 1620 could only run one program at a time. Think about that for a moment.

My "operating system" consisted mainly of a message written on the back of a Hollerith card that said something like: "Flip sense switch 1 and wait for the program to punch out a deck of cards (about a minute). When you're done, put the deck in the reader and press LOAD."

Every time the program went around its main loop, it checked Sense Switch 1, and if it was set, it sent the contents of memory to the card punch. Dumping memory only took one instruction, but it wasn't something you could do from FORTRAN, so I put in a STOP statement (which FORTRAN did have) and changed it to a dump instruction. By scanning the program's object code (remember this is a decimal machine; an instruction took up 12 columns on the card) and replacing the HALT instruction with DUMP.

It worked.

    MR: Collaboration Distance
     MR Erdos Number = 7
     S. R. Savitzky 	  coauthored with    Kenneth W. Wegner 		MR0260667
     Kenneth W. Wegner 	  coauthored with    Mark H. Ingraham 		MR1501805
     Mark H. Ingraham 	  coauthored with    Rudolph E. Langer 		MR1025350
     Rudolph E. Langer 	  coauthored with    Jacob David Tamarkin 	MR1501439
     Jacob David Tamarkin coauthored with    Einar Hille 	        MR1555331
     Einar Hille 	  coauthored with    Gábor Szegő 	        MR0008279
     Gábor Szegő 	  coauthored with    Paul Erdős 	        MR0006783
     MR0260667 points to: K. W. Wegner and S. R. Savitzky, (1970)
     Solutions of φ (x) = n, Where φ is Euler's φ-Function on JSTOR,
     The American Mathematical Monthly, 77(3), 287-287.
     DOI: 10.1080/00029890.1970.11992471.

There are two other numbers of interest: the Shūsaku Number, measuring a Go player's distance from the famous 19th-Century Go player Hon'inbō Shūsaku, and the Sabbath Number, measuring a musician's distance from the band Black Sabbath. I'm pretty sure I have a Sabbath number through filkdom. I definitely have a Shūsaku number of 5 from having lived down the hall from Jim Kerwin, Shūsaku Number 4, my sophomore and junior years at Carleton. That's another story.

And if I expect to write more journal entries about math, I'm going to have to extend my posting software to allow entries written in LaTeX. Hmm.

The Mandelbear's Memoirs

For some time now I've been eyeing Lenovo's ThinkPad Compact Bluetooth Keyboard with TrackPoint with a mixture of gadget lust and skepticism -- most of the reviews I saw said that the Bluetooth connection had a tendency to be laggy. Combined with the amount of trouble I've been having with Bluetooth on Linux Mint lately, and the lack of a USB connection, and the high price, it's been pretty far down on my list of things to buy.

Anyone who knows my fondness for addiction to Thinkpad keyboards can figure out what was going to happen when Lenovo came out with the ThinkPad TrackPoint Keyboard II, featuring both Bluetooth and a wireless USB dongle, but otherwise looking almost exactly like my wired KU-1255 keyboard and the keyboards on most of my Thinkpad laptops. I discussed that in "The Curmudgeon Contemplates Keyboards", a couple of weeks ago.

It arrived yesterday, much sooner than I'd expected. It's lovely, and just about what I expected. It's hard to go wrong with a Thinkpad keyboard.

Being nearly icon-blind it took me a while to puzzle out the switches, because the quick-start sheet had nothing but a few pictures to explain them. It didn't say anything at all about the "Android/Windows" switch. So I went looking on their tech support website and found nothing but a PDF of the quick-start. Not helpful. (After a day and a half I found a review that explained that it gives F9-F12 Android-specific functions, and indeed I was eventually able to make out the tiny markings above them on the beveled edge of the bezel.)

The website -- and most of the reviews -- also mentioned its support for "6-point entry for the visually impaired", but DDG and Google found nothing except references to this keyboard. Braille, maybe? Whatever. There's nothing about it on the tech-support site.

There are some things I really appreciate as a cat's minion. It's exactly the right size to sit on top of my laptop (Sable is a Thinkpad X230; the keyboards are almost identical) with the lid closed and an external monitor plugged in. If a cat shows signs of wanting to sit on it, I can set it aside (or close the lid), and pick it up later. (I broke the micro-USB connector on one of my wired Thinkpad keyboards, because I often flip it up behind the laptop with the keys away from me -- and the cat.) If a cat does sit on it, the on-off switch is easily reachable on the right-hand side. Much easier than unplugging the cable.

So let's sum up. On the positive side: the wireless USB, Bluetooth, the classic ThinkPad feel and layout, the TrackPoint nub, and two of the three buttons are exactly as I would expect. (The middle button is in the same plane as the two side buttons, and the raised dots are much lower and are no longer blue.) The charging connector is USB-C. I haven't used it long enough to evaluate battery life, but it's been on since yesterday and claims to be at 99%; Lenovo claims two months, so that's believable. It's just the right size to sit on an ultrabook like a Thinkpad X230 with the lid closed.

I'm not sure whether to count the low-contrast markings on the function keys as positive or negative. I've pretty-much abandoned my old emacs key-bindings for them, and some of the functions indicated by the icons are actually useful. I'll get out my label-maker, or label them with white-out.

On the negative side: the USB cable is just for charging. For goodness' sake, how much circuitry would it have taken for it to make that a third connection mode? The documentation is sketchy -- the QuickStart page is nothing but icons and arrows, and for an icon-impaired curmudgeon that's a bit of a problem. Nowhere in the documentation does it explain what the Android/Windows switch is for. There's nothing on Lenovo's tech support website, either. There's no backlight, and the function keys are labeled with low-contrast tiny letters. The dongle is, of course, incompatible with Logitech's, so it uses another USB port. (This is a minor quibble, because I had the slot I unplugged the old keyboard from.)

Some people would make the position of the Fn key, to the left of Ctrl, as a problem. They might also complain about the Page Up and Page Down keys' flanking the Up-Arrow in the inverted T arrangement. Since I've be using Thinkpads since sometime in the last Millennium, and the new page-up/page-down positions for 95% of the last decade, I don't have a problem with either of those -- they're exactly what I want. Some people would miss the trackpad and palm rest; I've been using a wired but otherwise identical keyboard for years, and don't miss them. Your mileage may vary.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

Not a good week. Not horrible, either, by contemporary standards, but Colleen spent Monday through Thursday in the hospital with another UTI, and the air quality has gotten progressively worse. Up until today Whidbey Island -- or at least the Oak Harbor measuring station -- has had a slightly lower AQI than most of the surrounding measurements, but today it's solidly up into "Unhealthy" (around 185, though it depends somewhat on which map you're looking at and how you interpolate; the Washington department of Ecology's map has it in the mid-to-high 200s, which is Very Unhealthy). Parts of Seattle are up into the Hazardous range. "Don't breathe anything you can see" -- good advice if you can manage it. I can't.

I've been making progress on upgrading (laptop)Sable to a 1TB SSD and three distributions (Mint/MATE, LMDE/Cinnamon, and UbuntuStudio/Xfce4). The main obstacles are the fact that Mint and UStudio both identify themselves as "ubuntu", so their boot/efi information clobber one another, and the fact that a lot of my setup for (window manager)Xmonad was based on Gnome, which doesn't play well with MATE or Xfce. And some of it was based on the (previously-valid) assumption that I would need only one set of config files per machine. Working on it, and (setup manager)Honu will be the better for it when I'm done. Hopefully this week. I also expect to get a few curmudgeon posts out of it.

I have not been singing nearly as much as (I feel that) I should be. A lot less than is good for me. This is, sadly, typical.

( Notes & links, as usual )

...about disk partitioning. Content warning: rather specialized geekness. If that's not something you're into, you might want to skip this.
( tl;dr )

  Dreamwidth makes an excellent rubber duck -- thanks for listening.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

Hmm. File corruption on (laptop)Sable, political corruption (a given these days), some interesting debugging on (temporary replacement laptop) Raven, singing, no walking to speak of, Colleen doing her exercises, Colleen's usual medical problems and some less usual ones, deli sandwiches by curbside pickup, killer hurricane, killer cops,... FSCK (literally as well as indirectly figuratively).

Oh yeah, almost forgot -- C.D.C. Now Says People Without Covid-19 Symptoms Do Not Need Testing (via siderea | How Can You Tell the CDC is Lying? Their Lips Are Moving.)

The usual mixed week, here at this end of the Rainbow Caravan.

( Notes & links, as usual )

If you happen to be running a Windows DNS server, I hope you have automatic updates enabled. Today's security update fixes CVE-2020-1350, also known as SigRed: A 17-year-old 'wormable' vulnerability for hijacking Microsoft Windows Server. I think that title kind of says it all, doesn't it? For the record, it's a heap-based buffer overflow that can be triggered by a malicious DNS query, and it's described as "wormable", with a CVSS base score of 10.0. Wormable means that it can propagate itself and spread exponentially to other vulnerable servers.

It's not at all inaccurate to describe this as "COVID-19 for Windows DNS server". Go fix.

Resources

• July 2020 Security Update: CVE-2020-1350 Vulnerability in Windows Domain Name System (DNS) Server - Microsoft Security Response Center
• SigRed: A 17-year-old 'wormable' vulnerability for hijacking Microsoft Windows Server | ZDNet
• Patch all your Windows DNS servers - CVE-2020-1350 - CVSS score of 10 - Cyber Security - Spiceworks

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

Around the end of 2018 I wrote a Songs for Saturday post about my song "The World Inside the Crystal", which is about my -- I'm not sure what to call it: contention? belief? fantasy? -- that inside of computers is a world where magic works. I wrote the song itself in 1985, about the time my first kid was born. (I don't remember which came first.) Anyway, about four years later I wrote another: "Daddy's World". I sang it for my music teacher last Monday and she had some questions that made me realize that there are a lot of people, some of them no doubt on my reading list, who have no idea what it's referring to. Unless you had a Mac in your house before 1990 or thereabouts, have the definition of the Mandelbrot set memorized, and know a little about complex numbers, four-dimensional geometry, and integrated circuits, that may include you.

( Here there be lyrics, and footnotes. )

The recording of "Daddy's World" on YouTube comes from my CD, Coffee, Computers, and Song, and has my kids joining in on the chorus. Neither of them could sing all that well, but I really wanted them there. I don't seem to have it on any concert recordings -- sorry about that.

If your Windows 10 boxes -- all of them, both desktops and servers, didn't apply the update that came out Tuesday, go do that now. You can chase the references below while the update is downloading.

Here's what Microsoft said about it when they released the patch. There are more details in the resource list below. Some of those go on to link to proof-of-concept exploits. Good luck!

h/t to @thnidu.

Resources

• NVD - CVE-2020-0601
• Windows 10 Has a Security Flaw So Severe the NSA Disclosed It | WIRED
• CVE-2020-0601 | Windows CryptoAPI Spoofing Vulnerability
• January 2020 Security Updates: CVE-2020-0601 - Microsoft Security Response Center
• CVE-2020-0601: a critical Windows vulnerability discovered by…NSA!

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

I haven't put on my curmudgeon's hat in way too long. This isn't going to be a very long post, and if you don't know what a hash function is and what it's used for, all you need to do is make sure you're keeping up with security upgrades. Modern web browsers are already safe, and have been for the last three years or so; if you're still using a browser older than that, you should upgrade it. Some other programs in common use are not safe yet, so watch for security upgrades in the coming months.

If you're still with me, I just wanted to point the people who worry about such things at the latest vulnerability-with-a-catchy-name: SHA-1 is a Shambles. Tl;dr: the cost to construct a pair of different messages with the same SHA-1 hash has dropped to well under $100K worth of rented GPU time. Attacks still aren't exactly practical -- they used 900 GPUs for a couple of months -- but it's only a matter of time.

Section 7 of the paper [PDF] goes into detail on current usage of SHA-1 and what is being done about it. SHA-1 has been deprecated since 2011, and is no longer allowed in digital signatures. There are, however, still some older programs and protocols where it's an option, and X.509 certificates are still being issued with SHA-1 signatures (although modern browsers will reject them). They're being fixed, but you should make sure gpg, ssh, and web browsers are up to date, and if you're a developer, please stop using or accepting keys or certificates with SHA-1 signatures.

Git uses SHA-1 hashes to identify objects, and indirectly to sign commits. The developers are working on using longer hashes, and it now includes collision-detection; I'll be particularly interested in that work going forward.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

Today the computer curmudgeon talks about how he blogs.

I think it's widely known that I update this journal (and by that I mean both my Dreamwidth journal, which you are probably reading now, and my Computer Curmudgeon website), using a rickety combination of shell scripts and makefiles called MakeStuff. There are several good reasons for that. (Whether "because I can" is a good reason or not is debatable. There are others.)

A little over a year ago I made a planning post, and the "Where I am now" section remains a pretty good, albeit sketchy, description of the process. There's also an even sketchier one in the README file for MakeStuff/blogging. It had a list of what I wanted to do next, but essentially the only thing I've actually done is posting in either HTML or Markdown.

I have, however, reorganized things a bit, so that all of the relevant scripts are in MakeStuff/blogging -- the last part was moving in the script, now called charm-wrapper, that takes the post's metadata out of its email-like header and turns it into a command line for charm, a livejournal/dreamwidth posting client written in Python. It isn't a very good solution, but it works.

And since I'm running out of time to make a post today, I'm going to start this series with the other utilities in MakeStuff/blogging. And then go add this list to the README.

• check-html is a simple wrapper for html-tidy, a popular HTML syntax checker. Since it's not actually being used to fix syntax, it can play fast-and-loose with things like the header (it's just text) and blog-specific tags like <cut> and <user>. It handles those by putting a space after the "<" character. It would be trivial to add this to the make recipe for post.
• last-post is a site-scraper that returns the URL of your most recent post. It's useful, because charm doesn't return it. (I eventually put that functionality into charm-wrapper, but it's still useful. Eventually it wants to take a date on the command line.
• word-count is what I use to generate the NaBloPoMo statistics at the bottom of posts in November. (In other months, you just get a straight list; you can also get a listing for a whole year.)

NaBloPoMo stats:
     43 2019/11/01--rabbit-rabbit-rabbit.html
   1731 2019/11/02--s4s-memorials.html
   1465 2019/11/03--done-since-1027.html
    145 2019/11/04--i-ought-to-post-something.html
    430 2019/11/05--how-to-makestuff.html
-------
   3814 words in 5 posts this month (average 762/post)
    430 words in 1 post today

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

Wherein the curmudgeon cogitates out loud, and solicits suggestions.

Recently, my business (HyperSpace Express) checking account's balance has gone up considerably thanks to a writing gig. And the keyboard on my favorite laptop, a Lenovo X120e netbook called Cygnus, has been giving me trouble recently. It's developed a habit, which I think is thermal, of shutting down mid-boot. And last week random keys stopped working. I fixed that one -- nothing but a loose cable, (this time: it's on its second replacement keyboard) -- but not before I started looking at laptops again.

For quite a long time, the laptop I'd been considering lusting after as an upgrade has been the Lenovo X230. (The pointing stick and middle mouse button are required, along with an easy Linux install, so my choices are somewhat limited.) The X230 only slightly bigger than Cygnus, but a considerable upgrade: somewhat lighter, up to 16MB of RAM, a faster CPU, USB-3, and longer battery life are the main features I'd like to have. The fact that it has a docking connector that just happens to match a dock I have sitting around is a nice extra. They're available on eBay for anywhere between $150 and $400, depending on features, and can often be obtained defenestrated or with Windows 7. (I also considered the 220, which has the old-style beveled keys, but it has little else to recommend it. Besides, I'm used to the chicklets on Cygnus and I prefer the new layout.)

A few days ago, though, I made the mistake of also looking at the X1 Carbon series. It's tempting. First the negatives: it's bigger, with a 14" screen. It's more expensive -- more like the $300-600 range. It has less I/O -- you need a dongle for ethernet. The RAM is soldered on; you get your choice of 4 or 8 GB -- the 230 is upgradable to 16. Confusingly, it comes in a six different "generations" rather than having different model numbers; each generation has a different collection of I/O ports. The touchpad is larger than the one on the 230, which is a negative for a clumsy bear. It uses the M.2 form factor for SSDs, so I can't just take a drive out of any of my other laptops and stick it in. Windows 10 is standard. If you go for the "yoga" variant, which flips over to become a tablet, it's heavier.

On the other hand, it has a larger (16x9) screen, which would be especially nice for lyrics. The "yoga" version would be perfect on a music stand. It has somewhat better battery life than the 230. It comes standard with SSD. And it is, surprisingly, about half a pound lighter in the non-yoga flavor. Even the yoga is lighter than Cygnus. And although it doesn't have all the I/O I'd like to have, it's all I'm likely to need on a day-to-day basis. (The 4th generation, or the equivalent 1st generation yoga, looks like the sweet spot for I/O; it's pretty close to the 230.)

On the gripping hand, can I really justify having yet another laptop? I currently have five thinkpads (admittedly, one is old enough vote and has the Y2K bug, and the next oldest is also an IBM; the newest is currently out on loan), two other Lenovos, and a Dell netbook. I can't find my Asus Eeee, but I think it's around somewhere. (I didn't buy them all; I'm also the household's repair depot dumping ground for old computers.) But still. And I'd have to get new stickers.

There's also the question of what I want to do with yet another laptop I don't use on a daily basis. I already keep one in the bedroom. I could, of course, keep one on the desk and one in my backpack, but I'd have to take the backpack one out to sync it every time I left the house.

Buy one of each? ... ... see above, only doubled.

Sell one? Naaaaaaaaaaaaaaaaaaaaaa...

Resources

• Category:X1 Carbon - ThinkWiki
• Category:X230 - ThinkWiki

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

In my previous curmudgeon post, Writing Without Distractions, I gave version control only a brief mention, and promised a follow-up post. That would be this one. This post is intended for people who are not in the software industry, including not only poets but other writers, students, people who program as a hobby, and programmers who have been in suspended animation for the last decade or three and are just now waking up.

The Wikipedia article on version control gives a pretty good overview, but it suffers from being way too general, and at the same time too focused on software development. This post is aimed at poets and other writers, and will be using the most popular version control system, git. (That Wikipedia article shares many of the same flaws as the one on version control.) My earlier post, Git: The other blockchain, was aimed at software developers and blockchain enthusiasts.

What is version control and why should I use it?

A version control system, also called a software configuration management (SCM) system, is a system for keeping track of changes in a collection of files. (The two terms have slightly different connotations and are used in different contexts, but it's like "writer" and "author" -- a distinction without much of a difference. For what it's worth, git's official website is git-scm.com/, but the first line of text on the site says that "Git is a free and open source distributed version control system". Then in the next paragraph they use the initialism SCM when they want to shorten it. Maybe it's easier to type? Go figure.)

So what does the ability to "track changes" really get you?

( Quite a lot, actually! )

...and Finally

The part you've been waiting for -- the end. This post is already long, so I'll just refer you to the resources for now. Expect another installment, though, and please feel free to suggest future topics.

Resources

Tutorials

• git help tutorial and git help tutorial-2. You may also have the Git User's Manual installed on your computer.
• Everyday Git.
• Learn Enough Git to Be Dangerous. This is where I usually point newcomers to git. This is actually the third volume in the Learn Enough to Be Dangerous series; the first is about the command line and is a good place to start if you'rle a complete beginner with command-line tools.
• GitHub's Git and GitHub learning resources page has links to some good tutorials, too.
• Pro Git - Book Everything is in here, including installation instructions (in Chapter 1) and a tutorial (Chapter 2)

Digging Deeper

• Pro Git - Book The rest of Pro Git will take you as deep as you want to go.
• Git user's Manual.
• Git Git's official website
• Git - Reference This is the official reference manual, in the form of Unix "man" pages. That means that you can use the man command to read them, but it's easier to follow links on the web.
• git help - that's right, the manual is also available by way of git itself. That can be very convenient.
• Git - Wikipedia
• Version control - Wikipedia
• Software configuration management - Wikipedia
• Git: The other blockchain

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).
Donation buttons in profile.

Interesting couple of articles on Ars Technica:

Nostalgia: “The Linux of social media”—How LiveJournal pioneered (then lost) blogging (h/t to wcg)

Pre-nostalgia: Tumblr’s porn ban is going about as badly as expected | Ars Technica

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).

Some day I ought to put together a comprehensive list of privacy-related links. This is not that list; it's just a few of the links that came my way recently, in no particular order.

I'd suggest starting with the ACLU's What Individuals Should Do Now That Congress Has Obliterated the FCC’s Privacy Protections. It's a good overview.

DuckDuckGo is my current privacy-preserving search engine of choice. The DuckDuckGo Blog has been a good source of additional information. I especially recommend this article on How to Set Up Your Devices for Privacy Protection -- it has advice for iOS, Android, Mac, Windows 10 and 7, and Linux. Also check out a broader range of tips here.

The Electronic Frontier Foundation, as you might expect, is another great source of information. I suggest starting with Tools from EFF's Tech Team. While you're there, install Privacy Badger. It's not exactly an ad blocker; what it does is block trackers.

Here's an article on Which Browser Is Better for Privacy? (Spoiler: it's Firefox.) Then go to Firefox Privacy - The Complete How-To Guide.

For the paranoid among us, there are few things better than Tor Browser. If you use it, you'll probably want to turn off Javascript as well.

The Linux Journal's article on Data Privacy: Why It Matters and How to Protect Yourself has a lot of good advice, most of which isn't Linux-specific at all.

However, if you are running Linux, you'll want to look at How To Encrypt Your Home Folder After Ubuntu Installation, Locking down and securing SSH access to your server, and Own Your DNS Data.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com).

Most humans multitask rather badly -- studies have shown that when one tries to do two tasks at the same time, both tasks suffer. That's why many states outlaw using a cell phone while driving. Some people are much better than others at switching between tasks, especially similar tasks, and so give the appearance of multitasking. There is still a cost to switching context, though. The effect is much less if one of the tasks requires very little attention, knitting during a conversation, or sipping coffee while programming. (Although I have noticed that if I get deeply involved in a programming project my coffee tends to get cold.) It may surprise you to learn that computers have the same problem.

Your computer isn't really responding to your keystrokes and mouse clicks, playing a video from YouTube in one window while running a word processor in another, copying a song to a thumb drive, fetching pages from ten different web sites, and downloading the next Windows update, all at the same time. It's just faking it by switching between tasks really fast. (That's only partially true. We'll get to that part later, so if you already know about multi-core processors and GPUs, please be patient. Or skip ahead. Like a computer, my output devices can only type one character at a time.)

Back when computers weighed thousands of pounds, cost millions of dollars, and were about a million times slower than they are now, people started to notice that their expensive machines were idle a lot of the time -- they were waiting for things to happen in the "real world", and when the computer was reading in the next punched card it wasn't getting much else done. As computers got faster -- and cheaper -- the effect grew more and more noticable, until some people realized that they could make use of that idle time to get something else done. The first operating systems that did this were called "foreground/background" systems -- they used the time when the computer was waiting for I/O to switch to a background task that did something that did a lot of computation and not much I/O.

Once when I was in college I took advantage of the fact that the school's IBM 1620 was just sitting there most of the night to write a primitive foreground/background OS that consisted of just two instructions and a sign. The instructions dumped the computer's memory onto punched cards and then halted. The sign told whoever wanted to use the computer to flip a switch, wait for the dump to be punched out, and load it back in when they were done with whatever they were doing. I got a solid week of computation done. (It would take much less than a second on your laptop or even your phone, but we had neither laptop computers nor cell phones in 1968.)

By the end of the 1950s computers were getting fast enough, and had enough memory, that people could see where things were headed, and several people wrote papers describing how one could time-share a large, fast computer among several people to give them each the illusion that they had a (perhaps somewhat less powerful) computer all to themselves. The users would type programs on a teletype machine or some other glorified typewriter, and since it takes a long time for someone to type in a program or make a change to it, the computer had plenty of time to do actual work. The first such systems were demonstrated in 1961.

I'm going to skip over a lot of the history, including minicomputers, which were cheap enough that small colleges could afford them (Carleton got a PDP-8 the year after I graduated). Instead, I'll say a little about how timesharing actually works.

A computer's operating system is there to manage resources, and in a timesharing OS the goal is to manage them fairly, and switch contexts quickly enough for users to think that they're using the whole machine by themselves. There are three main resources to manage: time (on the CPU), space (memory), and attention (all those users typing at their keyboards).

There are two ways to manage attention: polling all of the attached devices to see which ones have work to do, and letting the devices interrupt whatever was going on. If only a small number of devices need attention, it's a lot more efficient to let them interrupt the processor, so that's how almost everything works these days.

When an interrupt comes in, the computer has to save whatever it was working on, do whatever work is required, and then put things back the way they were and get back to what it was doing before. This takes time. So does writing about it, so I'll just mention it briefly before getting back to the interesting stuff.

See what I did there? This is a lot like what I'm doing writing this post, occasionally switching tasks to eat lunch, go shopping, sleep, read other blogs, or pet the cat that suddenly sat on my keyboard demanding attention.

Let's look at time next. The computer can take advantage of the fact that many programs perform I/O to use the time when it's waiting for an I/O operation to finish to look around and see whether there's another program waiting to run. Another good time to switch is when an interrupt comes in -- the program's state already has to be saved to handle the interrupt. There's a bit of a problem with programs that don't do I/O -- these days they're usually mining bitcoin. So there's a clock that generates an interrupt every so often. In the early days that used to be 60 times per second (50 in Britain); a sixtieth of a second was sometimes called a "jiffy". That way of managing time is often called "time-slicing".

The other way of managing time is multiprocessing: using more than one computer at the same time. (Told you I'd get to that eventually.) The amount of circuitry you can put on a chip keeps increasing, but the amount of circuitry required to make a CPU (a computer's Central Processing Unit) stays pretty much the same. The natural thing to do is to add another CPU. That's the point at which CPUs on a chip started being called "cores"; multi-core chips started hitting the consumer market around the turn of the millennium.

There is a complication that comes in when you have more than one CPU, and that's keeping them from getting in one another's way. Think about what happens when you and your family are making a big Thanksgiving feast in your kitchen. Even if it's a pretty big kitchen and everyone's working on a different part of the counter, you're still occasionally going to have times when more than one person needs to use the sink or the stove or the fridge. When this happens, you have to take turns or risk stepping on one another's toes.

You might think that the simplest way to do that is to run a completely separate program on each core. That works until you have more programs than processors, and it happens sooner than you might think because many programs need to do more than one thing at a time. Your web browser, for example, starts a new process every time you open a tab. (I am not going to discuss the difference between programs, processes, and threads in this post. I'm also not going to discuss locking, synchronization, and scheduling. Maybe later.)

The other thing you can do is to start adding specialized processors for offloading the more compute-intensive tasks. For a long time that meant graphics -- a modern graphics card has more compute power than the computer it's attached to, because the more power you throw at making pretty pictures, the better they look. Realistic-looking images used to take hours to compute. In 1995 the first computer-animated feature film, Toy Story, was produced on a fleet of 117 Sun Microsystems computers running around the clock. They got about three minutes of movie per week.

Even a mediocre graphics card can generate better-quality images at 75 frames per second. It's downright scary. In fairness, most of that performance comes from specialization. Rather than being general-purpose computers, graphics cards mostly just do the computations required for simulating objects moving around in three dimensions.

The other big problem, in more ways than one, is space. Programs use memory, both for code and for data. In the early days of timesharing, if a program was ready to run that didn't fit in the memory available, some other program got "swapped out" onto disk. All of it. Of course, memory wasn't all that big at the time -- a megabyte was considered a lot of memory in those days -- but it still took a lot of time.

Eventually, however, someone hit on the idea of splitting memory up into equal-sized chunks called "pages". A program doesn't use all of its memory at once, and most operations tend to be pretty localized. So a program runs until it needs a page that isn't in memory. The operating system then finds some other page to evict -- usually one that hasn't been used for a while. The OS writes out the old page (if it has to; if it hasn't been modified and it's still around in swap space, you win), and schedules the I/O operation needed to read the new page in. And because that take a while, it goes off and runs some other program while it's waiting.

There's a complication, of course: you need to keep track of where each page is in what its program thinks of as a very simple sequence of consecutive memory locations. That means you need a "page table" or "memory map" to keep track of the correspondence between the pages scattered around the computer's real memory, and the simple virtual memory that the program thinks it has.

There's another complication: it's perfectly possible (and sometimes useful) for a program to allocate more virtual memory than the computer has space for in real memory. And it's even easier to have a collection of programs that, between them, take up more space than you have.

As long as each program only uses a few separate regions of its memory at a time, you can get away with it. The memory that a program needs at any given time is called its "working set", and with most programs it's pretty small and doesn't jump around too much. But not every program is this well-behaved, and sometimes even when they are there can be too many of them. At that point you're in trouble. Even if there is plenty of swap space, there isn't enough real memory for every program to get their whole working set swapped in. At that point the OS is frantically swapping pages in and out, and things slow down to a crawl. It's called "thrashing". You may have noticed this when you have too many browser tabs open.

The only things you can do when that happens are to kill some large programs (Firefox is my first target these days), or re-boot. (When you restart, even if your browser restores its session to the tabs you had open when you stopped it, you're not in trouble again because it only starts a new process when you look at a tab.)

And at this point, I'm going to stop because I think I've rambled far enough. Please let me know what you think of it. And let me know which parts I ought to expand on in later posts. Also, tell me if I need to cut-tag it.

Another fine post from The Computer Curmudgeon (also at computer-curmudgeon.com). If you found it interesting or useful, you might consider using one of the donation buttons on my profile page.

NaBloPoMo stats:
   8632 words in 13 posts this month (average 664/post)
   2035 words in 1 post today

Actually two PSAs.

First: Especially if you're running Windows, you ought to go read The Untold Story of NotPetya, the Most Devastating Cyberattack in History | WIRED. It's the story of how a worldwide shipping company was taken out as collateral damage in the ongoing cyberwar between Russia and the Ukraine. Three takeaways:

1. If you're running Windows, keep your patches up to date.
2. If you're running a version of Windows that's no longer supported (which means that you can't keep it patched, by definition), either never under any circumstances connect that box to a network, or wipe it and install an OS that's supported.
3. If at all possible, keep encrypted offline backups of anything really important. (I'm not doing that at the moment either. I need to fix that.) If you're not a corporation and not using cryptocurrency, cloud backups encrypted on the client side are probably good enough.

Second: I don't really expect that any of you out there are running an onion service. (If you had to click on that link to find out what it is, you're not.) But just in case you are, you need to read Public IP Addresses of Tor Sites Exposed via SSL Certificates, and make sure that the web server for your service is listening to 127.0.0.1 (localhost) and not 0.0.0.0 or *. That's the way the instructions (at the "onion service" link above) say to set it up, but some people are lazy. Or think they can get away with putting a public website on the same box. They can't.

If you're curious and baffled by the preceeding paragraph, Tor (The Onion Router) is a system for wrapping data packets on the internet in multiple layers of encryption and passing them through multiple intermediaries between you and whatever web site you're connecting with. This will protect both your identity and your information as long as you're careful! An onion service is a web server that's only reachable via Tor.

Onion services are part of what's sometimes called "the dark web".

Be safe! The network isn't the warm, fuzzy, safe space it was in the 20th Century.

Another public service announcement from The Computer Curmudgeon.

Today in my continuing series on programming languages I'm going to talk about "scripting languages". "Scripting" is a rather fuzzy category, because unlike the kinds of languages we've discussed before, scripting languages are really distinguished by how they are used, and they're used in two very different ways. It's also confusing because most scripting languages are interpreted, and people tend to use "scripting" when they should be using "interpreted". In my opinion it's more correct to say that a language is being used as a scripting language, rather than to say that it is a scripting language. As we'll see, this is particularly true when the language is being used to customize some application.

But first, let's define scripts. A script is basically a sequence of commands that a user could type at a terminal[1] -- often called "the command line" -- that have been put together in a file so that they can be run automatically. The script then becomes a new command. In Linux, and before that Unix, the program that interprets user commands is called a "shell", possibly because it's the visible outer layer of the operating system. The quintessential script is a shell script. We'll dive into the details later.

[1] okay, a terminal emulator. Hardly anyone uses physical terminals anymore. Or remembers that the "tty" in /dev/tty stands for "teletype"'.

The second kind of scripting language is used to implement commands inside some interactive program that isn't a shell. (These languages are also called extension languages, because they're extending the capabilities of their host program, or sometimes configuration languages.) Extension languages generally look nothing at all like something you'd type into a shell -- they're really just programming languages, and often are just the programming language the application was written in. The commands of an interactive program like a text editor or graphics editor tend to be things like single keystrokes and mouse gestures, and in most cases you wouldn't want to -- or even be able to -- write programs with them. I'll use "extension languages" for languages used in this way. There's some overlap in between, and I'll talk about that later.

Shell scripting languages

Before there was Unix, there were mainframes. At first, you would punch out decks of Hollerith cards, hand them to the computer operator, and they would (eventually) put it in the reader and push the start button, and you would come back an hour or so later and pick up your deck with a pile of listings from the printer.

Computers were expensive in those days, so to save time the operator would pile a big batch of card decks on top of one another with a couple of "job control" cards in between to separate the jobs. Job control languages were really the first scripting languages. (And the old terminology lingers on, as such things do, in the ".bat" extension of MS/DOS (later Windows) "batch files". Which are shell scripts.)

By far the most sophisticated job control language ran on the Burroughs 5000 and 6000 series computers, which were designed to run Algol very efficiently. (So efficiently that they used Algol as what amounted to their assembly language! Programs in other languages, including Fortran and Cobol, were compiled by first translating them into Algol.) The job control language was a somewhat extended version of Algol in which some variables had files as their values, and programs were simply subroutines. Don't let anyone tell you that all scripting languages are interpreted.

Side note: the Burroughs machines' operating system was called MCP, which stands for Master Control Program. Movie fans may find that name familiar.

Even DOS batch files had control-flow statements (conditionals and loops) and the ability to substitute variables into commands. But these features were clumsy to use. In contrast, the Unix shell written by Stephen Bourne at Bell Labs was designed as a scripting language. The syntax of the control structures was, in fact, derived from Algol 68, which introduced the "if...fi" and "do...done" syntax.

Bourne's shell was called sh in Unix's characteristically terse style. The version of Unix developed at Berkeley, (BSD, for Berkeley System Distribution -- I'll talk about the history of operating systems some time) had a shell called the C shell, csh, which had a syntax derived from the C programming language. That immediately gave rise to the popular tongue-twister "she sells cshs by the cshore".

The GNU (GNU's Not Unix) project, started by Richard Stallman with the goal of producing a completely free replacement for Unix, naturally had its own rewrite of the Bourne Shell called bash -- the Bourne Again Shell. It's a considerable improvement over the original, pulling in features from csh and some other shell variants.

Let's look at shell scripting a little more closely. The basic statement is a command -- the name of a program followed by its arguments, just as you would type it on the command line. If the command isn't one of the few built-in ones, the shell then looks for a file that matches the name of the command, and runs it. The program eventually produces some output, and exits with a result code that indicates either success or failure.

There are a few really brilliant things going on here.

• Each program gets run in a separate process. Unix was originally a time-sharing operating system, meaning that many people could use the computer at the same time, each typing at their own terminal, and the OS would run all their commands at once, a little at a time.
• That means that you can pipe the output of one command into the input of another. That's called a "pipeline"; the commands are separated by vertical bars, like | this, so the '|' character is often called "pipe" in other contexts. It's a lot shorter than saying "vertical bar".
• You can "redirect" the output of a command into a file. There's even a "pipe fitting" command called tee that does both: copies its input into a file, and also passes it along to the next command in the pipeline.
• The shell uses the command's result code for control -- there's a program called true that does nothing but immediately returns success, and another called false that immediately fails. There's another one, test, which can perform various tests, for example to see whether two strings are equal, or a file is writable. There's an alias for it: [. Unix allows all sorts of characters in filenames. Anyway, you can say things like if [ -w $f ]; then...
• You can also use a command's output as part of another command line, or put it into a variable. today=`date` takes the result of running the date program and puts it in a variable called today.

This is basically functional programming, with programs as functions and files as variables. (Of course, you can define variables and functions in the shell as well.) In case you were wondering whether Bash is a "real" programming language, take a look at nanoblogger and Abcde (A Better CD Encoder).

Sometime later in this series I'll devote a whole post to an introduction to shell scripting. For now, I'll just show you a couple of my favorite one-liners to give you a taste for it. These are tiny but useful scripts that you might type off the top of your head. Note that comments in shell -- almost all Unix scripting languages, as a matter of fact -- start with an octothorpe. (I'll talk about octothorpe/sharp/hash/pound later, too.)

# wait until nova (my household server) comes back up after a reboot
until ping -c1 nova; do sleep 10; done

# count my blog posts.  wc counts words, lines, and/or characters.
find $HOME/.ljarchive -type f -print | wc -l

# find all posts that were published in January.
# grep prints lines in its input that match a pattern.
find $HOME/.ljarchive -type f -print | grep /01/ | sort

Other scripting languages

As you can see, shell scripts tend to be a bit cryptic. That's partly because shells are also meant to have commands typed at them directly, so brevity is often favored over clarity. It's also because all of the operations that work on files are programs in their own right; they often have dozens of options and were written at different times by different people. The find program is often cited as a good (or bad) example of this -- it has a very different set of options from any other program, because you're trying to express a rather complicated combination of tests on its command line.

Some things are just too complicated to express on a single line, at least with anything resembling readability, so many other programs besides shells are designed to run scripts. Some of the first of these in Unix were sed, the "stream editor", which applies text editing operations to its input, and awk, which splits lines into "fields" and lets you do database-like operations on them. (Simpler programs that also split lines into fields include sort, uniq, and join.)

DOS and Windows look at the last three characters of a program's name (e.g., "exe" for "executable" machine language and "bat" for "batch" scripts) to determine what it contains and how to run it. Unix, on the other hand, looks at the first few characters of the file itself. In particular, if these are "#!" followed by the name of a program (I'm simplifying a little), the file is passed to that program to be run as a script. The "#!" combination is usually pronounced "shebang". This accounts for the popularity of "#" to mark comments -- lines that are meant to be ignored -- in most scripting languages.

The scripting programs we've seen so far -- sh, sed, awk, and some others -- are all designed to do one kind of thing. Shells mostly just run commands, assign variables, and substitute variables into commands, and rely on other programs like find and grep to do most other things. Wouldn't it be nice if one could combine all these functions into one program, and give it a better language to write programs in. The first of these that really took off was Larry Wall's Perl. Like the others it allows you to put simple commands on the command line -- with exactly the same syntax as grep and awk.

Perl's operations for searching and substituting text look just like the ones in sed and grep. It has associative arrays (basically lookup tables) just like the ones in awk. It can run programs and get their results exactly the way sh does, by enclosing them in backtick characters (`...` -- originally meant to be used as left single quotes), and it can easily read lines out of files, mess with them, and write them out. It has has objects, methods, and (more or less) first-class functions. And just like find and the Unix command line, it has a well-earned reputation for scripts that are obscure and hard to read.

You've probably heard Python mentioned. It was designed by Guido van Rossum in an attempt to be a better scripting language Perl, with an emphasis on making programs more readable, easier to write, and easier to maintain. He succeeded. At this point Python has mostly replaced Perl as the most popular scripting language, in addition to being a good first language for learning programming. (Which is the best language for learning is a subject guaranteed to invoke strong opinions and heated discussions; I'll avoid it for now.) I avoided Python for many years, but I'm finally learning it and finding it much better than I expected.

Extension languages

The other major kind of scripting is done to extend a program that isn't a shell. In most cases this will be an interactive program like an editor, but it doesn't have to be. Extensions of this sort may also be called "plugins".

Extension languages are usually small, simple, and interpreted, because nobody wants their text editor (for example) to include something as large and complex as a compiler when its main purpose is defining keyboard shortcuts. There's an exception to this -- sometimes when a program is written in a compiled language, the same language may be used for extensions. In that case the extensions have to be compiled in, which is usually inconvenient, but they can be particularly powerful. I've already written about one such case -- the Xmonad window manager, which is written and configured in Haskell.

Everyone these days has at least heard of JavaScript, which is the scripting language used in web pages. Like most scripting languages, JavaScript has escaped from its enclosure in the browser and run wild, to the point where text editors, whole web browsers, web servers, and so on are built in it.

Other popular extension languages include various kinds of Lisp, Tcl, and Lua. Lua and Tcl were explicitly designed to be embedded in programs. Lua is particularly popular in games, although it has recently turned up in other places, including the TeX typesetting system.

Lisp is an interesting case -- probably its earliest use as an extension language was in the Emacs text editor, which is almost entirely written in it. (To the point where many people say that it's a very good Lisp interpretor, but it needs a better text editor. I'm not one of them: I'm passionately fond of Emacs, and I'll write about it at greater length later on.) Because of its radically simple structure, Lisp is particularly easy to write an interpretor for. Emacs isn't the only example; there are Lisp variants in the Audacity audio workstation and the Autodesk CAD program. I used the one in Audacity for the sound effects in my computer/horror crossover song "Vampire Megabyte".

Emacs, Atom (a text editor written in JavaScript), and Xmonad are good examples of interactive programs where the same language is used for (most, if not all, of) the implementation as well as for the configuration files and the extensions. The boundaries can get very fuzzy in cases like that; as a Mandelbear I find that particularly appealing.

Another fine post from The Computer Curmudgeon.