In computability theory, you have all those proofs involving a hypothetical situation in which you equip a machine with an 'oracle' that can answer some class of extra-hard question.
It's out of scope to wonder how those oracles might be implemented. But here's my theory.
User: <clicks "I'm not a Turing machine">
CAPTCHA: "Select all images containing Turing machines that halt."
@oblomov I'm sorry, I'm completely unable to make sense of this. I don't know who 'they' are, or what warp processing has to do with theoretical Turing machines!
My best guess is that this might have been intended as a reply to some completely different toot, and posted here by mistake?
It's annoying that shutdown(SHUT_WR) handles duplicate fds backwards.
I open a socket and fork(), so one process can read and the other write. If the writer wants to send EOF, it has to explicitly SHUT_WR. If it crashes without doing so, EOF is never sent.
With pipes, the reader closes its copy of the writing pipe, and EOF happens once the other copy closes – explicitly or not.
But no socket API call has the semantics of 'I don't want to write any more, but maybe someone else still does'.
@simontatham@mjd It's surprising to me that there's no mechanism that turns SS_CANTRECVMORE on one end of a PF_UNIX socket into SS_CANTSENDMORE on the other end. But I also checked three different editions of the daemon book and they don't even describe the SHUT_RD case at all, it's like it was a total afterthought.
There have historically been network protocols that were dual-simplex in nature where shutting down the receive direction would have done something useful.
@wollman@mjd mmm. If you have a separate Unix pipe per direction and you close the read one, the writer at the other end finds out you're not listening, via SIGPIPE or EPIPE, and then it knows to stop wasting effort on generating the rest of its output.
In TCP, there's no analogue of that, so you just have to have a message in
your higher-layer protocol saying 'shut up, I don't care any more' if you think it's likely to be useful. And then I guess you do that for PF_UNIX too.
@fm_volker yes! The last time I tried really violently to get into a DVD case (as it turned out, because of a security device the shop had forgotten to remove), I destroyed the disc completely.
That time, the film was 'Pirates of the Caribbean'. So I'll always remember it as the day I almost watched Jack Sparrow.
You can represent an eventually-periodic infinite string as two finite strings: an initial segment and a repeating one. The representation isn't unique, e.g. (ABC, DECDECDEC) is the same string as (AB, CDE).
How do you find the minimal string pair equivalent to an input one?
Cute answer I just thought of: make a ρ-shaped finite state machine, and run the standard DFA minimisation algorithm, iteratively refining an eq rel on the states, to give a minimal equivalent ρ.
Can't you normalise by looking at the last letter on the initial and repeat section, and if they're the same, remove it from the initial and move it from the back to the front on the repeat? Do repeatedly until they differ.
(And don't forgot to remove repeats from the repeats section.)
@sgf yes, that works, but I didn't like that the last step involves checking every factor d of len(repeat) to see if repeat[0:d] * (len(repeat)//d) == repeat.
It's not exactly a problem – finding all factors of n is easy in an algorithm that's committed to taking Ω(n) time anyway. But it's nasty.
That's why I describe the ρ algorithm as 'cute' – it inspires (in me) a feeling of 'awww!', rather than the 'ugh!' from the other approach.
That old joke that goes "I know how to start spelling 'bananana' but I don't know when to stop". Other words subject to the same effect include 'queueueue' and 'homomomomorphism'.
But today I'm mostly having that problem with the \texttt command in LaTeX. Three ts in a row is a lot, and my motor cortex seems to have learned the rule 'you need one more t than you think', so I keep accidentally just keeping on going. I've managed \textttt{four} and \texttttt{five}. Not sure about six yet.
How is it supposed to work, when you get one of those emails whose body reads 'Sender Name would like to recall the message, "Subject Line"'?
I assume some mail system like Exchange is supposed to find the matching previous message and delete both. And my normal Unix mail system doesn't.
But how does it decide on the matching message? I can't find any header that unambiguously identifies it. No 'Recalled-message-id:' or similar. How does a system supporting this feature make it work?
@cawhitworth "pay for Exchange": I can see how a company might have that attitude (whether I like it or not!), but does that square with @andrewg's comment elsethread that recall only works within the same Exchange server? If that's true, then even paying for Exchange doesn't make it work properly.
(Not that you'd necessarily want someone in Org A to be able to destroy mail on Org B's server, but as before, at least identifying it would still be practically useful.)
Chatting about data structures with colleagues, and one mentioned a "left-leaning red-black tree".
I guess in a left-leaning red-black tree, the algorithms ensure that every node receives a reasonable minimum amount of processing. Whereas in a right-leaning red-black tree, the nodes all just get to compete with each other in a free market.
@simontatham Oh yeah, I completely forgot about binomial heaps!
I'm a huge fan of Fibonacci heaps, which can be merged in constant amortized time! Sadly, they involve a lot of pointer operations so they aren't all that useful in practice.
@a I have to confess that despite being a huge data-structures nerd in most other respects, I've never quite managed to get my head round how a Fibonacci heap works. I understand what useful properties it has, and why that makes it a good fit for e.g. Dijkstra's algorithm, but how it works just never quite comes together in my brain.
"This message couldn't be sent right now. Click for more details."
'More details', Outlook, should mean more details of why the message couldn't be sent. It doesn't mean 'show me the same error message but this time with the full text of the email'. I just finished typing the email. I already know what it says. Tell me what went wrong!
@dwm@simontatham at a previous job I had a python script to sync between and Outlook calendar and google calendar; with that done the IMAP support was BALGE for me.
@demoographics that sounds actually interesting, at least for the part where it reads your Outlook calendar and gets the information into a locally usable form. What was your technique for that?
With that part solved, I could use a solution of my choice for the most important thing, namely reminding me when I have a meeting. Then I wouldn't mind opening a browser for all other calendar operations, which are much rarer.
Famous apocryphal story: cryptographer tells amateur cipher designer 'In each of these 3 envelopes is an attack against your cipher. Open one and check it. Then find the other two by yourself.' Amateur is never heard from again.
Surely the cryptographer in this story could have cheated by putting the same attack in each envelope!
Done properly, there should have been 4 envelopes. Open any two, check they are (a) attacks, (b) not the same as each other. Then go look for the remaining two.
Whenever I drink fizzy wine, I can't resist making these tiny turtles out of the bottle tops. A bad habit learned from my dad.
I've never yet succumbed to the urge to make four tiny elephants and a #Discworld to go on top of one, but it's surely only a matter of time. Perhaps by 3D printing?
Centuries after Sauron's defeat, Middle-Earth developed motor racing, and Gandalf found his new dream job: driving the safety car.
Unfortunately, he didn't think of applying for that job until he needed a career change, having been fired from the prestigious position of Head of Examinations at the University of Gondor.
In bash, writing ${var?} instead of just ${var} or $var means if var isn't defined then bash will throw an error and not execute your command, instead of expanding it to "" and carrying on.
mv file1 file2 $subdir # oops, I overwrote file2
mv file1 file2 ${subdir?} # error message instead of disaster
My favourite use of this is for example commands in documentation, with placeholders for the user to fill in. Then it's OK if a user accidentally copy-pastes it without filling them in!
@simontatham I'm just a moron, but why would anyone want the default to be this vs the opposite?? "If you don't recognize this, STOP" seems way more sensible.
The Dragon Book orthodoxy for handling source code is a regex-based lexer and an LR parser, in series, with no feedback between them and no weird edge cases.
What widely used languages can really be parsed this way? So many major languages can't: type name ambiguity, context-sensitive lexing of >>, offside rule, conditionally significant newlines, …
(Not counting really simple things like Lisp: something with a grammar the size of C, suitable as a full-scale example for a parser generator.)
@simontatham Rust maybe? I can’t say that I have the entire grammar in my head, but they avoid the obvious pitfalls re: confusion between identifiers and type expressions by writing „name: type“ on declarations and enclosing type hints in <angle brackets>.
Also, they have very clear semantics for semicolons that do not involve significant whitespace. Not sure if Rust has shift operators, though, or if they use function syntax for that.
Discussion last night in a legacy social network¹ suggested that the ML family might be an answer to my question, OCaml in particular:
• mandatory semicolons ⇒ no weird newline business
• whitespace completely insignificant ⇒ no offside rule
• type parameter syntax needs no >> exception
• syntax separates variable names from type names
• mandatory casing rule avoids other identifier ambiguities
I haven't checked in full detail, but it sounds plausible!