shachaf

I use signalfd when I can, and this argument doesn't make much sense to me. The main goal of most signals you'd use it with -- like SIGCHLD/SIGPIPE -- is to wake you up and tell you that something happened, not to give you all the information. If you get a SIGCHLD, you can call wait() to get information. If you get SIGPIPE you can poll your file descriptors (though you might be doing that anyway so the signal isn't very useful). For the purpose of waking you up, coalescing isn't a problem -- only missed notifications are a problem, and signalfd handles those correctly.

Of course, for "real" signals that you must handle synchronously, like SIGSEGV, signalfd is less useful and makes less sense (and arguably something closer to Windows's SEH might make more sense). It's an odd historical artifact of Unix that SIGCHLD and SIGSEGV use the same mechanism.

The perspective I have in the post is that Multi-Paxos and Raft and so on are still doing pretty much exactly consensus for each log entry, they're just sharing lock IDs/ballots/terms across multiple log entries, and having the leader reuse the first phase -- acquiring the lock, reading the existing state -- across multiple instances of the second phase -- writing with the lock.

I think this is compatible with what you're saying, but maybe makes them seem more similar than treating them as two different problems.

Hmm, do you mean N+K+1 (to have enough points for both the data and parity shards)? Why isn't N+K sufficient, fitting a polynomial to N points and emitting K more?

I would suggest against relying too closely on this article in its current state. The "precedence climbing" code is needlessly complicated -- it has a nested loop which doesn't do anything, only one loop is necessary -- and it doesn't really explain what's going on (which is a relatively simple idea), just writes some pseudocode and mechanically evaluates it.

I didn't see this reply until today either.

On laziness, I only mean that the language feature isn't important. You can certainly represent infinite data using laziness (and you must represent it as some form of codata, such as a function), but it's not really the crucial thing here.

Here's a simpler version of seemingly impossible programs, which is better for explaining what I mean: Instead of bit streams, use conatural numbers, i.e. the natural numbers + infinity. You can define these in various ways (e.g. monotonic bit streams), but we'll use a regular Haskell type:

  > data Conat = Z | S Conat

Ignoring bottoms (which we won't permit), this has all the natural numbers as inhabitants, but it also has infinity:

  > inf :: Conat
  > inf = S inf

Note that, if I give you a conatural, all you can do with it is peel off successors; you can't distinguish infinity from "a really big number", extensionally.

A predicate on conaturals is a total function that takes a conatural and returns a boolean. As in the bit stream case, totality is a very strong requirement. For example, "is n even" isn't a valid predicate, because the way to check for evenness is to peel off pairs of successors until you reach either 0 or 1, but that doesn't halt on infinity. In particular, to be total, every predicate must give up eventually: After seeing k successors (for some unknown k), it has to give up and return true or false. If there was no such k, the predicate wouldn't terminate on infinity.

Now you can ask: Given a predicate, how can I decide whether there's any input that it holds for? And this is "seemingly impossible": You can test the predicate on infinity, and, say, on every finite number up to some N, but that doesn't give you any guarantee about the numbers you haven't tested. If all you can do is query p with any finite set of Conats -- even interactively, deciding what to ask it based on its previous responses! -- you don't get enough information to decide if the predicate is satisfiable.

The trick is to construct a special conatural which is defined in terms of p itself. If you think of this more imperatively, you can imagine a program that queries the predicate about increasingly larger natural numbers -- 0, 1, 2, 3, ... -- and prints out an "S" each time the predicate returns false, and a "Z" when the predicate returns true. If the predicate is false for all inputs, it prints out "S"s forever -- but that's still a valid (productive) conatural number.

This conatural is -- by construction -- the smallest input that satisfies p, if there is one, and infinity if there isn't. Now you can apply p to this number, and, if there's any input that satisfies p, p will return true.

The point I was making above is that it's crucial for this conatural to be able to call p. It doesn't introspect p, in the sense of being able to access its source code, but it's not independent either. And, although laziness expresses this elegantly, I wouldn't really say it's the core of the trick here. You could express the same thing using Turing machines that write out "S"s to their output tape, for example (as long as you don't require them to terminate overall, only to be productive). You do need to guarantee that the "conatural" Turing machine that you give to p has access to p (either by embedding its source code or by being able to call it as an oracle).

Here's the implementation in Haskell (which is simpler than the bit stream case given in the article, and doesn't need mutual recursion):

  > -- find p returns a conatural that satisfies p, if one exists.
  > -- (If one doesn't exist, it returns infinity.)
  > find :: (Conat -> Bool) -> Conat
  > find p = if p Z then Z else S (find (p . S))

  > -- Does any conatural satisfy the predicate?
  > exists :: (Conat -> Bool) -> Bool
  > exists p = p (find p)

No, the article's p takes a function:

> type Cantor = Natural -> Bit > (#) :: Bit -> Cantor -> Cantor > x # a = \i -> if i == 0 then x else a(i-1)

(You could represent bit streams with something like data Stream = Cons Bit Stream in Haskell, of course, but that's not what the article does. The code in the article works in e.g. Python almost as-is.)

And you can certainly pass closures to the predicate. Not closing over a mutable variable, of course -- I just mean that the bit stream function itself has to have access to p, which is the trick that makes this possible. If you couldn't do that -- if you could only query it with bit sequences that were defined independently of p -- this wouldn't be possible.

Laziness isn't the essential thing here -- the article's construction specifically doesn't rely on laziness, and would work in a strict language (almost verbatim -- you might need to write "lambda i: f(i)" instead of "f" in a few places).

I'd say that the thing that makes the article's version work is that you can pass a closure to the predicate, which is a channel for communicating extra information that makes it not quite a black box. In an imperative language, you could imagine passing in a function that mutates some state to get information out (or throws an exception, the way you set it up). The article shows that even that isn't necessary: You can pass in a sequence (represented as a function from index to value) that closes over the predicate itself, and recursively uses it to build a bit sequence that satisfies it, if one exists.

By the way, there's a clearer (I think) version of the core idea here that uses conatural numbers (the naturals + infinity) that people don't usually present, but might be worth writing up.

Is there any similar tool for string diagrams? They can be very expressive on paper, but it would be much more convenient to manipulate them on a computer.

The last part is backwards -- when F is a functor, the only law we need to check is the identity law, but checking the composition law isn't enough. For example,

  fmap _ _ = []

satisfies fmap f . fmap g = fmap (f . g), but not fmap id = id.

On the "Random Thought": The GIF doesn't need to be animated. A GIF is made of multiple frames and each frame contains multiple image blocks. Each image block has its own coördinates and color table. You should be to use multiple image blocks in one frame (GCE block) to get one frame with 24-bit color.

For historical reasons most browsers don't respect a frame delay of 0 (computers used to be slow enough that even a 0 delay was good enough for animation; as they got faster browsers added extra delays to make old animations work correctly), but I think some renderers will correctly treat it as one frame (at least http://slbkbs.org/jsgif/ does! It has other problems with tricky GIFs, though -- the disposal method code is broken, for one).

Of course, you should just use PNG.

That's what Hoogle (http://www.haskell.org/hoogle/) and Hayoo! (http://holumbus.fh-wedel.de/hayoo/hayoo.html) are for.

Not quite: Each image descriptor has its own Local Color Table, but the delays aren't set by the image descriptor, they're set by the Graphics Control Extension block, and you can have multiple image descriptors per GCE block. So the GIF can look something like: HDR(GCT) GCE(delay10) IMG(LCT) IMG(LCT) IMG(LCT) GCE(delay10) IMG(LCT) IMG(LCT) IMG(LCT) ..., with several image descriptors per frame, each with its own palette.

However, due to historical reasons (GIFs optimized for old browsers on slow computers), modern browsers sometimes insert a small delay between image descriptors even if they're in the same frame. I generally consider this a bug. However, there are many broken GIFs out there...

It's possible to make animated GIFs that use more than 256 colors per frame (although they'll probably be bigger than a format designed for that sort of thing).

Yes, but then the canonical URL would be on github.com.

This was meant as a proof-of-concept and has several big inefficiencies that could be fixed pretty easily if someone was actually going to use it for something. The UI could also be improved, and I think at least IE9 could be reasonably easy to support (though I haven't tried).

I was using XHR because an important constraint was to do everything client-side, and there's no other way that I could find to get the raw image data. If you have server-side support, though, a lot of things can be made much simpler. Is there a reason not to proxy, like crux_ suggested?

OK, I put it up on GitHub. https://github.com/shachaf/jsgif

_The Tao is Silent_, by Raymond Smullyan, comes to mind.

Things have gotten worse, though, it seems; when I signed up it took about a month before I got the invitation, and I know others who've been waiting ~two months now and still haven't gotten it.

If embedded MIDI isn't working, use

    javascript:window.location = document.getElementById('toneframe').contentWindow.document.getElementsByTagName('embed')[0].src

To download the MIDI file directly.

Where does e come into this specifically? That is, why does 5^(i*pi) have an imaginary part?

I like to think that people vote on a comment based on the content, not on the (current) score. It is not particularly unlikely that twenty-four people thought:

This is a worthwhile comment! It points out something that I did not realize, and change the meaning of the article to a degree. I may as well vote on it, that it may move upward in the list and other people read it earlier than other comments.

Also remember that +1 isn't specified to be "Insightful" or "Informative" like Slashdot; nor can you vote a "half-good" comment up a half-point. Instead, to achieve the same effect, a half-good comment must appeal to half as many people. This comment happened to appeal, on its own merits, to twenty-four people.

(Does this mean that the highest-voted comments might be the ones that appeal to the biggest percentage of the site, rather than the ones of the highest quality? Hmm. Does that mean that for the voting system to work well, a good percentage of users must specifically only vote comments that are very good?)

What about letting people append to comments after the time limit? I've always thought that would be sensible: People could add to what they've said before in a visible way, but not "rewrite history".

After all, additions are already frequently marked as such (e.g., "EDIT:").