プログラミング言語「ほむほむ」について

前回に「問題がある」と言った点、それは何かというと

構文規則がよく解らない

ということである。

Grassの文法と異なる点は以下のとおり。

wがほむ

スペース・タブにはさまれた"ほむ"がW

vは改行

元々が単なるネタであまり細部を詰める気がなかったからだと思われるが、曖昧過ぎてパーザが書けない。こういう「文字を限った難解言語」（Grass とか Brainfuck とか Whitespace とか）は「意味のある文字以外は（エラーでなく）無視する」とすることが多い。*1しかし、この曖昧さだと例えば

ほむっほむ ☆ ほむほむっ ほむ ほむ！ <改行>

のようなかなり不規則な入力行が来た時にどう解釈すべきなのか判断がつかない。*2こういう場合には作者の与えているインタプリタ（Home2Lang.scala）*3の動作を正とするのが一つの手であるが、私は Scala なんて 1 ミリも知らない。困った。

判らないなりに何となく Home2Lang.scala を眺めていると奇妙なことに気付いた。（120 行目）

  def prog :Parser[List[Insn]] = rep( abs ) ~ rep( app ) ~ rep( v ) ^^
    { case a ~ p ~ v => a ::: p  }

これだと、「App の後に Abs を書けない」ことになる。((Home2LangParser の全体を見る限り、〈~〉は「パターンの連接」であろう。「パターンの OR」は 111 行目にある〈|||〉のはずである。))無論、Grass はそうではなく、実際にネットにある Grass プログラムで「App の後に Abs がある」ののは幾らでもある。この仕様を正とすると、なぜこの重要な相違点が説明されていないのかが判らない。結局、（後でみるように）Home2Lang.scala には「実装上の手違い」が幾つかあることが判ったので、この違いも「実装上の手違い」であると判断した。つまり、Grass の規則と同一であるとした。

最終的に、ソースと日本語の両方から適当に判断して、以下のものを「仕様」と定めることにした。（Grass のプログラム文字列への変換の形で書くことにする。）

プログラムは文字列として与えられる。文字コードや「改行」の定義については処理系依存とする。*4（※1）
「空白文字」とは SPACE(U+0020) または TAB(U+0009) のことである。*5
文字列を先頭から順に読み、以下の規則で変換した新しい文字列（Grass のプログラム）を生成する。
1. 「改行」が現れた場合、（1 個の）〈v〉に変換する。
2. 〈ほむ〉(U+307B U+3080) が現れた場合、（1 個の）〈w〉に変換する。
3. 「(空白文字が 1 個以上) (〈ほむ〉が n 個) (空白文字が 1 個以上)」（n ≧ 1）のパターンが現れた場合、n 個の〈w〉に変換する。
4. 3 項以外で空白文字が現れた場合の変換結果は未定義である。*6（※2）
5. 1〜4 の何れにも該当しない場合は、現在読んでいる文字を無視する。
変換結果（〈w〉と〈W〉と〈v〉の列）に以下の後処理を施したものを最終的な「対応する Grass のプログラム」とする。
1. 末尾にある〈v〉の列を削除する。
2. 先頭が〈w〉でない場合、または 2 個以上の〈v〉が連続する箇所がある場合の変換結果は未定義とする。*7（※3）

（複雑すぎる……）

この規則で、先に挙げた「ほむっほむ_☆…」（「_」で SPACE を表すことにする）を解析すると「_☆」の箇所で引っかかって「未定義」になる。「無関係な文字を予め削除してから変換する」だと「wwWWwWv」((無論これ自体も〈v〉の前に〈W〉があるので不正であるが。))となるが、そうではないことに注意。

ところで、grassator のインタプリタは上の規則を緩和している、つまり「未定義」の場合の幾つかを有効なものとして「定義している」。*8

※1 について：文字コードは UTF-8 である。*9「改行」は Lua インタプリタ *10に依存すると思う。
※2 について：ある行において、〈ほむ〉の前に出現する空白文字の列が偶数回ならば〈w〉、奇数回ならば〈W〉という解釈をする。((やはり、「_☆_」は「2 つの」空白列となることに注意。))
※3 について：先頭の〈v〉の列も無視する。((その後で先頭が〈W〉ならばエラーである。))また、〈v〉が 2 個以上続く列は 1 個の〈v〉に置き換えられる。

この規則で、先に挙げた「ほむっほむ_☆…」を解析すると「wwwwWw」となる。

Home2Lang.scala を上述の仕様に合わせて、かつ他の「実装上の手違いと思われるもの」*11について修正するための差分を掲載する。ただし、前に言った通り、Scala は 1 ミリも知らないので取り扱いに注意されたい。「未定義」の場合に実際にどうなるかは把握していない。

--- HomuHomuOrg.scala	Thu Dec 08 04:00:24 2011
+++ Homuhomu.scala	Thu Dec 08 04:13:09 2011
@@ -57,7 +57,8 @@
   val ChurchFalse = Fn( Abs( 1, Nil,  NoPosition) :: Nil,  Nil)
 
   override def apply( v:Value, ced:CED ) = v match {
-    case CharFn( c ) => CED( ced.c, ced.e ::: ( if( char == c ) ChurchTrue else ChurchFalse ) :: Nil, ced.d )
+    // 明らかにリストの前に付加でないとおかしい
+    case CharFn( c ) => CED( ced.c, ( if( char == c ) ChurchTrue else ChurchFalse ) :: ced.e, ced.d )
     case _ => throw new Exception("eval error value is not CharFn")
   }
   override def toString = "CharFn(%s, %s)".format( char , char.toInt)
@@ -76,16 +77,19 @@
 object Out extends Value {
   override def apply( v:Value, ced:CED ) = v match {
     case CharFn( c ) =>
-      print(c)
+      // 何故か Scala 2.9.1 だとこれでないと失敗する
+      Console.print(c)
       CED( ced.c, v :: ced.e, ced.d )
     case _ => throw new Exception("eval error value is not CharFn")
   }
   override def toString = "Out"
 }
 object In extends Value {
+  val cin = Source.stdin
   override def apply( v:Value, ced:CED ) ={
-    val c = readChar
-    CED( ced.c, CharFn( c ) :: ced.e, ced.d )
+    // readChar は 1 文字ずつ読むのではない
+    val c = if (cin.hasNext) CharFn( cin.next ) else v
+    CED( ced.c, c :: ced.e, ced.d )
   }
   override def toString = "In"
 }
@@ -117,8 +121,12 @@
   def abs :Parser[Abs] = wrap( rep1( w ) ~ rep( app ) ~ rep(v) ) ^^
     { case ~( p, ws ~ body ~ vs ) => Abs( ws.size, body, p ) }
 
-  def prog :Parser[List[Insn]] = rep( abs ) ~ rep( app ) ~ rep( v ) ^^
-    { case a ~ p ~ v => a ::: p  }
+  // Abs と App の並びの規則を Grass に一致させる
+  def progel :Parser[List[Insn]] = rep1( abs ) | (rep1( app ) <~ rep( v ))
+  def progtl :Parser[List[Insn]] = rep( progel ) ^^
+    { case pr => pr.flatten }
+  def prog :Parser[List[Insn]] = rep( v ) ~> abs ~ progtl ^^
+    { case a ~ pr => a :: pr }
 
   def parse( s:String ):Option[GrassRuntime] = parseAll( prog , s ) match {
     case Success( insn, _ )  =>  Some( new GrassRuntime( insn, s ) )

さらに、普通のインタプリタのソフトウェアのように「ソースファイル名を指定する」形で実行するように変更したものを公開した。

https://gist.github.com/1491665

scalac でコンパイルした後、以下のようにして「ほむほむ」のプログラムを実行できる。*12 Java と同様に、NabeAzz.homu の文字コードはロケール指定のものに合わせる必要があるようである。

scala Homuhomu NabeAzz.homu

NabeAzz.homu について、Scala 2.9.1 + JDK 1.6.0_29 で正常動作することを確認した。

ところで、print() が Scala 2.9.1 でそのままでは使えないってどういうことなのか…？ Ruby 1.9 で grass.rb が動かないのは想定範囲内だったけど、もしかしたら Scala も同様な世界だとか…？

*1:実際、Home2Lang.scala のパーザもそうしている。

*2:Home2Lang.scala に実際に食わせると、かなり予想外の解析結果になることが多い。

*3:このファイル名は Gist のページに載っている。

*4:普通は「LF(U+000A)」「CR(U+000D)」「CR LF の列」の各々を「1 つの改行」と見做す。

*5:全角空白(IDEOGRAPHIC SPACE; U+3000) は含まれない。単純に Home2Lang.scala に従った。

*6:つまり「〈W〉である〈ほむ〉」の列の間に「無意味な文字」は入れられない。Home2Lang.scala では実際に意図しない解析結果になる。

*7:そのままだと結果の Grass プログラムは不正になるが、必ずしもエラーにしなくてもよいということ。

*8:それ以外の「未定義」はエラーとなる

*9:ところで、Grass も「ほむほむ」も言語の入出力は「バイト単位」である（「文字単位」でない）ことに注意。grassator は 8 ビットクリーンであるが、Home2Lang.scala はそうではない。

*10:つまり、それをコンパイルするのに用いた C 言語のライブラリ

*11:これのせいで Nabeazz.homu を動作させるのに随分苦労した……。

*12:コンパイルすると .class だらけになるので、JAR にした方がよいかも知れない。

マクロツイーター

はてダから移行した記事の表示が崩れてますが、そのうちに直せればいいのに（えっ）

プログラミング言語「ほむほむ」について