Lispに関するホフスタッターの論評（1983年）

 (gist.github.com/jackrusher)
1 ポイント 投稿者 GN⁺ 2024-10-18 | 1件のコメント | WhatsAppで共有
  • Douglas Hofstadterによる1983年の文章は、AI研究で広く使われていた Lisp を、小さな数学的カーネルの上に築かれた優雅で柔軟な言語として紹介している
  • Lispの対話性は read-eval-print loop に表れており、ユーザーが式を入力すると、インタプリタがそれを読み取り、評価し、出力したあと、次の入力を待つ
  • Lispオブジェクトは アトム（atom） と リスト（list） を中心に構成され、nilは空リストでありながらアトムでもあるという例外的な位置を占める
  • quote, eval, car, cdr, cons, setq, set, lambda, def, cond は、コードとデータを同じリスト構造として扱えるようにし、新しい関数を段階的に作れるようにする
  • 関数合成、条件式、副作用とapplicativeスタイル、再帰的思考が例を通じてつながり、最後の power 関数と「porpuquine」の比喩がLisp的な再帰を示唆している

AI研究とLispの位置づけ

  • 1983年時点のAIは、柔軟性、常識、洞察、創造性、自己認識、ユーモアのような振る舞いをコンピュータに実装しようとする研究分野だった
  • 米国にはAIに専門的に関わる人が約2,000人おり、海外にも同程度の規模の研究者がいた
  • AI研究者たちはAIへ至る最良の道筋をめぐって大きく意見が分かれていたが、プログラミング言語の選択では Lisp をほぼ共通して使っていた
  • Lispという名前は「list processing」に由来するが、完全な頭字語ではない
  • Lispの魅力は、「crisp」で「elegant」な言語である点にある
    • 多くの言語が恣意的な機能を多数抱える一方で、LispやAlgolのような一部の言語は、数学の一分野のように自然なカーネルを中心に構成されている
    • Lispのカーネルは「crystalline purity」を備えており、この純粋さは美的感覚だけでなく柔軟性にも寄与している

数理論理学からリスト処理言語へ

  • Lispの深いルーツは 数理論理学 にある
    • Thoralf Skolem、Kurt Godel、Alonzo Churchが1920〜1930年代の論理学に残したアイデアが、のちにLispへ取り込まれた
  • 本格的なコンピュータプログラミングは1940年代に始まり、Lispのような高水準言語は1950年代に登場した
  • 最初のリスト処理言語はLispではなく IPL（Information Processing Language） だった
    • IPLは1950年代半ばにHerbert Simon、Allen Newell、J. C. Shawが開発した
  • John McCarthyは1956〜1958年に、既存のアイデアをもとにLispという代数的なリスト処理言語を作った
    • LispはMIT Artificial Intelligence Project周辺の若い研究者たちに急速に広まった
    • IBM 704に実装され、ほかのAIグループへと広がった
    • 複数の方言が生まれたが、優雅な中心カーネルは共有されていた

対話的なLispとREPL

  • Lispは、ほかの多くの高水準言語とは異なり、対話型言語として提示されている
  • ユーザーは端末でLispを起動したあと、プロンプトを見て式を入力する
    • 例: (plus 2 2) と入力すると 4 が出力され、新しいプロンプトが現れる
  • Lispインタプリタの中核的な動作は read-eval-print loop である
    • 式を読み取る
    • 式を評価する
    • 適切な値を出力する
    • 次の式を読む準備ができたことを知らせる
  • この構造により、ユーザーは「願い」を一つずつ入力し、すぐに結果を確認できる
  • 多くの非対話型言語では、先にプログラム全体を書いてから実行しなければならないため、複数の段階が完全にかみ合う必要があり、エラー修正も間接的でコストが高い
  • Lispは一度に一つずつ式を実行する方式により、段階的な開発とデバッグを可能にする

Polish notationと括弧

  • Lispの算術式は、演算子が被演算子の前に来る Polish notation を使う
    • 例: (times (plus 6 3) (difference 6 3)) は27に評価される
  • この記法は、ポーランドの論理学者Jan Lukasiewiczがコンピュータ以前に作った記法である
  • Lispの式には括弧が多く登場する
    • 長い式が複数の閉じ括弧で終わることも珍しくない
    • 最初は負担に感じるが、慣れると論理構造が直感的に見える
  • 例は、インデントによって構造を示す pretty printing 形式で提示されている

アトム、リスト、nil

  • Lispの核心は操作可能な構造であり、すべてのプログラムは構造を作り、修正し、破壊する形で動作する
  • 構造には2種類ある
    • アトム（atom）: それ以上分割できない基本オブジェクト
    • リスト（list）: 複数の要素が特定の順序で集まった構造
  • すべてのLispオブジェクトはアトムかリストであり、唯一の例外が nil である
    • nilはアトムであると同時にリストでもある
    • nilは空リストを表す
    • () と nil は同じ意味だが、nilのほうがより頻繁に使われる
  • リストの要素はアトムであることも、リストであることもある
    • 例: (zonk blee strill (croak flonk)) は4つの要素を持つリストで、最後の要素はさらに2要素のリストである
  • Lispの文そのものもリストである
    • (plus 2 2) もリストである
    • Lispインタプリタはリストとアトムを操作して新しい「命令」を作り、評価できる

値、quote、eval

  • アトムは値を持つことができる
    • 数値アトムは自分自身を恒久的な値として持つ
    • nilの値はnilである
    • tも自分自身を恒久的な値として持つ特別なアトムである
  • setq はアトムに値を割り当てる
    • (setq pie 4) は pie の値を4にする
    • (setq pie (plus 2 2)) も pie の値を4にする
  • アトムの値は数値だけでなく、任意のLispオブジェクトであり得る
    • アトムでもよく、リストでもよい
  • quote は評価を止め、リストやアトムをそのままデータとして扱わせる
    • (setq pie (plus 2 2)) は内側の式を評価して pie に4を保存する
    • (setq pi '(plus 2 2)) はリスト (plus 2 2) そのものを pi に保存する
  • eval は値として保存された式を再び評価する
    • pi の値が (plus 2 2) なら、(eval pi) は4を返す
    • インタプリタは通常1段階だけ評価するが、eval を使えば追加の評価を要求できる

car、cdr、cons

  • nilでないすべてのリストは少なくとも1つの要素を持ち、最初の要素を car と呼ぶ
    • (eval pi) のcarは eval
    • (plus 2 2) のcarは plus
  • carが必ずしも関数名である必要はない
    • ((1)(2 2) (3 3 3)) のcarは (1) である
  • carを取り除いて残ったリストが cdr である
    • (a b c d) のcdrは (b c d)
    • 続いて (c d), (d), nilへと縮んでいく
  • nilにはcarもcdrもなく、carやcdrを取ろうとするとエラーになるべきである
  • cons は既存のリストの前に新しいcarを付けて、新しいリストを作る
    • x が (cake cookie) のとき、(cons 'pie x) は (pie cake cookie) を作る
    • このとき既存の x は変更されない
  • quoteの有無によって結果は変わる
    • pie の値が4なら、(cons pie x) は (4 cake cookie) を返す
    • (cons 'pie x) はアトム名 pie そのものを先頭に付ける

setqとsetの違い

  • Lispインタプリタが常に引数を評価するわけではなく、setq が代表的な例外である
  • setq の第1引数は評価されず、そのまま変数名として扱われる
    • setq のqはquoteを意味し、第1引数が引用されたかのように処理される
  • set は setq に似ているが、第1引数も評価する
    • xの値がkのとき、(set x 7) はxを変えず、kの値を7に変える
  • 例として次の順序が示されている
    • (setq a 'b)
    • (setq b 'c)
    • (setq c 'a)
    • (set a c)
    • (set c b)
  • この実行後、a、b、cの値はいずれも a になる
  • set はあまり使われず、このような混乱も頻繁には起こらない

関数定義とlambda

  • プログラミングの大きな力は、既存の演算から新しい複合演算を定義し、それを繰り返してより複雑な演算レパートリーを築ける点にある
  • Lispでは、すでに知られている関数を使って新しい関数を定義する
  • rac はリストの最後の要素を返す関数の例である
    • 最後の要素を得るには、リストを反転してcarを取ればよい
    • 定義: (def rac (lambda (lyst) (car (reverse lyst))))
  • lambda の後の (lyst) は関数のパラメータ、つまりダミー変数を表す
  • def で定義したあとは、rac は car のように使える関数になる
    • (rac '(your brains)) は brains を返す
  • readers-digest-condensed-version 関数は、長いリストから最初の要素と最後の要素だけを含む短いリストを作る
    • James Joyceの Finnegans Wake 全体を単語リストとして扱うと、(riverrun the) が得られる例が出てくる
  • rejoyce という逆演算は、2語で始まりと終わりが定まった小説を生成する想像上の関数であり、作成は読者の練習として残されている

値の返却、副作用、applicativeスタイル

  • 一部の人々は、Lispと関連言語において2つの目標が望ましく、かつ可能だと考えている
    • すべての文が値を返す
    • 文の効果は戻り値を通じてのみ発生する
  • 本文で扱われるLisp方言は1つ目の条件を満たすが、2つ目の条件まで必ず満たすわけではない
  • (reverse x) はx自体を変えず、xと同じだが順序が反転した新しいリストを作って返す
    • (plus 2 2) が2の値を変えないのと同じ方式である
  • cons も既存のリストを変更せず、新しいリストを返す
  • 一方、setq は変数束縛を変える 副作用 を残す命令の例である
    • 副作用には、変数束縛の変更のほかに入出力も含まれ得る
  • applicativeプログラミングを支持する人々は、副作用なしに関数が値を計算して渡す方式だけを好む
  • このスタイルで許される束縛は、関数呼び出し中に一時的に生じる lambda binding である
    • 関数の計算が終わると、ダミー変数の束縛は消える
  • 筆者はapplicativeスタイルを優雅だと見ているが、大規模なAIスタイルのプログラムを作る際には実用的ではないと考えている
  • 厳格なapplicativeプログラミングでは、def も恒久的な関数定義をメモリに保存するため、許されない極端な例になる

条件式condと判断

  • Lispがより興味深いことを行うには、途中の過程で起こることに応じて判断できなければならず、その際に 条件式 が必要になる
  • 例: (cond ((eq x 1) 'land) ((eq x 2) 'sea))
    • xが1なら land
    • xが2なら sea
    • それ以外ならnilを返す
  • eq は2つの引数の値が等しければ t、異なれば nil を返すLisp関数である
  • cond 文は cond という関数名で始まり、複数の節を持つ
    • 各節は条件と結果からなる2要素リストである
    • 条件を順に検査し、nilでない値を返す最初の条件を見つけると、その結果を評価して cond 全体の値として返す
    • 以降の節は検査しない
  • 最後に t を条件とするcatch-all節を入れると、nilの代わりにデフォルトの結果を返せる
    • 例として、land、seaの条件がどちらも失敗すると air を返す cond が示されている

累乗と再帰的構造

  • 文章の末尾には、パターンが明確な関数定義が登場する
    • square は k * k
    • cube は k * square(k)
    • 4th-power は k * cube(k)
    • 同じ方式で続いていく
  • このパターン全体を一度に包含する2引数関数 power を定義できるかが問いとして提示される
    • (power 9 3) は729
    • (power 7 4) は2,401を返すべきである
  • 必要な道具は本文ですべて提示されており、読者の機転が求められる
  • 最後のGlazunkian porpuquineの話は、再帰的構造を寓話のように扱う
    • porpuquineのトゲは、より小さなporpuquineである
    • Outer Glazunkiaでは常に9本、Inner Glazunkiaでは常に7本のトゲがある
    • 0インチのporpuquineにはトゲがなく、無限後退を止める
  • この動物の「buying power」または「power」は、中に含まれる小さな0インチporpuquineの鼻の数と結びついており、先に提示された power 問題へとつながる比喩で締めくくられる

原文再掲の文脈

  • Gistの冒頭部分では、この記事が1980年代半ばのScientific Americanのバックナンバーで出会ったDouglas HofstadterによるLisp紹介文だと述べている
  • 例は、Emacsでいくつかのエイリアスを設定すれば今でも実行できる
    • plus → +
    • quotient → /
    • times → *
    • difference → -
  • 末尾では、Hofstadter独特のLisp案内を楽しんだなら、彼の著書 Metamagical Themas で似た文章をさらに読めると案内している

関連記事

1件のコメント

 
GN⁺ 2024-10-18
Hacker News のコメント

  • 例の "oval" と "snot" という関数名に戸惑ったが、数秒後、それぞれ "eval" と "snoc" の誤植だと気づいた
    元のコードは (cond ((eq (eval pi) pie) (eval (snoc pie pi))) (t (eval (snoc (rac pi) pi)))) のように読むべき
    https://www.jstor.org/stable/24968822 で Scientific American の原文を入手して確認したところ、実際に oval/snot は eval/snoc の誤植だった

    • 訂正の訂正: "oval" と "snot" は "eval" と "snoc" の誤植で間違いない
      そして snoc は cons を逆にしたもの、rac は car を逆にしたもののようだ
    • OCR エラーの可能性もありそう

  • この記事は、Lisp の人気が弱かった核心的な原因が Lisp を説明する方法にあったことを改めて示している
    こうした Lisp の記事は、子どもの頃の私に、実際に使えることを何ひとつ教えてくれなかったし、アセンブリ/C/Pascal などに比べて、ある作業 X がどれほど簡単になるのかも示してくれなかった
    今の私なら、「アセンブリで7か月かかったスペルチェッカー？ バンク切り替えメモリを使うマイクロコンピュータなら、Lisp ではほとんど取るに足らない仕事だし、ガベージコレクションもひどい CPU 上で決定的に動かせる」と見せただろう
    数多くの Lisp の記事や教材が、リスト、再帰、AI の話ばかり繰り返し、有用なことをする方法を示さなかったため、ピンセットと米粒と糊でプログラミングしていたかのような時間が惜しく感じられる

    • Common Lisp: A Gentle Introduction to Symbolic Computation はこの文脈で役に立つかもしれない: https://www.cs.cmu.edu/~dst/LispBook/
    • Practical Common Lisp もある: https://gigamonkeys.com/book/
    • Hofstadter の続編記事には、もっと興味深い例があった
      子どもの頃に初めて見た Byte 誌には、記号微分と代数的単純化を Lisp で書いたコードがあり、追うのは難しかったが、何か魅力を感じた
      Basic でならもっと簡単だったはずもなく、後から見るとそのコードはそれほど優れたものではなかったが、80年代後半の PC 上の XLisp と SICP に出会ってから、ようやく Lisp に本格的にはまった

  • Hofstadter の文章が本当に好きだ。Lisp を発見したときに感じた感情をよく捉えている
    80年代にプログラミングを学んでいた子どもで、高校と大学初期には BASIC、Fortran、Pascal、COBOL をすでに少し触っていたが、違いはあっても根本的には共通点があった
    ところが UC Berkeley の最初のコンピュータサイエンスの授業は、Lisp 方言である Scheme で行われ、完全に衝撃だった
    Hofstadter が言うように数学に最も近い感覚で、数学理論の授業を多く思い出させ、初めて見つけた美しい言語だった
    「Lisp と Algol は、数学の一分野のように自然な核心を中心に作られている。Lisp の核心には、美的感覚に訴えるだけでなく、ほとんどの言語よりはるかに柔軟にする結晶のような純粋性がある」という引用が特に良かった

    • Haskell を使ったことがあるのか気になる。私には、手続きではなく定義でできているので、はるかに数学に近く感じられ、見た目も数学のように見える
    • 元記事から少し外れる危険はあるが、これを「数学」と呼ぶと、かえって曖昧になる可能性があると思う
      代数的位相幾何学者になりたかった立場から見ても、Scheme は動的型付けとガベージコレクションを使う言語全般に広がるプログラミングスタイルを 優雅かつ最小限に表現したものに近い
      完成されているように見え、Scheme で問題解決の方法を考えた後、ほかの動的型付け言語に移しても優雅な解法に到達できるという意味で、「理論」のように感じられる
      Scheme は当時の伝統的な Lisp に比べて、レキシカルスコープ、関数と変数の単一名前空間といった点で単純化され、整理された言語だった

  • 1983年といえば、この分野が始まってから20年ほど経った時点だが、「柔軟性、常識、洞察、創造性、自己認識、ユーモア」を持つようにコンピュータをプログラムする AI について語っている
    このリストが、LLM が本当に苦手なもののリストのように読めて、かなり面白い
    それでも少なくともその方向に ゼロではない進歩は生まれたわけだ

    • 私が出会う普通の人たちと比べれば、LLM は 常識、洞察、創造性、自己認識、ユーモアを平均的な人間くらいには示しているように思う
      もしかするとそれ以上に示していると感じるが、そう言うと自分でも少し変に聞こえる
    • Hofstadter の研究グループには、こうした問題に取り組もうとしてきた長い歴史がある
      多くはまだ成果につながっていないとしても、興味深く読める

  • この記事と一緒に言及されている2本の関連稿は、Hofstadter の本 Metamagical Themas の第17〜19章に収録されており、Scientific American の同じ連載に載ったほかの記事も一緒に入っている
    [0]: https://www.goodreads.com/book/show/181239.Metamagical_Thema...
    本のタイトルは、Martin Gardner が Scientific American に書いていた「Mathematical Games」のアナグラムから来た連載タイトルで、Hofstadter がその連載を引き継いだ

    • この本が本当に好きだ。Hofstadter の古典である Gödel, Escher, Bach が好きな人には強くおすすめする
    • この本は読むにも眺めるにも本当に美しく、興味深い挿絵が多い

  • 記事では、nilにcarやcdrを適用するとゼロ除算のようにエラーになるべきだと述べているが、現代の Lisp ではもはやそうでない場合が多い
    John McCarthy が定義した当初の Lisp では、CARとCDRはNILに対して定義されていなかった: <https://dl.acm.org/doi/pdf/10.1145/367177.367199>
    しかし Common Lisp と Emacs Lisp では、(car nil)と(cdr nil)をnilと定義している: <https://www.lispworks.com/documentation/HyperSpec/Body/f_car...>, <https://www.gnu.org/software/emacs/manual/html_node/elisp/Li...>

    • Maclisp ではどうなのか気になったので、Lars Brinkhoff の公開 ITS に telnet で接続して確認してみた
      LISP 2156で(status lispversion)は/2156を返し、(car nil)と(cdr nil)はいずれも NIL を返した
    • 数学的に設計された言語の誕生に、carやcdrのような非常に具体的な実装上の細部が中核として入り込んでいたのは驚きだ
      “List Processor”の最も基本的で有名な演算子はリストではなく、Lisp がデータ構造を作るときに使う特定の機械表現要素である cons に対して動作するよう作られていた
      cons が常にリストとして解釈されるわけでもなく、リスト再帰関数の基底ケースである非常に重要なリストは cons では表現されてすらいない
      60年が過ぎた今でも Lisp プログラムの大半は cons 演算で満ちており、より正確な名前は“Cons Processor”だったのかもしれない
      言語と実装が密接に噛み合う必要があった時代に Lisp が生まれたことを思い起こさせ、だからこそコンピュータ言語を数理論理に基づかせたという成果がいっそう驚くべきものに感じられる
    • Scheme はそうではない。nilのCARやCDRを取るとエラーになる
    • 残念ながら Scheme ではnilのcar/cdrがエラーなので、私のような初心者にはコードがかなり人間工学的でないように感じられる
      それでも Common Lisp より Guile Scheme のほうが好きなので惜しい
    • nilに何かを適用してもエラーにならず、再びnilを返す言語設計上の選択を指す用語があるのか気になる
      SQL も思い浮かぶし、個人的には良くない選択だと思うので、ほかに言葉がないなら“bleeding nils/NULLs”と呼びたい
      特にnilがブール比較でfalseと同じでないなら、なお悪い
      Ruby と Elixir ではnilがfalseのように扱われ、Elixir は純粋なブール値だけを受け取るandと、nilをfalseとして扱う&&を分けて提供している
      こうした設計は最初はコードをすっきりさせられるが、実際にはエラーである不適切に処理されたnilが、いくつもの呼び出しスタックの先にあるまったく別の箇所で表面化し、デバッグをはるかに難しくすることがある

  • この記事の Lisp 情報はすでに知っていたが、それでも楽しく読めた。Hofstadter は言葉遣いが実に魅力的だ
    特にreaders-digest-condensed-versionの逆演算であるrejoyceを作り、(rejoyce 'Stately 'Yes)を実行すると Lisp の妖精が James Joyce が書いたかもしれない Ulysses 全編 を最初から生成する、という冗談が面白かった
    少し時間はかかったが、結局その地点には到達したわけで、2024年の AI が 1983年に彼が想像したものと完全に同じではないとしても、短いシードからテキストを再生成することは、今日の AI にはかなりよく合ったタスクだ

  • Lisp は、Hofstadter が扱った奇妙なループという概念を表現できる主要な言語として、今も残っていると思う
    Lisp だけがホモイコニックな言語というわけではないが、人々が実際に使える言語の中では、eval がパースすべき文字列を受け取らない最大級のものに属する
    Lisp を関数型プログラミング全体と同一視されるのは嫌いだ
    関数型プログラミングが嫌いなわけではないが、Lisp の記号的な性格のほうがはるかに興味深く、(go tag) セクションで駆動されるコードを作って GOTO 的なプログラミングも非常に簡単にできる点が、いつまでも面白い

    • 2000年代に一時的に主流で採用された、もうひとつのきちんとした関数型のホモイコニック言語として XSLT がある
      XSLT と XML を使って、反復的なコードを直接書く代わりに XSLT を生成する形のメタプログラミング機能がかなり広く使われていた
      ただし構文は Lisp の構文よりも大きな問題だった
      日常的に使いやすい構文でありながら、同時に抽象構文木としても扱いにくすぎない言語を作るのは簡単ではなく、Lisp は比較的成功した数少ない例である
    • 特に Scheme の継続ベースのプログラミングまで行くと、関数型と非関数型プログラミングの境界はほとんど意味がないほど曖昧になる
    • 2024年のプログラマーが Lisp から得られる、Python の functools ではあまりうまくできない深いレベルのホモイコニック／記号サポートが実際には何なのか気になる: https://docs.python.org/3/library/functools.html
      Lisp なしで記号的 AGI を作っているので、専門家の手がかりを聞きたい
      私が理解している Python 側の機能は、filter()、map()、reduce() のように別の関数をイテラブルオブジェクトに適用する関数、@singledispatch のように呼び出しをルーティングするラッパー、@cache や partial() のようにフロー制御や性能上の利便性を与える関数、wraps() のように任意に関数を包む機能といった程度だ
      これらは大半が、関数を特殊な方法で呼び出すための便利機能のように見え、「自己省察」を第一級の関心事のように扱う Lisp への称賛のレベルには届かないように思える
      上記の機能にないものとして、Lisp が実際に何を提供しているのか知りたい
    • 多くの人が Lisp に学界を通じてしか触れず、Lisp を教える研究者たちが実際に Lisp で何かを開発することには関心がないからでもある
      彼らは Lisp を概念伝達の手段として使い、その概念はたいてい関数型再帰を中心に回っている
      Scheme とその周辺文化も一役買っている
      Scheme は関数型言語だけではないが、以前の Lisp 系よりも純粋プログラミングを強調し、基本言語が反復構造の代わりに末尾再帰構造を提供し、実装に末尾呼び出し最適化を要求する

  • Common Lisp でも defalias をマクロとして定義すれば、Emacs の defalias のように使える: https://stackoverflow.com/questions/24252539/defining-aliase...

  • Metamagical Themas に載った Hofstadter の Lisp 記事が好きで、その連載最後の記事のコードを職場の勉強会向けに Clojure に合わせて移植・整理した
    [1] http://johnj.com/posts/oodles/

    • 現代の Lisp に移した翻訳版があるのかも気になる