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 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
}

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.

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.

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.

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.

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!

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.

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.

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.

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.

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.

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-click on your project's entry, and select "Build Path -> Configure Build Path". Then, click on Add JARs..., and select js.jar from the directory you just placed it in.

Then, open the RhinoParkServlet that was created automatically, and replace the body of the class with the following:

This snippet illustrates the basic steps of using Rhino. First, we call Context.enter(). This returns a Context object, which we will need in order to use Rhino, as well as setting the thread's context to the returned object. The rest of the code is wrapped in a try/finally block, to ensure that Context.exit() gets called once we're done.

Next, we call initStandardObjects() on our Context. This creates a Scriptable we can use as a global scope, containing the basic objects that JavaScript scripts expect to find in its environment.

Then, we call evaluateString on the context, passing in the scope we created, the code to execute, a name and line number for the module, and an optional security manager we don't need one, so we leave it as null. This actually executes the code, returning the result. We stringify the result, and write it to the response. If the Javascript has an error, Rhino will throw a RhinoException when we call evaluateString. In that case, we catch the exception and return it in the response instead.

Try it out - start the development server, and go to http://localhost:8080/. Enter a snippet of JavaScript and click 'Submit' to see it evaluated and returned.

Sandboxing

All isn't quite well yet, though. Try entering the following snippet in the console:

Rhino supports a JavaScript feature called LiveConnect, which assists interoperation between Java and JavaScript by making it possible for JavaScript to seamlessly instantiate and use Java classes. Unfortunately, on its own, this constitutes a huge security hole. Rhino makes it easy to patch, however. Create a new class in the project called DenyAllClassShutter, and enter the following:

This class implements the ClassShutter interface from Rhino, which has a single method, visibleToScripts. This method is passed the name of a class or package, and is expected to return a boolean indicating if the class or package in question should be accessible from JavaScript. Since we don't want to permit any LiveConnect functionality in our case, we simply return false always.

To make use of this, we need to make a single modification to RhinoparkServlet:

Try the snippet from above again - it will now return an error.

In a future post, I'll pick up the embedded interpreter theme again, and we'll see what other neat tricks we can play with it on App Engine.

This is part of a series of articles on writing a blogging system on App Engine. An overview of what we're building is here.

Over the last 9 posts, we've covered building a fully functional blogging system for App Engine from scratch, and I've even migrated this blog to it. In the process, we've covered many important components of App Engine, including the new deferred library (and through it, Task Queues), important design principles, such as pre-generation of content, and interesting technologies such as PubSubHubbub, CSEs, Disqus, and sitemaps.

There's also been significant community involvement, for which I am very grateful. Amongst the contributors were:

• Moraes, who ported bloggart to werkzeug, calling it bloggartzeug
• Sylvain, who ported bloggart to tornado, calling it bloggartornado
• andialbrecht, who contributed - and continues to contribute - enhancements and bugfixes for bloggart
• Everyone who contributed a name suggestion on the first post, and everyone who has provided feedback during the series
• Everyone who filed bug reports and feature requests in the issue tracker

To give some sort of objective assessment of how well Bloggart measures up, we need to compare it to our original goals, outlined in the very first post:

Simple authoring.

Achieved. With andialbrecht's recent contribution of support for several additional markup languages, including plain text, ReStructuredText, Markdown and Textile, users can now write in whatever format they prefer.

Good isolation of code and markup.

Mostly achieved Sylvain has pointed out that to some degree the use of Djangoforms runs counter to this, so it can still use a little work.

RSS and Atom support. This should go without saying, these days.

Achieved. We only implemented Atom support, but since everything supports both, these days, I still count this as a success.

PubSubHubbub support.

Achieved.

Sitemap support.

Achieved.

Tagging, and filtering based on tag.

Achieved. This could still use some enhancement, though.

Easily support new output formats.

Achieved with the use of our generator pattern.

Extensible.

Achieved, as evidenced by the volume of contributions from readers!

Easy import of posts from other blogging systems.

Achieved, though we could have spent more time on it.

Multiple author support.

Not achieved - but definitely on the todo list!

Scheduled posts.

Not achieved, though basic support for draft posts is available. Also on the todo list.

Fast. Really, really fast.

Achieved! With typical rendering times sub 50 milliseconds in production, and cold-starts typically below 500ms, we knocked this one out of the park. This could be improved still further with a little care as to what the static module imports.

Where to from here, you may ask? At this point, I believe I've extracted most of the explanatory value from the series. There are still features to be implemented, but many of them make for dull writing and boring reading. Scheduled posts and multiple author support may warrant an article of their own in the future, but for now we're going to take a break from blogging about Bloggart.

This isn't it for Bloggart itself, though. There's nearly 20 issues open in the issue tracker, and since they're mostly feature requests, I consider that a victory. Development - both by myself and by other contributors - will doubtlessly continue, and in the near future I hope we can present the App Engine community with a 1.0 release, ready for deployment by people who don't care to hack on it to get it working!

In the meantime, contributions - feature suggestions, bug reports, and actual code - are more than welcome from all of you. Let me know what you think, and how things could be improved, in the comments, and keep filling out bug reports and sending in patches!

Once again, I'd like to express my gratitude to everyone who's contributed to this series, in ways large and small, and to everyone who's read and commented on it.

In the next post we'll tackle... well, you'll have to wait and see.

Edit: To my shame, I mis-measured the rendering and startup times of Bloggart. I've updated the timings in the list above. The new ones aren't _quite_ as impressive, but they're still good.

It appears I've just inadvertently discovered a bug in Bloggart which causes it to 'republish' old posts, updating the last-modified time and causing them to show up in the Atom feed again. So no, I didn't just get married then stuck in Switzerland.

If I ever track down the author of Bloggart, I'll give him such a hiding he'll wish he'd never written it. ;)

In a previous post, we discussed API call hooks for Python. It's possible to hook and modify RPC calls in Java, too. In this post, we'll demonstrate how.

All API calls in Java are handled by the class com.google.apphosting.api.ApiProxy. This class behaves similarly to the ApiProxyStubMap in the Python SDK, having makeSyncCall and makeAsyncCall functions that take care of invoking the relevant API calls. Unlike the Python runtime, however, all Java API calls are handled by a single delegate class, defined by the interface ApiProxy.Delegate. The active delegate for an App Engine app can be retrieved with ApiProxy.getDelegate, and set with ApiProxy.setDelegate.

Another difference from the Python API is that API calls are serialized into byte arrays before being passed to the ApiProxy, and responses are likewise deserialized by the caller. As a result, the makeSyncCall method takes a byte array as an argument, and returns a byte array.

Because all calls are routed to a single Delegate, the granularity of hooks supported is restricted to hooking all API calls, or none. To make things easier, we'll define a Delegate implementation that dispatches API calls to other Delegate subclasses based on the API being called:

import java.util.HashMap;
import java.util.Map;

import com.google.apphosting.api.ApiProxy;
import com.google.apphosting.api.ApiProxy.ApiProxyException;
import com.google.apphosting.api.ApiProxy.Delegate;
import com.google.apphosting.api.ApiProxy.Environment;
import com.google.apphosting.api.ApiProxy.LogRecord;

public class ApiProxyHook implements Delegate<environment> {
	private Delegate baseDelegate;
	private Map<string> hooks = new HashMap<string>();
	
	public ApiProxyHook(Delegate base) {
		this.baseDelegate = base;
	}
	
	public void log(Environment environment, LogRecord record) {
		this.baseDelegate.log(environment, record);
	}

	public byte[] makeSyncCall(Environment environment, String packageName,
			String methodName, byte[] request) throws ApiProxyException {
		Delegate hook = this.hooks.get(packageName);
		if(hook != null) {
			return hook.makeSyncCall(environment, packageName, methodName, request);
		} else {
			return this.baseDelegate.makeSyncCall(environment, packageName, methodName, request);
		}
	}

	public Delegate getBaseDelegate() {
		return baseDelegate;
	}

	public Map<string> getHooks() {
		return hooks;
	}
}

To install this class, we fetch the existing delegate, pass it to the constructor of our ApiProxyHook class, and set the resulting instance as the new delegate, like this:

ApiProxy.setDelegate(new ApiProxyHook<environment>(ApiProxy.getDelegate();

Typically, you'd execute this code in a static block, or elsewhere in a location that gets executed only once per runtime.

To demonstrate the code in action, let's define a class that implements the multi-tenancy behaviour we demonstrated for Python in the original article:

import com.google.apphosting.api.ApiProxy.ApiProxyException;
import com.google.apphosting.api.ApiProxy.Delegate;
import com.google.apphosting.api.ApiProxy.Environment;
import com.google.apphosting.api.ApiProxy.LogRecord;
import com.google.apphosting.api.DatastorePb.PutRequest;
import com.google.apphosting.api.DatastorePb.GetResponse;
import com.google.apphosting.api.DatastorePb.Query;
import com.google.apphosting.api.DatastorePb.GetResponse.Entity;
import com.google.apphosting.api.DatastorePb.Query.Filter;
import com.google.apphosting.api.DatastorePb.Query.Filter.Operator;
import com.google.storage.onestore.v3.OnestoreEntity.EntityProto;
import com.google.storage.onestore.v3.OnestoreEntity.Property;

public class MultiTenantHook implements Delegate {
	public class InvalidDomainException extends RuntimeException {
	}
	
	private static final String DOMAIN_PROPERTY_NAME = "_domain";

	private Delegate baseDelegate;

	public MultiTenantHook(Delegate base) {
		this.baseDelegate = base;
	}
	
	public void log(Environment arg0, LogRecord arg1) {
	}

	public byte[] makeSyncCall(Environment env, String packageName,
			String methodName, byte[] request) throws ApiProxyException {
		if(methodName.equals("Put")) {
			return this.handlePut(env, request);
		} else if(methodName.equals("Get")) {
			return this.handleGet(env, request);
		} else if(methodName.equals("RunQuery")) {
			return this.handleQuery(env, request);
		} else {
			return this.baseDelegate.makeSyncCall(env, packageName,
					methodName, request);
		}
	}
	
	private String getDomain(Environment env) {
		return (String)env.getAttributes().get("net.notdot.current_domain");
	}
	
	private String getDomainProperty(EntityProto entity) {
		for(Property property : entity.propertys()) {
			if(property.getName().equals(DOMAIN_PROPERTY_NAME)) {
				return property.getValue().getStringValue();
			}
		}
		return null;
	}
	
	private void setDomainProperty(EntityProto entity, String domain) {
		for(Property property : entity.mutablePropertys()) {
			if(property.getName().equals(DOMAIN_PROPERTY_NAME)) {
				property.getMutableValue().setStringValue(domain);
				return;
			}
		}
		
		Property property = entity.addProperty();
		property.setName(DOMAIN_PROPERTY_NAME);
		property.setMultiple(false);
		property.getMutableValue().setStringValue(domain);
	}

	private byte[] handleQuery(Environment env, byte[] requestData) {
		Query query = new Query();
		query.mergeFrom(requestData);
		
		Filter domain_filter = query.addFilter();
		domain_filter.setOp(Operator.EQUAL);
		Property property = domain_filter.addProperty();
		property.setName(DOMAIN_PROPERTY_NAME);
		property.getMutableValue().setStringValue(this.getDomain(env));
		
		return this.baseDelegate.makeSyncCall(env, "datastore_v3", "RunQuery",
				query.toByteArray());
	}

	private byte[] handleGet(Environment env, byte[] requestData) {
		GetResponse response = new GetResponse();
		response.mergeFrom(this.baseDelegate.makeSyncCall(env, "datastore_v3",
				"Get", requestData));
		
		String domain = this.getDomain(env);
		for(Entity e : response.entitys()) {
			EntityProto entity = e.getEntity();
			if(!this.getDomainProperty(entity).equals(domain)) {
				throw new InvalidDomainException();
			}
		}
		
		return response.toByteArray();
	}

	private byte[] handlePut(Environment env, byte[] requestData) {
		PutRequest request = new PutRequest();
		request.mergeFrom(requestData);
		
		String domain = this.getDomain(env);
		for(EntityProto entity : request.mutableEntitys()) {
			this.setDomainProperty(entity, domain);
		}
		
		return this.baseDelegate.makeSyncCall(env, "datastore_v3", "Put",
				request.toByteArray());
	}

}

The code above bears many similarities to the Python example. The Protocol Buffer library behaves very similarly to the Python one, so only syntactic changes are necessary, along with the changes required because of the different hook system.

This code demonstrates another feature of the ApiProxy class - the Environment. Environment is a class that provides some details required by the App Engine environment, such as the current App ID, version, and the credentials of the currently logged in user (if any). It also provides an attribute dictionary, which we're using in the above snippet to retrieve the hostname for the current request - eliminating the need to pass the ServletRequest object to API calls.

There's one further requirement, then: A Filter class to set the 'net.notdot.current_domain' property to the domain the current request was made to. Here's a basic implementation:

import java.io.IOException;

import javax.servlet.Filter;
import javax.servlet.FilterChain;
import javax.servlet.FilterConfig;
import javax.servlet.ServletException;
import javax.servlet.ServletRequest;
import javax.servlet.ServletResponse;

import com.google.apphosting.api.ApiProxy;

public class MultiTenantFilter implements Filter {
	static {
		ApiProxyHook hook = new ApiProxyHook(ApiProxy.getDelegate());
		hook.getHooks().put("datastore_v3", new MultiTenantHook(hook.getBaseDelegate()));
		ApiProxy.setDelegate(hook);
	}

	public void destroy() {
		// TODO Auto-generated method stub

	}

	public void doFilter(ServletRequest request, ServletResponse response,
			FilterChain chain) throws IOException, ServletException {
		ApiProxy.getCurrentEnvironment().getAttributes().put(
				"net.notdot.current_domain", request.getServerName());
		chain.doFilter(request, response);
	}

	public void init(FilterConfig arg0) throws ServletException {
		// TODO Auto-generated method stub

	}

}

Note the static initializer for this class sets up the API stubs as needed. Installing this Filter class for all requests ensures the environment is configured in the way required by our stub, and our Java code can now benefit from the same isolation we previously implemented in Python.

Shiny, and headed my way (hopefully) in time for .astronomy:

Chrome 4 went stable yesterday. One of the many new things in this release is the addition of Strict Transport Security. STS allows a site to request that it always be contacted over HTTPS. So far, only Chrome supports it. However, the popular NoScript Firefox extension also supports it and hopefully support will appear in Firefox proper at some point.

The issue that STS addresses is that users tend to type http:// at best, and omit the scheme entirely most of the time. In the latter case, browsers will insert http:// for them.

However, HTTP is insecure. An attacker can grab that connection, manipulate it and only the most eagle eyed users might notice that it redirected to https://www.bank0famerica.com or some such. From then on, the user is under the control of the attacker, who can intercept passwords etc at will.

An STS enabled server can include the following header in an HTTPS reply:

Strict-Transport-Security: max-age=16070400; includeSubDomains

When the browser sees this, it will remember, for the given number of seconds, that the current domain should only be contacted over HTTPS. In the future, if the user types http:// or omits the scheme, HTTPS is the default. In fact, all requests for URLs in the current domain will be redirected to HTTPS. (So you have to make sure that you can serve them all!).

For more details, see the specification.

There is still a window where a user who has a fresh install, or who wipes out their local state, is vulnerable. Because of that, we'll be starting a "Preloaded STS" list. These domains will be configured for STS out of the box. In the beginning, this will be hardcoded into the binary. As it (hopefully) grows, it can change into a list this is shared across browsers, like the safe-browsing database is today.

If you own a site that you would like to see included in the preloaded STS list, contact me at <script type="text/javascript">document.write('\u0061\u0067\u006c\u0040\u0063\u0068\u0072\u006f\u006d\u0069\u0075\u006d\u002e\u006f\u0072\u0067')</script>.

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. ;)

Now for something really controversial: what’s wrong with protected symbols?

In an ELF shared library, an ordinary global symbol may be overridden if a symbol of the same name is defined in the executable or in a shared library which appears earlier in the runtime search path. This is called symbol interposition. It is often used with functions such as malloc. A shared library can define malloc and it can have code which calls malloc. If the executable linked with the shared library defines malloc itself, then the version in the executable will be used rather than the version in the shared library. This permits the executable to control the memory allocation done by the shared library, perhaps for debugging or logging purposes. In this regard, shared libraries act much as static archives do.

This has a few consequences. One of them is that within a shared library, all references to a global symbol must use the GOT and PLT, to make the overriding possible. That means that all function calls and variable accesses are slightly slower. Also, some compiler optimizations are forbidden: the compiler can not inline a call to a global symbol, since that symbol might be overridden at run time.

When building a shared library, you can provide a version script which indicates that some symbols are actually not global. That can eliminate the GOT and PLT accesses, but it does not permit the compiler optimizations, and you do have to write that version script and keep it up to date.

When compiling code that goes into a shared library, you can set the visibility of symbols. You can use hidden visibility, which means that the symbol is not visible outside the shared library. You can use internal visibility, which is a lot like hidden—I’ll skip the difference here. Or you can use protected visibility. Protected visibility means that the symbol is visible outside of the shared library, and can be accessed as usual. However, all references from within the shared library will use the definition in the shared library. In other words, the symbol acts more or less as usual, but it can not be overridden. This means that accesses to the symbol avoid the GOT and PLT, and it permits compiler optimizations.

So, what’s wrong with them? It turns out that protected symbols are slower at dynamic link time, which means that programs which use the shared library start up slower. This happens because of the C rule that two pointers to the same function must compare as equal. Since protected symbols are globally visible, you can get a pointer to a protected function in the main executable. You can also get a pointer to that same function in the shared library, of course. Those pointers have to be equal, or the C rule will break.

As noted, the access to the function in the shared library will not use the GOT or PLT. The access in the main executable obviously will use the PLT. How can we make those function pointers equal? We can’t. The executable will have a direct reference to the PLT. The shared library will have a direct reference to the function itself. In neither case will there be a relocation for the reference. So there is no way to make the results equal. (This can work for some targets, but not for ones with simple function references like the x86 targets.)

So, I must have lied. The lie was that there is a case where you need to use the GOT for a protected symbol: when compiling position independent code for a shared library, and taking the address of a protected function, you need to use the GOT. Unfortunately, gcc for the x86_64 target, surely the most widely used gcc target today, gets this wrong: http://gcc.gnu.org/PR19520. This generally reveals itself as an error report when you go to create a shared library: relocation R_X86_64_PC32 against protected symbol `NAME' can not be used when making a shared object.

In any case, when the compiler gets it right, the dynamic linker has to fill in that GOT entry. In order to make the function pointers compare as equal, it has to fill in the entry with the address of the PLT in the executable (or the earlier shared library). But remember, this is a protected symbol, and protected symbols don’t support symbol interposition. So the dynamic linker must only use the PLT of the executable if the reference in the executable refers to the definition in the shared library. That means that when the dynamic linker sees a reloc against a protected symbol in a shared library, it has to do another walk through the executable and earlier shared libraries to see if any of them have a definition for the symbol, in which case the GOT entry must not be set to that earlier PLT entry but must instead be set to the address of the symbol in the shared library itself. This check has to be done for every symbol in the shared library.

Those extra symbol resolution passes means a slow down for every program which uses the shared library, and that is what is wrong with protected symbols.

So how do you get the compiler and linker speedups available by avoiding symbol interpositioning? Unfortunately, you have to give your symbols hidden visibility, which means that they can not be accessed from other modules. Assuming you do want them to be accessed, you need to define symbol aliases for the ones which should be publicly visible. That means that you need to use different names for the hidden symbols. This is awkward at best. Unfortunately I have nothing better to offer. ELF is designed to support symbol interpositioning, and there is no very good way to avoid that without causing other consequences.

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

セミコロン

Go言語の文法上、ステートメントの終了にはC言語同様にセミコロンが使われますが、C言語とは異なるのは、それらセミコロンはソース上に現れないことです。その代わりに、lexer(字句解析プログラム)がソースを調べて、ある単純なルールに基づき自動的にセミコロンを付け加えるので、打ち込むコードにはセミコロンがほとんど不要です。

ルールはこうです。改行直前のトークンが識別子(intやfloat64といった単語を含む)、または文字列や数値定数といった基本的なリテラル、または下のトークンのどれかであるときに、lexerはトークンの後ろにセミコロンを付け加えます。

break continue fallthrough return ++ -- ) }

このルールは次のようにまとめられます。「改行文字の直前に、ステートメントの終わりと成りえるトークンがあるときにセミコロンが挿入される。」

また、右波括弧”}”の直前にあるセミコロンも省略可能です。次のようなステートメントではセミコロンはいりません。

    go func() { for { dst <- <-src } }()

Go言語の慣用記法に沿ったプログラムにおいては、セミコロンが記述されるのはforループ節のイニシャライザ、条件、繰り返しの各要素を分割するようなときだけです。ただし一行を複数のステートメントに分割するにはセミコロンが必要なので、このようなコードを記述するときはセミコロンを挿入してください。

注意事項：制御構造(if、for、switch、select)の左波括弧”{“を、その次の行に絶対に置いてはいけません。もし置いてしまうと、括弧の前にセミコロンが挿入され、それによって予期しない影響が起きる可能性があります。よって次のように記述してください。

if i < f() {
    g()
}

下のように書いてはいけません。

if i < f()  // wrong!
{           // wrong!
    g()
}

I’ll read anything which Iain Banks writes, but, frankly, his recent novel Transition was rather weak. I think he was a bit low on the idea bank for this one. This is one of the novels where he sets up surprises, but unfortunately they were not surprising. The ideas which were meant to be challenging and surprising just seemed wrong. The changes to the main character were poorly motivated. The explicit sex, which worked in his novel Complicity because it expanded the characterization, here seemed irrelevant and tossed in just to avoid a talking heads problem.

In a lesser writer, I would think that the ending was setting up a sequel. I sincerely hope that is not the plan here.

Separately, I’ve been reading NESFA’s nice series of collected Zelazny stories. Zelazny has always been one of my favorite SF authors, and it’s refreshing to be reminded of just how good he was. His novels were generally good, of course (avoid the second five Amber novels), but it was in his short stories that he really shone.

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

名前

Go言語において、他の言語同様に名前は重要です。場合によっては、名前そのものが意味を持つことがあります。たとえば名前の頭文字が大文字かどうかで、パッケージの外からの可視性が決まります。Go言語プログラムにおける命名規則の解説に少し時間を割いてみましょう。

パッケージ名

パッケージがインポートされると、パッケージ名はそのパッケージへのアクセッサとなります。次に例を示します。

import "bytes"

このインポートによって、bytes.Bufferにアクセスすることができるようになります。

パッケージの内容を参照する際に、利用者すべてが同一の名前を使ってアクセスできるのであれば、それは有益なことです。それは即ち、パッケージ名が短く簡潔であり、すぐに連想できるような良い名前でなければならないということです。

慣例では、パッケージ名は小文字でひとつの単語です。アンダースコアや大文字が混ざって(mixedCaps)はいけません。

パッケージ使用者がその名前をタイプすることを考慮して、簡潔すぎるぐらいにしてください。名前が重複することを気にする必要はありません。パッケージ名は、単にインポート時にデフォルトとして使われる名前であり、ソースコード全体でユニークである必要はありません。万が一、パッケージのインポート時に重複が起きたときは、別なローカルな名前をつけることができます。いずれにせよ、インポートのファイル名によってどのパッケージが使われるかが決まるので、区別がつかなくなることはまずありません。

もう一つの慣例は、パッケージ名がそのソースディレクトリのベース名であるということです。たとえばsrc/pkg/container/vectorに置かれているパッケージは、"container/vector"としてインポートし、名前はvectorとなります。container_vectorやcontainerVectorとはなりません。

パッケージを利用する側は、そのパッケージの内容へアクセスするためにパッケージ名を使用します。（import .表記を使うとアクセス時にパッケージ名が不要となりますが、これはテストや他の一般的でない状況に使うためのものなので、ここでは無視します。）パッケージ名を使うので、エクスポートされる名前は、同じ名称が繰り返されることを避けるためにパッケージ名を利用することがあります。たとえば、bufioパッケージ内の、バッファ付きリーダ型は、BufReaderではなくReaderと名づけられています。これはユーザ側からはbufio.Readerという明確かつ簡潔な名前で見えるためです。さらに、インポートされた実体は、常にそのパッケージ名を使って指定されるため、bufio.Readerはio.Readerと名前がかち合うことはありません。おなじように、ring.Ring型の新しいインスタンスを作成する関数(Go言語におけるコンストラクタ)は通常、NewRingと名づけられますが、Ringがそのパッケージからエクスポートされている唯一の型で、かつパッケージ名がringであれば、単にNewとします。この関数はパッケージを利用する側からは、ring.Newとなります。このようにパッケージの構造を利用して良い名前を付けてください。

もう一つの短い例は、once.Doです。once.Do(setup)関数は、何をする関数か想像がつきますが、これをonce.DoOrWaitUntilDone(setup)と書き換えても、より分かりやすくはなりません。長い名前は、慣れたとしても読みやすくなることはありません。複雑もしくは微妙なニュアンスを持つものに名前をつけるときは、すべての情報を名前で表現しようとするより、通常は役立つドキュメントコメントを書いたほうがよいでしょう。

インタフェース名

慣例として、ひとつのメソッドだけを持つインタフェースには、そのメソッド名の後にサフィックス(-er)を加えた名前を付けます。Reader、Writer、Formatterなどが該当します。こういった名前は他にもあり、インタフェース名とそこから得られる関数名が重要であるため、このようにして名前を作成します。

Read、Write、Close、Flush、Stringといったメソッドは、決められた役割とシグネチャを持ちます。混乱を避けるため、同じ役割およびシグネチャを持たないメソッドに対しこれらの名前を使わないでください。それとは反対に、型に実装しようとしているメソッドが、有名なメソッドと同じ役割を持つのであれば、それと同じ名前とシグネチャを使ってください。(注：文字列変換メソッドの名前は、ToStringではなくStringです)

MixedCaps

最後になりますが、Go言語の慣例では、複数の単語から成る名前をつけるときはアンダースコアを使わずに、MixedCapsまたはmixedCapsのように単語の先頭だけ大文字を用います。

The dramatic growth of income inequality in the U.S. over the last 30 to 40 years may mark the end of a long experiment in U.S. society, starting with Teddy Roosevelt and ending with Richard Nixon (things were already changing under Jimmy Carter). Teddy Roosevelt was the first of the progressive presidents, and was a major force in a shift in society in which government worked to limit the power of large corporations and guarantee basic rights like food and shelter to all citizens.

Those times are gone, and we have returned to the Gilded Age. Through a natural analogy with Greek mythology, I think we should call the present day the Argent Age. This is due to a broad shift in societal values: government is the problem, and business and the free market is the solution. The inevitable result is that an increasing number of people are poor and have little control over their own lives. In the Gilded Age their anger expressed itself in prairie populism which targeted financiers and politicians. In the Argent Age financiers aren’t doing so well at the moment, but the main anger is against politicians (again) and a somewhat imaginary liberal elite who are assumed to control the national discourse.

In both ages the wealthy by and large ignore the poor; when they consider them at all they tend to advocate a trickle-down theory. Rags-to-riches stories are prominent in both ages (Horatio Alger vs. American Idol), which serve as a form of bread and circuses. In both ages the wealthy exert enormous if somewhat hidden control over the political process.

The Gilded Age ended with Teddy Roosevelt and the Square Deal. He was a more or less accidental president, pushed onto the ticket as a vice-presidential candidate by a Republican boss who wanted him out of his position as governor of New York, and becoming president after McKinley’s assassination. Despite this inauspicious start, he immediately started working to curb the power of corporations, passing the Meat Inspection Act and the Pure Food and Drug Act, and making the serious use of the Sherman Antitrust Act.

The Argent Age will end too, but I can’t guess how. I hope we don’t have to wait for another Teddy Roosevelt; he was a true original.

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

コメント

Go言語では、C形式の/* */ブロックコメント、およびC++形式の//行コメントが使用できます。基本は行コメントですが、ブロックコメントはパッケージのコメントとして使われる他、コードをブロック単位で無効化するのに役立ちます。

godocプログラム(ウェブサーバ機能もある)は、Go言語のソースファイルから、そのパッケージ内容に関したドキュメントを抽出します。トップレベルの宣言の直前に、空行を挟まずに記述されているコメントは、その宣言に対する説明として宣言とともに抽出されます。これらコメントのありようがgodocによって生成されるドキュメントの品質を左右します。

すべてのパッケージにはパッケージコメントが必要です。これはパッケージ文の前に置かれたブロックコメントです。パッケージが複数のファイルに分かれているときは、どれかひとつにパッケージコメントを記述しておけば、それが使われます。パッケージコメントはパッケージの説明、およびパッケージ全体の情報を提供するものであるべきです。パッケージコメントはgodocページの頭に出力されるので、そのあとに続いて出力されるドキュメントの詳細部に対する導入部分としての役割もあります。

/*
    The regexp package implements a simple library for
    regular expressions.

    The syntax of the regular expressions accepted is:

    regexp:
        concatenation { '|' concatenation }
    concatenation:
        { closure }
    closure:
        term [ '*' | '+' | '?' ]
    term:
        '^'
        '$'
        '.'
        character
        '[' [ '^' ] character-ranges ']'
        '(' regexp ')'
*/
package regexp

シンプルなパッケージであれば、パッケージコメントも簡潔で構いません。

// The path package implements utility routines for
// manipulating slash-separated filename paths.

コメントに、アスタリスクを並べるような特殊な書式は不要です。生成された出力は、等幅フォントで表示されるかどうか分からないので、gofmtのようにスペースによる配置に頼らないよう気をつけてください。最後になりますが、コメントは何ら解釈されることはないプレーンテキストであるため、HTMLや、_this_のようなアノテーションはそのままの形で出力されるので用いないほうがよいでしょう。

パッケージ内の、トップレベルの宣言の直前にあるコメントはすべて、その宣言に対するドキュメントコメントとして扱われます。また、プログラム内でエクスポート（大文字で記述）されている識別子にはすべて、ドキュメントコメントが必要です。

ドキュメントコメントは様々な自動フォーマットが適用されることを考慮すると英語の文章が望ましいです。また先頭の一文は、宣言した識別子で始まる文章で、かつ概要を記述したものでなければなりません。

// Compile parses a regular expression and returns, if successful, a Regexp
// object that can be used to match against text.
func Compile(str string) (regexp *Regexp, error os.Error) {

Go言語では宣言文をグループ化することができます。このときは一連の定数または変数に対して、ひとつのドキュメントコメントで記述することができます。このようなコメントは宣言全体に対して行われるので、たいていは形式的なものとなってしまいます。

// Error codes returned by failures to parse an expression.
var (
    ErrInternal      = os.NewError("internal error")
    ErrUnmatchedLpar = os.NewError("unmatched '('")
    ErrUnmatchedRpar = os.NewError("unmatched ')'")
    ...
)

プライベートな識別子であってもグループ化することで、項目どうしに関連性があることを表すことができます。下の例では、一連の変数がmutexによって保護されていることを示しています。

var (
    countLock   sync.Mutex
    inputCount  uint32
    outputCount uint32
    errorCount uint32
)

今回から実践Go言語(Effective Go)の翻訳をはじめます。
何回かに分けて公開しますので、おつきあいください。

はじめに

Goは新しい言語です。既存の言語からアイデアを取り入れてはいますが、他の言語にはない機能をもっているため、実際に記述されたGoのプログラムは、他の類似した言語とはだいぶ異なるものになります。C++またはJavaプログラムをGo言語へ直接変換しても、あまりうまくは行きません。JavaのプログラムはあくまでJavaで書かれており、Go言語で書かれてはいないからです。一方で、Go側の視点からこの問題を考えると、変換に成功したとしても、全く違うプログラムができてしまうことになります。言い換えると、Go言語を使いこなすには、Go言語の機能や文法を理解することが重要です。おなじく、Go言語のプログラミングにおける慣例を知っておくことも重要です。たとえば名前の付け方、書式化、プログラムの構築などです。慣例に従って記述されたプログラムは他のGo言語プログラマからも理解しやすいプログラムとなります。

この文書は、分かりやすく慣用的なGo言語のコードを書く際のヒントを与えます。また、この文章は言語仕様とチュートリアルの補足であるため、それらを先に読んでおいてください。

サンプルプログラム

Go言語付属のパッケージソースは、コアライブラリを提供するだけではなく、Go言語のサンプルプログラムとしての役割もあります。問題への糸口や実装方法を探しているときに、このサンプルプログラムがその答えやアイデア、知識を提供してくれるでしょう。

ソースコードの書式

ソースコードの書式に関する問題点は多くの論議を呼んでいるのに関わらず、あまり重要視されておりません。人々は異なる書式に順応することができますが、それはしないに越したことはありませんし、全員が同じ書式を使うのであれば、このトピックに時間を割く必要もありません。問題点は、長文のドキュメントを読ませることなくこの理想に近づいていく方法です。

Go言語では、我々はちょっと変わったアプローチを取り、コンピュータにフォーマット問題の大部分を任せました。gofmtプログラムは、Go言語のプログラムを読み込むと、インデントと垂直位置を標準スタイルに変更し、必要であればコメントの内容を保ったまま再書式化した上でソースコードを出力します。見慣れない構文をどう扱えばよいか分からなければgofmtを実行してください。それが返した答えが合っていないようであれば、そのままにせずにプログラムを修正(もしくはバグ報告)してください。

例です。構造体のフィールドのコメントを一列に並べることに時間を費やす必要はありません。代わりにgofmtがそれを行ってくれます。はじめに、宣言を行います。

type T struct {
    name string // name of the object
    value int // its value
}

gofmtによってカラムが整列されます。

type T struct {
    name    string // name of the object
    value   int    // its value
}

ライブラリ内のすべてのコードは、gofmtで書式が揃えられています。

若干、フォーマットの詳細についての説明が残っていますので、簡潔に説明します。

インデント

インデントにはタブを使います。これはgofmtのデフォルトです。スペースは必要がない限り使わないでください。

行の長さ

Go言語には、行の長さ制限は有りません。パンチカードからはみ出す心配は無用です。行があまりにも長くなったときは、改行してタブでインデントしてください。

括弧

Go言語はあまり括弧を必要とはせず、制御機構(if, for, switch)の構文には括弧は不要となっています。また、演算子の優先順位は簡潔かつ明確です。たとえば、

x<<8 + y<<16

この式は、見たとおりの値を表します。

I never cease to amaze me how I am always learning new things when programming C/C++ even after this many years. However I thought that mostly related to quirks in C++ and C++ template stuff. Yesterday I discovered something in C, which I kind of think I should have known. Especially since I have used it countless times without really knowing it. Why not make this a little quiz, to see if you really thought about it too.

You have probably written code like this before int x = 2, y = 3 or for (i = 0, j = 1; i < size; ++i, ++j). So here is the quiz. Without looking up in a reference or googling. What does this do, and print out?

int i = 5, size = 5;
i < size || (i = -1), ++i;
printf("%d\n", i); 
 

Answer: It increments i but wraps when becomes size or bigger. Meaning incrementing i when it is size or larger sets it to zero. So 0 is printed out. How is how it works:

1. The || operator will only evaluate the right expression if the left one was false. Because the right expression does not need to be evaluated to determine that the whole expression is true when left is true.
2. So when i is 5 the left expression is false and i is thus set to -1.
3. The comma operator is an expression operator. a, b makes sure b is evaluated after a. Meaning ++i will always be evaluated, but after all the other expressions that needs to be evaluated to find the value of the expression.

int i = 5, size = 5;
if (i >= size)
  i = 0;
++i;
printf("%d\n", i); 
 

What got me into this was trying to understand this macro found in the source code of the lua script language:

#define luaL_addchar(B,c) \
  ((void)((B)->p < ((B)->buffer+LUAL_BUFFERSIZE) || luaL_prepbuffer(B)), \
   (*(B)->p++ = (char)(c)))
 

It is basically used to copy characters into a buffer. B->p is current position in buffer. The code makes sure that luaL_prepbuffer is called if the size of the buffer is exceeded. That function will empty the current buffer (passing on the contents) and making it ready to receive more characters. So the current pointer is reset to the start.

The question is of course why do this? Probably because it makes it possible to treat the macro more like a function. An expression can be placed most places a function call can be placed. However multiple statement, even if they are enclosed by {} can not.

for (i < 0; i < size; luaL_addchar(B,c))
 

for (i < 0; i < size; {if (B->p >= B->buffer+LUAL_BUFFERSIZE) 
                         luaL_prepbuffer(B); 
                       *B->p++ = c;})
 

So what if Ubuntu's mission is to target ex-Windows users?

So what does that have to do with Fedora?

I recently had to create some code using the interpreter pattern from GoF. However I didn't have my Design Pattern by the Gang of Four ready so I had to look it up at wikipedia. That got me looking at example implementations in C# and Java. Being all about Go for the time being it got me thinking what the same code would look like in Go using closures instead of classes. Just like I demonstrated with other patterns in previous posts.

The code below demonstrates the interpreter pattern by implementing an interpreter of Reverse Polish notation as described on the wiki page. The wiki example uses a class to implement each grammar rule. Here we use a closure. A higher order function will return a function which when run will evaluate the grammar in given context.

import "fmt"
import . "container/vector"
import . "strings"

type Expression func(variables map[string]int) int

func Number(number int) Expression {
  return func(variables map[string]int) int {
    return number
  }
}

func Plus(left, right Expression) Expression {
  return func(variables map[string]int) int {
    return left(variables) + right(variables)
  }
}

func Minus(left, right Expression) Expression {
  return func(variables map[string]int) int {
    return left(variables) - right(variables)
  }
}

func Variable(name string) Expression {
  return func(variables map[string]int) int {
    return variables[name]
  }
}

What is interesting to notice is that the Java version using classes to define grammars takes up 43 lines, while the Go version takes 25 lines. The C# version takes even more lines: 63. However that is in large part because the approach is a bit different. The Evaluator takes about the same number of lines.

func Evaluator(expression string) Expression {
  var expStack Vector
  for _, token := range Split(expression, " ", 0) {
    switch {
    case token == "+": 
      subExpression := Plus(expStack().(Expression), 
                            expStack().(Expression))
      expressionStack.Push(subExpression)
    case token == "-": 
      subExpression := Minus(expStack().(Expression), 
                             expStack().(Expression))
      expressionStack.Push(subExpression)
    default:
      expressionStack.Push(Variable(token))
    }    
  }
  syntaxTree := expStack().(Expression)
  
  return func(context map[string]int) int {
    return  syntaxTree(context)
  }
}

func main() {
  expression := "w x z - +"
  sentence   := Evaluator(expression)
  variables  := map[string]int {"w" : 5, "x" : 10, "z" : 42}
  result     := sentence(variables)
  fmt.Println(result) 
}

func plus(a, b int)  int { return a + b }
func minus(a, b int) int{ return a - b }

func BinOp(left, right Expression, op func(a, b int) int) Expression {
  return func(variables map[string]int) int {
    return op(left(variables), right(variables))
  }
}

I recently spent some time sorting through linker version script issues, so I’m going to document what I discovered.

Linker symbol versioning was invented at Sun. The Solaris linker lets you use a version script when you create a shared library. This script assigns versions to specific named symbols, and defines a version hierarchy. When an executable is linked against the shared library, the versions that it uses are recorded in the executable. If you later try to dynamically link the executable with a shared library which does not provide the required versions, you get a sensible error message.

Sun’s scheme (as I understand it) only permits you to add new versions and new symbols. Once a symbol has been defined at a specific version, you can not change that in later releases. if you change the behaviour of a symbol, you don’t change the version of the symbol itself, instead you add a new version to the library even if it does not define any symbols. That is sufficient to ensure that an executable will not be dynamically linked against a version of the shared library which is too old.

Eric Youngdale and Ulrich Drepper introduced a more sophisticated symbol versioning scheme in the GNU linker and the GNU/Linux dynamic linker. The GNU linker permits symbols to have multiple versions, of which only one is the default. These versions are specified in the object files linked together to form the shared library. The assembler .symver directive is used to assign a version to a symbol (the version is simply encoded in the name of the symbol). This scheme permits using symbol versioning to actually change the behaviour of a symbol; older executables will continue to use the old version. This also permits deleting symbols, by removing the default version. The older versions of the symbol remain but are inaccessible.

That is all fine. The problems come in with the extensions to the version script language. First, the GNU linker permits wildcards in version scripts. Second, the GNU linker permits symbols to match against demangled names, again typically using wildcards. Third, the GNU linker permits the version script to hide symbols which have explicit versions in input object files.

Every symbol can only have one version. When the linker asks for the version of a symbol, there can only be one answer. The support for wildcards and matching of demangled names in the GNU linker script means that there may not be a unique answer for the version to use for a given name. The fact that the GNU linker permits version scripts to hide symbols with explicit versions means that in some cases you absolutely must list a symbol two times in a version script (because you might have a local: *; entry which must not match your symbol with an old version). This potential confusion means that using linker scripts correctly with wildcards requires a clear understanding of exactly how the linker parses a version script.

Unfortunately, this was never documented. Until now. Here are the rules which the GNU linker uses to parse version scripts, as of 2010-01-11.

The GNU linker walks through the version tags in the order in which they appear in the version script. For each tag, it first walks through the global patterns for that tag, then the local patterns. When looking at a single pattern, it first applies any language specific demangling as specified for the pattern, and then matches the resulting symbol name to the pattern. If it finds an exact match for a literal pattern (a pattern enclosed in quotes or with no wildcard characters), then that is the match that it uses. If finds a match with a wildcard pattern, then it saves it and continues searching. Wildcard patterns that are exactly “*” are saved separately.

If no exact match with a literal pattern is ever found, then if a wildcard match with a global pattern was found it is used, otherwise if a wildcard match with a local pattern was found it is used.

This is the result:

• If there is an exact match, then we use the first tag in the version script where it matches.
  • If the exact match in that tag is global, it is used.
  • Otherwise the exact match in that tag is local, and is used.
• Otherwise, if there is any match with a global wildcard pattern:
  • If there is any match with a wildcard pattern which is not “*”, then we use the tag in which the last such pattern appears.
  • Otherwise, we matched “*”. If there is no match with a local wildcard pattern which is not “*”, then we use the last match with a global “*”. Otherwise, continue.
• Otherwise, if there is any match with a local wildcard pattern:
  • If there is any match with a wildcard pattern which is not “*”, then we use the tag in which the last such pattern appears.
  • Otherwise, we matched “*”, and we use the tag in which the last such match occurred.

As mentioned above, there is an additional wrinkle. When the GNU linker finds a symbol with a version defined in an object file due to a .symver directive, it looks up that symbol name in that version tag. If it finds it, it matches the symbol name against the patterns for that version. If there is no match with a global pattern, but there is a match with a local pattern, then the GNU linker marks the symbol as local.

I want gold to be compatible, but I also want gold to be efficient. I’ve introduced a hash table in gold to do fast lookups for exact matches. That makes it impossible for gold to follow the exact rules when matching demangled names. Currently gold does not do the final lookup to see if a symbol with an explicit version should be forced local; I don’t understand why that is useful. It is possible that I will be forced to add that to gold at some later date.

Here are the current rules for gold:

• If there is an exact match for the mangled name, we use it.
  • If there is more than one exact match, we give a warning, and we use the first tag in the script which matches.
  • If a symbol has an exact match as both global and local for the same version tag, we give an error.
• Otherwise, we look for an extern C++ or an extern Java exact match. If we find an exact match, we use it.
  • If there is more than one exact match, we give a warning, and we use the first tag in the script which matches.
  • If a symbol has an exact match as both global and local for the same version tag, we give an error.
• Otherwise, we look through the wildcard patterns, ignoring “*” patterns. We look through the version tags in reverse order. For each version tag, we look through the global patterns and then the local patterns. We use the first match we find (i.e., the last matching version tag in the file).
• Otherwise, we use the “*” pattern if there is one. We give a warning if there are multiple “*” patterns.

I hope for your sake that this information never actually matters to you.

The merger between AOL and Time Warner, the biggest merger in U.S. history, happened ten years ago. It is now generally considered to have been the worst merger of all time.

Hindsight is 20/20, but I clearly remember that when I first read it I thought it was a joke. I was working in Silicon Valley, as I still do today, and it was obvious that the Valley was in the boom part of its regular boom/bust cycle. Money was pouring into Internet companies, but it was obvious that it was a bubble headed for a crash. That’s not hindsight either, it’s what I and plenty of other people thought at the time.

So AOL’s stock price was obvious vapor, especially considering that cable modems were starting to spread and AOL had no obvious plans to get out of the cheap dialup world that it lived in. AOL’s walled garden had already disappeared into the wider Internet.

Time Warner, on the other hand, was a serious company with real products and real continuing customers. Actually they turned out to be heading into a terrible decade along with the rest of the media, but I didn’t see that coming. The notion that they would merge with AOL—actually AOL’s market cap was higher so it was more of an acquisition of Time Warner by AOL—seemed completely laughable to me.

A friend of mine suggested that the real goal was for Steve Case to put real grounding under AOL’s absurd market cap, by using it to buy a real company. I’m not sure I agree—I think Case may have really believed that AOL somehow deserved its market cap. I have no idea how he convinced everybody else involved. It just seems so obviously crazy on the face of it.

Of course, one thing arguing in favor of the merger is that our form of capitalism requires companies to always grow, which is very hard for very large companies to do. At some point, the personal incentives for executives are such they will do better if they do something even if it looks crazy, because doing nothing will certainly not lead to growth. I haven’t checked I’m sure the executives who agreed to the merger did fine out of it.

There have been mergers which I thought would fail but turned out to more-or-less succeed, such as HP/Compaq. But I always thought AOL/Time Warner one would fail, and on that one I was right.

The Go Programming Language Specificationの翻訳、最終回です。
すべての訳はGo言語仕様[日本語訳]にまとめてあります。

システム考察

unsafeパッケージ

組み込みパッケージunsafeは、コンパイラに実装されており、低レベルのプログラミング向けの機能を提供します。これには型システムから逸脱した機能が含まれています。そのためunsafeを使っているパッケージは、型が安全であることを手作業でよく確認しておかなくてはなりません。このパッケージでは、以下のインタフェースを提供しています。

package unsafe

type ArbitraryType int  // shorthand for an arbitrary Go type; it is not a real type
type Pointer *ArbitraryType

func Alignof(variable ArbitraryType) int
func Offsetof(selector ArbitraryType) int
func Sizeof(variable ArbitraryType) int

func Reflect(val interface {}) (typ runtime.Type, addr uintptr)
func Typeof(val interface {}) reflect.Type
func Unreflect(typ runtime.Type, addr uintptr) interface{}

すべてのポインタ、およびuintptr型の値は、Pointerに変換することができます。またその逆も可能です。

Sizeof関数は、変数を表す式を受け取り、その変数のサイズをバイト数で返します。

Offsetof関数は、構造体のフィールド表すセレクタ(§セレクタ)を受け取り、構造体のアドレスからフィールドへの相対オフセットをバイト数で返します。下は構造体sのフィールドfを使った例です。

uintptr(unsafe.Pointer(&s)) + uintptr(unsafe.Offsetof(s.f)) == uintptr(unsafe.Pointer(&s.f))

コンピュータのアーキテクチャによっては、メモリのアドレスにアライメントが必要となることがあるため、変数のアドレスは、変数の型が持つアライメントも考慮します。Alignof関数は、変数を表す式を受け取り、変数（の型）のアライメントをバイト数で返します。下は変数xを使った例です。

uintptr(unsafe.Pointer(&x)) % uintptr(unsafe.Alignof(x)) == 0

Alignof、Offsetof、Sizeofの呼び出しは、コンパイル時にint型の定数となります。

unsafe.Typeof、unsafe.Reflect、unsafe.Unreflect関数は、実行時にインタフェースに格納されている動的な型および値へのアクセスを許します。Typeofは、valの動的な型を runtime.Typeとして返します。Reflectは、valの動的な値のコピーを割り当て、型とそのコピーのアドレスを返します。UnreflectはReflectの逆で、型とアドレスからインタフェースの値を作成します。これらの関数を利用しているreflectパッケージでは、インタフェースの値を安全、かつより便利に調べる方法を提供しています。

サイズとアライメントの保証

数値型(§数値型)では、以下に示すサイズが保証されています。

型                        サイズ(バイト数)

byte, uint8, int8         1
uint16, int16             2
uint32, int32, float32    4
uint64, int64, float64    8

以下に示す、アライメントの特性が最低限保証されています。

1. 変数x(型は問わない)：1 <= unsafe.Alignof(x) <= unsafe.Maxalign
2. 変数xが数値型のとき：unsafe.Alignof(x)は、 unsafe.Sizeof(x)およびunsafe.Maxalign 以下であり、少なくとも1以上である。
3. 変数xが構造体型のとき：unsafe.Alignof(x)は、xの各フィールドをfとしたときunsafe.Alignof(x.f)の中で一番大きい値と同じであり、少なくとも1以上である。
4. 変数xが配列型のとき：unsafe.Alignof(x)は、unsafe.Alignof(x[0])と同じであり、少なくとも1以上である。

実装との差異 – TODO

• 実装は、gotoステートメント、および(宣言以外の)宛先に対する制約を守っていません。
• メソッド式は未実装です。
• Gccgoではひとつのソースファイルに、ひとつのinit()関数しか許していません。

Enough about programming for a moment. Here are some questions I have about climate change

1. Temperature measurements clearly show that the Arctic regions are warming up. Atmosphere measurements clearly show that the amount of carbon dioxide in the air is increasing. The physics showing that increasing carbon dioxide in the atmosphere can lead to increasing temperature are simple enough that I can understand them. This all hangs together nicely. It seems to me that people who argue that climate change is not occurring need to explain why increasing carbon dioxide does not make the earth warmer, and why the earth is getting warmer anyhow. That is, instead of having a neat explanation for what real measurements show, they have two puzzles. It does not seem parsimonious.

2. I’ve seen arguments that climate change may be occurring, but that it may not be due to human activity. To which I can only respond, who cares what causes it? We should still think about what to do about it.

3. I frequently see that it may be too costly to take the actions required to stop climate change. This argument seems like a misunderstanding of economics. Changes to the climate are a classic economic externality. Somebody has to pay for them, one way or another. If we don’t apply a carbon tax one way or another, then it will be applied for us later on. You can’t escape an externality by pretending that it doesn’t happen, the best you can do is push it onto somebody else. In our case we are currently pushing it onto future generations. That may be a rational choice, if we believe that future generations will be richer than we are. But we shouldn’t pretend that we can’t afford to stop climate change. We don’t have a choice about whether to pay for it.

4. In any case, adjusting for climate change only hurts the economy if we measure the economy in terms of consumption of natural resources. That is not a very relevant measure of the U.S. economy today. Shifting to different technologies will cost jobs in some areas and create job in others. We can grow the economy while using fewer natural resources. It’s entirely possible for us to shift to carbon neutral technologies without hurting the economy (that is, it is possible in an economic sense; it may or may not be possible in a technological sense). I’m not saying it will be easy, but it is certainly possible. The U.S. is currently letting countries like Germany and China get a significant technological lead in this area, but it’s probably not too late to catch up.

5. I really don’t understand why climate change has become a partisan issue in the U.S. There is nothing either Republican or Democratic about science, or about skepticism.

6. Freeman Dyson makes the very interesting point that about 8% of the carbon dioxide in the atmosphere is absorbed by vegetation every year. That means that biological processes can have enormous effects on carbon dioxide levels. We should be experimenting with biologically based forms of carbon capture. Probably people are already doing this.

7. The climate is already changing. I think the only interesting question now is whether we will prevent a significant rise in sea level. My current bet is that we won’t; history is definitely on the side of people avoiding dealing with environment issues until they are blatant. This is not a good time to invest in beachfront property.

Type something:     "fmt." 
Use Emacs cmd:      <M+TAB>  
Or alternative cmd: <M+x> complete-tag
Result:             "fmt.Printf"

Continue to press <M+TAB> to cycle through alternative completions.

Type something:      "ProbablyPrime"
Use Emacs cmd:       <M+.> 
Or alternative cmd:  <M+x> find-tag
Result:              The file "int.go" will open on line 359.


Emacs cmd: <M+*> // Will send you back to the previous file.
Emacs cmd: <M+x> find-tag-other-window // Will display the tag in a second window

I recently encountered a nice example of cargo cult programming. In bug 10980 Robert Wohlrab helpfully built a large number of Debian packages with the gold linker and reported errors about unknown options. These were options supported by the GNU linker but not by gold. (I’ve now added all the options to gold).

Among the options that packages used were -g and -assert. The GNU linker accepts and ignores these options. It has never done anything with them. Why do people pass them to the linker? I can only assume that they were copied from some other linker invocation.

In today’s increasingly complex world of programming, when so much code involves integrating libraries in various ways, I expect that cargo cult programming is on the rise.

The Go Programming Language Specificationの翻訳、13回目です。
前回までの訳はGo言語仕様[日本語訳]にまとめてあります。

プログラムの初期化と実行

ゼロ値

値を格納するため宣言や、make()、new()の呼び出しによりメモリが割り当てられたとき、明示的に初期化をしなければ、そのメモリはデフォルトの初期化が行われます。このような値の要素には、それぞれその型のゼロ値がセットされます。論理値型のゼロ値はfalse、整数型は0、浮動小数点型は0.0、文字列型は""です。ポインタ、関数、インタフェース、スライス、チャネル、マップ型のゼロ値はnilです。この初期化は再帰的に行われるので、たとえば構造体が配列のとき、初期値が指定されなければ、各要素のフィールドはゼロ値となります。

次の2つの宣言は等価です。

var i int;
var i int = 0;

続いて、

type T struct { i int; f float; next *T };
t := new(T);

これは、下の値を持ちます。

t.i == 0
t.f == 0.0
t.next == nil

次も同じことが当てはまります。

var t T

プログラムの実行

インポートを伴わないパッケージの初期化は、パッケージレベルのすべての変数への初期値代入、およびソース内で定義されている次の名前とシグネチャを持ったパッケージレベルの関数の呼び出しにより行われます。

func init()

パッケージに複数のinit()関数が含まれるとき(ひとつのソースファイルに複数記述も可)は、順不同で実行されます。

パッケージ内で、パッケージレベルの変数の初期化、および定数値の決定は、それぞれのデータの依存する順で行われます。たとえばAのイニシャライザがBの値に依存するならば、Aの値はBの後に決まります。この依存関係がループしてしまうときはエラーとなります。
依存関係の分析は、辞書的かつ再帰的に行われます。Aの値がBに影響を受けている、またはAのイニシャライザがBの影響を受けている、またはAが影響を受けている関数がさらにBの影響を受けているときに、AはBに依存しているとみなされます。
ある2つのアイテムがお互いに依存していなければ、それらはソース内に出現した順で初期化されます。依存関係の分析はパッケージごとに行われるため、Aのイニシャライザが、Bを参照している別のパッケージで定義されている関数を呼び出したときの結果は規定されていません。

初期化コードが、“go”ステートメントを含んでいたとしても、全プログラムの初期化が終了するまで、そのステートメントで指定した関数の実行を開始しません。したがって、すべての初期化コードは単一のゴルーチン内で動作します。

init()関数はプログラムのどこからも参照することができません。すなわち、明示的に呼び出すことも、変数にこの関数のポインタを代入することもできません。

パッケージがインポートを伴うときは、このパッケージ自身の初期化より前に、インポートされたパッケージが初期化されます。ひとつのパッケージを複数回インポートしても、そのパッケージが初期化されるのは一回だけです。

パッケージのインポートでは構造上、初期化の依存関係が循環しないことが保証されています。

完成されたプログラムは、次の関数を持つmainパッケージを持たなくてはなりません。

func main() { ... }

これは、複数のパッケージを結合して作られたとしても同様です。このmain.main()関数は、引数および戻り値を持ちません。

プログラムの実行はmainパッケージを初期化したあと、main.main()関数を実行することで開始されます。

main.main()から抜けたときに、プログラムは終了します。このとき、他（main以外）のゴルーチンの終了待ちは行いません。

実装上の制約：コンパイラはmainパッケージが、他のどのパッケージからもインポートされることはないと仮定しています。

The goal of generics in a programming language is to save programmer time. Generics permit you to write code that works with multiple types only once. They also permit one programmer to write generic algorithms which you can use with your program’s types. This kind of thing is attractive to anybody who has written a lot of C code, where you find yourself writing the same linked list and hash table code over and over again. The core code will use void * pointers but for everything else you need type casts. Those type casts are mechanical and tedious.

I would say that the most significant advantage of C++ over C is the C++ mechanism for generic programming, which is templates. C++ has a powerful template system which is somewhat like a macro system built into the language proper. It’s not really a macro system—in a true macro system the code would be parsed only at template instantiation time, but in fact C++ code is parsed at template definition time—but I’ve discovered that people who are not deeply familiar with the language think of it that way, and it is an effective approach. C++ pays for this power in compilation time, as each template must be separately compiled for each type for which it is instantiated. It also pays in language complexity, which is most visible to users in the widely noted incomprehensible error messages. For a while the new C++ standard introduced the idea of concepts which would at least improve the error messages, but concepts themselves turned out to be very complex and were dropped from the standardization process for now.

Other languages have other approaches to generics. I know these languages less well, so I hope I don’t make any mistakes. Java restricts generics to types which are inherited from Object, which permits the templates to be instantiated a single time; a cost of Java’s approach is that the actual types are lost (this is known as type erasure). C# instantiates generics at runtime using a JIT; all types which are representable as pointers can share a single instantiation. ML has two different generics implementations: simple polymorphism which can be used for, e.g., type-safe containers, and a powerful system in which you can write a transformation which takes a set of types, variables, and functions and produces a different set; the latter system is pretty much as powerful as C++ templates but does not need to be compiled each time (I think) and produces comprehensible error messages. LISP has an extremely powerful macro system which simply rewrites the program, something which is relatively easy to do in LISP due to the simple syntax; this is so powerful that it lets you add new syntactic constructs to your program.

I’ve been thinking about generics because of Go. Go’s goals include fast compilation and efficient execution. Those goals are in conflict when it comes to generics. Go is not interpreted, and it is not the case that every type looks like a pointer. Therefore efficient execution suggests separate compilation for each instantiation, which of course slows down compilation time. ML’s approach is quite powerful, but it may be complex to use in simple cases, and it’s hard to understand how to implement it for Go. Relying on every type matching the empty interface doesn’t help when somebody wants to write a generic function for chan T, since chan int is not the same as chan interface{}.

Implementing generics in Go looks like a struggle among the goals of fast compilation time (i.e., avoid multiple compilation of generics), easy programming (i.e., have some form of generics), and fast execution (i.e., different types are represented differently). All languages have those goals in different degrees, and all languages seem to compromise on one of them when it comes to implementing generics. The question for Go is whether we can find an appropriate compromise.

The Go Programming Language Specificationの翻訳、12回目です。
前回までの訳はGo言語仕様[日本語訳]にまとめてあります。

パッケージ

Go言語のプログラムは、複数のパッケージをひとつにリンクすることによって作られます。さらに各パッケージは、そのパッケージに所属する定数、型、変数、関数を宣言している、ひとつ以上のソースファイルから構成されます。これらパッケージ内の要素は、同一パッケージ内であれば、別ファイルからアクセスすることができます。また要素がエクスポートされていれば、他パッケージからアクセスすることができます。

ソースファイルの構成

各ソースファイルは、そのファイルがどのパッケージに属しているかを定義するパッケージ文で始まります。以降は必須ではありませんが、ソースファイル内で使用したいパッケージを宣言する一連のインポート宣言。さらに、関数、型、変数、定数の一連の定義が続きます。

SourceFile       = PackageClause { ImportDecl [ ";" ] } { TopLevelDecl [ ";" ] } .

パッケージ文

各ソースファイルはパッケージ文で始まり、そのファイルが所属するパッケージを定めます。

PackageClause  = "package" PackageName .
PackageName    = identifier .

このパッケージ名(PackageName)はブランク識別子であってはなりません。

package math

パッケージの実装は、同じパッケージ名を共有するファイル群によって構成されます。実装によっては、同一パッケージ内のすべてのソースファイルが、同一ディレクトリ内に置かれている必要があります。

インポート宣言

インポート宣言によって、インポートされたパッケージ内でエクスポートされている識別子を使うことで、インポート宣言を記述しているソースファイルから、それらにアクセス可能になります。インポートでは、アクセスするために使用する識別子（PackageName）、およびインポートされるパッケージを指定するImportPathを指定します。

ImportDecl       = "import" ( ImportSpec | "(" [ ImportSpecList ] ")" ) .
ImportSpecList   = ImportSpec { ";" ImportSpec } [ ";" ] .
ImportSpec       = [ "." | PackageName ] ImportPath .
ImportPath       = StringLit .

PackageNameは、限定付き識別子を使い、そのパッケージでエクスポートされている識別子にアクセスするために使用されます。PackageNameは、ファイルブロック内で宣言されます。PackageNameを省略したときは、インポートされた側パッケージのパッケージ文で指定されている識別子がデフォルトとして使用されます。名前の代わりにピリオド(.)が指定されたときは、そのパッケージでエクスポートされている全識別子が、カレントのファイルのファイルブロックで宣言され、プレフィックスなしでアクセスできるようになります。

ImportPathの解釈は実装に依存しますが、一般的には、コンパイル済みパッケージのパス名の一部であり、パッケージのリポジトリへの相対パスです。

仮に、Sin関数をエクスポートしているmathパッケージがあり、"lib/math"というパスにそのコンパイル済みパッケージがインストールされているとします。下の表では、各インポート方法でこのパッケージをインポートしたとき、そのファイル内でSin関数がどのようにしてアクセスされるかを説明します。

インポート宣言                Sinのローカル名

import   "lib/math"         math.Sin
import M "lib/math"         M.Sin
import . "lib/math"         Sin

インポート宣言は、インポート「する側」と「される側」の依存関係を宣言します。自分自身のパッケージをインポートすること、またはインポートしたパッケージ内でエクスポートされている識別子を一切参照しないことは誤った使い方です。インポートによる副作用(初期化)のためだけにパッケージをインポートするときは、パッケージ名としてブランク識別子を使ってください。

import _ "lib/math"

パッケージサンプル

これは、並列処理による「素数のふるい」を実装した、Goのパッケージ一式です。

package main

import "fmt"

// 2,3,4,...というシーケンスをチャネル'ch'に送信
func generate(ch chan<- int) {
	for i := 2; ; i++ {
		ch <- i;	// 'i'をチャネル'ch'に送信
	}
}

// チャネル'in'の値をチャネル'out'にコピー
// ただし'prime'で割り切れる値を除く
func filter(src <-chan int, dst chan<- int, prime int) {
	for i := range src {	// 'src'から受信した値でループ
		if i%prime != 0 {
			dst <- i;	// 'i'をチャネル'dst'に送信
		}
	}
}

// 素数のふるい：フィルターを数珠つなぎに組み合わせて処理する
func sieve() {
	ch := make(chan int);	// 新しいチャネルを作成
	go generate(ch);	// generate()をサブプロセスとして開始
	for {
		prime := <-ch;
		fmt.Print(prime, "\n");
		ch1 := make(chan int);
		go filter(ch, ch1, prime);
		ch = ch1;
	}
}

func main() {
	sieve();
}

The Go Programming Language Specificationの翻訳、11回目です。
前回までの訳はGo言語仕様[日本語訳]にまとめてあります。

組み込み関数

組み込み関数として、いくつかの関数が事前宣言済みとなっています。組み込み関数の呼び出しは他の関数と同様ですが、いくつかの関数では、第一引数に「式」ではなく「型」を受け取ります。

BuiltinCall = identifier "(" [ BuiltinArgs ] ")" .
BuiltinArgs = Type [ "," ExpressionList ] | ExpressionList .

close、closed

cをチャネルと仮定したとき、事前宣言済み関数close(c)は、これ以上の値を送信操作により受け付けないようチャネルをマーキングします。closeより前に送信された値を受信したあとは、受信操作はそのチャネル型のゼロ値を返すようになります。このようにゼロ値が受信されたあとは、closed(c)はtrueを返すようになります。

長さ、キャパシティ

組み込み関数lenとcapは、様々な型の引数を取り、int型の結果を返します。実装上、これらが返す結果が常にintと適合することが保証されています。

呼び出し   引数の型              戻り値

len(s)    文字列型              文字列のバイト長
          [n]T, *[n]T          配列の長さ(== n)
          []T                  スライスの長さ
          map[K]T              マップの長さ(定義されているキーの数)
          chan T               チャネルのバッファ内でキューイングされている要素数

cap(s)    [n]T, *[n]T          配列の長さ(== n)
          []T                  スライスのキャパシティ
          chan T               チャネルのバッファのキャパシティ

スライスのキャパシティは、根底にある配列に割り当てられている要素数です。これは常に、下の関係が保たれます。

0 <= len(s) <= cap(s)

メモリの割当

組み込み関数newは型Tを取って、型*Tの値を返します。このときメモリの内容は初期値のセクション(§ゼロ値)で記述されているように初期化されます。

new(T)

例です。

type S struct { a int; b float }
new(S)

この例では、型Sの変数に対してメモリを動的に割り当て、初期化(a=0, b=0.0)したのち、そのメモリのアドレスを持つ、型*Sの値を返します。

スライス、マップ、チャネルの作成

スライス、マップ、チャネルは、newによる間接的なメモリ割り当てを必要としない、参照型です。
組み込み関数makeは、型Tを取ります。このTはスライス、マップ、チャネル型でなければなりません。また、オプションとして式のリスト(作成する種類によって異なる)を取ります。makeは型T(*Tではない)を返します。このときメモリの内容は初期値のセクション(§ゼロ値)で記述されているように初期化されます。

make(T [, 式のリスト(オプション)])

例です。

make(map[string] int)

この例では、新しいマップの値を作成し、空のマップとして初期化します。

パラメータの値によって、スライス、マップ、バッファリングされたチャネルの割り当てサイズが変更できます。

s := make([]int, 10, 100);        // len(s) == 10, cap(s) == 100のスライス
s := make([]int, 10);             // len(s) == cap(s) == 10のスライス
c := make(chan int, 10);          // バッファサイズ10のチャネル
m := make(map[string] int, 100);  // 100要素を初期容量として持つマップ

ブートストラッピング

現在の実装では、ブートストラッピング(Go言語コンパイラ自身のコンパイル)に役立つ、いくつかの組み込み関数を提供しています。これらの関数は文書化されていますが、このまま言語に残されるかどうかは保証されません。また、これらの関数は結果を返しません。

関数        振舞い

print      全引数を出力する(各フォーマットは実装依存)
println    printと同じだが、各引数間にスペース、および最後に改行を出力する
panic      printと同じだが、出力後に実行を中断する
panicln    printlnと同じだが、出力後に実行を中断する

新年あけましておめでとうございます。
本年も golang.jp をよろしくお願いします。
golang.jpは、今年も引き続きGo言語の日本語情報を少しでも増やすための努力をしていきます。

話は変わりまして、昨年末の記事ですが、
@ITにGo言語のインストール～簡単なプログラムのコンパイルの記事が載っていましたので紹介させていただきます。
http://www.atmarkit.co.jp/fcoding/articles/go/02/go02a.html

On the surface Go and Java might seem to have a lot in common. They are both modern C/C++ like languages with garbage collection, supporting object oriented programming.

But beyond that there are quite a lot of differences. I will not highlight so much of Java's strengths compared to Go, as Java has been around for a long time. What is more interesting is why a developer should want to choose Go over Java, given Java's ubiquity, large number of frameworks, tools etc.

First issue is efficiency both with respect to memory usage and performance. Go allows much more low level tuning similar to C. A problem in Java is that all types except primitive types are reference types. That means related data can't be stored in one location. E.g. say we have a Car object with 1 Engine object, 4 Wheel objects etc. All those objects are stored in different locations in memory. While in C or Go you could store all the Car related data as one continuous block of memory. Why is that important? In modern computers CPU's can process data a lot faster than it can be feed to it by regular RAM memory. Due to this frequently used parts of the main RAM memory are stored in a super fast memory called cache. For caches to be efficient related data needs to be close in address space. That is hard to achieve in Java.

An example of this in practice is the distributed version control system git. It is known to be very fast. It is written in C. A Java version JGit was made. It was considerably slower. Handling of memory and lack of unsigned types was some of the important reasons.

JGit struggles with not having an efficient way to represent a SHA-1. C can just say "unsigned char[20]" and have it inline into the container's memory allocation. A byte[20] in Java will cost an *additional* 16 bytes of memory, and be slower to access because the bytes themselves are in a different area of memory from the container object. We try to work around it by converting from a byte[20] to 5 ints, but that costs us machine instructions

Like C, Go does allow unsigned types and defining data structures containing other data structures as continuos blocks of memory

Method calls

Before reading this it might be good to read Scott Stanchfield's article on why all java method calls use pass-by-value, and that there is no such thing as pass-by-reference in Java. However as mentioned Java does not support value types for other than primitive types. This causes problems for method calls. One problem is that small objects like a Point might often be faster to copy in a method call, rather than copy their reference which is what Java does. More importantly perhaps is that value semantics is often easier understood. E.g. it would be natural to assume that Point would be a value type. If I pass a Point object to a function I don't expect my point to be modified by called function. And yet that can easily happen in Java.

Too strong focus on OOP

Since the decision was made that Java would have no free functions (even though static methods in a way is free functions) this has caused the Java designer to come up with very cumbersome syntax to deal with problem that would have been best handled with free functions. Instead of closures Java got nested classes:

 myButton.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            frame.toFront();
        }
    });

 myButton.addActionListener(func(e ActionEvent) {
  frame.toFront();
 });

Actually the Java version requires even more code, because the ActionListener class needs to be defined somewhere. The function object passed in the Go example is defined right were it is used.

Why Java code end up being considerably more verbose than Go code

When you start building more complicated things this problem starts adding up, causing excessive amounts of code to be needed in Java, while short readable code can be used in Go for the same thing. Consider this example. For a game engine I was writing I used Lua as a script language. Algorithms for planning movement of Non player characters was based on combining different functions describing different behavior. Without a lot of background information the code below is not easy to follow. But bare with me:

flank, seek and combo are functions created by other functions makeFlank, makeSeek etc. The combo function is created by combining the flank and seek functions. Basically each function takes two arguments referred to as s0 and s1, which denotes a orientation and position in space. Below is the code that creates the seek function:

The details of the code is not important. It is mainly vector operations used to calculate how desirable s1 is with respect to getting the non player character to the goal position target. The candidate s1 position and orientations are produced elsewhere by considering places in space which does not cause collision with other objects etc. The code below shows how we would do this in Java. Since Java does not have closures we have to use classes:

The different behaviors will then be combined as follows:

With Go we can write the code more like we did in the dynamic script language Lua.

func makeSeek(target Vec2) func(s0, s1 State) float {
  func seek(s0, s1 State) float {
   p0 := s0.position();
   p1 := s1.position(); 
   d1 := s1.direction(); 

   // direction to target   
   dir_target := (target.minus(p1)).unit();

   // direction of from current point to next on path
   dir_path := (p1.minus(p0)).unit();
   return 0.25*(1.0 + d1.dot(dir_target))*(1.0 + dir_path.dot(dir_target));    
  }
  return seek; 
}

The the different behavior can be combined in much the same way as it was combined in Lua. The last statement can be done in many ways. The code below is valid since Go supports functions with arbitrary number of arguments, but it can't be properly type checked at compile time.

flank := makeFlank(player, 10);
seek  := makeSeek(target);
combo := makeCombo(flank, 1.0, seek, 0.001);

For stronger type checking one might want to do something like the code below, which requires defining a struct Elem with a function pointer and float member.

combo := makeCombo(List{Elem{flank, 1.0}, Elem{seek, 0.001}});

Doing something similar to the Java way is also possible:

var funcs FuncList;
funcs.Add(flank, 1.0);
funcs.Add(seek, 0.001);
combo := makeCombo(&funcs);

What should be apparent is how much boilerplate code one has to write when making Java programs:

1. Every method needs public in front
2. Type has to be repeated for every argument in method definition.
3. An interface has to be defined every time we want to simulare combining two functions.
4. The type of a variable has to be specified every time even though the compiler should be able to figure it out based on assignment

The lua code goes on to create new functions:

Since eval and larger have different function signatures, we would need to create two new interfaces in Java and two class implementing them. Each class will have two methods and some member variables. In contrast the Go solution would only require a total of 4 new functions. No classes or interfaces needs to be created.

Conclusion

As stated earlier the aim of this article was to make the case for Go over Java, so you have to excuse my bias. Java has improved a lot over the years. It used to be extremely verbose for simple things like reading and writing to console. Java 5 improved upon that a great deal. But as these examples show, Java still requires a lot of boilerplate code that doesn't add anything to readability and ability to abstract or reason about the problem you are trying to solve.

I have not touched upon other clear Go advantages like compile time, channels for easing concurrency programming etc. I wanted to show that even without Go's most touted features here is a lot to gain. As new versions of Java comes out new features are added which addresses deficiencies in the language. However the problem is that gradually Java loses some of its original appeal which was that it was a very simple language. Go starts with a small feature set than present Java, perhaps more comparable to the original Java. However the features are better selected so similar kind of expressive power as todays Java can be expressed with far fewer features. I think that is worth somthing

package main
import ( "fmt")


type foo struct {
     list   []int
     num    int
     data   string
}

//Here is the initializer
func newFoo(m []int, n int, o string) *foo {
     f := new(foo)
     f.list   = m
     f.num    = n
     f.data   = o
     return f
}

func main(){
     myfoo := newFoo([]int{1,2,3}, 9, "Hello")
     fmt.Printf("%v\n", myfoo)
}

output> &{[1,2,3] 9 Hello}

func newFoo(m []int, n int, o string) *foo {
     return &foo{m,n,o}
}

It has been said that design patterns is a symptom of language deficiency. If you need a pattern that indicated a language feature should have existed instead.

Here I'd like to show how many class design patterns can be simplified in the Go programming language to look less like patterns and more like language features. This post was inspired by previous discussions online (Joe Gregorio) about how design patterns were rarely talked about in the Python community, due to the simple fact that in dynamic languages, the need for specific patterns isn't really there. The language often supports directly what you simulate with a pattern. The examples I will use will mostly be related to computer games. Meaning examples will be about classes and objects you typically find in a game engine

Command Pattern

Let's say we have a game editor which lets us place sprites in a game world.

The code below shows how we might imagine this could be done in C++. When the user click on a position, that position pos is given to a function along with the sprite which will be placed there.

class Command {
 virtual void Do() = 0;
 virtual void Undo() = 0;
};

class PlaceSpriteCmd : public Command {
 Sprite* _sprite;
 Point _oldpos, _newpos;
 
public:
 PlaceSpriteCmd(Sprite* sprite, Point pos) : 
  _sprite(sprite), _newpos(pos) 
 {
  _oldpos = sprite->position();
  
 }
 
 void Do() {
  sprite->setPosition(_newpos);
 }
 
 void Undo() {
  sprite->setPosition(_oldpos);
 }
 
};

static CommandStack _undoStack, _redoStack;

void PerformUndoableCmd(Command *cmd) {
 cmd->Do();
 _undoStack.push(cmd);
}

void UndoLastCmd() {
 Command* cmd = _undoStack.pop();
 cmd->Undo();
 _redoStack.push(cmd); 
}

void onPlaceSprite(Sprite* sprite, Point pos) {
 Command *cmd = new PlaceSpriteCmd(sprite, pos);
 PerformUndoableCmd(cmd);
}

The code is written with clarity in mind, so it is not meant to compile. It has no error checking, would probably leak memory etc.

1. Create a Command base interface.
2. For each command we need a concrete subclass of this interface.
3. Three methods have to be implemented at least in these subclasses: Constructor, Do and Undo.
4. We need to define some member variables in concrete subclass to store enough information to be able to perform the undo. E.g. in the case above we store the both current and new position to support undo and redo.

Since Go supports closures, functions are essentially first class objects which is in many ways what we simulate with Command subclasses, this becomes a lot simpler:

func MakePlaceSpriteCmd(sprite *Sprite, newpos Point) (undo, redo func()) {
 oldpos := sprite.Position()
 undo = func() { 
  sprite.SetPosition(oldpos) 
 }
 
 redo = func() { 
  sprite.SetPosition(newpos) 
 }
 
 return
}

type Command struct {
 undo, redo func()
}

var undoStack, redoStack CommandStack

func PerformUndoableCmd(undo, redo func()) {
 redo()
 undoStack.push(Command{undo, redo})
}

func UndoLastCmd() {
 cmd := undoStack.pop()
 cmd.undo()
 redoStack.push(cmd); 
}

func onPlaceSprite(sprite *Sprite, pos Point) {
 undo, redo := MakePlaceSpriteCmd(sprite, pos)
 PerformUndoableCmd(undo, redo);
}

It might not look a lot simpler, but that is mainly because of a certain fixed amount of code that has to be both places. What should hopefully be clear from the example however is that the difference becomes more noticeable as one starts adding commands. In the C++ case that involves creating a whole class.

Strategy Pattern

The main motivation behind the strategy pattern is to avoid an explosion in number of subclasses and code duplication. E.g. consider a real time strategy game with sprites for Allied tanks, Axis tanks and Soviet tanks. All the sprites are rendered differently, and might have different amounts of armor, gas tank volume etc. The tanks might have different behavior like cautious, aggressive, sneaky etc. The naive approach would be to create a subclass of the allied tank for each of those behaviors. However we would have to do this for each tank type even though the behavior code might be exactly the same. This leads to an explosion in subclasses.

Hence the use of the strategy pattern, which involves encapsulating the behavior into a separate objects and assign different behavior objects to tank objects at runtime. The previous post on Go vs Java touches upon this with the discussion of steering behaviors. Essentially steering behaviors could be thought of as the same as behaviors for sprites. The Go vs Java example shows how a language like Go with first class functions simplifies greatly the creation of strategy objects, in much the same way as we demonstrated in the Command pattern section above.

In Java and C++ we would have needed to create subclasses such as Agressive, Sneaky and Cautious of an interface, say Behavior. Go gets away with defining closures.

type Sprite struct {
 pos Point
 draw func(pos Point)
}

func (sprite *Sprite) Draw() {
 sprite.draw(sprite.pos)
}

Factory Pattern

In the Design Patterns book by the Gang of Four, different construction patterns are demonstrated using the example of a maze. The idea is that a maze consists of a number of connected rooms of different types. The reason for using some kind of factory is that we might want to change the types of rooms used but we don't want to have to change the code that creates the maze by instantiating room objects and connecting them. Here is an example of what the maze construction code might look like in C++:

void BuildMaze(RoomFactory* factory) {
 Room* a = factory->CreateRoom("Prison");
 Room* b = factory->CreateRoom("GuardRoom");
 Connect(a, b); 
}

In Go we don't need to use an instance of a class at all. It is more convenient to simply use a function object:

func BuildMaze(createRoom func(roomType string) Room) {
 a := createRoom("Prison");
 b := createRoom("GuardRoom");
 Connect(a, b); 
}

But in practice it goes beyond this. Those familiar with more dynamic OOP languages like Smalltalk and Objective-C know that classes are objects and can thus be passed around in the code. In languages like C++ and Java we usually simulate this by creating a factory class for each class we want to be able to pass around as if the class was an object.

In Go we can achieve much the same without extra code. The idiomatic way of creating an instance of a struct is to call a free function. This is because Go does not support constructors. So instead of coding constructors to instantiate structs you code free functions. The beneficial side effect of this is that because functions are first class objects, these creation functions can be passed around in similar fashion as Objective-C class objects. Constructors are not regular functions and can thus not be passed around in this fashion. Thus separate factory functions or classes needs to be created in languages like Java and C++.

Conclusion

While writing this blog entry, I tried to compare Go with Python. It became apparent that while Go can achieve a lot of the same simplicity as Python, it still can't do all patterns as simple as in Python. The most problematic pattern I noticed was subject-observer. In Joe Gregorio's presentation on the lack of design patterns in Python, it is written as this:

class Point(object): 
    def __init__(self, x, y): 
        self.x = x 
        self.y = y 

    def scale(self, n): 
        self.x = n * self.x 
        self.y = n * self.y 
def notify(f): 
    def g(self, n): 
        print n 
        return f(self, n) 
    return g 
Point.scale = notify(Point.scale) 

p = Point(2.0, 3.0) 

p.scale(2.5) 

Which can't be easily reproduced in Go. However the other patterns mentioned by Joe Gregorio: Iterator, Factory and Strategy should be just as easy as I hope I demonstrated clearly here. Another aspect which I haven't seen anybody write about in detail is lack of refactoring in Python and Ruby code bases. I am not saying it doesn't happen but I notice a couple developers who develop in both C++, Java and Ruby point out that they almost never refactor their Ruby code, while it is frequent occurrence in Java and C++. The reason being given that the need seldom seem to arise. I think it would be interesting to see in the future when more experience is gained from using Go, what the experience will be for Go. Will there be a lot of design patterns and refactoring or will the experiences be more similar to that of Python and Ruby developers?

The Go Programming Language Specificationの翻訳、10回目です。
前回までの訳はGo言語仕様[日本語訳]にまとめてあります。

ステートメント

ステートメントは実行を制御します。

Statement =
	Declaration | LabeledStmt | SimpleStmt |
	GoStmt | ReturnStmt | BreakStmt | ContinueStmt | GotoStmt |
	FallthroughStmt | Block | IfStmt | SwitchStmt | SelectStmt | ForStmt |
	DeferStmt .

SimpleStmt = EmptyStmt | ExpressionStmt | IncDecStmt | Assignment | ShortVarDecl .

StatementList = Statement { Separator Statement } .
Separator     = [ ";" ] .

ステートメントリスト(StatementList)の要素はセミコロンで区切られます。ただし直前のステートメントが次のときだけはセミコロンは省略可能です。

• 宣言リストが、閉じる丸括弧“)”で終わっているとき。もしくは、
• 閉じる波括弧“}”で終わっていて、それが式の一部ではないとき。

空ステートメント

空ステートメントは、何も行いません。

EmptyStmt = .

空ステートメントを加えることで、ステートメントリストをいつでも実質的にセミコロンで終了させることができます。

ラベル付きステートメント

ラベル付きステートメントは、goto、break、continueステートメントの宛先となります。

LabeledStmt = Label ":" Statement .
Label       = identifier .

Error: log.Fatal("error encountered")

式ステートメント

関数呼び出し、メソッド呼び出し、チャネル操作は、ステートメントの文脈内に記述することができます。

ExpressionStmt = Expression .

f(x+y)
<-ch

インクリメント／デクリメントステートメント

“++”と“–”ステートメントは、型を持たない定数1を使って、オペランドをインクリメントまたはデクリメントします。代入を伴うときは、オペランドは変数、ポインタ間接参照、フィールドセレクタ、インデックス式のいずれかでなければなりません。

IncDecStmt = Expression ( "++" | "--" ) .

以下の代入ステートメントは、同じ意味合いです。

Inc/Dec             代入
x++                 x += 1
x--                 x -= 1

代入

Assignment = ExpressionList assign_op ExpressionList .

assign_op = [ add_op | mul_op ] "=" .

左辺の各オペランドは、アドレス指定可能か、マップのインデックス式、ブランク識別子のいずれかでなければなりません。

x = 1
*p = f()
a[i] = 23
k = <-ch

代入操作 x op= yにおいて、opが二項算術演算子のとき、x = x op yと同等ですが、このときxが評価されるのは一度だけです。また、このop=はひとつのトークンを構成します。代入操作において、左辺、右辺双方の式リスト(ExpressionList)は、単一値となるひとつの式でなければなりません。

a[i] <<= 2
i &^= 1<<n

組み合わせ代入は、複数値となる操作の各要素を、変数リストに個別に代入します。これには2つの形式があります。1番目の形式では、右辺のオペランドは、関数の評価、チャネル、マップ操作、型アサーションのような、ひとつの複数値となる式です。左辺のオペランドの数は、右辺の値の数と一致しなければなりません。例えば、fが2つの値を返す関数のときは、

x, y = f()

これは、1番目の値をxに、2番目の値をyに代入します。ブランク識別子を使うと、複数値となる式から返された値を無視することができます。

x, _ = f()  // f()から返される2番目の値を無視

2番目の形式では、左辺のオペランドの数は、右辺の式の数と一致し、かつ各右辺の式はすべて単一値とならなければなりません。右辺のn番目の式は、左辺のn番目のオペランドに代入されます。このとき右辺の式が評価されるタイミングは、左辺のオペランドの何れかに代入が行われるより前に行われます。でなければ評価の順序規則から外れてしまうためです。

a, b = b, a  // aとbを入れ替え

代入において、それぞれの値は代入先オペランドの型と代入の適合性を持たなければなりません。型を持たない定数をインタフェース型の変数へ代入するとき、その定数はbool、int、float、string型いずれかの値へ変換されます。どの型になるかは、値が論理値、整数、浮動小数点、文字列型定数のどれであるかに依存します。

ifステートメント

ifステートメントは、2つに分岐したロジックを論理値型の式の値に従って実行します。式の評価結果がtrueとなるときは、if側のロジックが実行されます。falseとなるときに、elseが記述されていれば、それが伴うロジックが実行されます。条件が記述されなかったときはtrueと記述したことと同等です。

IfStmt    = "if" [ SimpleStmt ";" ] [ Expression ] Block [ "else" Statement ] .

if x > 0 {
	return true;
}

シンプルステートメント(SimpleStmt)が、式(Expression)の直前にあるときは、式が評価されるより前にシンプルステートメントが実行されます。

if x := f(); x < y {
	return x;
} else if x > z {
	return z;
} else {
	return y;
}

switchステートメント

switchステートメントは、複数に渡る分岐の実行を行います。どの分岐を実行すべきか判断するため、式または型指定と、switch内のcaseとが比較されます。

SwitchStmt = ExprSwitchStmt | TypeSwitchStmt .

switchステートメントには、式switchと型switchの2つの形式があります。式switchのcaseには、switch式の値と比較するための式が含まれます。型switchのswitchには、switch式にて特殊な形式で示された型と比較するための型が含まれます。

式switch

式switchにおいては、switchの式が評価されたあと、case式(定数である必要はない)が、左から右へ、上から下へと評価されていきます。switch式と等しい最初のcaseが見つかると、それが伴うステートメントが実行され、それ以外のcaseはスキップされます。一致するcaseがないときにdefaultケースがあれば、そのステートメントが実行されます。defaultケースは最大でも1つまでしか記述できませんが、switchステートメント内のどこにでも記述することができます。式が記述されなかったときはtrueと記述したことと同等です。

ExprSwitchStmt = "switch" [ SimpleStmt ";" ] [ Expression ] "{" { ExprCaseClause } "}" .
ExprCaseClause = ExprSwitchCase ":" [ StatementList ] .
ExprSwitchCase = "case" ExpressionList | "default" .

caseまたはdefault節内の最終ステートメントだけには、制御が次のcaseまたはdefault節の先頭ステートメントへと流れるべきであることを示す、fallthroughステートメント(§ｆallthroughステートメント)を記述することができます。これが記述されないときは、制御の流れはswitchステートメントの終わりへ移ります。

シンプルステートメント(SimpleStmt)が、式(Expression)の直前にあるときは、式が評価されるより前にシンプルステートメントが実行されます。

switch tag {
default: s3()
case 0, 1, 2, 3: s1()
case 4, 5, 6, 7: s2()
}

switch x := f(); {
case x < 0: return -x
default: return x
}

switch {  // 式が記述されていないので"true"として扱われる
case x < y: f1();
case x < z: f2();
case x == 4: f3();
}

型switch

型switchは、値の代わりに型を比較します。その他の点では、式switchとほぼ同じです。型switchは、予約語typeを型名の代わりとして使った型アサーションの形式を持つ特殊なswitch式であることによって識別されます。caseはリテラルの型と、型アサーションの式が示す動的な型とを比較します。

TypeSwitchStmt  = "switch" [ SimpleStmt ";" ] TypeSwitchGuard "{" { TypeCaseClause } "}" .
TypeSwitchGuard = [ identifier ":=" ] Expression "." "(" "type" ")" .
TypeCaseClause  = TypeSwitchCase ":" [ StatementList ] .
TypeSwitchCase  = "case" TypeList | "default" .
TypeList        = Type { "," Type } .

型スイッチガード(TypeSwitchGuard)には、省略形式による変数の宣言を含むことができます。この形式が使われるとき、各case/default節内でその変数が宣言されます。リスト(TypeList)内に型をひとつだけ指定したcase節では、この変数はcaseで指定した型を持ちます。型を複数指定したときは、変数は型スイッチガードの式が表す型となります。

caseに指定する型をnil(§事前宣言済み識別子)とすることもできます。このcaseは、型スイッチガード内の式がnilインタフェース値であるときに選択されます。

下は、interface{}型の値を返す関数fを使った、型switchです。

switch i := f().(type) {
case nil:
	printString("f() returns nil");
case int:
	printInt(i);  // i is an int
case float:
	printFloat(i);  // i is a float
case func(int) float:
	printFunction(i);  // i is a function
case bool, string:
	printString("type is bool or string");  // i is an interface{}
default:
	printString("don't know the type");
}

これは、下のように書き直すこともできます。

v := f();
if v == nil {
	printString("f() returns nil");
} else if i, is_int := v.(int); is_int {
	printInt(i);  // i is an int
} else if i, is_float := v.(float); is_float {
	printFloat(i);  // i is a float
} else if i, is_func := v.(func(int) float); is_func {
	printFunction(i);  // i is a function
} else {
	i1, is_bool := v.(bool);
	i2, is_string := v.(string);
	if is_bool || is_string {
		i := v;
		printString("type is bool or string");  // i is an interface{}
	} else {
		i := v;
		printString("don't know the type");  // i is an interface{}
	}
}

シンプルステートメント(SimpleStmt)が、型スイッチガードの直前にあるときは、型スイッチガードが評価されるより前にシンプルステートメントが実行されます。

fallthroughステートメントは、型switchにおいては許可されていません。

forステートメント

forステートメントは、ブロックの繰り返し実行を行います。繰り返しは、条件(Condition)、for節(ForClause)、range節(RangeClause)のいずれかによって制御されます。

ForStmt = "for" [ Condition | ForClause | RangeClause ] Block .
Condition = Expression .

最も単純な形式のforステートメントでは、条件の評価結果の論理値がtrueとなっている間、ブロックの実行を繰り返します。条件は繰り返しが行われる直前に毎回評価されます。条件が記述されなかったときはtrueと記述したことと同等です。

for a < b {
	a *= 2
}

for節(ForClause)によるforステートメントも条件(Condition)によってコントロールされますが、それに加えて、代入、インクリメント、デクリメントなどを行う初期化ステートメント(InitStmt)、またはポストステートメント(PostStmt)を記述できます。初期化ステートメントは省略形式による変数の宣言ですが、ポストステートメントはそうである必要はありません。

ForClause = InitStmt ";" [ Condition ] ";" PostStmt .
InitStmt = SimpleStmt .
PostStmt = SimpleStmt .

for i := 0; i < 10; i++ {
	f(i)
}

初期化ステートメントが空でなければ、繰り返しの初回に条件が評価される直前に一度だけ実行されます。ポストステートメントはブロックを実行した直後、(ブロックが実行されたときだけ)実行されます。for節の各要素は空にすることができますが、条件だけを記述した場合を除き、セミコロンの記述が必要です。条件が指定されなかったときはtrueと記述したことと同等です。

for cond { S() }    is the same as    for ; cond ; { S() }
for      { S() }    is the same as    for true     { S() }

range節によるforステートメントは、配列、スライス、文字列、マップ、チャネルから受信した値、これらの全エントリを使って繰り返しを行います。エントリ毎にまず、カレントのインデックスまたはキーをイテレーション変数に代入するか、もしくはカレントの「インデックスと要素のペア」または「キーと値のペア」をそれと対になるイテレーション変数に代入します。そのあとでブロックが実行されます。

RangeClause = ExpressionList ( "=" | ":=" ) "range" Expression .

range節の右側の式の型は、配列、スライス、文字列、マップ、配列へのポインタ、チャネルのどれかでなければなりません。チャネルのときを除いて、左辺の識別子リスト(ExpressionList)は、1～2個の式(代入と同じく、これらは変数、ポインタ間接参照、フィールドセレクタ、インデックス式のどれか)でなければなりません。各繰り返しにおいて、1番目のイテレーション変数にセットされるのは文字列または配列またはスライスのインデックス、マップのキーのいずれかであり、2番目のイテレーション変数があれば、それにセットされるのは1番目の変数と対応する文字列、配列要素、マップの値です。配列またはスライスのインデックスの型(これは常にint)、要素の型、マップのキーおよび値の型は、対応するイテレーション変数に対して代入の適合性を持っていなければなりません。

文字列を扱うとき、range節は文字列内のユニコードポイントを繰り返します。連続する繰り返しの際、インデックス用変数にセットされる値は、文字列中のUTF-8エンコードされたコードポイントの連続したバイト列の先頭のインデックスであり、2番目のint型の変数にセットされる値は、それと対応するコードポイントの値です。繰り返しの最中に無効なUTF-8シーケンスが現れたときは、2番目の変数は0xFFFD(Unicode replacement character)となり、次の繰り返しのときに文字列内を1バイト進めます。

チャネルを扱うときは、識別子リスト(ExpressionList)には、識別子がひとつだけでなければなりません。ループはチャネルがクローズされるまでチャネル上に送られた値を受信し続けますが、チャネルがクローズされるまでは、送られたゼロ値は処理されません。

イテレーション変数が、range節(“:=”)によって宣言されるとき、この変数のスコープは、forステートメントの終了までです(§宣言とスコープ)。このときこれらイテレーション変数の型は、それぞれint型と配列要素型のセット、もしくはマップのキーと値のセットのどちらかとなります。イテレーション変数がforステートメント外で宣言されているとき、その変数の実行後の値は、最後に繰り返した状態です。

var a [10]string;
m := map[string]int{"mon":0, "tue":1, "wed":2, "thu":3, "fri":4, "sat":5, "sun":6};

for i, s := range a {
	// iの型はint
	// sの型はstring
	// s == a[i]
	g(i, s)
}

var key string;
var val interface {};  // mの値の型は、valに対して代入の適合性がある
for key, val = range m {
	h(key, val)
}
// key == マップの繰り返し内で最後に現れたエントリのキー
// val == map[key]

繰り返し中に、まだ処理されていないマップエントリが削除されたときは、そのエントリが処理されることはありません。また繰り返し中に、マップエントリが追加されたときの動作は実装に依存しますが、ひとつのエントリが複数回処理されることはありません。

goステートメント

goステートメントは、独立した並列スレッドまたはゴルーチン(goroutine)として、関数またはメソッドの実行を同一アドレス空間で開始します。

GoStmt = "go" Expression .

この式(Expression)は、関数またはメソッドの呼び出しでなければなりませんが、通常の呼び出しとは異なり、プログラムは実行された関数の完了を待ちません。

go Server()
go func(ch chan<- bool) { for { sleep(10); ch <- true; }} (c)

selectステートメント

selectステートメントは通信可能な集合の中から、実行可能なものを選択します。switchステートメントに似ていますが、すべてのcaseで通信操作を行っている点が異なります。

SelectStmt = "select" "{" { CommClause } "}" .
CommClause = CommCase ":" StatementList .
CommCase = "case" ( SendExpr | RecvExpr) | "default" .
SendExpr =  Expression "<-" Expression .
RecvExpr =  [ Expression ( "=" | ":=" ) ] "<-" Expression .

selectステートメント内のすべての送信・受信式において、チャネル式(送信式の右側の式も含めて)は、上から下へと順番に評価されます。selectステートメントの結果としてcaseがひとつ以上実行可能となると、その内のひとつが選択され、それが伴う通信処理とステートメントが評価されます。どれも実行可能とならないとき、defaultケースがあれば実行されますが、defaultケースがないときは、通信のどれか1つが実行可能となるまで、ステートメントはブロックします。チャネルおよび送信式が複数回評価されることはありません。チャネルのポインタがnilのときは、selectステートメント内にそのcaseが存在しないことと同等ですが、送信のときは式だけは評価されます。

まず、selectステートメント内のすべてのチャネルおよび送信式が評価されてから、その評価の二次的作用が通信に対して起こります。

実行可能なcaseが複数あるときは、平等かつ公平に選択が行われ、実行する通信がひとつだけ決定されます。

受信のcaseには、省略形式による変数の宣言を使って新しい変数を宣言することもできます。

var c, c1, c2 chan int;
var i1, i2 int;
select {
case i1 = <-c1:
	print("received ", i1, " from c1\n");
case c2 <- i2:
	print("sent ", i2, " to c2\n");
default:
	print("no communication\n");
}

for {  // ランダムなビットシーケンスをcに送信
	select {
	case c <- 0:  // note: no statement, no fallthrough, no folding of cases
	case c <- 1:
	}
}

returnステートメント

returnステートメントは、それが記述されている関数の実行を終了し、必要であれば戻り値として単一または複数の値を呼び出し元に返します。

ReturnStmt = "return" [ ExpressionList ] .

戻り値を持たない関数のreturnステートメントは、戻り値を返してはいけません。

func no_result() {
	return
}

戻り値を持つ関数から戻り値を返すには、3通りの方法があります。

1. 戻り値として単一値または複数値がreturnステートメントで明示的にリストされます。個々の式は単一値であり、かつ対応する関数の戻り値の型と、代入の適合性を持っていなければなりません。

   func simple_f() int {
   	return 2
   }
   
   func complex_f1() (re float, im float) {
   	return -7.0, -4.0
   }

2. returnステートメントの式リストは、複数値を返す関数の(一回の)呼び出しです。これは関数から返されたそれぞれの値が、適切な型を持ったテンポラリの変数に代入され、その変数がreturnステートメントにリストされるかのように振る舞います。そのあとは、前のケースで説明した規則が当てはまります。

   func complex_f2() (re float, im float) {
   	return complex_f1()
   }

3. 関数の戻り値のパラメータに名前をつけているときは、returnの式を空にすることができます(§関数型)。戻り値パラメータは、通常のローカル変数と同様に、その型のゼロ値(§ゼロ値)で初期化され、関数内で必要に応じて値の代入が行われます。returnステートメントは、これら変数に格納されている値を返します。

   func complex_f3() (re float, im float) {
   	re = 7.0;
   	im = 4.0;
   	return;
   }

breakステートメント

breakステートメントは、最も内側にあるfor、switch、selectステートメントの実行を終了します。

BreakStmt = "break" [ Label ].

ラベルが指定されているときは、そのラベルはfor、switch、selectステートメントのどれかを伴っていなければならず、breakステートメントによって、これらステートメントが終了します(§forステートメント、§switchステートメント、§selectステートメント)。

L: for i < n {
	switch i {
		case 5: break L
	}
}

continueステートメント

continueステートメントは、最も内側のforループのポストステートメントから次の繰り返しを開始します (§forステートメント)。

ContinueStmt = "continue" [ Label ].

オプションとして指定可能なラベルは、breakステートメントのラベルと同じです。

gotoステートメント

gotoステートメントは、指定したラベルを持つステートメントへ制御を移します。

GotoStmt = "goto" Label .

goto Error

gotoステートメントの実行が原因で、それまでスコープ外だった変数が、スコープ内に入るようなケースは許されません。たとえば、この例などが相当します。

goto L;  // BAD
v := 3;
L:

この例は、ラベルLへジャンプすることで、変数vの作成をスキップしてしまうため誤りです。

fallthroughステートメント

fallthroughステートメントは、式switch(§式switch)の次のcase節の先頭のステートメントへ制御を移します。このfallthroughステートメントが記述できるのは、式switch内のcaseまたはdefault節の、空ではない最終ステートメントだけです。

FallthroughStmt = "fallthrough" .

deferステートメント

deferステートメントは、deferステートメントを記述している関数自体が復帰するまでの間、指定した関数の実行を先延ばしします。

DeferStmt = "defer" Expression .

deferに指定する式は、関数またはメソッドの呼び出しでなければなりません。deferステートメントが実行される度に、関数呼び出しのパラメータは評価され、評価結果が保存されますが、関数の実行は行われません。保留された関数呼び出しは、deferステートメントを記述している関数から復帰する直前(戻り値があれば、その評価後)に、LIFOの順序で実行されます。

lock(l);
defer unlock(l);  // この関数から復帰する直前にunlockが行われる

// この関数から復帰する直前に、3 2 1 0と出力される
for i := 0; i <= 3; i++ {
	defer fmt.Print(i);
}

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.

The Go Programming Language Specificationの翻訳、9回目です。
前回までの訳はGo言語仕様[日本語訳]にまとめてあります。

式

式は、値の算出方法を規定します。値の算出はオペランドに演算子および関数を適用することで行われます。

オペランド

オペランドは、式の基本要素である値です。

Operand    = Literal | QualifiedIdent | MethodExpr | "(" Expression ")" .
Literal    = BasicLit | CompositeLit | FunctionLit .
BasicLit   = int_lit | float_lit | char_lit | StringLit .

限定付き識別子

限定付き識別子とは、パッケージ名をプレフィックスとして指定した識別子で、これにはブランク識別子は使用できません。

QualifiedIdent = [ PackageName "." ] identifier .

限定付き識別子は、別パッケージの識別子にアクセスするときに使用します。その識別子はエクスポートされていなければなりません。すなわち識別子がユニコードの大文字で始まっている必要があります。

math.Sin

複合リテラル

複合リテラルは構造体、配列、スライス、マップを構築し、評価をその都度行って新しい値を作成します。複合リテラルは、値の型と、それに続く波括弧{}でくくられた要素リストから構成されます。この要素は単一式、もしくはキーと値のペアのどちらかです。

CompositeLit  = LiteralType "{" [ ElementList ] "}" .
LiteralType   = StructType | ArrayType | "[" "..." "]" ElementType |
                SliceType | MapType | TypeName | "(" LiteralType ")" .
ElementList   = Element { "," Element } [ "," ] .
Element       = [ Key ":" ] Value .
Key           = FieldName | ElementIndex .
FieldName     = identifier .
ElementIndex  = Expression .
Value         = Expression .

このLiteralTypeは、構造体、配列、スライス、マップ型のいずれかでなければなりません(文法上、型がTypeNameと記述されたとき以外はこの制約が適用されます)。式の型は、LiteralTypeの各フィールド、または要素、またはキーの型との間で代入の適合性を持たなければなりません。このとき変換はできません。
キーは、構造体リテラルのフィールド名、配列またはスライスリテラルのインデックス式、マップリテラルのキーのいずれかとして解釈されます。マップリテラルのときは、全ての要素に対しキーを記述しなくてはなりません。また複数の要素に同じフィールド名やキー値を指定したときはエラーとなります。

構造体リテラルには次の規則が適用されます。

• キーはLiteralTypeで宣言されているフィールド名でなければなりません。
• リテラルにキーが含まれないときは、各フィールドの要素をフィールドが宣言されている順にリストしなければなりません。
• キーを持つ要素がひとつでもあるなら、全ての要素にキーを持たせなければなりません。
• リテラルにキーが含まれているときは、構造体の全フィールドに要素を持たせる必要はありません。省略されたフィールドはゼロ値となります。
• リテラルの要素リストは省略可能です。このようなリテラルはその型のゼロ値となります。
• 他のパッケージに属している構造体の非エクスポートフィールドに要素を設定しようとするとエラーとなります。

構造体を定義します。

type Point struct { x, y, z float }
type Line struct { p, q Point }

次のように記述します。

origin := Point{};                            // Pointはゼロ値
line := Line{origin, Point{y: -4, z: 12.3}};  // line.q.xはゼロ値

配列リテラル、スライスリテラルには次の規則が適用されます。

• 各要素は、配列内の位置を示す整数インデックスを持ちます。
• キーを伴った要素は、そのキーをインデックスとして使用します。キーは整数の定数式でなければなりません。
• キーを伴わない要素は、前の要素のインデックスを+1した値をインデックスとして用います。先頭の要素がキーを伴わないときは、そのインデックスはゼロです。

複合リテラルのアドレスを取得(§アドレス演算子)すると、リテラル値のインスタンスを指すユニークなポインタが生成されます。

var pointer *Point = &Point{y: 1000};

配列リテラルの長さは、LiteralType内で指定した長さです。要素数がリテラルで指定した長さに足りないとき、不足した要素にはその要素型のゼロ値がセットされます。配列のインデックスの範囲を超えたインデックス値を要素に指定するとエラーとなります。配列の長さに…と記述すると、要素の最大インデックス値に+1した値を指定したことと同じになります。

buffer := [10]string{};               // len(buffer) == 10
intSet := [6]int{1, 2, 3, 5};         // len(intSet) == 6
days := [...]string{"Sat", "Sun"};    // len(days) == 2

スライスリテラルは、元になっている配列リテラル全体を表します。そのためスライスの長さとキャパシティは、要素の最大インデックス値に+1した値となります。スライスリテラルは次の形式です。

[]T{x1, x2, ... xn}

そして次は、配列リテラルに対してスライス操作を行うショートカットです。

[n]T{x1, x2, ... xn}[0 : n]

“if”、”for”、”switch”ステートメントの条件内に、LiteralTypeとしてTypeName形式を使った複合リテラルが現れると、意味が曖昧になり構文解析に支障をきたします。これはリテラル内の波括弧{}でくくられた式と、これらのステートメントに続くステートメントブロックとの見分けがつかないためです。この稀なケースにて発生する曖昧さを解決するには、複合リテラルを丸括弧()内に記述しなければなりません。

if x == (T{a,b,c}[i]) { ... }
if (x == T{a,b,c}[i]) { ... }

次は正しく配列、スライス、マップリテラルを使った例です。

// 素数リスト
primes := []int{2, 3, 5, 7, 9, 11, 13, 17, 19, 991};

// chが母音(vowel)のとき、vowels[ch]の値はtruevowels[ch]
vowels := [128]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true, 'y': true};

// 配列 [10]float{-1, 0, 0, 0, -0.1, -0.1, 0, 0, 0, -1};
filter := [10]float{-1, 4: -0.1, -0.1, 9: -1};

// 平均律音階の周波数(Hz) (A4 = 440Hz)
noteFrequency := map[string]float{
	"C0": 16.35, "D0": 18.35, "E0": 20.60, "F0": 21.83,
	"G0": 24.50, "A0": 27.50, "B0": 30.87,
}

関数リテラル

関数リテラルは匿名関数を表します。匿名関数は関数の型および関数の本体から構成されます。

FunctionLit = FunctionType Body .

func (a, b int, z float) bool { return a*b < int(z) }

関数リテラルは変数に代入することも、直接実行することも可能です。

f := func(x, y int) int { return x + y }
func(ch chan int) { ch <- ACK } (reply_chan)

関数リテラルはクロージャです。そのため関数リテラル内から、外側の関数内で定義した変数を参照可能です。これらの変数は外側の関数と、関数リテラル間で共有され、これらからアクセス可能な限り存続します。

基本式

基本式は、単項式、二項式に与えられるオペランドです。

PrimaryExpr =
	Operand |
	Conversion |
	BuiltinCall |
	PrimaryExpr Selector |
	PrimaryExpr Index |
	PrimaryExpr Slice |
	PrimaryExpr TypeAssertion |
	PrimaryExpr Call .

Selector       = "." identifier .
Index          = "[" Expression "]" .
Slice          = "[" Expression ":" Expression "]" .
TypeAssertion  = "." "(" Type ")" .
Call           = "(" [ ExpressionList ] ")" .

x
2
(s + ".txt")
f(3.1415, true)
Point{1, 2}
m["foo"]
s[i : j + 1]
obj.color
Math.sin
f.p[i].x()

セレクタ

次の形式の基本式があります。

x.f

これは、x(またはxがポインタ型であれば*x)で表される値が持つ、フィールドまたはメソッドfを表します。識別子fは（フィールドまたはメソッドの）セレクタと呼ばれます。セレクタはブランク識別子であってはなりません。この式の型はfの型です。

セレクタfは、型Tのフィールド/メソッドfを表すか、もしくはT内でネストしている匿名フィールドのフィールド/メソッドfを表します。fに到達するまで渡り歩いた匿名フィールドの数は、Tにおけるfの深さと呼ばれます。Tに直接宣言されていればフィールド/メソッドfの深さはゼロです。T内の匿名フィールドAで宣言されていればフィールド/メソッドfの深さは、Aの深さ+1となります。

セレクタには次の規則が適用されます。

1. 仮に、型Tもしくは*Tである値xがあり、Tがインタフェース型でなく、該当するフィールドまたはメソッドfが存在するならば、x.fが表すのは、T内で深さの値が最も小さいフィールドまたはメソッドfです。最も浅い深さのfがひとつだけでなければ、このセレクタは不正となります。
2. 仮に、型Iもしくは*Iである値xがあり、Iがインタフェース型で、かつ該当するメソッドが存在するならば、x.fが表すのは、xに割り当てられている値が持っているfという名前の実メソッドです。xに値がないかnilのとき、x.fは不正となります。
3. これら以外のケースでは、x.fは不正となります。

セレクタは自動的にポインタの間接参照を行います。xがポインタ型のとき、x.yは(*x).yの簡略形として使用可能です。yも同じくポインタ型のとき、x.y.zも同様に(*(*x).y).zの簡略形です。
ただし、*xがポインタ型のときは、明示的に間接参照を行わなければなりません。これは自動間接参照が行われるのは１レベルだけだからです。例えば、T型の値xが*Aとして宣言された匿名フィールドを含んでいるとき、x.fは(*x.A).fの簡略形です。

例文のために、宣言を行います。

type T0 struct {
	x int;
}

func (recv *T0) M0()

type T1 struct {
	y int;
}

func (recv T1) M1()

type T2 struct {
	z int;
	T1;
	*T0;
}

func (recv *T2) M2()

var p *T2;  // with p != nil and p.T1 != nil

次のように記述します。

p.z         // (*p).z
p.y         // ((*p).T1).y
p.x         // (*(*p).T0).x

p.M2        // (*p).M2
p.M1        // ((*p).T1).M1
p.M0        // ((*p).T0).M0

インデックス

次の形式の基本式があります。

a[x]

これは、配列、スライス、文字列、マップa内の、xでインデックス指定された要素を表します。このxの値は、インデックスまたはマップのキーと呼ばれます。これには次の規則が適用されます。

仮にaが、配列型の型Aまたは*A、もしくはスライス型の型Sの値であるとします。

• xは整数値で、0 <= x < len(a)でなければならない
• a[x]はインデックスxの位置にある配列要素であり、a[x]の型はAの要素型である

仮にaが、文字列型である型Tの値であるとします。

• xは整数値で、0 <= x < len(a)でなければならない
• a[x]はインデックスxの位置にあるバイトであり、a[x]の型はbyte型である
• a[x]には値を代入できない

仮にaが、マップ型である型Mの値であるとします。

• xの型は、Mのキーの型と互換性を持つ必要があり、かつこのマップはxをキーとするエントリを持っていなければならない
• a[x]は、マップ内のxをキーとする値であり、a[x]の型はMの値の型である

これ以外のa[x]は不正となります。また、インデックスまたはキーが範囲外であるときは、たとえインデックス式としては正しくても、ランタイム例外が発生します。

ただし、インデックス式がマップであるときは、次の形式を使ってmap[K] V型であるマップaから代入または、変数の初期化を行えます。

r, ok = a[x]
r, ok := a[x]
var r, ok = a[x]

このインデックス式の結果として、(V, bool)型の2つの値が返されます。指定したキーがマップ内に存在したときは、この式は(a[x], true)を返します。存在しない時は、(Z, false)を返します。このZはV型のゼロ値です。このときは、ランタイム例外は発生しません。上の例のように、このときのインデックス式は、値と成否を返すような関数を呼び出したのと同様に振舞います。 (§代入)

同様に、マップに代入するときは、次の特殊な形式を使うことができます。

a[x] = r, ok

このとき、論理値であるokの値がfalseであれば、キーがxであるエントリはマップから削除されます。okの値がtrueであれば、通常通りマップに要素が代入されます。

スライス

文字列、配列、またはスライス自身をスライスすることで、部分文字列、または部分配列の参照を作ることができます。スライスを行うときは、結果として得たい要素をインデックス式で選択します。得られる結果は0から始まるインデックスを持ち、長さはスライスするときに指定した2つのインデックス値の差と等しくなります。次は配列aのスライスです。

a := [4]int{1, 2, 3, 4};
s := a[1:3];

このスライスsの型は[]intであり、長さは2、キャパシティは3です。要素の値は次となります。

s[0] == 2
s[1] == 3

スライスの長さはマイナス値にはなりません。また配列または文字列のスライス作成時のインデックス[lo:hi]が、「 0 <= lo <= hi <= 長さ」を満たしていなくてはなりません。スライスからスライスを作成するときは、上限値は長さではなくキャパシティとなります。

スライスする対象が、文字列またはスライスのとき、スライスの結果は文字列もしくは同じ型のスライスになります。しかしスライスの対象が配列のときは、スライスの結果は、その配列の要素型と同じ要素型を持ったスライスになります。

型アサーション

式xおよび型Tがあると仮定して、次の基本式をみてください。

x.(T)

この式は、xはゼロ値ではなく、かつxにはT型の値が格納されていると断定します。このx.(T)という表記は、型アサーションと呼ばれます。このときのxの型はインタフェース型でなければなりません。

より明確にすると、Tがインタフェース型でないときx.(T)は、xの動的な型とTが同一の型であることを表しています。（§型の同一性と互換性）。もし、Tがインタフェース型のときx.(T)は、xがインタフェースTを実装している動的な型であることを表します（§インタフェース型）。

型アサーションが有効であれば、その式が表す値は、xに格納されている型Tの値となります。ただし型アサーションに失敗したときはランタイム例外が発生します。これらを言い換えると、正しいプログラムにおいては、xの動的な型が実行時にしか分からなくともx.(T)がTになりうることだけは分かっているということです。

型アサーションが代入、または初期化で使われるときは次の形式になります。

v, ok = x.(T)
v, ok := x.(T)
var v, ok = x.(T)

このアサーションの結果として、(T, bool)型の2つの値が返されます。アサーションに成功したときは、この式は(x.(T), true)を返します。失敗したときはこの式は(Z, false)を返します。このZはT型のゼロ値です。このときは、ランタイム例外は発生しません。上の例のように、このときの型アサーションは、値と成否を返すような関数を呼び出したのと同様に振舞います。 (§代入)

呼び出し

下は、F型の関数であるfの式です。

f(a1, a2, ... an)

これは引数、a1, a2, ... anを伴なうfの呼び出しです。1つの特例を除いて、各引数は単一値となる式であり、その値はFのパラメータの型と代入の適合性を持つ必要があります。これらの引数の式は関数の呼び出し前に評価されます。この式の型は、Fの戻り値の型となります。メソッドの実行も同様ではありますが、メソッドは、そのメソッドのレシーバの型の値に対するセレクタとして指定されます。

Atan2(x, y)    // 関数の呼び出し
var pt *Point;
pt.Scale(3.5)  // レシーバptによるメソッドの呼び出し

特例として、関数またはメソッドgの戻り値と、別の関数またはメソッドであるfの各パラメータの数およびそれらの代入の適合性が一致していれば、f(g(parameters_of_g))の呼び出しによって、gの戻り値をfのパラメータとして順に代入したのち、fが実行されます。ただし、fの呼び出しにはgからの戻り値以外のパラメータを指定することはできません。またfの最後のパラメータが…のときは、fの戻り値のうち通常の代入を行った残りがそこに代入されます。

func Split(s string, pos int) (string, string) {
	return s[0:pos], s[pos:len(s)]
}

func Join(s, t string) string {
	return s + t
}

if Join(Split(value, len(value)/2)) != value {
	log.Fatal("test fails")
}

メソッド呼び出しx.m()は、x(の型)のメソッド群がmを含んでいて、かつ引数リストがmの引数リストと代入の適合性があるときに有効となります。またxがアドレス指定可能であり、&xのメソッド群がmを含んでいるならば、x.m()は、(&x).m()の簡略形として使用可能です。

var p Point;
p.Scale(3.5)

これ以外のメソッド型やメソッドリテラルはありません。

…パラメータの解析

関数fが…パラメータを持つとき、…は常に一番最後の仮パラメータとなります。fの呼び出しのとき、…より前の引数は通常通り扱われます。それらのパラメータのあとに続いて現れた任意数(ゼロも含む)の引数が…パラメータにバインドされます。

f関数内では…パラメータは、静的な型interface{} (空インタフェース)を持ちます。
各呼び出しにおいて、このパラメータの動的な型は、呼び出し時に並べられた引数を連続したフィールドとして持つ構造体となります。つまり、…に与えられた実引数が構造体にラップされて、実引数の代わりとして渡されます。リフレクションインタフェースを使用すると、この動的な型から要素を取り出して、本来の実引数を得ることができます。

関数とその呼び出しです。

func Fprintf(f io.Writer, format string, args ...)
Fprintf(os.Stdout, "%s %d", "hello", 23);

このFprintf呼び出しにおいて、このargsの動的な型は概念的に、struct { string; int }となります。

特例として、関数が受け取った…パラメータを、別の関数を呼び出す際に…パラメータとして使用するときは、このパラメータは再ラップされることなくそのまま渡されます。すなわち、…仮パラメータは変更されることなく…実パラメータとして受け渡されます。

演算子

演算子はオペランドを伴って式を作ります。

Expression = UnaryExpr | Expression binary_op UnaryExpr .
UnaryExpr  = PrimaryExpr | unary_op UnaryExpr .

binary_op  = log_op | com_op | rel_op | add_op | mul_op .
log_op     = "||" | "&&" .
com_op     = "<-" .
rel_op     = "==" | "!=" | "<" | "<=" | ">" | ">=" .
add_op     = "+" | "-" | "|" | "^" .
mul_op     = "*" | "/" | "%" | "<<" | ">>" | "&" | "&^" .

unary_op   = "+" | "-" | "!" | "^" | "*" | "&" | "<-" .

比較演算子については別途説明します。それ以外の二項演算子では、チャネル、シフト、型を持たない定数のいずれかを伴う演算子を除き、オペランドの型は同じでなければなりません (§型と値の特性)。定数のみを伴う演算子については、定数式のセクションを参照ください。

チャネルの送信のときは、最初のオペランドは常にチャネルであり、2番目のオペランドは、チャネルの要素型に対して代入の適合性を持つ値でなくてはなりません。

シフト演算を除き、一方のオペランドが型を持たない定数で、もう一方がそれ以外のときは、定数のオペランドが相手側のオペランドの型に変換されます。

シフト演算の右側のオペランドは符号なし整数型か、もしくは符号なし整数型に変換可能で型を持たない定数でなければなりません。

定数とならないシフト演算の場合で、左側オペランドが型を持たない定数であるときは、その定数の型はシフト演算自体を左側オペランドひとつと置き換えてみたときに得られる型となります。

var s uint = 33;
var i = 1<<s;          // 1はint型
var j = int32(1<<s);   // 1はint32型で、j == 0
var u = uint64(1<<s);  // 1はint64型で、u == 1<<33
var f = float(1<<s);   // 不正。1はfloat型で、シフト不可
var g = float(1<<33);  // 正しい。1<<33はシフト演算の定数で、g == 1<<33

演算子の優先順位

単項演算子は高い優先順位を持っています。++と--演算子は、式ではなくステートメントを構成するため演算子のグループからは除外されています。そのためステートメント*p++は、(*p)++と同じです。

二項演算子には、6つの優先順位レベルがあります。乗算演算子は最も強く、それに続いて加算演算子、比較演算子、<- (チャネル送信)、&&(論理積)、最後が ||(論理和)です。

優先順位         演算子
    6             *  /  %  <<  >>  &  &^
    5             +  -  |  ^
    4             ==  !=  <  <=  >  >=
    3             <-
    2             &&
    1             ||

同じ優先順位を持つ二項演算子は、左から右へと対応づけされます。例で示すと、x / y * zは、(x / y) * zと同じになります。

+x
23 + 3*x[i]
x <= f()
^a >> b
f() || g()
x == y+1 && <-chan_ptr > 0

算術演算子

算術演算子は数値に対して使用します。その算出結果の型は一つ目のオペランドの型と同じになります。四則演算子(+, -, *, /)は、整数及び浮動小数点に対して使用しますが、+は文字列にも使います。その他の算術演算子は整数にのみ使います。

+    和                     整数、浮動小数点、文字列
-    差                     整数、浮動小数点
*    積                     整数、浮動小数点
/    商                     整数、浮動小数点
%    剰余                   整数

&    ビット演算 and          整数
|    ビット演算 or           整数
^    ビット演算 xor          整数
&^   ビットクリア(and not)   整数

<<   左シフト                整数 << 符号なし整数
>>   右シフト                整数 >> 符号なし整数

文字列は、+演算子、または+=代入演算子を使用して連結することができます。

s := "hi" + string(c);
s += " and good bye";

文字列の加算は、オペランドを連結することで新たな文字列を作り出します。

整数型のとき、/と%は以下の関係を満たします。

(a / b) * b + a % b == a

(a / b)は、ゼロに近づくように切り捨て／切り上げられます。例を上げますと、

 x     y     x / y     x % y
 5     3       1         2
-5     3      -1        -2
 5    -3      -1         2
-5    -3       1        -2

被除数が正の値で、除数が2の累乗の定数であるときは、その割り算は右シフトに置き換えられ、剰余の計算はビット演算のANDに置き換えられます。

 x     x / 4     x % 4     x >> 2     x & 3
 11      2         3         2          3
-11     -2        -3        -3          1

シフト演算子は、右オペランドで指定されたシフト数、左オペランドをシフトします。実装としては、シフトの左オペランドが、符号あり整数のとき算術シフト、符号なし整数のときは論理シフトが使われます。シフト数は符号なし整数でなければなりません。また、シフト数には上限がありません。シフト数nでシフトを行うとき、シフト演算は左オペランドをn回繰り返して、シフト数1でシフトしたように振舞います。シフト演算の結果として、x << 1 はx*2と同じであり、x >> 1は x/2を負の無限大の値に近づくように切り捨てた値と同じになります。

整数オペランドに対する単項演算子+、-、^は以下で示すように定義されています。

+x                          は、0 + x
-x    符号反転               は、0 - x
^x    ビットの補数           は、m ^ x (xが符号なしのとき、mの全ビットは1。
                                      xが符号ありのとき、mは-1)

浮動小数点においては、+xはxと同じであり、-xはxの符号を反転させた値です。

整数のオーバフロー

符号なし整数において、+、 -、*、<<演算子はmodulo 2ⁿ (nは、この符号なし整数型のビット幅)で計算されます(§数値型)。大雑把な解説をすると、これら符号なし整数の演算は、オーバフローした高位のビットを破棄するので、プログラム側はこの「ラップアラウンド」が行われることを期待してもよいでしょう。

符号あり整数において、+、 -、*、<<演算子はオーバフローを起こすことがあり、演算結果の値として何が返されるかは、この符号あり整数の値、演算子、オペランドにより決まります。オーバフローが起きても例外は発生しません。オーバフローは起こらないという前提のため、コンパイラはこれに関するコードの最適化は行いません。たとえば、x < x + 1が常に成り立つとは限りません。

比較演算子

比較演算子は、bool型の値を返します。演算子==と!=は、いくつかのケースを除いて配列と構造体以外のすべての型に適用できます。他の比較演算子に適用できるのは数値と文字列だけです。

==    等しい
!=    等しくない
<     小なり
<=    小なりイコール
>     大なり
>=    大なりイコール

数値型のオペランドは、一般的な方法で比較されます。

文字列型のオペランドは、バイト単位で（辞書的に）比較されます。

論理値型のオペランドは、双方がtrue 、または双方がfalseのときに等しいとみなされます。

複合型の比較の規則は、§比較の適合性にて解説します。

論理演算子

論理演算子は論理値に適用され、オペランドと同じ型で結果を返します。右オペランドが評価されるかどうかは条件によります。

&&    and条件    p && q  is  "if p then q else false"
||    or条件     p || q  is  "if p then true else q"
!     否定       !p      is  "not p"

アドレス演算子

アドレス演算子&は、オペランドのアドレスを生成します。このときオペランドはアドレス指定可能でなければならず、また変数、ポインタの間接参照、配列またはスライスのインデックス操作、アドレス指定可能な構造体のフィールドセレクタのいずれかでなければなりません。関数の戻り値はアドレス指定可能ではありません。オペランドとしてポインタ型を取るポインタの間接参照演算子*は、オペランドによって指し示されている値を取り出します。

&x
&a[f(2)]
*p
*pf(x)

通信演算子

チャネルという用語は「チャネル型の値」を意味します。

送信操作には、二項演算子“<-”を使用します。この演算子はチャネルと値(式)に作用します。

ch <- 3

送信操作によって、チャネル上に値を送信します。チャネルと式は通信を開始する前に評価されます。通信は、送信が実行可能となるまでブロックされ、可能になると値はチャネルに送られます。バッファリングされていないチャネルへの送信は、受信側の準備ができているときに実行可能です。バッファリングされているチャネルへの送信は、バッファに空きがあるときに実行できます。

送信操作が、式のコンテキスト中に現れるならば、その式の値は論理値であり、操作はブロックされません。通信が行われたときは、その論理値の値はtrueとなります。行われなかったときはfalseになります。(成否とは関係なく、チャネルと送信される式は評価が行われます。)
次の2つの例は等しい内容です。

ok := ch <- 3;
if ok { print("sent") } else { print("not sent") }

if ch <- 3 { print("sent") } else { print("not sent") }

言い換えるなら、プログラムが送信操作の値をチェックするときは、送信はブロックされず、その式の値は操作の結果となります。プログラムで値をチェックしなければ、それが行われるまで操作はブロックし続けます。

受信操作には、単項演算子“<-”を使用します。この式の値は受信した値であり、その型はこのチャネルの要素型です。

<-ch

値が利用可能になるまで式はブロックされ、そのあとは変数に代入するなど、他の式と同じように利用できます。受信した値を受け取らなければ、その値は破棄されます。

v1 := <-ch
v2 = <-ch
f(<-ch)
<-strobe  // クロックパルス待ち

受信式が代入、または初期化で使われるときは次の形式になります。

x, ok = <-ch
x, ok := <-ch
var x, ok = <-ch

この受信操作のときはブロックされません。受信操作が実行できるときは、論理値型の変数ok にtrue が、xには受信した値が格納されます。そうでなければokにはfalse がセットされ、xにはその型のゼロ値がセットされます。(§ゼロ値）

メソッド式

メソッドMが、型Tのメソッド群に含まれているとき、Mの引数リストの先頭にこのメソッドのレシーバを加えることで、 T.Mを普通の関数として呼び出すことができます。

MethodExpr    = ReceiverType "." MethodName .
ReceiverType  = TypeName | "(" "*" TypeName ")" .

2つのメソッド、Mv(レシーバは型 T)とMp（レシーバは型*T)を持つ構造体型Tについて考えてみます。

type T struct {
	a int;
}
func (tv  T) Mv(a int)   int   { return 0 }  // 非ポインタのレシーバ
func (tp *T) Mp(f float) float { return 1 }  // ポインタのレシーバ
var t T;

次の式をみてください。

T.Mv

これは、Mvメソッドとは等しいですが、必ず引数の先頭にレシーバを持った関数です。この関数のシグネチャは、次のようになります。

func (tv T, a int) int

この関数は明示的にレシーバを指定することで、通常通り呼び出すことができます。下の3つの呼び出しは等価です。

t.Mv(7)
T.Mv(t, 7)
f := T.Mv; f(t, 7)

次の同じような式をみてください。

(*T).Mp

これは、Mpメソッドを表す関数値であり、次のシグネチャを持っています。

func (tp *T, f float) float

非ポインタのレシーバを持つメソッドから、ポインタのレシーバを持った関数を得ることができます。これは次のようになります。

(*T).Mv

これは、Mv メソッドを表す関数値であり、次のシグネチャを持っています。

func (tv *T, a int) int

このような関数では、本来のメソッドのレシーバへ受け渡す値を得るためにレシーバを間接参照します。メソッドは、関数呼び出しで渡されたこのアドレスの値を上書きすることはありません。

最後のケースとして、ポインタのレシーバを持つメソッドを、非ポインタのレシーバ関数として使用することはできません。なぜならポインタのレシーバを持つメソッドは、この型のメソッド群には含まれていないからです。

メソッドから取得した関数の値は、関数の呼び出し構文によって呼び出されます。このときレシーバは、呼び出しの引数の先頭に与えられます。つまり、f := T.Mvのとき、fはt.f(7)ではなく、 f(t, 7)として実行します。レシーバにバインドする関数を作成するには、クロージャを使ってください。

インタフェース型のメソッドから関数の値を引き出すこともできます。結果得られる関数は、そのインタフェース型のレシーバを必ず受け取ります。

変換

変換とは、Tが型であり、xが型Tへ変換可能な式であるとき、T(x)で表される式です。

Conversion = LiteralType "(" Expression ")" .

一般的に変換は、xの値が型Tと代入の適合性を持っているとき、あるいは値と型Tが代入の整合性をとりうるとき、あるいは値の型、T、またはこれらのコンポーネント型が名前を持たないときに成功します。通常、このような変換は、xの値でなく型を変更するため、実行時にはコストがかかりません。

変換規則は、Tが数値型または文字列型である変換に適用されます。これらの変換によって値の内容が変わったり、実行コストが増えたりする可能性があります。

整数型間の変換

値が符号を持った数値であるならば、無限精度まで暗黙的に符号拡張されます。さもなければ、その値はゼロ拡張されます。そのあとで変換結果となる型に合うように精度が切り捨てられます。たとえば、x := uint16(0x10F0)ならば、uint32(int8(x)) == 0xFFFFFFF0になります。変換の結果は常に有効な値となり、オーバフローは起こしません。

浮動小数点型を含む変換

1. 浮動小数点数を整数に変換するとき、小数部は捨てられます（ゼロに近づくよう切り捨て／切り上げ）。
2. 数値を浮動小数点型に変換するとき、結果となる値はその浮動小数点型で規定されている精度に丸められます。たとえば、float32型の変数xの値は、格納されるときIEEE-754 32ビットの数値以上の精度が使われます。しかし、float32(x)が表すのは32ビットに丸められたxの値です。同様に、 x + 0.1は32ビット以上の精度が使われますが、float32(x + 0.1)はそうなりません。

浮動小数点値を含んでいるすべての変換において、結果となる型が値を表現することができなければ、変換自体は成功しますが、結果となる値は実装依存となります。

文字列への変換

1. 整数値を変換することで、その整数が表すUTF-8文字を持つ文字列が得られます。

   string(0x65e5)  // "\u65e5" == "日" == "\xe6\x97\xa5"

2. 整数のスライスを変換することで、各整数を文字列へ変換したあと結合した文字列が得られます。スライスの値がnilであれば、結果は空文字列になります。

   string([]int{0x767d, 0x9d6c, 0x7fd4})  // "\u767d\u9d6c\u7fd4" == "白鵬翔"

3. バイトのスライスを変換することで、スライス内の連続したバイトデータをそのまま持った文字列が得られます。スライスの値がnilであれば、結果は空文字列になります。

   string([]byte{'h', 'e', 'l', 'l', 'o'})  // "hello"

ポインタと整数間で変換を行う仕組みは言語上はありません。ただしunsafeパッケージでは、ある程度の制限はありますがこの機能を実装しています。

定数式

定数式は、定数オペランドだけを含み、コンパイル時に評価される式です。

論理値型、数値型、文字列型定数がオペランドとして合法的に使えるときは常に、型を持たない論理値型、数値型、文字列型定数をそれぞれオペランドとして使用できます。シフト演算を除き、二項演算のオペランドが型を持たない整数定数と、同じく型を持たない浮動小数点定数であるとき、整数定数は型を持たない浮動小数点定数に変換されます（/と%がこれに相当します）。

結果がbool型となる比較演算子を除き、型を持たない定数に演算子を適用した結果は、同種(すなわち、論理値型、整数型、浮動小数点型、文字列型定数いずれか）の型を持たない定数となります。

定数式は、常に正確に評価されます。そのため評価中の値と定数は、言語でサポートされている事前定義済みの型よりかなり大きな精度を必要とするかもしれません。よって以下は、正しい宣言です。

const Huge = 1 << 100;
const Four int8 = Huge >> 98;

型を持っている定数の値は常に、その定数の型の値を正確に表せなければなりません。よって以下の定数式は正しくありません。

uint(-1)       // -1はuintでオーバフローを起こす
int(3.14)      // 3.14はintegerで切り捨てられる
int64(Huge)    // 1<<100はint64でオーバフローを起こす
Four * 300     // 300はint8でオーバフローを起こす
Four * 100     // 400はint8でオーバフローを起こす

単項のビット補数演算子^を使用したマスクは、非定数の規則と適合します。このマスクは符号なし定数のときは全て1に、符号あり、または型を持たない定数のときは-1になります。

^1          // 型を持たない整数定数。-2に等しい
uint8(^1)   // エラー。 uint8(-2)と同じで、範囲外
^uint8(1)   // uint8型の定数。0xFF ^ uint8(1) = uint8(0xFE)となる
int8(^1)    // int8(-2)と同じ
^int8(1)    // -1 ^ int8(1) = -2となる

評価の順番

代入または式の要素を評価するときには、全ての関数呼び出し、メソッド呼び出し、通信操作は、字句ごとに左から右へと順に評価されます。

代入例です。

y[f()], ok = g(h(), i() + x[j()], <-c), k()

これら関数の呼び出しと通信は、f()、 h()、 i()、 j()、 <-c、 g()、k()の順で起こります。しかし、これら関数呼び出しと通信の順番は、xのインデックス指定と評価、およびyの評価と比べると未定義です。

単一式中の浮動小数点演算は、演算子がもつ結合法則に従って評価されます。明示的な括弧は、規定の結合法則を上書きすることで評価に影響を及ぼします。式x + (y + z)では、xを加える前にy + zの加算が行われます。