dæmonology

The Haskell Community Offers Advice To Writers...

Yesterday
Post a comment

From a Haskell quotes archive:

<shapr> how will you know when you've written enough?

<kosmikus> I don't really know yet, but one of the following:

(a) if my supervisor tells me I have,

(b) if every chapter heading has content following it,

(c) if the deadline is there

<shapr> that's an excellent heuristic

This heuristic breaks down a bit for unpublished, unsigned fiction authors, i.e. A) you're unsigned, so nobody is going to tell you when you're done, B) you're unpublished as well as unsigned, so your deadlines are completely unfixed, so C) you're pretty much reduced to...

(b) if every chapter heading has content following it,

..which isn't so helpful, is it? Or is it?

More Language Design Thoughts

6 days ago
Post a comment

So, I've got a parser and lexical analyzer for a strawman of a surface language based on the F-zip work by Benoît Montagu and Didier Rèmy at INRIA. It builds an abstract syntax tree that looks pretty familiar if you read their papers and looked at the presentation materials. What I'm thinking about now is how to transform that surface language into an interior language for the purpose of efficiently generating LLVM output. I think F-zip is the beginning of a good idea. There are a whole bunch of ways it needs to be extended, e.g. subtyping, type shapes, etc. I could try to list them exhaustively, but I'd miss a few.

There are two extensions that the INRIA people are unlikely to think about, and that's the avenue I'm pursuing: A) substructural types for pointer ambits, à la Cyclone; and B) some kind of support for concurrency, à la the Kell calculus. The former one is a huge pile of work, but I can ape most of it by looking at the excellent work Morrisette and his team have already done. The latter problem is where I think the real magic still lies.

Milner's book on the π-calculus contains a demonstration of how the λ-calculus can be embedded in it. My hunch is that an explicitly typed, polyadic π-calculus can easily accommodate the whole of F-zip, plus whatever additional weirdness I can dream up. I'm going to try to find out. My interior language will look a lot like the Kell calculus (a π-calculus variant) extended with open existential types for first-class modules and substructural types for safe pointer ambits. I'll be generating LLVM code that relies heavily on the recently added support of tail-call optimization for a continuation passing style (CPS) runtime that will look kinda like how Pict works (but with some additional optimizations for inlining unobservable pure functions). That will make it look like a three-headed monster.

I should call my interior language KG, which would secretly be an abbreviation of King Ghidorah.

Thoughtful readers may be wondering why I'm taking the approach of starting with a functional surface language and embedding it into a process calculus. The answer is that I've looked at all the programming languages with embedded syntax for a π-calculus variant. There are a whole lot of languages like that, and they all strike me as making it too damned hard to write simple sequential algorithms, and let's face it: a lot of important algorithms are just cannot be improved by concurrent processing. Consider insertion/deletion in red-black trees. Concurrent— even parallel— processing is just not going to speed that up. And sometimes, paying for the overhead of concurrency is just never going to be worth it, e.g. iteration on trees of small, bounded size. Programmers will still need to manage concurrency explicitly for the foreseeable future.

Another Game Solved

Jul 9, 2008
Post a comment

This gives me a thrill up my leg.

PORTLAND, Ore. — Humanity was dealt a decisive blow by a poker-playing artificial intelligence program called Polaris during the Man-Machine Poker Competition in Las Vegas.

Poker champs fought the AI system to a draw, then won in the first two of four rounds (each round had Polaris playing 500 hands against two humans, whose points were averaged.) But in the final two rounds of the match, Polaris beat both human teams, two wins out of four, with one loss and one draw.

[...]

I'm surprised it's taken this long to write an AI that can pwn the Poker table. In fact, I suspect there are older implementations running on dedicated servers hosted in the Turks And Caicos Islands that can give Polaris a beatdown that will leave marks for years.

Still, it's nice to know that the news is going out now. Playing a game of Poker intermediated by a telecommunication system is one of the dumbest things a human can do these days.

A Minor Milestone

Jul 8, 2008
Post a comment

Tonight, I finished the first major rewrite of my first [unpublished] novel. For those just tuning in, it's a fantasy genre thing, so if that's not your boat, then you can just ignore this post. I like the fantasy genre (plus, it's important to note that I'm one of those annoying buttheads who thinks that most of what passes for "science-fiction" these days is merely fantasy with an extra helping of techno-babble to fool the rubes), so I've been writing a fantasy. Next, I might try my hand at something more contemporary. But first, I have this huge pile of unread books that have been waiting for this milestone...

This novel has been in the works for a long time, but it spent a lot of that time sitting untouched on the shelf because I wasn't sufficiently motivated to finish it. The first draft has been sitting on my hard drive since I sent it around to a select group of friends, most of whom reacted with variations on "it's kinda interesting, but it's full of problems— here let me show you them!" Some of that was useful, so I took the plunge and dove into a full rewrite from the ground up.

The second draft is quite a bit different from the first. It still has most of the same characters, and the story bears a strong resemblance to the one in the first draft, but there are a lot of major departures. The world is more than a little different. I think the second draft is much better plotted. The characters are stronger, too, I think. All in all, I'm not terribly ashamed of this draft.

I will be giving it another quick pass in the next couple of days, looking for howling discontinuities and other vermin. Then, I will be fulfilling my promise to Gee by sending off query letters to the appropriate literary agents. (She won't believe it's unpublishable until I collect the rejection slips that prove it. I suppose that's what spouses are supposed to do, but it still feels weird. I've never been terribly concerned over whether a publisher ever develops an interest in it. I just wanted it to be of commercial quality. I think I've succeeded at that, whether a publisher ever makes an offer or not.)

Those of you who are on my LiveJournal friend's list (editors and agents excluded): if you're interested in reading it, send me an email or post a comment in the LJ version of this thread, and I'll add you to the group I'll be using to post the chapters.

I Hate The C Language Family

Jul 8, 2008
2 comments

This is the fifth time today my build has failed because I forgot that stupid semicolon these languages require for statement terminators.

More Things I've Learned About Compiler Design

Jun 28, 2008
Post a comment

When your language allows the programmer to specify the precedence of operators, you're going to have a hard time parsing it with a grammar accepted by Yacc. That's because Yacc produces LALR(1) parsers, and that isn't going to work for you. Fortunately, for my current project, I have a really nice module of parsing combinators in my OCaml NAE Core Foundation that can produce LL(x) parsers. What's so nice about it? I can still use a static lexer with it, and I've got a nice lexical analyzer already. (It supports layout boxes like the ones planned for Haskell', which is the first reasonable model for whitespace sensitive syntax I've ever seen.)

So— what do you know? It turns out all that fiddling around wasn't necessarily a complete waste of time.

"Compilers You Can Formally Trust"

Jun 26, 2008
Post a comment

Oh, now that is rude.

How much do YOU trust your compiler? Is your compiler on your side? Or is it on the other side? How would you find out? If you could find out, would you really want to know? How would you react if you discovered your compiler was lying to you? Spying on you for your enemies? Sabotaging your programs? Terrorizing your users?

Don't just report your compiler! Certify it!

(On a related note... should I be worried that this is French project?)

F⋎!

Jun 26, 2008
Post a comment

Thanks to Didier Rémy and Benoît Montagu, I now have a solution to my type system problem.

ML est mort! Vivat F^⋎! Vivat! Vivat! Vivat!

Where Is James?

Jun 19, 2008
Post a comment

Received my brand-spanking-new copies of Advanced Topics in Types and Programming Languages (edited by Benjamin Pierce) and Garbage Collection: Algorithms for Automatic Dynamic Memory Management (by Richard Jones). The combination of these two books has unscrewed the lid off my head and poured unfiltered caffeine directly onto the grey matter. Short summary of my reaction: I suspect I really can make my own systems programming language.

Also, outlined the final chapter of my unpublishable unpublished fantasy novel. Need to tear myself away from all this code wankery and finish the damned thing.

Again... About Internet Neutrality

Jun 10, 2008
Post a comment

It's been awhile since this was a big news item, but the problem hasn't gone away. In fact, it's likely to get worse soon, as the Internet evolves into the post-surplus era, i.e. when the unallocated IPv4 address pool is depleted and free addresses must either be reclaimed from abandoned allocations or traded under some kind of market regime yet to be developed.

The major telecommunications providers haven't stopped working against Internet neutrality regulation. It's very likely they're going to win some kind of concessions, and those will almost certainly lead to a slow deterioration in the openness of the Internet, and the quashing of current progressive attempts to use the Internet to organize in opposition to the dominant cultural hegemony of our current collection of warmongering, theocratic, panopticon-loving, neoconservative assholes.

Think I'm joking? Sadly, no. I wish there was something to be done about it, but I'm not optimistic there's much political will among the teeming masses of the public. Fortunately, I have an idea that might help, but you'll have to read all the way through this rant to see what it is.

Since I've got some professional expertise in telecommunications and Internet engineering, I'm going to take some time first to try to explain in layman's terms some of the technical details about how the end of Internet neutrality has the potential to bring about such a starkly depressing outcome. Hopefully, my friends will appreciate this. Maybe, they'll agree with me, and they'll pay attention to what policy-makers who depend on them for votes and campaign contributions are saying and doing during this election season.

Otherwise, I'm wasting a lot of keystrokes.

Basically, the large Internet service providers would like very much to be able to offer their retail customers tiered pricing plans for Internet service in much the same way they currently do for satellite/cable television service. Described like that, it might not sound all that ominous— unless you're like me, and you'd rather claw your own eyes out with a rusty potato peeler than watch just about anything regularly broadcast on television.

To do this, what the large Internet service providers will do is cut exclusive peering deals with major content providers, whereby lower-tier retail customers of the ISP, who pay a lower monthly rate, are limited, or even prevented, from accessing content provided elsewhere. Customers who pay the lowest rate might be prevented from using any social networking sites other than the one or two that their ISP has cut an exclusive peering deal with. Others who pay a higher rate might get a wider range from which to choose, but they still might not get comparatively fast service to the out-of-network provider's content. In other words, you pay an extra $10/month so you can use Vox.com, but it's pokey slow and horrible compared to MySpace.com because you're still not paying for the "business class" service.

The "business class" service, naturally, gets you full neutrality, but you have to pay "business class" monthly rates. Guess what most of your retail customers will be paying. That's right: they'll have residential class service, which will be a private address behind a box with a single dynamically-assigned IPv6 address, which is itself masquerading behind an IPv6-v4 network address translator that rotates the IPv4 address a lot more frequently than the IPv6 one. If you want to communicate with your customer with any kind of speed or reliability, then you can cut a peering deal with all the major ISPs (or, more likely, you can buy the package from your ISP that they prearranged for small businesses like you), and that will give you a high-capacity direct route to their IPv6 home network, or at least a more stable private IPv4 address.

If you don't have the bucks to pay for this kind of peering deal, then you can probably still get service from some small independent ISP, and your customers will be able to reach you over the slow, not best-effort path their ISP's let them have for communicating with riff-raff like you— if they even let them go near you in the first place. Remember, they've cut exclusive deals with your competitors to drive their users away from you in exchange for a piece of your competitor's action with them. This is part of how they're doing it.

Now, let's pretend for a moment that you're not in the business of selling monogrammed rubber dogshit made in a sweatshop in Saipan to your loyal rubber dogshit customers in Redneckistan, Wyoming. No, you're in the business of trying to organize people to support you in a bid for a seat in the U.S. Congress, or you're trying to get people motivated to keep the old-growth redwood stands in the California State Park system from being sold off at auction to the Chinese military for use as targets on their artillery ranges. Or you're trying to raise awareness about how the local chemical plant is poisoning the river, and that's why all the fish you're catching have six eyes and human arms growing out of their gills. Or you're trying to help people understand how the information networks they use to inform themselves about public policy are being used to promote convenient lies to support a morally corrupt and criminal war for the profiteering opportunities it presents to those who won't ever have to fight in it. Or, not to be too meta, trying to help people understand why Internet neutrality is a good idea.

The list goes on and on. Do not try to run any bullshit here about how the companies that today are fighting Internet neutrality tooth and nail will be bending over backward to treat all comers fairly when it comes time to cut these exclusive peering arrangements with content providers. They will not. They have no intention of doing so. If they did, then they wouldn't need to kill Internet neutrality in the first place. They could just sell tiered pricing plans to their customers and dispense with the exclusive peering arrangements altogether.

I said I had an idea for how to approach this problem.

Here it is: tell these Internet service providers they have a choice. They can stop being neutral carriers ONLY if they're willing to take responsibility for the content they're carrying. If they carry messages that amount to false advertising or other forms of fraud, then they're the ones who are accountable for the damages. If they carry messages that endorse candidates for political office, then that's a campaign contribution. If they carry explicit movies of naked children playing hide-the-bratwurst with grown Congressmen, and that violates local community obscenity standards, then they're criminally liable for it. This happens for all content they carry on any of their channels. Any of them. They don't get to be pick-and-choose about which channels are neutral and which of them are not. If they're not neutral carriers, then they're content repackagers, and they're the ones who are responsible for the content they provide, not the original content developers.

The service providers won't like this arrangement one bit. It's basically the deal they have today: A) you can be a neutral carrier and provide all the bits the quality of service their senders are paying you for— regardless of what color they are, or where they're going— or, B) you can be Compuserve. We're going to be in a world of hurt if we let them turn the entire Internet into their own monopsonistic empire.

Yes, I just used a big scary word. Look it up. It means, There Is Effectively Only One Buyer.

Put more simply, it means this: You want to provide content to the whole Internet? Excellent. There's just one problem— there's effectively only one entity that will buy it from you: the giant Internet service providers, who collude to keep small competitors from challenging their dominance of the industry. And they decide what you will sell and how much they will pay for it. Not you. Or your consumers. They and they alone decide.

And they don't like you. A) They don't have to like you, and B) it's not in their interests to like you. Not one little bit. They're the goddamned phone company. That's why.

Now, do you see how this works, Larry?