言語の庭

用語の庭

ことばの、植物図鑑。

教科書の定義ではなく、この庭の声で書いてあります。

プログラム program
読み手（コンピュータ）に宛てて書く、曖昧さのない文。上から順に読まれ、書いたとおりのことが起きる。
エラー error
誠実な読み手からの返事。「ここまで読めた。ここで分からなくなった」という、世界でいちばん正確な読書感想文。失敗の印ではない。
変数 variable
値につけた名前（あだ名）。箱ではない。同じ値に複数の名前をつけられるし、名前は別の値に付け替えられる。
ループ（くりかえし） loop
「3回ノックして」という日本語の省略を、コンピュータに通じる形にしたもの。新しい概念ではなく、ことばに最初からある仕組みの形式化。
条件分岐（もしも） if
「もし雨なら傘を持つ」の形式化。条件は「ほんとうか、うそか」で答えられる文でなければならない。
関数 function
辞書に新しいことばを載せること。一度「ゆでる」を定義すれば、毎回ゆで方を説明せずに済む。定義は一度、使用は何度でも。
引数 argument
ことばが要求する「〜を」「〜で」の空欄。「ゆでる（卵を、7分）」の卵と7分。
式 expression
評価されると値になるもの。「1 + 2 × 3」は式で、評価すると 7 という値になる。文が「こと」なら、式は「もの」。
評価 evaluation
式を値にすること。実体は「構造の木を、深い葉っぱから順に畳む」操作。
構文木 syntax tree
文の構造を枝分かれで描いたもの。プログラムの中では { op, left, right } のような、ただのデータの入れ子。
トークン token
ことばの粒。「言語の庭」を「言語/の/庭」と区切るように、コンピュータも文をまず粒に分けてから読む。
字句解析 lexical analysis
文字の列をトークン（粒）に切り分ける工程。言語処理系の3工程の1番目。
構文解析 parsing
トークンの並びから構造の木を組み立てる工程。3工程の2番目。優先順位の正体は、この工程が作る木のかたち。
インタプリタ interpreter
文字列→粒→木→値、と進む翻訳の手順を書いたプログラム。その場で意味にする。書き出しておくならコンパイラ。
再帰 recursion
手順の中に自分自身が現れること。木の枝の先にまた木があるから、木を畳む手順には再帰が自然に現れる。目が回るのは普通。
バグ bug
意図と動作のずれ。文法のまちがいはコンピュータが教えてくれるが、意図とのずれはあなたにしか分からない。
環境 environment
言語の記憶の正体。名前→値の対応表（辞書）が1冊あるだけ。変数が「箱」でない証拠でもある。
スコープ scope
名前が通じる範囲。実装の正体は辞書の重なり——関数を呼ぶたびにローカルな辞書を1冊重ね、手前から引く。
真偽値 boolean
「はい」「いいえ」という値。何を真とするか（1は真か？）の答えは言語ごとにちがう。真理の境界線すら設計。
キーワード keyword
if や while のような言語の合図。意味と表記は別もので、表記は対応表1枚で差し替えられる衣装にすぎない。
停止性問題 halting problem
「このプログラムは止まるか」を実行せずに判定するプログラムは書けない——書けないことが証明されている（チューリング、1936）。
正規表現 regular expression
ことばの「かたち」を言い当てる、数文字で書ける小さな言語。検索窓の裏に住んでいる。数えることはできないが、そのかわり暴走しない。
もよう（パターン） pattern
正規表現で書いた検索の指示書。特定のことばではなく「電話番号っぽさ」「日付っぽさ」のような、ことばのかたちを指す。
状態機械 state machine
丸（状態）と矢印（遷移）でできた機械。正規表現は実行のたびにこれに組み立てられる。覚え書きが有限個しかないので、入れ子は数えられない。
アルゴリズム algorithm
曖昧さがなく、必ず終わる手順。プログラムはそれをことばにしたもの。9世紀の数学者アル＝フワーリズミーの名前がなまった。
二分探索 binary search
そろっている列のまんなかを見て、半分を捨てる——のくりかえし。100万個でも約20回。速さは「そろっている」という前提への信頼で買っている。
計算量 computational complexity
手順の手間を「くらべた回数」で測ったときの、増え方のかたち。対数・比例・n log n・2乗。機械を速くするより、かたちを変える方が効く。
メモ化 memoization
一度計算した答えに名前をつけてとっておき、二度目は計算せずに答える工夫。速さを記憶の場所代で買う——時間と空間のトレードオフ。
チューリング機械 Turing machine
テープ・ヘッド・状態だけでできた、思考のための最小の計算機械。コンピュータが生まれる前に、計算の限界をこの機械が教えてくれた。
万能機械 universal machine
テープに書かれた他の機械の表を読んで、そのまねをする機械。「プログラムもデータである」の原点。あなたがコース2で作った評価器も、その一員。
対角線論法 diagonal argument
名簿の対角線をたどってぜんぶ裏返すと、名簿のどの行とも食い違うものが作れる——という技。停止性問題の証明の心臓部（カントール、1891）。
型 type
値の種類（数・真偽など）と、その種類にゆるされた操作の決まり。「一冊」「一頭」の助数詞がまちがうと感じる、あの違和感の親戚。
型検査 type checking
プログラムを実行せずに読んで、型のつじつまを調べること。実行が一本の道しか調べないのに対し、読む検査はすべての道をいっぺんに調べる。
型推論 type inference
書かなくても分かる型を、機械が埋めてくれること。「x * 2 が数なら、戻りも数」のように、式のかたちから型をたどる。
チョムスキー階層 Chomsky hierarchy
言語を力の順にならべた地図。正規言語＜文脈自由言語＜チューリング機械。力が増すごとに、速さや「止まる保証」をレジに置いていく。