Lisp の調べ Android の調べ 将棋の調べ 鉄道の調べ ビールコレクション
Software Design 2015年8月号
に執筆した「気軽に試してみよう！今こそ Lisp 入門」は
初心者向きの記事であったことやページ数の関係で、書き切れなかったことをここに（ぼちぼち）書いてみます。
「ソフトウェアデザイン 2015年8月号
第1特集 なぜ関数型プログラミングは難しいのか？
Lisp，Scala，Haskell，Elixir，Python，Clojure，関数型のエッセンスを学習する」より
（参考）Web増補版 はじめてのLisp関数型プログラミング ―ラムダ計算からリファクタリングまで一気にわかる
|
Tweet |
λ計算は関数型プログラミングでは基本中の「キ」ですが、本文は初心者向けということでカットしていますが、ここでは少し説明します。
λ計算（λ-calculus）はα変換とβ-簡約、η-変換の規則があります。
α-変換は束縛変数の名前を変える変換で、β-変換（簡約）は関数適用です。
η-変換はすべての引数で同じ値を返す関数は等価である（関数の外延性）とするものです。
α-変換の例はλx.fx → λy.fy であり、β-変換の例は(λx.fx)3 → f3であり、η-変換の例は λx.fx → f（但しxはfで自由でないとき）です。
Lisp 風に書くのであれば、(lambda (x) (f x))→(lambda (y) (f y))、((lambda (x) (f x)) 3)→（f 3)、(lambda (x) (f x))→fです。
λ計算はこの3個の規則だけで計算します。
次にカリー化とは、複数の引数を取る関数を、1引数の関数に変換することです。
最初の引数を取る関数にして、その関数は残りの引数を取る関数を返します。
λ式ではλx.λy.fxyとカリー化（1引数化）して表現します。またλx.λy.fxyをλxy.fxyと略記することがあります。
Lisp 風に表現すると(lambda (x y) (f x y)) を (lambda (x) (lambda (y) ((f x) y)))に変換することです。
またλ計算では数値を以下の例のようにλ式で表現できます。これをチャーチ数と言います。
例. 0=λx.λy.y, 1=λx.λy.xy, 2=λx.λy.x(xy), ..., n=λx.λy.x(x(...(xy)))...)。
このとき、1個足し算をするSUC関数は λx.λy.λz.y(xyz)となります。SUC(0)が1になり、SUC(1)が2になることを確かめてみてください。
---おまけ---
・SUC(0)=1, SUC(1)=2となることの確認
SUC(0) = (λx.λy.λz.y(xyz))λx'.λy'.y' = λy.λz.y((λx'.λy'.y')yz) = λy.λz.y((λy'.y')z) = λy.λz.y(z) = λx.λy.xy = 1
SUC(1) = (λx.λy.λz.y(xyz))λx'.λy'.x'y' = λy.λz.y((λx'.λy'.x'y')yz) = λy.λz.y((λy'.yy')z) = λy.λz.y(yz) = λx.λy.x(xy) = 2
・これを Lisp 風にして確認
0 = (lambda (x) (lambda (y) y))、SUC = (lambda (x) (lambda (y) (lambda (z) (y ((x y) z)))))となり、
SUC(0) = ((lambda (x) (lambda (y) (lambda (z) (y ((x y) z))))) (lambda (x') (lambda (y') y'))) =
((lambda (y) (lambda (z) (y (((lambda (x') (lambda (y') y')) y) z))) = ((lambda (y) (lambda (z) (y ((lambda (y') y') z))) =
(lambda (y) (lambda (z) (y z))) = (lambda (x) (lambda (y) (x y))) = 1となります。・・・括弧の数が間違っていなければいいのですが。
---おまけ終わり---
このようにλ計算では値も式も同じλ式で表現できます。
また、λ計算はチューリング完全であり、チャーチ・ロッサー性も保証されるなどの重要な性質があります。
引数の評価をいつするかという問題です。
評価を遅延させることで、その評価を無駄にする機会が減らすことができます。
通常の評価戦略では「内側優先 innermost」「左側優先 leftmost」戦略で実装されていますが、
この評価戦略では、(defun foo (x y z) (if (eq x y) z)) のとき、x と y が等しくないときも z を
評価してしまいます。
その結果、例えば、(foo 1 2 (tarai 15 10 5))では(tarai 15 10 5)の評価が無駄になります。
これを解決するために、色々な評価戦略が考えられています。
一番、簡単なものは(a)「外側評価 outermost」で評価する戦略や、
(b) プログラマが遅延評価をする引数を選択させる戦略、
(c) またプログラムを解析して、必須項（必ず評価が必要な引数）である x と y のみを評価する「必須評価 call by need」戦略などがあります。
これは関数型プログラミングの本質ではありませんが、効率的に実行するためのテクニックの一つで、関心の高い話題になっています。
関数型プログラミングは基本的には並行(Concurrent)動作と並列(Parallel)動作が可能で、
またスレッドセーフ(thread safe)であり、リエントラント(reentrant)です。
これはグローバル変数を持たず、状態を持たず、再代入などによる副作用を生じさせないからです。
しかし純粋な関数型プログラミング以外では、「多少」の副作用は使うでしょうから、
手続き型プログラミングまではないにしろ、並行処理を可能にするためには、少しは制御が必要になるでしょう。
これは逆に考えれば、並行に動作させたい箇所は純粋な関数型プログラミングをすることで、
変な制御を不要にすることができます。
本文でも副作用はバグの温床であり、そのバグを見つけるのは砂漠の中の砂粒を見つけるくらい困難なことであると言いました。
しかし、まだ脅しが少ないように感じています。
もっともっと副作用の恐怖を騙る、いえ、語るべきだったかも知れません。
本文で説明したように参照透過性を持つ関数型プログラミングでは、副作用を考慮しなくていいので、
等価なものを単純に置き換えることができます。
これにより、プログラムを形式的に（数学的に）取り扱うのが容易になります。
関数型プログラミングは形式手法とうまくマッチします。
本文は、関数型プログラミングそのものの記事でなく、Lisp 入門の記事でしたので、
関数型プログラミングの利点と欠点を箇条書きにして、欠点と付き合う方法も一言で済ませています。
やはり、ここはもっと具体例を入れて、関数型プログラミングの利点と欠点を実感させて、洗脳、いえ、推薦したかったのですが。
次回は「関数型プログラミングは本当のところ、どうよ？kwsk」でしょうか。
チャーチ・ロッサー性（Church-Rosser Property: CR性）とは、項書き換え系（Term Rewiting System:TRS）において、
項 t1 と t2 が有限回で書き換えられるとき、t1 と t2 が合流する項 t3 があるという性質です。
つまり、CR性があると、ラムダ計算のβ簡約（項書き換え）が書き換え順序に関係なく適用できるので、
並列処理や最適化において、重要な性質になっています。
どのような書き換え規則のときに、このCR性が保証できるのかは、色々と研究がなされています。以下にその例を示します。
Gomi,H., Oyamaguchi,M. and Ohta,Y.: On the Church-Rosser Property of
Root-E-overlapping and Strongly Depth-Preserving Term Rewriting Systems,
Trans.IPS.Japan, vol.39, No.4, pp.992-1005(1998).
Gomi,H., Oyamaguchi,M. and Ohta,Y.: On the Church-Rosser Property of
Non-E-overlapping and Strongly Depth-preserving Term Rewriting Systems,
Trans.IPS.Japan, vol.37, No.12,pp.2147-2160(1996).
また CR性とともに、重要な性質に「停止性」があります。TRS が停止するための条件、つまりラムダ計算のβ簡約が停止するための
条件に関する研究も多くなされています。
ここの項目に関して、やさしい例やオチを仕込んでいません。今後、これらを入れるようにしますので、お待ちください。
末尾再帰とは、if 文の再帰項（再帰呼び出しが入っている項）のトップレベル（最左）の関数が自分自身となっているものです。
つまり、(defun foo (n) (if (= n 0) ... (foo ...))の形になっている再帰です。
末尾再帰になっていると、再帰で消費するスタックサイズが減少し、また最後の再帰呼び出しが単純な go to 文に最適化することが可能です。
Scheme では言語仕様で末尾再帰の最適化をする仕様になっています。
・・・末尾再帰化はは言語インプリメンタの腕の見せ所なのに義務になっているところが嫌。
例えば、階乗 fact の定義が (defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1)))))のとき、末尾再帰は
(defun fact-tail (n) (fact-tail2 n 1))
(defun fact-tail2 (n f) (if (<= n 1) f (fact-tail2 (- n 1) (* n f))))
となります。
またフィボナッチ数計算 fib の定義が (defun fib (n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))))) のとき、末尾再帰は
(defun fib-tail (n) (fib-tail2 n 0 1))
(defun fib-tail2 (n f0 f1) (if (< n 1) f0 (fib-tail2 (- n 1) f1 (+ f0 f1))))
となります。
末尾再帰を go to 文に変換しなくても、再帰のスタックは減少しますので、それだけで効果があります。
例えば、階乗 fact は元のままであれば、(fact 153)までしか計算できなかったのが、末尾再帰にすると 198まで計算できます。
ISLisp>(fact-tail 198) 19815524305648002601818171204326257846611456725808373449616646563928629396065410 62613829859326594532422555809394270449322255383895082002776537504082796055103300 15793284111386240552007272342323020465242271420611379865359604881481118913950814 67526982493475408477527124840709196781511817187496273890924527108598562553359394 406400000000000000000000000000000000000000000000000
mapcar については本文で紹介しましたが、それと対になっている reduce については
ページ数の関係で紹介していませんでした。しかし map と reduce は高階関数の便利な例として、
そして何よりも便利な機能です。
次に Common Lisp の関数 map と reduce の例を示します。
(map 'list #'+ '(1 2 3) '(10 20 30)) → (mapcar #'+ '(1 2 3) '(10 20 30)) → (list (+ 1 10) (+ 2 20) (+ 3 30)) → (11 22 33)
(reduce #'+ '(1 2 3 4 5)) → (+ (+ (+ (+ 1 2) 3) 4) 5) → 15
また、reduce のエラーチェック無し版の実装は以下のようになります。
(defun reduce (fun list)
(if (= (length list) 2)
(funcall fun (car list) (car (cdr list)))
(reduce fun (cons (reduce fun (list (car list) (car (cdr list)))) (cdr (cdr list)))) ))
プログラム中に、1 + 2 が現れれば、どんなコンパイラでも コンパイル時に事前に
計算して、3 の値を生成するコードに入れるでしょう。
これと同様に、例えば、f(1, g(2)) のようなすべての引数が定数か定数項からなる項「定数項」も事前計算したくなるでしょう。
例えば、f(1, 2) や f(g(x), g(2))、foo(1).bar(x) となっていれば、それぞれ f(1, 2) や g(2)、foo(1) の定数項を事前
計算したくなるでしょう。
しかし、副作用があるかも知れない言語では、この事前計算を行うと、結果が異なって
しまう危険性があります。このため事前計算は慎重にならざるを得ません。
例えば、f(g(x), g(2))で g(2)をコンパイル時に計算すると、後で実行時に g(x)を計算した
結果の副作用が及ばず、違う値になるかも知れません。
最適化などのために引数の評価順序を保証しない言語では、もちろん、定数項の事前計算は
できます。結果が違ってもプログラマの責任になります。・・・厳しいです。
ここから得られる教訓は、(1) 副作用を使わないようにするか、(2) コンパイラが困るような
定数項はプログラマが自分自身で事前計算しておくかになります。
定数項なんて、使わないよという方も、結構使っていますので、ご注意ください。
FRP は関数型プログラミングと直交する概念ですが、関数型言語で流行していますので、ここで紹介します。
リアクティブプログラミングとは、値の関係を暗黙的な再計算によって常に同じに保つものです。
例えば、a == b + 1という関係を定義すれば、a が 3 や 4 になったときに b は 4 や 5 に暗黙的な再計算によって「自動的に」なるものです。
上記は関係とその実装を同時に言っていますが、実装を無視すれば、a の値によって b の値はいつも a + 1 になっています。
実際の実装では再計算は効率よく実施します。
C などのホスト言語と全く無関係な単なる書き換えマクロでなく、
Lisp 言語そのものでマクロ展開を動的にできる強力で柔軟なマクロ機能を持っています。
このため、Lisp 言語自身の拡張が容易にできます。
これは別の問題も解決できます。
Lisp には色々な方言、流派がありますが、この強力なマクロ機能により、互換パッケージが気楽に作れます。
例えば、ISLisp に Common Lisp パッケージを作るのも可能です。
Common Lisp の dolist のマクロ定義は、ISLisp では以下のようになります。
この他の Common Lisp 互換パッケージをマクロ定義のサンプルとして、後でサンプルプログラムとして、紹介しています。
(defmacro dolist (lists &rest forms)
`(let ((list ,(second lists))
(,(car lists) nil) )
(while list
(setq ,(car lists) (car list))
,@forms
(setq list (cdr list)) )))
Lisp は実行中に関数を動的に定義できます。 オブジェクト指向機能を持つ Lisp ではクラスも動的に再定義可能です。
S式(Symbolic Expression)が今の Lisp の構文であり、EV-Lisp の構文(f x y)のように書きます。
M式(Meta Expression)はマッカーシーが当初、Lisp の構文として考えていたもので、EVQ-Lisp の構文的に f[x;y]のように記述します。
S式は内部表現であり、意味論を記述するものとして考えていました。
現在は、構文も内部表現も意味論も S式で表現します。
Common Lisp などで導入された関数閉包と Scheme に昔からある継続は重要な概念です。
両者の関係も含めて学ぶ必要があります。
多くのプログラミング言語では関数の返す値は1個です。
2個以上の値を返すときは、「へたくそ」な実装で、副作用を期待した引数を渡すとか、
ヒープ領域を使用してメモリを無駄遣いして返すとかの実装になります。
Common Lisp では複数の値を返す機構があります。もちろん、ヒープ領域を使いません。
安心して多値を返してください。
Lisp のベンチマークプログラムとして有名なのに tarai関数があります。
竹内郁雄が1976年に作成したもので、
(defun tarai (x y z) (if (<=x y) y (tarai (tarai(1- x) y z) (tarai (1- y) z x) (tarai (1- z) x y))))
です。再帰関数で数多く実行されます。
Lisp はオブジェクト指向機能の実装の実験場としても使われていました。
Common Lisp の CLOS は総称関数で実装されましたが、Flavors のオブジェクト指向機能がエポックであったことを紹介したかったと思っています。
CLOS や ILOS の持つ適用可能メソッドの優先順位によって、if 文なしプログラミング（パターンマッチ）が組めます。
例えば、整数の 0 だけを持つシングルトンクラスを定義すれば、整数のクラスと比較して、より特定的なので、シングルトンクラスが優先されます。
これによって、例えば、階乗を(singleton 0)のクラスのメソッド（総称関数）と(integer)のクラスのメソッドを定義すれば、if文が不要になります。
もっと言えば、単純なパターンマッチよりももっと複雑なマッチングアルゴリズムが組めます。
Lisp は純粋な関数型プログラミング言語でないという評価がありますが、
逆に考えれば、関数型プログラミング言語のパラダイムと手続き型（命令型）プログラミング言語のパラダイムを
合わせ持ったマルチパラダイム言語だという売り文句をもっと積極的に書くべきだったかも知れません。
要は問題に応じた、最適なプログラミングパラダイムでプログラミングできるように、プログラミング言語はその仕掛けを提供するのがいいと思います。
一方、パラダイムを規制することで、作成されるプログラムを統一管理する方法もありますが・・・好みではありません。
Common Lisp の言語仕様は1000ページを越えるものになっていますが、一方、Scheme の言語仕様は数10ページしかありません。
まさに Lisp は世界最大の言語であり、世界最小の言語でもあります。
CLtL2は1000ページ以上ありますので、自立できます。
Common Lisp におけるタイプとクラス、構造体の関係はやはりオーバースペックのような気がします。
もっとうまく三角関係を調整できることもできたろうに・・・ジョークネタにも？
シンボルが持つ値や関数、プロパティを1個のみで管理する Lisp-1 か、2個以上で管理する Lisp-2 かの話です。
最近の Lisp は Lisp-2 で、値と関数などを別に持つことができます。
一方、Lisp-1 では (defvar automobile '車)はできても、(defvar car '車)はできません。一般人からは不思議がられます。
しかし、Lisp-1 の方はメモリフットプリントは小さいのですが、今では些細なことになりました。
例えば、append は副作用を生じさせないために第1引数のリストをコピーします。
もし副作用が問題ないときは副作用版の append である nconc を使うことで、コピーの無駄を省けます。
このように Lisp プログラミングではパフォーマンスチューニングのために、副作用版の関数を使うことがあります。
Lisp と言えば GC。GC と言えば Lisp。というくらい、Lisp と GC は一体化されて話題になっています。
事実、GC の実験場としての役割も果たしてきました。Guy L.Steel が SUN(Oracle)で Java の GC の開発に携わったのもこの流れでしょう。
本文でも触れましたが、同じデータ表現である S 式でデータもプログラムも表現するために、 動的なプログラミング、特にリフレクション（プログラムの動的変更）が他の言語、Java や Ruby, Python などの リフレクション機能のような面倒な呪文を覚える必要はありません。自然な流れで実行できます。
一般的な Lisp 処理系では無限長整数(bignum)をサポートしています。
整数とシームレスに使えます。内部で整数と無限長整数は自動的に変換しています。
スタックとヒープサイズに大きさは制限されます。
例えば、Windows 版の OKI ISLisp であれば、153の階乗が計算できます。
これは bignum の制限ではなく、階乗計算時のスタックサイズの制限です。
例えば後述されている末尾再帰にした階乗計算では198まで計算できます。
ISLisp>(defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1))))) FACT ISLisp>(fact 153) 20063439050956823947782887469891171856624614961616117193423109928484094602523809 23396132940626035884355303931450486630471730519135077116322163056671295549006202 96603188543122491838966881134795135997316305640071571629943041039657861120000000 000000000000000000000000000000
汎変数は Common Lisp から導入された概念で、今までの Lisp が変数に代入する関数は setq でしたが、
これを拡張して、変数だけでなく、すべての場所（汎変数）に代入できるようにした setf が導入されました。
例えば、(setf (car (cdr list)) 10)のように使うことができ、これは list の2番目の要素を10にするものです。
また defsetf により、setf の動作が定義できるようになりました。それも簡単な形で定義するものと、
マクロ定義と同様な方法で定義する2種類がサポートされています。
Common Lisp 以降、この汎変数の考えは多くの Lisp やその他の言語に影響を与えています。
メタサーキュラーは日本語では「超巡回的な」または「メタ巡回的な」と訳されています。
Lisp 関数である apply と eval は、Lisp インタプリタそのものです。
その Lisp インタプリタの一つの関数として apply と eval があり、apply と eval はインタプリタの一部です。
このように実現が巡回的になっていることをメタサーキュラーと言います。
このようなメタサーキュラーな Lisp の意味論は不動点として与えられると考えられています。
本文でもクロージャは環境を閉じ込めると言いました。
クロージャが閉じ込める環境は、変数そのものを閉じ込めます。以下の例を見ていきます。
; 二つのクロージャは同じ x を閉じ込めます ISLisp>(defglobal c (let ((x 10)) (cons (lambda () x) (lambda (y) (setq x y))))) C ISLisp>c (#<UFUNCTION 0026F636: #<LAMBDA>> . #<UFUNCTION 0026F436: #<LAMBDA>>) ISLisp>(apply (car c) ()) ; 「閉じ込めた x」の値は 10 になっています 10 ISLisp>(apply (cdr c) '(20)) ; 「閉じ込めた x」に 20 を代入します 20 ISLisp>(apply (car c) ()) ; 「閉じ込めた x」の値は 20 になっています 20
次にこのクロージャの実装を考えてみます。実装を考えることで、よりクロージャのことが分かってきます。
上記の(car c)のクロージャが閉じ込めたのは、その値が10であるローカル変数 x です。これを (x 10)と表記します。
次に(cdr x)のクロージャが閉じ込めたのも同じ x です。これも(x 10)と表記します。
この二つの(x 10)が同じものであるようにすれば、どちらか一方で値を変えれば、もう一方でも副作用で値が変わります。
クロージャの一つの実装方法は(x 10)のリストを同じもの＝同じアドレスのリストにする方法があります。
今回はリストで説明しましたが、実際はベクターの方がいいでしょうし、内部ではファーストクラスオブジェクトにする必要もありません。
Lisp のシンボルはシンボルテーブルによってインターンされています。
シンボルテーブルとは名前の示す通り、シンボルを管理しているテーブルで、その実装はハッシュテーブルです。
シンボルがインターンされているとは、シンボルテーブルに登録されていることです。
シンボルは、シンボルテーブルの実装であるハッシュテーブルによって、その唯一性を保証しています。
つまり、シンボルの名前が同じとき、例えば(eq 'symbol1 'symbol1)は t を返します。
シンボルがインターンされることによって、シンボルの等価判定が高速にできます。
しかし逆にシンボルをインターンするときには時間が掛かります。
インターンの逆のアンインターンもあります。これはシンボルをシンボルテーブルから削除することになります。
ここまで話を聞けば分かるかも知れませんが、インターンは Lisp 実装の大きなキーになります。
その実装のキーはシンボルテーブルの実装であるハッシュテーブルです。Lispインプリメンタにとっては苦労のしがいがあるところです。
まず、スコープは参照の有効範囲のことで、エクステントは参照の有効時間のことです。
レキシカルスコープ lexical scope とは、コンパイル型言語であれば、普通のスコープです。
単純に字句解析だけで求まる有効範囲(scope)で、昔からの歴史あるスコープです。
例えば、(lambda (x) (lambda () x)) のとき、x は外側のラムダで宣言されたものです。誰がどう見てもそうですよね！
レキシカルスコープは Scheme で採用され、Common Lisp 以降の Lisp では、このレキシカルスコープを採用しています。ってこれだけだと当たり前のことのようですよね？
しかし、昔の Lisp、主にインタプリタで動作することが主目的である Lisp では、レキシカルスコープでないスコープがありました。
もっと悪いことに、昔の Lisp ではインタプリタのときとコンパイルしたときのスコープが違う極悪非道なものもありました。
インタプリタでは、ダイナミックスコープ（無限スコープ＋動的エクステント）で、コンパイルするとレキシカルスコープになるという極悪非道なものでした。
これはインタプリタではレキシカルスコープを作るのが面倒だったからです。これについては「クロージャは苦労するんじゃ」を参考にしてください。
レキシカルスコープは上述したものですが、これ以外に無限スコープ infinite scope があります。
無限スコープはエクステント（有効時間）内であれば、どこからでも参照できるものです。
エクステントには動的エクステント dynamic extent があり、これは特定の時間範囲で有効というものです。
Common Lisp の例では with-open-file (ファイルがオープンしている間有効)があります。
さらに Common Lisp ではスペシャル変数、ISLisp では動的変数 dynamic variable のエクステントがそうです。
昔の Lisp のインタプリタで、ローカル変数（引数）のエクステントもそうでした。
[昔の Lisp の例] (setq x 10), (defun foo (x) (bar)), (defun bar () x)としたとき、(foo 20)の値は 10 でなく 20 でした。
エクステントにはその他に無限エクステント infinete extent があります。いつでも参照が有効になるものです。
クラスのインスタンスなどの一般のデータがこれに相当します。
Lisp オブジェクトは参照がなくなれば GC によってオブジェクトは消滅しますが、このときも無限エクステントと言います。
深い束縛 deep binding と浅い束縛 shallow binding をご存知でしょうか。
言葉通りに深くきつくと縛るか、浅く緩く縛るかです。
・・・ではなくて、動的スコープ（無限スコープ＋動的エクステント）のときの実装方法です。
ここで例を考えてみます。(defun foo (x) (bar)) (defun bar () (baz)) (defun baz () x)を考えてみます。
もちろん、レキシカルスコープのときは、baz の x はグローバルな x です。
しかし、動的スコープのときは、(foo 10)と呼び出されたときは、baz の x は foo の x になり、10です。
このように実行時に x が決定されるので、動的スコープ（動的エクステント）と呼ばれます。
この動的スコープの実装を考えてみます。
まず、このときのスタックがどうなっているかを見ると、foo のフレームの上（push 方向を上としたとき）に
bar のフレームがあり、その上に baz があります。
普通に考えられる実装としては、このスタックを baz フレームから foo のフレームにある x を見つけるまで
フレーム単位でスタックを上から下へ辿っていきます。いわゆるスタック辿りです。
これが深い束縛です。スタックを深く深く辿っていくために、このように呼ばれます。
この実装は簡単です。探索は単純な繰り返しで実装できます。
関数から戻るときにスタックを畳むのも簡単です。スタックポインタやフレームポインタを戻すだけです。
しかしxの探索は O(n)も掛かります。関数の呼び出しの深さに比例します。深すぎます。不快です。腐海の底に沈みます。
これに対して、浅い束縛とはどんな実装でしょうか。
浅い束縛はどんな変数探索も1回で見つけるものです。
この実装方法は、動的変数（ダイナミックスコープを持つ変数。Common Lisp ではスペシャル変数）も
グローバル変数と同じようにシンボルテーブルに登録します。
これで動的変数の探索はグローバル変数と同様にシンボルテーブルから取り出すだけです。
シンボルテーブルはハッシュテーブルで実装されていますから、もちろんO(1)です。
しかし実装は複雑になります。関数から戻るときにスタックを畳みますが、このときシンボルテーブルに登録されている
動的変数の値を設定し直さなくてはいけません。ここが面倒です。そして実行時間も掛かります。
しかし動的変数の探索が速いので、普通はこちらの浅い束縛で実装されています。
あなたはどちらで束縛しますか？
Common Lisp ではスペシャル変数、ISLisp では動的変数（ダイナミック変数）と呼ばれる変数は、ダイナミックスコープ（無限スコープ＋動的エクステント）を持つ変数です。
ダイナミックスコープについては、(23) 深い束縛と浅い束縛、あなたの好みは？を参照してください。
一言で言えば、動的にスタック辿りをして変数を見つけるものです。実行しないと何に束縛しているか分かりません。
このスペシャル変数はこのようにカタカナで書くと、なんか格好いい変数のように聞こえます。スペシャルですから。
いいものではありません。きっと、あなたの将来に禍（わざわい）を招くでしょう。デバッグするときに・・・
誰が私のスペシャル変数を壊したのか？（マザーグース風に）
Lisp には色々な掟があります。構文規則やその意味論だけでなく、慣習 convention と呼ばれる掟があります。
今日はその中で一番大切な掟について書きます。一番大事な掟とは、ずばり命名規則です。ネーミングです。これだけで、どれほどの Lisper か分かります。
例えば、C# は Pascal - Delphi という流れで、命名規則は Pascal 形式（FooBar のようにキャピタライズする形式）が基本です。
Java はややこしくて、クラス名は Pascal 形式、メソッド関数名は Camel 形式(fooBar のように最初の単語は小文字 lower case にする形式）、
定数は Snake 形式（FOO_BAR のように大文字 upper case で書き、連結は _ (アンダーバー)で行う形式）です。
このように、ネーミングは各プログラミング言語の文化になっています。
Common Lisp を始めとする Lisp のネーミングはどうなっているでしょうか。やはり、ここでも他のプログラミング言語と比較して、異質なものになっています。
まずは使える文字が違います。-(ハイフン、マイナス記号で代替)などが使えます。これはプログラマ以外では一般常識でしょう。この意味では Lisp 以外がおかしいのです。
次に先頭文字が数字から始まっても大丈夫です。数字と区別するための文字がどこかにあれば大丈夫です。例えば、1.2e0 は数字ですが、1.2e0x は名前です。
Lisp では大文字と小文字の区別はしますが、デフォルトでは大文字インターンです。小文字でインターンしたいときはエスケープ文字を使います。
例えば、|aBc|や\ab\c のようにします。しかし面倒なので普段は大文字インターンになります。
ここまでは強制的な仕様ですので、ここは Lisper 全員が守ります。
Lisp ではハイフンが使えますので、単語の連結は foo-bar のようにします。例えば、ILoveYou でなく、i-love-you です。これが第一の規則です。
次の掟は、グローバル変数のネーミングです。*global-variable* のように、* アスタリスクで囲みます。これが第二の規則です。
なお、* には特別な意味はなく、単に目立ちたいからです。もっと言えば、グローバル変数を使う戒めになります。* が恥ずかしければ、使うな！ということです。
Common Lisp のスペシャル変数もグローバル変数の一種ですので、罰（×）の意味で * で囲みます。
定数は一般的な掟はありません。+foo-bar+ のように + で囲うネーミングもありますが、全く一般的でありません（きっぱり）。
それよりもやはり SNAMKE 形式でしょう。。。
述語関数（t または nil の真理値を返す関数）は、語尾に述語 Predicate の P を付けるのが掟になっています。例えば、integerp です。
但し Scheme などではこの限りではありませんが、これも第三の規則です。
実はネーミングに関しては、まだまだ表と裏の掟があるのですが、今日はここまでになります。。。
Lisp の原罪と呼ばれるものがあります。それは括弧です。括弧の多さです。Lisp の括弧が深すぎて、これが Lisp の深い闇になっています。
この括弧を見やすくするために、Lisper はホワイトスペース、特にインデントを使って、立ち向かってきました。
しかし、このインデントが新たな戦いの幕開けになっています。つまり、どのようにインデントをするかで、流派があります。そこで争いがあります。
この争いは Lisp に限ったことではありません。古くは C 言語でもこの戦いはありました。
K&R派 v.s. ホワイトスミス派の戦いが勃発しました。
最近では、PASCAL - Delphi の流れを組む C# のインデントスタイルと、一方、Java 世界で流行っている傾斜派と呼ばれる争いがあります。
プログラムを見やすくするための戦いですが、みにくい争いになっています。
Python では、死活問題ですが、逆に大きな差はなく、それほど戦いはありません。
残念ながら、Lisp の世界でも、C や Java ほどではないですが、このインデントの戦いはあります。傾斜派とか、Delphi 派とかのスタイルではありませんが、やはり、改行の位置と、
改行の後の空白の個数、つまりタブに相当するインデンテーションの戦いがあります。
さらに Lisp では、閉じ括弧と閉じ括弧に空白を入れる位置についての戦いもあります。
一方、整形出力（プリティプリント）はこのインデントに影響されます。
同様に整形入力（プリティリーダ）も影響を受けますが、最近では、Lisp プログラムも普通のエディタで入力することが多く、エディタに依存します。
なお、エディタについては別でお話させていただきますが、もちろん、Emacs がお勧めです。
このインデントとプリティプリントでのお勧めのスタイルは、ここでは紹介しません。宗教戦争になりますので、それにくみしません。
郷に入っては郷に従うことが、やはり、ここでも大事です。スタイルに拘りすぎない方がいいかも知れません。
（ぼそっ）どうせ、Emacs エディタで1発でスタイルは変更できますので。
変数 variable とは、値 value を格納できる場所を提供するものです。
変数に対する操作は値参照（未束縛参照も含む）と値変更（初期値設定と未束縛化も含む）です。
逆に考えれば、値参照と値変更の関数が定義されているオブジェクトとみなすことができます。
今や、この考えは普通の考えで、例えば、中途半端ながら、Java や C# などにも、セッタ関数やゲッタ関数として、アクセッサ関数が定義されています。
Lisp は当初から、束縛 binding するのは値だけでなく、ラムダ式も普通の値と同様に束縛できます。
つまり、Lisp では変数と関数は同じものです。
束縛しているものがラムダ式のときは関数適用を行い、普通の値のときは右辺値であれば値参照し、左辺値であれば値変更を行います。
つまり Lisp は本来的に値指向であり、関数指向（関数型）でした。
特に Lisp-1 ではそのイメージが分かりやすいものです。
変数はもはや値だけでなく、値を格納する場所さえも隠ぺいできます。実装者に一任できます。
実装者は初期値設定、値参照、値変更、未束縛化の4個の関数を作りますので、それを使うだけです。
Lisp ではコンパイラも関数であり、その関数 compile は関数単位で実行中にコンパイルできます。
つまり Lisp は動的分割コンパイルが可能です。
これが Lisp の実行時間が遅くなる原罪の一つになっています。
分割コンパイルができず静的リンクをする言語と比較して、実装で苦労する点です。
次にこれを実装側から考えてみます。最初は簡単な方法を考えてみます。
(1) シンボル経由で関数を実行
例えばシンボル経由で関数呼び出しをする方法があります。シンボル経由ですので、メモリアクセスが1回入ってしまい、遅いです。
ベンチマークのようなプログラムでは、これは致命的な遅さです。C プログラムには決して勝てないでしょう。
しかし実験的な小さな Lisp 処理系ではこの実装を採用しているものもあります。
そこで次に余計なメモリアクセスをせずに済む方法を考えてみます。
(2) 動的コンパイルで動的リンク
動的コンパイルをしたときに、新しいコードを呼び出すように、関数呼び出しの飛び先アドレス直接書き換える方法があります。
つまり、動的にリンキングする方法です。
このリンキングの実装では、コンパイル実行が少し遅くなりますがシステムのリンカを使う方法と、面倒ですが自作でリンカを作る方法があります。
これは別の Lisp の罪「他言語インタフェース」の実装でもきっと同じ作りになるでしょう。
ウェイトレス「コーヒーでいいですか？」
Lisper「T」(yes の意味で Lisp の真の値である T と答えた)
ウェイトレス「紅茶(Tea)ですね」
人工知能マシンでなく、Lisp のベンチマークプログラムである。
その証拠に Lisp を作れば必ず、tarai(またはtak)を実行していた。
情報処理学会の記号処理研究会でも、ベンチマーク大会が開催されていた。
Lisp の述語関数(真理値を返す関数)は、integerp や subtypep などのように post-P (語尾に述語 Predicate の P を付ける)が慣例である。
Lisper「コピーするのですか→コピピ」（発音はこぴぃーぴっ？）
Lisper「この文字は P ですか→ピピ」（発音はぴぃーぴっ？）
Lisp を中置記法にしてみた
(fact defun (n) ((n <= 1) if 1 (n * ((n - 1) fact))))
どうでしょうか？見やすいでしょうか？見にくいですよね。やはり、前置記法の方がいいですよね。
(defun fact (n) (if (n <= 1) 1 (* n (fact (n - 1)))))
Lisper は他のプログラミング言語との他流試合が好きである。
これはどんな言語にも勝てる自信があるからである。
なんとなれば、Lisp には色々な方言、亜流があり、彼らを味方に引き入れて、勝つのである。
並列勝負なら、昔からある各種の並列 Lisp を前線に送り出し、勝負をするのである。
ここで一つだけでなく複数の合わせ技を用いるのが勝つ秘訣である。
それでも負けそうなときには、逆転できる魔法の言葉がある。
「でもそれは、Lisp の影響を受けているんでしょう」
これはニクラウス・ヴィルトの有名な本の題名であり、プログラマであれば、誰も一度は目にしたことがあるだろう。
・・・その本を読んでいるかどうかは別にして。
一方、リスプはデータとプログラムは同じリストで表し、データとプログラムは同じであると考える。
これも Lisper であれば、誰しもがそう思うであろう。
これはつまり、「データ構造＝プログラム」と表現できるだろう。これと二クラウスの式をと組み合せると、どうなるのだろうか
アルゴリズム＋データ構造＝プログラム --- (1) データ構造＝プログラム --- (2) アルゴリズム = 0 --- (3) = (1)ー(2)を計算
このようにアルゴリズムは 0 となり、これは Lisp では NIL であり、虚無である。一般には無用の長物である。
(defun O_O () '1+1=?) ; (O_O) (defun ^_^ () '2!) ; (^_^) (defun @-@ () '10!) ; (@-@) (defun ^O^ () 'full!) ; (^O^) ISLisp>(O_O) 1+1=? ISLisp>(^_^) 2! ISLisp>(@-@) 10! ISLisp>(^O^) FULL!
(解説) (@-@)君が答えたのはもちろん2進数です。(^O^)は許容量を超えたのでしょう。
なお Lisp では名前に ^ や -, @, !などの記号も自由に使えます。
EV-Lisp 対 EVQ-Lisp
(car '(1 2 3)) v.s. car(1 2 3)
InterLisp v.s. MacLisp
戦国時代の両雄の戦い。
日本の Common Lisp 委員会の思い出など。
ページ数に余裕があれば、井田昌之を中心として活動していた電子協（電子情報技術産業協会の合併前の業界団体の一つ）
の Common Lisp 委員会の思い出を語ります。
"generic function"の訳語がどのようにして決まったのかなどのこぼれ話が中心になるかも知れません。
Emacs, AutoCAD, Interleaf, GAT など
人工知能(AI)エンジン、エキスパートシステム、数式処理（REDUCE, Maxima）、他
ロボット：iRobot社のルンバ、レゴ マインドストーム(XS)
各種
本文にも紹介しましたが、
ISLisp はhttp://www.islisp.org/jp/download-jp.htmlから
ダウンロードできます。
ミラーサイトはhttp://www.islisp.com/jp/download-jp.htmlにあります。
Common Lisp 版、高階関数の例、末尾再帰の例などを追加したサンプルプログラム
(defun fib (n) (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2))) ))
↓ if 文の then 節の 1 を n に修正
(defun fib (n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2))) ))
(fib 0) の値を 1 から 0 に修正しました。
本文の読者の皆様、ご迷惑をお掛けしまして、すみませんでした。
マクロ定義のサンプルプログラムとして、ISLisp の Common Lisp 互換パッケージをマクロ定義したもの
但し、1-、1+、inc、dec、second、third、pop、push、dotimes、dolist、print、prin1、terpri、read-from-string だけです。
また一部の関数は Common Lisp のサブセットの仕様になっています。
関数 (load ファイル名)で Lisp プログラムファイルをロードできます。
"samples.txt" をロードするときは、(load "samples.txt")を実行します。
なお Lisp ファイルの属性名は、一般的には "lsp" です。"txt" としているのはウェブで見やすくするためです。
またマクロ定義のサンプル(Common Lisp 互換パッケージ)は、(load "cl.txt")でロードできます。
サンプルプログラムの実行例は以下のようになります。
ISLisp>(fact 50) → 30414093201713378043612608166064768844377641568960512000000000000 ISLisp>(fib 11) → 89 ISLisp>(append2 '(1 2 3) '(4 5 6)) → (1 2 3 4 5 6) ISLisp>(mapcar1 (lambda (x) (* x 2)) '(1 2 3)) → (2 4 6) ISLisp>(qsort #'< '(5 4 3 2 1)) → (1 2 3 4 5) ISLisp>(hanoi 5) → 31回の移動 ISLisp>(nqueen 9) → 352個の解
factの値から分かりますように、Lisp では一般的に bignum (無限長整数)をサポートしています。
ちなみに Windows 版では (fact 153) まで計算できます。(fact が使うスタックに依存します。)
「やさしい Lisp の作り方 by Java and by C#」の記事が ここにありますので、参考にしてください。
---------------------------------------------- 問1. mapcon は真リストがお好き？ (mapcon (lambda (x) x) '(1 2 3 . 4)) を評価すると、その値はどれか？ 以下から選びなさい。 [a] (1 2 3 2 3 3) [b] (1 2 3 2 3 3 . 4) [c] (1 2 3 4 2 3 4 3 4) [d] (1 2 3 4 2 3 4 3 . 4) ----------------------------------------------
正解は[b]。
真リストでない mapcon の振る舞いを問う問題である。
mapcon が nconc で連結されていることに「mapcon という名前から気づけば」nconc のドット対結合の問題と等価になる。
つまり、(nconc '(1 . 2) '(3 . 4))→(1 3 . 4)と同じ問題である。
---------------------------------------------- 問2. 怪談 nconc の怨念 (nconc '(1 . 2) '(1 . 2))を評価すると、(1 1 . 2) になり、その長さ(length (nconc '(1 . 2) '(1 . 2))) は、2 になる。 それでは (let ((x '(1 2 . 3))) (length (nconc x x)) ) を評価すると、その値はどれか？ 以下から選びなさい。 [a] 3 [b] 4 [c] 5 [d] Error ----------------------------------------------
正解は[d]。
この問題は真リストでないリストに対する nconc と length の振る舞いを
問う問題を偽装しているが、実は nconc の破壊的操作を問う問題である。
問1が偽装するための前振り問題であった。
nconc によって、x の末尾は自分自身の先頭に繋がり、その結果、循環リストになってしまう。
Lisp Skill Examsがあります。
いじわるにはしていません。Common Lisp と ISLisp の知識で解ける問題になっています。
オリジナルの Android アプリが英語版のみリリースしている関係で、英語版になっています。
著者に寄せられた質問またはコメントに対して、ここに回答させていただきます。
もちろん、具体的な話を直接書かず、抽象化させていただきますので、ご安心ください。
また、すべての質問にお答えできないかも知れませんので、ご容赦ください。
関数型プログラミングの原理であるλ計算は、チューリング完全ですから、
能力は手続き型言語と同等です。つまり原理的には、どんなプログラムでも関数型プログラミングで記述できます。
しかし実際問題はやはり、状態を積極的に使った方がいいような問題では、状態マシン的な作りをしたプログラムの方がいいと思います。
副作用 side effect という言葉からは悪いイメージがありますが、便利な仕掛けなのも確かです。
しかし、わざわざ副作用を使わずに再帰でプログラミングできるときは使わないようにした方がいいでしょう。
副作用を用いると、それがバグの温床になることも多々あり、そのデバッグも大変になりますから。
Lisp のシンボルにどんな型の値でも「実行中に（動的に）」格納できます。
例えば、整数の 1 でも、リストの(1 2 3)でも、関数の #'car でも代入できます。
これを「動的型付け」と呼んでいます。
Java などではコンパイル時に型宣言をする静的型付けが基本ですが、呪文を唱えると動的型付けもほんの一部できるようになりました。
Lisp では高速化のために、型宣言をすることもできますが、基本的に動的型付けです。
この動的型付けの実装を考えてみます。
すべてを文字列型にして、呼び出す関数に応じて型変換するという実装もありますが、これでは遅いですので、真面目な実装を考えます。
動的型付けを実装するためには「型情報」をどこかに持たせる必要があります。
この型情報をデータと別に持たせると、例えば、構造体にして別に待たせると、使用するメモリが大きくなり、処理する時間も掛かり、遅くなります。
しかし、この実装方法は簡単ですので、小さな Lisp 処理系ではしばしば採用されています。
もっと真面目な実装方法では、例えば、32ビットマシンであれば、32ビットのどこかに数ビットを使用して、型情報を格納する方法があります。
この型情報を「タグ」と呼んでいます。実装の種類として、タグを固定長にするのか、可変長にするのか、タグを上位に置くのか、下位に置くのかなどがあります。
また別の実装方法としては、アドレスによって、型を区別する方法などもあります。
この実装によって、Lisp の実行速度が変わるだけでなく、GC のアルゴリズムにも影響を与えます。
すべてのプログラミングは絶対的に難しいとも、逆にすべてのプログラミングは絶対的に簡単であるとも、
また関数型プログラミングだけ、他のプログラミングと比較して、相対的に難しいとも言えるでしょう。
これは(1)「関数型プログラミングは難しいのか？いや、そんなことはない。簡単だ（反語）」という意味か、
(2)「関数型プログラミングは難しいのか？もちろん、難しい。そんなことは当たり前だ（反語）」という意味か、
(3)「関数型プログラミングは、他の例えば、手続き型（命令型）プログラミングやオブジェクト指向プログラミング、
論理型プログラミングなどと比較して、難しいのか？（裸の王様の素朴な質問）」の意味で捉えるかによって、
解釈は違ってきます。
また各プログラミングパラダイムで、どれが一番難しいか、または逆にどれが一番簡単かを議論しても、あまり意味がないでしょう。
ここでは「なぜ関数型プログラミングは難しいのか？またはそう思われているのか？」をテーマにしています。
本文に関数型プログラミングのメリットは箇条書きにしていますが、二つに絞れば、一つ目は(1)プログラムが巨大化している中、
プログラムの信頼性を向上させることです。
プログラムが大規模化していく流れの中で、プログラミングの生産性向上が求められ、例えば、オブジェクト指向プログラミングが使われるようになりました。
しかし暗黙的コード（例.スーパークラスへのアクセスやメソッド適用順序など）のため、バグが埋没されやすく、デバッグするときは逆に生産性を落とす結果になりました。
一方、関数型プログラミングは副作用をあまり使わないため、それによるバグが少なくなります。
さらに暗黙的コードがないシンプルな計算モデルであるため、バグの埋没やデバッグがしにくいということがありません。
生産性よりも信頼性です！・・・たぶん。
2番目の関数型プログラミングのメリットは(2)並行処理に向いているということです。
これは他の並行モデル、例えば、アクターモデルと比較してみると、「副作用」の存在をどう扱うかが違っています。
並行プログラムの（生産性でなく）信頼性という面で見て、副作用は邪魔な存在です。
λ計算を元に動作する並行モデルの方がアクターなどの他のモデルよりも、シンプルで信頼性の高いモデルです。・・・と思っていますが、どうでしょうか？（弱気？）
今は昔、AI が新しいものとして流行っていたとき、「なぜ AI マシンは Lisp なんですか？ Lisp は何がいいんですか？」
という質問を若い人から、えらい人まで、色々と質問されていました。
そこで学んだ教訓は、真面目に難しいことを答えるよりも、一言で答えた方が良かった経験が有ります(文中の Lisp を Prolog に変えても同じです)。
なぜ、Lisp がいいかって？そりゃ、決まっているだろ。「かっこ」いいからさ。--- すみません、オチませんでした。
本文でも書いたものより、30％増しで過激に言い切ると、
(i) 再帰プログラミングをやったことがない
(ii) そもそも lambda って発音できないし。ってλは何語？大文字のΛは↑に似ているし
(iii) グローバル変数は好きだし、使いまくってるし（Java であればフィールド変数の使いまくりだし）
(iv) 代入文は3度の飯よりも好きだし、3行に1個は使ってるし
(v) 繰り返し文はもちろん大好き、for 文が特に大好き
(vi) 関数を引数にするって何？関数を返すって、そんなキモイものいらないし
(vii) 兎に角、普段とプログラミングの方法が違うんだよ
とか、思っているのかも知れません。だから、関数型プログラミングは「食わず嫌い」で難しいと思っているのでしょう。
このような俗世のプログラミングから解脱できず、キヨクウツクシイ関数型プログラミングの世界は自分には難しいと思っているのでしょう。（嘘です、冗談ですってば）
でも実際は難しくありませんので、安心してください。修行する必要も解脱する必要もありません。在家のままでいいのです。
モナドなど問題などありません。ラムダも楽です。再帰など最近なら簡単にできます。
しかし、重要なアドバイスがたった1個だけあります。
まずは Lisp から始めてください。されば救われます。
質問をお聞きしますと、PerlやPython、Curl などの軽量級言語(Lightwight Language, LL)と関数型プログラミングをごっちゃにされているようです。
関数型言語と LL は重なる部分がありますが、関数型プログラミングは（LL側から批判的に使われる）重量級言語でも、可能です。
つまり、LL と関数型プログラミングは直交する関係です。このため、「LL が大規模開発に向いていない」とする批判は、今回の件では正しいかも知れませんが、
関数型プログラミングとは直接関係ありません。
一方、大規模開発におけるオブジェクト指向の優位性を持って、関数型プログラミングが大規模向きでないとする批判もあります。
確かにクラスベースのオブジェクト指向では、大規模開発に対する一つの解決として、「クラスによる分割」「カプセル」「差分プログラミング」などを示しています。これは関数型にはないものです。認めるしかないでしょう。
しかし、同様に関数型プログラミングは、規模と品質の関係において、解決する方法を提供しているのも確かです。
関数型プログラミングは規模生産性ではなく、規模信頼性において、より力を発揮するでしょう。
(*) ページ数は編集部からの要請でなく、著者が良心の呵責？！に耐えかねて、自主規制した結果です。
逆に当初予定よりも大増ページしていただき、感謝しております。それでも書き切れなかったのがここです。
visitors from 2015/7/26
visitors on today
Lisp の調べ Android の調べ 将棋の調べ 鉄道の調べ ビールコレクション
Copyright © 2015 GOMI Hiroshi All Rights Reserved