オレオレLisp処理系を実装してみた(感想)

SICP4章が「Lisp実装しようぜ」なのですが、本ではSchemeでLispを実装するというメタサーキュラーなevalを作ってて、実装言語と被実装言語の境目をちゃんと理解できるか不安だったのでC++で実装してみる、ということをやってみました。
やってみたら意外と簡単で、足りないところは多々ありますが3日でLispとしてとりあえず動くようになりました。
(実装メモ1日目、2日目、3日目)

以下は今回の実装を体験してわかったこととか感想とかです。

オレオレLisp処理系を実装してみた(3日目=最終日)

Lisp処理系の実装メモ3日目です。(1日目, 2日目)

実装メモとしてはこれが最終日になりますが、感想などのまとめを次の記事としてのせるつもりです。

例によってコードは一番下に載せてます。

オレオレLisp処理系を実装してみた(2日目)

Lisp処理系の実装メモ2日目です。(1日目、3日目)

例によって最後にその日の最後の時点くらいのコードを載せますが、
結構がっつり書き換えたりしてるんで、あんまりメモ内の記述と整合性がないかもしれません。あくまで参考ということで。

オレオレLisp処理系を実装してみた(1日目)

この週末でLisp処理系をスクラッチから作ってみたので、そのときのメモをアップしていきいます。
この記事はその初日のメモです。(2日目、3日目)

あんまり推敲もしてないので読みにくいかもしれません。
その日のコードは最後に Gist を貼っておきます。

Schemer のための「すぐ理解できるYコンビネータ」

ラムダ計算の説明などによく登場するYコンビネータ(不動点コンビネータ)ですが、
「ラムダだけで再帰関数を定義できる」というのはわかってもYコンビネータを使った関数の定義は複雑ですし、
そもそもYコンビネータ自体の定義からしてどうなってるのかよくわからないので、少し難解です。

しかし、Schemer (Schemeプログラマ) 向けには簡単に理解できる説明があります。
Scheme でよく使う call-with というイディオムがありますが、これを使うことで
「Yコンビネータとは call-with-myself である」と言えるのです。

具体例で説明します。

自分が書いているプログラムが正しく動くと信じてプログラムを書く感覚

次のような記事が話題になっていたんだけど、少し感じるところがあったのでメモっとく。ただの自分の感覚なので、結論とかは特にない。

『難しいプログラムでは自分がいままで書いたコードが正しく動くと信じて残りのコードを書く必要がある -- Medium』

多分この元記事の方は複雑なプログラムのことについて言っていて、俺の考えてるような単純な例ではなかろうと思うんだけど、自分の場合は結構単純なプログラムであっても再帰が関わってくるとそう感じる場合がある。単純にループにできそうにないやつ（本質的に再帰的なやつ）とか。

例えば Scheme でリストの長さを返す関数 length は次のように定義できる。

(define (length lst)
 (if (null? lst)
     0
     (+ 1 (length (cdr lst)))))

これも実際には再帰呼出しのlengthを書くところではlengthが正しく動くことを信じて書いてるわけではあるけど、再帰呼出しのlengthが最後に出てくるので（末尾再帰という意味ではなくて記述上の順番として）、これまで書いた部分が正しいという確信を得やすいのもあって、あんまり「 length が正しく動くかどうかわかんないけど正しく動くと信じて書く」って感覚はない。（単純すぎるってのもあるかもしれんが）

次に、「同じくリストの長さを返す関数、ただしリストの最後から連続した偶数要素の部分がある場合その長さはカウントしない」という関数 length2 を考えてみる。

例えば

(length2 '(1 2 3 4 5)) => 5
(length2 '(1 2 3 4 5 6)) => 5
(length2 '(1 2 3 4 5 6 6 6)) => 5
(length2 '(1 2 3 4 5 6 6 6 7)) => 9

のような感じだ。

length2 を再帰で書くとこうなる:

(define (length2 lst)
 (if (null? lst)
     0
     (let ((rest (length2 (cdr lst))))
       (if (and (zero? rest)
                (even? (car lst)))
           0
           (+ 1 rest)))))

# リストの要素が数字じゃない場合とかの処理は本質じゃないので割愛

こういう場合に (let ((rest (length2 (cdr lst)))) の部分を書くときは、「length2はまだ完成してないんだけど、これから書く部分も含めて全部正しく動くはずだぜ」という感覚を強く感じながら書いてる。

まぁlength2も蓄積変数を1個余分に導入するだけで簡単にループにできそうですけどね。

『プログラミングGauche』を読んだ

フムフムヌクヌクアプアア本としても知られる『プログラミングGauche』を最近読みました(今3周目を読んでます)。

読後の感想ですが、ひとことで言えば『Scheme すごい、Gauche 楽しい』って感じです。
プログラミング自体の初心者には向きませんが、ほかの言語を知っていれば難易度の勾配もゆるやかで、無理なく読み進められる良い本だと思います。

とくに面白かったのは7章（手続き）、18章（マクロ）、 19章（継続）あたりです。
関数プログラミングに触れたことがない人は、7章まで読むとその面白さを体験できると思います。Common Lispを触ったことがある自分でも、Lisp-1での関数プログラミングの気持ちよさは特筆すべきものがありました。あとLispのパワーを顕著に体感できるのが18,19章です。こういうのを知ってしまうと Scheme ならアレができるのに、とか思ってしまいそうです。

以下、Scheme/Gauche/本書に関して面白かったところとかをつらつら書いてみます：

gitworkflows(7)を図解したスライドをアップしました

前回に引き続き、こちらも会社の読書会でGit関連本の番外編として実施したgitworkflows(7)の解説資料（の加筆修正版）です。

マニュアルからすると講義用にかなりつまみ食い的な内容になってます。
副読本的な位置づけでマニュアルを読むのも良いかなと思います。

Gitの布教などにお使いください。

コンセプトから理解するGitコマンド

Gitのコマンドってわかりにくい、というかとっつきにくいものや、役割が複数あって覚えにくいものとか多い気がします。

でもGitが内部でデータ(コミットやツリー、ブロブ等いわゆるGitオブジェクト)をどのように扱っているかを理解すると、コマンドの役割や挙動の理解も進むのでは、と思ってスライドを作りました。

Git 2.0 rc1

先日(2014/04/26) Git 2.0 の rc1 (Release Candidate 1) がテスト用に公開されました。

来るリリースに向けた変更点で大きいのは、やはり 1.9 までとの非互換性です。具体的には

• ブランチ指定なしで git push した場合のデフォルトの挙動が 'simple' になった
• サブディレクトリで git add -u または git add -A したとき（pathを明示的に指定しない場合）、ツリー全体が対象になった
• git add <path> したとき(<path>を明示的に指定したとき)の挙動が git add -A <path> と同じになった

あたりです。(実は小さな非互換な変更が別にひとつあります。詳細はリリースノート草稿をどうぞ)

1番目はすでにいろいろなところで記事になっていて有名ですね。私としてはブランチ指定なしのpushをあまりしないので、特にどちらの挙動が便利という感覚はありませんが、simpleのほうが安全なデフォルトだと思います。

2番めは git commit などの挙動との一貫性という意味で、より統一された挙動になっています。

3番目はファイルを削除したあとでそのファイル削除をステージしたい場合、 git add <削除したファイル> とする(あるいはそれを含むディレクトリを指定する)だけで削除をステージできます。これまではgit add -A <削除したファイル> とするか、 git rm <削除したファイル>が必要でした。
ステージングには git add <path> だけで対応できるようになり、 git addはより「ステージングのためのコマンド」という性格が強くなったようにも思います。
削除だけではなく 非追跡ファイルも追加される、という点には注意が必要ですが、そうしたくなければもともと -u オプションがあるわけですから、特に先入観のない初心者にとって受け入れやすい挙動になったのではないでしょうか。

コマンドやオプションのややこしさを指摘されることもあるGitですが、今回のような非互換性を伴う変更を乗り越えて改善を続けており、今後の進化も期待が持てます。

なお、今回の非互換性の導入については、2.0での変更に向けてかなり以前から関係する挙動に警告を表示するなど、既存ユーザに配慮した移行がなされました。これは1.6の頃に非互換な変更を導入した際の反省に基づくものだそうです。

他に1.9から追加された機能で個人的に気になるものとしては、

• git rebase で '-' が '@{-1}' なブランチ名として解釈されるようになった(タイプ数が減るのは嬉しい。)
• git config で --file - を指定すると値を標準入力から読み取れるらしい(スクリプティングなどで使う機会があるかも？)
• git commit 時に常にGPG署名するための設定 "commit.gpgsign" が追加された。(これが必要な環境ってちょっと怖い。毎コミットについて改ざんも否認もできなくなるので嬉しいシチュエーションもありそう)
• "pull.ff" 設定で pull --no-ff や pull --ff-only をデフォルトの挙動にできる。(ff-onlyは非メンテナ作業時 = ほとんどの場合に便利)

あたりでしょうか。(勘違いしてる可能性もあるので、正確にはリリースノート草稿を参照してください。他にもたくさんの新機能が導入されていますので、それらについてもリリースノート草稿を確認してもらうのが良いと思います)


さて、このまま大きな不具合などがなければ5月の中旬から下旬あたりには 2.0 正式リリースになると思います。今から楽しみですね。

「Git 2.0 がリリースされた」というデマ

「Git 2.0がリリースされた」という話がtwitterで広まっていましたが、2014/03/14現在、実際にはリリースされていません。
(2014/04/27追記: 2.0-rc1がリリースされましたので、もうすぐ本当に2.0がリリースされます→日本時間で5/29に当初予定より約2weekおくれでリリースされました)

「Git 2.0のリリースノート」「Git 2.0がもうすぐリリースされる」はまだしも、「Git 2.0がリリースされた」は完全に誤りです。

twitterで検索したところ、的確な内容をつぶやいているのは数人の方だけのようでした。正しい内容を最も端的に指摘されていたのは @uu59 さんの

次バージョンのためにrelnote用意するのはgitの伝統なので2.0リリースはまだ数ヶ月は先だと思います https://t.co/axdjeIRZlF https://t.co/pZNHot2V6T
— ゆーごく (@uu59) March 13, 2014

だと思います。

これまでと同じようなリリース間隔(12weekごと)であれば、順調にいっても2.0のリリース時期は5月の第2週以降になりそうです。
2.0 のリリースノートについても実際に 2.0 がリリースされるまでには新機能・バグフィックスに関する記述が追加されていくと思いますので、今回話題になった時点のドラフト版とは厳密には異なるものになります。

ただ、今回の件は海外でも釣られた人が多かったようで、「2.0がリリースされた」と記事にしてしまったニュースサイトもありました。ドラフト版リリースノートという、それらしい証拠っぽく見えるものがあったので釣られた人も多かったのかなと思います。

なお、1.8 シリーズまでは機能リリースが 1.8.x で、バグフィックスリリースが 1.8.x.y というバージョン番号が付けられていました。
先日リリースされた 1.9 シリーズもそうなるのかなと思っていたのですが、次回機能リリースが 2.0 (2.0.0) となると(※)、付与規則が変わったんですかね？

※ 2.0までマージしない約束になっていた、これまでとは互換性のない挙動を導入するトピックがnextからmasterにマージされたので、次回の機能リリースが2.0なのは確定のはずです。

2014/03/20追記:
やはり1.9シリーズからバージョン番号付与規則が変更されたそうです。これまでのバージョン番号はw.x.y.zでメンテナスリリースではzを、機能リリースではyを、大きな変更を伴う機能リリースではxを増加させ、wは本当に大きな変更のために予約されてきましたが、x.yzで十分じゃね?という話になったようです。1.9.1リリースの話とともに詳しい記述がメンテナHamanoさんのブログ記事 Git Blame: Git 1.9.1 にあります。

Gitで特定の関数の変遷だけを確認する(git log -L)

最近知ったのですが、 git log では特定の関数の歴史だけを見ることができます(たぶんGit 1.8.4 以降)。

やり方は
git log -L :<regex>:<file>
これだけです。git showのように、コミットメッセージとともに、<file>中で最初に<regex>にマッチする関数に関してのみdiffを表示してくれます。diffは関数の途中で省略されず、全体を1ハンクに収めるかたちで、見やすく表示されます。
-L オプションは複数回指定可能です。

関数名は現在のHEADの<file>の内容の中でマッチするものを指定する必要があります。HEADの内容でマッチさえすれば、歴史をたどっていく途中で関数名が変わっても、コンテキストから推測して最後まで(初めてその関数を追加したコミットまで)追跡してくれるようです。

どの言語における関数にも対応しているかどうかは確認していませんが、-L には <start>,<end>:<file> という指定も可能で、前述の書式では指定が難しい場合にも細かく開始地点と終了地点を指定できます。(<start>, <end>にはファイル内の行数、正規表現、オフセットなどが使えます)

うーん便利。

Gitで今作ったコミットを以前のコミットに半自動的に融合させる(rebase autosquash)

よく「トピックブランチにおけるコミットは、トピックに関連した内容のみ、論理的単位で小さく作れ」といわれますが、実際にコードを書いているときは最初から完璧だと思える一連のコミットをつくり上げるのは非常に困難です。

たとえば、「あー、この変更はさっきのコミットに含めておくべきだったな」とか。

コンフリクトしたマージの解消作業を再利用する(git-rerere)

前回や前々回の記事では、nextのようなブランチを再構成する利点を解説しましたが、「再構成の利点はわかったけど、コンフリクトしたマージはrebaseしたらどっかいっちゃうのでできるだけやりたくない」という人も多いかと思います。

実はgitにはコンフリクトしたマージの解消方法を記録して、同じコンフリクトに対しては同じ解消方法を自動的に適用する機能があります。

それが git-rerere(1) です。rerereは REuse REcorded REsolutionの略みたいです。この機能はデフォルトでは無効になっているので、明示的に有効にしてやる必要があります。詳しい方法などは git-rerere(1) やrerereを解説したブログなどを参照すると良いと思います。

参考:
 - git-rerere(1)
 - unpushの日記: git-rerereのメモ

Gitのコミットグラフ(歴史)を綺麗に保つ効果(2)

前回に引き続き、綺麗な歴史を残す利点についてです。
今回は少し複雑な例を用います。

Gitのコミットグラフ(歴史)を綺麗に保つ効果

Gitではコミットグラフ(歴史)を綺麗にしておきやすいという特徴があります。

あまり気にしない人もいるかもしれませんが、どういったところが嬉しいのか簡単な例で説明してみたいと思います。

gitworkflowsの補足(2) - よくある誤解

gitwokflows(7)に関する補助的な解説その2です。

gitworkflowsについて、ありがちな誤解や質問について妄想してみました。なお、これはgitworkflows(7)を自分のプロジェクトに採用することを考えた場合の話で、Git本家でやっているワークフローそのものの話ではありませんのでご注意を。

gitworkflowsの補足(1) - gitworkiflowsを採用する目的

gitworkflows(7)についての補足記事です。

gitworkflowsを採用する目的、あるいはgitworkflowsを採用する利点は何よ？というところですが、これは一言でいえば「masterに綺麗な歴史を残す(残せる)」というものです。

Gitのブランチに別名をつける(symbolic-ref)

Gitのブランチに別名をつける方法を紹介します。

やり方は、

% git symbolic-ref refs/heads/<新しい名前> refs/heads/<参照先>

です。

以下解説。

gitworkflowsの補足(0) - 補助的解説など

gitworkflows(7)日本語訳の補助記事です。

git-flowでもgithub flowでもない、Git本家推奨のワークフロー

gitworkflows(7) 日本語訳です。Copyright, ライセンスは原文(Git本体)と同じです。

修正などを反映した最新版はこちらにあります。