【PAIP】3 Overview of Lisp

体を壊しては元も子もないので、調子をみながら。リハビリ。

さて、第三章の趣旨は、

"Chapter 3 provides an overview of the Lisp primitives. It can be skimmed on first reading and used as a reference whenever an unfamiliar function is mentioned in the text."

とのこと。なのでリラックスしていく。ただ、CL入門とANSI-CLの復習の意味もこめて写経はしっかりやる。

• 3.1 A Guide to Lisp Style
  
• lispでは同じ関数であっても多様な書きぶりが可能である。
  
• どれを選ぶべきかについて、6つの指針がある。それの説明。
  
• 指針が衝突した場合の判断について。
  
  
• 3.2 Special Forms
  
• andやorを条件分岐で多様するのはBad styleであると。するとPGのANSI-CLはBad style連発だったな。。。ひとそれぞれ？
  
• Norvigも拡張loop否定派っぽい。
  
• listをみるのに二つの視点あり。first and restとsequence。この本では後者をよく使う。なぜかというと、first and restでとらえると、listがconsでできているというlispの言語仕様にひっぱられすぎることがおおいから。最後の要素について何かしたいときとかは、sequenceととらえていた方が直接的である。
  
• progn利用規制を明示。厳しいな。。。
  
• 「As C.A.R. Hoare put it, "One thing the language designer should not do is to include untried ideas of his own"」これがMacro心構えだよと。なるほど。
  
  
• 3.3 Functions on Lists
  
• 3.4 Equality and Internal Representation
  
• 3.5 Functions on Sequence
  
• この3つ、新しい知見は特になし。
  
  
• 3.6 Functions for Maintaining Tables
  
• 属性リストはあまり使わない。hash tableを使うのが主流。理由は、
  
  
  
  • 属性リストは常にglobal。二つのプログラムを同時に利用したりすると衝突の回避がやっかい。
    
  • clrhashに対応する機能が無いなど、管理用の機能が整備されていない。
    
  
  
  
• 3.7 Functions on Trees
  
• 3.8 Functions on Numbers
  
• この2つ、新しい知見はなし。
  
  
• 3.9 Functions on Sets
  
• CLにおけるbit-vector。これは初めて見たかな。PCLで見ていたが、わすれている、という可能性もある。
  
  
• 3.10 Destructive Functions
  
• そうか、Lisp以外の言語では、副作用をもたらすものをfunctionではなくprocedureと呼んでいるのか。それはそれで合理的。
  
  
• 3.11 Overview of Data Types
  
• 3.12 Input/Output
  
• この2つ、新しい知見はなし。
  
  
• 3.13 Debugging Tools
  
• "..., but it also offers a third: (3) add annotations that are not part of the program but have the effect of automatically altering the running program." これが何を指しているのかが今ひとつわからない。
  
  
• 3.14 Antibugging Tools
  
• バグ警報のためにコーディング作業をあらかじめ費すのは、それなしでデバグ作業する羽目になるより安くつくよ。
  
• 複雑なデータ構造を扱うときは、一貫性チェッカをつくっとくべし。
  
• めんどくさいテストケースについては、何時でも実施できるよう手元においておくべし。(regression testing)
  
• それは複雑なもんじゃなくてもよくて、assertをdefunでまとめておくだけでも十分。
  
  
• 3.15 Evaluation
  
• ああ、そうなのか、funcall,applyとevalというのは「評価する」という意味では同種なのか。REPLな観点からevalを特別視していたけれども、プログラマの観点で、コードの中で評価対象を作成してそれを評価するための機構としては、これらは同列にとらえられるものなのだ。
  
• そして、コードの中の評価対象って何だっけ? というと、まあ「関数」と「引数」だ。なので、funcall,applyはそれらを引数にできる、と。
  
• そしてその引数たる「関数」をコード中で作れますよ、というのがlambdaでありclosureということだ。
  
• なので、昔のLispでは、コードの動的取り扱いにevalを多用していたが、今はfuncall,applyとlambdaを使う、と。
  
• 大したことではないが、視点がすっきり整理できた。
  
  
• 3.16 Closure
  
• free lexical variablesを補足するのがclosure、という説明だけ。
  
• とてもコンパクトに説明していてよいのだが、closureがわからない人が、これでわかるようになるのは無理だろう。
  
  
• 3.17 Special Variables
  
• うぉ。この節、コンパクトにlexical variablesとspecial variableの要点を説明している。
  
• これはこれですっきり。
  
• でも触れてないことも多いし、この説明だけでわからない人が理解するのは無理。
  
• わかっている人のためのものだろう。
  
• Norvigの説明を自分なりにアレンジしつつまとめる。
  
  
  
  • CLはデフォルトはlexical variables。
    
  • lexical variablesのスコープは、レキシカル。すなわちコードで範囲を抜けると、そのvariablesに名前でアクセスすることはできない。ここまでは他の言語と一緒。
    
  • ただし、CLのlexical variablesはclosureに捕捉され得るので、捕捉されている場合は、プログラムの実行がスコープを抜けた後も、存在することはできる。もちろんスコープは抜けているので名前ではアクセスはできない。しかし存在しているので、closureがそれを操作する機能をもっていれば、closureが無くなるまでそれは存在し操作できる。これがエクステント。closureが存在しない言語では、スコープとエクステントはlexical variablesにおいても同じとなる。ここが他の言語と違うところ。
    
    
  • special variablesのスコープはグローバルである。なので、プログラム中のどこからでも参照できる。ここまでは他の言語のglobal variablesと一緒。
    
  • ただし、CLのspecial variablesは、letなどによって局所的に動的にshadowingできる。なので、special variablesのスコープは、グローバルだがlocal (dynamic) shadowing付きであるといえる。ここが他の言語と違うところ。
    
  • そしてこのshadowingのextentはスコープと同じである。コードのゾーンを抜ければ、shadowingは無効になる。それゆえspecial variablesのextentは動的(dynamic)であるという。
    
  • まとめると
    

    
    lexical variables : scope = lexical, extent = indefinite (as closure)
    special variables : scope = global , extent = dynamic (as shadowing)
    

    
    
  
  
  
• 3.18 Multiple Values
  
• 複数の値を返したいときってあるよね。-> Listとかstructureで返せばいいよね。->でも、そうするとそれらの構造を定義したり、それらを関数の中で生成しなきゃいけないよね。-> I'm lisper. めんどくさいのはイヤ。-> 多値発祥。
  なるほど。。。
  
  
• 3.19 More about Parameters
  
• &optional, &keyなど自身のことをlambda-list keywordsと呼ぶよ。
  
• complement、便利だな。
  
  
• 3.20 The Rest of Lisp
  
• ま、基本は自分でやるべしだよ、この本はAIの本だし、という感じ。
  

うむ。とりえあず、最初の100ページはクリアした。
PART II Early AI PROGRAMS に進もう。

結局病院へ。。。

過労により病院へ。とりあえず点滴。
MOPセミナには行けず。
予約してたのに、いけなかった。数理システムさんに申し訳ない。
また、とても残念。

今日はMOPセミナ

今日は黒田さんのMOPセミナ。
業務繁忙で、ほぼ二徹状態。
とほほ。

【PAIP】2 A Simple Lisp Program

二章の趣旨は、

"Chapter 2 is a more extended example showing how the Lisp primitives can be put together to form a program. It should be studied carefully by the novice, and even the experienced programmer will want to look through it to get a feel for my programming style."

とのこと。私はnorviceなので、しっかりやらなければいけないし、Norvigが、これがおれ様のプログラミングスタイルだ、というなら興味深いのでしっかりやりたい。

• 2.1 A Grammar for a Subset of English
  
• シプサでもやったな、これ。文脈自由文法。
  
• あっさり。
  
  
• 2.2 A Straightforward Solution
  
• "a function with no arguments would always return the same thing" ごもっとも。関数は関数。
  
• "..., but they are still called functions in Lisp, because they return a value" なるほど。
  
• 関数による実装。できるといえばできる。
  
• しかし文法が複雑になると、文法を記述するためにLispをごちゃごちゃかかねばならん。それをなんとかしたい。
  
  
• 2.3 A Rule-Based Solution
  
• で、文法を記述する、ということと、その文法に従って文を生成するということを分解して考えるのはどうか、ということ。
  
• defparameterで定義したものを変更するのは人手であり、defvarで定義したものを変更するのはプログラムのrun-timeにおいてプログラムによって行われる。変更の頻度でいえば、defvarのほうが遥に高い。なるほど。
  
  
• 2.4 Two Paths to Follow
  
• 問題の解決をLisp codeとしてそのまま書き下すか、それとも、問題のできるだけ自然な表現をまず確立して、それのインタプリタを書く形で問題を解決するか。
  
• AIプログラミングでは後者が有効な場合が多い。
  
• Lispは後者が得意である。
  
• 問題自身の言葉で記述できる限り記述して、直接Lispで書く部分を最小化せよ。なるほど。
  
  
• 2.5 Changing the Grammar without Changing the Program
  
• インタプリタ方式だと簡単に文法を変えられるよ。
  
  
• 2.6 Using the Same Data for Several Programs
  
• インタプリタ方式だと、作成済みの文法を別のプログラムの入力としても使えるよ。
  

Lispはやっぱ、LISt Processor なんだ、という実感。こういう具体的な問題への適用をイメージした形でリストの取り扱いに習熟するのが大事に感じた。これは実はPGのANSI-CLでも感じた。

はじめ、ちょろちょろ。

【PAIP】1 Introduction to Lisp

一章の趣旨は、

"Chapter 1 gives a quick introduction by way of small examples that demonstrate the novel features of Lisp. It can be safely skipped or skimmed by the experienced programmer."

とのこと。私はan experienced programmerではないので、ここからやっていくことにする。

以下、メモ。

• この章が難しく感じるなら入門書をやってから来てね、という関門的な章らしい。いきなり玉砕するかも。
  
  
• はじめにObjectsをさくっと定義しているところがよい。このObjectsの捉え方は、手短だが、計算理論における正しい捉え方だ。そこでは、datumもoperationもObjectsである、と。
  
• LispシステムのことをLispと呼んでいる。これ、米国のLisperとやりとりすると結構でてくる表現。If your lisp has some trouble with gc ...とか。
  
• 実践CLのときにも書いたと思うけど、expressionを式と和訳上結びつけたのは日本の数学や計算機科学の最大の損失ではないか。expressionは和訳するなら「表現」でばっちりだと思うのだが。
  
  
• 1.1 Symbolic Computation
  
• もしかしてエディタxyzzyの名前のネタもとは、このP7なのか?
  
• quoteの説明は、readアルゴリズムには踏み込まず、evaluate回避という視点のみ。ANSI-CLと似た感じかな。
  
  
• 1.2 Variables
  
• symbolがobjectsの名前付けにつかえる、という書きぶりがうまい。
  
• 名前づけの対象になるObjectsは、variablesとfunctions。
  
• ここでのvariablesは、他の言語の変数よりも、数理論理学の変項のニュアンス。まあvariablesを変数という言葉と和訳上の対応を決めたのも、かなりセンス悪いと思いますが。もう「可変」でよかったのではないかと。
  
  
  
• 1.3 Special Form
  
• (setf x 3)の総体がa special form。setfは、special syntaxで、compilerに対する指示マーカー。という理解が現代的、とな。
  
• 用語の混乱の危険があるときは、(setf x 3)をa special form expression、setfをa special form operatorと呼ぼう、とな。
  
  
• 1.4 Lists
  
• あっさり。
  
  
• 1.5 Defining New Functions
  
• lambda listじゃなくてparameter listと呼ぶ。
  
• 関数の名前は、その関数の役割りを明示すべき。そのために、単に名前を明示するためだけであっても関数定義せよ。
  
  
• 1.6 Using Functions
  
• "a function must return a value, and it must not return any incorrect values." これが関数の設計観点であると。なるほど。
  
  
• 1.7 Higher-Order Functions
  
• lambdaのbetter nameはmake-functionだろう、と。
  
• λ発祥は、Churchのタイポグラフィの工夫だったのか。。。(^ -> Λ -> λ)
  
• (lambda (x) ...)と#'(lambda (x) ...)の違いはちょっとやる、と。
  
• CLのlambdaを考えるときは、鯛焼が頭に浮かぶ。これは竹内先生の呪いだ。。。
  
• run-timeに関数を生成できるのがlambda表現のメリットである(それはわかる)。そういう関数をclosureと呼ぶ(あり?そういうことだっけ?)。3.16で説明する(待ちます。。。)。
  
  
• 1.8 Other Data Types
  
• CLでは25種のObjectが定義されている。
  
• 文字列紹介。
  
  
• 1.9 Summary: The Lisp Evaluation Rule
  
• 評価機構の簡単な説明。環境については触れず。
  
• lispではreadとevaluationが別プロセスであることの説明。
  
  
• 1.10 What Makes Lisp Different?
  
• AIアプリケーションにとってLispが重要である7つの主因を掲示。
  
• そしてそれらをひとつひとつ分析する。
  
• 分析の内容が具体的でわかりやすい。
  

そういえば、昔、この一章を眺めたことがあった(それも忘れてた)。そのときは、言っていることはまあわかるが、それらが自分が確信をもって身につけているものとは到底思えなかった(lambdaのくだりとか)。なので、その先を読むのをやめた。

今回はさすがに準備してきたので、自分でも先に進んでよいと思える。
こつこつ。

【PAIP】Preface

うーん。Prefaceを読んだだけで、Norvigが如何に明晰な人なのかが良くわかる。

Prefaceは、プログラミングをいかに学ぶべきか、Lispがどういう点で優れているか、ということでいろいろ言われていることを簡明に整理している(PGのような煽りはなし)。またLispとAIプログラミングの関係、通常のプログラミングとAIプログラミングの関係、それらを簡単に整理した上で、本書がどのようなスタンスでそれらに臨んでいるかを記述している。

また、この本をどのように使うべきかという指針が述べられている。そのうちのひとつが、

"For the Professional Lisp Programmer: Read as much of the book as possible, and refer back to it often. ..."

とのこと。「プロのLispプログラマなら、この本をしゃぶりつくせ」ということですね。

こつこつ。。。

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp を覗いてみることにする

少々考えて、ついにPAIPを覗いてみることにした。PAIPはCL「勉強」のひとつの目標としていたので、感慨深い。

PAIPについて少し書いてみる。著者はPeter Norvig。現在はGoogleの技術をひっぱる一人だ。もともとAI方面であり、その著書のひとつがPAIPである。現在はPythonistaであるという。Rubyならわかるが、Pythonへ、というのがどういう考えなのかは私は理解できていない。PAIPはCLと古典的AIについて書かれた本というのが世の中の位置付けだが、特にそのCLの書きぶりがキレイでありCLをやらない人でも読んで得るもの多し、と言われている。

CLの書きぶりについては、キレイという評価とともに、筋が良いというか基本に忠実という評判だ。なので、職人的というか先進的というかなんというかのプログラミングスキルではないらしい。なので、上級者向け、というものではなく、本来敷居は低い本らしい。

敷居を高く感じさせるのは、CLのイントロは付いているけど、それは本格的には別のところでやっといてね、ということだろう。導入部に推奨書籍がいくつか挙げられている。なので、CLの基礎はまあ身についていることを前提としているということ。で、CLの基礎を身につけるって、すっごく簡単というほど簡単ではないということじゃないか。

後は、題材がAIプログラミングなので、そもそも扱っている問題がいろいろ考えさせる部分が多いということもあるかと思う。

PAIPを読み込めば、CL入門者からCL初級者に格上げしてもいいように思う。さらにその上で、Norvigのもうひとつの著書であるAIMAを読み込めばCL中級者と言えるのではないか。(AIMAはCLソースが公開されている)

私自身としては計算理論というか計算機科学の訓練がまだ弱いので(シプサも中断中)、時期尚早かもしれない。

しかし、ここで一度背伸びして、当面の目標の高さを確かめてみてもいいかな、と考えた。学習プロセスには、深く掘ってみるタイミングと、幅広く視野を広げて鳥瞰するというタイミングがあるように思う。それがいい形でスパイラルしていくのが効果があると思える。今は視野を広げるタイミングという判断だ。

というわけで、PAIPを覗いてみる。いつまでにどうこうという目標は立てない。なんだかよくわからなくなって、読んでいる意味がなくなったらいつでも撤退しようと思う。