Archive:
In this section:
Subtopics:
Comments disabled |
Sat, 28 Aug 2021 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?
Naah, it kinda falls apart after that. [Other articles in category /book] permanent link On Twitter, Mike Coutermarsh suggested:
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:
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 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:
(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
[Other articles in category /math] permanent link |