マクロツイーター

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

Googleが開発した新しい残念言語「og」登場!!

これは嘘ニュースです

(重要なことなので予め反転しました)

要するに、Google素晴らしいオモチャの綺麗なグラフィックを残念なテキストに変換した、ということ。

これだけで何となく解ると思うが、一応説明しておく。*1

  • 機械はテープとプログラムとプログラムカウンタ(PC)からなる。
  • テープは 1 次元に並んだセルの集まりである。
    • セルは左右に両方向に無限に並んでいる。
    • 各セルには単一の ASCII 文字*2が書かれている。
    • ヘッドのあるセルの文字を読んだり書き換えたりできる。
  • プログラムは 2 次元に並んだ命令の配列で、PC はその上を移動するカーソルである。
    • 機械の実行の各ステップで PC にある命令が実行される。その後、原則として PC は「1 つ右」に移動するが、命令の種類によっては異なる位置に移動するものがある。*3
    • PC より右にある命令が全て . (nop)であれば機械は停止する。
  • 命令は以下のものが存在する。(インタプリタでの命令の表記方法の説明を兼ねる。)
    • <--> : ヘッドを 1 つ左/右に移動する。
    • 'XX は ASCII 文字): ヘッド位置のセルに X を書き込む。
    • ^XvXX は ASCII 文字): ヘッド位置のセルの文字が X である場合、PC を「1 つ上」/「1 つ下」に移動する。(それ以外は、「1 つ右」に移動。)
    • @nn は正整数の 10 進表記): PC を「n 個左」に移動する。
    • . : 何もしない。
    • プログラム(命令の 2 次元配列)の各行の内容をソーステキストの 1 つの論理行で表す。ソースに記述された部分以外のプログラムの領域には全て .(nop)があると見做される。*4
    • 命令の記述の間にある(改行以外の)空白文字は無視される。
    • # は一行コメントの開始を表す。ソース上のコメントおよび空白文字しかない行は無視される。*5
    • 'X^XvXX の部分に _ を書くと代わりに空白文字を指定したことになる。*6また、単一の ASCII 文字の代わりに 2 桁の 16 進表記を書いて、その符号値の文字を表すことができる。((つまり、'0A で改行文字を書き込む。'A␣ ならば「A」を書き込む。'5F とすると「_」を書き込める。))
  • 入力・出力に関する定義:
    • 初期状態において、テープには「プログラムへの入力」の文字列が書き込まれていて、ヘッドはその左端のセルにある。
    • 初期状態において、PC はソースで記述された領域の左上にある。
    • 初期状態から機械を停止するまで稼働させる。その後、ヘッドの初期位置からテープを右方向に読み最後の非空白文字が現れるまでの部分にある文字列が「プログラムの出力」となる。

で、この「og」言語のインタプリタLua で実装したものを公開する。

以下に挙げるのは、入力のビット列を反転したもの(10100 → 01011)を出力する og のプログラムソースである。

[flipbits.og]
v0 .  v1 v_ -> @5
'1 v1 '0 ^0 ^1 .
.  .  .  .  ^1 .

先ほどのインタプリタで次のようにして実行できる。(「lua」は Lua の実行ファイルの実際の名前に置き換える。*7

> lua goog.lua flipbits.og 10100

これで出力の「01011」が表示される。さらに、

> lua goog.lua -vvv flipbits.og 10100

のように -vvv を指定すると機械の内部状態が表示される。

少し複雑なプログラムの例

FizzBuzz を作ってみた。ただし数値は二進表記にしている。

#            5             10       13
v_ -> @2 <- 'o <- '/ <- ': v:
'$ .  <- ^_ v: @3 .  .  .  @5
v$ v0 v1 -> @4 <- '1 .  @5
v$ v0 '_ .  <- v: @2 .  ^/
v$ '_ <- v: @2 <- '1 v1 ^/
'_ v_ .  <- '0 .  .  <- ^/ ': v:
v: <- @2 .  -> -> '+ -> ^/ @2 @6
<- <- '0 <- '% v/ -> @2
v$ .  -> '$ @4 -> @4
#            5             10       13
'_ -> '$ v% <- @2 .  @7
v0 v: v1 -> @4 -> @3 ^$ .  .  .  .  @5
v0 v: '0 .  .  ^0 .  .  .  .  .  .  ^$
v0 <- <- '1 .  .  <- v% @2 .  .  .  ^$
v0 '_ <- '0 <- '% v% @6 .  .  .  .  ^$
'1 v/ -> @2 .  .  @5 .  .  .  .  .  ^$
#            5             10       13
v/ -> .  vn <- @5 'F -> 'i -> v_ .  ^$
v/ .  v_ 'o .  -> ^$ @2 .  .  @8 .  ^$
v/ v_ 'z -> 'z -> 'B -> 'u -> @9 .  ^$
v/ 'z -> 'z -> '$ .  .  .  .  .  v$ ^$
-> vb .  ve .  vh .  vk <- v/ .  v$ ^$
v/ 'c vc 'f vf 'i vi 'l vl @9 .  v$ ^$
v/ v/ .  .  .  .  .  .  <- @8 .  v$ ^$
v/ v$ -> @2 .  .  .  .  .  .  .  v$ ^$
v/ 'F -> 'i -> 'z -> 'z -> '$ .  v$ ^$
-> vd .  vi .  .  .  .  <- v/ .  v$ ^$
v/ 'e ve 'j vj .  .  .  .  @9 .  v$ ^$
v/ v/ .  .  .  .  .  .  <- @8 .  v$ ^$
v/ v$ -> @2 .  .  .  .  .  .  .  v$ ^$
v/ 'B -> 'u -> 'z -> 'z -> '$ .  v$ ^$
-> va .  vc .  vf .  vg <- v/ .  v$ ^$
v/ 'b vb 'd vd 'g vg 'h vh @9 .  v$ ^$
v/ .  .  .  .  .  .  .  <- v/ .  v$ ^$
-> vj .  vl .  vm .  'a <- v/ .  v$ ^$
v/ 'k vk 'm vm 'n vn .  <- @9 .  v$ ^$
v/ .  .  .  .  .  .  .  <- @9 .  v$ ^$
#            5             10       13
v/ .  .  v: <- @2 '+ v+ .  .  v% @8 ^$
<- v: @2 .  .  .  ^_ <- ^% @3 v% .  ^$
#            5             10       13
v% v_ <- @3 '1 .  .  .  v1 @7 .  v% ^$
v% '+ <- v0 ^$ -> @2 '0 -> ^: v_ v% ^$
v% .  '$ .  .  v$ -> ^$ @2 ^: @8 v% ^$
v% <- @2 .  @4 .  .  .  <- ^: @2 @7 ^$
v: v+ -> @3 ^_ .  .  .  @4 .  .  .  ^$
v: '_ <- v0 v: -> @2 .  ^_ .  .  .  ^$
v: .  .  v0 v+ -> @2 -> ^_ .  .  .  ^$
v: v_ .  v0 '_ <- .  ^1 ^_ -> @9 .  ^$
v: v_ .  .  v: -> @2 .  ^_ .  .  .  ^$
v: v_ .  .  v+ -> @2 -> ^_ .  .  .  ^$
v: v_ '+ v+ '_ <- .  ^0 -> @8 .  .  ^$
v: v: ^_ <- @3 '_ v_ .  .  -> ^$ @2 @8
v: .  .  .  .  ^+ <- ^% @3 .  .  .  ^+
v: .  '_ ^_ .  ^$ -> @2 .  .  .  .  ^+
v/ v+ -> @3 .  .  .  .  .  .  .  .  ^+
v/ .  .  .  ^+ 
#            5             10       13
<- v% '_ @3 '_ -> '_ v_ .  .  v$
.  '_ .  -> ^/ @2 .  -> ^$ @2 '_

入力として上限の整数を(二進表記で)指定する。以下に実行例を載せる。

>lua goog.lua fizzbuzz.og 100000
1 10 Fizz 100 Buzz Fizz 111 1000 Fizz Buzz 1011 Fizz 1101 1110 FizzBuzz 10000 10
001 Fizz 10011 Buzz Fizz 10110 10111 Fizz Buzz 11010 Fizz 11100 11101 FizzBuzz 1
1111 100000

*1:ただし Turing 機械などの抽象機械についての知識があることを前提に説明する。

*2:正確には ASCII に限らず「符号値 0〜255 の文字」が使える。

*3:命令の説明において PC の移動が明記されるものは既定の「1 つ右」は適用されない。

*4:だから、PC がソース領域の上や下に出た場合も機械は停止する。(nop しかない行に移動することになるので。)

*5:ソース上で「何もない行」をわざわざ記述する必要は生じないはずである。

*6:インタプリタデバッグ出力でも空白文字は代わりに「_」で表示される。

*7:Lua 5.1 と 5.2 版に対応している。TeX な人は texlua が使える。