Scheme 過去◇現在◇未来 前編 https://web.archive.org/web/20130812221924/http://www010.upp.so-net.ne.jp/okshirai/scheme-20070402222203.txt からの転載

scheme-20070402222203.txt

Scheme 過去◇現在◇未来 前編

bit/April 1996/Vol. 28, No.4 p4～9

Guy L. Steele Jr.
訳 井田昌之

----------------------------------------
はじめに ――― 訳者より

Schemeの開発者の一人であるGuy L. Steele博士が、1995年7月10日にLisp協議
会のシンポジウムで講演を行なった。場所は青学会館である。本稿は、その講
演を元にまとめたものである。その内容は、開発の当事者でしか語れないもの
が多く、たとえば、Schemeの発端のいきさつには、Carl Hewitt先生も大きく関
係している点など、訳者にとっても、なるほどと新鮮で興味深いものであった。
当時のMITの人工知能研究所のホットな様子を垣間見た気がした。

本文では敬称を略した。登場人物の肩書はどんどん変化したので、それを完全
に追跡するのは困難だったこと、また、博士の講演そのものでも、全く敬称が
使われなかったからである。

Scheme関連の研究・調査を行ないたい読者の便宜をはかれるよう、本文にはで
きるだけ、脚注として参照文献を付した。

----------------------------------------
挨拶

こんにちは、LISP協議会にお招きいただいてありがとうございます。今日は、
Scheme言語の始まりについてお話しします。また、そもそものいきさつから今
日に至るまでの歴史を議論します。今後についてもいくつか述べます。おそら
く、Common Lisp†の事をご存知な方もいらっしゃるでしょうが、Common Lisp
はたいへん大きく複雑な言語です。一方、Schemeはたいへん小さいです。今日
の話を聞いて、なぜSchemeが小さいのか、なぜCommon Lispよりエレガントだと
私が考えているか、皆さんに理解していただける事を期待します。いくつかの
明確な理由があるのです。

† 彼は、Common Lispの開発者としても有名である。Common Lispの仕様につい
ては、『Common Lisp 第二版』, 共立出版, 1991. がある。

----------------------------------------
その発端 ――― PlannerからPlasmaへ

まず、どのようにしてSchemeが始まったのかについてお話しします。Schemeは
たいへん注意深く設計された言語であって、プログラミング言語のあり方につ
いての十分な研究と理解に基づいたものであったといえればよかったかもしれ
ません。しかし、事実はぜんぜん違います。

この言語は、MITの二人の聡明な人間がしていた、大きな論争に始まります。そ
れは、私がMITに学生としてくるちょっと前のことでした。この論争というのは、
Carl Hewittと、新しく学生として入ったGerry Sussmanの間に起こったもので
す。Carl Hewittは、MITの人工知能研究所にいて、ロボットのための言語の設
計に興味を持っていました。60年代の半ばでは、ロボットが自分でなすべきこ
とについて定理証明ができるかどうかが重要のようでした。とくに、ロボット
が具体的な行動をする前にその行動のプランニングをできるかどうかが重要で
した。そこでCarl HewittはPlanner†1というプログラミング言語を設計しまし
た。

それは、プログラマやロボットが定理証明をするのを助けるためのものでした。
アイディアというのは、プログラマがルールを書き出し、Planner言語が自動的
にルールから定理を演繹するというものでした。したがって、Plannerはおそら
く最初のルールベースのプログラミング言語でした。

Gerry SussmanはMITに来て、Plannerを実装するプロジェクトのメンバーになり
ました。Carl Hewittは、簡単な言語を設計するということは決してありません
でしたので、Plannerはたいへん複雑な言語でした。そこで彼らはまず、
Muddle†2と呼ぶシンプルなプログラミング言語の設計から始めることにしまし
た。そして、Muddleを使って、Plannerを作成しようとしたのです。Carl
HewittはMuddleの設計を受け持ち、Gerry SussmanはMuddleの実装を受け持ち、
そしてPlannerの実装をしようとしたのです。これもなお、困難な仕事で、完全
なPlanner言語はついに実現されませんでした。しかし、Muddleは完全に作られ、
他の研究プロジェクトで用いられました。Common Lispの機能のうち、引数リス
トの、&optional, &rest, &keyword、その他のキーワードなどは直接Muddleか
らきています。

一方、ロボットのための何らかのプログラミング言語が必要となり、Plannerの
小型版、Microplanner†3を作る別のプロジェクトが始まりました。それは、
Muddleで実現する代わりに、Common Lispの前身の一つであるMacLisp†4で作ら
れました。このMicroplannerはまずまずの成功を収め、MITの人工知能プロジェ
クトのいくつかはこれで書かれました。おそらく、その中でもっとも有名なプ
ロジェクトは、Terry Winogradによる「積木の世界」で積木を動かすSHRDLUで
しょう。

Microplannerを経験したあと、Gerry Sussmanともう一人の学生Drew
McDermottはそれに満足しませんでした。プログラミングするのが難しかったか
らです。彼らはさらに別のプログラミング言語を発明することを決心しました。
それは、Conniver†5と呼ばれました。

MicroplannerとConniverとの違いは、Microplannerでは定理証明も制御構造も
オートマティックであったことです。Microplannerは定理証明をするのにルー
ルを使っていましたので、自動バックトラックで次々とテストをしていきまし
た。ときどき、この自動バックトラックは非効率的です。Conniver言語では、
SussmanとMcDermottは、プログラマがこのバックトラックをもっと制御できる
ように、言い換えれば、バックトラック以外の何かもできるようにしようとし
ました(ここで、McDermottとSussmanによって書かれた論文があることを指摘し
ておきます。そのタイトルは、「なぜConniverはPlannerよりよいのか」です)。

そこで、ある種の進歩があったのです。Carl HewittとGerry Sussmanの間の議
論は、ロボットをプログラミングするもっともよい方法、そして、人工知能を
プログラミングするもっともよい方法に関してであったのです。しかし、互い
にあらそうのではなく、やったことは競って別の言語の設計をしたのです。
「私の言語の方が君のよりいいよ」と互いに言い合ったのです。

Conniverで終わりではありませんでした。Carl Hewittは、Plasma†7という名
の言語を設計しました。Plasmaは、Conniverよりよかったのです。

Plasmaは、アクタモデルというCarl Hewittの新しいアイディアに基づいていた
ので、以前の言語とは異なっているものでした。だから、Schemeを理解するに
は、まずCarl Hewittのアクタモデルを理解する必要があります。

----------------------------------------
Schemeの理解は、まずアクタの理解から

アクタ(Actor)とは何か?そのアイディアは、SIMULA67とSmalltalkにヒントを得
ています。アクタは、オブジェクトのようなものです。これらの説明をします
が、私の言い方はCarl Hewittが使った言葉とは全く同じではありません。

アクタはオブジェクトです。アクタはメッセージを送受できます。アクタは他
のアクタを知っています。もう少し言えば、他のアクタへのポインタを持って
います。

Carl Hewittは、すべての計算をアクタを使って説明しようとしました。今日、
Plasmaはまったくオブジェクト指向言語であったと言うことができます。しか
し、あの時点では、オブジェクト指向言語という言葉はあまり使われていませ
んでした。それで、この言語を理解するのにもがいていました。Carl Hewittの
大きな貢献は、彼は「オブジェクト」という言葉を、それ自身何もしないがそ
こにあるものとし、「アクタ」は何かをする何かとしてみたことです。それは、
エージェントです。事実、私はアクタではなくエージェントという言葉が使わ
れなかったことにたいへん驚きました。ラテン語では、アクタとエージェント
は同一の動詞からきています。

----------------------------------------
1に、メッセージ`+ 2 c'を送ると、cに3が送られる!?

アクタ計算の例を見てみましょう(図1参照)。Carl Hewittにとって、1とか2と
かいった数というのはアクタです。

普通のプログラミング言語では、1と2を加算に送ると考えるでしょう。そして、
加算関数が3を返します。しかしHewittは違った考え方をしました。1は一つの
アクタだとします。もし、1にメッセージを送ると、コンティニュエーションc
を得ます。とくに、1にメッセージ(+ 2 c)を送ると、最終的にアクタcはメッセ
ージとして3を受けとります。74年頃の時点で、これは非常に奇妙な考え方でし
た。Gerry Sussmanと、そのころMITに学生として入った私には、理解するには
困難なものでした。

┌───┐            │        ┌───┐
│      │⇒3         │        │      │⇒c
└───┘            │        └───┘
↓  ↓  ↓            │        ↓
+   2   c  4          │        3    +   2   c  4

図1

Conses as Actors
・A cons cell is an actor that knows about two other actors a and d.
・If you send it the message `car c' then actor c receives the message `a'.
・If you send it the message `cdr c' then actor c receives the message `d'.
・If you send it the message `atom? c'
  then actor c receives the message `false'.

アクタの別の例をお見せしましょう。Lispのコンスセルがアクタだとします。
図で示しましょう(図2)。コンスセルは、二つの別のアクタを知っているアクタ
です。

普通、この二つのアクタをaとdあるいはcarとcdrと呼びます。もし、`car c'の
メッセージをこのコンスセルに送ると、アクタcはメッセージとしてaを受けと
ります。したがって、コンスアクタに、「あなたのcarは何か」と尋ねることが
できるのです。そしてそれをメッセージとして返します。実際にはアクタaを私
たちに返すのではありません。それをアクタcに渡すのです。今日、私たちはア
クタcを「コンティニュエーション」と呼びます。しかし、そのころはそうした
用語はありませんでした。コンスセルに送れるもう一つのメッセージは、`cdr
c'です。そうすると、アクタcは、メッセージdを受けとります。このコンスセ
ルに送れるもう一つのメッセージに`atom? c'があります。この場合、cは、偽
というメッセージ、「私はアトムではない」ということを受けとります。

┏━┳━┓
┗┿┻┿┛
  a   d

図2

1974年のLispプログラマにとって、これは非常に奇妙な概念です。すべての人
はコンスセルはただ36ビットのメモリだということを知っていました。18ビッ
トがcarで、18ビットがcdrです。誰でも、そのcarやcdrを覗いてみることがで
き、rplacaやrplacdで置き換えることができます。

Carl Hewittは言います。「そうじゃない。コンスセルはオブジェクトではない。
それはアクタだ。『お渡しするオブジェクトであなたのcarを置き換えてくださ
い。お願いします。』と言わなければいけない。」

----------------------------------------
PLASMAが投げかけたもの
――― Schemeの始まり

Hewittは、アクタ言語Plasmaを設計しました。この言語の中のすべてのものは
アクタです。これは、たいへん複雑な言語で、たいへん複雑な文法を持ってい
ます。Sussmanと私は、それがどう動くのか理解できませんでした。

MacLispで書かれたPlasmaの処理系がありました。それを試すことができました。
また、Plasmaでプログラムを書いてみました。それは動作しましたが、なぜ、
動くのか理解できませんでした!

Sussmanと私はそれがどう動くのか理解しようとしました。Sussmanと私は、小
さなインタプリタを書きました。言語を理解するもっとも簡単な方法はそのイ
ンタプリタを書くことです。インタプリタを書くもっともよい言語はLispです。

そこで、私たちはPlasmaのたいへん小さなバージョンを書くことにしました。
次のAI言語を設計しようという気はありませんでした。そうではなく、不要な
機能を省いたPlasmaを理解しようとしたのです。それは小さな言語でした。そ
のインタプリタはLispで書いたので、そのおもちゃの言語はLisp構文を持って
いました。Plasmaの複雑な構文を持つのではなく、単純なLisp構文を持たせた
のです。

どうやって、そのおもちゃのアクタ言語を書いたのかお話しましょう。まず、
2ページくらいの長さのたいへん小さいLispインタプリタを書くことから始めま
した。

一つだけLisp1.5マニュアル†9から特殊な変更をしました。それは、そのころ
普通に使われていたダイナミックスコーピングの代わりに、レキシカルスコー
ピングを用いることでした。二つの理由でレキシカルスコーピングをしました。
まず、Plasma言語を調べた結果、アクタはレキシカルスコーピングがいるよう
に思ったこと。もう一つは、Sussmanはそのころ、Algol 60を教えていて、レキ
シカルスコーピングに興味を持っていたことからです。彼は、Algolのようなレ
キシカルスコーピングを持つ言語を作ることは面白そうだと感じたのです。こ
れが、SchemeにAlgolの設計が及ぼした直接の影響です。

私たちはさらに二つのことを加えて、レキシカルスコーピングのLispの開発を
始めました。一つは、アクタの生成手段、もう一つはメッセージ送信です。ア
クタの生成のためには、alpha式を用意しました。これはラムダ式に似ています。
アルファ式は、最初にalphaを置き、次にそのアクタに送られるメッセージの要
素を表す変数名を並べます。その後に、メッセージを受けとられた時に実行さ
れるコードであるボディを書きます。

Carl Hewittが言っていることから私たちが理解できたのは、アクタと関数の違
いは、アクタは値を返さないということでした。その代わりにボディは何らか
の方法で、値を他のアクタに送ります。普通、何かを送っている宛先のアクタ
は、元のメッセージの中に、コンティニュエーションとして存在します。

私たちは、alphaという言葉を選びました。というのは、それがアクタというギ
リシャ語の最初の文字だからです。このような式の評価は、Lispの値としてア
クタを生成します。このアルファ式はアクタを生成するのです。つまり、その
式のLispとしての値はアクタです。それが私たちがアクタを生成する仕方であ
りました。メッセージを送る仕方についてSussmanに尋ねました。私は覚えてい
ません。そして彼も覚えていません。しかし、私たちはsendという特殊形式を
持っていたように思います。しかし、関数適用の構文は、また、メッセージ送
信の構文となりうると、その後わかりました。というのは、もし、最初に関数
があるのなら関数呼び出しになるし、最初にアクタがあるのならメッセージ送
信になるだろうということです。

アクタにメッセージを送るには、send、そのアクタ、そしてその引数という順
に書きます。

それはアクタを生成し、メッセージを送るのには十分な、たいへん小さいシン
プルな言語でした。それでもあらゆる関数、アクタ、そしてそれらの組み合わ
せを試してみることができました。Schemeのまさに初期の処理系でのサンプル
コードを示しましょう。

† McCarthy, J., et al.
Lisp 1.5 Programmer's Manual
The MIT Press, 1963.

----------------------------------------
関数とactor

Functions and Actors

・Factorial function:
  (define factorial
    (lambda (n)
      (if (= n 0)
          1
          (* n (factorial ( - n 1))))))

・Factorial actor:
  (define actorial
    (alpha (n c)
      (if (= n 0)
          (send c 1)
          (send actorial (- n 1)
                (alpha (z) (send c (* n z)))))))

これは、Lispの教科書にもよく出てくる階乗(factorial)のプログラムです。
factorialは、関数としてラムダ式で定義されています。この関数は、1引数nを
とり、もしそれがゼロなら1を値として返し、そうでなければ、値n-1で再帰呼
び出しをし、その値とnをかけ、結果を返します。この定義とアクタ版を比べて
ください。アクタ版は、英語のジョークでactorialという名にしています。

actorialはアクタを生成するアルファ式で定義されています。値を返すように
は考えられていません。その代わりに、値cは、値をそこに送るコンティニュエ
ーションです。

actorialを見てみましょう。actorialは、2引数、nとcを受けとります。もし、
nがゼロなら値1をcに送ります。そうでなければ、二つの値、n-1と新しいコン
ティニュエーションをactorialに送ります。

この新しいコンティニュエーションはそれ自身アクタです。それは、zを受けと
り、nとzをかけ、cに結果を送ります。したがって、最終的にcは正しい値にセッ
トされます。

実際には、actorialのこの定義は純粋なアクタではありません。これは入り混
じった記法です。というのは、actorialはアクタだけれど、等号とマイナスと
乗算は関数だからです。等号とマイナスと乗算をアクタとすると、全体が純粋
なアクタとなります。次のスライドでそれをお見せしましょう。

Detailed Factorial Actor
(define actorial
  (alpha (n c)
    (send = n 0
      (alpha (p)
        (if p
            (send c 1)
            (send - n 1
              (alpha (m)
                (send actorial m
                  (alpha (z)
                    (send * n z c))))))))))

このスライドが私の話の中でもっとも複雑なものです。あとは簡単になります。

OK、さあ始めましょう。これはちょっと複雑です。actorialは、メッセージと
して二つのものnとcを受けとります。次に三つのものを等号アクタに送ります。
値n、値ゼロ、それとコンティニュエーションです。そして、そのコンティニュ
エーションは、値pを受けとります。もし、その値が真であれば、値1をcに送り
ます。もし、pが偽ならば、三つの値をマイナスに送ります。値は、nと1ともう
一つのコンティニュエーションです。

このマイナスは、値をコンティニュエーションに送ります。この新しい値は、
n-1と等しいものです。これはmと呼ばれます。この新しい値mは、actorialに第
3のコンティニュエーションとともに送られます。actorialが計算する値はzと
呼ばれます。このコンティニュエーションは、その後、乗算アクタに三つの値、
nとzともともとのコンティニュエーションcを送ります。次に乗算はその積をc
に送ります。

それが、私たちがほしいものです。もし、この計算過程を注意深く見てくれれ
ば、これは同一の計算なのがわかるでしょう。なぜ、私たちが理解が困難だと
感じたかを理解してもらえると思います。

Plasmaプログラムは、これに似ていますが、もっと複雑な構文を持っていまし
た。Plasmaプログラムは、Lispに比べて2倍は長く、10倍は理解するのが困難で
した。Gerry Sussmanと私はシンプルな構文のシンプルな言語の、小さなインタ
プリタが大好きでした。楽しいので、この小さな言語でたくさんのプログラム
を書きました。Carl Hewittの論文からたくさんの例を引いてきて、それを私た
ちのインタプリタで走らせました。

----------------------------------------
Schemeという名前の誕生

これは人工知能によい言語かもしれないとわかってきて、私たちはだんだん興
奮してきました。

Carl Hewittが複雑な言語を設計し、Gerryが私たちが理解し使えるものを実現
してくれるというのはこれが初めてではありませんでした。Carl Hewittは、使
うのには複雑すぎる言語であるPlannerを設計し、一方、Gerry Sussmanは
Microplannerを設計し、人々はそれを使いました。これはそれと同一のストー
リーだと思いました。

Carl Hewittは、複雑なPlasma言語を設計し、Gerry Sussman(と私)は、Scheme
を設計しました。これは使えるシンプルなLispだと思いました。私たちは、新
しいAI言語を作ろうとしているのではありませんでした。私たちは自分たちが
理解できるようなシンプルな言語を偶然作ったのです。

もし、これがConniverやPlasmaのあとの新しいAI言語となり得るなら、よいAI
言語の名前を持つべきです。英語でPlannerはプランする何かです。Conniverは
スニーキー(こそこそする、卑劣)なプランナーです。だから、もっとスニーキ
ーなプランナーを何と呼ぼうか。そりゃ、スキーマー(陰謀家、策略家)だ。そ
れで、Schemerとつけたのです。

残念ながら、我々は60年代に設計されたOSを使っていたので、すべてのファイ
ル名は6文字以下でなければなりませんでした。それで、ファイル名SCHEMERは
最初の6文字だけに切り捨てられました。その結果、SCHEMEというファイル名が
ポピュラーな名前となりました。言語全体は偶然に設計され、その名も偶然に
付けられました。多くの人は私たちがすばらしい仕事をしたと考えています。
私にはどうしてだかわかりません。

†1 Hewitt, Carl E.,
PLANNER:A Language for Proving Theorems in Robots
Proc. of the First int'l Joint Conference on AI, pp295-301, 1969.

†2 Galley, S.W. and Pfister, Greg.
The MDL Language, Programming Technology Division Document SYS. 11.01.
Project MAC
MIT, Nov. 1975.

†3 Sussman, Gerald Jay, Terry Winograd, and Eugene Charniak
Microplanner Reference Manual
Report AIM-203A, AI LAB, MIT, 1971.

†4 Moon, David
MacLisp Reference Manual version 0
Technical Report, MIT LCS, 1978.

Pitman, Kent
The revised MacLisp Manual(Saturday evening edition)
Technical report 295, MIT LCS, 1983.

†5 Sussman, G.J., and McDermott, Drew V.
From PLANNER to CONNIVER ――― A Genetic Approach
Proc. the 1972 FJCC, pp 1171-1179, AUG. 1972.

McDermott, Drew V., and Sussman Gerald Jay
The CONNIVER Reference Manual
AI Memo 295 A, MIT AI Lab., Jan. 1974.

†6 Sussman, G.J., and McDermott, Drew V.
Why Conniving is Better thatn Planning
AI Memo 255 A, MIT AI Lab., April 1972.

†7 Smith, Brian C., and Hewitt, Carl
A PLASMA Primer
Working Paper 92, MIT AI Lab., October 1975.

--------------------------------------------------------------------------------
Scheme 過去◇現在◇未来 後編

bit/May 1996/Vol. 28, No.4 p84～92

Guy L. Steele Jr.
訳 井田昌之

----------------------------------------
訳者より

前回は、Carl HewittとGerry Sussmanの間にあってGuy Steeleがどのような役
割を演じてきたか、それをどのように自分で感じていたかが述べられた。Carl
Hewittの設計したPlasmaの仕組みを知るために簡単な処理系を作り、それを、
PlannerそしてConniverの次という意味でSchemerと呼んだこと、それが、当時
のコンピュータの制限から6文字に切られ、Schemeという名前になったいきさつ
などが語られた。今回の部分では、アルファ式として導入したもののクロージャ
との関係、アクタとの関係などにまず触れられ、次にラムダ式を用いたコンパ
イラの最適化の話、そして、Schemeの言語仕様の変化に対する興味深い洞察が
話されている。

前回と同様、登場する人物の氏名には一切敬称を略した。また、読者の便宜の
ためにできるだけ多くの参考文献を付した。

----------------------------------------
クロージャとアクタ

しかし、設計のネーミングの二つの偶然だけでなく、もう一つの偶然もありま
した。それはおもしろいものでした。私たちは、関数とアクタをサポートする
Lispインタプリタを作りました。引数をつけて関数を呼び出したり、メッセー
ジをアクタへ送ることができます。そしてそのインタプリタにアクタが実装さ
れた仕方を見て、私たちは、たいへん驚きました。ラムダクロージャの実装と
アルファアクタの実装は、同一のコードだったのです。

「すごいですねぇ。」

私たちはアクタと関数クロージャは同一のものだと決断しました。これはたい
へん有益な結論です。というのは、このことから、アクタはラムダカリキュラ
スで説明できるということを意味すると気がついたのです。これは、実際は偶
然ではありませんでした。しかし、偶然のように感じました。Lispの中のレキ
シカルスコーピングはそれと同一のものです。Sussmanと私はレキシカルスコー
プのLispは、ラムダカリキュラスと同一であるということを発見しました。

それは、1975年のことです。すぐにラムダカリキュラスの論文を読みだしまし
た。とくに、私たちはAlonzo Churchの1941年の論文†に戻りました。彼の論文
の中では、アクタとしてのコンスセルのようなペアのシミュレーションが論じ
られていることに気がつきます。彼がそれをメッセージ送信になるべきだと理
解していたとは思いませんが、1941年の論文でコンスセルのような何かが出て
いるのを見つけるのはたいへん興味深いことです。

それから4年後、1979年に私は結婚しました。妻と私は二人ともMITの学生でし
た。もう少しお話しすると、私たちはSussmanの研究室にいました。結婚して6
カ月後に妻は、彼女の母から、親戚のことがたくさん書かれている手紙を受け
とりました。彼女は祖父のHerbert Taylorと叔父のSam Churchについて話して
くれました。また、「いとこのAlonzoからの手紙をもらった。彼はプリンスト
ンにいました。」と書かれていました。それを彼女は私に見せてくれました。

私は言いました。「バーバラ、プリンストンにいて、引退したAlonzo Churchと
いう人は何人いると思う?」彼女は、「たった一人よ。」「なんてこった!」
Alonzo Churchは、彼女のいとこだったのです。まったく世界は狭いですね。

Sussmanと私は関数とアクタは同一だと認めました。どんなことになるのでしょ
う? 関数は値を返すものと考えられています。アクタはそうではありません。
代わりにアクタはメッセージを送ります。この質問に対する正しい答えは「そ
れがどうした」「なんでも、いいじゃないか」です。

引数を受けとり、何かをするからということで、何がアクタであるか関数であ
るかを、識別することはできないのです。

アクタ、あるいはクロージャがどんなことをできるか考えてみましょう。いく
つかのことがあります。まず、他のアクタやクロージャを呼び出せます。再帰
的に行なってもかまいません。たぶん条件テストもできるでしょう。これも再
帰的な場合もあります。then部あるいはelse部が何か別のことをしてもいいで
す。あるいは、言語に用意されたプリミティブを呼び出すこともできます。帰
納の基礎となるケースです。しかしSussmanと私は偶然、もし言語中のプリミティ
ブが値を返すなら、すべてのアクタあるいはlabelsクロージャも値を返すこと
を発見しました。もしすべてのプリミティブがメッセージを送るなら、すべて
のアクタやクロージャもメッセージを送るのです。

だから、アクタやクロージャとして振る舞うものというのは、用いているプリ
ミティブに依存するのです。したがって、言語が純粋に関数なのか純粋にアク
タなのかはそのプリミティブに依存します。

† Church, Alonzo
The Calculi of Lambda Conversion
Anunals of Mathematics Studies 6, Princeton University Press, 1941.

----------------------------------------
Initial Report on Schemeとそれに続く論文

Sussmanと私はSchemeに関する最初のレポート†1を書きました。1975年12月の
ことです。lambdaという関数コンストラクタを置きました。見てきたように、
それはアクタコンストラクタでもあります。labelsという不動点オペレータも
加えました。これはLisp1.5のlabelのようなものです。モダンなプログラミン
グ言語ではletrecと呼ばれています。条件オペレータとしてifを加えました。
ifの代わりにcondを置けたかもしれませんが、その方がシンプルだと思ったの
です。

setqに似たasetと呼ぶ副作用オペレータを置きました。それらに加えて、
catchと呼ぶ暗黙の関数コンティニュエーションを得る方法を加えました。
catchは特殊形式で、最近のSchemeではcallccと普通呼んでいるものです。関数
の適用は、関数に引数を与えます。そして、変数を参照することももちろんで
きます。リスト、数、などの基本的なデータタイプがあります。それが最初の
Schemeでした。いろいろなことにはできるだけ一つのことを入れるだけで済ま
せようとしました。開発用というのではなく、教育のために、この言語をたい
へん小さいものに保とうとしてきたからです。

Sussmanと私は、次のこの小さな言語を使って制御構造全体というものを、もう
一度説明しようとしました。Carl Hewittは、アクタに関する論文を書きました。
“Viewing Control Structures as Patterns of Passing Messages”†2です。
1974年か75年のことです。Hewittの論文は、繰返し、再帰、ループ、そしてあ
らゆる種類の複雑な制御構造をアクタとメッセージによって説明しました。
Sussmanと私は、Schemeを使って、Carl Hewittのやっていることをシンプルな
方法で説明しようとしました。

それで、“Lambda:the Ultimate Imperative”†3という論文を書きました。そ
こでは、制御構造をラムダカリキュラスを使って説明しようとしたのです。そ
れは新しいアイディアではありませんでした。Peter LandinとJohn Reynoldsは、
Algolをラムダカリキュラスで説明しようとしました†4。denotational
semantics†5という理論領域がそのころ現れてきました。事実、Sussmanと私は
これらのアイディアを自分たちのフレームワークで繰り返しました。

私たちの新しい貢献だというのは、ラムダカリキュラスでの制御構造のモデル
は実行できるということでした。ラムダカリキュラスの理論モデルをすべて
Lisp構文則に翻訳し、それを走らせました。それで、MITの他の人達はたいへん
便利だと言ってくれました。次の論文“Lambda:The Ultimate Declarative”†
6では、ラムダの宣言的サイドを見ていました。

この論文では、2点を強調しました。まず、ラムダの主な目的は、メッセージに
到着する引数に名を与えることです。もう一つは、関数の呼び出しは必ずしも
値を返すわけではないことです。もし、関数呼び出しが値を返さなくてもよい
とすると、帰る必要もないのです。このことを、関数はアクタと同じであり、
呼び出しはメッセージと同じなので、理解できます。

これは、関数呼び出しを、引数を渡せるgotoのようなものとしてコンパイルで
きることを教えてくれます。とくに、関数呼び出しは、戻り番地をスタックに
積む必要がなくなるのです。戻りたい時にだけ積めばよい。あるいはこのこと
を別の考え方で見ると、戻り番地はまさにコンティニュエーションです。もし、
新しいコンティニュエーションを作りたくなければ、戻り番地をプッシュする
必要はないのです。

この原則に基づいてコンパイラを設計するなら、末尾再帰は自動的に処理でき
るようになります。そしてそのコンパイラは末尾再帰の正しい処理を保証しま
す。そして、Lispでのオブジェクト指向プログラミングができるようになるの
です。

これらのアイディアにしたがって、私は自分の修士論文†7の一部として、
Schemeのコンパイラを実際に作りました。その中で、私は今まで話してきたよ
うなコードコンパイルのアイディアについてまとめました。また、ラムダカリ
キュラスを使って最適化コンパイルをする方法をまとめました。そのころ、70
年代では、ソースレベルのプログラム変換はなおも新しいアイディアでした。
私はdenotational semanticsとして説明されるプログラム変換は、コンパイラ
中で直接使えることを認識しました。

そのころ、私は「その言語でコンパイラが書けなければ、いい言語ではない」
という言葉に強く影響を受けていました。だから、私はSchemeでコンパイラを
書きました。ブートストラッピングでの別の問題を発見しました。自分自身コ
ンパイルするようにするには、インタプリタを走らせなければなりませんでし
た。さらに悪いことに、改良をどんどんすると自分自身をコンパイルするコン
パイル時間はどんどん長くなります。そこで、家に端末を持って帰って毎晩コ
ンパイルしました。朝起きるといつもできていました。3カ月で100回くらいコ
ンパイルしたことになります。コンパイラをうまく作れると、それを使ってそ
のコンパイラをコンパイルして、もっと速く実行できるようにします。

けれども、何回かはコンパイラにバグを入れてしまったこともありました。そ
の場合、インタプリタを使ってブートストラップし直しました。これはとても
あきあきするような作業でした。

ラムダカリキュラスに基づくコンパイラ最適化の二、三の例を示しましょう。

----------------------------------------
ラムダカリキュラスによるコンパイラ最適化

Example:OR

(or x y)
(if x x y)
((lambda (p) (if p p y) x))
((lambda (p q) (if p p (q))) x (lambda () y))

最初の例はorです。
(or x y)

この意味は、Lispの場合と同じで、もしxが真ならば真を返し、yの評価はしな
い。しかも、もしxが偽ならばyを評価し、その値を返す。そこで、次のような
変形もあり得ます;
(if x x y)

しかし、これは、マクロとしてはやりたくありません。とくにxが複雑な式の場
合に。またそれは副作用があるかもしれません。2回実行はしたくありません。

したがって、やりたいことはxを1回だけ評価し、その値を見て、もしそれが真
ならそれを返し、再び、実行しないようにさせます。多くのコンパイラはこの
アイディアをすでにもっています。Cコンパイラもすでにもっています。しかし
そのころまでは、どんなコンパイラもソースからソースへの変換で扱ってはい
ませんでした。Rabbitでは、この拡張を試みました。xを評価し、その値を変数
pに束縛し、それをテストします。ここのソースコードを見てください。xの評
価は1回だけ行ないます。もう一つ別の問題があります。変数pがyの中で使われ
ていたとしたらどうしますか? yの中では誤ったpを参照してしまいます。

そのころの普通のトリックはgensymで変数名を作ることです。しかし、私たち
はこの仕掛けでは満足できませんでした。そうしたマジックは言語の外にある
べきです。私たちはラムダ変数を使って、完全にその言語の範囲内でソース変
換をしたかったのです。

私たちは、もっとラムダ式を使うことでこれが可能なことを発見しました。こ
のラムダ式では、変数xを変数pに束縛し、変数qを別のラムダ式に束縛しそして
それがyを呼び出し、実行します。

Algolの分野では、このラムダ式はthunkと呼ばれます。さて、thunkは英語では
変な(silly)名前です†8。

この意味は、このラムダ式(外側のもの)は単に二つのものを名付けます。変数
xとそのthunkを名付けます。ここで名前pとqを用います。もしpが真ならp、そ
うでないならqを呼びます。この関数呼び出しを、正しいスコープにあるthunk
へのgotoに実際に変更することを考えることができます。

Example:IF

(if (if a b c) d e)

(if a (if b d e)
      (if c d e))

((lambda (x y)
   (if a (if b (x) (y))
         (if c (x) (y))))
 (lambda () d)
 (lambda () e))

二つ目の例として、このifを考えてみましょう。入れ子になったifがあるとし
ます。ここで示すようなものへのソース変換がよいことが最近発見されていま
す。

私はこの変換をカリフォルニア大学アーバイン校のカタログ†9の中で発見しま
した。アーバインのプログラム変換カタログは、まずソースレベルでの変換と
して変換をシステマティックに並べようとした最初のものでした。

この変換は必ずしも十分なものではありません。というのは、dとeのためのコ
ードが重複しているからです。この考え方によるとdとeに対して、ただ一つの
コピーだけをもてばいいのです。そしてこの意志決定木を下がっていって正し
いコードの断片に到達します。Schemeを使ってRabbitコンパイラは次のように
表現します。xとyがdとeに対する二つのthunkを名付けます。それでdのコード
は1回だけ現れます。eのコードも1回だけ現れます。その後、実際の実行できる
コードは、a, b, c上の意志決定木となります。この意志決定した後、dの
thunk、あるいはeのthunkのどちらかへの直接のgotoが起きます。Rabbitコンパ
イラはまさしくこのようにコンパイルします。これらの関数呼び出しは、分岐
命令になるのです。それで、興味深いことは、これらのラムダ変数(xとy)は、
データ変数を表すのではないことです。

xとyは、文のラベルのようなものです。それで、Schemeは変数の名と文ラベル
の名を一つのメカニズムで説明できるのです。

----------------------------------------
Revised Report on Scheme

Sussmanと私はSchemeに関してさらにいくつかの論文を書きました。次の論文は
“Revised Report on Scheme†10”です。これはSchemeの定義を多少改訂した
ものです。主な新しい機能としては、ダイナミックバインディングを追加した
ことがあります。それで各変数はレキシカルかダイナミックのどちらであって
もよく、プログラマが選択できるようになりました。

このときまでに、他のユーザは基本的にコードを書くためにSchemeを使ってい
ました。それで、Schemeをもっと便利にするためにいくつかの機能を加えまし
た。let, cond, doをマクロとして加えました。また、ユーザがマクロを定義で
きるようにしました。この論文を私たちは、“Revised Report on Scheme”と
呼びました。というのは、私たちはAlgol 60に敬意を払いたいと思っていたか
らです。“Revised Report on Algol 60”†11はたいへんよく書かれたレポー
トだと思っていました。私たちはそれと同じくらいにきれいに書きたいと努力
しました。

次に私たちは、別の論文を書きました。“The Art of Interpreter”†12とい
うものです。プログラミング言語の設計をどうやって実験できるのか説明しよ
うとしたものです。Sussmanと私がSchemeを設計している間に、“Lambda:The
Ultimate Declarative”など、いくつかの論文を書き†13、また、たくさんの
小さなインタプリタを書きました。あるときなどは、1週間に10あまりの異なる
インタプリタを書きました。古いインタプリタを修正し、新しいものを作るの
は、そして、言語が小さいのであればたいへん簡単な作業でした。インタプリ
タを書いて、インタプリタの中のさまざまな小さな違いが言語に大きな違いを
与えることを示しました。

私たちは、また、副作用とステートについても説明しました。副作用のもっと
もよい定義はDan Weinrebによるものです。私たちは「二つのオブジェクトが同
一である」ことの意味を理解しようとしたことがあります。Sussmanと私は、偉
大な学者の本を調べてそれを理解しようとしました。しかし、Dan Weinrebは、
言いました。「二つのコインがあって、一方がレールの上にあって、もう一つ
がつぶれたらそれは同一ものだ。」つまり、二つのオブジェクトがあって、一
方での変化が常に他方に影響するのであればそれらは同一だ、という意味です。

----------------------------------------
Schemeの広がり

このころ、Schemeはもっとポピュラーになってきました。Sussmanと私は1970年
代にインディアナ大学の研究者、Daniel FriedmanとDavid Wiseたちと、論文†
14を交換しました。インディアナ大学、エール大学などがSchemeの研究をして
いました。

エールは二つのたいへんよいSchemeコンパイラを作りました。80年代初期には、
商用のSchemeが出現してきました。Texas Instrumentsは100ドル以下というた
いへん安い価格でTI Schemeを出しました。Will Clingerのいたオレゴン大学の
人達はMacSchemeを作りました。そのころCommon Lispの開発が始まったのです。

SchemeはCommon Lispの設計に影響を与えました。NILというちょっと奇妙な名
前のLispがあります。このプロジェクトの開始には多少関わっていました。こ
れはDigital VAXとスタンフォードS1に対するLispを作ろうとして設計されたも
のです。NILはMacLispににていますが、レキシカルスコーピングをします。
NILはその後、Common Lispの重要な前身となりました。それがCommon Lispがレ
キシカルスコーピングをする理由です。

たくさんの人々がSchemeに関係してきたので、標準化委員会が作られました。
委員会が始まり、Schemeを改良しようとしていくつものレポートが書かれまし
た。委員会では、Revised Revised Report、Revised Revised Revised Report、
Revised Revised Revised Revised Report、そして今は、Revised Revised
Revised Revised Revised Reportが作られています。

Schemeのレポートは4回改訂され、それがIEEE Scheme標準となりました。IEEE
Scheme標準は5年前に出ています。それを改訂するか否かが問題になったことが
あります。私たちはそのままでよしとしました。Schemeコミュニティは、同一
の言語仕様を5年間提供してきたのです。

Schemeコミュニティはとてもフレンドリーです。ほとんど彼らはコンセンサス
で合意してきました。Revised reportの作業をしていたときの委員会の大原則
は、「もし変更が提案された場合、誰かがnoと言ったらそれは入れられない」
ということでした。別の言い方をすると、誰もがそれに同意しないと直さない。
これは言語を小さいものに保ちます。

これとCommon Lispコミュニティと比べてもいいかもしれません。Common Lisp
はフレンドリーではないとも言えるでしょう。コンセンサスで動くのではなかっ
た。5年間私は委員長をしていました。論点の調停をしていました。それは私の
一生でもっとも困難な仕事でした! Common Lispでの原則は、「変更が提案され
るとき、誰かがyesと言うとその機能は言語に入れられていきます!」だから、
Common Lispは大きくなりました。

この比較はフェアでないかもしれません。Common Lispの目的はたいへん異なっ
ているものだと思います。Common Lispは産業用のプログラミング言語となるよ
うに意図されていました。教育のためにCommon Lispを小さいままにすることは
ゴールではありませんでした。だから、Common Lispはとってもとっても大きな
サブルーチンパッケージとなったのです。それを使うのは簡単ですが、教える
のは困難です。

Schemeの貢献にはどんなものがあったのか、控えめにまとめてみたいと思いま
す。まず、Schemeはたいへん小さな、しかし、便利な言語です。実際にそこに
は新しいアイディアは何もありません。その代わりに、偶然、いくつかの古い
アイディアがたくさんのことを説明できることを示しています。ことに、ラム
ダカリキュラスに基づく言語が有用なことを示しました。Schemeは小さいので、
実現は容易です。そして、理論と実際の間の架け橋を与えています。理論的な
ラムダカリキュラスとdenotational semanticsのやりかたは実際的なコンパイ
ラを書くのにも便利なものです。

----------------------------------------
Schemeの将来

Schemeの将来について私の推理を述べましょう。もう言ったようにIEEE標準は
しっかりとしたもので5年間変化がありませんでした。ユーザが変更してほしい
と示唆したものは、マクロと、ある種のモジュールシステムでした。不運なこ
とに、数年を経てもこれらの機能によい合意はありませんでした。

マクロがたいへんよいものだと言う点にはかなり共通した合意があります。マ
クロにはいくつかの設計プロポーザルがありました。モジュールについても同
じことが言えます。

私の推理では、Schemeはおそらく今と同じようなままでいるだろうと思ってい
ます。それでOKかもしれません。高校や大学や教育機関で広く使われているの
です。また、CADの機能拡張言語用、ちょうどEmacsにはEmacs Lispがあるよう
に、などのインダストリアルな応用も見られます。CADのいくつかはSchemeを使っ
ています。Schemeは全体としてたいへんよくできていて、変更の必要はないよ
うにも見えます。

最近の数年間、私はSchemeから他の関数型言語への技術移転を認識しています。
プログラミング言語ML†15やHaskell†16は、Algolに似た構文をもっています
が、多くの点で、Schemeに似ています。かつてSchemeコミュニティにあったた
ぐいのプログラミング言語のイノベーションが、MLやHaskellでなされているの
を知っています。

Schemeは凍結されているのか、Schemeにイノベーションが戻ってくるのかはよ
くわかりません。たとえば、Schemeは、徐々にMLのデザインに基づくモジュラ
ーシステムになるのでしょう。

いつものように将来は不確定です。でも、Schemeは今のところ、もっとも便利
なLispだと思っています。

これで、私の話は終わりです。

どうもありがとうございました。

----------------------------------------
今後の勉強のために ―― 訳者からの紹介

Schemeそのものについて、勉強するには次のような文献がある。

まず、Scheme自身の文法については、Revised^5 Reportが現在まとめられつつ
あるとのことであるが、本文中にあるように、正式な最新のレポートはIEEEに
よる
IEEE CS:“IEEE  Standard for the Scheme Programming Language”,
IEEE STD 1178-1990, 1991である。

Revised Revised Revised Reportと呼ばれているのは、
Rees, Jonathan and William Clinger(Eds.):
“Revised^3 Report on the Algorithmic Language Scheme”,
Vol. 21, No. 12, December 1986であり、
Revised Revisedレポートというのは、
Clinger, William:“The Revised Revised Report on Scheme:or, An Uncommon Lisp”,
AI Memo 848 MIT AI Lab., Aug. 1985、
Revised Reportというのは、
Steele, Guy Lewis Jr. and Sussman, Gerald Jay:
“The Revised Report on SCHEME:A Dialect of LISP”,
AI Memo 452 MIT AI Lab., January 1978のことである。

これらの大元の論文は、本文中にも引用されているが、
Sussman, Gerald Jay and Steele, Guy Lewis Jr.:
“SCHEME:An Interpreter for Extended Lambda Calculus”,
AI Memo 349 MIT AI Lab., December 1975がそれである。

また、Schemeだけではなく、Lisp全般の歴史は、次の文献に詳しい。

Steele, G. L. and Gabriel Richard:
“The Evolution of Lisp”,
History of Programming Languages Conference Preprint,
ACM Sigplan Notices, Vol. 28, No. 3, pp. 231-270. March 1993.

このコンファレンスには、他の多くのプログラミング言語の歴史についても論
文が発表されているので、プログラミング言語の研究をするものは一読をされ
ることをお勧めする。

(いだ まさゆき  青山学院大学 情報科学研究センター)

†1 Sussman, Gerald Jay and Steele, Guy lweis Jr.
SCHEME:An Interpreter for Extended Lambda Calculus
AI Memo 349 MIT AI Lab., December 1975.

†2 Hewitt, Carl E.
Viewing Control Structures as Patterns of Passing Messages
Artificial Intelligence, Vol. 8, No. 3, pp. 23-364, 1977.

†3 Steele, Guy Lewis Jr. and Sussman, Gerald Jay
LAMBDA:The ultimate Imperative
AI Memo 353 MIT AI Lab., March 1976.

†4 Landin, Peter
A correspondence between Algol 60 and Church's lambda notation
Part 1, CACM, Vol. 9, No. 2, p 89-101, 1965.

†5 Stoy, Joseph E.
Denotational Semantics:The Scott-Strachey Approach to Programming Theory
Proc. ACM National conference, pp. 717-740, ACN, 1972.

†6 Steele, Guy Lewis Jr.
LAMBDA:The Ultimate Declarative
AI Memo 379 MIT AI Lab., November 1976.

†7 Steele, Guy Lewis Jr.
Compiler Optimization Based on Viewing LAMBDA
as Rename plus Goto S. M. thesis
MIT, May 1977.
Published as
“RABBIT:A Compiler for SCHEME(A Study in Compiler Optimization)”
AI TR 474 MIT AI Lab., May 1978.

†8 なぜthunkという名前がsillyだと感じたかについての補足: 二つの理由が
あった。まず、第一に、音のひびき。thunkというのは何か大変硬いものにある
程度硬いものがぶつかった時の音。たとえば、The bat hit the baseboll,
thunk!など。第二に、子どもたちはしばしば、thinkの過去形はthunkだと間違
える。sink--sunk, stink--stunkなどがあるから。Here is a new game I
thunk upなどといったりする。本当はthought upなのに。だから、その言葉は
子どもの言葉のように思える。それで、大人の英語の話し手には、thunkを名詞
として使うのはsillyだといえる。

†9 Standish, T. A. et al.
The Irvine Program Transformation Catalogue
University of Califaornia, Jan. 1976.

†10 Steele, Guy Lewis Jr. and Sussman, Gerald Jay
The Revised Report on SCHEME:A Dialect of LISP
AI Memo 452 MIT AI Lab., January 1978.

†11 Naur, P., et al.
Revised Report on the Algorithmic Language ALGOL 60
CACM, Vol. 6, No. 1, pp. 1-17, Jan. 1963.

†12 Steele, Guy Lewis Jr. and Sussman, Gerald Jay
The Art of the Interpreter;
or, The Modularity Complex(Parts Zero, One, and Two)
AI Memo 453 MIT AI Lab., May 1978.

†13 Steele, Guy Lewis Jr.
Macaroni is Better than Spaghetti
Proc. of the Symposium on Artifical Intelligence and Programming Languages
August 1977.
SIGPLAN Notices 12, 8, SIGART Newsletter 64(August 1977), pp. 60-66.
steele, Guy Lewis Jr. and Sussman, Gerald Jay
Constraints
AI Memo 502 MIT AI Lab., November 1978.
Invited paper, Proc. APL 79 conference.
ACM SIGPLAN STAPL APL  quote Quad 9, 4(June 1979), pp. 208-225.
Steele, Guy Lewis Jr. and Sussman, Gerald Jay
Design of LISP-Based Processors; or, SCHEME:A Dielectric LISP
or, Finite Memories Considered Harmful
or, LAMBDA:The Ultimate Opcode
AI memo 514 MIT AI Lab., March 1979.
Sussman, Gerald Jay and Steele, Guy Lewis Jr.
Constraints ―― A Language for Expressing Almost-Hierarchical Descriptions
Artificial Intelligence Journal, Vol. 14, pp. 1-39, 1980.
Sussman, Gerald Jay, Holloway, Jack, Steele, Guy Lewis Jr. and Bell, Alan.
Scheme-79 ―― LISP on a Chip.
IEEE Computer, Vol 14, No. 7, pp. 10-21, July 1981.

†14 Wand, Mitchell and Friedman, Daniel P.
Compiling Lambda Expressions Using Continuations and Factorization
Technical Report 55, Indiana University, July 1977.
Wand, Mitchell
Continuation based program transformations strategies
J. ACM, Vol. 27, No. 1, pp. 164-180, 1978.

†15 Milner, Robin
A proposal for Standard ML
ACM sympo. on Lisp and Functional Programming, pp.184-197, 1984.

†16 Hudak, Paul, et al.
Report on the Programming Language Haskell
Technical Report Yale University and Glasgow University
New Haven and Glasgow, Aug. 1991.