ホモアイコニックな Python 言語

 (aljamal.substack.com)
2 ポイント 投稿者 GN⁺ 2024-05-13 | 2件のコメント | WhatsAppで共有
  • Lisp の ホモアイコニシティ は、コードとデータを同じ形で扱う性質であり、古典的な「Lisp in Lisp」を Python に移し替えると、このアイデアがより馴染みのある構文の中で現れる
  • もともとの Lisp は、コード表現である M-expression とデータ表現である S-expression を併せ持っており、「Lisp in Lisp」は M-expression で S-expression Lisp を実装している
  • Python 版では S-expression を Python リスト で表現し、M-expression は関数呼び出しと条件文へ移し替えることで、別個のパーサなしにインタプリタを構成する
  • 最初のインタプリタは atom, eq, car, cdr, cons, append のようなリストの基本原始演算の上に成り立ち、lambda をサポートするために assoc, pairlis, 環境リストが追加される
  • eval は式と環境を一緒に受け取り、変数バインディングを処理し、pairlis と assoc を通じて 動的スコープ 方式で引数と値を結び付ける

Lisp が示したコードとデータの統合

  • Lisp は 1960 年代初頭に John McCarthy が著した Lisp paper と Lisp 1.5 manual を通じて、数十年後にも有効な多くのアイデアを残した
  • その中核の一つが ホモアイコニシティ である
    • 一般的な言語では、コードはデータに作用する演算の列として理解される
    • Lisp はコードとデータを同じ形で扱い、演算子と被演算子の境界を曖昧にする
  • Alan Kay は Lisp 1.5 manual 13 ページ下部の「Lisp in Lisp」コードを “Maxwell's Equations of Software” と呼んだ
    • 数行のコードの中にプログラミング世界全体が宿っているという大きな気づきだった、という趣旨の引用が含まれている

「Lisp in Lisp」を Python に移し替える方法

  • 目標は、古典的な「Lisp in Lisp」コードを Python で書き直しつつ、元のコードの精神をできるだけ維持することにある
  • Lisp には 2 つの構文表現がある
    • M-expression: コード表現、meta の略
    • S-expression: データ表現、symbolic の略
    • 両者は意味的には等価である
  • 既存の「Lisp in Lisp」コードは M-expression で書かれ、S-expression Lisp を実装している
  • Python 実装では Lisp の S-expression を Python リスト で表現する
    • Lisp は “List Processing” の略であり、リストという単一のデータ構造を中心に動作する
    • Python リストは Lisp の S-expression をエミュレートするのに適した表現として使われる
  • M-expression は Python の関数呼び出しや条件文のようなコード構造へ翻訳される
    • この対応付けのおかげで、文字列操作や別個の パーサ 実装なしにインタプリタを作れる

リストの原始演算で作る最初のインタプリタ

  • Lisp 実装には、言語の外側から提供されるいくつかの 基本関数 が必要である
  • Python 実装で使われるリストの原始演算は次のとおり
    • atom(x): x がリストかどうかを確認
    • eq(x,y): x と y が等しいかを確認
    • car(x): リストの先頭要素
    • cdr(x): リストの残り
    • cons(x,y): 原子をリストに付け加える
    • append(x,y): 2 つのリストを連結する
  • いくつかの再帰的な原始演算を除けば、Groq 上の Llama3-70b を活用して、「Lisp in Lisp」コードの部分集合を実行するインタプリタを素早く作ることができた
  • 例では Python リストが S-expression のように動作する
  • 全コードは github gists で公開されている

lambda と再帰のための拡張

  • 最初の実装には重要な機能である lambda が欠けている
    • lambda は Lisp で匿名関数を定義し呼び出す主要な方法である
    • Lisp では lambda がなければ再帰を実装できない
    • 再帰がなければ、計算可能なあらゆるものを計算できる最小基準である チューリング完全性 に到達できない
  • lambda を導入するために assoc(x,y) と pairlis(x,y) が追加される
    • assoc(x,y) はリストで実装されたキー/値検索であり、連想リストを使う
    • pairlis(x,y) は Python の zip(x,y) のように 2 つのリストを組にする
  • 元の Lisp では、単純な線形走査であっても 再帰 で処理しなければならなかった
    • 元の Lisp にはループがなかったためである
    • Python への翻訳では assoc と pairlis をリスト内包表記でより簡潔に表現できる
  • COND 処理では元の Lisp の evcon をループに翻訳し、LAMBDA 処理でも evlis に同じ方法を適用している

環境リストと動的スコープ

  • 元の Lisp の eval 関数は 2 つの引数を受け取る
    • 1 つ目の引数は評価する S-expression
    • 2 つ目の引数はキー/値の一覧からなる環境リストである
  • 環境は LAMBDA 処理で 変数バインディング を保持する
    • 関数に x 変数があり、そこへデータを代入すると、pairlis が x シンボルとデータを結び付ける
    • 結び付けられた値は環境リストに保存または追加される
    • x が必要になると assoc が環境から探し出し、式に再び代入する
  • このバインディング方式は 動的スコープ と呼ばれる
  • 最終実装は元の「Lisp in Lisp」を Python に移し替えた形であり、最後の例では lambda の実行まで含まれている

関連記事

2件のコメント

 
GN⁺ 2024-05-13
Hacker News のコメント

  • シンプルで高速な Python 風スクリプティング Lisp に興味があるなら、Clojure スタイルの言語として Hy と Janet は見る価値がある

    1. Hy(https://hylang.org/): Python バイトコードにコンパイルされ、通常の Python より遅いが、すべての Python ライブラリと互換性がある
    2. Janet(https://janet-lang.org/): Lua スタイルの非常に軽量な組み込み向け仮想マシンで約 1MB。似た演算では Python よりおおむね 2 倍速く、C との相互運用が非常に簡単
    • 高速な Python 風スクリプティングなら、バッテリー同梱の Common Lisp である https://github.com/ciel-lang/ciel もある
      起動の速いバイナリとして提供され、日常的な作業向けのライブラリも含まれている
      CL↔Python 方面は https://github.com/CodyReichert/awesome-cl?tab=readme-ov-fil... も参考になる
    • Hy が Python より遅いって？ 少なくとも実行時間ではそうであってはならない
      自分は Hy のメンテナー だが、意味のある性能差が見えるならそれはバグだ
      1. Basilisp(https://github.com/basilisp-lang/basilisp): 「Python 3.8+ をターゲットにした Clojure 互換-ish な Lisp 方言」
    • 気まぐれに見えるかもしれないが、Lisp は必須の囲み括弧のせいで、いつも反論を招く言語のように感じられた
      M 式はこの落とし穴を避けているので、Lisp の同図像性（homoiconicity）と概念的な優雅さを保ちながら、こうした括弧を要求しない実用言語があったのか気になる
    • https://github.com/yaml/yamlscript
      まさに思い浮かべているそれ。説明も非常に直截的だ: “Program in YAML”
      ほとんどこれ以上言うことはない

  • ちょっと待って、これは単に Python で実装した Lisp ではないのか？
    タイトルが示唆するような同図像的な Python ではないように見えるが、自分は何を見落としているのだろう？

    • Greenspun の第十法則によれば、その通り: https://en.m.wikipedia.org/wiki/Greenspun's_tenth_rule
    • 自分も、同僚に Lisp を受け入れさせなくても使わせられる 同図像的 Python だと思ってかなり興奮したが、そうではなく、ただの Lisp だった
    • そう見える。この同図像的 Python を見たくて気になったが、可能なのかもよく分からない
      そのためには Python の文法がタプル、リスト、辞書で構成され、インタプリタがそれらを直接評価する必要があるだろう
    • 違いは何？

  • Python で簡潔に実装できる別の関数型言語として Binary Lambda Calculus がある
    コードのかなりの部分は BLC の純粋な入出力モデルを扱っており、変数検索には連想リストではなく de Bruijn インデックスで環境配列をインデックスする
    同じページには他の 9 言語での実装もあり、BLC の自己インタプリタがパーサとトークナイザまで含めて 232 ビット（29 バイト）で最も簡潔だ
    [1] https://rosettacode.org/wiki/Universal_Lambda_Machine#Python

  • MIT のプログラミング基礎科目では、全学生に Python で Lisp インタプリタ を書かせる
    以前その授業が実際に Lisp で行われていた時代の名残だ
    https://py.mit.edu/spring24

    • 同じように、自分が大学で受けた授業でも Lisp で基本的な Lisp インタプリタ を実装させられた

  • 似たようなことを JS のリストでやったことがある: https://github.com/andrelaszlo/js-lisp

  • 現代の言語が何十年も経ってから Lisp の驚くべき機能を再発見しているのは、笑えると同時に皮肉でもある
    数日前、自宅サーバーの API を 9 時間呼び出していた Python プログラムが止まってしまい、腹が立った。似たような API 呼び出しで、事前定義したプロンプトテンプレートと文法制約を使って LLM を呼び出していた
    残りの反復を別で回す前にプログラムの状態を保存して終了したかったが、実行中の Python コードを修正したり変数を覗いたりする方法が見つからず、結局 9 時間分の作業を失った
    数日後に https://malisper.me/debugging-lisp-part-1-recompilation/ を見て、Common Lisp がこうした機能を何十年も前から言語に組み込んでいたことに驚いた。最強クラスのマクロシステムのような他の機能も同じ

    • 現代の言語が何十年も経って Lisp の機能を再発見するのは驚くことではない。Lisp 系は最も柔軟で表現力のある言語だから
      だが、それこそが問題でもある。表現力が強すぎる
      Lisp はいつもミクストメディアの視覚芸術を思い起こさせる。表現の自由は良さそうに見えるが、結局はより伝統的な単一メディアの芸術より成果物が概して劣ることが多い。媒体の制約も表現力と同じくらい重要だということが分かる
    • ある程度状態を覗き見るには Py-spy や Pystack を使える
      あるいは https://github.com/malor/cpython-lldb もある
      さらに多くの方法は https://github.com/albertz/pydbattach/
    • 何時間も動くプロセスなら、作業をディスクに保存し、中断した地点から再開できる準備をしておくべき
    • 例外は投げられなかったの？

  • この実装のどこが 同像的な Python なの？

  • プログラムが大きくなるにつれて Lisp が読みにくくなりがちな傾向を、ある程度抑えてくれる 型システム を持つ Lisp はあるのだろうか？
    型システムでなくても、そうした性質を制御できる別の要素があるのか気になる
    メタプログラミングは本当に素晴らしいが、時にはこれまで見た中で最も難解な抽象 Haskell のように読めるのに、道しるべになる型シグネチャすらない
    型システムとリンターはコードを自動的に手なずける最良の道具だと思っているが、Lisp を選ぶ理由そのものを制約せずに Lisp プロジェクトの傾向をどう抑えられるのか、あまり想像できない

    • 型システムのある Lisp なら Common Lisp が思い浮かぶ
      事実上の標準に最も近い SBCL は、コンパイル時の型チェックもかなり優れている
      例えば (declare (type String a b)) の後に (+ a b) と書くと、A の派生型が STRING なのに NUMBER であるべきだ、という警告を出してくれる
      私が Scheme から CL に移った最大の理由がこの型チェックで、その後は restarts や continuable asserts のようなちょっとした良い機能のおかげで居続けた
    • 親しみやすく取っつきやすい側には Typed Racket、強力だが複雑な側には Shen がある
    • https://en.wikipedia.org/wiki/Dylan_(programming_language)

  • 式指向の Python があれば、今の Python よりずっと良いものになるはず
    この記事はタイトルが示唆する内容ではないが、Lisp の説明としては良い

    • 式指向の Python は、もはや Python ではないだろう
      それでも構わないが、「式を二級の構文として扱うこと」はかなり根本的で意図的な選択だ。括弧まみれを書こうとする開発者に苦労させるための設計でもある
      だから lambda: と := は使用を抑えるためにわざと不格好で、匿名関数も書けない
      Python は、賢いことをしたいなら callable オブジェクトではなく イテレータ でやれ、と言う言語だ

  • すべてに Lisp 式の無文法 があればいいのに
    私にとってはそのほうが良いし、幸い CL ではそうするのが簡単だ
 
kayws426 2024-05-13

Pythonに埋め込まれたLispの方言
https://hylang.org/