dollar-expression ($式)

2013-11-24 02:32

$ define $ partition pred lis
  $ let recur $ $ lis lis
    $ if $ null-list? lis
      $ values lis lis
      $ let $ $ elt  $ car lis
              $ tail $ cdr lis
        $ receive (in out) $ recur tail
          $ if $ pred elt
            $ values $ if (pair? out) (cons elt in) lis
                     out
            $ values in
                     $ if (pair? in) (cons elt out) lis

                         ↓ ↑

(define (partition pred lis)
  (let recur ((lis lis))
    (if (null-list? lis)
      (values lis lis)
      (let ((elt (car lis))
            (tail (cdr lis)))
        (receive (in out) (recur tail)
          (if (pred elt)
            (values (if (pair? out) (cons elt in) lis) out)
              (values in (if (pair? in) (cons elt out) lis)))))))))

もくじ

• 概要
• 適当な定義
• Q&A
  • Q. 括弧の中で構文糖は使えますか？
  • Q. シンボルの$を使いたいときはどうしますか？
  • Q. $hogeやhoge$と書いたらどうなりますか？
  • Q. $$と書いたらどうなりますか？
  • Q. '$や`$などはどうなりますか？
  • Q. #$と書いたらベクタリテラル#( ... )の構文糖になりますか？
  • Q. $ )と書いたらどうなりますか？
  • Q. 行が右に長くなってきたら折り返しはできますか？
  • Q. ドット対を$で囲むことはできますか？
  • Q. タブはどう扱いますか？
  • Q. マーカーは$以外でもいいのでは？
  • 補足: なぜ$どうしを離すのか
  • 細かい仕様まとめ
• 読み込み器 ($式→S式) の実装
  • 処理系に挟む場合
  • readを再利用して手抜きする場合
• 書き出し器(S式→$式) の実装
• その他
  • インデントに意味がある構文
  • 参考記事
  • TODO

概要

冒頭のような文法を普通のS式にする変換器をGaucheで書いてみた。

$式(どるしき)という、閉じ括弧を省略できるS式の構文糖を考えた。インデントの具合から閉じ括弧を補完する。

S式と$式はJSONと(ややこしくない範囲の)YAMLのような関係にある。$式のパーサはS式のパーサとしてそのまま使える。

この構文糖の目的はPython系の文法が好きな人向けにインデントで表せる分のS式の閉じ括弧を省略できる記法を提供することで、S式以外の構造を表すものではないし、括弧を完全に排除することでもないし、Lispを他のプログラム言語らしく見せかけるためでもない。

以下Gauche (Scheme)の文法を念頭において考えている。

適当な定義

$式の字句構造はほぼS式と同様。

ただし、$を「開き括弧マーカー」と呼び、特別に扱う。(最初(でやっていたがエディタが混乱したのでやめた)

イメージとしては、$式用の(read)関数はこういう動作をする。

• アトムや括弧やクォートはそのままS式と同じように読み込む。
• $ があったらそれよりも字下げが下の$式を繰り返し読み込み、リストにまとめて返す。

マーカは、そこよりも右下に始点があるトークンをすべて括弧に囲む。 トークンの始点とは、そのトークンを構成する最初の文字のこと。 構文糖の解釈後マーカ自身は消えてなくなり、代わりに開き括弧が置かれる。 それに対応する閉じ括弧は、$よりも左下か真下に始点があるトークンが現れたとき、その手前に挿入される。

基本的には「$から下方向にテキストを選択して囲む」という感じ。改行入りの文字列などがぶつかっても大丈夫にするために始点だけを見るようにしている(つまり、矩形選択ではなく普通の選択)。

たとえば、以下の内容は

$ "foo
bar" $ baz
   quu
"qux"

次のように書いたのと同様になる。

( "foo
bar" (baz)
  quu)
"qux"

Q&A

元がふわふわしたアイデアなので、細かい所にかなり抜けがある。Q&A方式で文法の細かいところを考えていく。

組み合わせによって必要な処理が変わってくるので、ここではS式との互換性、実装がラクなこと、個人的な好みをこの順で選択の基準とする(※ラクかどうかの判断もsnipsnipsnipの偏見)。

Q&Aが他にあればコメントや追記をお願いします。(fork me!)

Q. 括弧の中で構文糖は使えますか？

A1 (採用)

いいえ。内部では$式の構文糖は使えません。通常のS式として解釈されます。

A2 (没)

はい。内部でも$式の構文糖が使えます。

A3 (没)

括弧は使えません。$だけでやってください。

これによって$式はS式のスーパーセットになるので、混ぜて書けるようになる。

閉じ括弧の対応を考えなくてすむ。

既存のread手続きが再利用できるので実装がラクになる。

Q. シンボルの$を使いたいときはどうしますか？

A1 (採用)

|$|を代わりに使って下さい。または、$を使いたい時は括弧の中で使ってください。

A2 (没)

使えません。

A3 (没)

$$を代わりに使って下さい。$$を$、$$$を$$のように$を一つ減らして解釈します。

理不尽さや制限が他の案に比べて少ない。

Gaucheでは$というマクロがあるが、この構文糖自体と目的がかぶっているのであまり困らないはず。

Q. $hogeやhoge$と書いたらどうなりますか？

A1 (採用)

シンボル$hogeやhoge$として扱われます。$は空白で区切られる必要があります。

A2 (没)

(hoge ...やhoge(...として扱われます。$はどこでも開き括弧と同様に扱われます。

$はシンボルに許される文字なので、シンボルに隣接した場合エスケープの必要がある。

Gaucheのpa$やreduce$を個人的によく使うのでエスケープしたくない。

$を離して書くことで後述する落とし穴をある程度防ぐことができる。

Q. $$と書いたらどうなりますか？

A1 (採用)

シンボル$$として扱われます。

A2 (没)

((として扱われます。

上の動作との一貫性。また、$を離して書くことで後述する落とし穴をある程度防ぐことができる。

Q. '$や`$などはどうなりますか？

A1 (採用)

クォートされたシンボルです。(quote |$|)として読まれます。
構文糖で準クォートのリストを書きたい場合は$ quasiquote $ ...と平で書いて下さい。

A2 (没)

クォートされたマーカーです。(quote (マーカーに囲まれる内容 ..))として読まれます。

こう書いた時()と$のどちらが表示されるかという話。A1では$、A2では()がプリントされる。

$ write '$

これは、quoteの処理と$式の処理の優先順位の話になる。

どちらもありえるが、好みで$がプリントされる方を選んだ。つまり、$式の解除は'→quoteの変換の後に行われる。

'fooが(quote foo)の構文糖と考えると、A1のほうが「括弧の内部には$式の構文糖は及ばない」というルールと一貫性がある。

Q. #$と書いたらベクタリテラル#( ... )の構文糖になりますか？

A1 (採用)

いいえ。構文糖で準クォートのリストを書きたい場合は$ vector 1 2 3と平で書いて下さい。

A2 (没)

はい。#$ 1 2 3とすれば#( 1 2 3 )として構文糖になります。

便利そうだが、#$をどうエスケープしていいかわからないので見送り。

Q. $ )と書いたらどうなりますか？

A1 (採用)

( ) )と解釈され、エラーになります。

A2 (没)

( )と解釈され、エラーは起こりません。

$を)で閉じられたら便利かもしれない。でも目が混乱すると思うので見送り。

通常のreadを使いまわすことを考えると、単独の)はエラーになるので使えない。とはいえ、これは先読みで対処することはできるので理由にはならない。

Q. 行が右に長くなってきたら折り返しはできますか？

A1 (採用)

いいえ。折り返したい場合は括弧の中に囲んで通常のS式として書いて下さい。

A2 (没)

はい。\を行末に書くと次の改行は無視されます。

A3 (没)

はい。\を行末に書くと次の行以降はその行より字下げされたものとして扱います。
\のある行よりも字下げが上がる行が現れた時、\の効果は解除されます。

オフサイドはあれば便利だが、括弧で一応解決できるし、ルールは少ないほうがよい。

Q. ドット対を$で囲むことはできますか？

A1 (採用)

はい。

A2 (没)

いいえ。ドット対は括弧の中だけで使えます。

囲めない理由はない。強いて言うなら、これによって$式をS式のリーダで読み込んだ時にエラーになる可能性が生まれる。

でもサンプル変換器では未実装。

Q. タブはどう扱いますか？

A1 (採用)

カラム数に足して次の8の倍数になる数だけスペース文字があるものとして扱います。

A2 (没)

スペース1文字と同じように扱います。

タブストップの処理はPythonを参考にする。

でもサンプル変換器では未実装。

Q. マーカーは$以外でもいいのでは？

A1 (採用)

いいえ。$式という名前が気に入ったので。

A2 (没)

はい。(を自動で閉じてもよいですね。

A3 (没)

はい。#$など拡張用のトークンを使うほうが安全ですね。

これは完全に好み。$式でなく:式でも!式でもいいと思う。

どんな記号を選んでも理由はつくが、$や:や!は通常のシンボルとして許されるので若干弱い。行頭にほぼ使われない.もいいかもしれない。最初は(のまま単純に「自動括弧閉じ器」を作ってみたこともあったが、あまりに目が落ち着かなかったので諦めた。

元の由来はHaskellの$(関数適用)演算子だが、Haskellは中置で、$式は前置というのが違い。

ドルマークは縦棒と開き括弧と閉じ括弧をまとめたように見えるという話をどこかで読んだ。

補足: なぜ$どうしを離すのか

condではまったから。

たまたまcondの処理の部分を2字ぶん下げたとする。

 (cond
   ((foo?)
     bar))

上の開き括弧を単純に$で置き換えるとこうなる。

 $cond
   $$foo?
     bar

これを$式で復元するとこうなって、元と構造が変わってしまう。

 (cond
   ((foo?
     bar)))

condの処理を条件部分よりも下げるとハマるというのは落とし穴として大きすぎる。 しかも文法的にはエラーではない。

これは$を離して書き、インデントを2字で統一することで問題がなくなる。

 $ cond
   $ $ foo?
     bar

対処療法的な感はあるが、そもそもインデント文法でインデントを間違えたらどうしようもないので文法チェッカーを別に作るしか無いと思う。

くっつけたままインデントを1字に統一するという後ろ向きな方法もあるので、このこと単体では$を全て離す理由にはならないかもしれない。

細かい仕様まとめ

• 括弧の内部はS式としてパースされ、内部では$式の構文糖は無効になる。
• 文字$は空白に囲まれた単独の場合でのみ有効で、それ以外の場合は全て通常のシンボルになる。
  • マーカーでなくシンボルの$を使いたい時は|$|と書く。
  • $hoge$のように書いてもそのまま$hoge$というシンボルになる。
  • $$はそのまま$$というシンボルになる。
  • '$は(quote $)になる。
• 開き括弧マーカー$で開かれた括弧は、閉じ括弧で閉じることはできない。
• ベクタリテラルの開き括弧マーカー版は無い。
• 行を途中で折り返す方法は$式には無い。そういう場合は括弧で囲んでS式に戻る。
• ドット対はS式の括弧の中でしか使えない。

読み込み器 ($式→S式) の実装

Haskellのレイアウトに習って、字句解析と構文解析の間にやる方法を考えた。つまり

1. 字句解析器を改造し、各トークンのカラム番号(行頭から何文字目か)がわかるようにする。
   あるいは、カラム番号を示す特殊なトークンを新たに用意する。
2. 構文解析の前に、カラム番号の増減をもとに閉じ括弧を補う処理を挟む。

'をquoteに直す処理と$式の処理のどちらを先にやるかで'$の解釈が変わってくるので注意。

処理系に挟む場合

処理系に組み入れる場合は、quoteの処理がすんだ直後のあたりに処理を挟むとしてこんな具合だろう。(まだ作ったことがないので適当)

1. 通常のS式として字句解析する。ただし、次のような特別扱いを加える。
   • 各トークンに、その始めの文字の行頭からのカラム位置をひも付けておく。
   • 開き括弧マーカーはシンボル$と区別する。 つまり、縦棒で囲まれた|$|はシンボル$として扱うが、 囲まれない$は開き括弧マーカーとして記憶する。
2. quoteなどを処理しておく。
3. トークン列を走査して次のように処理する。 括弧ネストのカウンタと数値のスタックが必要。
   1. 通常の開き括弧の類があったら無視フラグを立てる。
   2. 1に対応する閉じ括弧を見つけたら無視フラグを下ろす。
   3. スタックトップにあるより左か真下にあるトークン(マーカー含む)が現れたら、 そのトークンがスタックトップより右になるまで、 トークンの直前に閉じ括弧を挿入し、ポップすることを繰り返す。
   4. 開き括弧マーカーを見つけたら、 無視フラグが立っている場合、$シンボルに置き換える。 無視フラグが立っていない場合、そのカラム位置をスタックに記憶して、 開き括弧に置き換える。
4. スタックに開き括弧が残っていれば、その分閉じ括弧を挿入する。
5. トークン列から通常のS式と同様に木構造を組み立てる。

readを再利用して手抜きする場合

本来なら上の方法だと思うが、とりあえずやってみたかったので、既存のS式のreadを再利用してGaucheで書いてみた。

ドット対とタブストップが未実装。

1. カラムを記憶しながらreadを繰り返し、カラム数とS式のペア(以下$トークン)を集める。 処理系でする場合と違ってリストが読み出されることもあるが、 Q&Aで決めた通りなら問題ない。 readの前に先読みで少し前処理をする。
   1. 空白を読み飛ばす。
   2. 開き括弧マーカー$とシンボル|$|を区別するため、一文字先読みする。
   3. ドット`.`をそのままreadするとエラーになるので、回避のため先読みする。

      未実装。

2. $トークンの列を走査して次のように処理する。 カラム数とS式のリストのペアを要素とするスタックを用意する。 最初はスタックに(-1)を入れておく。スタックは決して空にならない。
   1. スタックトップの物よりも$トークンが右にある(カラム数が大きい)場合は、 スタックトップのリストの末尾に付け足す。
   2. スタックにあるより左か真下にある$トークンが現れたら、 その$トークンがスタックトップより右になるまで、以下の操作を繰り返す。
      • ※ ポップしたリストを新たなスタックトップにあるリストの末尾に付け足す
   3. 開き括弧マーカーを見つけたら、 スタックにカラム数つきの新しいリストをプッシュする。
3. スタックが1要素になるまで※を繰り返し、残った最終的なS式のリストを得る。

書き出し器(S式→$式) の実装

プリティプリンタをいじれば出来ると思う。

その他

インデントに意味がある構文

Haskell。空白に意味を持たない{...}と;による文法を基礎として、構文糖としてインデントを元に区切り記号を補うという形で定義している。この方法が好きなので$式もそれにならった。

Python。Haskellと違い完全に括弧を排除している(SyntaxError: not a chance)。特別なトークンとしてINDENTとDEDENTを用意している。括弧内でインデントの制限がないことの便利さにPythonで気づいた。

CoffeeScript。特別なトークンとしてINDENTとOUTDENTを用意している。

PythonとCoffeeScriptは「ブロックの途中で半端にインデントを増減してはならない」というチェックがあるのが親切。これは$式と関係なく作れると思うのと、letなどをどう扱えばよいのかわからないので割愛。

Lisp系では、SRFI 49: Indentation-sensitive syntaxとSRFI 110: Sweet-expressions（Readable Lisp S-expressions Project）がある。正確にはこれはSchemeのための構文糖であって、S式のための構文糖である$式とは少し目的が違う。この2つは行頭の開き括弧を暗黙にしようとしているのが気に入らない。

define factorial(n)
  if {n <= 1}
     1
     {n * factorial{n - 1}}

他にS式の構文糖(というよりプリプロセッサ？)を見つけたら教えて下さい。

参考記事

• Wiliki:Lisp:S式の理由

文法としてのS式について。

• C2 Wiki:Syntactically Significant Whitespace Considered Harmful

構文にホワイトスペースを使うことについて。

TODO

• $式と$式で書かれたプログラムの切り分け
• 逆変換器
• 実行器
• 変換器をブラウザで動かす