独学Common Lisp

リストとラムダ、Lispの全て

チューリングマシンとラムダ計算

C言語の登場以来、"Hello World"でプログラミングの学習を始めるのが定番となっていますが、おそらくLispにおいては「計算」から始めるのが一般的でしょう(LISPはC言語よりもかなり古い言語です)。それは言語の考え方の違いであり、C言語はシステム開発言語なので「入出力」が特に重要な用途ですが、Common LispはC言語などとは別の計算モデルを持つ言語だからです。

C言語は計算機の動作にとても近い言語です。現代における計算機とは、メモリとCPUを中心とし、メモリにデータとプログラムをロードして、メモリから必要なデータをCPUのバッファに読み込ませて判断を行いながら次のデータ、次のデータへと進んでいきます。データとプログラムは共にメモリに読み込まれますが、プログラムは「判断する機械」の役割を担い、データは「処理される対象物」となります。そのため、メモリの確保や解放を伴いながら、プログラムをフィルタとしてデータを処理していきます。このような計算モデルはAlan Mathison Turingによって理論が提示され、John von Neumannによって機械としての設計が可能となりました。このような計算モデルを「チューリングマシン」と呼び、現代のコンピュータは「ノイマン型」であると呼ばれます。

しかし、チューリングマシンは人間の概念的な計算モデルとは対照的であり、人間は自分の脳(メモリ)の領域を右へ左へ移動しながら計算することはありません。私たちはより抽象的に数式を数式として、すなわち「数」と「記号」の並びに意味を感じながら計算を行います。1 + 2という数式を見ると、1という数と+という記号と2という数が存在することを認識し、+という記号がその前後の数を加算する記号であるという意味と文脈を考えて、3という結果を得ます。つまり、+という意味を持つ記号に対して12という数を「適用(application)」した結果、3という「評価(evaluation)」を得るのです。このように、数と記号という要素で適用と評価を繰り返していく計算モデルを考えたのがTuringの指導教官であったAlonzo Churchです。このモデルは「ラムダ計算」と呼ばれます。ラムダ計算は人間がそのまま理解できます。(なお、数学的なラムダ計算の体系では数も含めて全てを関数で表しますが、Common Lispは数や記号を独立したデータ型として持っています。)

LISPはラムダ計算を計算機で実行するために考えられました。Common Lispの背景にあるのはC言語とは異なるラムダ計算という計算モデルであり、ラムダ計算を最も簡潔に表現する手法として「リスト」が採用されました。

前置記法とリスト記法

先ほどの1 + 2という計算を思い出してください。ここでは3つの要素がありますが、3つの要素は大きく2つに分けることができました。それは「数」と「記号」です。12は数であり、+は記号です。

前節の説明では「12+に適用すると3と評価される」と説明しましたが、12+も「評価」してみることを考えましょう。

1には何かが適用されているでしょうか。何も適用されていません。では1を評価するとどのような結果が得られるでしょうか。評価する文脈が運動会の徒競走であれば1は「1位」のことを指すのかもしれませんが、我々が行いたい「計算」においては11で、ほかの何者でもありません。22です。より厳密に言えば、我々は'1'という「数字」を見て1という「数」であると評価しています。

では、+はどうでしょう。+1 + 2という文脈で使われた時に12を加算するのですから、+は「2つの数を加算する機能を持つ」ということになります。縦棒と横棒が垂直に交わったこの記号を「プラス」というのは「加算する」という「機能」があるからにほかなりません。つまり、+という記号は「加算する機能(Function)」として「評価」されます。計算において「機能(Function)」は「関数(函数)」と訳されますが、基本的にはキーボードに付いているファンクションキーのようなものと同じ概念です。

つまり、「数(数字)」を評価すると「数(Number)」を得ることができ、「記号(Symbol)」を評価すると「関数(Function)」を得ることができます。そして第二段階として一つの関数に2つの数を適用して、3という一つの数を得ているのです。

このように考えると、1 + 2という3つの要素の並びについて、本当にこれが正しい唯一の記法なのかという疑問が湧いてきます。なぜなら、本質的に同じ「数」に分類される12が分断されており、その分断をしているのは12を与えることで機能する関数+そのものなのです。丁寧に左から読んでいくと、これが「加算する」という機能であることが分からないまま、とりあえず1という数字を1という数として評価しなければなりません。+を認識した時点で初めてこれが「加算する」という数式であることを確認することができます。

人間の目は視野が広いので数式を一見しただけでそれが加算であることを認識できますが、計算機にはそれができません。そこで、+という関数としての記号を前に置く記法がLISPでは用いられています。つまり、+ 1 2です。

しかし、例えば( 1 + 2 ) * 3はどうでしょう。これは7つの要素で構成されています。1, 2, 3という3つの数と+, *という2つの記号、そして(, )というカッコです。数と記号はこれまで述べた通りですが、カッコは違う役割を担っています。それは「評価順序を決める」ということです。カッコはそれ自体が何かに評価されるわけでなく、ほかの要素の評価と適用のための「構文」なのです。英語でThis is a pen.と書いてあれば「これはペンです」と訳されますが、Is this a pen?と書いてあれば「これはペンですか」と訳されるように、同じ要素を使っても「構文」で意味が変わります。変わる、というよりも「変える」ために構文が存在します。このように、カッコは「構文」を示すため、それ自体として評価されることはなく、通常は「要素」としてカウントすることもありません。

(1 + 2) * 3を前置記法に変えると* (+ 1 2) 3ということになり、カッコをそのまま用いて表現することができます。ここで、カッコが計算の優先順位のためではなく、+という関数に適用される引数の範囲を示していることに着目して見てください。1 + 2 * 3は計算できますが、* + 1 2 3は計算できません。前者が計算できるのは、「演算子」に計算の優先順位をつけているためであり、計算結果が変わりますが計算することはできます。しかし、後者は*+という関数としての記号に何を適用させるのかが全く分かりません。つまり、後者にとってのカッコは「関数に適用する引数の範囲を決める」ためのものだったのです。

このカッコの役割をより一般化して考えると、(関数 引数1 引数2)という関係として記述できることになります。そこで、最初の+ 1 2もこの記法で記述すると(+ 1 2)となり、* (+ 1 2) 3(* (+ 1 2) 3)となります。試しにこれらを自分がインストールしたCommon Lispの処理系を起動した直後のインタプリタに入力して、Enterを押して見てください。計算式が評価され、39という評価結果が得られます。

これがCommon Lispの記法の全てです。このような記法を「リスト記法」と呼びます。

ラムダ計算とlambda

前節で用いた+*は意味を持つ記号であり、関数として評価されました。Common Lispでは記号を「シンボル(Symbol)」と呼びますが、果たしてシンボルに紐付けられた関数はどのように記述するのでしょうか。その関数の記述が「ラムダ(λ:lambda)」です。

例えば(+ 1 2)という時の+は λ x y . x + y と表現されます。これは数学上の表現ですので、Common Lispの表現に変えると(lambda (x y) (+ x y))となります。xyはどのような記号(シンボル)でもよく、2つの引数を取ることは重要ですがその引数にどのような記号が割り当てられるかは関係がありません。

+(lambda (x y) (+ x y))であると述べたのは、まさに言葉通りの意味です。前節で(+ 1 2)を入力したのと同じように、+の部分をラムダに置き換えてEnterを押してみてください。

((lambda (x y) (+ x y)) 1 2)
; => 3

+という記号(Symbol)が(lambda (x y) (+ 1 2))という関数(Function)に紐づけられているからこそ、結果が同じになります。つまり、「記号を評価して関数を得る」と言っていた時の「関数」がラムダです。これは言葉通りの意味です。ちなみにCommon Lispの+はC言語などの+よりも便利であり、引数が2つである必要はありません。(+ 1 2 3)6と評価されるように、引数の数は何個でも構いません。数学の + という演算子というよりもむしろExcelのSUM関数のようなものに近いです。

では、(* (+ 1 2) 3)のラムダ化に挑戦してみましょう。+(lambda (x y) (+ x y))であり、*(lambda (x y) (* x y))ですから、それぞれのシンボルに紐づけられたラムダをそのまま記述すればいいことになります。

((lambda (x y) (* x y)) ((lambda (x y) (+ x y)) 1 2) 3)
; => 9

見にくいと感じる場合は、改行してインデント付けを行います。

((lambda (x y) (* x y))
 ((lambda (x y) (+ x y)) 1 2)
 3)
; => 9

ラムダと束縛

Common Lispではlambdaはそれ自体が記号(Symbol)です。このシンボルはそれがラムダ表現であるという目印になります。つまり、

(lambda (引数1 引数2 ...) ラムダの中身)

という記述はそれが関数としてのラムダ表現であるということを示しています。このlambdaにはいくつかの特徴があります。

まず、lambdaで作られる関数は、引数が与えられた時にその引数を引数リストに列挙されたシンボルに紐付けます。(lambda (x y) (+ x y))というラムダに1 2という2つの引数が与えられると、xというシンボルに1が、yというシンボルに2が紐付けられます。このことをCommon Lispでは「バインド(bind)する」と呼び、日本語では「束縛する」と訳されます。その束縛は「ラムダの中身」部分だけ有効であり、これを「レキシカルスコープ(lexical scope)」を持つ、と言います。つまり、引数を引数リストのシンボルに紐付け、その状態でラムダの中身を処理し、得られる最終結果がそのラムダそのものの評価となります。

これは当然のことのように思われますが、中学校や高校で習う数学とは感覚が異なるでしょう。数学で関数は

f(x, y) = x + y

と定義し、使うときは

f(1, 2) = 1 + 2

と直接引数を引数リストの部分に記述するか、

x = 1
y = 2
f(x, y) = 1 + 2

とあらかじめ代入しておくかだったはずです。数学上の関数f()には与えられた引数を基に評価結果を得ることができますが、与えられた引数を引数リストに記述されたシンボルに束縛する機能は欠如していることになります。これがC言語をはじめとする現代の主流の言語で「代入」が多用される理由です。関数の定義と適用、そして引数の束縛を同時に行うことができるのがlambdaです。

もう一つの顕著な特徴は、関数はデータであるということです。言葉遊びなどではなく、真の意味でデータです。試しに、ラムダそのものをインタプリタに入力してみてください。

(lambda (x y) (+ x y))
; => #<Anonymous Function #x3020008F99EF>

#< ... >という評価結果は、Common Lispが読み取れないデータであることを示す評価結果です。例えば1はCommon Lispで読み取れますが、メモリ上に作成された関数は印字しても読み取ることができません。印字しても読み取ることはできませんが、データである以上、引数として別の関数に渡すこともできますし、関数を評価した結果として新しい関数を返すこともできます。データとしての関数を使って適用するにはfuncallを使います。

((lambda (f) (funcall f 1 2)) (lambda (x y) (+ x y)))
; => 3

lambdaが2つ存在します。先に右側のlambdaを見てください。これは今まで出てきた加算用の自作ラムダです。lambdaで生成されるこの自作ラムダはインタプリタに印字すると

#<Anonymous Function ...>

でしたが、このデータとしての関数を左のラムダに引数として渡すことができます。左のlambdaは渡されてきた自作加算ラムダをfというシンボルに束縛し、funcallを使って12という新しい引数を自作加算ラムダに適用します。その結果、データとしてやりとりされた自作加算ラムダが評価結果を返し、3が得られます。

では、少し振り返ってみてください。我々が最初に(lambda (x y) (+ x y))を使ったのは、「+というシンボルが評価されると加算関数が得られる」という意味の中で加算関数を自分でlambda表現にしたのでした。ラムダがデータであるということは、我々は+というシンボルから、束縛されたラムダそのものをデータとして取り出すことができるということです。シンボルからデータを取り出すにはfunctionを使います。

(function +)
; => #<Compiled-function + #x3000000BB0AF>

先ほどの(lambda (x y) (+ x y))の時とよく似ていますが、こちらはコンパイルされています。+はCommon Lisp処理系の実装者によって予め実装され、コンパイルされ、Common Lispに同梱されているのです。しかし、自作の加算ラムダと同じデータとしての関数であり、前述と同じように引数として渡すことができます。

((lambda (f) (funcall f 1 2)) (function +))
; => 3

+はシンボルですが、束縛されているのは関数としてのデータです。Common Lispにおける関数はこのように「キャッチボール」することができます。

ちなみに、funcallも関数ですが、functionは関数ではありません。

(function funcall)
; => #<Compiled-function FUNCALL #x30000007FA0F>
(function function)
; => ERROR

エラーが発生したら焦らずCtrl + Dを押すか、エラーメッセージに従って元の画面に戻るキー操作をしてください。Common Lispはエラーが起きるとデバッグ(Debug)モードに入ります。

functionは「スペシャルオペレータ(Special Operator)」と呼ばれるもので、データとしての関数が紐付いている訳ではありません。functionスペシャルオペレータは関数が束縛されたシンボルまたはlambda表現を引数にとり、データとしての関数を構築します。

(function (lambda (x y) (+ x y)))
; => #<Anonymous Function #x3020008BB53F>

Common Lispではlambdaが第一にシンボルとして定義されており、それがラムダ表現であることを示しますが、それだけでは単にラムダ表現であることを示す言葉通りのシンボル(目印)です。lambdaによるラムダ表現がfunctionの引数として使われていない場合、Common Lispの処理系によってfunctionが補完され、データとしての関数(ラムダ)が構築されます。このことはCommon Lispの仕様で定められており、仕様に準拠した処理系であれば等しく処理されますので、付けても付けなくても構いません。

Common Lispの「文法(構文)」と呼ぶものがあるとすれば、このページに書いている前置的なリスト記法とラムダ計算が全てと言っても過言ではありません。ラムダの持つ様々な特徴(関数の定義、適用と評価、引数の束縛、データとしての関数)はCommon Lispの根幹ですから、丁寧に学んでおいた方が後の学習が楽になります。このページで行った計算といえば1 + 2(1 + 2) * 3だけですが、LISPの計算の世界が凝縮しています。

参考文献

  1. チューリングマシンとラムダ計算、LISPを学ぶことの意義については「バベル案内」(Steve Yegge)を参照してください(原文)。10年以上前の文献ですが、初期のAmazon.comでLispが使用されていたことを示すほか、代表的な言語に対する適切な洞察が述べられています。
  2. 前置記法ラムダ計算についてはWikipediaを参照してください。このページではなぜ前置記法を使うかという理由に着目して記述しました。
  3. 加算関数と乗算関数についてはCommon Lisp HyperSpecを参照してください(Function +およびFunction *)。
  4. functionスペシャルオペレータについてもCommon Lisp HyperSpecを参照してください。「データとしての関数」という言葉を使いましたが、「レキシカルクロージャ("lexical closure")」という表現が正確です。合わせてfuncallも参照してください。
  5. lambdaにはシンボルとしての仕様マクロとしての仕様があることを述べました。一番上の"Syntax"という部分に使い方(構文)が掲載されていますが、シンボルの方は評価結果(=> function)が記載されていないことに留意してください。マクロの仕様では function が評価結果となることが記載されています。
  6. 最後に、functionスペシャルオペレータは#'というSharp-Quoteリーダーマクロで置き換えることができます。+というシンボルからデータとしての関数を取り出す(レキシカルクロージャを構築する)には(function +)と記述しますが、これは#'+と等価です。一般的には#'+のような記法が好まれます。

Copyright © 2017- satoshiweb.net All rights reserved.