The Universe of Discourse

More words change meanings

“Salient” seems to have lost its original meaning, and people mostly use it as if it were synonymous with “relevant” or “pertinent”. This is unfortunate. It's from Latin salīre, which is to jump, and it originally meant something that jumps out at you. In a document, the salient point isn't necessarily the one that is most important, most crucial, or most worth consideration; it's the one that jumps out.

It is useful to have a word specifically for something that jumps out, but people no longer understand it that way.

Cognates of salīre include “assail" and “assault”, “salmon” (the jumping fish), and the mysterious “somersault”.

[Other articles in category /lang] permanent link

Words change meanings

This Imgur gallery has a long text post about a kid who saw the movie Labyrinth) in London and met David Bowie after. The salient part was:

He seemed surprised I would want to know, and he told me the whole thing, all out of order, and I eked the details out of him.

This is a use of “eke” that I haven't seen before. Originally “eke” meant an increase, or a small addition, and it was also used in the sense of “also”. For example, from the prologue to the Wife of Bath's tale:

I hadde the bettre leyser for to pleye, And for to se, and eek for to be seye

(“I had more opportunity to play, and to see, and also to be seen.”)

Or also, “a nickname” started out as “an ekename”, an also-name.

From this we get the phrase “to eke out a living”, which means that you don't have quite enough resources, but by some sort of side hustle you are able to increase them to enough to live on.

But it seems to me that from there the meaning changed a little, so that while “eke out a living” continued to mean to increase one's income to make up a full living, it also began to connote increasing one's income bit by bit, in many small increments. This is the sense in which it appears to be used in the original quotation:

He seemed surprised I would want to know, and he told me the whole thing, all out of order, and I eked the details out of him.

Addenda

Searching for something in a corpus of Middle English can be very frustrating. I searched and searched the University of Michigan Corpus of Middle English Prose and Verse looking for the Chaucer quotation, and couldn't find it, because it has “to se” and “to be seye”, but I searched for “to see” and “to seye”; it has “eek” and I had been searching for “eke”. Ouch.

In the Chaucer, “leyser” is “leisure”, but a nearly-dead sense that we now see only in “complete the task at your leisure”.

[Other articles in category /lang] permanent link

Diminishing resources in the Korean Language

Hangul, the Korean alphabet, was originally introduced in the year 1443. At that time it had 28 letters, four of which have since fallen out of use. If the trend continues, the Korean alphabet will be completely used up by the year 7889, preceded by an awful period in which all the words will look like

앙 앙앙앙 앙앙 앙 앙앙앙앙 앙

and eventually

ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ!

[Other articles in category /lang] permanent link

Worst. Miracle. Ever.

Some traditional miracles ascribed to saints and other holy people are better than others. Jesus walking on water and quieting the storm are impressive and showy, but essentially unhelpful. Contrasting this kind of show-magic with the miracles of the Buddha, Jorge Luis Borges describes “a miracle of courtesy”:

The Buddha has to cross a desert at noon. The gods, from their thirty-three heavens, each send him down a parasol. The Buddha does not want to slight any of the gods, so he turns himself into thirty-three Buddha. Each god sees a Buddha protected by the parasol he sent.

(It's Borges, so it's also possible he just made it up.)

My favorites of the Christian miracles are the miracles of the loaves and fishes, which are miracles of generosity and compassion. A multitude of people have come to see Jesus heal the sick:

As evening approached, the disciples came to him and said, “This is a remote place, and it’s already getting late. Send the crowds away, so they can go to the villages and buy themselves some food.”

Jesus replied, “They do not need to go away. You give them something to eat.”

“We have here only five loaves of bread and two fish,” they answered.

“Bring them here to me,” he said. And he directed the people to sit down on the grass. Taking the five loaves and the two fish and looking up to heaven, he gave thanks and broke the loaves. Then he gave them to the disciples, and the disciples gave them to the people. They all ate and were satisfied and the disciples picked up twelve basketfuls of broken pieces that were left over.

(Matthew 14:15–20)

Much better than walking on water.

Anyway, that is peripheral to what I wanted to write about. Lately I learned that there is a painting by Il Sodoma (1477–1549, original name Giovanni Antonio Bazzi) titled St Benedict repairs a Broken Colander through Prayer.

A broken what now? Colander? Like, the thing I use to drain my tortellini?

I looked in the Big Dictionary to find out if maybe “colander” might sometimes mean something more impressive than the kitchen utensil, maybe some expensive and specialized piece of church equipment. Nope:

A vessel, usually of metal, closely perforated at the bottom with small holes, and used as a sieve or strainer in cookery.

There doesn't appear to be any such thing in the painting:

St. Benedict is kneeling in prayer, second from left, wearing a halo. The colander, it turns out, is the two rectangular brown things by his knees. As you see, one piece is visibly cracked. I don't know what is the red schmutz on the other piece.

(The long-haired guy in the middle, with the expensive gloves, is Il Sodoma himself. He is known to have kept pet badgers, which also make an appearance here.)

Google searches for "st. benedict" "colander" were no help. They mostly produced references to this painting again.

I then wondered if maybe “colander” was a mistranslation. The Italian title for this painting is Come Benedetto risalda lo capistero che si era rotto. The Goog translates this as “How Benedict heals the broken master”, which was quite confusing. Google further confused me by glossing risalda as “rises”, which made me wonder if the repair of the broken colander (risalda lo capistero) was somehow a metaphor for the rising of Jesus. The idea seems rather silly, but Renaissance thinking does not always make sense to me, so I did not rule it out immediately. But no, risalda is repair, and capistero is a colander, or more precisely a sieve. The Goog's translation was simply wrong. (Fair enough, Google Translate is not intended to translate early-renaissance Italian.)

Book 2 of the Dialogues of Pope Gregory is about St. Benedict, and chapter 1 is titled “How he made a broken sieve whole and sound”:

It fell so out that his nurse borrowed of the neighbors a sieve to make clean wheat, which being left negligently on the table, by chance it was broken in two pieces, Whereupon she fell pitifully weeping, because she had borrowed it. The devout and religious youth Benedict, seeing his nurse so lamenting, moved with compassion, took away with him both the pieces of the sieve, and with tears fell to his prayers; and after he had done, rising up he found it so whole, that the place could not be seen where before it was broken.

So “colander” isn't quite right, but it's not too far off. The implement is probably made of wood, not metal. But it is indeed a perforated kitchen utensil. The suntanned lady on the left of the painting is the nurse, gazing ruefully at the table.

The colander is a tray for sifting wheat. The upper part (at left, with the big crack in it) has some sort of perforations or screen, which don't show up well in the painting. The lower part (at right) is a tray in which the sifted material is caught.

The right side of the painting depicts a later time after the colander has been repaired. The miraculous sieve has been hung up on a column (top center) for the wonderment of a crowd of admiring visitors.

Saint Anthony could command animals and was such an arresting speaker that even fish came to hear him preach. Some saints invoke the power of God to heal the blind and paralyzed, the drowned, the leprous, and the epileptic. St. Benedict healed a broken colander.

[Other articles in category /religion] permanent link

Simpson's paradox and Maxine Hong Kingston's mom

Yesterday's Simpson's paradox example reminds me of Maxine Hong Kingston's mother in The Woman Warrior:

When a sick person was about to die, my mother could read the fact of it a year ahead of time on the daughters-in-law’s faces. … My mother would take one look at the daughter-in-law who answered the door at the sick house and she’d say, “Find another doctor.” She would not touch death; therefore, untainted, she brought only health from house to house. “She must be a Jesus convert,” the people from the far villages said. “All her patients get well.”

[Other articles in category /math] permanent link

Simplest example of Simpson's paradox

I had read many times about Simpson's paradox but it never quite clicked for me. I saw many examples, but I couldn't quite get what was really going on. And I could never remember the numbers in the examples, so I couldn't ponder it while waiting for the bus or whatever.

Last month I sat down and thought about it, with the idea of coming up with the simplest and most memorable possible example. Here it is.

• Imagine there is a disease that kills 50% of the people who get it.

• There is a pill you can take if you get the disease. Of the people who take the pills, 80% die.

• It looks like the pills are killing people. But they aren't, they are helpful.

This is Simpson's paradox.

• What is really happening is that half the people with the disease have mild cases and half have severe cases. A patient with a mild case will get better on their own. But everyone with a severe case dies unless they receive treatment.

• People with mild cases don't bother to take the pills, because they are going to get better anyway.

• Only people with severe cases take the pills. 80% of them die, but without the pills they all would have died.

Now I understand Simpson's paradox.

[Other articles in category /math] permanent link

Shitpost

Imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of !!R(5, 5)!! or they will destroy our planet. In that case, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for yo mama's weight in pounds. In that case, we should attempt to destroy the aliens.

(With posthumous apologies to Paul Erdős)

[Other articles in category /math] permanent link

Ida-related flooding in Philadelphia

On September 1, Hurricane Ida hit Pennsylvania. Several tornadoes touched down near where I live in Philadelphia, and five people were killed. Fortunately Philadelphia itself was spared, and from where I live it only appeared to be an unusually-heavy rainstorm.

But Philadelphia is on the Schuylkill River, and all the water that Ida dumped northwest of Philadelphia ended up in the Schuylkill, which flooded epically and historically

I-95 and I-76 also run through Philadelphia, and connecting them, in a deep trench along the northern boundary of the business district, is the Vine Street Expressway. Normally it looks like this:

(Google Street View, July 2019)

But on September 1 it looked like this:

Holy cow. I'd never seen anything like this before. How long would the expressway be shut down? I had no idea.

Toph and I went up there on September 4 to see the damage, but by then there wasn't much to see. It looked like this:

Traffic was flowing normally in the eastbound lane (far side). The westbound lane (near side, with the cone) was still closed but it was obvious that they were finishing the cleanup. That's some amazing work. I have no idea how you even begin to get something like that cleaned up, and no idea how to get it done in three days.

The streets were a little dirtier than usual, but if I hadn't known to look I probably wouldn't have noticed. (Philadelphia.) We did pass houses that had piles of ruined books outside, and we encountered two gentlemen who were glumly carrying out loads of soggy carpet from their flooded basement.

We walked on the path that runs by the river, which is normally about two or three meters above the level of the river itself. The river didn't look higher than usual, but we did see signs of the flood. The path is between the river and the train tracks, and there is a fence to keep you from crossing the tracks.

Here's picture I took on September 4:

The river has piled driftwood and other trash at the base of the fence. The fence itself is clogged with leaves and paper, left there when the river poured through it as through a sieve. The river not only overtopped its banks and flooded the footpath, it must have reached at least to the top of the fence.

Here's another shot of the fence. Over here the sieve became too clogged to let the water through and the entire fence collapsed. The on-ramp for the expressway is visible in the background.

Here's Google's Street View picture of what the fence was like in July 2016:

I have no special point to make, and leave you with this, which I think should be part of the Philadelphia historical archives. Content warning: unsanitary behavior.

[Other articles in category /misc] permanent link

On having the right theorem

A recent Math StackExchange question asks “Prove every permutation of the alphabet contains a subset of six letters in order”. That is, you take a string of length 26 that contains each letter once; you can find a subsequence of six letters that is either increasing or decreasing.

Choosing a permutation at random, suppose we have:

    q y x u l i n g w o c k j d r p f v t s h e a z b m

Then the sequence x w v t s e b has length 7 and is in descending order. Or:

    t h e q u i c k b r o w n f x j m p s v r l z y d g

This contains the ascending sequence h q r s v y. Also the descending sequence t q o n m l d.

I thought about this for a while but couldn't make any progress. But OP had said “I know I have to construct a partially ordered set and possibly use Dilworth's Theorem…” so I looked up Dilworth's theorem.

It turns out I did actually know Dilworth's theorem. It is about partially-ordered sets. Dilworth's theorem says that if you partition a partially-ordered set into totally-ordered subsets, called ‘chains’, then the number of such chains is at least as big as the size of the largest “antichain”. An antichain is a subset in which no two elements are comparable.

This was enough of a hint, and I found the solution pretty quickly after that. Say that !!S[i]!! is the position of letter !!i!! in the string !!S!!. Define the partial order !!\prec!!: $$ i\prec j \qquad \equiv \qquad i < j \text{ and } S[i] < S[j] $$

That is, !!i\prec j!! means that !!i!! is alphabetically earlier than !!j!! and its position in !!S!! is to the left of !!j!!. This is obviously a partial ordering of the letters of the alphabet. Chains under !!\prec!! are, by definition, ascending sequences of letters from !!S!!. It's easy to show that antichains are descending sequences.

Partition !!S!! into chains. If any chain has length !!6!! or more, that is an ascending sequence of letters and we win.

If not, then no chain has more than 5 letters, and so there must be at least !!6!! chains, because !!5·5=25!! and there are !!26!! letters. Since there are at least !!6!! chains, Dilworth's theorem tells us there is an antichain of at least !!6!! letters, and hence a descending sequence of that length, and we win.

Once you have the idea to use Dilworth's theorem, the problem collapses. (You also have to invent the right !!\prec!! relation, but there's really only one possible choice.)

Maybe I'll write a followup article about how just having a theorem doesn't necessarily mean you have an algorithm. Mathematicians will say “partition !!S!! into chains,” but actually programming something like that might be nontrivial. Then finding the antichain among the chains might also be nontrivial.

[Other articles in category /math] permanent link

Mo in an alternate universe

In a transparent attempt to capitalize on the runaway success of The Wonderful Wizard of Oz, the publishers of L. Frank Baum's earlier book A New Wonderland re-released it under the title The Magical Monarch of Mo. What if this ploy had actually worked? Would the book have inspired a movie?

We're off to see the Monarch,
The Marvelous Monarch of Mo…

Naah, it kinda falls apart after that.

[Other articles in category /book] permanent link

How to fix hiring?

On Twitter, Mike Coutermarsh suggested:

Job interview: “algorithms”

Reality: “Turn a 127 message deep slack thread between 5 engineers into a decision”

I suppose this was meant facetiously but I think it might contain the germ of a good idea.

Applicants are usually given timed a programming quiz. What if instead, the candidate was supplied with the 127-message Slack thread and given 24 hours to write up a proposal document? I honestly think this might produce good results.

Such a submission would be extremely probative of the candidate's talents and abilities, including:

• reading and understanding technical arguments
• balancing engineering tradeoffs
• foreseeing potential issues
• writing clear English
• planning
• seriousness
• writing coherent, well-organized, and persuasive documents

It is much more difficult to cheat on this task than on a typical programming exercise. The candidate certainly can't submit a prewritten essay that they found somewhere; that would be easy to detect. A candidate who can take someone else's prewritten essay and quickly rewrite it to plausibly appear original is probably quite well-qualified on many of the important metrics! (Plus an additional important one: the ability to do research. They had to locate, recognize, and read the essay they rewrote.)

It shouldn't be hard to change up the essay topic periodically, since the engineers will be producing several of those 127-message Slack threads every month. This also tends to impede cheating.

When a good candidate comes for an in-person interview, you have a ready-made topic of conversation. Instead of coding at the whiteboard, you can ask them to discuss their proposal.

Complaints that this would discriminate against candidates with poor command of English do not hold water. Good command of English is one of the job requirements, and the whole point of a job interview is to discriminate against unqualified candidates. Besides, if the hiring process encourages candidates to improve their English writing abilities, rather than cramming a bunch of red-black-tree algorithms, language trivia, or irrelevant brainteasters, so much the better for everyone.

[Other articles in category /misc] permanent link

Why is the S combinator an S?

The most important combinator in combinatory logic is the !!S!! combinator, defined simply:

$$ S x y z ⇒ (x z)(y z) $$

or in !!\lambda!!-calculus terms:

$$ S = \lambda x y z. (x z)(y z). $$

A wonderful theorem states that any !!\lambda!!-expression with no free variables can be converted into a combinator expression that contains only the combinators !!S, K,!! and !!I!!, where !!S!! is really the only interesting one of the three, !!I!! being merely the identity function, and !!K!! a constructor of constant functions:

$$ \begin{align} I x & = x \\ K x y & = x \\ \end{align} $$

In fact one can get along without !!I!! since !!S K K = I!!.

A not-too-infrequently-asked question is why the three combinators are named as they are. The !!I!! is an identity function and pretty obvious stands for “identity”.

Similarly the !!K!! constructs constant functions: !!K x!! is the combinator which ignores its argument and yields !!x!!. So it's not hard to imagine that !!K!! is short for Konstant, which is German for “constant”; no mystery there.

But why !!S!!? People typically guess that it stands for “substitution”, the idea being that if you have some application $$A\,B$$ then !!S!! allows one to substitute some term !!T!! for a free variable !!v!! in both !!A!! and !!B!! prior to the application:

$$ S\, A\, B\, T = A[v/T]\, B[v/T]. $$

Although this seems plausible, it's not correct.

Combinatory logic was introduced in a 1924 paper of Moses Schönfinkel. In it, he defines a family of combinators including the standard !!S!!, !!K!!, and !!I!!; he shows that only !!S!! and !!K!! are required. His initial set of combinators comprises the following:

$$ \begin{array}{cllrl} I & \textit{Identitätsfunktion} & \text{“identity function”}& I\,x =& x \\ C & \textit{Konstanzfunktion} & \text{“constancy function”} & C\,x\,y =& x \\ T & \textit{Vertauschungsfunktion} & \text{“swap function”} & T\,x\,y\,z=& x\,z\,y \\ Z & \textit{Zusammensetzungsfunktion} & \text{“composition function”} & Z\,x\,y\,z=& x\,(y\,z) \\ S & \textit{Verschmelzungsfunktion} & \text{“fusion function”} & S\,x\,y\,z=& x\,z\,(y\,z) \end{array} $$

(Schönfinkel also had combinators representing logical operations (one corresponding to the Sheffer stroke, which had been discovered in 1913), and to quantification, but those don't concern us right now.)

!!T!! and !!Z!! are now usually called !!C!! and !!B!!. These names probably originated in Curry's Grundlagen der kombinatorischen Logik (1930). Curry 1930 is probably also the origin of the change from !!C!! to !!K!!. I have no idea why Schönfinkel chose to abbreviate Konstanzfunktion as !!C!! instead of !!K!!. Curry notes that for !!I, K, B, C, S!! Schönfinkel has !!I, C, Z, T, S!!, but does not explain his changes. In Curry and Feys’ influential 1958 book on combinatory logic, the !!B!! and !!C!! combinators given names that are are literal translations of Schönfinkel's: “elementary permutator” and “elementary compositor”.

Returning to the !!S!! combinator, one sees that its German name in Schönfinkel's paper, Verschmelzungsfunktion, begins with the letter V, but so does Vertauschungsfunktion, so abbreviating either with V would have been ambiguous. Schönfinkel instead chose to abbreviate Verschmelzungsfunktion with S for its root schmelzen, “fusion”, and Vertauschungsfunktion with T for its root tauschen, “swap”. The word schmelzen is akin to English words “melt” and “smelt”.

The “swap” is straightforward: the !!T!! combinator swaps the order of the arguments to !!x!! in !!x\,y\,z!!: $$T\,x\,y\,z = x\,z\,y$$ but does not otherwise alter the structure of the expression.

But why is !!S!! the “melting” or “fusion” combinator? It's because Schönfinkel was interested in reducing abitrary mathematical expressions to combinators. He will sometimes have an application !!(f\, x)(g\, x)!! and he wants to ‘fuse’ the two occurrences of !!x!!. He can do this by rewriting the expression as !!S\, f\, g\, x!!. Schönfinkel says:

Der praktische Nutzen der Function !!S!! besteht ersichtlich darin, daß sie es ermöglicht, mehrmals auftresnde Veränderliche — und bis zu einem gewissen Grade auch individuelle Functionen — nur einmal auftreten zu lassen.

Clearly, the practical use of the function !!S!! will be to enable us to reduce the number of occurrences of a variable — and to some extent also of a particular function — from several to a single one.

(Translation from van Heijenoort, p. 362.)

So there you have it: the !!S!! combinator is so-named not for substitution, but because S is the first letter of schmelzen, ‘to fuse’.

References

• Schönfinkel, M. “Über die Bausteine der mathematischen Logik” (“On the building-blocks of mathematical logic”), Mathematische Annalen (1969), p. 305–316; Berlin, Göttingen, Heidelberg.

  English translation in Van Heijenoort, Jean (ed.) From Frege to Gödel: a Source Book in Mathematical Logic, 1879–1931 (1967) pp. 355–366 Harvard University Press; Cambridge and London.

• Curry, H.B. “Grundlagen der kombinatorischen Logik” (“Fundamentals of combinatory logic”), American Journal of Mathematics Vol. 52, No. 3 (Jul., 1930), pp. 509-536.

• Curry, H.B. and Robert Feys Combinatory Logic (1958) p. 152 North-Holland Publishing Company, Amsterdam.

[Other articles in category /math] permanent link