Due to unforseen technical difficulties, today's blog post has been delayed. Look for it next week, where I'll describe what you can do to get started writing an app for the new Apps Marketplace right now.

In other news, I'm spending most of next week travelling, so I won't be able to keep up my usual thrice-weekly updates. Regular blogging will resume the following week. Sorry!

実践Go言語(Effective Go)の翻訳、11回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

埋込み

Go言語には型によるサブクラス化という典型的な概念はありませんが、構造体またはインタフェースに型を埋込み、実装を「借りる」仕組みがあります。

インタフェースの埋込みはとても単純です。下は以前説明したio.Readerとio.Writerインタフェースの定義です。

type Reader interface {
    Read(p []byte) (n int, err os.Error)
}

type Writer interface {
    Write(p []byte) (n int, err os.Error)
}

ioパッケージではこれと同じように、オブジェクトに対しメソッドの実装を規定するためのインタフェースが、他にもいくつかエクスポートされています。たとえば、ReadとWrite両方を持つインタフェースio.ReadWriterがあります。これら2つのメソッドを明示的に記述することでio.ReadWriterを定義することもできますが、次のようにして2つのインタフェースを埋込んで新しいインタフェースを作成するほうがより簡単で、意図が伝わりやすくなります。

// ReadWriteは、基本的なメソッドReadとWriteをグルーピングしたインタフェース
type ReadWriter interface {
    Reader
    Writer
}

このようにすることで、Readerが行えること、およびWriterが行えることをReadWriterが兼ね備えていて、このインタフェースが埋込みインタフェース（メソッド群内に共通のメソッドを持っていてはならない）の結合により作られていることが見て取れます。ただしインタフェース内に埋込むことができるのはインタフェースだけです。

この基本的な考え方は構造体にもあてはまりますが、構造体の場合はより広範囲に渡る影響があります。bufioパッケージは2つの構造体型、bufio.Readerとbufio.Writerを持ち、当然それぞれパッケージioの対応するインタフェースを実装しています。bufioではさらに埋込みを利用して、ひとつの構造体にReaderとWriterを組み込んでバッファ付きの読み書きを実装しています。下の例で構造体内に型を列挙していますが、このときフィールド名は付けていません。

// ReadWriterは、ReaderとWriterのポインタを格納している
// これはio.ReadWriterの実装
type ReadWriter struct {
    *Reader
    *Writer
}

この構造体はこう書き換えることも可能です。

type ReadWriter struct {
    reader *Reader
    writer *Writer
}

ただこうした場合は、下のようにして呼び出しを転送するメソッドを用意し、フィールド内の各メソッドを実装しioインタフェースを満たすようにしなければなりません。

func (rw *ReadWriter) Read(p []byte) (n int, err os.Error) {
    return rw.reader.Read(p)
}

しかし、直接構造体を埋込んでしまえば、この冗長な記述は要らなくなります。埋込まれた型が持っているメソッドは自動で持ち上げられるため、すなわちbufio.ReadWriterはbufio.Readerと bufio.Writerのメソッドを持つだけでなく、3つのインタフェース(io.Reader、io.Writer、io.ReadWriter)の全てを満たすようになります。

埋込みとサブクラス化では大きな違いがあります。型を埋込んでいるとき、埋込んだ型が持っているメソッドは埋込み先のメソッドともなりますが、実行しているメソッドのレシーバは埋込み先の型ではなく、あくまで元の型です。サンプルコードの bufio.ReadWriterのReadメソッドが実行されることと、先程の転送メソッドが実行されることは結果としてまったく同じです。(レシーバはReadWriterフィールドのreaderで、ReadWriter自身ではありません。)

また、埋込みを使うことで少し扱いやすくもなります。下の例では、通常の名前付きフィールドと並んで、埋込みフィールドを記述しています。

type Job struct {
    Command string
    *log.Logger
}

これでJob型は、log.Logger型が持つLog、Logfといったメソッドを持つようになりました。もちろん、Loggerにフィールド名を与えることはできますが、それは必須ではありません。これで、Jobを使ってログが記録できるようになりました。

job.Log("starting now...")

このLoggerは普通の構造体フィールドであるため、いままで通りの方法で初期化が行えます。

func NewJob(command string, logger *log.Logger) *Job {
    return &Job{command, logger}
}

埋込まれているフィールドを直接参照しなければならないときは、フィールドの型名(パッケージ名は不要)をフィールド名として用います。つまりJob型である変数jobの*log.Loggerにアクセスしたいときはjob.Loggerと書きます。これはLoggerのメソッドに手を加えたいときに役立ちます。

func (job *Job) Logf(format string, args ...) {
    job.Logger.Logf("%q: %s", job.Command, fmt.Sprintf(format, args))
}

型を埋込むことで名前の競合が発生する恐れがありますが、その解決ルールは単純です。最初に、フィールドまたはメソッドXは、その他の、より深い入れ子内にあるXを隠蔽します。たとえばlog.LoggerにCommandと名づけられたフィールドまたはメソッドが含まれていても、JobのCommandフィールドがそれより優先されます。

2番目として、同一の入れ子階層に同じ名前が現れたとき、通常ではエラーとなります。たとえばJob構造体に、Loggerと名づけられた別のフィールドまたはメソッドが含まれているときlog.Loggerの埋め込みは不正です。ただし、このとき重複した名前が、型定義より外側のプログラムから一切アクセスされなければ大丈夫です。この決まりによって、埋め込まれた型へ外部から変更を加えてもある程度保護されます。つまり、フィールドの追加で他の型が持つフィールドとかち合ってしまっても、どちらのフィールドも一切使用されることがなければ何ら問題ありません。

In January 2007 I posted an article on my web site titled “Regular Expression Matching Can Be Simple And Fast.” I intended this to be the first of three; the second would explain how to do submatching using automata, and the third would explain how to make a really fast DFA. I posted the second article a few months ago.

Today, the third and final article is available, along with an open source production implementation called RE2.

Recently, I've been pondering, with some workmates, the practicality of putting together our own interactive table, similar to the Microsoft Surface or the reactable.

There are a number of variations on how to build one, but the one we're planning on trying seems to be the simplest: Build a custom table with a frosted glass or perspex top, and place a projector in the base, projecting onto the bottom of the frosted surface. Additionally, have a camera under the table, pointing at the surface, to detect touches and objects.

There are a number of variations on this theme. trackmate is a system of 2d barcodes and open source software that allows you to tag and track objects. Their example configurations involve a frosted plexiglass surface, with even illumination and a camera placed underneath. None of them directly support surfaces with images projected onto them, though.

This instructable demonstrates the construction of a multitouch table that supports both touch detection and a projector, through a technique called frustrated total internal reflection. It relies on a strip of infra-red LEDs along the edge of the panel, and touching the panel disrupts the internal reflection, allowing an infra-red camera under the table to detect your touches. Since it uses infra-red, it's not affected by the projector.

A good overview of different techniques for multitouch tables is available here.

The projector is another consideration: There's limited space in the table, if we want it to be a reasonable height, but most projectors will only create a fairly small image at those distances. One solution is a short throw projector - a projector with a particularly wide angle lens. Some of these can produce an image over a meter wide at a distance of only about 70cm (a typical height for a table)! They're not even much more expensive than regular projectors, these days.

Our ideal interactive table would combine several of these features: We want to be able to interact with it with fingers, but we also want to be able to place tagged objects on it and have them recognized. Unfortunately, nobody seems to have tried this approach yet: The trackmate examples all use even visible-light illumination to read the tags, while the multitouch examples use infra-red illumination for detecting touches, which isn't going to work for reading printed tags.

My thus-far hypothetical approach is a hybrid: I'd like to use regular visible light illumination provided by the projector, and, after calibrating the two devices, subtract the projected image from the image recorded by the camera, and feed the difference to the routines for recognizing touches and tags. While I hope this will work, it'll take some tests to be certain.

On the software side of things, there are a number of libraries available. trackmate, as already mentioned, tracks custom 2d barcodes, while touchlib takes care of recognizing and tracking 'blobs' such as fingers. At a lower level, libraries like opencv provide primitives for doing image processing yourself.

Finally, what applications do we want to use this for? Besides all the stuff we can already run (mostly demos, so far), what I would really like to use this for is augmented boardgaming. I have two games in mind to start: The 18xx series of games, and RPGs.

The goals for RPGs are fairly straightforward: Provide an interface to simulate tactical movement for battles, where the DM can control things and players can interact with the grid. Additionally, provide some utilities for tracking all the things that usually require manual bookkeeping. Finally, for extra bonus points, be able to recognize dice thrown on the surface, so players can roll the dice and have the computer recognize the outcome.

My goal with the 18xx games are a bit more involved. I'd like to implement a complete interactive-table version of them, starting with simulating just the board. The board in the 18xx games uses hexagonal tiles, which presents challenges all of its own - there don't seem to be any robust tile engines for Python. Pygame Utilities has one, but it's incomplete, and PGU is no longer maintained. fife may have one, but it dies with a bus error any time I try to run a demo on my mac. Unless someone surfaces with a recommendation of another one, it looks like I might have to write my own, which will at least be an interesting challenge. This page links to a lot of useful resources on handling hex grids on a computer.

Hex tile editors are similarly sparse, with most of them being written for windows or dos(!) and unmaintained. The tiled map editor is quite a nice looking editor which claims not to support hexagonal tiles, until you look closer, and notice that it exists in two versions - the 'new' QT version and the 'old' Java version. The Java version, while no longer maintained, is perfectly usable, and supports hex tiles. It also has quite a nice output format. Huzzah!

In terms of how this will interface with the interactive table, what I'd like is a simulation of the board, with real physical hex tiles that you can place down to lay new track. Once you've placed the tiles you want to, and oriented them the way you want, you can tap a 'submit' button, and the game will read the trackmate codes from the bottom of the tiles, figure out what they are and how they're facing, and add them to its own view of the board. You can then remove the physical tiles. This seems like the best of both worlds, as you get the intuitive usage of the game, without the clutter of easily knocked tiles on the board all the time. The game can then do routing and so forth for other game phases entirely in the computer, allowing you to simply tap on tiles to set up a route.

That's it for now. Apologies for the lack of a 'real' blog post - a combination of busy-ness, other things on my mind, and lack of inspiration for a 'real' post led to this braindump instead. If you have any ideas or suggestions about our interactive table project or about implementing a hex tile engine, please speak up in the comments!

実践Go言語(Effective Go)の翻訳、10回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

インタフェースとそれ以外の型

インタフェース

Go言語のインタフェースは、オブジェクトの振舞いを規定する手立てです。このセクションではインタフェースにより実現できることすべてを説明します。今まですでに2、3の簡単な例を見てきました。たとえばカスタム出力はStringメソッドを実装することで作られ、一方FprintfはWriteメソッドによって出力先をどこへでも変更できます。Go言語のコードでは、通常インタフェースは1～2個のメソッドしか持たず、またWriteメソッドを持つio.Writerのようにたいていメソッド名と関連した名前が付けられます。

型には複数のインタフェースを実装することができます。たとえばあるコレクション型がLen()、Less(i, j int) bool、Swap(i, j int)メソッドを持つsort.Interfaceを実装していればsortパッケージのルーチンを使ってソートが可能になり、その上さらに独自の出力メソッドを実装することもできます。下の例のSequence型は、少々不自然ですがこれらをすべて実装しています。

type Sequence []int

// sort.Interfaceに必要な全メソッドを実装
func (s Sequence) Len() int {
    return len(s)
}
func (s Sequence) Less(i, j int) bool {
    return s[i] < s[j]
}
func (s Sequence) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

// 出力用メソッド - 出力前に要素を並び替え
func (s Sequence) String() string {
    sort.Sort(s)
    str := "["
    for i, elem := range s {
        if i > 0 {
            str += " "
        }
        str += fmt.Sprint(elem)
    }
    return str + "]"
}

変換

さきほどのSequenceのStringメソッドを変更して、Sprintが本来持っているスライス出力機能を利用するようにしました。Sprintを呼び出す前にSequenceを純粋な[]intに変換することで、既存の処理を利用することが可能になります。

func (s Sequence) String() string {
    sort.Sort(s)
    return fmt.Sprint([]int(s))
}

このとき変換が行われ、sがただのスライスとみなされるため、スライスに規定されている書式で文字列が返されます。ここで変換を行われなければ、SprintはSequenceのStringメソッドを見つけ出し、呼び出しを無限に繰り返してしまいます。この2つの型(Sequenceと[]int)は名前を除けば同一であるため、これらの型の間における変換は問題なく行われます。この変換では新しい値が作られることはなく、既存の値が一時的に新しい型を持つかのような働きをします。(これと異なる変換もあります。たとえば整数を浮動小数点へ変換したときは新しく値が作成されます。)

Go言語のプログラムでは、異なるメソッド群を使用するために式の型を変換することがよく行われます。例として、既存の型sort.IntArrayを使ってサンプルプログラム全体を下のように軽量化することが可能です。

type Sequence []int

// 出力用メソッド - 出力する前に要素を並び替え
func (s Sequence) String() string {
    sort.IntArray(s).Sort()
    return fmt.Sprint([]int(s))
}

これで、Sequenceに複数のインタフェース(ソートと出力)を実装する代わりに、データを複数の型(Sequence、 sort.IntArray、[]int)に変換できることを利用して各機能を実現できるようになりました。このような使い方をすることは実際にはほとんどありませんが効果的な使い方です。

概説

ある型がインタフェースをひとつだけ実装していて、そのインタフェースのメソッド以外にエクスポートされたメソッドを持たないならば、型自体のエクスポートは不要です。インタフェースだけをエクスポートすることで、次の点を明白にすることができます。ひとつは、重要なのは実装ではなく振舞いであること。もうひとつは、振舞いは同じでも異なる機能を持った別個の実装であることです。また、共通メソッドを実装している各箇所で、その都度ドキュメントを記述する手間が省けるという利点もあります。

このような場合は、コンストラクタは実装している型ではなく、インタフェース値を返さなければなりません。一例として、ハッシュライブラリのcrc32.NewIEEE()とadler32.New()では、双方ともhash.Hash32インタフェース型の値を返します。Go言語プログラムでこのハッシュアルゴリズムをAdler-32からCRC-32に変更するために必要なのは、コンストラクタの呼び出しを入れ替えるだけです。それ以外のコードは、ハッシュアルゴリズムの変更による影響を受けません。

同様のアプローチにより、crypto/blockパッケージのストリーム暗号アルゴリズムは、一連のブロック暗号から独立しています。これらは特定の実装を返すのではなく、bufioパッケージにならってCipherインタフェースをラップしたhash.Hash、io.Reader、io.Writerいずれかのインタフェース値を返します。

下はcrypto/block内のインタフェースです。

type Cipher interface {
    BlockSize() int
    Encrypt(src, dst []byte)
    Decrypt(src, dst []byte)
}

// NewECBDecrypterは、rからデータを読み込み、
// c内の電子コードブック(ECB)モードを使って復号化を行うReaderを返します。
func NewECBDecrypter(c Cipher, r io.Reader) io.Reader

// NewCBCDecrypterは、rからデータを読み込み、
// c内の暗号ブロックチェイニング(CBC)モードと初期化ベクタivを使って
// 復号化を行うReaderを返します。
func NewCBCDecrypter(c Cipher, iv []byte, r io.Reader) io.Reader

NewECBDecrypterおよびNewCBCReaderで扱うことができるのは、特定の暗号化アルゴリズムやデータソースではなく、どのCipherインタフェースの実装であっても、またどのio.Readerでも適用することが可能です。これらはio.Readerインタフェース値を返すため、ECB暗号化をCBC暗号化と入れ替えるときは部分的な変更だけですみます。コンストラクタを呼び出している箇所は変更が必要ですが、その周囲のコードではコンストラクタから返されるのはio.Readerだけとみなしていれば違いに気づくことさえないでしょう。

インタフェースとメソッド

ほぼすべての型に対してメソッドを付け加えることができるので、これはすなわち、どのインタフェースであっても、ほとんどの型に実装可能であると言えます。この実例のひとつが、Handlerインタフェースを定めているhttpパッケージにあります。Handlerを実装しているすべてのオブジェクトで、HTTPリクエストを処理することが可能です。

type Handler interface {
    ServeHTTP(*Conn, *Request)
}

ここでは簡略化のため、POSTは無視してHTTPリクエストが常にGETであると仮定します。 (この簡略化がハンドラの書き方に影響を及ぼすことはありません。) 下は、ページの訪問回数を単に数えるだけのハンドラの実装一式です。

// 単純なカウントサーバ
type Counter struct {
    n int
}

func (ctr *Counter) ServeHTTP(c *http.Conn, req *http.Request) {
    ctr.n++
    fmt.Fprintf(c, "counter = %d\n", ctr.n)
}

(今回のテーマを気にとめつつ、FprintfがどのようにしてHTTP接続を出力するか注意してみてください。)
参考までに、こういったサーバをURLパスに割り当てる手順です。

import "http"
...
ctr := new(Counter)
http.Handle("/counter", ctr)

ところで、なぜCounterを構造体としているのでしょうか。必要なのは整数ひとつだけのはずです。(ただし値が増えたことを呼び出し側にも伝わるように、レシーバはポインタである必要があります。)

// 単純なカウントサーバ
type Counter int

func (ctr *Counter) ServeHTTP(c *http.Conn, req *http.Request) {
    *ctr++
    fmt.Fprintf(c, "counter = %d\n", *ctr)
}

自作プログラムが内部ステータスを持っていて、そこにページが訪問されたことを通知しなければならないとしたらどうすればよいでしょうか。このようなときは、次のようにチャネルとウェブページとを関連付けてください。

// 訪問がある度に通知を送信するチャネル
// (たぶんバッファリングされている必要がある)
type Chan chan *http.Request

func (ch Chan) ServeHTTP(c *http.Conn, req *http.Request) {
    ch <- req
    fmt.Fprint(c, "notification sent")
}

最後に、パス/argsを訪問したときにサーバプログラムを起動した際に与えられた引数を出力するようにしてみましょう。引数の出力関数は下のように簡単に書けます。

func ArgServer() {
    for i, s := range os.Args {
        fmt.Println(s)
    }
}

これをHTTPサーバへ変更していきます。さきほどのArgServer関数を適当な型(値は何でも良い)のメソッドとすることもできますが、それより良い方法があります。メソッドはポインタとインタフェース以外すべての型に定義することができるため、関数に対してメソッドを書くことも可能です。httpパッケージには、下のコードが含まれています。

// HandlerFunc型は、通常の関数をHTTPハンドラとして
// 使用可能にするためのアダプタです。
// fが適切なシグネチャを持つ関数であれば、HandlerFunc(f)は
// fを呼び出すハンドラオブジェクトとなります。
type HandlerFunc func(*Conn, *Request)

// ServeHTTPはf(c, req)を呼び出す
func (f HandlerFunc) ServeHTTP(c *Conn, req *Request) {
    f(c, req)
}

HandlerFuncはServeHTTPメソッドを持つ型であるため、この型の値はHTTPリクエストを処理できます。メソッドの実装を見てください。このメソッドのレシーバは関数fであり、メソッド内でfを呼び出しています。これは少々風変わりではありますが、前出のチャネルをレシーバとしてそのチャネルへ送信するメソッドと大差ありません。

ArgServerをHTTPサーバにするため、まずは正しいシグネチャを持つように修正します。

// 引数サーバ
func ArgServer(c *http.Conn, req *http.Request) {
    for i, s := range os.Args {
        fmt.Fprintln(c, s)
    }
}

これでArgServerはHandlerFuncと同じシグネチャを持つようになったので、以前SequenceをIntArray.Sortを使用するためIntArrayに変換したときと同様に、ArgServerをHandlerFunc内のメソッドを使用するためにHandlerFunc型に変換可能になりました。このセットアップを行うコードは次のように簡潔に書けます。

http.Handle("/args", http.HandlerFunc(ArgServer))

誰かが/argsページを訪問したときに呼び出されるハンドラは、値はArgServerで型はHandlerFuncとなりました。まず、HTTPサーバによってArgServerをレシーバとしてHandlerFunc型のServeHTTPメソッドが実行され、続いてHandlerFunc.ServeHTTP内のf(c, req)を通してArgServerが呼び出されます。そのあと引数の表示が行われます。

このセクションで、構造体、整数、チャネル、関数を使ってHTTPサーバを作成したのは、インタフェースがまさにメソッド群であり、(ほとんど)すべての型に対して定義できることを示すためです。

Another “no news” post. As I gather minutes here and there I’m still working in the syscall package. (Backups are good. Up to the minute backups are best …)

My minutes are limited right now due to a family illness. (Prognosis very good, but some way to go.)

I’ve been making some small non-porting related contributions to Go which haven’t required as much mental energy to at least stay in touch.

Roger Zelazny, in discussing why he liked to write science fiction, referred to Northrop Frye’s theory of modes. In Zelazny’s interpretation, Frye described characters in fiction in four modes:

1. The mythic mode is stories about gods.
2. The high mimetic mode is stories about heroes, people who are better than ordinary humans.
3. The low mimetic mode is stories about ordinary people.
4. The ironic mode is stories about people who are worse than ordinary people–criminals, buffoons.

(Frye also talked about a romantic mode but Zelazny doesn’t mention it.)

Zelazny said that he liked science fiction because it let him write literature in the mythic or high mimetic mode. Certainly many of his stories are about gods or people with great powers. Zelazny argued that literature today outside of science fiction is mainly confined to the low mimetic and the ironic mode. There are many superb stories about ordinary people. There are few stories about remarkable people which are not history and are not genre stories like science fiction or romances.

This started me thinking about other areas where stories are told in the high mimetic mode. Superhero comics are obviously told entirely in that mode. Another place we see it is a certain set of action movies: James Bond, for example, is a high mimetic mode character. But these stories, while enjoyable, rarely rise to the level of good literature.

An exception is The Hurt Locker. This excellent movie, which well deserved the Oscars it just won, is a straight-up action movie. It passed one of the acid tests of the action movie: I saw it twice, and I didn’t see anything the second time around that I missed the first time. With artistic movies I often get a new perspective on a second viewing; with action movies I rarely do. The movie also operates in the high mimetic mode: the protagonist, William James, is a heroic character. He is not a perfect human being, but he is exceptionally capable and brave.

But despite the high mimetic mode character, the movie does not operate as a standard hero’s journey, there is no evil mastermind or any identified antagonist. The movie is simply a collection of relatively unrelated incidents which reveal the characters. James does come to understand himself better during the movie—or, since we really only hear his inner thoughts in one scene, perhaps he understood himself all along. The combination of literary techniques with high mimetic mode make this a genuinely exceptional movie.

Zelazny, of course, used the same approach throughout his career, with varying degrees of success.

I've been laughing at this for weeks. It's too good not to share.

The first rule of Formal Logic Club is you do not prove the consistency of Formal Logic Club.

The second rule of Formal Logic Club is you do not prove the inconsistency of Formal Logic Club.

— James Grimmelmann

(Yes, this looks like http://xkcd.com/703/, but it beat xkcd to the punchline by ten years, and it's funnier.)

One little known package in the google.appengine.ext package is ereporter. This package exists to make it easier to get summaries of errors generated by your Python App Engine app, and today we'll show you how.

Far too often for new webapps, error reports for live webapps are a catch-as-catch-can type practice, with reports coming in from dedicated users, and whenever you think to check the logs page of your app. A lot of bugs can slip through this way, however, with exceptions going unnoticed to everyone but the users who experience them, then walk away in disgust, never to return again. With ereporter, however, we'll demonstrate how to set up a simple handler that takes care of capturing all the exceptions that occur in your app, and emailing a daily report to you, summarizing what went wrong.

Installing ereporter consists of 3 stages: Modifying your handler script, modifying your app.yaml, and adding a cron job. Let's start by modifying your handler script(s). Add the following to the top of all your handler scripts (that is, scripts that are mentioned in app.yaml):

import logging
from google.appengine.ext import ereporter

ereporter.register_logger()

The register_logger call causes ereporter to instantiate itself, and hook into the Python logging framework, where it will capture any calls to logging.exception. The webapp framework calls this function to log any uncaught exceptions, and your framework probably does too. If you want, you can also use logging.exception yourself, whenever you want an exception report added to ereporter.

Now that ereporter can capture your exceptions, we need to add the components it requires to send you the daily email. First up is the new handler in app.yaml:

handlers:
- url: /_ereporter/.*
  script: $PYTHON_LIB/google/appengine/ext/ereporter/report_generator.py
  login: admin

This handler will be the target of a cron job that calls it once a day, to generate the daily exception report. Add the cron job to cron.yaml:

cron:
- description: Daily exception report
  url: /_ereporter?sender=you@yourdomain.com
  schedule: every day 00:00

You need to replace the email address you@yourdomain.com with the address of any of the administrators of your app. A to address is not required, as the tool emails the report to all the admins of the app, but you still have to specify a valid sender address.

That's all there is to it - you'll now get nicely formatted HTML exception reports for your app, with exceptions broken down by app version and exception source. If an exception occurs multiple times in the same location, ereporter will roll them up into one entry, with a sample stacktrace and an approximate count of occurrences, to make it easier to see what the biggest problems your app is encountering are.

The report generator takes a few more options that control its output - for details, see the source code.

[Download a UTF-8 version of this file.]

nb name search index keyword
nb—search and index notes in files by keyword

nb keyword

nb description search keyword path file line acme
Nb searches for the given keyword in each nbindex file listed in
$HOME/nbindexes.  If it finds a match, nb prints the path, filename,
and line number of the indexed file in the format acme uses to refer to
lines in a file.

nb file format store index line path file line acme nbindexes
This file is an example.  Nb searches all files in the current directory
for lines which begin “^nb ”, and copies them into the file nbindex.
Each match is listed with its filename, and line number, e.g. for acme
to show the line on a right-click of the mouse.  It then adds the
path and filename of the current directory’s nbindex file to the file
$HOME/nbindexes.

By convention I use 1 blank line to separate paragraphs after an nb
line, and 2 blank lines to separate nb lines, but nb doesn’t care about
this.

nb nbindex example search keyword
This is the nbindex file for this file.

	nb.1:1 name search index keyword
	nb.1:5 keyword
	nb.1:8 description search keyword path file line acme
	nb.1:15 file format store index line path file line acme nbindexes
	nb.1:28 nbindex example search keyword
	nb.1:50 source plan9port rc script
	nb.1:70 port plan9port rc shell script grëp
	nb.1:75 author jason.catena@gmail.com
	nb.1:78 bugs

This is the output of the command “nb keyword”.  It lists the full
path since it may refer to files anywhere in the filesystem.

	/usr/local/plan9/bin/nb.1:1 name search index keyword
	/usr/local/plan9/bin/nb.1:5 keyword
	/usr/local/plan9/bin/nb.1:8 description search keyword path file line acme
	/usr/local/plan9/bin/nb.1:28 nbindex example search keyword

nb source plan9port rc script
#!/usr/local/plan9/bin/rc
flag e +

catalog=$HOME^'/nbindexes'
if(test -r $catalog && ! ~ $1 ''){
	list=`{cat $catalog}
	grëp $* $list | sed 's,nbindex:[0-9]+: ,,'
}

grep -n '^nb ' * >[2]/dev/null | sed 's,: ?nb +, ,' > nbindex
echo `{pwd}^'/nbindex' >> $catalog
if(~ $TMPDIR ''){
	TMPDIR=/var/tmp
}
tmp=$TMPDIR^'/nbindexes.'^$USER^'.'^$pid
sort -u $catalog > $tmp
mv $tmp $catalog

nb port plan9port rc shell script grëp
Nb in written in plan9port’s rc, but should be straightforward to port
to any shell.  Use grep instead of grëp.

nb author jason.catena@gmail.com

nb bugs
Nb generates the index after it searches, to present results immediately,
so it does not show changes since its last run.  If you want to see
the latest changes, then run nb with no parameters before you supply a
keyword (e.g. in acme, middle-click on nb after you edit an nb line or
following text).

UTF-8 is a way to encode Unicode code points—integer values from 0 through 10FFFF—into a byte stream, and it is far simpler than many people realize. The easiest way to make it confusing or complicated is to treat it as a black box, never looking inside. So let's start by looking inside. Here it is:

The convenient properties of UTF-8 are all consequences of the choice of encoding.

1. All ASCII files are already UTF-8 files.
   The first 128 Unicode code points are the 7-bit ASCII character set, and UTF-8 preserves their one-byte encoding.
2. ASCII bytes always represent themselves in UTF-8 files. They never appear as part of other UTF-8 sequences.
   All the non-ASCII UTF-8 sequences consist of bytes with the high bit set, so if you see the byte 0x7A in a UTF-8 file, you can be sure it represents the character z.
3. ASCII bytes are always represented as themselves in UTF-8 files. They cannot be hidden inside multibyte UTF-8 sequences.
   The ASCII z 01111010 cannot be encoded as a two-byte UTF-8 sequence 11000001 10111010. Code points must be encoded using the shortest possible sequence. A corollary is that decoders must detect long-winded sequences as invalid. In practice, it is useful for a decoder to use the Unicode replacement character, code point FFFD, as the decoding of an invalid UTF-8 sequence rather than stop processing the text.
4. UTF-8 is self-synchronizing.
   Let's call a byte of the form 10xxxxxx a continuation byte. Every UTF-8 sequence is a byte that is not a continuation byte followed by zero or more continuation bytes. If you start processing a UTF-8 file at an arbitrary point, you might not be at the beginning of a UTF-8 encoding, but you can easily find one: skip over continuation bytes until you find a non-continuation byte. (The same applies to scanning backward.)
5. Substring search is just byte string search.
   Properties 2, 3, and 4 imply that given a string of correctly encoded UTF-8, the only way those bytes can appear in a larger UTF-8 text is when they represent the same code points. So you can use any 8-bit safe byte at a time search function, like strchr or strstr, to run the search.
6. Most programs that handle 8-bit files safely can handle UTF-8 safely.
   This also follows from Properties 2, 3, and 4. I say “most” programs, because programs that take apart a byte sequence expecting one character per byte will not behave correctly, but very few programs do that. It is far more common to split input at newline characters, or split whitespace-separated fields, or do other similar parsing around specific ASCII characters. For example, Unix tools like cat, cmp, cp, diff, echo, head, tail, and tee can process UTF-8 files as if they were plain ASCII files. Most operating system kernels should also be able to handle UTF-8 file names without any special arrangement, since the only operations done on file names are comparisons and splitting at /. In contrast, tools like grep, sed, and wc, which inspect arbitrary individual characters, do need modification.
7. UTF-8 sequences sort in code point order.
   You can verify this by inspecting the encodings in the table above. This means that Unix tools like join, ls, and sort (without options) don't need to handle UTF-8 specially.
8. UTF-8 has no “byte order.”
   UTF-8 is a byte encoding. It is not little endian or big endian. Unicode defines a byte order mark (BOM) code point FFFE, which are used to determine the byte order of a stream of raw 16-bit values, like UCS-2 or UTF-16. It has no place in a UTF-8 file. Some programs like to write a UTF-8-encoded BOM at the beginning of UTF-8 files, but this is unnecessary (and annoying to programs that don't expect it).

UTF-8 does give up the ability to do random access using code point indices. Programs that need to jump to the nth Unicode code point in a file or on a line—text editors are the canonical example—will typically convert incoming UTF-8 to an internal representation like an array of code points and then convert back to UTF-8 for output, but most programs are simpler when written to manipulate UTF-8 directly.

Programs that make UTF-8 more complicated than it needs to be are typically trying to be too general, not wanting to make assumptions that might not be true of other encodings. But there are good tools to convert other encodings to UTF-8, and it is slowly becoming the standard encoding: even the fraction of web pages written in UTF-8 is nearing 50%. UTF-8 was explicitly designed to have these nice properties. Take advantage of them.

For more on UTF-8, see “Hello World or Καλημέρα κόσμε or こんにちは 世界,” by Rob Pike and Ken Thompson, and also this history.

Distracted by reinstalling my notebook and some Real Life “stuff”, the slow progress continues.

I have a script that largely massages syscalls.master into something I want to work on.

Further work is needed on types, on deciding what system calls not to expose, and which system calls need wrapping.

実践Go言語(Effective Go)の翻訳、9回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

メソッド

ポインタ vs. 値

メソッドは、名前がつけられていればポインタとインタフェースを除くすべての型に定義することができます。（レシーバは構造体である必要はありません。）

以前、スライスの説明のところで書いたAppend関数を今度はスライスのメソッドとして定義してみます。これにはまず、メソッドと結びつけるために新たに名前付きの型を宣言し、メソッドにこの型のレシーバを定義します。

type ByteSlice []byte

func (slice ByteSlice) Append(data []byte) []byte {
    // 本体部分は前と全く同じ
}

このままでは、更新したスライスをメソッドから返す必要がまだ残っています。レシーバとしてByteSliceへのポインタを受け取るようメソッドを定義しなおすことによって、その問題を回避できます。こうすれば呼び出し元のスライスに対しメソッド内から上書き可能になります。

func (p *ByteSlice) Append(data []byte) {
    slice := *p
    // 本体部分は上とおなじだが、returnは除外
    *p = slice
}

実のところ、もう少し改善可能です。たとえば、この関数を標準的なWriteメソッドに合わせるように変更すると下のようになります。

func (p *ByteSlice) Write(data []byte) (n int, err os.Error) {
    slice := *p
    // これも上と同じ
    *p = slice
    return len(data), nil
}

このようにすることで*ByteSlice型は、利便性の高い標準インタフェースio.Writerを満たすようになり、下の例のようにスライスに対し出力することが可能となります。

    var b ByteSlice
    fmt.Fprintf(&b, "This hour has %d days\n", 7)

上でByteSliceのアドレスを渡しているのは、*ByteSliceでなければio.Writerインタフェースを満たさないためです。レシーバとしてポインタまたは値のどちらを受け取るかによって、次の違いがあります。レシーバとして値を受け取るメソッドでは、ポインタまたは値で呼び出すことができますが、ポインタを受け取るメソッドでは、ポインタでしか呼び出すことができません。これは後者ではメソッド内でレシーバを変更可能であるためです。(複製された値に加えた変更は破棄されてしまうため。）

ちなみに、Writeをバイトのスライスで使うというアイデアはbytes.Bufferで実装済です。

実践Go言語(Effective Go)の翻訳、8回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

初期化

初期化において、Go言語とCやC++言語では見かけ上それほど差がないように見えますが、Go言語の初期化はより強力です。複合構造体は初期化を行いながら構築することが可能です。また異なるパッケージ間においてもオブジェクトの初期化順序は正しく取り扱われます。

定数

Go言語における定数は、その名の通り「定数」です。定数はコンパイル時に作成されます。これは定数が関数内でローカルに定義されているときも同様です。ただし定数となり得るのは数値、文字列、論理値だけです。定数はコンパイル時に作成されるという制約上、コンパイラによって評価可能な定数式でなければなりません。たとえば1<<3は定数式ですが、math.Sin(math.Pi/4)は定数式ではありません。これは後者を評価するためにはmath.Sinの呼び出しが必要となるためです。

Go言語での定数の列挙にはiota列挙子を使います。iotaは式の一部となって、かつその式は暗黙的に繰り返すことができるので値の複雑なセットも簡単に作成することができます。

type ByteSize float64
const (
    _ = iota  // 一番目の値はブランク識別子に代入して無視
    KB ByteSize = 1<<(10*iota)
    MB
    GB
    TB
    PB
    EB
    ZB
    YB
)

Stringのようなメソッドを型と結びつけることができるので、型の一部として上のような値を出力用に自前で自動フォーマットすることが可能になります。

func (b ByteSize) String() string {
    switch {
    case b >= YB:
        return fmt.Sprintf("%.2fYB", b/YB)
    case b >= ZB:
        return fmt.Sprintf("%.2fZB", b/ZB)
    case b >= EB:
        return fmt.Sprintf("%.2fEB", b/EB)
    case b >= PB:
        return fmt.Sprintf("%.2fPB", b/PB)
    case b >= TB:
        return fmt.Sprintf("%.2fTB", b/TB)
    case b >= GB:
        return fmt.Sprintf("%.2fGB", b/GB)
    case b >= MB:
        return fmt.Sprintf("%.2fMB", b/MB)
    case b >= KB:
        return fmt.Sprintf("%.2fKB", b/KB)
    }
    return fmt.Sprintf("%.2fB", b)
}

式YBの出力は1.00YBになり、ByteSize(1e13)の出力は9.09TBとなります。

変数

変数は、定数と同じように初期化することができますが、変数のイニシャライザは通常の式であり、実行時に評価されます。

var (
    HOME = os.Getenv("HOME")
    USER = os.Getenv("USER")
    GOROOT = os.Getenv("GOROOT")
)

init関数

最後になりますが、各ソースファイルにはそれぞれ必要に応じて、セットアップのためにinit()関数を定義することができます。ひとつだけ制約があり、初期化中にゴルーチンを起動することはできますが、初期化が完了するまで実行は開始しません。すなわち、初期化処理中に実行されるスレッドは常にひとつだけです。

init()関数は、パッケージでインポートしている他のパッケージが初期化されたあと、パッケージ内で宣言されているすべての変数のイニシャライザが評価されたあとに呼び出されます。init()関数の一般的な使い方は、宣言としては記述できないような初期化処理を行うほか、処理の実行開始直前に、プログラムのステートの妥当性チェックおよびステートの修正を行います。

func init() {
    if USER == "" {
        log.Exit("$USER not set")
    }
    if HOME == "" {
        HOME = "/usr/" + USER
    }
    if GOROOT == "" {
        GOROOT = HOME + "/go"
    }
    // GOROOTはコマンドラインから--gorrotフラグを指定することで上書き可能
    flag.StringVar(&GOROOT, "goroot", GOROOT, "Go root directory")
}

For the past couple of weeks, I've been working on one of those projects that seems to suck up every available moment (and some that technically aren't). Now, however, it's largely done, and as an extra bonus, I've been given permission to release it as an early preview for those that are interested.

The code in question is a new implementation of the local datastore for the Python App Engine SDK. While some of you are probably delighted at the news, I expect most of you are puzzled. Why do we need a new local datastore implementation? Let me explain.

The purpose of the local stubs in the App Engine SDK is to exactly replicate the behaviour of the production environment, and in general they do that very well. A specific non-goal is replicating the performance characteristics of the production environment, or being as scalable as the production environment - the stubs are designed for testing, not production use.

The Python SDK's datastore implementation operates by storing the entire contents of your development datastore in memory. It writes changes to disk so that it can reload your datastore when the dev_appserver is restarted, but the in-memory copy is the primary source for all operations. Queries are executed by iterating over every entity of the right kind and filtering based on the criteria you specify.

Despite the use of a linear scan, this straightforward implementation is more than sufficient for most developers. The amount of test data one typically wants to load is fairly small, and it's hard to beat the performance you get from having everything stored in memory. Problems arise, however, when you need to load a larger than normal amount of test data into your app. As soon as the amount of stored data (including storage and indexing overhead) exceeds your available physical memory, performance slows down dramatically, as the dev_appserver has to page bits of the datastore to and from disk. Startup performance can be impacted, too, since the datastore stub has to read the entire datastore off disk each time the dev_appserver is started.

The new local datastore implementation fixes both these issues by rewriting the datastore stub to use SQLite as a backend. Data is stored by SQLite on disk, so memory consumption should not be a problem, and startup times will likewise be unaffected by the size of the local datastore. Here's what you can expect with the new datastore stub:

• Improved startup times if you store a lot of data in your local datastore.
• Improved performance if you store a lot of data in your local datastore.
• Lower memory consumption.

Equally importantly, though, here's what you shouldn't expect:

• Performance improvements when dealing with small amounts of data. Although a linear scan for all queries sounds inefficient, it really is hard to beat keeping all your data in memory for speed - so if you have relatively little data, you may not see much or any improvement.
• A relational schema. If you open up the SQLite database created by the dev_appserver, don't expect it to be laid out with a table per kind, and columns for properties. More on how the datastore is structured later, if you're interested.

Also, please bear in mind that this is pre-release code. It may wipe out all your data. It may cause the spontaneous generation of a black hole which swallows your cat. It may even work as expected! Nearly anything could happen.

Without further ado, you can get the patch and instructions on how to use it here. Feedback is appreciated - either in the groups, or right here on my blog.

How it works

What follows is a description of some of the internal workings of the datastore_sqlite_stub. If you just want to use it, you can stop now - otherwise, read on!

The basic structure of the SQLite stub is very similar to that used by the production datastore. An 'Entities' table holds all the entities, indexed by entity type and the 'path' component of their key. An 'EntitiesByProperty' table stores every indexed property for every entity, with columns for kind, property name, property value, and the path of the entity this row refers to.

All permitted queries can be executed by selecting from the Entities table, with some number of joins to the EntitesByProperty table. For example, a kind-only query or an ancestor-only query can be satisfied by the Entities table alone. A single property query requires a single join to the EntitiesByProperty table, constrained to find only entities with the correct kind, property name, and value (or range of values). Finally, multiple property queries are satisfied by using multiple joins to the EntitiesByProperty table, one for each required property. Unlike the production datastore, composite indexes aren't (currently) implemented, so queries that would normally require a composite indexes use the aforementioned strategy, leaving it up to the DB to find an efficient query plan.

Another difference from the production datastore is that data in the SQLite stub is partitioned by app ID - so each app has its own Entity and EntitiesByProperty tables.

Data representation and indexing

Data representation provides a particular challenge when it comes to indexing. App Engine provides a wide array of data types, and since the datastore is schemaless, any field can potentially contain any datatype.

Unlike most relational databases, SQLite uses a dynamic typing system, whereby any field can be of any data type - types declared in CREATE TABLE statements merely define 'affinities'. At first glance, this would appear to solve our problem - we can simply store the values as you would expect, and SQLite will allow us. We immediately run into a couple of problems, however.

The first problem is that SQLite doesn't provide the same sorting characteristics as the App Engine datastore. For example, while App Engine sorts all integers before all floats, SQLite sorts them by their magnitude. This could be remedied by splitting the column into two parts - the type and the value - and sorting by them and selecting on them both, were it not for the second issue...

The second issue is that SQLite doesn't implement all the data types App Engine provides - for example, Key and GeoPt. In order to be completely consistent with production, the ordering on these properties is important, too - it's not enough to be able to check for equality. Given that, it looks like we're going to need an alternative encoding scheme.

At first glance, Protocol Buffers seem like they should be it. Given the same values for fields, the Protocol Buffer encoder will always create the same binary PB, so we can definitely compare for equality. Individual fields of a Protocol Buffer are emitted in order, too, so thanks to the way the App Engine PBs are designed, in theory we ought to sort each data type correctly as well. This brilliant idea, alas, is torpedoed by several practical issues with sorting Protocol Buffers:

1. PBs encode fixed length fields like integers and floats little-endian, which doesn't sort correctly.
2. Variable length integers are encoded using a scheme that likewise does not preserve ordering of the number being encoded.
3. Strings are length-prefixed, which means strings are compared first based on size, then on contents - 'aaa' sorts after 'z'!

In production, App Engine solves this by using a special encoding for Protocol Buffers that preserves the desired ordering properties - and that's the approach the SQLite stub takes, too. Here's how it deals with each of the three issues outlined above:

1. Fixed length numbers are encoded big-endian, so they sort as expected. Further, the sign bit is flipped, and the entire value is inverted with a bitwise NOT if it's negative, to ensure that negative numbers sort smaller than positive numbers.
2. Variable length integers are encoded by a special scheme that uses the first byte to indicate the sign of the number and the number of bytes that follow. Small values (between -119 and 119) are encoded in a single byte to save space.
3. Strings are escaped instead of being length prefixed. Nulls in a string (\0) are replaced with the escape sequence \1\1, while \1 bytes are replaced with \1\2. Strings are then terminated with a null byte. This encoding is reversible, but ensures the strings still sort in the same order as they did previously.

With a Protocol Buffer encoder that implements those tweaks, we can simply encode the fields we want to index using it, and insert them as BLOB fields into the database. The encoding ensures that SQLite can sort them as byte values, without needing to interpret or understand them, and the sort order will come out as expected.

That's it for the description of the internals. If you decide to try out the new local datastore, please do provide feedback - here, or in the official group.

C has always permitted comparisons between any integer type, and C++ follows its lead. Comparing signed types to signed types is straightforward: you sign extend the smaller type. Likewise, when comparing unsigned types to unsigned types, you zero extend. When comparing signed and unsigned types, the rules are less clear.

The C standard specifies a type ordering: long long > long > int > short > char. If the unsigned type appears in that ordering before the signed type, then the signed value is converted to the unsigned type. Note that this happens even if the types are the same size (e.g., either long long and long or long and int are often the same size). Otherwise, if the signed type is larger than the unsigned type, in the sense of having more bits, then the unsigned value is converted to the signed type. Otherwise both values are converted to the unsigned type which corresponds to the signed type.

Pre-standard K&R C used a different rule, but that is old enough now that we no longer have to worry about it.

What this rule means is that if you write portable code, such that you don’t know the sizes of types, you can not predict whether the comparison will be done as a signed comparison or an unsigned comparison. Therefore, the gcc compiler has an option -Wsign-compare. However, this option is sufficiently awkward to avoid that it is not part of -Wall, though it is part of -Wextra (the difference between -Wall and -Wextra is that the former gives warnings for which false positives are easy to avoid through simple code changes; the latter gives warnings which are generally useful but for which false positives are harder to avoid).

There are good reasons to use signed types: they don’t have odd behaviour around zero, so you can write i < limit - 1 without worrying about the case limit == 0. There are good reasons to use unsigned types for things like the number of elements in a container: you get the full range of sizes, rather than limiting yourself to only the positive half. In particular, the C++ standard containers use unsigned types as their size. Combining these two rules gets you in trouble with portable code. The only reasonable answer I can see for portable code is to use -Wsign-compare and work around the many false positive warnings.

Go avoids these problems in two ways. First, there are no implicit conversions, so you can never be surprised by having a comparison become unsigned when you expected signed. You have to explicitly say which type of conversion you mean. Second, Go intentionally discards half of memory, and takes the philosophy that if you want a container which can hold more values than fit in a signed int, you should write a special purpose large container.

実践Go言語(Effective Go)の翻訳、7回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

データ

new()による割り当て

Go言語の基本的なメモリ割り当てには、new()とmake()の2つがあります。これら2つはそれぞれ異なる働きをし、適用先の型も別となります。混乱させてしまうかもしれませんがルールは単純です。

まずnew()について説明します。これは組み込み関数であり、他の言語におけるnew()と基本的に同じです。new(T)は、型Tの新しいアイテム用にゼロ化した領域を割り当て、そのアドレスである*T型の値を返します。Go言語風に言い換えると、new(T)が返す値は、新しく割り当てられた型Tのゼロ値のポインタです。

new()から返されるメモリはゼロ化されています。ゼロ化済みオブジェクトは、さらなる初期化を行わなくても使用できるため、こういったオブジェクトの準備にnew()は便利です。すなわち、データ構造体の利用者がnew()でそれを作成すると、すぐに使える状態となります。たとえば、bytes.Bufferのドキュメントには、「Bufferのゼロ値は、利用準備が整った空のバッファである。」と記述されています。同様にsync.Mutexには明示的なコンストラクタやInitメソッドは用意されていませんが、その代わりにsync.Mutexのゼロ値は、非ロック状態のミューテックスであることが定められています。

この便利なゼロ値は連鎖的に働きます。下の型宣言をみてください。

type SyncedBuffer struct {
    lock    sync.Mutex
    buffer  bytes.Buffer
}

このSyncedBuffer型の値もまた、割り当てや宣言を行うと同時に使用準備が整います。下のコードの変数pとvは、このままで正しく機能します。

p := new(SyncedBuffer)  // type *SyncedBuffer
var v SyncedBuffer      // type  SyncedBuffer

コンストラクタと複合リテラル

下の例はosパッケージからの抜粋です。この例のようにゼロ値では充分でなく、コンストラクタによる初期化が必要となることがあります。

func NewFile(fd int, name string) *File {
    if fd < 0 {
        return nil
    }
    f := new(File)
    f.fd = fd
    f.name = name
    f.dirinfo = nil
    f.nepipe = 0
    return f
}

上のコードには冗長な部分が多く見られます。複合リテラルとは、実行する度に新しいインスタンスを生成する式であり、これを使うことで下のコードのように単純化することができます。

func NewFile(fd int, name string) *File {
    if fd < 0 {
        return nil
    }
    f := File{fd, name, nil, 0}
    return &f
}

このようにローカル変数のアドレスを返しても問題ありません。関数から戻ったあとも、変数に割り当てたメモリは生き残ります。複合リテラルのアドレスを取得したときは、実行する度に新しいインスタンスが割り当てられる仕様なので、最後の2行を次のようにまとめることができます。

    return &File{fd, name, nil, 0}

複合リテラルでは、すべてのフィールドを順番通りに記述しなければなりません。ただし明示的に「フィールド:値」の組み合わせで要素にラベルをつけたときは、イニシャライザは順序通りである必要はなく、また指定しなかった要素には、その型のゼロ値がセットされます。すなわち次のように書き換えられます。

    return &File{fd: fd, name: name}

特殊なケースとして、複合リテラルがひとつもフィールドを含まないときは、その型のゼロ値が作られます。すなわち、式new(File)と&File{}は等価です。

また複合リテラルでは、フィールドのラベルをインデックスまたはマップのキーとみなして、配列、スライス、マップを作成することもできます。次の例において、Enone、Eio、Einvalがそれぞれ個別の変数でありさえすれば、その値に関わらず初期化は成功します。

a := [...]string   {Enone: "no error", Eio: "Eio", Einval: "invalid argument"}
s := []string      {Enone: "no error", Eio: "Eio", Einval: "invalid argument"}
m := map[int]string{Enone: "no error", Eio: "Eio", Einval: "invalid argument"}

make()による割り当て

割り当てに話を戻します。組み込み関数make(T, args)は、new(T)とは使用目的が異なります。makeで割り当てできるのはスライス、マップ、チャネルだけであり、初期化された、すなわちゼロ値でないT型(*Tでない)の値を返します。makeとnewを使い分ける理由は、これらの3つの型が隠蔽されたデータ構造への参照であり、このデータ構造が使用前に初期化されている必要があるためです。スライスを例にとると、スライスはデータ(配列内)へのポインタ、長さ、キャパシティという３つの情報から構成されており、それらの情報が初期化されるまではスライスの値はnilです。makeはスライス、マップ、チャネルの内部データ構造を初期化し、使用可能となるよう値を準備します。下は、makeの例です。

make([]int, 10, 100)

この例では、100個のintを持つ配列を割り当てたあと、その配列の先頭から10個目までの要素を示す、長さが10でキャパシティ100のスライス構造を作成します。(スライス作成時、キャパシティは省略可能です。詳細はスライスに関するセクションを参照ください。)これに対して、new([]int)は新しくメモリを割り当て、ゼロ化したスライス構造のポインタを返します。つまりこれはnilスライス値へのポインタです。

下は、new()とmake()の違いを例示したものです。

var p *[]int = new([]int)       // スライス構造の割り当て(*p == nil)。あまり使わない。
var v  []int = make([]int, 100) // vは100個のintを持つ配列への参照

// 必要以上に複雑な書き方
var p *[]int = new([]int)
*p = make([]int, 100, 100)

// 一般的な書き方
v := make([]int, 100)

覚えておいていただきたいことは、make()が適用可能なのはマップ、スライス、チャネルだけであり、返されるのはポインタではないことです。ポインタが必要であればnew()で割り当ててください。

配列

配列はメモリ配置を厳密に指定したいときや、ときにはメモリ割り当てを回避したいときに役立ちますが、配列の主な役割は、次セクションの主題であるスライスから参照されることです。そのスライスについて説明する前に基礎知識として、配列について2、3説明しておきます。

Go言語とC言語では配列の動作に大きな違いがあります。Go言語では次のように振舞います。

• 配列は値です。ある配列を他へ代入するとすべての要素がコピーされます。
• すなわち関数に配列を渡すと、関数側ではポインタではなく、その配列のコピーを受け取ります。
• 配列のサイズは型の一部です。[10]intと[20]intは異なる型です。

値として扱うと有用なこともありますが、高コストでもあるため、C言語のような動作と効率が必要であれば、配列へのポインタを関数に渡すことも可能です。

func Sum(a *[3]float) (sum float) {
    for _, v := range *a {
        sum += v
    }
    return
}

array := [...]float{7.0, 8.5, 9.1}
x := Sum(&array)  // 注：明示的にアドレス演算子を使用

しかし、これはGo言語では一般的ではなく、通常はスライスを使用します。

スライス

スライスは配列をラップして、データ列に対しより普遍的かつ効果的で使い易いインタフェースを提供します。変換行列のような明らかに多次元のデータ構造を扱う場合を除いて、配列を扱うGo言語のプログラムでは、配列そのままではなくスライスが多用されます。

スライスは参照型です。すなわちスライスを別のスライスに代入したときは、双方が同じ配列を参照します。たとえば関数がスライスを引数として取るとき、関数内でスライスの要素に変更を加えると、ポインタ渡しのように関数の呼び元からも変更内容が参照できます。ゆえにRead関数では、引数としてポインタと個数を受け取る代わりに、スライスを受け取ることが可能となります。このときスライスが持つ長さ情報は、読み込むべきデータの上限となります。下は、osパッケージのFile型のReadメソッドのシグネチャです。

func (file *File) Read(buf []byte) (n int, err os.Error)

このメソッドは読み込んだバイト数と、エラーがあればエラー値を返します。ある大きなバッファbufから先頭32バイトを読み込むためには、次のようにバッファをスライスしてください。※この「スライス」という言葉は名詞ではなく動詞です。

    n, err := f.Read(buf[0:32])

こういったスライスの使い方は一般的かつ効率的です。実際のところ、あまり効率を考慮に入れなければ、下のコードでも同様にバッファの先頭32バイトを読み込めます。

    var n int
    var err os.Error
    for i := 0; i < 32; i++ {
        nbytes, e := f.Read(buf[i:i+1])  // 1バイト読み込み
        if nbytes == 0 || e != nil {
            err = e
            break
        }
        n += nbytes
    }

スライスが持つ長さ情報は、その参照先配列の範囲内であれば変更することができます。(試しにスライスを同じスライスに代入し直してみてください。) スライスのキャパシティは組み込み関数のcapで参照できます。キャパシティとはスライスが扱える長さの上限値です。
下はスライスにデータを追加する関数です。この関数ではデータの長さがキャパシティを超えるときは、スライスは再割り当てされ、結果得られたスライスが関数から返されます。nilスライスが関数に与えられたときには、仕様上nilスライスがlen、capともに0を返すことを利用しています。

func Append(slice, data[]byte) []byte {
    l := len(slice)
    if l + len(data) > cap(slice) {  // reallocate
        // 再利用を考慮し、必要なサイズの倍、割り付ける
        newSlice := make([]byte, (l+len(data))*2)
        // Copy data (could use bytes.Copy()).
        for i, c := range slice {
            newSlice[i] = c
        }
        slice = newSlice
    }
    slice = slice[0:l+len(data)]
    for i, c := range data {
        slice[l+i] = c
    }
    return slice
}

Appendではsliceの要素を変更していますが、スライス自体(ランタイムデータ構造がポインタ、長さ、キャパシティを保持している)は値渡しされているため、処理を終えたあと関数からスライスを返す必要があります。

マップ

マップは、異なる型の値を結びつける便利で強力な組み込みデータ構造です。マップのキーには、イコール演算子が定められていればどんな型(例えば整数、浮動小数、文字列、ポインタ、動的な型がイコールをサポートするのであればインタフェースさえ)でも使えます。ですが構造体、配列、スライスにはイコールが定義されていないため、マップのキーとして使用することはできません。スライスと同じくマップもまた参照型であるため、マップを関数に渡し、その関数内でマップの内容に変更を加えると、変更内容は呼び出し元からも参照可能です。

複合リテラル構文を使い、キーと値をコロン区切りで指定することでマップを作成できるので、作成と同時に初期化が簡単に行えます。

var timeZone = map[string] int {
    "UTC":  0*60*60,
    "EST": -5*60*60,
    "CST": -6*60*60,
    "MST": -7*60*60,
    "PST": -8*60*60,
}

マップへの値の設定と取得は、配列の操作と構文的に似通っていますが、インデックスが整数である必要がない点で異なります。マップ内に存在しないキーを使って、マップから値を取得しようとするとプログラムがクラッシュする要因と成り得るので、これを回避するため下のように複数代入式を使ってください。

var seconds int
var ok bool
seconds, ok = timeZone[tz]

これは見たままですが、「カンマok」慣用句と呼ばれています。この例では、tzが存在すれば、secondsに適切な値がセットされ、okの値は真となります。存在しなければ、secondsにはゼロがセットされ、okの値は偽となります。下はこれを利用した関数です。

func offset(tz string) int {
    if seconds, ok := timeZone[tz]; ok {
        return seconds
    }
    log.Stderr("unknown time zone", tz)
    return 0
}

マップ内に値が存在するか調べたいとき、値自体の取得が不要であればブランク識別子(ただのアンダーライン(_))を使うことができます。ブランク識別子を使うとどんな型の値でも代入または宣言することができ、値を他に影響およぼすことなく破棄することができます。マップ内の存在チェックをするときは、次のように本来は値が返される変数の代わりにブランク識別子を指定してください。

_, present := timeZone[tz]

マップから登録を削除するには、代入方向を変えて複数代入式の右側に論理値を指定してください。この論理値の値が偽のとき登録が削除されます。このときマップ内にキーが存在しなくても問題ありません。

timeZone["PDT"] = 0, false  // 標準時に

出力

Go言語におけるフォーマット出力は、C言語のprintf群のスタイルと類似していますが、より高機能・多機能です。これら関数はfmtパッケージ内で定義されています。先頭一文字は大文字となっており、fmt.Printf、fmt.Fprintf、fmt.Sprintfなどが用意されています。文字列関数(Sprintfなど)は、指定したバッファに文字列を格納するのではなく、新しい文字列を返します。

フォーマット文字列の指定は必要ではありません。各Printf、Fprintf、Sprintfにはそれぞれ他にペアとなる関数、例えばPrintとPrintlnが用意されています。これらの関数はフォーマット文字列をとらず、代わりに引数ごとにデフォルトフォーマットを生成します。ln版では、引数の間に両引数とも文字列でないときだけ空白を挿入し、出力の後ろに改行を付加します。[訳注：実際試したところ、非ln版のときは引数がともに文字列でないときだけ引数間に空白が挿入されるのに対し、ln版のときは常に空白が挿入されるようです] 下の例では、各行はいずれも同じ内容を出力します。

fmt.Printf("Hello %d\n", 23)
fmt.Fprint(os.Stdout, "Hello ", 23, "\n")
fmt.Println(fmt.Sprint("Hello ", 23))

チュートリアルでも解説したように、fmt.Fprintとそれに関連する関数は、一番目の引数にio.Writerインタフェースを実装していればどんなオブジェクトでも指定可能です。 よく使われるのは、お馴染みの変数os.Stdouとos.Stderrです。

ここからC言語との違いが現れます。まず、%dのような数値フォーマットでは、フラグによる符号やサイズの指定は行いません。その代わりに出力ルーチンは、引数の型を参照して値の属性を決定します。

var x uint64 = 1<<64 - 1
fmt.Printf("%d %x; %d %x\n", x, x, int64(x), int64(x))

これの出力結果です。

18446744073709551615 ffffffffffffffff; -1 -1

例えば整数値を10進表記で出力するようなデフォルトの変換でよければ、どんなケースにも対応可能なフォーマット%vを使うことができます。このとき出力される内容は、PrintとPrintlnの出力結果と全く同じです。さらにこのフォーマットは、配列、構造体、マップなどどんな値でも出力することができます。下は、前のセクションで定義したタイムゾーンマップを出力するステートメントです。

fmt.Printf("%v\n", timeZone)  // fmt.Println(timeZone)としても同じ

これの出力結果です。

map[CST:-21600 PST:-28800 EST:-18000 UTC:0 MST:-25200]

マップの出力では、キーの出力は当然ながら順不同となります。
構造体を出力するとき、限定フォーマット%+vを使うと構造体の各フィールドに対してフィールド名も出力されます。また、代替フォーマット%#vを使うとどんな値でも完全なGo言語の構文形式で出力されます。

type T struct {
    a int
    b float
    c string
}
t := &T{ 7, -2.35, "abc\tdef" }
fmt.Printf("%v\n", t)
fmt.Printf("%+v\n", t)
fmt.Printf("%#v\n", t)
fmt.Printf("%#v\n", timeZone)

これらの出力結果です。(アンパサンドに注意)

&{7 -2.35 abc   def}
&{a:7 b:-2.35 c:abc     def}
&main.T{a:7, b:-2.35, c:"abc\tdef"}
map[string] int{"CST":-21600, "PST":-28800, "EST":-18000, "UTC":0, "MST":-25200}

引用符付き文字列の出力も、stringまたは[]byte型の値に対して%qを使えば可能です。(代替フォーマット%#qでは、可能であればバッククォートを使います。) また%xを文字列またはバイト配列に対して適用したときは、整数に適用したときと同様に、長い16進数文字列を出力します。このときフォーマットにスペースを入れると(% x)、バイト間にスペースが出力されます。

もう一つの便利なフォーマットは%Tです。これは値の型を出力します。

fmt.Printf("%T\n", timeZone)

これの出力結果です。

map[string] int

自作の型でデフォルトのフォーマット処理を制御したければ、必要なことはその型にメソッドString() stringを定義するだけです。下は先ほどの型Tに実装してみた例です。

func (t *T) String() string {
    return fmt.Sprintf("%d/%g/%q", t.a, t.b, t.c)
}
fmt.Printf("%v\n", t)

これのフォーマット出力結果です。

7/-2.35/"abc\tdef"

自作のString()メソッドはSprintfからも呼び出されます。これは出力ルーチンが完全にリエントラント(再入可能)かつ再帰的に呼び出されるためです。もう少し手を加えて、出力ルーチンが受け取った引数を、同様の別ルーチンにそのまま渡すことも可能です。Printfのシグネチャの最後の引数には…型が使われているため、フォーマット指定以降には、いくつでもパラメータを指定できます。

func Printf(format string, v ...) (n int, errno os.Error) {

Printf関数内の変数vは、別の出力ルーチンに渡すことも可能です。下は、以前使用した関数log.Stderrの実装です。ここでは、実際にフォーマット処理を行うために、fmt.Sprintlnに引数をそのまま渡しています。

// Stderrは標準出力にログを簡単に出力するヘルパー関数です。Fprint(os.Stderr)と似ています。
func Stderr(v ...) {
    stderr.Output(2, fmt.Sprintln(v))  // Outputはパラメータ (int, string)を取る
}

ここで説明した範囲は出力機能のほんの一部です。より詳しい説明はパッケージfmtのgodocドキュメントを参照ください。

After the unfortunate outage the other day, how to handle downtime with your App Engine app is a bit of a hot topic. So what better time to address proper error handling for situations where App Engine isn't performing at 100%?

There's three major topics to cover here: Handling timeouts from API calls, using the Capabilities API, and testing your app's support for handling failures. We'll go over them in order.

Handling timeouts

At the 'stub' level, timeouts and other exceptions are communicated by the stub throwing an google.appengine.runtime.apiproxy_errors.ApplicationError. ApplicationError instances have an 'application_error' field, which contains an ID, drawn from google.appengine.runtime.apiproxy_errors, which indicates the cause of the error. As you can see, DEADLINE_EXCEEDED is 4. Other errors of interest are OVER_QUOTA, which will occur if your app runs out of quota for a given API call or capability, and CAPABILITY_DISABLED, which is thrown if the API capability has been explicitly disabled (more on this later).

Each of the various APIs catches ApplicationErrors thrown by their stub, and wraps them in a higher level exception. The datastore, for example, has a function, _ToDatastoreError that maps different error codes to exceptions from datastore_errors, which results in an ApplicationError(4) being transformed into a datastore_errors.Timeout exception. The urlfetch API, similarly, maps exceptions, with a timeout (along with some other errors) being represented as a DownloadError.

The best way to handle timeouts varies from API to API. The datastore API now automatically retries timed out operations. If it cannot execute the operation even after multiple timeouts, it will return a db.Timeout exception (or a db.TransactionFailedError if the exception occurred inside a transaction). For an in-depth description of how to handle datastore timeouts and why they happen, I recommend this excellent and well written article.

Memcache, in contrast, generally won't return timeout errors on get operations, but will rather fail to return a value. Set operations return error codes rather than throwing exceptions, in conformance with the memcached API it imitates. See the memcache docs for details.

Wherever possible, you should handle exceptions on a call-by-call basis, and deal with them appropriately. Sometimes, however, an exception from a given API call simply means you're unable to service the user's request, and have to show them an error page and ask them to try again later. In such situations, it helps to have a catch-all exception handler, which gets invoked for any exceptions that make it to the top level of your app. The webapp framework provides just such a facility in the form of the handle_exception method, which gets called with the exception if your handler methods (get, post, etc) throw one. By default, this method calls self.error(500), logs the exception, and then prints the stacktrace to the output if debugging is enabled. Overriding this to present a nicer message to your users is probably a good idea - even better, override the error() method to display appropriate error pages for all the status codes your app can return!

The Capabilities API

While it's important to have proper exception handling for API calls, that's not all you can do. With the Capabilities API, you can proactively query App Engine to check if a given API, capability, or specific method is available. Documentation, unfortunately, is rather light at the moment, so consult the source for details.

In general, calls to the Capabilities API take a service name - such as 'memcache' or 'datastore_v3' - and optionally either a 'capability', such as 'write', or a specific method, such as 'put'. The API then returns whether or not that entire API, capability, or individual method is available. For example:

from google.appengine.api import capabilities

images_enabled = capabilities.CapabilitySet('images').is_enabled()
datastore_write_enabled = capabilities.CapabilitySet('datastore_v3', capabilities=['write']).is_enabled()
memcache_get_enabled = capabilities.CapabilitySet('memcache', methods=['get']).is_enabled()

We can make use of this to, for example, create some WSGI middleware that automatically returns a friendly error message any time the datastore is entirely disabled (presuming our app is dependent on the datastore, and sets a flag in the WSGI environment if it's read-only:

def capability_middleware(application):
  def wsgi_app(environ, start_response):
    if not capabilities.CapabilitySet('datastore_v3').is_enabled():
      print_error_message(environ, start_response)
    else:
      environ['capabilities.read_only'] = capabilities.CapabilitySet('datastore_v3', capabilities=['write']).is_enabled()
      return application(environ, start_response)

  return wsgi_app

Obviously, far more sophisticated handling of disabled capabilities are possible - for example, you can use the 'read_only' flag the above middleware sets to disable any features of your site that require writing to the datastore, politely informing users that it's not available, rather than resorting to an error page.

Testing timeouts and capabilities

Once you've implemented proper error handling, and you're using the capabilities API, the question inevitably arises: How do I test this? We can do this using hooks - specifically, using a pre-call hook that throws the exception we want to test. Here's a class that makes it simple to test for error returns from APIs:

from google.appengine.runtime import apiproxy
from google.appengine.runtime import apiproxy_errors

class APIErrorHook(object):
  def __init__(self):
    self.error_map = {}  # Maps (api, method) tuples to error statuses

  def set_error_code(self, service, method, code):
    self.error_map[(service, method)] = code

  def get_error_code(self, service, method):
    """Returns the error code to return for a service and method, or None."""
    return self.error_map.get((service, method), None)

  def _error_hook(self, service, method, request, response):
    error_code = self.get_error_code(service, method)
    if error_code:
      raise apiproxy_errors.ApplicationError(error_code)

  def install(self, apiproxy, unique_name):
    apiproxy.GetPreCallHooks().Append(unique_name, self._error_hook)

This should all be fairly straightforward: Once the hook is installed, calling set_error_code with a service and method name will cause all future invocations to raise an ApplicationError with that code. Calling set_error_code with None as the code will make the API call operate normally again. Here's an example of it in use:

from google.appengine.api import apiproxy_stub_map

error_hook = APIErrorHook()
error_hook.install(apiproxy_stub_map.apiproxy, 'error_hook')

db.get(a_key)  # Works

error_hook.set_error_code('datastore_v3', 'Get', apiproxy.DEADLINE_EXCEEDED)
db.get(a_key)  # Throws a db.Timeout error

error_hook.set_error_code('datastore_v3', 'Get', None)
db.get(a_key)  # Works again

That's all there is to it. You can easily use this in your unit tests or for manual testing - just remember to install the API hook when you need it.

For testing the Capabilities API, we need a little more sophistication. The default implementation of the capability service always returns 'ENABLED' for every call. Normally, modifying this behaviour would require writing our own capability stub and reaching into the SDK to replace the default one with our implementation. Fortunately, however, the capabilities API is simple enough that we can instead register a post-call hook that changes the return value to whatever we want it to be. Here's an extension of the above class that adds the ability to enable and disable APIs:

class CapabilityHook(APIErrorHook):
  # Maps (service, method) tuples to the capability it depends on
  _CAPABILITY_MAP = {
    ('datastore_v3', 'Put'): 'write',
    ('datastore_v3', 'Delete'): 'write',
  }

  def __init__(self):
    self.disabled_capabilities = set()  # Set of (service, capability) tuples that are disabled
    super(CapabilityHook, self).__init__()

  def set_capability_disabled(self, service, capability, disabled):
    if disabled:
      self.disabled_capabilities.add((service, capability))
    else:
      self.disabled_capabilities.discard((service, capability))

  def get_error_code(self, service, method):
    if (service, '*') in self.disabled_capabilities:
      return apiproxy.CAPABILITY_DISABLED
    required_capability = CapabilityHook._CAPABILITY_MAP.get((service, method), None)
    if required_capability and (service, required_capability) in self.disabled_capabilities:
      return apiproxy.CAPABILITY_DISABLED
    return super(CapabilityHook, self).get_error_code(service, method)

  def _capability_hook(self, service, method, request, response):
    # Accumulate a mapping of capabilities to enabled-ness
    capabilities = {}
    for capability in request.capability_list():
      if (method, capability) in self.disabled_capabilities:
        capabilities[(method, capability)] = False
      else:
        capabilities[(method, capability)] = True
    for method in request.call_list():
      required_capability = CapabilityHook._CAPABILITY_MAP.get(method, '*')
      if required_capability in self.disabled_capabilities or (service, '*') in self.disabled_capabilities:
        capabilities[(method, capability)] = False
      else:
        capabilities.setdefault((method, capability), True)

    # Add them to the response
    response.clear_config()
    for (service, capability), enabled in capabilities.items():
      config = response.add_config()
      config.set_package(service)
      config.set_capability(capability)
      config.set_status(capabilities.IsEnabledResponse.ENABLED if enabled else capabilities.IsEnabledResponse.DISABLED)

    # Calculate the summary response
    config.set_summary_status(capabilities.IsEnabledResponse.ENABLED if False not in capabilities.values() else capabilities.IsEnabledResponse.DISABLED)

  def install(self, apiproxy, unique_name):
    apiproxy.GetPostCallHooks().Append(unique_name, self._capability_hook, 'capability_service')
    super(CapabilityHook, self).install(apiproxy, unique_name)

This is substantially more complicated than the previous handler, because it has to implement the intricacies of the capabilities API. The basic operation is fairly straightforward, however. The set_capability_disabled method allows you to disable or enable specific capabilities. To disable or enable an entire service, use set_capability_disabled with a capability name of '*'. CapabilityHook then extends the get_error_code method to add additional checks: It returns CAPABILITY_DISABLED if the entire service is disabled, or if the method being requested is mentioned in its _CAPABILITY_MAP with a capability name, and that capability is disabled.

The class also implements a post-call hook for the capability service; this modifies responses by checking its own internal list of capabilities and assembling a response appropriately. The summary status is set to ENABLED iff all the individual queried capabilities and methods are themselves enabled.

Here's a simple example of it in use:

capability_hook = CapabilityHook()
capability_hook.install(apiproxy_stub_map.apiproxy, 'error_hook')

db.put(some_entity)  # Succeeds
db.get(some_key)  # Succeeds
capabilities.CapabilitySet('datastore_v3', capabilities=['write']).is_enabled()  # Returns True

capability_hook.set_capability_disabled('datastore_v3', 'write')
db.put(some_entity)  # Fails, raising datastore_errors.Error
db.get(some_key)  # Still succeeds
capabilities.CapabilitySet('datastore_v3', capabilities=['write']).is_enabled()  # Returns False

There you go: How to handle API call errors, how to detect disabled capabilities, and how to test both of them. Now you're prepared for the next scheduled maintenance, or the unlikely event of another unplanned outage!

Still working, nothing much more to show. The syscall package is being beaten into behaving.

I’ve received one offer to beta test; be sure I’ll post here (and to the NetBSD mailing lists) when I get to alpha and beta testing stages.

Cheers,

Giles

Increasing antibiotic resistance in bacteria is a nice demonstration of:

• The speed and effectiveness of evolutionary change.
• The Law of Unintended Consequences
• The danger of hospitals

Antibiotics are in effect poisons that don’t happen to affect humans, typically because they interfere with bacterial cell walls that our cells don’t have. It doesn’t take long in human terms for bacteria to develop resistance to antibiotics, though presumably it does take quite a while in bacteria terms. With regard to selection under extreme pressure from antibiotic poisons, bacteria have an advantage over more complex animals: they can evolve faster because they can exchange new genetic material directly rather than only passing it on to their children. This is isomorphic to cultural evolution in h humans: the way that a good idea can spread quickly through a human population.

The unintended consequences I see are three-fold. First, when the first antibiotics were used (i.e., penicillin) they were considered to be miracle drugs. People didn’t realize initially that miracles have a limited lifespan depending on how heavily you use them, and there are many penicillin resistant bacteria these days. Second, antibiotics were eventually spread through society in the form of soaps and creams. This turned out to be almost wholly counter-productive, in that it exposed bacteria to low levels of antibiotics, making it easier for them to evolve resistance before they were poisoned. Third, the industrial food system relies on antibiotics to keep animals alive and more-or-less well even though they live in exceedingly unhealthy conditions (packed in tightly, covered with feces, etc.). This has also greatly increased bacterial exposure to antibiotics, increasing resistance, thus unwittingly exchanging safer and cheaper food for increased danger in other areas of life.

The benefit of hospitals is that you can put experts and expensive equipment in one place where they can efficiently work to help people. The danger of hospitals is that you put all the sick people in the same place, which gives infections a steady supply of people who are weakened and less able to fight off infections. In effect hospitals become sanctuaries for infections. Two hundred years ago a hospital was not a place for healing; it was a place for dying. Modern medicine has changed that to an extraordinary degree. But antibiotic resistant bacteria remind us that is a hospital is a place you should go only when you have no other choice. Doctors making house calls is inefficient and expensive, but it would almost certainly be healthier for people who are not too sick to be cared for at home.

Jack Audio

$ sudo gpasswd -a <USER> audio

$ mount | grep shm

fs.inotify.max_user_watches = 524288

jackd -R -P89 -s -dalsa -dhw:0 -r48000 -p256 -n3

Connecting GStreamer to Jack

$ gst-inspect-0.10 | grep jack

Introducing libflashsupport-jack

Dear sweet VLC

<script charset="utf-8" expr:src=""http://feeds.feedburner.com/~s/goplexian?i=" + data:post.url" type="text/javascript"></script>

Frequently, it's necessary or useful to consume an Atom or RSS feed provided by another application. Doing so, though, is rarely as simple as it seems: To do so robustly, you have to worry about polling frequency, downtime, badly formed feeds, multiple formats, timeouts, determining which items are new and other such issues, all of which distract from your original, seemingly simple goal of retrieving new updates from an Atom feed. You're not alone, either: Everyone ends up dealing with the same set of issues, and solving them in more or less the same manner. Wouldn't it be nice if there was a way to let someone else take care of all this hassle?

As you've no doubt guessed, I'm about to tell you that there is. I'm speaking, of course, of PubSubHubbub. I discussed publishing to PubSubHubbub as part of the Blogging on App Engine series, but I haven't previously discussed what's required to act as a subscriber. Today, we'll cover the basics of PubSubHubbub subscriptions, and how you can use them to outsource all the usual issues consuming feeds.

At this point, you may be wondering how this is useful if the feed you're consuming doesn't support PubSubHubbub. Fortunately, the PubSubHubbub protocol provides for the possibility of hubs doing polling on feeds that do not support PubSubHubbub themselves. The public hub on http://pubsubhubbub.appspot.com/ doesn't currently have this enabled, but there are plenty of alternatives. First and foremost, you can run your own hub. The reference implementation is an App Engine app, so you can deploy it the same way you do your regular app. You can even deploy the hub as an alternate version under the same App ID, providing you with a 'private' hub that you can access the same way you would any other hub.

An easier alternative, however, is to use a hub provider that already supports polling. One such provider is superfeedr, who provide services for both publishers and subscribers. They're a commercial outfit, but they offer a "hackr plan", which is free if you monitor fewer than 1000 feeds - and their rates seem very reasonable. For simplicity, we'll be demonstrating subscriptions using their service, but the rest of the article applies equally to any other hub.

First, sign up to superfeedr. Once you've signed up and verified your account, you're ready to go!

Subscribing to a feed using hubbub is a three stage process:

1. Send a subscription request to the hub
2. Handle the subscription callback
3. Process notifications

We'll go over each of these steps, using an example app that allows users to receive notifications of new posts over XMPP. First, we need to define models to keep track of subscriptions and individual subscribers:

class Subscription(db.Model):
  @property
  def url(self):
    return self.key().name()

  verify_token = db.StringProperty(required=True)  # Random verification token.

class Subscriber(db.Model):
  @property
  def subscription(self):
    return self.parent
  
  @property
  def address(self):
    return self.key().name()

We're making heavy use of entity relationships and key names here. To enforce uniqueness, the key name of a Subscription entity is the URL of its feed, and Subscriber entities are child entities of Subscriptions, with their key name being the XMPP address of the subscriber.

Sending subscription requests

Now we can handle the first part of subscribing to a feed: Sending the request to the hub. Doing so is a straightforward matter of sending an HTTP POST request to the correct URL, as detailed in the hubbub spec. We'll do so when a user asks to be subscribed, using an XMPP Handler:

class XmppHandler(xmpp_handlers.CommandHandler):
  def send_subscription_request(self, subscription):
    subscribe_args = {
        'hub.callback': urlparse.urljoin(self.request.url, '/hubbub'),
        'hub.mode': 'subscribe',
        'hub.topic': subscription.url,
        'hub.verify': 'async',
        'hub.verify_token': subscription.verify_token,
    }
 
    headers = {}
 
    if HUB_CREDENTIALS:
      auth_string = "Basic " + base64.b64encode("%s:%s" % HUB_CREDENTIALS)
      headers['Authorization'] = auth_string
 
    response = urlfetch.fetch(HUB_URL, payload=urllib.urlencode(subscribe_args),
                              method=urlfetch.POST, headers=headers)
 
 
  def subscribe_command(self, message):
    if not message.arg.startswith("http"):
      message.reply("Subscription requests must consist of a URL to subscribe to")
      return
 
    created, subscription, subscriber = db.run_in_transaction(
        add_subscription,
        message.arg,  # URL to subscribe to
        message.sender,  # User who is subscribing
    )
 
    if created:
      self.send_subscription_request(subscription)
    
    message.reply("Subscription created!")

When a user sends a message starting with '/subscribe', the 'subscribe_command' method is called. After doing some basic verification, it calls 'add_subscription' inside a datastore transaction, which returns the subscription and subscriber entities. This is necessary to make sure we don't subscribe to the same feed multiple times. Here's the code for add_subscription:

def add_subscription(topic, recipient):
  created = False
  subscription = Subscription.get_by_key_name(topic)
  if not subscription:
    created = True
    subscription = Subscription(key_name=topic, verify_token=str(uuid.uuid4()))
  subscriber = Subscriber(key_name=recipient, parent=subscription)
  db.put([subscription, subscriber])
  return created, subscription, subscriber

If this user is the first to subscribe to this feed, the send_subscription_request method is called. This constructs a dictionary of arguments for the subscription request, consisting of the URL to send callbacks and updated entries to, the mode ('subscribe'), the topic we're subscribing to, and a couple of verification arguments - 'hub.verify' and 'hub.verify_token'. The first one specifies that we're happy to handle the verification callback after the current request has completed, and the second argument provides a secret token that only we and the hub know of. This is to make it impossible for other people to subscribe us to a feed without our permission, as we'll see shortly.

After assembling the dictionary of subscription arguments, we deal with authorization. Public hubs, like http://pubsubhubbub.appspot.com/ don't require any authentication, but other providers, such as superfeedr, do. If we provided credentials (a (username, password) tuple in the HUB_CREDENTIALS) variable), we add those to the request. Finally, we make the subscription request using urlfetch.

Handling subscription callbacks

Part 2 is handling the subscription callback from the hub. The hub does this to make sure that nobody else forged the subscription request, and to make sure that we are operating a valid endpoint. This is where the verify_token parameter from above comes in: When we receive a subscription callback, we should check that the hub.verify_token argument the hub is supplying matches the one we stored when we made the request. If it does, we respond to the request by echoing back the 'hub.challenge' string it sends us, to confirm that we really want to subscribe. Here's how we handle it in our app:

class CallbackHandler(webapp.RequestHandler):
  def get(self):
    if self.request.GET['hub.mode'] == 'unsubscribe':
      self.response.headers['Content-Type'] = 'text/plain'
      self.response.out.write(self.request.GET['hub.challenge'])
      return
      
    if self.request.GET['hub.mode'] != 'subscribe':
      self.error(400)
      return
 
    subscription = Subscription.get_by_key_name(self.request.GET['hub.topic'])
    if not subscription or subscription.verify_token != self.request.GET['hub.verify_token']:
      self.error(400)
      return
 
    self.response.headers['Content-Type'] = 'text/plain'
    self.response.out.write(self.request.GET['hub.challenge'])

As you can see, this is very straightforward: We check that it's a subscription request ('hub.mode' is 'subscribe'), then we fetch the subscription and check that the tokens match. If all is well, we echo back the challenge string in the response, which is how hubbub verifies that we're okay with the subscription request.

Processing updates

Now that the subscription process is out of the way, we can handle the updates themselves. For this, we'll use the Universal Feed Parser library, though since the hub processes and sanitizes the feed, we could just as easily use a standard XML parser. Since new entries are sent as a POST request to the same URL as the subscription callback, we add a post() method to our CallbackHandler:

  def post(self):
    """Handles new content notifications."""
    feed = feedparser.parse(self.request.body)
    id = find_self_url(feed.feed.links)
    subscription = Subscription.get_by_key_name(id)
    subscriber_keys = Subscriber.all(keys_only=True).ancestor(subscription).fetch(1000)
    subscriber_addresses = [x.name() for x in subscriber_keys]
    if not subscription:
      logging.warn("Discarding update from unknown feed '%s'", id)
      return
    for entry in feed.entries:
      message = "%s (%s)" % (entry.title, entry.link)
      xmpp.send_message(subscriber_addresses, message)

def find_self_url(links):
  for link in links:
    if link.rel == 'self':
      return link.href
  return None

Here, we parse the request body with UFP, and extract the feed's 'self' URL using a convenience method. We then use that 'self' URL to retrieve the Subscription entity, and for each item in the feed, we notify all the subscribers of the update. Note that because we store the subscribers' XMPP addresses as key names, we don't need to fetch the Subscriber entities themselves - just their keys.

That's it - you now never have to worry about polling intervals, sanitization, or unavailable feeds again! The full source for the example app in this post is here, and you can try it out by messaging xmpphubbub@appspot.com. A few caveats before you go, though:

• There's no unsubscribe in the example - so be careful what you subscribe to!
• Real code would have more error checking, such as verifying that the response to the subscribe request was a 2xx, that the callback is made (sooner or later).
• Superfeedr doesn't support automatic subscription renewal - so if you want to know for certain that it hasn't forgotten about a subscription, and you haven't heard from it in a bit, you'd better re-subscribe.
• Superfeedr also doesn't support "authenticated content distribution", a mode that uses a shared secret to generate an HMAC signature for updates. In my mind, this is a major omisson - because it means that anyone who knows your callback URL can invent RSS updates at will! Edit: superfeedr does support authenticated content distribution.

Those caveats aside, I'm confident that if you compare this solution to implementing your own polling infrastructure, you'll find that it comes out significantly simpler. Plus, as soon as the publishers of your feeds start using Hubbub, you'll get instant updates!

Go is defined to be a safe language. Indices into array or string references must be in bounds; there is no way to reinterpret the bits of one type as another, no way to conjure a pointer out of thin air; and there is no way to release memory, so no chance of “dangling pointer” errors and the associated memory corruption and instability.

In the current Go implementations, though, there are two ways to break through these safety mechanisms. The first and more direct way is to use package unsafe, specifically unsafe.Pointer. The second, less direct way is to use a data race in a multithreaded program.

If you were going to build an environment that ran untrusted Go code, you'd probably want to change the available packages to restrict or delete certain routines, like os.RemoveAll, and you'd want to disallow access to package unsafe. Those kinds of restrictions are straightforward.

The data races that can be used to break through the usual memory safety of Go are less straightforward. This post describes the races and how to rearrange the data structures involved to avoid them. Until the Go implementations have been tuned more, we won't be able to measure whether there is a significant performance difference between the current representation and the race-free implementation.

Package Unsafe

Here's a simple packaging of a type that lets you edit arbitrary memory locations, built using the standard package unsafe:

import "unsafe"

type Mem struct {
 addr *uintptr // actually == &m.data!
 data *uintptr
}

// Peek reads and returns the word at address addr.
func (m *Mem) Peek(addr uintptr) uintptr {
 *m.addr = addr
 return *m.data
}

// Poke sets the word at address addr to val.
func (m *Mem) Poke(addr, val uintptr) {
 *m.addr = addr
 *m.data = val
}

func NewMem() *Mem {
 m := new(Mem)
 m.addr = (*uintptr)(unsafe.Pointer(&m.data))
 return m
}

(The Go type uintptr is an unsigned integer the size of a pointer, like uint32 or uint64 depending on the underlying machine architecture.)

The key line is near the bottom, the use of the special type unsafe.Pointer to convert a **uintptr into a *uintptr. Dereferencing that value gives us m.data (actually a *uintptr) interpreted as a uintptr. We can assign an arbitrary integer to *m.addr, that changes m.data, and then we can dereference the integer as *m.data. In other words, the Mem struct gives us a way to convert between integers and pointers, just like in C. There are no races here: this is just something you can do by importing unsafe. The Mem wrapper is a bit convoluted—normally you'd just use unsafe directly—but we're going to drop in a different implementation of NewMem that doesn't rely on unsafe.

A Race

The current Go representation of slices and interface values admits a data race: because they are multiword values, if one goroutine reads the value while another goroutine writes it, the reader might see half of the old value and half of the new value.

Let's provoke the race using interface values. In Go, an interface value is represented as two words, a type and a value of that type. After these declarations:

var x *uintptr

var i interface{} = &x
var j interface{} = (*uintptr)(nil)

The data structures for i and j look like:

Suppose we kick off a goroutine that alternately assigns i and j to a new interface value k:

var k interface{}

func hammer() {
 for {
  k = i
  k = j
 }
}

After each statement executes, k will look like either i or j, but during the assignment, there will be a moment when k is half i and half j, one of these:

The top case gives us a **uintptr nil, which we could obtain more easily via legitimate means, but the bottom case gives us the value &x (actually a **uintptr) interpreted as a *uintptr. If we can catch the interface when it looks like the case on the right, we'll have rederived the conversion we used above via unsafe. Based on that insight, we can rewrite NewMem without unsafe:

func NewMem() *Mem {
 fmt.Println("here we go!")

 m := new(Mem)

 var i, j, k interface{}
 i = &m.data
 j = (*uintptr)(nil)

 // Try over and over again until we win the race.
 done := false
 go func(){
  for !done {
   k = i
   k = j
  }
 }()
 for {
  // Is k a non-nil *uintptr?  If so, we got it.
  if p, ok := k.(*uintptr); ok && p != nil {
   m.addr = p
   done = true
   break
  }
 }
 return m
}

The same kind of race happens in all of Go's mutable multiword structures: slices, interfaces, and strings. In the case of slices, the trick is to get a pointer from one slice and a cap from a different one. In the case of strings, the trick is to get a pointer from one string and the len from a different one. (The string race isn't as interesting, because strings cannot be written to, so it would only let you read memory, not write it.)

The Fix

The race is fundamentally caused by being able to observe partial updates to Go's multiword values (slices, interfaces, and strings): the updates are not atomic.

The fix is to make the updates atomic. In Go, the easiest way to do that is to make the representation a single pointer that points at an immutable structure. When the value needs to be updated, you allocate a new structure, fill it in completely, and only then change the pointer to point at it. This makes the assignment atomic: another goroutine reading the pointer at the same time sees either the new data or the old data, but not a mix, assuming the compiler is careful to read the pointer just once and then access both fields using the same pointer value.

(The red border indicates immutable data.)

For slices and strings, it makes sense to keep the multiword representation but put an immutable ”pointer and cap” stub structure between the slice and the underlying array. This keeps the same basic efficiency properties of slices at the cost of a few extra instructions on each indexing operation.

The idea here is to keep a structure with a mutable offset and length to support efficient slicing but replace the pointer with an immutable base+length pair. Any access to the underlying data must check the final offset against the immutable cap. Copying slice values is still not an atomic operation, but an invalid len will not keep an out-of-bounds index from being caught.

This representation requires a couple more assembly instructions, because each index must be checked against two bounds, first the relative len and then the absolute cap:

LEAL x, SI
MOVL i, CX
CMPL CX, 4(SI)
JGE panic




MOVL 0(SI), DI
MOVL (4*CX)(DI), AX

LEAL x, BX
MOVL i, CX
CMPL CX, 4(BX)
JGE panic
ADDL 8(BX), CX
MOVL 0(BX), SI
CMPL CX, 4(SI)
JGE panic
MOVL 0(SI), DI
MOVL (4*CX)(DI), AX

 
 
// i >= len?
 
 
// i+off >= cap?
 
// &x[0] -> SI
// x[i] (or x[i+off]) -> DI
 

With suitable analysis, an optimizing compiler could cache 0(BX), 4(BX), 8(BX), and 4(SI), so in a loop, it is possible that the new representation would run at the same speed as the original.

An ambitious implementation might continue to use the current data structures for slices, interfaces, and strings stored on the stack, because data on the stack can only be accessed by the goroutine running on that stack. (Local variables whose addresses might escape to other goroutines are already allocated on the heap automatically, to avoid dangling pointer bugs after a function returns.)

Garbage Collection

This fix is feasible only because Go is a garbage-collected language: we can treat the red stub structures as immutable and trust that the garbage collector will recycle the memory only when nothing points to them anymore. It's much harder to build a safe language without a garbage collector to fall back on.

Security Implications

It is important to note that these races do not make the current implementations any less secure than they already are. The races allow clever programmers to subvert Go's memory safety, but a less clever programmer can still use the aptly-named package unsafe.

These races only matter if you are trying to build a Go service that can safely run arbitrary code supplied by untrusted programmers (and to the best of my knowledge, there are no such services yet). In that situation, you'd already need to change the implementations to disable access to the unsafe package and remove or restrict functions like os.Remove or net.Dial. Changing the data representations to be race free is just one more change you'd have to make. Now you know, not just that a change is needed but also what the change is.

The races exist because the data representations were chosen for performance: the race-free versions introduce an extra pointer, which carries with it the cost of extra indirection and extra allocation. Once the Go implementations are more mature, we'll be able to evaluate the precise performance impact of using the race-free data structures and whether to use them always or only in situations running untrusted code.

I better understand now how the pkg/syscall/z*.go files are generated. That’s the good news, part 1.

The good news part 2 is that with a working NetBSD/amd64 host, I have filled in placeholders similar to the 386 files in the pkg/runtime/amd64 directory.

The not so good news is back in pkg/syscall, where I’ve stripped syscalls_netbsd.go back to basics and am filling it based on analysis of NetBSD’s syscalls.master file. Just copying from FreeBSD or Darwin wasn’t going to cut it.

The updated patches have been uploaded in case anyone’s really curious (and it gets me an offsite backup) but they’re still some way off being useful.

–giles

Short version: Arrghhh!

Long version:

For historical reasons (and some commercial software) my "own" machines run OS X. (Up until a week ago I had a ten year old x86 machine as well, but I’d used up all my spare parts, and wanted the cupboard space, so it had to go.)

Virtualisation (or “Virtualization”, depending on the version of English you write), you say. Didn’t I use to be an expert on that? (By most definitions, yup. But not on x86/x86_64.)

I have been using Parallels 4.x, and found it usable. I could (with arm twisting) get it to run NetBSD-4.0/i386 (32 bit, not 64 bit) and there were limitations with its networking support on OS/X.

Parallels keep encouraging me to buy their (now not-so-new) 5.x, and offer a trial version. So I tried it. (Emphasis on the past tense.)

• it won’t run NetBSD-5.0/amd64 any way I can figure out (a main target for a go port)
• it will run NetBSD-5.0/i386, and is fast (but I’m not so convinced about the stability)
• it runs Linux (surprise ☺)
• it won’t run FreeBSD-8.0/amd64, which I want for comparison purposes.
• its ACPI is … peculiar (And yeah, I know ACPI is overly complex and stupid.  I even know what the acronym stands for.  But we have to live with it these days, "the industry" tells us)

And they want money for this. Maybe I’d prefer to give my money to VMware.

But before I do anything rash, I try VirtulBox again. It’s updated a few versions since I used it last; it’s sorta-kinda-partly-at-least open source. Last time I ran it it had problems with NetBSD, ran slow, and caused my laptop to run hot.

This time, installs NetBSD-5.0 (i386 and amd64), with ACPI (gee, revolutionary in 2010, dontchathink?) and they’ve moved to include bridged networking on OS/X, which means I don’t have to run it on my laptop.

Looks like a winner. Except that it won’t run FreeBSD/amd64 any way I can figure out. (I am sure I saw it installing and losing access to its “disks”, but all subsequent attempts to boot it make it look like a 32 bit machine trying to boot a 64 bit kernel). It does run FreeBSD-8.0/i386, at least. And 32 and 64 bit Linux, of course.

Maybe I want VMware after all. Something that "just works" would be nice. Truly nice. Especially if it keeps working when I stress it, which isn’t necessarily going to be the case with any of them. (Or OS X, of course. Don’t mention the transitory network problem that I can’t pin down to hardware, software, or even a single machine yet.)

Rant for the day is now over. Progress might resume shortly.

In a previous Damn Cool Algorithms post, I discussed log structured storage, and how it applies to databases. For a long time, I've wanted to implement a database based on log structured storage, and a few other nice mechanics from other database systems:

• Tables are key:value mappings, with duplicate keys allowed (Bigtable, BDB)
• Map-based views, also known as materialized views, for indexing (couchdb).
• Reducer support for views (couchdb).

Since my previous posts about go have been generally well received, and because I want to explore the language a bit more, I'll be implementing all this in Go. The approach I'd like to take is one of gradually building up abstractions. We'll tackle each of the components in its own post:

1. An interface for writing records to an append-only file or set of files.
2. A B-Tree implementation, built on the record interface.
3. Map-based / materialized views, based on the B-Tree implementation.
4. Reducers for views.

Unlike previous series, this one is likely to be fairly fragmented. There's a fair chunk of functionality to be implemented here, so I won't be able to get it out at my usual three posts a week schedule. In the meantime, the usual posts on App Engine and other topics will continue.

In the first post in the series, we'll implement an interface for writing records to an append-only file (or set of files), and reading records back, given their address. This may not sound like the most thrilling component, but it's necessary in order to implement the rest of the system, and we'll learn a lot about Go's IO interface by doing it.

This is the current patch list, in the order I apply them. (Curently I don’t think the order matters, but in case it does, here’s what I use)):

noparallel

This one’s trivial, and won’t be needed in the final port. It merely turns off the “-j4” option in the build, which makes reading the build output easier. (Sure, it might slow down the build too, but I’m working on a virtual machine anyway, so speed’s not of the essence.)

netbsd

Minor bits and pieces to include NetBSD as a valid build target. Nothing interesting here, move along.

libmach

This will need some work, and honestly I don’t know what it requires yet. For now, I have just copied the FreeBSD port which has left a whole lot of functions stubbed out. I presume those functions do something useful, but until I know what they’re used for I don’t know what to implement. As for now they’re not stopping me working on the rest of the build, the placeholders get to stay.

runtime

This patch is for all the stuff under $GOROOT/src/pkg/runtime/. As it involves low level kernel access and provides facilities like semaphores and thread support, it’s important. It is also an area in which NetBSD is almost completely different from OS X (a.k.a. Darwin), Linux, and FreeBSD. Plus to make things even more complicated, the existing ports have all used low level OS specific features in preference to higher level standardised features such as the pthreads library supplies. Doubtless there is a reason (or reasons!) for this, but all I have so far is speculation.

Work here isn’t progressing very fast: I want to think about it some more, and have found simpler and more obvious work to go on with in the next patch.

syscall

This patch is for all the code under $GOROOT/src/pkg/syscall/. It includes things like system call numbers, errno values, and translations between C and Go types. Conceptually it’s not too difficult; in practice it requires creating some material by hand, and writing scripts to create other source files. I’d hoped this would be almost idenitcal to the FreeBSD port, but it turns out there are some divergences between FreeBSD so it’s not as simple as cut & paste.

This patch isn’t done yet, but it’s not far off, and then I think I’ll return to the runtime changes.

In the modern industrial food system, a cow is a chemical factory which converts corn into beef or milk. This is inefficient and unsafe in several different ways. Cows can not be maintained in sterile environments, so E. coli and other bacteria from their feces can contaminate the meat. Cows evolved to eat grass, so feeding them corn, while cheaper and more efficient, significantly increases bacteria count. Moving cows from feedlot to slaughter house, and moving beef from slaughter house to market, is inefficient.

Now that we have industrialized the food chain, there is increasing study of synthetic life. There is even a Registry of Biological Parts intended to make it easier to design your own life forms. These mostly work as modifications of existing life forms. There are, for example, people working on making bacteria which can efficiently produce diesel fuel; it apparently works in small quantities but there are still scaling issues.

Different people are working on what seems to be called in vitro meat: flesh which has never been part of an actual animal. This is generally done by culturing muscle cells.

In view of these efforts, it seems ridiculous to use something as complex and inefficient as a cow to produce beef. How long will it be until we have fully synthetic meat products? (This will of course raise a host of interesting health issues, but I think it’s safe to predict that none of them will be addressed until and unless the product is already popular.)

For people concerned about the increasing industrialization of food, synthetic meat will only make matters worse. However, as a vegetarian, I think the only valid choices are synthetic meat or no meat. So I would be happy to see increasing work in these fields, and I’m confident that they will become not only less cruel, but cheaper, than dealing with real cows.

This blog is intended to record progress on porting Google’s Go language to NetBSD. There is an open item #611 in Google’s issue tracker for this.

Initial efforts are going to concentrate on the 386 (a.k.a. i386) and amd64 ports; in theory it should be possible to port to NetBSD arm platfoms as well.

As yet there’s no mailing list: should there be desire for one, I’ll create one. For now, feel free to add comments to the blog, which I’ll endeavour to keep updated as I update the patches.

All assistance is welcome. Feel free to dig in. No questions are too foolish to ask!

There’s a page of general information here:

http://netherstone.org/golang/netbsd/

The in-progress diffs are maintained here:

http://netherstone.org/golang/netbsd/patches/

–giles

This is part of a series on writing a webapp framework for App Engine Python. For details, see the introductory post here.

Sessions are another component that's regularly required by webapps, but isn't really a core part of a framework. In this post, we'll discuss the session mechanisms available for App Engine and how they work, and settle on a recommendation for our own lightweight framework.

The basic mechanism behind a session library is straightforward: A random session ID is generated for the user, which is embedded in an HTTP cookie and sent to the user. Meanwhile, a record is created on the server with the same ID, containing any data the webapp wants to store about this user. When the user makes a subsequent request, the session library decodes the session ID from the cookie header, and loads the corresponding session record from permanent storage.

There are three major advantages of handling sessions this way, rather than naively storing session data directly in the cookie:

• We can store data that the client shouldn't be able to modify, such as the user's access flags.
• We can store data the client shouldn't even be able to read, or shouldn't be sent in the clear, such as their credentials.
• We can store more data than can be practically carried in an HTTP cookie.

There are, of course, situations in which some of these constraints don't apply. Sometimes none of them apply, such as in the case of preference cookies; sometimes size is not an issue, but we want integrity and/or confidentiality. In these cases, many session libraries provide "cookie only" sessions, which store the data entirely in the cookie, while adding signing and/or encryption to prevent tampering or reading of the cookie data by the user.

Using cookie-only sessions has one major advantage: You remove the necessity to retrieve the user's data from storage on each request. This needs to be balanced with the limited storage on the one hand, and the need to embed a secret key in your code that can be used to sign and verify the cookies.

For non-cookie sessions, the session data needs to be stored somewhere. Many systems use the local filesystem, but this isn't practical in the case of distributed systems like App engine. On App Engine, that leaves us with two main options: Memcache, and the datastore.

Memcache initially seems like quite an attractive option, as it's substantially faster to query and update than the datastore. This comes with a major caveat, though: Since memcache makes no guarantees about how long values will persist, there's absolutely no guarantee that your session will still be around when the user comes back for it.

Losing the occasional user session doesn't seem like to much of a problem at first, but there are several factors that need consideration. If you're using sessions to implement a shopping site, losing a user's session is the absolute last thing you want to do: A user who suddenly loses the contents of their shopping cart is quite likely to simply leave, costing you one or even multiple sales. Even if sales aren't involved, if users regularly get logged out of their accounts, they may grow frustrated with your site and leave. Ad-hoc testing isn't sufficient to establish how much of an issue this is, either: Problems may not come up when you test the system with a reasonable load, but may instead occur when the system's under heavy load.

The other option, of course, is the Datastore. At the cost of a little extra latency, we gain near perfect reliability. With proper design, fetching the session should only require a single datastore get operation, too - no queries, which are much more expensive.

Hybrid approaches are of course also possible: We can store to both memcache and the datastore, and fetch from one, then the other, thus minimizing latency whenever memcache is available.

Solutions

Enough theorizing - let's take a look at the ready-made sessions libraries for App Engine. The first one is Beaker.

Beaker is a standalone library for session handling, implemented as WSGI middleware. It also includes caching middleware. Beaker supports App Engine datastore sessions, though an open bug means that the library currently needs some modification to work on App Engine (Edit: Now fixed!).

Using Beaker is a matter of downloading and unpacking it into your app's root directory, then opening beaker/cache.py and deleting or commenting out lines 29 through 51 - the section dealing with pkg_resources, which is unavailable on App Engine - as well as line 10, which imports pkg_resources. To use Beaker, we simply insert it as middleware, like this:

router = WSGIRouter()

#...

beaker_opts = {
  'session.type': 'ext:google',
}
application = beaker.SessionMiddleware(router)

The session.type configuration option tells beaker what session storage to use - in this case, the Google datastore. Beaker also supports memcached - although not App Engine's implementation of it - and cookie-only sessions, which can be enabled by setting session.type to "cookie", and session.secret to a secret key for hashing and encrypting the cookie.

Another sessions implementation is provided by gaeutilities. gaeutilities supports datastore, memcache, and pure-cookie sessions. Using gaeutilities' sessions is even simpler:

session = appengine_utilities.sessions.Session()
session["keyname"] = "value" # sets keyname to value
print session["keyname"] # will print value

As you can see, no middleware is required in this case - gaeutilities takes advantage of App Engine's use of the system environment to retrieve session data. gaeutilities also includes features such as token rotation to make session hijacking more difficult, while Beaker uses only a single session ID.

One quick caveat: Unlike beaker, gaeutilities does not encrypt or sign cookie-only sessions, so they should only be used for data where user tampering is not a concern.

Conclusion

We've looked at two good sessions libraries for App Engine. Either one would be a good choice for our framework. Given the current state, however, gaeutilities seems like the better choice: It doesn't require modifications to work, it's built specifically for App Engine, and if you need a lightweight library, you can easily take just the session handling code and not include the rest of the library.

Services that consume or produce Twitter updates are popular apps these days, and there are more than a few on App Engine, too. Twitter provide an extensive API, which provides most of the features you might want to access.

Broadly, Twitter's API is divided into two distinct parts: The streaming API, and everything else. The streaming API is their recommended way to consume large volumes of updates in real-time; unfortunately, for a couple of reasons, using it on App Engine is not practical at the moment. The rest of their API, however, is well suited to use via App Engine, and covers things such as retrieving users' timelines, mentions, retweets, etc, sending new status updates (and deleting them, and retweeting them), and getting user information.

Authentication

Most of Twitter's API calls require authentication. Currently, Twitter support two different authentication methods: Basic, and OAuth. Basic authentication, as the name suggests uses HTTP Basic authentication, which requires prompting the user for their username and password. We won't be using this, since it's deprecated, and asking users for their credentials is a bad idea. The OAuth API makes it possible to call Twitter APIs on behalf of a user without knowing their password, and that's what we'll focus on today.

The key features of OAuth is that every consumer - that's you - needs a 'consumer key' and a 'consumer secret'. As the names imply, the first one is a key that identifies you, while the second is a secret value, known only to you and Twitter. Together, these allow you to prove to Twitter that you are who you say you are. In addition, for each user you authenticate, you'll need to store a user token and a user secret. These operate in the same way as the client token and secret, and allow you to prove to Twitter that you're making legitimate requests on behalf of that client.

In order to get permission to act on behalf of a user, you need to go through an authentication process. This consists of sending the user to a URL on twitter.com, where Twitter asks them if they want to authorize you to use their account. If the user agrees, Twitter redirects the user back to your site, embedding in the URL the details required. After that, you have all the necessary keys and secrets to use the API as that user (until they revoke your access!)

OAuth is a relatively straightforward protocol, but it'd be nice if we didn't have to implement it ourselves. Fortunately, Mike Knapp has already done all the hard work for us, in the form of the AppEngine-OAuth library (that link goes to my own fork of it, which has a few improvements that haven't yet made it into the mainline). This library takes care of all the nitty-gritty of OAuth authentication and making OAuth requests, making things Just Work.

Using AppEngine-OAuth

The first thing you should do is go to Twitter and create an OAuth consumer. Take the key and secret you're given, and store it somewhere - as a configuration variable in your code, or in the datastore, wherever suits. Next, download the library from the link above - you only need the file 'oauth.py', and place it in your app's root.

There are three major components you need to integrate: Sending the user to Twitter to be authenticated, handling the redirect back to complete authentication, and making API calls using the credentials. We'll tackle these in order.

Starting the Authentication process

Initiating authentication is easy. First, construct an oauth.TwitterClient:

consumer_key = "LKlkj83kaio2fjiudjd9...etc"
consumer_secret = "58kdujslkfojkjsjsdk...etc"
callback_url = "http://www.myurl.com/callback/twitter"
 
  client = oauth.TwitterClient(consumer_key, consumer_secret, callback_url)

Here, callback_url should be the complete URL of the callback handler in your app. Next, you can generate a URL and redirect the user to it as follows:

self.redirect(client.get_authorization_url())

Completing Authentication

When the user is done at Twitter, they will be redirected back to the callback URL you provided. Handling this requires constructing another instance of the TwitterClient, as above, and calling get_user_info on it:

class CallbackHandler(webapp.RequestHandler):
  def get(self):
    client = oauth.TwitterClient(consumer_key, consumer_secret, callback_url)
    auth_token = self.request.get("oauth_token")
    auth_verifier = self.request.get("oauth_verifier")
    user_info = client.get_user_info(auth_token, auth_verifier=auth_verifier)

The 'user_info' variable here is a dict containing the relevant information about the authenticated user. Of particular interest is the "token" and "secret" keys, which we need to store to authenticate future requests, and the "username" key, which identifies the user. Services like Twitter also return additional keys - for instance, "name", which is the user's display name, and "picture", a URL to their avatar. If you want to see a real working example of a callback handler, here's Tweet Engine's one.

Making Authenticated Requests

Now that you've authenticated the user and stored their credentials, you can make authenticated requests as them. Again, the OAuth library makes this easy. We once again construct a TwitterClient instance, and call .make_request on it, passing in the URL, the user's OAuth token and secret, as well as any additional parameters:

client = oauth.TwitterClient(consumer_key, consumer_secret, callback_url)

additional_params = {
  status: "Testing Twitter OAuth",
}

result = client.make_request(
    "http://twitter.com/statuses/update.json",
    token=client_token,
    secret=client_secret,
    additional_params=additional_params,
    method=urlfetch.POST)

The 'result' variable, here, is a urlfetch Response object, which you can treat as you would the result of any other urlfetch call. Again, for a real example, you can check out how Tweet Engine does it, though in this case it's slightly complicated by some extra layers of abstraction we haven't covered here.

Rate Limiting

One concern a lot of users have about using Twitter via App Engine is rate limiting. Twitter has two different rate limiting systems: per-IP, and per-app/per-user. This comes up a lot with users of the search API via App Engine, because all App Engine apps make external requests via the same pool of IPs. Authenticated requests, such as those we're making, are all rate limited per app and/or user, so we don't have to be worried about the per IP ratelimits.

That's all there is to using Twitter's OAuth API on App Engine. Have a use-case in mind? Let us know in the comments!

1. It's small. You can learn everything there is to know about Lua pretty quickly.
2. It moves slowly. There isn't a lot of hot new Lua tricks to blog about.
3. The existing documentation is fantastic.
4. Because it's embedded in other apps, there isn't a lot of "here's something useful" stuff that applies to all Lua users.

No one talks about screwdrivers either.

I have trouble finding a use for Lua, even though I like it better as a language than most.

The problem is that it isn't a good "starting place" for an app. Instead you write something in C/C++ and say "oh, I wish I had a dynamic language for this part" and then you add Lua on top. And this is part of why Lua is such a compelling language now - by being extension-focused it's been able to iterate the entire language many times over and make basic semantic changes without worrying about backwards-compatibility.

But if I start writing an app and want something Lua-like....it ends up being easier to start in Python. There are some good projects out there to address this but it's a question of maturity - as of right now Lua still doesn't really satisfy as a "batteries-included" platform.

"I think it's in part because Lua first became big in the game industry, which is not known for its openness and is still dominated by the large players. Many game companies guard their IP religiously, and often the developers are under NDAs. You won't see them organize a friendly neighbourhood somethingCamp to share and learn.

"I didn't understand the article. Lots of people use and talk about Lua. It serves a specific niche in application development. The Lua team is happy with the language. What is the issue?"

<script charset="utf-8" expr:src=""http://feeds.feedburner.com/~s/goplexian?i=" + data:post.url" type="text/javascript"></script>

Last week, I blogged about cursors, a new feature in version 1.3.1 of the App Engine SDK. Today, I'm going to demonstrate a practical use for them: Bulk datastore updates.

In both the Remote API and deferred articles, I used a (perhaps poorly named) 'mapper' class as an example of ways to use these libraries. In neither case was the class intended to be anything other than a sample use case for the library, but nevertheless, people have used the examples in production. The introduction of cursors provides a prime opportunity to introduce a more robust, yet simpler, version of the bulk updater concept.

First, let's define a few requirements for our bulk updater:

• Support for any query for which a cursor can be obtained
• Handles failure of individual updates gracefully
• Can fail the whole update process if enough errors are encountered
• Handles timeout errors, service unavailability, etc, transparently
• Can report completion to admins

As in the Remote API and Deferred articles, we'll implement the updater as an abstract class, which individual updater implementations should subclass. Here's the basic interface:

import logging
import time
from google.appengine.api import mail
from google.appengine.ext import db
from google.appengine.ext.deferred import defer
from google.appengine.runtime import apiproxy_errors


class BulkUpdater(object):
  """A bulk updater for datastore entities.
  
  Subclasses should implement, at a minimum, get_query and handle_entity.
  """

  # Number of entities to put() at once.
  PUT_BATCH_SIZE = 20
  
  # Number of entities to delete() at once.
  DELETE_BATCH_SIZE = 20
  
  # Maximum time to spend processing before enqueueing the next task in seconds.
  MAX_EXECUTION_TIME = 20.0
  
  # Maximum number of failures to tolerate before aborting. -1 indicates
  # no limit, in which case the list of failed keys will not be retained.
  MAX_FAILURES = 0
  
  def __init__(self):
    self.__to_put = []
    self.__to_delete = []
    self.__failed_keys = []
    self.num_processed = 0
    self.num_tasks = 0
    self.num_put = 0
    self.num_deleted = 0
  
  def get_query(self):
    """Returns the query to iterate over.

    Returns:
      A db.Query or db.GqlQuery object. The returned query must support cursors.
    """
    raise NotImplementedError()

  def handle_entity(self, entity):
    """Performs processing on a single entity.
    
    Args:
      entity: A db.Model instance to update.
    """
    raise NotImplementedError()

  def finish(self, success, failed_keys):
    """Finish processing. Called after all entities have been updated.
    
    Args:
      success: boolean: Indicates if the process completed successfully, or was
        aborted due to too many errors.
      failed_keys: list: A list of db.Key objects that could not be updated.
    """
    pass

The first thing we do is define some constants that will affect the operation of our updater - the batch sizes for put and delete operations, and the maximum time to execute before enqueueing the next task. This last one is necessary because tests have shown that the approach used in the deferred article, of catching the first deadline error and enqueueing the next task then, is not sufficiently reliable. We also define a maximum number of update failures to tolerate before aborting the update process.

We need some way for updater instances to propagate their changes back to the datastore. As with previous mappers, we want to batch these operations for efficiency. This time, let's define helper methods that the handle_entity() method can call:

  def put(self, entities):
    """Stores updated entities to the datastore.
    
    Updates are batched for efficiency.
    
    Args:
      entities: An entity, or list of entities, to store.
    """
    if isinstance(entities, db.Model):
      entities = [entities]
    self.__to_put.extend(entities)
    
    while len(self.__to_put) > self.PUT_BATCH_SIZE:
      db.put(self.__to_put[-self.PUT_BATCH_SIZE:])
      del self.__to_put[-self.PUT_BATCH_SIZE:]
      self.num_put += self.PUT_BATCH_SIZE

  def delete(self, entities):
    """Deletes entities from the datastore.
    
    Deletes are batched for efficiency.
    
    Args:
      entities: An entity, key, or list of entities or keys, to delete.
    """
    if isinstance(entities, (db.Key, db.Model, basestring)):
      entities = [entities]
    self.__to_delete.extend(entities)
    
    while len(self.__to_delete) > self.DELETE_BATCH_SIZE:
      db.delete(self.__to_delete[-self.DELETE_BATCH_SIZE:])
      del self.__to_delete[-self.DELETE_BATCH_SIZE:]
      self.num_deleted += self.DELETE_BATCH_SIZE

These methods are fairly straightforward: We add passed in entities or keys to our internal lists for batching purposes, and if there are enough entries, we execute the batch update process for each batch. We use a while loop rather than an if, because a single call to put() or delete() could add more than one batch's worth of entries to put or delete.

Now we can implement the code that does the actual work. We'll start by defining a method that executes a single batch of work:

  def __process_entities(self, q):
    """Processes a batch of entities.
    
    Args:
      q: A query to iterate over doing processing.
    Returns:
      True if the update process has finished, False otherwise.
    """
    end_time = time.time() + self.MAX_EXECUTION_TIME
    for entity in q:
      try:
        self.handle_entity(entity)
      except (db.Timeout, apiproxy_errors.CapabilityDisabledError,
              apiproxy_errors.DeadlineExceededError):
        # Give up for now - reschedule for later.
        return False
      except Exception, e:
        # User exception - log and (perhaps) continue.
        logging.exception("Exception occurred while processing entity %r",
                          entity.key())
        if self.MAX_FAILURES >= 0:
          self.__failed_keys.append(entity.key())
          if len(self.__failed_keys) > self.MAX_FAILURES:
            # Update completed (failure)
            return True
      
      self.num_processed += 1
      
      if time.time() > end_time:
        return False
    
    # The loop finished - we're done!
    return True

The __process_entities method takes a query, already positioned at the start of a batch, and iterates over it. We use iteration rather than the more efficient fetch(), because we don't know how many entities we will be able to process in the allotted time.

Most of this method is taken up with exception handling. Several exceptions are treated specially - db.Timeout, apiproxy_errors.CapabilityDisabledError, and apiproxy_errors.DeadlineExceededError, by immediately terminating the batch. We give up immediately on Timeout errors due to the new changes in 1.3.1 which mean that a Timeout returned to our code almost certainly indicates a need to retry at a later stage. Other errors are assumed to be user errors, and are caught and logged. If there's a finite threshold for the maximum number of user errors, the key of the failing entity is recorded, and we abort if we've reached the limit. Finally, after processing each entity, we check the current system time, to determine if we have reached our self-imposed deadline. The method returns True if processing is done - due to success or failure - and False otherwise.

Now we can define run(), the method that handles the whole process:

  def run(self, _start_cursor=None):
    """Begins or continues a batch update process."""
    q = self.get_query()
    if _start_cursor:
      q.with_cursor(_start_cursor)
    
    finished = self.__process_entities(q)
    
    # Store or delete any remaining entities
    if self.__to_put:
      db.put(self.__to_put)
    if self.__to_delete:
      db.delete(self.__to_delete)
    self.num_put += len(self.__to_put)
    self.__to_put = []
    self.num_deleted += len(self.__to_delete)
    self.__to_delete = []
    
    self.num_tasks += 1
    
    if finished:
      logging.info(
          "Processed %d entities in %d tasks, putting %d and deleting %d",
          self.num_processed, self.num_tasks, self.num_put, self.num_deleted)
      self.finish(len(self.__failed_keys) <= self.MAX_FAILURES
                  and self.MAX_FAILURES >= 0,
                  self.__failed_keys)
    else:
      defer(self.run, q.cursor())

run()'s main job is to create a query with which to call __process_entities(), and to clean up after it by storing and deleting any remaining entities. Finally, it checks if the process has finished; if it has, it calls finish(); otherwise, it enqueues the next task, picking up where this one left off.

Back in the original requirements, we included the requirement that it be possible to report completion to admins. Let's do that with a mixin:

class ReportingMixin(object):
  def __init__(self, email_sender=None):
    """Constructor.
    
    Args:
      email_sender: If set, send a completion email to admins, from the provided
        email address.
    """
    super(ReportingMixin, self).__init__()
    self.email_sender = email_sender

  def finish(self, success, failed_keys):
    super(ReportingMixin, self).finish(success, failed_keys)
    if not self.email_sender:
      return

    if success:
      message = "Bulk update job %s completed successfully!\n\n" % self.__class__
      subject = "Bulk update completed"
    else:
      message = "Bulk update job %s failed.\n\n" % self.__class__
      subject = "Bulk update FAILED"
    
    message += ("Processed %d entities in %d tasks, putting %d and deleting %d\n\n"
                % (self.num_processed, self.num_tasks, self.num_put,
                   self.num_deleted))
    
    if failed_keys:
      message += "Processing failed for the following keys:\n"
      for key in failed_keys:
        message += "%r\n" % key
    
    mail.send_mail_to_admins(self.email_sender, subject, message)

This mixin simply extends the finish() method, and if a sender address is provided, sends an email from it to all the app's admins, giving a brief report of the process's completion or failure.

Finally, we can define a couple of simple classes for commonly used types of update operation:

class BulkPut(ReportingMixin, BulkUpdater):
  def __init__(self, query, email_sender=None):
    super(BulkPut, self).__init__(email_sender)
    self.query = query

  def get_query(self):
    return self.query

  def handle_entity(self, entity):
    self.put(entity)


class BulkDelete(ReportingMixin, BulkUpdater):
  def __init__(self, query, email_sender=None):
    super(BulkDelete, self).__init__(email_sender)
    self.query = query

  def get_query(self):
    return self.query

  def handle_entity(self, entity):
    self.delete(entity)

These two classes are almost identical, except for the operation carried out on each entity. In each case, the constructor takes a Query object, which is stored as an instance attribute and returned by get_query; this works because Query objects are picklable, and run() is guaranteed not to modify the query except by calling .with_cursor() on it.

We can test our updater from the remote_api console, like so:

notdot-blog> updater = bulkupdate.BulkPut(models.BlogPost.all())
notdot-blog> updater.MAX_EXECUTION_TIME=1.0
notdot-blog> defer(updater.run)

Checking the admin console shows the deferred tasks being executed, and checking our email shows a message in our inbox titled "Bulk update completed".

As always, bear in mind the limitations of the deferred library when it comes to import path changes, etcetera.

The complete source of our new bulk updater can be found here.

Finally, a few suggestions for how you can use this module:

• Updating instances of a model whose definition has changed, for indexing purposes, using the BulkPut class we defined above.
• Bulk deleting an entity kind, or a subset of it, using the BulkDelete class we defined above.
• Calculating global statistics by storing them against the BulkUpdater instance across requests. Make sure these remain small - if the pickled size of the entity exceeds 10k, each deferred invocation will have to load it from the datastore and store it again at the end!
• Migrating models to new definitions or kind names.
• Performing more complex 'map' operations, such as inserting or updating one entity based on the contents of another.
• Doing periodic updates of stored counts, etc.

Got more ideas? Mention them in the comments! Are you using this class for something novel? Let us know!

This is part of a series on writing a webapp framework for App Engine Python. For details, see the introductory post here.

The first part of a framework you encounter when using one is, more often than not, the routing code. With that in mind, it's what we'll be tackling first. There are several approaches to handling request routing, and we'll go on a quick tour of the libraries and approaches before we decide on one and implement it.

The built-in App Engine webapp framework takes an extremely straightforward approach: The incoming request's URL is compared to a list of regular expressions in order, and the first one that matches has the corresponding handler executed. As an enhancement, any captured groups in the regular expression are passed to the request handler as additional arguments. You can see the code that does all this here - it's extremely straightforward and easy to follow.

The webapp module does one thing that I'm not a huge fan of: It ties the request routing in with handling the requests. The same function that finds the appropriate handler for a request also takes care of parsing the request and calling the appropriate methods on the RequestHandler subclass. As a result, RequestHandler classes are not WSGI applications, and you can't mix non-webapp apps in. With that caveat in mind, let's continue to look at some of the alternate approaches.

Django's approach to URL handling is documented here. It bears a remarkable resemblance to the webapp module's approach, and for good reason: A lot of App Engine's python library was inspired by Django. One difference worth noting about the way Django handles things is that the second parameter in each tuple is the string name of the module that will handle requests for that URL regex, rather than the class itself. This seems a little awkward, but provides a real benefit: It means we don't need to load every handler module in order to service a request to just one of them. We'll discuss optimisations like this in more detail in a later post.

In the realm of independent libraries, there are several prominent options. The routes library is a port of the Rails routing system, and uses a rather sophisticated system based on expressions that symbolically represent the sort of URLs you want to match. For example, the string "/error/{action}/{id}" matches any URL that has 3 slash-separated components starting with "/error", and breaks out the last two into separate variables, 'action' and 'id'.

Somewhat counterintuitively, the Routes library doesn't actually route requests to individual WSGI applications or handlers; instead it simply takes care of parsing URL patterns into dictionaries mapping set keys to values found in the URL. In that respect it's very sophisticated, allowing a great deal of flexibility in how you specify your URL parsing, including default values, regular expressions, and other features. It's then the job of another (simpler) piece of WSGI middleware to take the information routes produces and use it to dispatch to the appropriate handler.

Besides being typically easier to understand and more flexible than a naive regular-expression based system, Routes' approach has another advantage: It's possible to perform the reverse transformation, and generate a URL given a dict like that generated by routes. As long as your apps use this to generate URLs when they're needed, this means that you or your users can completely restructure the URL structure of your app without needing to make any changes to the rest of your code.

The werkzeug framework provides a similar mechanism, enhancing it with 'converter' functions that specify the accepted characters and converting the returned value. Unlike Routes, however, it doesn't provide the capability to use the mapping in the reverse direction, generating URLs. Edit: Werkzeug also supports doing reverse mappings, like Routes.

Finally, Webob's "do it yourself framework" demonstrates a method that is very similar to that defined by Routes, but has the substantial advantage that it's easily converted from the semantic form users enter into an ordinary regular expression. It is on this that we will base our own routing middleware.

First, let's take a look at the template_to_regex function from the webob framework, which we will use without modification:

 >>> import re
 >>> var_regex = re.compile(r'''
 ...     \{          # The exact character "{"
 ...     (\w+)       # The variable name (restricted to a-z, 0-9, _)
 ...     (?::([^}]+))? # The optional :regex part
 ...     \}          # The exact character "}"
 ...     ''', re.VERBOSE)
 >>> def template_to_regex(template):
 ...     regex = ''
 ...     last_pos = 0
 ...     for match in var_regex.finditer(template):
 ...         regex += re.escape(template[last_pos:match.start()])
 ...         var_name = match.group(1)
 ...         expr = match.group(2) or '[^/]+'
 ...         expr = '(?P<%s>%s)' % (var_name, expr)
 ...         regex += expr
 ...         last_pos = match.end()
 ...     regex += re.escape(template[last_pos:])
 ...     regex = '^%s$' % regex
 ...     return regex

The workings of this function are described in detail on the webob site, but we'll go over the basics here. Our ultimate goal is to take strings that contain expressions of the form "{variable:regex}" and convert them into fully formed regular expressions. For example, a template such as "/{year:\d\d\d\d}/{month:\d\d}/{slug}" should be converted into the regular expression "^/(?P<year>\d\d\d\d)/(?P<month>\d\d)/(?P<slug>[^/]+)$". The parentheses in the regular expression are capturing subexpressions, meaning their contents will be available to us if the expression matches, while the "?P<foo>" part signifies a label for that subexpression, allowing us to access it by name rather than by position.

The main part of the function is a loop over every template expression found in the input string. The output regular expression is built up in the variable named 'regex'. For each match, we first append the text between the previous match (if any) and the current one (after escaping it, so special characters aren't mistakenly interpreted as regular expression modifiers). Then, the variable name and regular expression are extracted from the template expression. If no regular expression was specified, the default expression "[^/]+", meaning one or more non-forward-slash characters, is used. The regular expression for this match is then appended to the regex-so-far, as a named sub-group as we described above. Finally, any remaining text is appended to the string, and the whole regular expression is wrapped in '^' and '$', the regular expression symbols that indicate the start and end of a string.

And yes, if you think using a regular expression to parse bits of regular expression into a new regular expression is all a bit meta, you're not alone.

Now that we've sorted out what format we'll use for specifying routes, we're ready to write the routing code itself. We'll be using a system similar to Routes, whereby you can specify additional default named arguments with your route and handler, but our handlers will be regular WSGI applications, called directly, rather than using the extra layer of indirection provided by Routes. Also, although we have left the door open for being able to do the reverse transform of handlers back to URLs, we won't be doing so in our first iteration.

class WSGIRouter(object):
  def __init__(self):
    self.routes = []

  def connect(self, template, handler, **kwargs):
    """Connects URLs matching a template to a handler application.
    
    Args:
      template: A template string, consisting of literal text and template
        expressions of the form {label[: regex]}, where label is the mandatory
        name of the expression, and regex is an optional regular expression.
      handler: A WSGI application to execute when the template is matched.
      **kwargs: Additional keyword arguments to pass along with those parsed
        from the template.
    """
    route_re = re.compile(template_to_regex(template))
    self.routes.append((route_re, handler, kwargs))

As you can see, the basic code for our router is extremely simple. We define a method, connect(), which takes a template string, a handler, and optional keyword arguments. This method calls template_to_regex to generate a regular expression, then inserts that and the additional argument in the list of routes. The real work happens when our router object is called as a WSGI application:

  def __call__(self, environ, start_response):
    for regex, handler, kwargs in self.routes:
      match = regex.match(environ['PATH_INFO'])
      if match:
        environ['router.args'] = dict(kwargs)
        environ['router.args'].update(match.groupdict())
        return handler(environ, start_response)

The name of the method, __call__, distinguishes this as a special method to python. Normally it's not possible to call an object as you would a function, but if your class defines the __call__ method, this method is executed when someone calls your object. This allows objects of our WSGIRouter class to act as regular WSGI applications.

When our router is called, it iterates over each of the routes that were provided, and for each one attempts to match it against the PATH_INFO CGI variable. If it finds a match, it extends the WSGI environment by adding a variable called 'router.args'. This variable consists of any static arguments that were passed to the connect() method, in addition to the values of all the matched template parameters. The router then calls the selected WSGI app, returning its result to its own caller. It's up to whatever WSGI application is being called to extract the router.args variable from its environment if it needs it, and to act on it accordingly.

Let's define a simple webapp to test all this out:

def hello_app(environ, start_response):
  start_response(200, [("Content-Type", "text/plain")])
  return ["Hello, world."]


def echo_app(environ, start_response):
  start_response(200, [("Content-Type", "text/plain")])
  return [repr(environ['router.args'])]


router = WSGIRouter()
router.connect("/hello", hello_app)
router.connect("/echo/{foo}/{bar:[0-9]+}", echo_app, test="test")

def main():
  run_wsgi_app(router)

if __name__ == '__main__':
  main()

This app defines two handlers, mapped to two different URL patterns. If you go to '/hello', you should see "Hello, world.". If you go to a URL such as "/echo/bleh/123", you should see the complete template dict - in this example, it'll be "{'test': 'test', 'foo': 'bleh', 'bar': '123'}".

That's it for routing! In the next post we'll handle decoding and encoding requests and responses.

Welcome back! I trust you all had a good holiday period? Mine was spent back in sunny New Zealand, seeing friends and family, visiting favorite restaurants, enjoying the sunshine, and learning to paraglide.

I would have started blogging again last week, but my first week back was made both exciting and frantically busy preparing for, then attending the BT Young Scientist Exhibition, where I gave tutorials on App Engine at the Google booth. But now, back to your regularly scheduled blogging...

Sometimes it seems like everyone has written their own blogging system, and everyone has written their own framework for webapps. That's not all these two things have in common, though: They're both excellent learning projects. Since you've already done the first, why not do the second? This will be the first of a series of posts covering how to write your own Python webapp framework. The framework, while targeted at App Engine, isn't exclusive to it.

As with the blogging project, it helps to set some goals before we get started. Here's our goals for this project:

• Lightweight. With cold startup time being a significant concern for many, it's essential to avoid creating a large, monolithic framework which requires importing a lot of extraneous code before it can serve even basic requests. Likewise, we don't want users of our framework to have to add a great deal of overhead to their app.
• Loosely coupled. Like all good frameworks, swapping out components should be easy, and nobody should be forced to use the entire framework if they only want part of it.
• 'Best-of-breed' components. As we'll see, there are already many good open source libraries that take care of individual tasks like routing, rendering templates, and session handling. Our framework should reuse these wherever possible.
• Fast. This overlaps with the first two, but it's worth a bullet point of its own. There's a great deal of variability in the performance of some of the libraries available, and we should do our best to pick the fast ones.

One caveat, however. My main goal for this series is to introduce you to the inside workings of a web framework, and the things it interfaces with, such as WSGI and CGI. We're not writing something with the goal of being a serious competitor to all those other frameworks out there, so don't expect enterprise-level support or an active development beyond the series. If, like me, you love to hack around with this sort of thing, feel free to pick it up - fork it, use it, improve it! If, however, you're just looking for a ready-made framework to use with your next webapp, you're probably better off choosing one of the many existing frameworks with App Engine support.

Before we begin, we need to cover the basics of what a framework is, and how it works. If you're already familiar with things such as HTTP, CGI, and WSGI, feel free to skip over this section. Otherwise, read on!

HTTP

At the bottom of the stack is HTTP, which you should already be somewhat familiar with. HTTP is fundamentally a request-based protocol: A client makes a request, consisting of a URI path, a method, a set of headers, and an optional body, and the HTTP server sends back a response, likewise consisting of a set of headers and an optional body.

CGI

In order to be able to write an application that operates over HTTP, an interface of some sort is required, and that interface is CGI. CGI is a venerable standard by now, first standardized back in 1993, and it's a little archaic by today's standards. Although it (or systems based on it, like WSGI) is still used today, many of its design features are more than a little odd for today's webapps.

When a webserver receives a request that is to be handled by a CGI script, it transforms the request into a set of environment variables. The request method (Eg, GET, HEAD, POST, etc) is passed as the REQUEST_METHOD variable, while the URI path is split up into several components, which are passed separately: SCRIPT_NAME, the URI to the CGI script, PATH_INFO, the remainder of the URI path, and QUERY_STRING, the contents of the query string. The protocol being used is passed in via the 'HTTPS' variable, which is set to 'on' if HTTPS is in use, and 'off' otherwise. Other headers are transformed by making them all uppercase, and replacing hyphens with underscores - eg, 'Content-Type' becomes 'CONTENT_TYPE'. Since most webapps now don't actually use CGI scripts, the first variable, SCRIPT_NAME, is often left blank, or is set to the path to the application as a whole.

CGI was originally designed to formalize the handling of HTTP requests by standalone executables. The request would be transformed as we described above, then the script in question would be executed with those variables in its OS environment. The request body, if any, would be passed in on standard input. The CGI script is expected to process the request, and return the headers, followed by a newline and the response body, on standard out. This general pattern is preserved, with some modifications, on App Engine.

The main difference in App Engine's handling of CGI is a performance optimisation: instead of re-executing your Python executable for each request, a single Python runtime is used for multiple requests. Each request simply re-imports the main handler script for your app, which results in re-executing all the code in it, though modules loaded from it are not re-imported. As a further optimisation, if you provide a function called 'main' in your handler module, that function is executed on the second and subsequent requests, instead of re-importing the module.

WSGI

WSGI is a Python standard for interactions between servers and webapps. It utilizes components of the CGI standard, enhancing them in a manner that makes it easier to use in Python. Although it's not necessary to use WSGI with App Engine, it is convenient, and most framework libraries expect it, so that's what we'll be using.

WSGI operates by calling an 'application' function with a specific signature. The function is expected to take two arguments, 'environ' and 'start_response', and return an iterable of strings. The environ argument is a Python dict, containing a standard CGI environment, along with certain extra values specific to WSGI. The 'start_response' argument is a function, which itself takes two parameters, 'status' and 'response_headers'.

When called, a WSGI application is expected to do its stuff, then call start_response with the HTTP status code and a dictionary of HTTP headers to return to the client. Then, it should return or yield the body of the response as an iterable sequence of strings. Since App Engine doesn't support streaming responses, returning or yielding are equivalent, so we'll simply use return, for simplicity.

The way WSGI works permits very modular design of apps and frameworks. WSGI middleware is code that takes a WSGI application and 'wraps' it, transparently adding functionality. An example of WSGI middleware is beaker, a Python library that provides caching and session handling for WSGI applications.

Here's a simple WSGI application that prints 'hello world':

def application(environ, start_response):
  start_response(200, {'Content-Type': 'text/plain'})
  return ['Hello, world!']

As you can see, this is still a bit low level for your average webapp - hence our quest to write our own framework. There are several major components to a webapp framework, and we'll be covering them over the next couple of weeks:

1. Routing
2. Request decoding & Response encoding
3. Request handlers
4. Templates
5. Sessions
6. Optimizing performance with load-on-demand

In each part of the series, we'll discuss the currently available options for that part of the framework, then decide on a solution that best suits our specific needs, and implement it. In some cases we'll go with pre-made solutions, while in others we'll choose to implement it ourselves. In the most part, the decision of which of these to choose will rest on which teaches us the most about how it all works.

Look out for the first post, on request routing, on Wednesday!

As you've probably guessed by now, I'm not posting over the holiday period. Expect new content, including an all new series of posts, in the new year, however!

In the meantime, enjoy your time with your families, if that's what you're doing. As for myself and my wife, Hayley, we're back in New Zealand, enjoying some quality time with our families.

Recently, the App Engine team announced that they'd be pre-releasing SDKs for testing and feedback, before they go live in production. With the first prerelease, 1.3.1, a number of new features are included in the SDK. Today we'll discuss cursors - how they work, and what they're useful for.

Cursors are a feature that many people have been waiting for with bated breath. As well as making pagination easier, they also provide a way around the "1000 result limit" that many people feel (in some cases correctly) makes it harder to achieve what they want to do on App Engine.

When it comes to investigating new features, there are two really useful tools: An interactive console - such as that on http://localhost:8080/_ah/admin/, http://shell.appspot.com/ or the remote_api console - and the source code. Many people forget that as an Open Source project, the App Engine SDK code is all available - and easily browseable on code.google.com.

Our first stop is google/appengine/ext/db/__init__.py. Of interest here is the cursor() method, which starts on line 1600. As you can see, when called on a query that's already been executed (with .fetch(), .get(), etc), it constructs a datastore_pb.CompiledQuery object, fills in its fields with information from the query, and returns the encoded Protocol Buffer, wrapped in base64 for easy transport. Let's give it a try in our interactive shell:

>>> class TestModel(db.Model): pass
>>> db.put([TestModel() for x in range(100)])

>>> q = TestModel.all()
>>> [x.key().id() for x in q.fetch(5)]
[1, 2, 3, 4, 5]

>>> q.cursor()
'CxoRY3Vyc29yPTUmb2Zmc2V0PTUgAAxgAA=='

About what we expected, given the source. How do we use it, though? The very next method after cursor() is with_cursor(), which, according to the docstring, will "set the start of this query to the given serialized cursor". Perfect! Let's give that a try, then:

>>> class TestModel(db.Model): pass

>>> q = TestModel.all()
>>> [x.key().id() for x in q.fetch(3)]
[1, 2, 3]

>>> r = TestModel.all().with_cursor(q.cursor())
>>> [x.key().id() for x in r.fetch(3)]
[4, 5, 6]

Easy! This will work for any query at all, and makes it possible to pick up where you left off, simply by storing the cursor string, and using it in a subsequent query.

But what's in these mysterious query strings? Well, we already know they're constructed from datastore_pb.CompiledQuery protocol buffers. Let's write a function that'll let us peek inside one:

import base64
from google.appengine.datastore import datastore_pb

def cursor_to_ascii(cursor):
  pb = datastore_pb.CompiledQuery(base64.urlsafe_b64decode(cursor))
  return pb.ToASCII()

Using it on our earlier cursor, we get:

PrimaryScan {
  start_key: "cursor=5&offset=5"
  start_inclusive: false
}
keys_only: false

As you can see, the internals of a cursor store pretty much the same information you'd store if you were doing pagination yourself - only, with the datastore doing it for you, everything is much easier, and likely more efficient to boot. Finally, let's try it on a slightly more complex query, one for TestModel.all().filter("foo =", bar"):

PrimaryScan {
  start_key: "shell\000TestModel\000foo\000\232bar\000\200"
  start_inclusive: true
}
keys_only: false

Apart from the obvious difference, you'll note this seems to be a different format to the first one. That's because the first one was generated by the dev_appserver, while this one was generated on shell.appspot.com. As you can see, they use slightly different notations - but then, that shouldn't matter, since you certainly shouldn't be relying on the internal format of these data structures for anything except informational purposes!

One caveat for early adopters: A near perfect storm of different minor bugs make testing this in interactive consoles - remote_api, shell.appspot.com and the dev_appserver console - more problematic than it should be. And, of course, cursors, like all other prerelease features, are likely to only work on the dev appserver. But then, that's why it's called a prerelease.

It's Friday evening, which means the Snow Sprint is wrapping up, and everyone's presenting their App Engine apps. There's some pretty impressive work been done in a mere 5 days...

Tweet Engine

First up is us! Myself, Jens Klein, and Sasha Vincic teamed up to write Tweet Engine, a twitter webapp for collaborative tweeting. Many organisations - both companies and open source groups - have shared twitter accounts. Using these shared accounts, however, can be a huge pain, especially if you have multiple accounts to manage. The goal of Tweet Engine is to make this more manageable.

Anyone can sign up by logging in with their Google account. Once signed up, you can add any number of Twitter accounts. We use the Twitter OAuth library, which allows us to obtain permission from a user without prompting you for your password.

Once you've added an account, you can give any number of other people permission to use it. Access is configurable, including full administrator access, just the ability to send and view tweets, or just the ability to suggest tweets for review and approval. Once a suggestion is submitted, anyone with sufficient permissions can approve or decline it. Scheduled tweeting is also supported, for both regular tweets and those that require approval - simply specify the date and time you want it published at.

We also support XMPP: Simply add account_name@tweet-engine.appspotchat.com to your XMPP list, and send tweets to it - they'll be sent immediately. Finally, thanks to Jens' recent efforts, Tweet Engine is also internationalized, in English and German (so far)!

Tweet Engine is, of course, OSS - the entire source is available on GitHub, here. Feel free to fork, download and deploy as you wish. If you implement something cool, don't forget to let us know!

Still on the drawing board:

• More documentation - about pages, help pages, and so forth.
• Email notifications of tweets waiting to be reviewed.
• A page that summarizes all the accounts you have.
• Much much more...

If you feel inspired, feel free to help out with these, too. Or if you just have an idea, file a bug.

gaelogger

Next up was gaelogger, an App Engine logging application. It has a sophisticated web-based interface, allowing filtering and viewing of logs, but its main functionality is as a programmatic logging service. Users can register clients, obtaining a client key, which allows them to log events to the service. The API uses JSONRPC, and supports both individual and batch logging, in addition to querying the logs.

Other users can do live queries in a 'tail -f' fashion, or subscribe to event notifications, receiving notifications via XMPP or email, setting filter criteria to specify what they want to be notified of. The notification service makes use of the Task Queue API in order to be able to send out notifications without being bottlenecked by the limitations of the request that submitted the event.

XMPP isn't just for output - they also support querying the logger via XMPP, as well as subscribing, unsubscribing, and submitting events via XMPP.

On the API end of things, there's already a Python logging handler, which uses threads to asynchronously upload new log events without slowing down the app that's using it.

There's a lot of similarities to gnip and PubSubHubbub here. I think it would be particularly interesting to see them offering atom output and using PubSubHubbub, especially if they consumed it as well as outputting it - it would expand this project's scope substantially.

waph

Another group wrote a monitoring frontend hosted on App Engine, due to being unhappy with ganeti's interface. It's currently at a fairly early stage, supporting creating new graps from the RRD files provided by ganeti - the created graphs then update automatically on the web interface, which certainly looks impressive. Graphs are rendered in-browser using the canvas API. Unfortunately, due to the restrictions of where they could fetch ganeti information from, they didn't end up writing any of the app on App Engine.

Open Dropbox

Open Dropbox is a clone of Dropbox. Unlike Dropbox, Open Dropbox is decentralised, It's still a work-in-progress, but here's what's planned: It will be possible to share and sync folders with hundreds of other users. They build the whole project around doctests, as they made it easier to think about requirements in a comprehensible fashion, while specifying the requirements in the form of a test.

Communication between peers is handled by having each peer generate a public key for themselves, then upload it over HTTPS to App Engine. Other peers can then request the keys - again over a secure link with the App Engine app. Messages between peers are secured and verified using the public keys, using keyCzar.

This post is a brief interlude in the webapps on App Engine series. Fear not, it'll be back!

Frequently, we need to do a datastore query for a set of records, then do something with a property referenced by each of those records. For example, supposing we are writing a blogging system, and we want to display a list of posts, along with their authors. We might do something like this:

class Author(db.Model):
  name = db.StringProperty(required=True)

class Post(db.Model):
  title = db.TextProperty(required=True)
  body = db.TextProperty(required=True)
  author = db.ReferenceProperty(Author, required=True)


posts = Post.all().order("-timestamp").fetch(20)
for post in posts:
  print post.title
  print post.author.name

On the surface, this looks fine. If we look closer, however - perhaps by using Guido's excellent AppStats tool, we'll notice that each iteration of the loop, we're performing a get request for the referenced author entity. This happens the first time we dereference any ReferenceProperty, even if we've previously dereferenced a separate ReferenceProperty that points to the same entity!

Obviously, this is less than ideal. We're doing a lot of RPCs, and incurring a lot of per-RPC overhead and delay. Further, since we're performing them serially, they take a lot longer than a batch fetch for the equivalent number of entities would take. Is there some way we can improve on this?

It turns out, there is. There's a well known mechanism for retrieving the key for a ReferenceProperty without dereferencing it, by using Property.get_value_for_datastore. For example:

key = Post.author.get_value_for_datastore(a_post)

Given a list of entities, then, we can get the keys they reference, and with those, we can fetch the referenced entities. How do we update the entities in the list with the retrieved references, though? The code for caching referenced entities is deep inside the ReferenceProperty class, and although we could monkey around with it, we really shouldn't - it's likely to break without notice.

There's a way around this impasse, however: We can simply set the ReferenceProperty to the value we retrieved, as if we were modifying it. This will cause the ReferenceProperty to update the value (but no change there), and to cache the entity for later dereferencing. Easy!

Here's the code:

def prefetch_refprop(entities, prop):
  ref_keys = [prop.get_value_for_datastore(x) for x in entities]
  ref_entities = dict((x.key(), x) for x in db.get(set(ref_keys)))
  for entity, ref_key in zip(entities, ref_keys):
    prop.__set__(entity, ref_entities[ref_key])
  return entities

Line 2 extracts the referenced key from each entity that was passed in, storing it in a list named ref_keys. On line 3, we first convert ref_keys to a set, eliminating any duplicates, then we retrieve the referenced entities with a db.get(). Finally, we construct a dict mapping entity keys to retrieved entities with the results. Line 4 iterates through the original entities and the keys they referenced, and line 5 sets the property on each entity to the retrieved value, looking it up in the dict we just constructed. At the end, we return the original list of entities, so we can use our function as a filter, if we wish. Here's how it's used:

posts = Post.all().order("-timestamp").fetch(20)
prefetch_refprop(posts, Post.author)
for post in posts:
  print post.title
  print post.author.name

This is looking really good - but what if we want to dereference multiple ReferenceProperty fields on the same set of entities? We could call prefetch_refprop once for each, but that's reintroducing some of the same inefficiency we wrote all this to combat. Can we do better? Naturally we can:

def prefetch_refprops(entities, *props):
    fields = [(entity, prop) for entity in entities for prop in props]
    ref_keys = [prop.get_value_for_datastore(x) for x, prop in fields]
    ref_entities = dict((x.key(), x) for x in db.get(set(ref_keys)))
    for (entity, prop), ref_key in zip(fields, ref_keys):
        prop.__set__(entity, ref_entities[ref_key])
    return entities

This is similar to the original function, but with a couple of added wrinkles. We've converted the "prop" argument to "*props", allowing us to pass any number of ReferenceProperty instances as additional arguments. On line 2, we create the list "fields", which consists of the cartesian join of entities and properties - that is, every combination of entity and property in the input lists. Line 3 operates much the same as previously, except that both the property and the entity are fetched from the fields list. Line 4 remains completely unchanged, while line 5, the loop, now zips together the fields list and the referenced keys. Line 6 behaves as previously.

Using this new function is exactly the same as using the original one, except that we can now pass multiple ReferenceProperty instances, as in "prefetch_refprops(posts, Post.author, Post.category)" - and they're all fetched with a single datastore get.

One caveat if you intend to use this recipe: With regular dereferencing, two fields that reference the same entity will return different objects, which can be modified independently. With our recipe, though, if the keys are the same, the entities will be the same object - so modifying post1.author could modify post2.author! Bear this in mind if you intend to modify the referenced entities.

This is part of a series on writing a webapp framework for App Engine Python. For details, see the introductory post here.

In the first three posts of this series, we covered all the components of a bare bones webapp framework: routing, request/response encoding, and request handlers. Most people expect a lot more out of their web framework, however. Individual frameworks take different approaches to this, from the minimalist webapp framework, which provides the bare minimum plus some integration with other tools, to the all-inclusive django, to the 'best of breed' Pylons, which focuses on including and integrating the best libraries for each task, rather than writing their own.

For our framework, we're going to take an approach somewhere between webapp's and Pylons': While keeping our framework minimal and modular, we'll look at the best options to use for other components - specifically, templating and session handling. In this post, we'll discuss templating.

To anyone new to webapps, templates may seem somewhat unnecessary. We can simply generate the output direct from our code, right? Many CGI scripting languages used this approach, and the results are often messy. Sometimes, which page to be generated isn't clear until after a significant amount of processing has been done, and dealing with errors and other exceptional conditions likewise becomes problematic. Finally, this approach tends to lead to gobs of print statements cluttering up the code, making both the structure of the page and the flow of the code unclear.

Templating systems were designed to eliminate these issues. Instead of generating the page as we process the request, we wait until we're done, construct a dictionary of variables to pass to the template, and select and render the template we need. The templating system then takes care of interpreting the template, substituting in the variables we passed where necessary. Templating doesn't have to be complicated - here's a simple templating system:

def render_template(template, values):
  return template % values

# Example
template = """Hello, %(name)s! How are you this %(time_of_day)s?"""
self.response.body = render_template(template, values)

This 'templating system' simply uses Python's string formatting functionality to generate its result. It quickly becomes apparrent that this isn't sufficient for templating web pages, though - we need more functionality. At a minimum, we need some form of flow control, so we can include sections of a page conditionally, such as login/logout links, and some form of looping construct, so we can include repeated sections, such as results from datastore queries. It helps if our templating system provides some features for template reuse, too, such as including other templates, or extending them.

How powerful should our templates be, though? This is a source of some disagreement. Some templating systems, like Django's, take a very minimalist approach, and contain only the bare minimum of functionality required to render templates. Any form of calculation - even things as simple as basic math and comparisons - should be done in code, with the results passed to the template. Other templating systems, like Mako, provide a much more full-featured templating language, and trust you not to abuse it.

Here's what sample templates look like in a few templating languages:

Django:

{% extends "base_generic.html" %}

{% block title %}{{ section.title }}{% endblock %}

{% block content %}
<h1>{{ section.title }}</h1>

{% for story in story_list %}
<h2>
  <a href="{{ story.get_absolute_url }}">
    {{ story.headline|upper }}
  </a>
</h2>
<p>{{ story.tease|truncatewords:"100" }}</p>
{% endfor %}
{% endblock %}

You're probably already familiar with Django's template syntax from previous posts. Because it's included with App Engine, it's often the easy default. As we've already mentioned, it's very restrictive about what you can do: It provides a few primitives, and relies on an extensible library of tags and filters (the bits after the | in {{...}}) to make it useful.

Mako:

<%inherit file="base.html"/>
<%
    rows = [[v for v in range(0,10)] for row in range(0,10)]
%>
<table>
    % for row in rows:
        ${makerow(row)}
    % endfor
</table>
   
<%def name="makerow(row)">
    <tr>
    % for name in row:
        <td>${name}</td>\
    % endfor
    </tr>
</%def>

Mako is another popular templating engine, and takes the opposite approach to Django: Templates are created by inserting actual Python code, inside special processing directives of the form <% .. %>. It even goes so far as to permit and encourage defining functions inside templates! Mako works around Python's use of indentation for control flow by defining new keywords such as 'endfor'.

Cheetah

<html>
  <head><title>$title</title></head>
  <body>
    <table>
      #for $client in $clients
      <tr>
        <td>$client.surname, $client.firstname</td>
        <td><a href="mailto:$client.email">$client.email</a></td>
      </tr>
      #end for
    </table>
  </body>
</html>

Cheetah is another templating system that takes the "we provide the gun, you point it at your foot" approach. It's similar to Mako in many ways, but doesn't require variable substitutions to be embedded in curly braces, and instead of using processing directives, it treats lines starting with a # as Python code. It also uses special directives such as 'end for' for nesting.

Jinja2

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<html lang="en">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    {% block head %}
    <link rel="stylesheet" href="style.css" />
    <title>{% block title %}{% endblock %} - My Webpage</title>
    {% endblock %}
</head>
<body>
    <div id="content">{% block content %}{% endblock %}</div>
    <div id="footer">
        {% block footer %}
        © Copyright 2008 by <a href="http://domain.invalid/">you</a>.
        {% endblock %}
    </div>
</body>

Jinja2 claims to have "Django-like syntax (but faster)". Notably, the syntactic elements for loops, control flow, etc, are a lot more Python-like, but they're still limited to what the language supports, and it still relies on specially defined tests, filters, etc.

Tenjin

<html>
  <body>
    <h1>${title}</h1>
    <table>
<?py i = 0 ?>
<?py for item in items: ?>
<?py     i += 1 ?>
<?py     color = i % 2 == 0 and '#FFCCCC' or '#CCCCFF' ?>
      <tr bgcolor="#{color}">
        <td>#{i}</td>
        <td>${item}</td>
      </tr>
<?py #endfor ?>
    </table>
  </body>
</html>

Tenjin claims to be the fastest Python templating framework - and it has benchmarks (although not exhaustive ones) to back it up. It takes the general approach, with Python expressions and statements embedded directly into the markup. Notably, indentation of the Python statements maters, producing a somewhat confused mix of markup and Python code.

Chameleon

<table border="1">
  <tr tal:repeat="row range(10)">
    <td tal:repeat="column range(10)">
      <span tal:define="x repeat.row.number;
                        y repeat.column.number;
                        z x * y"
            tal:replace="string:$x * $y = $z">1 * 1 = 1</span>
    </td>
  </tr>
</table>

Chameleon is based on the Zope Page Templates specification, which takes an interesting approach. Chameleon templates are valid XML documents, unlike many templating engines, and it uses namespaces for attributes and tags to define the template behaviour. For example, the "tal:repeat" tag indicates that the tag it's on and all its children should be repeated for each value in the Python iterator passed as an argument. tal:replace replaces an element with the value of the expression, while other expressions permit setting attributes and replacing body content, and a 'meta' namespace handles operations such as including other templates.

Chameleon extends the Zope standard in several ways: expressions can be arbitrary Python expressions, and values can be substituted using a ${...} syntax in addition to the XML syntax, which avoids a lot of boilerplate in some situations. Chameleon templates are compiled to Python code on first use - so you're not doing XML DOM manipulation on every template generation. Chameleon recently got App Engine support when the author refactored out some code that relied on modules not available in App Engine.

I haven't mentioned all Python's templating systems here, by a long shot - this is merely a representative sample. For a more complete list, see this page.

Our framework

Examining the different templating engines leads to an interesting observation: Those templating engines that take the Django approach of "only what's necessary" tend to, of necessity, be a lot larger and more involved - and hence have a steeper learning curve - than those that allow you to leverage your Python knowledge in some fashion. For that reason and others, I'm not a big fan of them - I'd rather provide someone with a powerful but lightweight system, and trust them not to shoot themselves in the foot, than use a more complicated system designed to make foot-shooting an impossibility. With that consideration and others in mind, we'll look at what is required to use Chameleon in our framework.

Using Chameleon

Installation is straightforward: Download the tarball from the PyPi page, and copy the Chameleon-1.1.1/src/chameleon directory into a directory on the system path (eg, your app's root folder).

To use Chameleon, we first define a template loader:

from chameleon.zpt import loader

template_path = os.path.join(os.path.dirname(__file__), "..", "templates")
template_loader = loader.TemplateLoader(template_path, auto_reload=os.environ['SERVER_SOFTWARE'].startswith('Dev'))

Template loaders serve to cache loaded and compiled templates, which is essential for performance. As such, it makes sense to define our loader once at module level, and use it for all requests. To render a template, we fetch a template from the loader, then call it with keyword arguments corresponding to the parameters we want to pass to the template:

def TestHandler(RequestHandler):
  def get(self):
    template = template_loader.load("test.pt")
    self.response.body = template(name="test")

In terms of integrating templates into our framework, there's not a great deal we can do without locking users of our framework into using our preferred templating system. You can bundle the templating system with the framework, and even make it create a loader when it's first used. The approach you take depends on where you want to be on the flexibility / ease-of-use axis.

In the next post, we'll discuss session handling, the options available on App Engine, and how to integrate it into our framework.

This is part of a series on writing a webapp framework for App Engine Python. For details, see the introductory post here.

Now that we've covered the background on request handling, it's time to tackle request handlers. Request handlers are the core and most obvious part of a web framework. They serve to simplify the writing of your app, and remove some of the boilerplate that you end up with if you write raw WSGI applications. Before we go any further, let's see what basic request handlers look like in a range of frameworks. Then we can discuss the pros and cons of each, and settle on one for ours.

Django:

def current_datetime(request):
    now = datetime.datetime.now()
    html = "<html><body>It is now %s.</body></html>" % now
    return HttpResponse(html)

App Engine's webapp framework:

class MainPage(webapp.RequestHandler):
    def get(self):
        self.response.headers['Content-Type'] = 'text/plain'
        self.response.out.write('Hello, webapp World!')

Werkzeug:

@expose('/display/<uid>')
def display(request, uid):
    url = URL.query.get(uid)
    if not url:
        raise NotFound()
    return render_template('display.html', url=url)

web2py:

def hello1():
    return "Hello World"

Pylons:

class HelloController(BaseController):

    def index(self):
        # Return a rendered template
        #return render('/hello.mako')
        # or, Return a response
        return 'Hello World'

You've probably noticed that the handlers here fall into two broad categories: Function based handlers, and class based handlers. Frameworks like Django, Werkzeug and web2py take a function-based approach, where each handler is a function. Frequently, such functions are expected to return the response. This matches up fairly closely with the WSGI approach, though frameworks generally add a lot of extra features and syntactic sugar.

Other frameworks, like Pylons and the webapp framework, use class based handlers: each handler is a class, subclassing a base request handler. Requests are handled by instantiating the class, then calling a handler method. In the case of Pylons, multiple different URL patterns may route to the same handler class, resulting in different handler methods being called, while in the case of the webapp framework, the method that gets called is determined entirely by the HTTP method of the request.

For various reasons, we're going to take the class-based approach in our framework. Whilst the function-based approach definitely has its merits, there are several benefits to using a class-based approach in our framework:

• Easier to understand. Everyone understands inheritance; not as many people understand the magic behind some of the function-based frameworks.
• Our handler classes can also be valid WSGI apps.
• It's easier for users of our framework to extend the handler's functionality for their own use.

As far as request routing and dispatching goes, we're going to take the same approach as the webapp framework: The method we call on our handler object depends entirely on the HTTP method of the request. We'll also take the opportunity to make use of WebOb's more advanced features, as we discussed yesterday.

Let's start with the basic functionality we need for our handler to work at all:

import webob
import webob.exc

class RequestHandler(object):
  ALLOWED_METHODS = set(['get', 'post', 'put', 'head', 'delete'])

  def __call__(self, environ, start_response):
    self.request = webob.Request(environ)
    self.response = webob.Response(request=self.request, conditional_response=True)
    try:
      self.handle()
      return self.response(environ, start_response)
    except webob.exc.WSGIHTTPException, ex:
      return ex(environ, start_response)
    except Exception, ex:
      return self.handle_exception(ex)

First, we define a set of allowed HTTP methods. We'll use those shortly. Then, we define the special method __call__, which as we previously discussed, is executed when something attempts to call instances of our class as functions. We take the standard WSGI application arguments, and immediately construct WebOb request and response objects, making sure to set up the response object so it supports conditional responses.

Then, we call the yet-to-be-defined method handle(), which will take care of dispatching the request to the appropriate user defined method. Apart from making the code cleaner, this also allows subclasses to override how requests are dispatched to methods, if they wish, or to add code that is executed regardless of the HTTP method. If handle() returns successfully, we return the response to the user by treating the WebOb response object as a WSGI application.

If the handle() method throws one of WSGI's status code exceptions, we catch that and call it to generate the WSGI response. If some other exception occurs, we catch that and call the handle_exception method, which is expected to do generic error handling for uncaught exceptions.

The handle() method is fairly straightforward, as it only needs to take care of dispatching requests to the appropriate method. Let's take a look:

  def handle(self):
    method_name = self.request.method.lower()
    method = getattr(self, method_name, None)
    kwargs = self.request.environ.get('router.args', {})
    if method_name not in self.ALLOWED_METHODS or not method:
      raise webob.exc.HTTPMethodNotAllowed()
    method(**kwargs)

First, we fetch and normalize the name of the HTTP method. We also extract the keyword arguments that were extracted by the router code back in the first post of the series. Then, we compare it against the list of allowed methods. If it doesn't match, or the method itself isn't found, we simply raise an HTTPMethodNotAllowed exception, which the exception handling code in __call__ takes care of for us. Finally, we call the method in question, passing the router arguments as keyword arguments.

The default implementation of handle_exception() is also fairly straightforward:

  def handle_exception(self, ex):
    logging.exception("Unhandled exception")
    lines = ''.join(traceback.format_exception(*sys.exc_info()))
    return webob.exc.HTTPInternalServerError(detail='%s' % lines)

All we do here is obtain a nicely formatted version of the exception, log it, and print it out. In a real, production-quality framework, you'd definitely want to make sure that in 'production mode', you don't show stacktraces to the users!

Finally, there's one more enhancement we can make to our basic framework to avoid a gotcha that the webapp framework and some other frameworks suffer from: Lack of support for the HEAD method. In webapp, and in our framework so far, if a browser makes a HEAD request, and the user hasn't explicitly implemented it, an HTTP 405 "Method not allowed" response is returned! This has practical implications - some sites such as digg do HEAD requests to check for the existence of a page, so failing to handle it can make it impossible to submit your site to services like digg.

Fortunately, this is easily worked around: All we have to do is provide a default implementation of head() that executes get(), then erases the content of the response. It's not the most efficient, but it is effective:

  def head(self, **kwargs):
    method = getattr(self, 'get', None)
    if not method:
      raise webob.exc.HTTPMethodNotAllowed()
    method(**kwargs)
    self.response.body = ''

The only complication here is that we can't rely on get() being defined in every handler subclass, so we have to use getattr to retrieve it, and throw a regular 405 error if it doesn't exist. Otherwise, we're simply executing get(), then erasing the body of the response before returning.

Let's use our new framework to write a couple of sample handlers:

class HelloHandler(RequestHandler):
  def get(self, name='world'):
    self.response.content_type = 'text/plain'
    self.response.body = 'Hello, %s.' % (name,)

class EchoHandler(RequestHandler):
  def get(self, **kwargs):
    self.response.content_type = 'text/plain'
    self.response.body = repr(kwargs)

router = WSGIRouter()
router.connect("/hello", HelloHandler())
router.connect("/hello/{name}", HelloHandler())
router.connect("/echo/{foo}/{bar:[0-9]+}", EchoHandler(), test="test")

Things are starting to look a little more familiar, right? No more boilerplate, no raw WSGI environments, just familiar and convenient handler classes, request and response objects.

At this point, we've written everything required of a bare-bones webapp framework. Most people expect more to be bundled with their framework, however, and in the next few posts we'll deal with that, starting with the next post, where we'll discuss templating.

This is part of a series on writing a webapp framework for App Engine Python. For details, see the introductory post here.

This post is mostly background on request and response encoding/decoding. If you're already fairly familiar with how this works in CGI and in higher level frameworks, you may want to skip this and wait for the next posting, on request handlers.

If you've ever written a CGI script, you'll be well aware of how much of a pain interpreting and decoding CGI environment variables and headers can be - so much so that the first action of many is to find or write a library to handle it for you! And if you've ever coded in a CGI-inspired language such as PHP, you're probably familiar with how much of a pain managing the combination of response headers and output content can likewise be.

As a result of this, one of the most basic tools a framework offers is some form of abstraction for request and response data. Typically, this takes care of collecting and parsing HTTP headers, parsing the query string (if any), decoding POSTed form data, and so forth. Better frameworks also take care of common header-related tasks, like interpreting cookies and headers that should affect the nature of the response.

Very nearly every framework defines its own request and response abstraction. Django and Werkzeug both define their own, for example, while the authors of the Paste framework recognized this trend towards repetition, and created WebOb, a standalone library that incorporates just the request and response objects from the Paste framework.

Due to the constraints, different frameworks' takes on request and response objects tend to be very similar - there's often not much to choose between them. For the same reason, it's also the case that writing our own request handling would be tedious, and not particularly enlightening. With that in mind, we'll go ahead and use the WebOb library, for these reasons:

• It fulfills all our requirements admirably
• It's available as a separate library
• It's already bundled with the App Engine SDK!
• It has several advanced features we can make use of to improve our framework overall

Without further ado, let's take a look at the basic workings of WebOb. Unsurprisingly, there are two major classes we need to concern ourselves with: Request, and Response. Let's examine them in order.

The Request object is fairly straightforward: To construct one, you must pass in a WSGI environment dictionary. The resulting Request object then exposes everything you would generally expect to have available: Information about the URL and the request method, headers, query and form data, and so forth. It also provides access to the raw body of the request (if any), and interprets cookies for you. Finally, it breaks common headers out into their own properties, including the 'accept' headers and those dealing with conditional requests and caching.

The response object is a little more surprising. In addition to all the usual functionality, such as allowing you to set headers and fill out the response body, the Response object is itself a fully-formed WSGI application. Apart from providing an easy way to actually send the response back to the client, this also provides additional functionality: The Webob response object automatically takes care of handling HTTP conditional requests for you - instantly providing your app with a bunch of features that many interactive apps don't support without much manual involvement, or at all.

Let's see a practical example of how to use the WebOb Request and Response objects in a WSGI application:

def application(environ, start_response):
  request = webob.Request(environ)
  response = webob.Response(request=request, conditional_response=True)
  response.content_type = 'text/plain'
  out = response.body_file
  out.write("Hello, %s!" % (request.GET.get('name', 'world'),))
  return response(environ, start_response)

As you can see, this is starting to look a little saner, and more like what you're used to if you regularly use frameworks. There's still a bit of boilerplate here, but we'll be taking care of that when we discuss request and response handlers in the next post.

One final feature of the WebOb library that we'll be making use of is its set of status code exceptions. This comprises a comprehensive set of classes for all the HTTP response codes. These classes are WSGI applications, so they can be used as a WSGI application, and they are also valid Python exception classes, so they can be thrown. This is particularly useful because it allows you to 'throw' an error status code in an intuitive fashion - for example:

  def some_handler(request):
    if not request.is_authorized:
      raise exc.HTTPForbidden()
    # Otherwise, do stuff...

You're not limited to using 400 and 500 status codes in this fashion. Somewhat less intuitive, but often useful, is the ability to throw a redirect:

  def some_handler(request):
    if not request.logged_in:
      raise exc.HTTPFound(location='/login')
    # Otherwise, user is logged in...

We'll be making use of these when we start to deal with request handling, in the next post.

Update: Added a few paragraphs about WebOb's status code exceptions.

I'm away at the Lovely Snow Sprint all next week. Posts in the series will continue as normal, but may be displaced by updates from the sprint if anything particularly fascinating happens. ;)

I recently ran the gold linker under Thread Sanitizer. It’s a nice plugin for Valgrind which looks for race conditions in multi-threaded programs. To describe it briefly, it builds Happens-Before relationships based on mutex operations and warns when it notices a write and a read/write to the same memory location without a Happens-Before relationship. This approach can yield false positives to be sure, but it does a very nice job of identifying real problems.

It was able to identify one real bug in gold, one problem that led to less efficient link time, and several cases where several threads would set a shared memory location to the same value. The latter cases are not a problem on x86 architectures, though they could be on other processors. In order to get clean Thread Sanitizer results in the future, I fixed all of the cases so that I could get a clean run of gold, at least with the default settings.

The real bug that it found was a typical multi-threaded bug: the code looked fine, but it had a well-hidden error. Gold uses a workqueue of tasks to execute, with a pool of worker threads. Many of the tasks are run using a blocker token. The blocker token is set to the number of tasks that precede it. As each task completes, it decrements the blocker count. When the count goes to zero, the next set of tasks can start. This is a simple way to parallelize linker operations, in which one set of operations (e.g., process the symbol tables) must be run before the next set (e.g., process the relocations) can begin. Naturally I paid close attention to the blocker behaviour when a task completed, and there were no problems there. The problem arose in setting the blocker count when the tasks started. The code was doing a loop of “increment the blocker count” and then “queue the task.” What I forgot was that the process of queuing the task actually lets another thread in the pool start working on it immediately. When the task completed, it decremented the blocker count with a lock. But if the task completed fast enough, the initial code was still running the loop queuing up new tasks, and thus incrementing the blocker count. I didn’t think that I needed to lock the increment, since I wasn’t expecting any task to actually complete before I started all of the tasks. A dumb mistake—just the kind of mistake one makes in multi-threaded programming.

Gold is written in C++. In Go I would of course have each task communicate its completion on a channel. The locking would be handled by the runtime, and there would be no chance for me to make the same sort of error. If you write multi-threaded code, and you can’t use Go, you should definitely check out Thread Sanitizer.

Sorry, but I'm totally mentally exhausted after a long week - including a talk at UCD on Wednesday - and I just don't have the energy to write up today's post. Look out for it on Monday, instead.

In Go, channels have a fixed length buffer. Sometimes it is useful to add a buffer of unlimited length to a channel (here is an example). The first question is what the interface should look like. I can think of three immediate possibilities (assume T is an arbitrary type – if Go had generics, this would be a generic function):

Given a channel, make sure that no writes to that channel will
block, and return a channel from which the buffered values can be read:

func Buffer(in <-chan T) <-chan T

Given a channel, return a channel that will buffer writes
to that channel:

func Buffer(out chan<- T) chan <-T

Given two channels, connect them via a buffering process:

func Buffer(in <-chan T, out chan<- T)

Of these possibilities, on balance I think I prefer the second, as no operations will be performed on the original channel except when a value is written on the returned channel.

I’d be interested in hearing arguments for or against the other possibilities.

Here is one simple, and relatively slow implementation. It uses the doubly-linked list implementation from the Go library. I timed it at 2076ns per item transferred on my machine. Note the code that runs before the select statement each time through the loop, which works out whether we want to be sending a value, and when it is time to finish. This relies on the fact that in a Go select statement, operations on nil channels are ignored.

import "container/list"
func BufferList(out chan<- T) chan<- T {
	in := make(chan T, 100)
	go func() {
		var buf = list.New()
		for {
			outc := out
			var v T
			n := buf.Len()
			if n == 0 {
				// buffer empty: don't try to send on output
				if in == nil {
					close(out)
					return
				}
				outc = nil
			}else{
				v = buf.Front().Value.(T)
			}
			select {
			case e := <-in:
				if closed(in) {
					in = nil
				} else {
					buf.PushBack(e)
				}
			case outc <- v:
				buf.Remove(buf.Front())
			}
		}
	}()
	return in
}

The above implementation allocates a new linked list item for every value transferred. Here’s an alternative implementation that uses an array as a circular buffer, amortising allocations over time by doubling the size of the buffer when it overflows, and shrinking it when there is too much space. Although the basic structure is similar, the code is more complex, and the time saving is modest – I timed it at 1729ns per item transferred, an improvement of 17%. Removing the code to shrink the buffer does not make it significantly faster.

func BufferRingOrig(out chan<- T) chan<- T {
	in := make(chan T, 100)
	go func() {
		var zero T
		var buf = make([]T, 10)
		var i = 0 // location of first value in buffer.
		var n = 0 // number of items in buffer.
		for {
			outc := out
			switch {
			case n == 0:
				// buffer empty: don't try to send on output
				if in == nil {
					close(out)
					return
				}
				outc = nil

			case n == len(buf):
				// buffer full: expand it
				b := make([]T, n*2)
				copy(b, buf[i:])
				copy(b[n-i:], buf[0:i])
				i = 0
				buf = b

			case len(buf) > 128 && n*3 < len(buf):
				// buffer too big, shrink it
				b := make([]T, len(buf) / 2)
				j := i + n
				if j > len(buf) {
					// wrap around
					k := j - len(buf)
					j = len(buf)
					copy(b, buf[i:j])
					copy(b[j - i:], buf[0:k])
				}else{
					// contiguous
					copy(b, buf[i:j])
				}
				i = 0
				buf = b
			}
			select {
			case e := <-in:
				if closed(in) {
					in = nil
				} else {
					j := i + n
					if j >= len(buf) {
						j -= len(buf)
					}
					buf[j] = e
					n++
				}
			case outc <- buf[i]:
				buf[i] = zero
				if i++; i == len(buf) {
					i = 0
				}
				n--
			}
		}
	}()
	return in
}

I wondered if the unnecessary tests before the select statement were making any significant difference to the time taken. Although it makes it easy to preserve the invariants, there is no need to test whether the buffer is empty when a value has just been placed in it, for example.

Here is a version that only does the tests when necessary. Interestingly, this change actually made the code run marginally slower (1704ns per item)

func BufferRing(out chan<- T) chan<- T {
	in := make(chan T, 100)
	go func() {
		var zero T
		var buf = make([]T, 10)
		var i = 0 // location of first value in buffer.
		var n = 0 // number of items in buffer.
		var outc chan<- T
		for {
			select {
			case e := <-in:
				if closed(in) {
					in = nil
					if n == 0 {
						close(out)
						return
					}
				} else {
					j := i + n
					if j >= len(buf) {
						j -= len(buf)
					}
					buf[j] = e
					n++
					if n == len(buf) {
						// buffer full: expand it
						b := make([]T, n*2)
						copy(b, buf[i:])
						copy(b[n-i:], buf[0:i])
						i = 0
						buf = b
					}
					outc = out
				}
			case outc <- buf[i]:
				buf[i] = zero
				if i++; i == len(buf) {
					i = 0
				}
				n--
				if n == 0 {
					// buffer empty: don't try to send on output
					if in == nil {
						close(out)
						return
					}
					outc = nil
				}
				if len(buf) > 128 && n*3 < len(buf) {
					// buffer too big, shrink it
					b := make([]T, len(buf) / 2)
					j := i + n
					if j > len(buf) {
						// wrap around
						k := j - len(buf)
						j = len(buf)
						copy(b, buf[i:j])
						copy(b[j - i:], buf[0:k])
					}else{
						// contiguous
						copy(b, buf[i:j])
					}
					i = 0
					buf = b
				}
			}
		}
	}()
	return in
}

Although the speed improvement from the above piece of code was disappointing, the change paves the way for a change that really does make a difference. A select statement in Go is significantly more costly than a regular channel operation. In the code below, we loop receiving or sending values as long as we can do so without blocking. Here’s a version of the list-based code that does this. I measured it at 752ns per item, an improvement of 63% over the original, or 2.7x faster.

func BufferListCont(out chan<- T) chan<- T {
	in := make(chan T, 100)
	go func() {
		var buf = list.New()
		var outc chan<- T
		var v T
		for {
			select {
			case e := <-in:
				if buf.Len() == 0 && !closed(in) {
					outc = out
					v = e
				}
				for {
					if closed(in) {
						in = nil
						if buf.Len() == 0 {
							close(out)
							return
						}
						break
					}
					buf.PushBack(e)
					var ok bool
					if e, ok = <-in; !ok {
						break
					}
				}

			case outc <- v:
				for {
					buf.Remove(buf.Front())
					if buf.Len() == 0 {
						// buffer empty: don't try to send on output
						if in == nil {
							close(out)
							return
						}
						outc = nil
						break
					}
					v = buf.Front().Value.(T)
					if ok := outc <- v; !ok {
						break
					}
				}
			}
		}
	}()
	return in
}

One objection to the above code is that in theory if there was a fast enough producer on another processor, the buffer process could spend forever feeding values into the buffer, without ever trying to write them out. Although I believe that in practice the risk is negligible, it’s easy to guard against anyway, by only adding a fixed maximum number of values before returning to the select statement.

Here’s my final implementation, using the looping technique and with the guard added in.

I timed it at 427ns per item transferred, an improvement of 79% over the original version, or almost 5x faster. Using a buffered channel directly is only 2.4x faster than this.

func BufferRingContCheck(out chan<- T) chan<- T {
	in := make(chan T, 100)
	go func() {
		var zero T
		var buf = make([]T, 10)
		var i = 0 // location of first value in buffer.
		var n = 0 // number of items in buffer.
		var outc chan<- T
		for {
			select {
			case e := <-in:
				for added := 0; added < 1000; added++ {
					if closed(in) {
						in = nil
						if n == 0 {
							close(out)
							return
						}
						break
					}
					j := i + n
					if j >= len(buf) {
						j -= len(buf)
					}
					buf[j] = e
					n++
					outc = out		// enable output
					if n == len(buf) {
						// buffer full: expand it
						b := make([]T, n*2)
						copy(b, buf[i:])
						copy(b[n-i:], buf[0:i])
						i = 0
						buf = b
					}
					var ok bool
					if e, ok = <-in; !ok {
						break
					}
				}
			case outc <- buf[i]:
				for {
					buf[i] = zero
					if i++; i == len(buf) {
						i = 0
					}
					n--
					if n == 0 {
						// buffer empty: don't try to send on output
						if in == nil {
							close(out)
							return
						}
						outc = nil
						break
					}
					if len(buf) > 128 && n*3 < len(buf) {
						// buffer too big, shrink it
						b := make([]T, len(buf) / 2)
						j := i + n
						if j > len(buf) {
							// wrap around
							k := j - len(buf)
							j = len(buf)
							copy(b, buf[i:j])
							copy(b[j - i:], buf[0:k])
						}else{
							// contiguous
							copy(b, buf[i:j])
						}
						i = 0
						buf = b
					}
					if ok := outc <- buf[i]; !ok {
						break
					}
				}
			}
		}
	}()
	return in
}

Obviously the final code is significantly bigger and more complex than the original. Which implementation should we choose? Lacking generics, this code cannot usefully be put into a library, as most channels are not of type chan interface{}.

Given this, in most instances, perhaps the first version is to be preferred, as it’s smaller to cut and paste, and easier to understand. In cases where performance is crucial, the final version can easily be substituted.

Perhaps there’s another faster technique that I haven’t found yet. I’d be interested to hear any ideas on the matter.

The code with all the tests and benchmarks can be found here.

This is part of a series on writing a webapp framework for App Engine Python. For details, see the introductory post here.

A major concern for many people developing for App Engine, particularly those building low-to-medium traffic sites, is instance load time. When App Engine serves the first request to a new instance of your app, it must import the request handler module you specified, which in turn imports all the other modules required to serve the request. In large apps, this can add up to quite a lot of additional overhead for loading requests, and substantially impact the experience for end users.

There are a number of things you can do to reduce loading times, including using lighter weight frameworks instead of all inclusive ones, and breaking seldom used components up into separate handlers - an approach taken by bloggart for the admin interface. One source of inefficiency stands out as a prime candidate for optimisation, though: unnecessary imports.

Many frameworks, including the built in webapp framework, require you to provide a list of handler classes that should be instantiated to serve requests, in a 'url map'. When a request comes in, the framework simply instantiates the relevant class and calls it to handle the request. However, doing this requires you to import all your handler classes so you can construct the url map, and this likely results in transitively importing your entire webapp, even though only a small proportion of it may be required to handle the request at hand.

You may have noticed that our framework, so far, doesn't appear to do any better on this front - and you'd be right. That's about to change, however. One thing we've kept a constant throughout writing the framework is making as many components as possible independent, often by making them WSGI applications in their own right. The router is a WSGI application, and so are handler classes, and so is the WebOb response object. Today, we'll make use of that feature to add support for lazy loading in a manner that's completely independent of our framework - and would work on any other WSGI-based framework, too.

The interface to our lazy loader will be straightforward: Instantiate a class with the fully qualified name of a module containing a WSGI application (such as a handler for our framework), and it will act as a WSGI application that imports the handler module on first access, and calls it in turn. To do this, we need to be able to import a module whose name is defined at runtime - and for that we use the Python builtin __import__.

__import__'s operation is fairly straightforward: Simply call it with the name of the module to be imported as the first argument, and it returns a module instance containing that module. As additional information, we pass it our local and global variables using two more arguments, to allow it to resolve relative imports. In short, this:

from mypackage import mymodule

Is equivalent to this:

mymodule = __import__('mypackage.mymodule', globals(), locals())

We also need to know how to retrieve a name from a module dynamically. This is even simpler: Every object in python (more or less) is backed by a dict, which can be accessed with its '__dict__' attribute. Retrieving a name from a module is thus achieved like so:

myclass = mymodule.__dict__['myclass']

With that in mind, writing our lazy importer is simple:

class WSGILazyLoader(object):
  def __init__(self, fullname):
    self.modulename, self.objname = fullname.rpartition('.')
    self.obj = None

  def __call__(self, environ, start_response):
    if not self.obj:
      module = __import__(self.modulename, globals(), locals())
      self.obj = module.__dict__[self.objname]
    return self.obj(environ, start_response)

To use it, we simply define our handler (and create an instance of it) in one module:

import framework

class HomeHandler(framework.RequestHandler):
  def get(self):
    self.response.body = "Hello, world!"

home_handler = HomeHandler()

And reference it using the lazy loader in another:

import framework
from google.appengine.ext.webapp.util import run_wsgi_app

application = framework.WSGIRouter()
application.connect('/', framework.WSGILazyLoader('home.home_handler'))

def main():
  run_wsgi_app(application)

if __name__ == "__main__":
  main()

You can enhance the lazy loader, of course. Possibilities include having it take the name of a class instead of an instance, and have it automatically instantiate the handler class for each new request, thus duplicating the instance-per-request mechanism of webapp and other frameworks.

Read the discussion of this change on the golang-nuts mailing list. See this notice in UTF-8 format.

For each line, the scanner accepts, in place of the first operator, any of the remaining operators, and outputs a token whose string (set in $GOROOT/src/go/token/token.go) is the first operator.

! ¬

!= ≠

& ∧

&& ⋀

&= ∧=

&^ ∧¬

&^= ∧¬=

… …

:= ≔

<- ←

<< ≪

<<= ≪=

<= ≤

== =? ≟

>= ≥

>> ≫

>>= ≫=

^ ⊻

^= ⊻=

| ∨

|= ∨=

|| ⋁

To install, copy $GOROOT/src/pkg/go/scanner/scanner.go to another file.

Replace scanner.go with scanner.go

Run $GOROOT/src/all.bash and check for 0 unexpected errors.

Changes to scanner.go update gofmt, which accepts UTF-8 operators and outputs their ASCII equivalents.  This mkfile production rule uses gofmt as a preprocessor to create a sharable and compilable file.

%.go: %.ℊℴ

cat $stem.ℊℴ | gofmt > $stem.go

See these files for an example of each new operator form in the context of a simple Go program.

myscanner.ℊℴ

chan.ℊℴ

Please mail me privately if something doesn’t work with this code, to avoid noise on the golang-nuts list, since we’re no longer discussing officially-released code.

E.O. Wilson’s notion of biophilia, which is slightly different from closely related to the newer idea of evolutionary psychology, posits that humans can not be healthy without some access to the natural world. The argument basically amounts to saying that we have evolved in a world which is not completely under human control, and we are not happy unless we are, at least to some extent, in such a world today.

I think the basic argument is likely true for most people. There was an interesting experiment which seemed to show that people next to a window onto an outside nature scene were under less stress than people next to a television screen showing the same image (I can’t find a link, but Journal of Evolutionary Psychology by PH Kahn). I think that many of us look for something to exist outside ourselves, and nature can play that role.

Some people use that as an argument for preserving the environment: we should preserve the environment to keep ourselves healthy (this is in some ways a variant on the idea that we should save the rainforest because we can find new pharmaceutical drugs there). Unfortunately, while I’m definitely in favor of preserving the environment, I think this argument fails. I think that technology can provide us the health benefits of access to the natural world, by hiding the sources of the technology. I think that a sophisticated robot dog can provide all the psychological benefits of a real dog, and more. With a good design we can get the unpredictability, the sense of a different mind and a different world operating. I think those are the things we need. I don’t think they have to actually come from nature.

It’s taken me a while to understand the point of the iPad. I can type on a keyboard faster than I can press keys on a screen, so the iPad would not be useful for me as a computer. And it wouldn’t fit in my pocket, so I wouldn’t carry around the way I carry my phone.

I think I get it now, though. The point of the iPad is to read books, watch videos, and play games. For that, it is looks quite convenient. I can carry it easily from room to room, I can prop it up while I’m eating, I can hold it up while I’m in bed (I assume it’s not too heavy for that). That is, the iPad is not a computer and it’s not a phone: it’s a media consumption device. It’s only real competition at the moment are the various e-book readers, which tend to be limited to just reading books. The first version of the iPad apparently won’t have a camera, and I don’t know whether it has a microphone, but I’m sure that future versions will have both, and that they will be a good way to do video chat.

With that understanding, the complaints I’ve seen about Apple’s tight control over the app store are kind of irrelevant. I don’t want to run arbitrary programs on my books, and I won’t want to run them on an iPad either. When I want to run programs, I’ll use a computer. The app store will be mainly an alternative way to publish information–authors will be able to sell directly to you, rather than going through a publisher.

More troubling are the complaints about Apple’s tight controls over content distribution. If other companies emulate Apple and Amazon, then we are taking another big step toward tight control over copyrighted content and the elimination of some fair use rights. When my only copy of a book is on my Kindle or my iPad, I can’t easily lend it to my friend. When publishers stop making physical books, libraries will become far less useful.

I’ve written before about how copyright will vanish. The iPad points to a way to bring it back: to build copyright controls into the architecture of how people read books. This is the kind of thing Lessig talked about in Code and Other Laws of Cyberspace. Building tight copyright control into a general purpose computer is really really hard. Building it into a closed system like the iPad is much simpler. I’m sure that enterprising people will crack the iPad’s controls, but it remains an open question whether they can crack the controls while still letting the iPad continue to access the various stores that will provide content.

Whether these are reasonable concerns depends entirely on how well the iPad does. I have no plans to buy one myself—I wouldn’t buy one even if I didn’t have these concerns. That is quite different from the iPhone, which I did buy a couple of months after it came out, though I’ve switched to a different phone since. I can’t predict how well the iPad will do; if it is very successful, then we’ll really have to worry about copyright issues in the future.

実践Go言語(Effective Go)の翻訳、6回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

関数

複数の戻り値

Go言語の目新しい特徴のひとつは、関数およびメソッドが複数の値を返せることです。これは、C言語のプログラムで扱いにくかった、受信エラー(EOFを表す-1など)や引数の値の変更などを改善します。

C言語で書き込みエラーが起きたときは、マイナス値を返すことにより通知され、共用の変数にエラーコードが格納されます。Go言語ではWriteは書き込みデータ数とエラーを別々に返すことができます。つまり次のような情報を得ることができます。「何バイトか書き込めましたが、デバイスが一杯になったので一部書き込めませんでした。」

osパッケージの*File.Writeのシグネチャは次のように定義されています。

func (file *File) Write(b []byte) (n int, err Error)

シグネチャが示すとおりに、このメソッドは書き込んだバイト数を返すとともに、n != len(b)のとき非nilのErrorを返します。これは一般的な書き方です。その他の例は、エラーハンドリングに関するセクションを参照ください。

同様のアプローチにより、戻り値に参照パラメータを模してポインタを返す必要がなくなります。次の関数は、バイト配列の指定位置から数値を取り出し、その値と次の位置を返す単純な関数です。

func nextInt(b []byte, i int) (int, int) {
    for ; i < len(b) && !isDigit(b[i]); i++ {
    }
    x := 0
    for ; i < len(b) && isDigit(b[i]); i++ {
        x = x*10 + int(b[i])-'0'
    }
    return x, i
}

この関数は次のようにして、入力配列から数値を取り出すために利用できます。

    for i := 0; i < len(a); {
        x, i = nextInt(a, i)
        fmt.Println(x)
    }

名前付き結果パラメータ

Go言語の、戻り／結果「パラメータ」には、名前をつけることができ、引数パラメータのように通常の変数として扱うことができます。名前が付けられていると、関数が呼び出されたときにその型のゼロ値で初期化されます。引数を持たないreturnステートメントを実行したときは、その時点で結果パラメータに格納されている値が、戻り値として使われます。

名前は必ずしも必要ではありませんが、名前をつけることでコードをより簡潔にすることができます。これは資料としても役立ちます。前出のnextInt関数の結果パラメータに名前を付けると、返されたint値がそれぞれ何を示しているか明確になります。

func nextInt(b []byte, pos int) (value, nextPos int) {

名前付きの結果パラメータは、初期化が行われた上で、パラメータなしのreturnと結びつけられるので、明確になるだけでなくシンプルになります。下は、この仕組みをうまく使ったio.ReadFullの例です。

func ReadFull(r Reader, buf []byte) (n int, err os.Error) {
    for len(buf) > 0 && err == nil {
        var nr int
        nr, err = r.Read(buf)
        n += nr
        buf = buf[nr:len(buf)]
    }
    return
}

Every programmer has a variable naming philosophy. This is mine:

A name's length should not exceed its information content. For a local variable, the name i conveys as much information as index or idx and is quicker to read. Similarly, i and j are a better pair of names for index variables than i1 and i2 (or, worse, index1 and index2), because they are easier to tell apart when skimming the program. Global names must convey relatively more information, because they appear in a larger variety of contexts. Even so, a short, precise name can say more than a long-winded one: compare acquire and take_ownership. Make every name tell.

The information content metric gives a quantitative argument against long-winded names: they're simply inefficient. I internalized this metric years ago but only realized this phrasing of it recently, perhaps because I have been looking at too much Java code.

実践Go言語(Effective Go)の翻訳、5回目です。
前回までの訳は実践Go言語[日本語訳]にまとめてあります。

制御構造

Go言語の制御構造は、C言語の制御構造と似通っていますが、大きく異なる点があります。ループにはdoやwhileはなく、若干改良されたforループだけです。switchはより柔軟になっています。ifとswitchはオプションとしてforのように初期化ステートメントを受け入れます。また、新しい制御構造として、型switch、および多重通信を取り扱えるselectがあります。文法も若干異なっており、丸括弧()は不要ですが、本体部は波括弧で区切られていなければなりません。

if

下はGo言語における単純なifステートメントです。

if x > 0 {
    return y
}

波括弧{}を必須にしたことにより、複数行に渡るifステートメントの記述が見やすくなりました。これは特に、returnやbreakのような制御ステートメントを含むときには優れた書き方です。

ifとswitchには初期化ステートメントを記述できるため、そこでローカル変数の準備を行うのが一般的です。

if err := file.Chmod(0664); err != nil {
    log.Stderr(err)
    return err
}

Go言語のライブラリ内で良く見られる書き方ですが、ifステートメントから次のステートメントへ制御が移らないとき(すなわち、break、continue、goto、returnのいずれかでifの本体から抜けるとき）は、不要なelseは省略します。

f, err := os.Open(name, os.O_RDONLY, 0)
if err != nil {
    return err
}
codeUsing(f)

下の例は、一連のエラー判定を必要とするよく出会う状況です。処理が成功と判断されたときは、エラー処理はスキップし、処理が下方へと流れていくので読みやすいコードとなっています。エラーのときはreturnステートメントで抜けてしまうため、elseステートメントは必要ありません。

f, err := os.Open(name, os.O_RDONLY, 0)
if err != nil {
    return err
}
d, err := f.Stat()
if err != nil {
    return err
}
codeUsing(f, d)

for

Go言語のforループは、C言語のforと似てはいますが、同じではありません。Go言語のforループは、C言語のforとwhileループを兼ねていますが、do-whileループに相当するものはありません。forループには３つの形式がありますが、セミコロンを使うのはそのうちひとつだけです。

// Cのforに相当する形式
for init; condition; post { }

// Cのwhileに相当する形式
for condition { }

// Cのfor(;;)に相当する形式
for { }

省略形式による変数の宣言(:=)を使うと、インデックス変数の宣言が容易です。

sum := 0
for i := 0; i < 10; i++ {
    sum += i
}

配列、スライス、文字列、マップの内容、もしくはチャネルから読み込んだデータをループさせるときは、range節でループを制御することができます。

var m map[string]int
sum := 0
for _, value := range m {  // キーは使われません
    sum += value
}

文字列を扱うときのrangeはより高機能で、UTF-8エンコードでユニコードの各文字を取り出します。このとき不正なエンコーディングあると、1バイトスキップした上で置換ルーン(Unicode replacement character U+FFFD)として扱います。下はループの例です。

for pos, char := range "日本語" {
    fmt.Printf("character %c starts at byte position %d\n", char, pos)
}

次が出力されます。

character 日 starts at byte position 0
character 本 starts at byte position 3
character 語 starts at byte position 6

最後になりますが、Go言語にはカンマ演算子がなく、また++と--は式ではなくステートメントです。forで複数の変数を回したいときは、下のように同時代入を使わなければなりません。

// aを逆に並び替える
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
    a[i], a[j] = a[j], a[i]
}

switch

Go言語のswitchは、C言語より多機能です。switchの式は、定数や整数である必要はありません。一致するものが見つかるまで、caseを上から下まで評価していきます。switchが式を伴わないときは、式の値がtrueとなるcaseにマッチします。これを利用してswitchを使ってif-else-if-elseチェーンを書くことができます。これは慣用的な書き方です。

func unhex(c byte) byte {
    switch {
    case '0' <= c && c <= '9':
        return c - '0'
    case 'a' <= c && c <= 'f':
        return c - 'a' + 10
    case 'A' <= c && c <= 'F':
        return c - 'A' + 10
    }
    return 0
}

caseから直下のcaseへと処理が自動的に移ることはありませんが、caseにはカンマで区切ったリストを指定できます。

func shouldEscape(c byte) bool {
    switch c {
    case ' ', '?', '&', '=', '#', '+', '%':
        return true
    }
    return false
}

下は、2つのswitchステートメントを使ったバイト配列の比較ルーチンです。

// Compare は2つのバイト配列を辞書的に比較して整数を返します。
// 結果は、a == bのとき0、a < bのとき-1、a > bのとき+1
func Compare(a, b []byte) int {
    for i := 0; i < len(a) && i < len(b); i++ {
        switch {
        case a[i] > b[i]:
            return 1
        case a[i] < b[i]:
            return -1
        }
    }
    switch {
    case len(a) < len(b):
        return -1
    case len(a) > len(b):
        return 1
    }
    return 0
}

switchは、インタフェース変数の動的な型を見つけるために用いることもできます。その型switchには、型アサーションの構文を使って丸括弧()の中にキーワード"type"と書きます。switchの式で変数を宣言したとき、その変数は各case節において適切な型となります。

switch t := interfaceValue.(type) {
default:
    fmt.Printf("unexpected type %T", t)  // %T は型を出力する
case bool:
    fmt.Printf("boolean %t\n", t)
case int:
    fmt.Printf("integer %d\n", t)
case *bool:
    fmt.Printf("pointer to boolean %t\n", *t)
case *int:
    fmt.Printf("pointer to integer %d\n", *t)
}

Go organizes programs into individual pieces called packages. A package gets to pick a short name for itself, like vector, even if the import statement must use a longer path like "container/vector" to name the file where the compiled code is installed. The early Go compilers used the package name as a unique identifier during linking, so that vector's New function could be distinguished from list's New. In the final binary, one was vector.New and the other list.New. As we started to fill out the standard library, it became clear that we needed to do something about managing the package name space: if multiple packages tried to be package vector, their symbols would collide in the linker. For a while we considered segmenting the name space, reserving lower-case names for standard packages and upper-case names for local packages. (Since package names and object file names are conventionally the same, one reason not to do this is that it would require a case-sensitive file system.)

Other languages simply use longer names. Both Java and Python tie the name to the directory in which the package is found, as in com.java.google.WebServer for the code in com/java/google/WebServer.class. In practice this leads to unnecessarily long identifiers, something Go tries to avoid. It also ties the name to a particular mechanism for finding code: a file system. One of the reasons that import paths are string constants in Go is so that it is easy to substitute other notations, like URLs.

Last spring, during a long discussion about how to divide up the package name space, Robert Griesemer cut the Gordian knot by suggesting that we allow multiple packages to choose a single name and fix the tool chain to cope. The import statement already allows introducing a local alias for the package during the import, so there's no linguistic reason package names have to be unique. We all agreed that this was the right approach, but we weren't sure how to implement it. Other considerations, like the open source release, took priority during most of 2009, but we recently returned to the problem.

Ultimately, the linker needs some unique name for each symbol in the program; the fundamental problem caused by deciding that package names won't be unique is to find another source of uniqueness that fits into the tool chain well.

The best approach* seems to be to use the package's import path as the unique identifier, since it must uniquely identify the package in the import statement already. Then container/vector's New is container/vector.New. But! When you're compiling a package, how does the compiler know what the package's import path will be? The package statement just says vector, and while every compilation that imports "container/vector" knows the import path, the compilation of vector itself does not, because compilation is handled separately from installing the binary in its final, importable location.

Last week I changed the gc compiler suite to do this. My solution to the import path question was to introduce a special name syntax that refers to “this package's import path.” Because the import paths are string literals in the Go compiler metadata, I chose the empty string—""—as the self-reference name. Thus, in the object file for package vector, the local symbol New is written "".New. When the linker reads the object file, it knows what import path it used to find the file. It substitutes that path for the "", producing, in this case, the unique name container/vector.New.

Not embedding a package's final installed location in its object file makes the object files easy to move and duplicate. For example, consider this trivial package:

package seq
var n int
func Next() int {
    n++
    return n
}

It's valid for a Go program to import the same path multiple times using different local names, but all the names end up referring to the same package:

package main

import (
    "fmt"
    s "seq" // changed to "seq1" later
    t "seq"
)

func main() {
    fmt.Println(s.Next(), s.Next(), t.Next(), t.Next())
}

prints 1 2 3 4, because it all four calls are to the same Next function:

$ 6g seq.go
$ 6g -I. main.go
$ 6l -L. main.6
$ 6.out
1 2 3 4
$ 

But if we change one of the imports to say "seq1" and then merely copy the "seq" binary to "seq1", we've created a distinct package, using lowly cp instead of a compiler:

$ cp seq.6 seq1.6
$ ed main.go
120
/seq
 s "seq"
s/seq/seq1
 s "seq1"
wq
121
$ 6g -I. main.go
$ 6l -L. main.6
$ 6.out
1 2 1 2
$ 

Now the s.Next calls refer to seq1.6's Next, while the t.Next calls refer to seq.6's Next. Duplicating the object actually duplicated the code. This is very different from the behavior of a traditional C compiler and linker.

A digression: the explicit "". prefix is not strictly necessary. It would be cleaner if the linker treated every symbol as needing to be qualified by the import path, so that all the "". could be dropped. But occasionally it's important to be able to break the rules, for example to define a symbol that is logically in one package be implemented in another. For example, the implementation of unsafe.Reflect is actually in the binary for package runtime, because that's where all the interface manipulation code lives:

$ 6nm pkg/darwin_amd64/runtime.a|grep Reflect
iface.6: T unsafe.Reflect
$

Another reason to use an explicit prefix is to admit names with no prefix at all, as would be generated by legacy C code. Otherwise, what should C's printf be in? If the linker enforced a strict boundary between packages, both of these examples would be impossible. Most of the time that would be a good thing, but systems languages do not have the luxury of stopping at “most of the time.” Last October, a few weeks before the public release of Go, I changed the linker to insert import path qualifiers on all names during linking, but it was too disruptive a change to commit before the release. Last week's implementation, which allows for semipermeable package boundaries, is a much better fit for Go.

This week Ian Lance Taylor is working on eliminating the global package name space assumption in gccgo. He'd like to avoid making changes to the linker, which rules out introducing a “this package” notation like "". Gccgo must be able to write objects that know their own import paths, which means gccgo must know the import path at compile time. But how? There will be a new gccgo command line option, and the build system will simply tell the compiler what the import path is.

In retrospect, I wonder if the effort of "" in the gc tool chain was justified compared to adding an option. The gc implementation is easier to use, but it's not clear how important that will be. Time will tell.

* An alternative approach would be to generate a random identifier each time the compiler is invoked and to use it for the package compiled by that run. When other packages import the compiled package, they can read the identifier and use it to generate references to that package's symbols. The most glaring problem with this approach is that the symbol names you'd see while debugging would be ugly, like mangled C++ names but worse. Another problem is that it would break aggressive incremental compilation: if fmt gets recompiled, all packages that import it would have to be recompiled to pick up the new identifier, even if the external interface hadn't changed. It would be nice to avoid those recompilations, especially in large programs.

Coincidentally, I saw the movies The Road and The Book of Eli just a few days apart. They are two different and yet oddly similar visions of what the world will look like after civilization collapses. Men will be predators. Women will suffer. Roads will be left covered with cars. Cannibalism will rise. People will dress in mismatched clothing and gather canned food.

The Road is a far better movie. It is also very sad, which seems a not inappropriate response to the fall of civilization. The Book of Eli has a couple of major story flaws. It also has a character who is obviously under the care of a skilled post-civilization beauty salon that they somehow omitted to mention in the story, a jarring presence in the otherwise apocalyptic landscape. Still, I enjoyed both films.

The zombie film has become a way of metaphorically imagining our fears, which is also what we see in a film like 2012: this is the way the world could end. That doesn’t describe these post apocalypse films, in which the collapse of civilization is only alluded to very briefly and is not shown at all. What are these films about? They both seem to be trying to say something rather than just be a generic action movie.

Both films wind up being about faith. The Road is about faith in humanity, a faith which the protagonist has lost. The Book of Eli, as the name suggests, is about faith in God, a faith which the protagonist has but everybody else has lost. The films are about what you can believe in, who you can trust, after society has fallen apart.

Tying this idea back to my own bête noire, perhaps these films are trying to investigate faith without society because we are lacking faith in society. When you don’t believe in civilization, it seems reasonable to write a story in which there is no civilization, and you explore what you actually do believe in. Of course I’m overthinking this, driven by the coincidence of two such similar movies arriving in the theaters at close to the same time. I doubt there will be another serious post-apocalypse films for several years.

The metaphorical nature of these films is clear when you consider what a collapse of civilization would really be like. It would be nothing like what these films portray. We’ve seen Dark Ages before, and we may again. People didn’t wear mismatched clothing.

I can’t close a post about The Book of Eli without mentioning that it clearly draws on the beginning of The Canticle of Liebowitz, a still-excellent post-apocalypse SF novel.

The Setup is a neat site. They find (somewhat) famous techie people and interview them about what hardware and software they use. I was browsing through it because I recognised some of the names, and because it's always neat to find out about tools that you don't use.

But it struck me how many people were using OS X as their primary, day to day, operating system. So I went through every one of them and added up the numbers (except Why the Lucky Stiff, because they put an underscore at the start of the domain name; stopping it from resolving).

Windows: 3.5, Linux: 3, Mac: 29.5

These folks aren't all hardcore coders to be sure, but one of the Linux users is RMS and I'm not sure he counts! It would be like asking Steve Jobs what he uses.

But gosh, that's a total OS X domination.

Lawrence Lessig is pushing for a constitutional amendment to change the campaign financing system. You can sign his petition over at http://action.change-congress.org/amendment.

I think Lessig is right that campaign financing is broken. Elections for national office are very expensive. Politicians spend a lot of their time fund-raising. Jesse Unruh was probably reasonably accurate when he said, about lobbyists, “If you can’t eat their food, drink their booze, screw their women and still vote against them, you have no business being up here” (apologies for the sexism, I’m just quoting). And of course many politicians raise most of their money from small donations. But many do not, and of those who do not, they are far more likely to be elected in the first place if they hold views which are congenial to people who are willing to spend a lot of money on politicians. That increasingly means corporations rather than individuals. That leads to a increasing focus of government on the needs of the wealthy rather than on the needs of the general population. And that leads to an increasing distrust and dislike of government by the general population. And that doesn’t do anybody any good, regardless of one’s political position.

I also think that Lessig is right that the only way to fix campaign financing is a constitutional amendment. The Supreme Court was willing to overturn a hundred years of precedent in their recent decision permitting unlimited corporate speech. Clearly ordinary laws are insufficient. And while the amendment process is obviously very heavyweight, the constitution does after all provide a right of free speech, and campaign financing laws are indeed a limitation on speech; an amendment does not seem inappropriate.

Unfortunately, a constitutional amendment must be voted in by politicians. They would basically be voting away their present support and their future income (many politicians retire to become lobbyists themselves). Passing such an amendment would require overwhelming popular support, and I’m skeptical that that will happen.

One of the great religious debates in compiler writing is whether you should use parser generators like yacc and its many descendants or write parsers by hand, usually using recursive descent. On the one hand, using parser generators means you have a precise definition of the language that you are parsing, and a program does most of the grunt work for you. On the other hand, the proponents of hand-written recursive descent parsers argue that parser generators are overkill, that parsers are easy enough to write by hand, and that the result is easier to understand, more efficient, and can give better error messages when presented with syntactically invalid programs.

Like in most religious debates, the choice of side seems to be determined by familiarity more than anything else. I knew how to use yacc before I knew how to write a parser by hand, which put me solidly on the parser generator side of the fence. Now that I do know how to apply both techniques, I'd still rather use a parser generator. In fact, I've worked on projects where I've written parser generators rather than write a parser by hand. Good notation counts for a lot, as we shall see.

In Coders at Work, Ken Thompson talks to Peter Seibel about yacc and lex:

Seibel: And are there development tools that just make you happy to program?

Thompson: I love yacc. I just love yacc. It just does exactly what you want done. Its complement, lex, is horrible. It does nothing you want done.

Seibel: Do you use it anyway or do you write your lexers by hand?

Thompson: I write my lexers by hand. Much easier.

Many of the objections raised by the hand-written parser camp are similar to Thompson's objection to lex—the tool doesn't do what you want—but there's no fundamental reason a tool can't. For example, the spurious conflicts that an LALR(1) algorithm produces are definitely hard to understand, but if you replace it with LR(1) or GLR(1), you get a more useful tool. And if you do learn how to work within the LALR(1) algorithm, even yacc is very powerful.

The objection to parser generates that seems to resonate most is that generators like yacc produce inadequate error messages, little more than “syntax error.” Better error messages were one of the key benefits hoped for when g++ converted from a yacc-based C++ parser to a hand-written one (and to be fair, C++ syntax is nearly impossible to parse with any tool; the many special cases cry out for hand-written code). Here the objection seems harder to work around: the parser internally gets compiled into an automaton—usually a big table of numbers—that moves from state to state as it processes input tokens. If at some point it can't find a next state to go to, it reports an error. How could you possibly turn that into a good message?

Clinton Jeffery showed how in a paper published in ACM TOPLAS in 2003 titled “Generating LR Syntax Error Messages from Examples.” As you can guess from the title, the idea is to introduce a training stage after the parser is generated but before it is used for real. In that stage, you feed examples of syntax errors into the parser and look at what state it ends up in when it detects the error, and maybe also what the next input token is. If the automaton hits an error in that state (and with that input token) during real use, you can issue the message appropriate to the example. The important part is that the parser states are basically an abstract summary of the surrounding context, so it's reasonable to treat errors in a particular state with a single message. For example, suppose you find that this Go program

package main

import (
 "fmt",
 "math"
)

causes a syntax error at the comma, in state 76. In the parser, that state means that you're in the middle of an import block and expecting to see a string constant. The state abstracts that context, so you'd end up in the same state if you were parsing this erroneous program:

package fmt

import ( "strings"; "testing", "xgb" )

Having told the parser that the appropriate error message for the first program is “unexpected , during import block,” the parser will use the same message for the second program.

It's an elegant idea, and the implementation can be kept on the side, without adding any complexity to the grammar itself. I heard about this idea through the grapevine years ago (in 2000, I think) but had never gotten a chance to try it until this week.

There are three Go parsers: Ian Lance Taylor wrote a hand-written recursive descent parser in C++ for gccgo, Robert Griesemer wrote a hand-written recursive descent parser in Go (import "go/parser") for godoc and gofmt, and Ken Thompson wrote a yacc-based parser in C for the gc compiler suite.

On Monday night, I implemented Jeffery's idea in the gc compiler suite. The gc compilers use bison, the GNU implementation of yacc. Bison doesn't support this kind of error management natively, but it is not hard to adapt. Changing bison would require distributing a new version of bison; instead, my implementation post-processes bison's output.

The examples are in a new file go.errors. Because the lexer is written by hand, it's not available in the simulation, so the examples are token name sequences rather than actual program fragments. In token lists, the program above and its corresponding error message are:

% loadsys package LIMPORT '(' LLITERAL import_package import_there ','
"unexpected , during import block",

Understanding the tokens on the first line requires knowing what the various grammar token names mean, but they basically mimic the syntax, and this tool is targeted at the people working on the grammar anyway. An awk program loads bison's tables from its debugging dump y.output and then processes the go.errors file, replacing each line like the above with the number of the offending state and input token. That produces a table that can be linked into the compiler and consulted when a syntax error is encountered. If the state and input token match an entry in the table, the better error is used instead of a plain syntax error.

That was an outsized amount of work to close one bug, but now it's easy to add better messages for other common situations. For example, the fact that only the short := declaration form is allowed in for initializers sometimes trips up new Go programmers. When presented with this program:

package main

import "fmt"

func main() {
 fmt.Printf("hello, world\n")
 for var i = 0; i < 10; i++ {
  fmt.Println(i)
 }
}

the compiler used to just say there was a syntax error on line 7, but now it explains:

$ 6g x.go
x.go:7: syntax error: var declaration not allowed in for initializer

because of this stanza in go.errors:

% loadsys package imports LFUNC LNAME '(' ')' '{' LFOR LVAR LNAME '=' LNAME
"var declaration not allowed in for initializer",

Gccgo and gofmt give more traditional token-based errors:

$ gccgo x.go
x.go:7:6: error: expected operand
...

$ gofmt x.go
x.go:7:6: expected operand, found 'var'

What's interesting isn't that neither has bothered to handle this as a special case yet. What's interesting is to consider the work required to do so. Changing either would require understanding the corresponding hand-written parser well enough to find the right place to put the special case. With the example-based approach, you just write an example, and the tool figures out where in the parser it needs to go.

All Go code lives in a package. Every Go source file starts with a package declaration which names the package that it lives in. A package name is a simple identifier; besides appearing in a package clause, package names are also used when referring to names imported from another package. That poses the problem of what to do when one program links together two different packages which use the same package name. We can’t expect the author of a large program to be aware of every package that the program uses. However, since Go compiles straight to object files, it’s natural to use the package name in the generated symbol names. How can we avoid multiple definition errors?

The gc compiler comes with its own Go specific linker. That linker now supports automatic symbol renaming at link time based on the name used to import the package. That name is presumed to be unique. This means that all imports of the same package must use the same name to import it; otherwise you might get multiple definitions of a global variable in the package. In the future there may be some need to adjust packages which are distributed without their source code, to ensure that they don’t accidentally alias locally compiled package names.

For the gccgo compiler I have so far avoided using a specific linker, or rather linker wrapper. For large programs gccgo now requires a new option, -fgo-prefix=PREFIX to be used when compiling a package. The PREFIX should be a string unique to that package; for example, in a typical installation, it could be the directory where the package is installed. This gives a unique name used in the compiled code. If the -fgo-prefix option is not used, everything will still work as long as there are not, in fact, two packages with the same name.

I spent this week attending and speaking at two different conferences - the Stack Overflow Dev Day in Amsterdam, and Øredev, in Malmö, Sweden.

Stack Overflow was a lot of fun. Talks covered topics such as FogBugz, jQuery, Fog Creek Software, creators of FogBugz, QT (pronounced 'cute'), FogBugz, Python, App Engine (my own talk), Yahoo! developer tools, and, of course, FogBugz.

Particular highlights for me were Simon Willison's talk about Python, and Christian Heilmann's talk on Yahoo! developer tools. Simon works at The Guardian, a UK newspaper that is particularly keen on exposing and consuming data and APIs, and used his hour to introduce Python by demonstrating how he uses it, particularly the interactive interpreter, on a day to day basis to extract and munge statistical data and produce content for news stories, such as infographics. Although I know Python very well, his presentation style was extremely engaging, and I had to restrain myself from going up to him and asking if he was looking for apprentices in the fine art of presenting. He's also a co-author of Django, so he showed off some of Django's features in his talk as well.

Christian's talk was completely without script, notes, or slides: He simply got up on stage and spent an hour with his laptop showing off what you can do with Yahoo!'s developer tools, including in particular YUI, Yahoo's JavaScript UI library, and YQL, Yahoo!'s general-purpose query language. The general crowd sentiment, which I shared, is that Yahoo! has some pretty awesome developer content out there, that Christian did an excellent job showing it off, and that Yahoo! seriously needs to get better about publicizing this.

After returning to Dublin on Monday night, I headed straight back out to Øredev on Tuesday morning. My own talk went reasonably well, although it was marred by demo problems. An impromptu Cloud Computing panel in the afternoon also went well, although it was poorly attended due to the short notice, so very few people attended. In the evening, they ran unconference-style "Birds of a Feather" sessions. I joined one on the subject "Spatial Indexing", and the 15 or so of us that attended spent a fascinating couple of hours discussing spatial indexing techniques and how to apply them. More, in fact, on that in a later post.

Øredev was (I should say 'is', since it continues today) absolutely packed with interesting talks. I didn't get an opportunity to attend many of them, alas, but Ola Bini gave a fascinating talk on Ioke, a language of his own creation. It's implemented on the JRE, so it even runs on App Engine, too. The evening keynote was by Cameron Purdy, who gave an interesting talk comparing and contrasting C++, Java and .NET. It's always interesting to hear from people who are polyglot and comfortable with it: objective assessment was in abundance, while the sort of idealizing you sometimes hear from "Java developers" and ".NET developers" was conspicuously absent.

On Thursday, Andres Almiray gave an engaging introduction to Groovy, including slides with interactively editable, executable code to demonstrate it. The presentation package is, apparrently, of his own creation - implemented in Groovy, naturally.

There were many more talks that looked really interesting but I didn't get a chance to attend, alas. All of the talks were videoed, and will be available online shortly; I'll link to the ones I mentioned above, and others that were of particular interest, when they become available.

For now, I'm spending my time recovering, catching up on email, preparing for .astronomy, and eating some of the Stroopwafel I brought back from the Netherlands. Expect regular posting to resume on Monday. :)

Last Thursday night at Oredev, after the sessions, was "Birds of a Feather" - a sort of mini-unconference. Anyone could write up a topic on the whiteboard; interested individuals added their names, and each group got allocated a room to chat about the topic. I joined the "Spatial Indexing" group, and we spent a fascinating hour and a half talking about spatial indexing methods, reminding me of several interesting algorithms and techniques.

Spatial indexing is increasingly important as more and more data and applications are geospatially-enabled. Efficiently querying geospatial data, however, is a considerable challenge: because the data is two-dimensional (or sometimes, more), you can't use standard indexing techniques to query on position. Spatial indexes solve this through a variety of techniques. In this post, we'll cover several - quadtrees, geohashes (not to be confused with geohashing), and space-filling curves - and reveal how they're all interrelated.

Quadtrees

Quadtrees are a very straightforward spatial indexing technique. In a Quadtree, each node represents a bounding box covering some part of the space being indexed, with the root node covering the entire area. Each node is either a leaf node - in which case it contains one or more indexed points, and no children, or it is an internal node, in which case it has exactly four children, one for each quadrant obtained by dividing the area covered in half along both axes - hence the name.

A representation of how a quadtree divides an indexed area. Source: Wikipedia

Inserting data into a quadtree is simple: Starting at the root, determine which quadrant your point occupies. Recurse to that node and repeat, until you find a leaf node. Then, add your point to that node's list of points. If the list exceeds some pre-determined maximum number of elements, split the node, and move the points into the correct subnodes.

A representation of how a quadtree is structured internally.

To query a quadtree, starting at the root, examine each child node, and check if it intersects the area being queried for. If it does, recurse into that child node. Whenever you encounter a leaf node, examine each entry to see if it intersects with the query area, and return it if it does.

Note that a quadtree is very regular - it is, in fact, a trie, since the values of the tree nodes do not depend on the data being inserted. A consequence of this is that we can uniquely number our nodes in a straightforward manner: Simply number each quadrant in binary (00 for the top left, 10 for the top right, and so forth), and the number for a node is the concatenation of the quadrant numbers for each of its ancestors, starting at the root. Using this system, the bottom right node in the sample image would be numbered 11 01.

If we define a maximum depth for our tree, then, we can calculate a point's node number without reference to the tree - simply normalize the node's coordinates to an appropriate integer range (for example, 32 bits each), and then interleave the bits from the x and y coordinates -each pair of bits specifies a quadrant in the hypothetical quadtree.

Geohashes

This system might seem familiar: it's a geohash! At this point, you can actually throw out the quadtree itself - the node number, or geohash, contains all the information we need about its location in the tree. Each leaf node in a full-height tree is a complete geohash, and each internal node is represented by the range from its smallest leaf node to its largest one. Thus, you can efficiently locate all the points under any internal node by indexing on the geohash by performing a query for everything within the numeric range covered by the desired node.

Querying once we've thrown away the tree itself becomes a little more complex. Instead of refining our search set recursively, we need to construct a search set ahead of time. First, find the smallest prefix (or quadtree node) that completely covers the query area. In the worst case, this may be substantially larger than the actual query area - for example, a small shape in the center of the indexed area that intersects all four quadrants would require selecting the root node for this step.

The aim, now, is to construct a set of prefixes that completely covers the query region, while including as little area outside the region as possible. If we had no other constraints, we could simply select the set of leaf nodes that intersect the query area - but that would result in a lot of queries. Another constraint, then, is that we want to minimise the number of distinct ranges we have to query for.

One approach to doing this is to start by setting a maximum number of ranges we're willing to have. Construct a set of ranges, initially populated with the prefix we identified earlier. Pick the node in the set that can be subdivided without exceeding the maximum range count and will remove the most unwanted area from the query region. Repeat this until there are no ranges in the set that can be further subdivided. Finally, examine the resulting set, and join any adjacent ranges, if possible. The diagram below demonstrates how this works for a query on a circular area with a limit of 5 query ranges.

How a query for a region is broken into a series of geohash prefixes/ranges.

This approach works well, and it allows us to avoid the need to do recursive lookups - the set of range lookups we do execute can all be done in parallel. Since each lookup can be expected to require a disk seek, parallelizing our queries allows us to substantially cut down the time required to return the results.

Still, we can do better. You may notice that all the areas we need to query in the above diagram are adjacent, yet we can only merge two of them (the two in the bottom right of the selected area) into a single range query, requiring us to do 4 separate queries. This is due in part to the order that our geohashing approach 'visits' subregions, working left to right, then top to bottom in each quad. The discontinuity as we go from top right to bottom left quad results in us having to split up some ranges that we could otherwise make contiguous. If we were to visit regions in a different order, perhaps we could minimise or eliminate these discontinuities, resulting in more areas that can be treated as adjacent and fetched with a single query. With an improvement in efficiency like that, we could do fewer queries for the same area covered, or conversely, the same number of queries, but including less extraneous area.

Illustrates the order in which the geohashing approach 'visits' each quad.

Hilbert Curves

Suppose instead, we visit regions in a 'U' shape. Within each quad, of course, we also visit subquads in the same 'U' shape, but aligned so as to match up with neighbouring quads. If we organise the orientation of these 'U's correctly, we can completely eliminate any discontinuities, and visit the entire area at whatever resolution we choose continuously, fully exploring each region before moving on to the next. Not only does this eliminate discontinuities, but it also improves the overall locality. The pattern we get if we do this may look familiar - it's a Hilbert Curve.

Hilbert Curves are part of a class of one-dimensional fractals known as space-filling curves, so named because they are one dimensional lines that nevertheless fill all available space in a fixed area. They're fairly well known, in part thanks to XKCD's use of them for a map of the internet. As you can see, they're also of use for spatial indexing, since they exhibit exactly the locality and continuity required. For example, if we take another look at the example we used for finding the set of queries required to encompass a circle above, we find that we can reduce the number of queries by one: the small region in the lower left is now contiguous with the region to its right, and whilst the two regions at the bottom are no longer contiguous with each other, the rightmost one is now contiguous with the large area in the upper right.

Illustrates the order in which a hilbert curve 'visits' each quad.

One thing that our elegant new system is lacking, so far, is a way of converting between a pair of (x,y) coordinates and the corresponding position in the hilbert curve. With geohashing it was easy and obvious - just interleave the x and y coordinates - but there's no obvious way to modify that for a hilbert curve. Searching the internet, you're likely to come across many descriptions of how hilbert curves are drawn, but few if any descriptions of how to find the position of an arbitrary point. To figure this out, we need to take a closer look at how the hilbert cure can be recursively constructed.

The first thing to observe is that although most references to hilbert curves focus on how to draw the curve, this is a distraction from the essential property of the curve, and its importance to us: It's an ordering for points on a plane. If we express a hilbert curve in terms of this ordering, drawing the curve itself becomes trivial - simply a matter of connecting the dots. Forget about how to connect adjacent sub-curves, and instead focus on how we can recursively enumerate the points.

Hilbert curves are all about ordering a set of points on a 2d plane

At the root level, enumerating the points is simple: Pick a direction and a start point, and proceed around the four quadrants, numbering them 0 to 3. The difficulty is introduced when we want to determine the order we visit the sub-quadrants in while maintaining the overall adjacency property. Examination reveals that each of the sub-quadrants' curves is a simple transformation of the original curve: there are only four possible transformations. Naturally, this applies recursively to sub-sub quadrants, and so forth. The curve we use for a given quadrant is determined by the curve we used for the square it's in, and the quadrant's position. With a little work, we can construct a table that encapsulates this:

Suppose we want to use this table to determine the position of a point on a third-level hilbert curve. For the sake of this example, assume our point has coordinates (5,2) Starting with the first square on the diagram, find the quadrant your point is in - in this case, it's the upper right quadrant. The first part of our hilbert curve position, then, is 3 (11 in binary). Next, we consult the square shown in the inset of square 3 - in this case, it's the second square. Repeat the process: which sub-quadrant does our point fall into? Here, it's the lower left one, meaning the next part of our position is 1, and the square we should consult next is the second one again. Repeating the process one final time, we find our point falls in the upper right sub-sub-quadrant, our final coordinate is 3 (11 in binary). Stringing them together, we now know the position of our point on the curve is 110111 binary, or 55.

Let's be a little more methodical, and write methods to convert between x,y coordinates and hilbert curve positions. First, we need to express our diagram above in terms a computer can understand:

In the snippet above, each element of 'hilbert_map' corresponds to one of the four squares in the diagram above. To make things easier to follow, I've identified each one with a letter - 'a' is the first square, 'b' the second, and so forth. The value for each square is a dict, mapping x and y coordinates for the (sub-)quadrant to the position along the line (the first part of the value tuple) and the square to use next (the second part of the value tuple). Here's how we can use this to translate x and y coordinates into a hilbert curve position:

The input to this function is the integer x and y coordinates, and the order of the curve. An order 1 curve fills a 2x2 grid, an order 2 curve fills a 4x4 grid, and so forth. Our x and y coordinates, then, should be normalized to a range of 0 to 2^order-1. The function works by stepping over each bit of the x and y coordinates, starting with the most significant. For each, it determines which (sub-)quadrant the coordinate lies in, by testing the corresponding bit, then fetches the position along the line and the next square to use from the table we defined earlier. The curve position is set as the least significant 2 bits on the position variable, and at the beginning of the next loop, it's left-shifted to make room for the next set of coordinates.

Let's check that we've written the function correctly by running our example from above through it:

Presto! For a further test, we can use the function to generate a complete list of ordered points for a hilbert curve, then use a spreadsheet to graph them and see if we get a hilbert curve. Enter the following expression into an interactive Python interpreter:

Take the resulting text, paste it into a file called 'hilbert.csv', open it in your favorite spreadsheet, and instruct it to generate a scatter plot. The result is, of course, a nicely plotted hilbert curve!

The inverse of point_to_hilbert is a straightforward reversal of the hilbert_map; implementing it is left as an exercise for the reader.

Conclusion

There you have it - spatial indexing, from quadtrees to geohashes to hilbert curves. One final observation: If you express the ordered sequence of x,y coordinates required to draw a hilbert curve in binary, do you notice anything interesting about the ordering? Does it remind you of anything?

Just to wrap up, a caveat: All of the indexing methods I've described today are only well-suited to indexing points. If you want to index lines, polylines, or polygons, you're probably out of luck with these methods - and so far as I'm aware, the only known algorithm for effectively indexing shapes is the R-tree, an entirely different and more complex beast.

I'm going to be spending the next week going to conferences. As a result, your regularly scheduled posts are likely to be absent next week; it's going to be hectic enough as it is. In the meantime, here's my talk schedule for the next while.

November 2: Presenting on App Engine Python at Stack Overflow Dev Day Amsterdam.
November 4: Presenting on App Engine Java at Øredev in Malmo, Sweden.
November 18: Python Ireland talk on App Engine at Scruffy Murphy's, Dublin, Ireland.
November 30 - December 4: At .Astronomy 2009 in Leiden, Netherlands, helping people put together Astronomy apps on App Engine
January 24 - January 30: LovelySnow Sprint in the Austrian Alps, another App Engine hackathon.

A lot of App Engine developers are fairly new to Python as well, and so probably haven't encountered a few subtle 'gotchas' about the Python programming language. This post aims to sum up the ones you're most likely to encounter while programming for App Engine.

Mutable default arguments

First up is something every Pythonista learns sooner or later. What's wrong with this snippet?

Well, what do we see if we run it more than once?

That was weird. What's happening here is fairly straightforward, once you're familiar with how Python handles function definitions and default arguments. At the time Python encounters our 'append' function definition, it evaluates it. This includes evaluating the default argument, which in our case is an empty list. But - and this is important - the evaluation of that default argument takes place when the function is evaluated, not when it's executed, meaning the same list gets used repeatedly. Because lists are mutable types, and our function modifies the value of l before returning it, we end up mutating it with each function call. It's effectively the same as doing this:

The solution to this is to use an immutable placeholder value - usually None - as the default argument, and initialize the list inside our function:

Recursive imports

When you import a module for the first time, Python creates a new global scope, and executes the code of the module inside it, then assigns that global scope to the name you just imported the module as. If the module you're importing itself has other modules, Python performs the same process for them, and so forth. On subsequent imports of a module, Python simply looks up the module in its internal list of loaded modules, and returns the existing scope.

Where this becomes a problem is if you have a module, a, which imports another module, b, which in turn attempts to import a - in other words, recursive imports. When something imports a, it's executed, causing the import of b. b executes, but when it reaches the 'import a' statement, Python throws an exception - it can't execute a again without creating an infinite loop, and it can't return the a it's currently importing, because it's not finished yet.

This doesn't come up that often, because dependencies usually don't form cycles. But if you're developing a fairly tightly coupled system, you may well encounter this at some point. Sometimes, it's a sign you need to refactor your placement of code in modules to eliminate the loops, but that's not always possible. For example, in part 3 of the Blogging on App Engine series we encountered exactly this problem, with the generators module importing the models module, and vice-versa.

The workaround is simple, but surprising to people used to compiled languages. Suppose we have the following in a.py:

And the following in b.py:

The solution is to modify one module - whichever is convenient - to move the 'import' statement inside the functions that need to reference the other module. For example, supposing we decide to modify b.py:

This works because at the time b.py is executed, the code in the 'uses_a' function is parsed, but not executed. By the time uses_a() is executed, both modules should have finished importing, so Python can resolve the 'import a' statement inside the function by simply fetching the already-imported module.

Edit: In my original version of this post, I had an example that looked like a recursive import, but wasn't. Python is smarter than me, and only throws an exception if you try to call a function in a recursively imported module where the function hasn't been parsed yet. I updated the example above to demonstrate this.

Iterating over query objects

Now to something App Engine specific. A common mistake - so common it's even shown up in the docs once or twice by accident - is to do something like the following:

The overall pattern here is a good one: Updating a set of entities, then using a batch put to store them back to the datastore in a single operation. It's much more efficient than saving them all individually. The code above, however, does absolutely nothing: No records will be updated. To see why, we need to take a closer look at what happens.

The object returned by the expression "Entity.all().filter('foo =', bar)" is a Query object. Query objects expose several methods to refine the query, but they also act as iterables, meaning you can fetch an iterator from them to iterate over the results of the query. The db.put() function also accepts an iterable, and fetches all its elements, storing the results to the datastore.

What happens here, then is that our 'for' loop gets an iterator object from q and executes its body for each entity returned. Then, db.put also fetches an iterator from q - a new iterator, which executes the query a second time, returning the original, unmodified entities, which db.put happily stores back to the datastore. Not only does this code do nothing, but it does it inefficiently!

The solution is a very small change to our code:

All we've done here is to switch from using the Query object's iterator protocol to fetching results explicitly. The .fetch() method returns a list of Entity objects. The for loop iterates over them, updating them, and then db.put() takes the same list, containing the entities we already modified, and stores them in the datastore. Since we're operating on the same list of entities in each step, everything works as expected.

Reserved module names

This is an issue that's come up a lot more since we added incoming email support to App Engine. Certain module names are used by the Python standard library, and attempting to use them yourself will lead to problems. A prominent example is 'email'. If you name your own module 'email.py', one of two things will happen, depending on the order of directories in the search path: Either every use of the 'email' standard library module will instead load your module, or vice-versa. Since people writing incoming email support on App Engine typically need to use the real 'email' module, neither option is a good one. Take care not to reuse module names from the Python standard library - and if in doubt, check the module list for confirmation. One easy way to avoid this gotcha is to put all your own code inside a package - then, you only need to check one name for conflicts.

Global variables and aliasing

Python only has two scopes - global, and local. Global scope is the scope of the module your code is in, while local scope is the scope of the current function or method. Python separates the two fairly strictly: Code in a local scope can read global variables, but can't, by default, modify them. Attempts to modify a global variable will lead to aliasing - creation of a local variable by the same name. For example:

Python provides a way to explicitly state that you want to modify a global inside a local scope: The global keyword. It works like this:

Note, however, that this is generally discouraged: Modifying global variables from within a function is seen as bad practice, and unpythonic. Also, remember that this restriction only prevents modifying the variables themselves, not their contents. For example, modifying a mutable list in the global scope is no problem without a 'global' keyword:

First import of handler modules

To wrap up, we'll cover one final App Engine specific gotcha. The execution model of App Engine Python apps is that the first request to a given request handler module is handled by simply importing the module, cgi-style. Subsequent requests are handled by checking if the module defined a 'main' function. If it did, the main function is executed, instead of re-importing the entire module.

If you want to take advantage of this performance optimisation for requests after the first one, you need to do two things: Define a main() function, and make sure that you call that main function yourself on first import. The second part of this is handled with this bit of boilerplate, which you are probably used to seeing at the bottom of modules:

If you omit this bit of code, however, the first import of your module simply parses anything, then does nothing, returning a blank page to your user. Subsequent requests execute main and generate the page as normal, leading to a frustrating debugging experience. So always remember the two line stanza from above!

Got your own tips, tricks, or gotchas? Leave them in the comments!

API call hooks are a technique that's reasonably well documented for App Engine - there's an article about it - but only lightly used. Today we'll cover some practical uses of API call hooks.

To start, let's define a simple logging handler. This can be useful when you're seeing some odd behaviour from the datastore, especially when you're using a library that may be modifying how it works. You can also use it to log any other API, such as the URLFetch or Task Queue APIs. For this, we just need a post-call hook:

To install this for the datastore, for example, we call this:

The arguments to Append are, in order, a name for the hook, the hook function itself, and, optionally, the service you want to hook. If you leave out the last argument, the hook is installed for all API calls.

Once a hook is installed, it remains installed as long as the runtime is loaded - including across requests, and for requests to different handlers. In order to make sure an API call hook is always available, the handler needs to be installed during the first request to a new runtime. The easiest way to do this is to install the handler at the top level of a module (outside any functions) and import that handler in your request handler module.

This is all very well, but still not particularly interesting. Let's implement something more interesting: A simple multi-tenant system, for apps that want to serve off multiple domains. When writing a multi-tenant app, it's important to segregate data owned by different users - one slip and you could leak data to the wrong domain. Using API hooks makes it possible to automatically modify datastore operations to include the domain the request was made against.

In order to simplify things, we'll encapsulate all this in a generic 'hooking' class:

Note how, in handle_pre_call_hook and handle_post_call_hook, we check to see if the URL starts with '/_ah'. If we don't, our hooks will do their magic even when using the local admin console!

To use this class, we subclass it, defining a set of hook functions, and provide a dict of those hook functions. There's three things we need to hook in order to provide isolation between tenants:

• Add the current domain to any entities being stored.
• Add an equality filter for the current domain to query and count requests.
• Check the domain is correct on any get requests.

A lot of the code here is dedicated to dealing with the structure of the request and response objects, which are Protocol Buffers. You can determine what fields are available and what they do by looking at the compiled Protocol Buffer definitions in the SDK, such as datastore_pb.py and entity_pb.py, or by looking at the definition files. A few copies of these are available online in various third-party projects that interact with App Engine, such as in BDBDatastore.

Entities, when encoded in Protocol Buffers, have their properties stored as a list of key/value pairs, so to get or check values, we have to iterate over all of them, looking for the value we need - hence the loops over properties in the code above. The dict-like and object-like functionality you're used to with the datastore is part of the higher-level API. Other than the boilerplate, the methods above are fairly straightforward, carrying out the three functions we outlined earlier. Note that we can define a single pre_query method for both Query and Count requests, because they both have the same Request object - a Query Protocol Buffer.

Installing this hook is a simple matter of calling the install() method at import time:

Obviously, a complete multi-tenancy library would require a lot more functionality than what we've implemented here - but this is the core functionality, and all in less than 100 lines of code.

One more example: Suppose you're tired of the default URLFetch timeout being 5 seconds, and you want it to be the maximum of 10 seconds. Then you could do something like this:

There are many more uses for API call hooks. They can be used to collect statistics, to perform validation and access checks, to accumulate data for usage-based billing, and to modify other API behaviours. If you have your own ideas on what they could be used for, let us know in the comments.

Hooked yet?

I've only made limited use of the Java runtime for App Engine so far: The two runtimes are largely equivalent in terms of features, and my personal preference is for Python. There are, however, a few really cool things that you can only do on the Java runtime. One of them is embedding an interpreter for a scripting language.

Rhino is a JavaScript interpreter implemented in Java. It supports sandboxing, meaning you can create an environment in which it's safe to execute user-provided code, and it allows you to expose arbitrary Java objects to the JavaScript runtime, meaning you can easily provide interfaces with which the JavaScript code can carry out whatever actions it's designed to carry out.

Rhino also supports several rather cool additional features. You can set callback functions that count the number of operations executed by the JavaScript code, and terminate it if it takes too long, you can serialize a context or individual objects and deserialize them later, and you can even use continuations to pause execution when waiting for data, and pick it up again later - possibly even in another request! Hopefully we'll show off some of these features in future posts.

You may still be wondering how useful server-side JavaScript can be in an App Engine app. Here's a few example use-cases:

• Allow users to provide custom code to be executed when conditions are met in your app.
• A tool for writing straightforward RESTful APIs for text mainpulation etc.
• A programming game, allowing people to submit programs that compete against each other for rankings.
• A CodeWiki, where users can enter code and demonstrate the result of executing it.
• A Google Wave bot that executes code entered in a Wave and adds a response with the result.
• A tool for performing operations over the entire datastore without having to explicitly cater for breaking tasks up into smaller chunks.

That, of course, is just a few ideas - I'm sure you can think of others yourself. Let us know in the comments if you think of anything interesting!

Implementation

Using Rhino is surprisingly simple. Create a new Web Application Project, select App Engine, and unselect GWT. I've called mine 'rhinopark'. Open index.html in the war directory, and replace it with the following:

This is all very straightforward. We provide a textarea for users to enter code in, and a submit button. Instead of a regular form submission, however, we use JQuery to send the code to the /rhinopark URL on the server, and insert the response in the 'output' element.

Next, you need to download Rhino. Extract the file 'js.jar' from the downloaded zip, and copy it to the war/WEB-INF/lib subdirectory of your project. Right-