Cognition: メタプログラミングを再定義する新しい antisyntax 言語

 (ret2pop.nullring.xyz)
3 ポイント 投稿者 GN⁺ 2024-05-03 | 1件のコメント | WhatsAppで共有
  • Cognition は、Lisp や連結型言語の 先読み(read-ahead) 問題を避けるために、完全後置(postfix)の antisyntax を採用した言語研究プロジェクトである
  • 中核機構である delimiter、ignore、singlet、falias、crank、metacrank により、プログラム自身がトークン化規則と実行サイクルを変更できる
  • ブートストラップは、すべての文字を単一トークンとして読む状態から始まり、空白と改行を区切り文字として使う環境へ自力で移行する
  • crank と metacrank は、トークンをいつ評価し、いつ積み上げておくかを制御し、# コメント、\\ escape、[ quote、( macro のような prefix 文法 を後置システム内で定義可能にする
  • Brainfuck 方言も別個のパーサではなく、Cognition の単語とトークン化規則 によって実装され、文法そのものをコード化し自動化する方向性を示している

既存文法に対して Cognition が問題視する点

  • Lisp は s-expression とマクロシステムによって強力なメタプログラミングを提供するが、それでもなお 固定された文法 の影響を受ける
    • 左括弧は右括弧が現れるまで読み続けるべきだという合図であるため、言語内部で括弧の役割を変えるのは難しく、実装によっては不可能である
    • すでに読み込んだトークンの区切り方を後から変えるには、多くの文字列処理が必要になる
  • 現在の入力を見て先をさらに読まなければならない過程が syntax であり、基本的な先読みを前提にした瞬間に特定の文法形態に縛られる
  • Cognition はこれを避けるため、完全後置方式の antisyntax を使う
    • 連結型言語に近いが、一般的な連結型言語も角括弧や文字列 quote 文字のために先読み問題を抱えるとみなしている
    • Racket のマクロシステムは、実行中の動的な文法変更ではなく前処理を使う方式として区別される

プロジェクトと基本アイデア

  • Cognition は Matthew Hinton とともに数か月にわたって進められている 進行中の研究プロジェクト である
  • 実装リポジトリは cognition-rust にあり、リポジトリには言語に関する論文も含まれている
  • 理解には、パース、トークン化、文法に関する背景知識が役立つ
  • 説明は “baremetal cognition” コードから出発し、Stem に近い文法へ発展していく流れをたどる

Baremetal Cognition とトークン化

  • baremetal Cognition は見た目こそ Brainfuck に似ているが、より強力なメタプログラミングが可能である
  • 非常に小さなブートストラップコードは、空白や改行まで意味を持って扱い、初期状態ではすべての単一文字がトークンとして読まれる
  • Cognition は基本的にスタックベースの設計だが、スタックより一般的な意味で container という用語を使う
  • 基本環境では、特別な falias を除いて、どの単語も自動実行されない

  • delimiter, ignore, singlet

    • delimiter は、トークナイザが 1 つのトークンの終わりと次のトークンの始まりを認識できるようにする
    • 単一文字の delimiter 一覧は Cognition コード内で変更・読み出しが可能である
    • ignore 文字は、各 read-eval-print loop のトークン収集開始段階でスキップされる
    • デフォルトでは、すべての文字が delimiter であり、ignore 文字は存在しない
    • delimiter、singlet、ignore の一覧は、whitelist/blacklist フラグによって動作を切り替えられる
    • 初期設定は、blacklist delimiter なし、whitelisted singlet なし、whitelisted ignore 文字なしである
    • singlet は、自身をトークンに含めたうえでトークン収集を終了させる第 3 のトークン化カテゴリである

  • falias

    • falias は、container に載った瞬間に実行される単語の一覧である
    • デフォルトの falias である f は、container に積まれず、container 最上位の単語を実行する
    • 例では f が d を実行すると、d は delimiter 一覧を単語の文字列値に変更する
    • その後、l、g、t、d のような文字を段階的に non-delimiter にし、空白と改行を delimiter および ignore に変えるブートストラップが続く

ブートストラップが作る実行環境

  • 初期ブートストラップは delimiter と ignore の規則を変更し、最終的に 空白と改行 がトークン delimiter となり、トークン開始段階では空白と改行が無視される環境を作る
  • その後 1 と crank を読み込み、f が crank を実行して crank 1 環境に入る
  • この過程の核心は、実行中にトークン化方式を変更できる点にある
    • delimiter、singlet、ignore の変更をプログラムとして自動化できる
    • 後置方式で先読みがないため、式を評価する前に 1 つ以上のトークンを先にパースしておく必要がない
  • falias は、prefix 単語や基本単語の自動実行なしでも特定の単語を実行させられる

crank と metacrank

  • crank は、スタック上のトークンをどの周期で実行するかを決める仕組みである
  • crank という単語は数値を引数に取り、その後 container に載る単語について、n 個ごとに stack top を実行する
    • ブートストラップ末尾の 1 crank は、すべてのトークンを評価する環境を作る
    • 5 crank 状態では、5 個目のトークンが入るまで単語を積み上げられる
  • 例示コードでは、2crank という単語を作るために unglue、swap、quote、prepose、def を用いている
    • unglue は単語の値を取り出し、crank のような builtin の関数ポインタも取得できる
    • prepose は Stem の compose に近いが、前方に付加して VMACRO に入れる
    • def は、2crank が 2 を stack に置いて crank builtin を呼び出すよう定義する

  • Cognition の container と macro

    • Stem では単語を stack に直接置けるが、Cognition では未評価の単語は container の中に入る
    • この設計により、compose のような単語が単一単語 container と別の container を一貫した API で扱える
    • Cognition の macro は Stem の quote とは異なる
    • macro が評価されると、crank を無視して内部のすべての要素が評価される
    • 単語にバインドされた macro を評価すると、macro 全体が crank に関係なく実行され、cranker は 1 回だけ増加する
    • macro は crank 非依存のコードや、最適化目的の expansion に有用である

  • metacrank

    • n m metacrank は、stack 上で上から n 個下の要素に対して、周期 m の評価を設定する
    • crank は 0 m metacrank と同じである
    • 1 トークンあたり評価できる metacrank は 1 つだけで、より低い metacrank が優先される
    • metacrank と crank は、ファイルのトークンだけでなく、単語定義を再帰的に評価する過程にも適用される
    • metacrank により、「n 個のトークンを読んだあとでこのトークンを実行したい」といった 直接的な文法操作 が可能になる
    • prefix 単語をプログラミングしたあと、不要になれば undef できる
    • 特定の終了文字ではなく、特定のトークン数の後で止まる prefix 文字も作れる
    • ユーザー入力を数式処理プログラムに渡し、その出力を metacrank のような文法システムに送ることもできる

Stem 方言へ発展する過程

  • Cognition は、ブートストラップ後に Stem v2 に近い文法を言語内部で段階的に構築していく
  • まず f を falias 一覧から削除し、ing だけを残す
    • f を直接 stack に置くと実行されてしまうため、ff を作ってから文字列を半分に切り、2 つの f を得る
    • その後 f は false に相当する空の単語として定義される

  • # コメント

    • # 文字は、初めて 本当の prefix のように動作するコード例である
    • このコメント文字は改行までのテキストを捨てる prefix として動き、パーサが先を読む形の文法を作る
    • 実装は geti、getd、gets、crankbase、halt、VMACRO cast、singlet、delim などを組み合わせる
    • geti、getd、gets はそれぞれ ignore、delimiter、singlet を文字列として取得する
    • halt はすべての metacrank を 0 にする
    • VMACRO cast は stack top の container を macro に変換する
    • # の定義は、トークン化規則を変更したうえで将来トークン化される単語に対して # を呼び出し、そのコメントを drop したあとで元の crank と metacrank に戻る

  • escape, quote, macro

    • \\ は、評価される単語であっても stack に載せられる escape 文字 として定義される
    • その後 [ quote の定義が追加され、さらにその quote を使って再帰 quote が可能な、より良い [ 定義へと自分自身を再定義する
    • 後置 def のため、以前の定義を使って新しい定義を作れる
    • このパターンは low-level Cognition でよく使われる開発方式である
    • ( は macro bracket として定義される
    • macro は自動展開されるよう作られており、すでに展開済みの macro を単語にバインドするほうが効率的だとされる
    • 機能的には同じ方法で評価される
    • expand は quote や macro 内の単語定義を unglue によって再帰的に展開する
    • まず基本的な expand を定義し、その後より一般的なケースを扱えるよう expand 自身を使って再定義する

Brainfuck 方言

  • Cognition は、発展した Stem 方言の上で Brainfuck 方言 を定義する
  • 実行例は ../crank -s 2 bootstrap.cog helloworld.bf brainfuck.cog である
  • brainfuck.cog は一般的な意味での Brainfuck パーサではない
    • Brainfuck の単語を定義する
    • Brainfuck をトークン化する
    • Cognition ネイティブ環境で実行する
  • この例は、Cognition 文法によって代替文法を容易に定義できることを示している
  • Cognition は、記号を読みその記号に応じて動作を決めるのではなく、metacrank を使う prefix 文字そのものを単語として定義 し、文法を単語定義の中に埋め込む

dialect dialect 構想

  • mkprefix のような単語を想定できる
    • たとえば [ と ] という 2 つの入力単語と何らかの演算を受け取り、[ が ] に出会うまでその演算を適用するよう自動定義する単語である
  • こうした構想が可能なのは、metacrank と def がどちらも 一般の単語 だからである
  • d、i、s まですべてが単語であるため、文法実装過程を自動化する、より抽象的な方言を作ることができる
  • 標準ライブラリにはまだ実装されていないが、Matthew Hinton と標準ライブラリの可能性として議論された項目がある
    • 抽象単語を自動生成して呼び出す metaword
    • 現在の wordlist を自動抽象化する word-generator 検索
    • 問題解決のために抽象化フレームワークを指示する方式

文法をコードとして扱う可能性

  • Cognition では、文字列処理は トークナイザ後処理 に等しく、文字列操作が強い意味を持つ
  • 潜在的な応用分野として、Symbolic AI、syntax や grammar の研究、言語と metalanguage のプロトタイプ実験が挙げられている
  • 設定ファイルを読むプログラム、Cognition ベースの shell、Cognition ベースの OS といったアイデアもある
  • 核心は、Cognition が “syntax as code” を可能にする点にある
    • 文法を動的にプログラミングできる
    • 文法生成そのものを自動化できる
  • Metastack や cd のような概念は扱われておらず、今後の記事で取り上げられる可能性のある話題として残されている

関連記事

1件のコメント

 
GN⁺ 2024-05-03
Hacker Newsのコメント
  • Racketのreaderレイヤー設定よりこの方式が優れている、という説得はまだされていない
    たとえばRacketでは、Datalogの構文を使いながら他のRacketモジュールと相互運用できる組み込みDatalog実装を作れるし、基本データモデルは変わらない
    S式に閉じ込められずにメタプログラミングでき、それでいてより高いレベルで処理する方式だ
    こうした構文ブートストラッピングは見事で研究上の価値もあるが、Racketのアプローチより根本的に優れているのかは分からない
    Lisp、Scheme、Racketのマクロは通常AST上で動作するが、RhombusはASTに似ていながら一部のパース判断を後回しにする「shrubbery」上で動作し、構文拡張に多少の柔軟性を与える
    参考: https://docs.racket-lang.org/guide/hash-reader.html、https://docs.racket-lang.org/datalog/datalog.html、Rhombus論文 https://doi.org/10.1145/3580417
    • Common Lispのreadtableより優れているとも確信できないし、CLのreadtableよりRacketの#langのほうが使いやすいと思う
      readtableだけでもCコンパイラを実装できるほど強力だ: https://github.com/vsedach/Vacietis
    • 基本例としてBrainfuckを使っているのを見ると、真面目に受け取れという意図なのかよく分からない
      個人的には「metacrank」が出てくるところで吹き出した
    • LispマクロがAST上で動作するという言い方は、Lispには当てはまらない
      Emacs Lisp、Common Lisp、ISLISPでは、マクロは何らかのデータを受け取り、何らかのデータを返すだけで、ASTのような概念はない
      (foo-macro ...)を呼び出すと、...は任意のデータであり得る
      たとえば(defmacro rev (&rest items) (reverse items))は、マクロ呼び出しのソース引数リストを受け取って逆順にするだけだ
      (rev 1 2 3 4 +)や(rev (rev 10 n -) (+ a 20 b) (rev 30 a *) list)のように使え、実際にはリスト、数値、シンボルが渡される
      テキストでもASTでもなく、evalに計算済みのデータを渡しても同じ方式で動作する
      Lispのreaderは基本的にデータ層であるS式を読み、EVALやマクロや他の機能は主にデータを受け取る
      コンパイラが内部的にAST表現を作ることはあり得るが、それは実装の自由であり、Lisp言語は通常、テキスト構文ではなくデータ構文の上で定義される
      Lispインタプリタは実行中にテキストではなくS式を処理する「List Processor」であり、COMPILEもテキストではなくS式を受け取る
      RacketとSchemeには別個のマクロシステムがある
  • 筆者への助言としては、最も重要な内容を先に置くと、文章はずっとしっかりしたものになる
    実際のプロジェクトであるCognitionが言及されるまでに300語以上が費やされており、Lispの話も良いが、それがプロジェクトで最も重要な部分なのかは疑問だ
    情報系の記事を読むときは、常に「自分の時間を使う価値があるか？」を考えるので、文書が何についてのものなのかを最初から示すべきだ
    「Cognitionはユーザーが変更可能な構文を探求する新しい言語だ」のような形で十分だったはずだが、最初の4段落を過ぎても読み続ける価値があるのか判断しにくかった
    • この言語を使う可能性も低いし、仮に使うとしても情報はこの記事ではなくドキュメントから得るだろう
      時間がお金なら、この記事を読んだ時間は無駄だったと言える
      インターネット上のすべてのコンテンツが個人の好みに合わせられることを期待するより、すでにある形式に適応するほうがよいと思う
      テキストは動画のように順番にしか消費できない媒体ではないので、斜め読みして興味深い部分を探し、なければ捨て、あれば最初に戻って読めばよい
      多様な書き方は、消費する情報を意識的に選別させるのでより良いし、受け身で消費するだけだと頭が怠ける
      ただし動画だったなら同意したと思う
      動画は見る前に時間を投じるか決める必要があり、2倍速や5〜10秒スキップは多少助けになるが、問題を解決するわけではない
    • 順序はかなり合理的に見えた
      まず問題を説明し、その次に解決策を紹介する構成だ
      数文読むだけで、Lispの名前は聞いたことがあるがEmacsの設定ファイル以外では使ったことのない私のような人を含め、99.999%が気にしない「問題」に対するドン・キホーテ的な解決策だとは分かったが、それでもそのまま読み続けた
    • Lisp関連の部分はプロジェクトの最重要要素ではないが、プロジェクトが解こうとしている問題の種類を示す役割は明らかに果たしている
      こうした部分がなければ、後の内容はもっと理解しにくかっただろう
    • 概念には興味があるが、最初の文がLispのS式構文への反応として必要性を正当化しているように見えたので、文脈を見失うのではないかと心配になった
      その背景を知らなければ記事全体の文脈を見失う可能性があり、これが藁人形論法なのかも判断しにくい
      そのため全体が非常に狭い必要性のために存在しているように感じられる一方で、タイトルははるかに一般的で、かなり興味深い概念のように見える
    • 今の記事でもまったく問題ないと思う
      最初の2文の中で解こうとしている問題が何かが示されており、自分の関心を見極めるには、提案された導入部よりずっと有用だ
  • 興味深い記事で、筆者たちにはここでの皮肉を気にせず、闇の魔術儀式を続けてほしい
    ただ個人的には、プログラミング純粋性の梯子を見上げると、Forthあたりが自分に耐えられる哲学的純粋性の限界だ
    • この記事の著者としては、皮肉は気にしておらず、むしろかなり面白いと思って歓迎している
      今後もさらに多くの闇の魔術を扱い続ける予定だ
  • メタプログラミングとプログラミングは同じものだ
    ただし、あらゆるLispを含むほとんどすべての言語がクォートを誤って扱っており、面白いことにm4は例外だ

Lisp はマクロでこの問題を回避し、オブジェクト言語の文で表現されたメタ言語の文を、引用を無視して扱えるようにしている。
この問題は、オブジェクト言語とメタ言語の両方で空白をアトムの終端として扱い、両者を区別しないことから生じる。
完全な後置式アンチシンタックスという Cognition のやり方は連結型プログラミング言語に似ているが、後置式言語は前置式言語の双対であり、同じ問題を抱える。
すべてのシンボルのアリティを事前に決めて高階関数を使わないようにするか、ツリーをシリアライズできる区切り子のペアが必要になる。
暗黙の 0 次スタックに依存するのは、うつ病を治そうとして前頭葉ロボトミーをするようなものだ。

  • フィードバックはありがたいが、まだ記事全体を読んでいないなら読んでみるとよい。
    私たちがどの程度新しいことをしているのかは私たちにも分からないし、Lisp で私たちのやっていることができると思うなら、それが間違いだと証明してくれてもよい。
  • Lisp と m4 で引用がどう違うのか、例が気になる。
    主張自体は興味深いが、もっと具体的なものが必要だ。
  • 暗黙のスタックについての比喩は派手ではあるが、暗黙のスタックは初期のコンピュータや電卓の時代から存在していた。
    前頭葉ロボトミーが高次処理能力を低下させるように、コマンド文字列計算の最も原始的な方式に戻ることも似たようなものだと言える。
    https://www.hpmuseum.org/rpnvers.htm
  • Cognition のプログラムが実行中に文法構造を定義・再定義し、その内外に出入りできる点は本当に美しいと思う。
    特に、その仕組みが非常に小さい点がよい。
    言語の専門家ではないので新規性があるのかは分からないが、記事を読むあいだ、作者たちが丘を越えるたびに新たな可能性の山脈を見つけていく喜びが感じられた。
    正しく理解しているなら、Cognition で本当に考える機械を作れるという話だ。
    プログラムが中断されて新しい命令で再起動されなくても、新しい入力をもとに自ら新しいサブルーチンを書いて実行できる。
    つまり、プログラムが新しい抽象化を作り、新しい API に接続しながら学習し適応できるということだ。
    私には、より大きなニューラルネットワークや新しい学習手法よりも、こちらの方が興味深い。
  • 前提が事実ではない。
    Common Lisp には reader macro があり、好きなように文法を変えられるし、reader macro で Fortran 文法を読む Fortran コンパイラもある。
    Common Lisp には読み取り時点の reader macro、マクロ、コンパイル時点の compiler macro があり、これらすべてのマクロ言語が Common Lisp だ。
    メタプログラミングはマクロや文法とはあまり関係がなく、型・インターフェース・クラス・メソッドなどの意味論と意味を操作する能力を指す。
    CL 自体が十分に強力でないなら、そのために CLOS、つまり Common Lisp Metaobject Protocol がある。
    • ここで言っているのは CL の reader macro のことだ。
      CL の reader macro で別のトークナイザを使うことはできるが、read table 内の式でトークナイザの切り替えを知らせる必要がある。
      Cognition では、関数を呼び出すと呼び出し元のコンテキストのトークナイザが変わるように見える。
  • 最小の機械を高水準言語のインタプリタとしてブートストラップする実用例に見える。
    チューリングマシンやラムダ計算のようなものでこの種の作業が重要だと学んだ理由は、高水準言語が基礎言語と等価であることを示し、したがって前者について推論した内容を後者にも適用できることを示すためだった。
    思い浮かぶ最初で唯一の例は停止性問題だ。
    実用的な規模では、基礎言語にメモリリークがないことを証明すれば、派生言語にもリークがないと言えるのだろうか。
    この種のブートストラップにはどんな利点があるのか気になる。
    答えが単にエベレスト登山のように「そこにあるから」なら、それも尊重する。
  • df の後の空白、3 行目の空白、改行が重要だというところで、すぐに「ありがたいが遠慮する」となった。
    前の行末の 3 つの空白文字は皮肉を表しており、末尾の空白を簡単に区別できない場所では文字どおりに解釈すればよい。
    • この実験の要点は、Forth には再定義できない文字が 1 つ、つまり空白があり、その制約をなくすとどうなるか、というものに見える。
      言及されたブートストラップ部分は、実際には読者に空白と改行を区切り子として扱うよう伝えている箇所だ。
      つまり、区切り子として宣言する区間で空白が意味を持つことに不満を言っているわけだ。
      もちろんそう考える権利はあるが、これをもっとよくやる方法があったのかは気になる。
    • その空白文字たちは、それ以前は他の文字と何ら変わらなかった空白を、実際に空白というものにする方法だ。
      一度はリテラルな空白がそのように意味を持たない限り、これを行う方法は思いつかない。
  • 「何らかの形の文法を持つ罠」と言うが、文法は構造を与える。
    文法なしで「sentence this without you syntax read can」のような文を読めると思うのか。
    Cognition は完全な後置式アンチシンタックスを使うというが、後置式も文法だ。
    ドイツ語話者に、文末に来る動詞について聞けばよい。
    最初の例でもオペランドと演算子の順序が重要で、それこそが文法だ。
    これはばかげたほど圧縮された言語を作ろうとする試みに見え、APL を強く思い出す。
    著者たちにヒントを出すなら、文法をなくしたのではなく、人間が読んで理解しにくくしただけであり、可読性と理解可能性はプログラミングにおいて重要な要素だ。
  • 読むのが少し大変だった。
    足元のルールが絶えず変わる感じで、ルールや単語が導入されたかと思うと勝手に再定義されるように見える。
    全体として Numberwang のような雰囲気があり、風刺のように受け取られる理由の一つに見える。
    もう一つの大きな理由は、ブートストラップ段階が滑稽なほどに書かれていることだが、それは意図したもののようだ。
    確かに深い何かがあるが、もっと濃いコーヒーを飲んでからもう一度読んでみる必要がありそうだ。
    • 説明すべきことが多く、今の説明の仕方が最適ではなかったとも思う。
      この記事の著者だが、問題は伝えるべき内容が本当に多いことだ。
      Matthew とこの言語設計について 3 週間、毎日何時間もやり取りしてきたし、実際に私を知らない人たちに補うべき文脈も多い。