Croud完成 - yarbの日記

クラウド・コンピューティング時代に適した、というよりもクラウドそのものを体現したプログラミング言語「Croud」を作ってみた。

クラウドそのものを利用した可読性の高い文法
草原に寝そべって空を見上げているかのような、心和むソースリスト
デフォルトでスタックを2本装備したチューリングコンプリートな設計
任意のタイミングでスタックを動的に拡張してスケールアウトが可能

Hello Worldは文字数が多くて面倒なので、以下は「Hello」を表示するコードの例。

$ cat hello.crd

()   ()  (_ )      ()     ()        (_ )
(_)  (_) (  )      (_)    (_)       ( _)

 ()    ()    (_)   ()  ()     ()  ( _)  ()  ()  (__)
(_)   (_)   (__)   (_) (_)    (_) ( _)  (_) (_) (  )

 ()  ()  ()  ()  (  )   ()   ()   ()  ()   (_)   () 
(_) (_)  (_) (_) ( _)  (_)   ( ) (_)  (_) (__)   (_)

()    ()  ( _)  () ()     (_)   ()    (_)    () 
(_)   (_) (__) (_) (_)   (__)   (_)  (__)    (_)

()    ()  ( _)  ()  ()   (_) ()   ()          () 
(_)   (_) ( _) (_)  (_) (__) (_)  ( )         ( )

()    ()   (_ ) ()    ()  (  )  ()    ()   (_)  ()
(_)   (_)  (  ) (_)   (_) (_ ) (_)   (_)  (__)  (_)

$ ./croud hello.crd
Hello$

そうでなくても腱鞘炎ぎみの手首が痛くなった。以下はフィボナッチ数列を計算する例。標準入力から受け取った数字の回数だけ数列を計算して停止する。

$ cat fib.crd

()   ()  (_ )   ()     ()    (_ )
(_)  (_) (  )   (_)    (_)   ( _)

 ()    ()    (_)   ()  ()     ()  ( _)  ()  ()  (__)
(_)   (_)   (__)   (_) (_)    (_) ( _)  (_) (_) (  )

 ()  ()  ()  ()  (  )   ()   ()   ()  ()   (_)   () 
(_) (_)  (_) (_) ( _)  (_)   ( ) (_)  (_) (__)   (_)

()    ()  ( _)  () ()     (_)   ()    (_) () 
(_)   (_) (__) (_) (_)   (__)   (_)  (__) (_)

()    ()  ( _)  ()  ()   (_) ()   ()  () 
(_)   (_) ( _) (_)  (_) (__) (_)  ( ) ( )

()    ()   (_ ) ()    ()  (  )  ()    ()   (_)  ()
(_)   (_)  (  ) (_)   (_) (_ ) (_)   (_)  (__)  (_)

$ ./croud fib.crd
20
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
$

使うモコモコは5種類。

 ()
 (_)  1 
 
 ()
 ( )  2 
 
  ()
 (_)  3 
 
 (_)
 (__) 4 
 
  (_)
 (__) 5

用意されている命令セットとモコモコの対応は、

OPNUM = {11 => :push, 12 => :drop, 13 => :dup, 14 => :swap,
  21 => :roll, 22 => :swit, 23 => :rot, 24 => :slide, 25 => :exp,
  31 => :add, 32 => :sub, 33 => :mul, 34 => :div,
  41 => :setl, 42 => :jmpl, 43 => :zjmpl, 44 => :nzjmpl,
  51 => :puts, 52 => :gets, 53 => :putnum, 54 => :getnum}

という感じ。Whitespaceを真似して作ったけどヒープはない。代わりにスタックを2本にし、スタック操作の命令も多めにしてみた。制御関係は単純なジャンプとゼロ判定のジャンプが2つだけ。入出力は数値と文字が1つずつ扱える。

Croudは、去年暮れに出版されて一部で話題となった「Rubyで作る奇妙なプログラミング言語」にあったWhitespaceの実装を参考にして演習として作ってみたもので、いろいろと勉強になった。何事も自分でやるとよく分かる。CommonLispやJavaの入門書をあわせて読みつつ、だいたい次のようなことが分かった。

Rubyのライブラリの一般的なファイル配置やインクルードの関係。
実は今まで謎だった、先頭からmodule宣言に囲まれたライブラリの意味。コロンコロン表記もちゃんと分かっていなかった。
strscanライブラリの使い方。こうした機構は実はスキャナという一般名称で多くの言語で用意されているらしいことをJavaの入門書を読みつつ微かに理解した。確かにこれはよくある処理で、ずっと昔「しゃくとり虫法」という呼び名をつけてPerlで実践していたことがある。
newメソッドではなくクラスメソッドを使った間接的なコンストラクタの呼び出し。newでオブジェクトを作って、それから何かの処理ためにオブジェクトにメッセージを送るという白々しい儀式を飛ばせる。
例外処理の重要性。しかし、遊びのプログラミングで、そんなものを几帳面に書くのは面倒すぎる。
スタックを2本も用意すれば、実はチューリングマシンと等価になるということ。つまり、Croudは真にスケーラブ（ry
逆にスタック1本だけでは、スタック操作命令を少し増やしたぐらいではどう頑張ってもフィボナッチ数列すら処理の停止条件が書けないこと。
スタックだヒープだテープだとかいうのはそれほど本質ではなくて、これらとまったく違うラムダ計算に基づいた処理系というものがあって、それは「計算とはベータ変換のこと」という謎めいた呪文に彩られているらしいこと。
謎めきつつもベータ変換は単純な記号処理っぽいので、自分で手を動かして計算すればYコンビネータの意味ぐらいはぼくにも分かるんじゃないかということ。
つまりGrassはイカしてるってこと。
この辺のことはオートマトンとかアブストラクトマシンがキーワードらしく、やっぱり体系立った勉強をしないと理解できないらしいこと。
オートマトンを理解することとプログラミングスキルは直接関係しそうもないこと。
予約語を2行にまたがるようにすると、やたら処理が面倒なこと。単純に1行目と2行目をzipすれば、何とでもなると思ったけど、まあ面倒くさい。
予約語を2行にまたがるようにすると、やたらプログラミングが面倒なこと。しかし、慣れてくると1行目をずらずら書いてから改行して、その後に2行目を書けるようになるらしい。
エソテリック系言語としては、命令セットを絞るか、トークンを絞るかしないとそれっぽくないということ。

ともあれ、以下、Croudのファイル構成とコード。

$ ls -lR
.:
合計 0
drwxr-xr-x 2 yarb yarb  72 2009-02-09 11:00 bin
drwxr-xr-x 2 yarb yarb 160 2009-02-10 00:20 example
drwxr-xr-x 3 yarb yarb  96 2009-02-09 22:44 lib

./bin:
合計 4
-rwxr-xr-x 1 yarb yarb 127 2009-02-09 11:00 croud

./example:
合計 16
-rw-r--r-- 1 yarb yarb 329 2009-02-09 23:36 fib.crd
-rw-r--r-- 1 yarb yarb 576 2009-02-10 00:20 hello.crd

./lib:
合計 4
drwxr-xr-x 2 yarb yarb 152 2009-02-09 23:14 croud
-rw-r--r-- 1 yarb yarb 212 2009-02-09 22:44 croud.rb

./lib/croud:
合計 16
-rw-r--r-- 1 yarb yarb 1387 2009-02-09 10:57 compiler.rb
-rw-r--r-- 1 yarb yarb 2386 2009-02-09 23:14 parse.rb
-rw-r--r-- 1 yarb yarb  443 2009-02-09 10:57 stack.rb
-rw-r--r-- 1 yarb yarb 1779 2009-02-09 11:05 vm.rb

(bin/croud)

#!/usr/bin/ruby
$LOAD_PATH.unshift File.expand_path("../lib", File.dirname(__FILE__))
require 'croud.rb'

Croud.run(ARGF.read)

(lib/croud.rb)

require 'croud/parse'
require 'croud/compiler'
require 'croud/vm'

module Croud
  
  def self.run(src)
    asm = Croud::Parse.parse(src)
    inst = Croud::Compiler.compile(asm)
    Croud::VM.run(inst)
  end

end

(lib/stack.rb)

module Croud

  class Stack
    
    def initialize(n=2)
      @stc = []
      n.times do
        @stc << []
      end
      @cur = 0
    end
    
    def stc
      @stc[@cur]
    end
    
    def switch
      @stc[@cur], @stc[@cur + 1] = @stc[@cur + 1], @stc[@cur]
    end

    def expand
      @stc << []
    end
    
    def slide
      @stc[@cur + 1] << @stc[@cur].pop
    end

    def rotate
      @stc << @stc.shift
    end

  end

end

(lib/parse.rb)

require "strscan"

SYMS = {" " => 0, "(" => 1, ")" => 2, "_" => 3}

CLOUD_SHAPE = {"5b2" => "1", "582" => "2", "17a" => "3",
  "5fb2" => "4", "17fa" => "5"}

OPNUM = {11 => :push, 12 => :drop, 13 => :dup, 14 => :swap,
  21 => :roll, 22 => :swit, 23 => :rot, 24 => :slide, 25 => :exp,
  31 => :add, 32 => :sub, 33 => :mul, 34 => :div,
  41 => :setl, 42 => :jmpl, 43 => :zjmpl, 44 => :nzjmpl,
  51 => :puts, 52 => :gets, 53 => :putnum, 54 => :getnum}

module Croud
  class Parse

    def self.parse(src)
      new(src).parse
    end

    def initialize(src)
      @src = src.split(/\n/)
      @asm = ""
    end

    def parse
      nums = inst = ""
      
      while line = @src.shift
        next if line !~ /[\(\) _]/
        nums += lpair2num(line, @src.shift)
      end
      s = StringScanner.new(nums)
      while cld = s.scan(/0*([15][^2a]+[2a])/)  # each cloud
        if cld =~ /5(..)a/ # numeric literal
          inst += cld2num($1).to_s(16)
        else
          cld.delete!("0")
          inst += CLOUD_SHAPE[cld].to_s
        end
      end

      s = StringScanner.new(inst)
      while op = s.scan(/\d\d/)
        @asm += OPNUM[op.to_i].to_s
        if (op == "11") || (op == "41") || (op == "42") || (op == "43") || (op == "44") 
          n = s.scan(/[0-9a-f]/)
          @asm += ","
          @asm += n
        end
        @asm += "\n"
      end
      @asm
    end

    def lpair2num(*lines)
      ul,dl = *lines
      nums = ""
      
      ul.split(//).zip(dl.split(//)).each do |pair|
        nums += pair2num(*pair)
      end
      nums
    end

    def pair2num(*pair)
      u,d = *pair
      
      if (u =~ /[ \(\)_]/) && (u =~ /[ \(\)_]/)
        num = SYMS[u] * 4 + SYMS[d]
      else
        raise "parse error"
      end
      num.to_s(16)
    end

    def cld2num(s)
      s.gsub("0","00").gsub("c","10").gsub("3","01").gsub("f","11").to_i(2)
    end
  end
end

if $0 == __FILE__
#  puts Croud::Parse.parse(ARGF.read)
  src = <<EOS
()  ()  ( _) ()  ()  (__)  ()  ()  (_)  () 
(_) (_) (__) (_) (_) (  ) (_) (_) (__)  (_)
EOS
  puts Croud::Parse.parse(src)
end

=begin
Some rules:

 (
 ( = (( = 1 *4 + 1 = 5

 )
 _ = )_ = 2 * 4 + 3 = 11 = 0xb

 Therefore,

 ()
 (_)  1 :5b2
 
 ()
 ( )  2 :582
 
  ()
 (_)  3 :17a
 
 (_)
 (__) 4 :5fb2
 
  (_)
 (__) 5 :17fa

 Numerics

 ( _)
 (_ )  :53ca  -> 3c -> 01,10 -> 0x6

 ( _)
 (  )  :50ca -> 0c > 0,10 -> 0x3
=end

(lib/compiler.rb)

module Croud

  class Compiler

    def self.compile(asm)
      new(asm).compile
    end

    def initialize(asm)
      @asm = asm
      @inst = []
    end

    def compile
      @asm.split(/\n/).each do |line|
        op,num = line.split(/,/)
        case op
        when "push"   then @inst << :push << num.to_i(16)
        when "drop"   then @inst << :drop
        when "dup"    then @inst << :dup
        when "swap"   then @inst << :swap

        when "roll"   then @inst << :roll
        when "swit"   then @inst << :swit
        when "rot"    then @inst << :rot
        when "slide"  then @inst << :slide
        when "exp"    then @inst << :exp

        when "add"    then @inst << :add
        when "sub"    then @inst << :sub
        when "mul"    then @inst << :mul
        when "div"    then @inst << :div

        when "setl"   then @inst << :setl << num.to_i(16)
        when "jmpl"   then @inst << :jmpl << num.to_i(16)
        when "zjmpl"  then @inst << :zjmpl << num.to_i(16)
        when "nzjmpl" then @inst << :nzjmpl << num.to_i(16)

        when "puts"   then @inst << :puts
        when "putnum" then @inst << :putnum
        when "gets"   then @inst << :gets
        when "getnum" then @inst << :getnum

        end
      end
      @inst
    end
  end

end

if $0 == __FILE__
  asm = <<EOS
push,a
puts
setl,1
rot
exp
swit
EOS
  p Croud::Compiler.compile(asm)
end

(lib/vm.rb)

require 'croud/stack'

module Croud

  class VM

    def self.run(inst)
      new(inst).run
    end

    def initialize(inst)
      @inst = inst
      @label = {}
    end

    def mk_jump_table
      @inst.each_with_index do |op, i|
        @label[@inst[i + 1]] = i if op == :setl
      end
    end

    def run
      self.mk_jump_table
      pc = 0
      s = Croud::Stack.new
      while pc < @inst.size
        op = @inst[pc]

        case op
        when :push
          pc += 1
          num = @inst[pc]
          s.stc << num
        when :drop
          s.stc.pop
        when :dup
          s.stc << s.stc.last
        when :swap
          x, y = s.stc.pop, s.stc.pop
          s.stc << x << y
        when :roll
          s.stc << s.stc.delete_at(-3)
        when :swit
          s.switch
        when :rot
          s.rotate
        when :slide
          s.slide
        when :exp
          s.expand
        when :add
          s.stc << s.stc.pop + s.stc.pop
        when :sub
          y, x = s.stc.pop, s.stc.pop
          s.stc << x - y
        when :mul
          s.stc << s.stc.pop * s.stc.pop
        when :div
          y, x = s.stc.pop, s.stc.pop
          s.stc << x / y
        when :jmpl
          pc = @label[@inst[pc + 1]]
        when :zjmpl
          pc = @label[@inst[pc + 1]] if s.stc.last == 0
        when :nzjmpl
          pc = @label[@inst[pc + 1]] if s.stc.last != 0
        when :puts
          print s.stc.last.chr
        when :gets
          s.stc << $stdin.gets.chomp!
        when :putnum
          print s.stc.last
          puts
        when :getnum
          s.stc << $stdin.gets.chomp!.to_i
        end
        pc += 1
      end
    end
  end
end

if $0 == __FILE__
  Croud::VM.run([:push,72,:push,73,:swap,:puts,:drop,:puts])
  puts
end