今日のアート

f:id:nisemono_san:20160529212240j:plain

mograg garageで行われたKYOTAROさんという方が描かれた絵です。

f:id:nisemono_san:20160602080832j:plain

手帳にも描いてもらいました。ありがとうございます!!

概要

タイトルが釣りっぽくなって申しわけない(だったらやらなきゃいいじゃん……)。

普段は練習にRubyを利用しており、あるコードを規則に従ってステップを作成するプログラムを作っていたところ、とてもではないが、メンテすることが不可能になってしまった。なので、Lispの方言の一つであるところのRacketを使ったところ、サクサクと実装できるようになった。なぜこの違いが生まれてしまったのか、できるだけプログラミング言語の特性に依存せずに、この違いを語ろうと思う。

はじめに

つい最近、知人と出あったところ、『プログラミング言語の基礎概念 (ライブラリ情報学コア・テキスト)』が話題にのぼった。このテキストはオンラインによる問題集が付属しており、知人によるところだと、既に50問近く解いており、自分はといえば、30問程度で足踏みしているのが現状だった。同じ課題を共有している知人というのはありがたいもので、「じゃあ自分ももう一度やり直してみるか」というモチベーションに繋るのだが、この課題というのが凶悪だ。

ちなみに、このブログのエントリに関しては、先達であるところの『プログラミング言語の基礎概念の練習問題を解くプログラムを作った(EvalML3まで) - はこべブログ ♨』を参考にさせてもらった。このブログの自動導出システムが無ければ、とうやって解決するべきか困ったところだろう。先に感謝の念を書いておこうと思う。

初歩の段階

『プログラミング言語の基礎概念』では、「ある命題に対して規則を与えていき、前提となるような規則までステップを完成させる」といったような仕組みになっている。これは前回にも一章分を書いたのだが、例えばS(Z) plus S(S(S(Z)) is S(S(S(S(Z))))という命題を導きだしたいとしよう。このとき、与えられる規則は次のような規則となる。ちなみに細かいことを言うと、Sはペアノ自然数における後続者関数で、Zはゼロとなる。このSが増えるに従って、数が1増える、ととりあず考えるといいと思う。

# 前提
Z puls n is n by P-Zero {};

# 規則
S(n1) plus n2 is S(n) by P-Succ {
  n1 plus n2 is n (何らかの規則)
};

この二つを利用して、先ほどの命題がちゃんと規則に従ってステップを踏んで到達できることを示したい場合、下のように書ける。

S(Z) plus S(S(S(Z))) is S(S(S(S(Z)))) by P-Succ {
  Z plus S(S(S(Z))) is S(S(S(Z)))) by P-Zero {};
};

前提におけるnは任意の数が入ること示しているわけだ。そして、このような簡単な規則であるならば、簡単に解けるのだが、この本が凶悪なのは、章が進むに従って、とてもじゃないが手動でやると尋常ではない規則のステップを踏まされるような規則が出てくることにある。参考に、第5章に出てくる課題は次のようになる。

|- let sq = fun x -> x * x in sq 3 + sq 4

見てみればわかるように、この課題は、簡潔なOCaml記法によって、それがプログラム上、どのような規則に従っているのかについて導き出すところまでやるようになっている。そして、当然このような規則は複雑怪奇となっていく。

自動導出システムの作成

このような規則を手で書き下していく場合、とてもじゃないけれど、長々とした証明が必要になる。例えば、手元の自動導出システムにかけた場合、下のような規則がずらずらと出てくる。

|- let sq = (fun x -> (x * x)) in ((sq 3) + (sq 4)) evalto 25 by E-Let {
  |- fun x -> (x * x) evalto ()[fun x -> (x * x)] by E-Fun {};
     sq = ()[ fun x -> (x * x)] |- (sq 3) + (sq 4) evalto 25 by E-Plus {
     sq = ()[ fun x -> (x * x)] |- sq 3 evalto 9 by E-App {
        sq = ()[ fun x -> (x * x)] |- sq evalto ()[ fun x -> (x * x)] by E-Var1 {};
        sq = ()[ fun x -> (x * x)] |- 3 evalto 3 by E-Int {};
        x = 3 |- x * x evalto 9 by E-Times {
          x = 3 |- x evalto 3 by E-Var1 {};
          x = 3 |- x evalto 3 by E-Var1 {};
          3 times 3 is 9 by B-Times {};
        };
      };
     sq = ()[ fun x -> (x * x)] |- sq 4 evalto 16 by E-App {
       sq = ()[ fun x -> (x * x)] |- sq evalto ()[ fun x -> (x * x)] by E-Var1 {};
       sq = ()[ fun x -> (x * x)] |- 4 evalto 4 by E-Int {};
       x = 4 |- x * x evalto 16 by E-Times {
         x = 4 |- x evalto 4 by E-Var1 {};
         x = 4 |- x evalto 4 by E-Var1 {};
         4 times 4 is 16 by B-Times {};
      };
    };
    9 plus 16 is 25 by B-Plus {};
  };
};

ぱっと見たところ、これは人間の書くものではないというのが一目でわかる。なので、どういう風に自動導出システムを構築するのかについて、少し考えていた。

式から式への変換

とはいえ、単純に式をパースして、そこから抽象構文木、つまりプログラムの構造を機械にもわかりやすいように作って、そこから自動変換してしまえば非常に楽ではあるものの、この問題は一つにやるべきことが一つ増えること(つまり、構文を解釈する方法が正しいかという問題がある)と、もう一つは単純に問題を解いているという実感が無くなってしまうことである。従って、方針としては次のようになる。

あらかじめ、式に対する最低限の抽象構文木はこちらで提示する
プログラムの役目は、その抽象構文木に従って規則を導きだすことである

なにを言いたいのかといえば、先の規則を導きだすさいには、次のようなLisp Likeな構文を与えることにする(以下はシステムの構築がRubyだったころのことである)

LETIN.new("sq", 
  FUN.new("x", TIMES.new("x", "x")),
  PLUS.new(CALL.new("sq", 3), CALL.new("sq", 4))).step

このHogeClass.newを、乱暴にしてしまえば(HogeClass 1 1)となる。基本的に、Lispや他の「関数型言語と呼ばれる一群」は、この手の規則を作るのに、暴力的なほど直感的に与えることができる(過去にもそういうブログを書いた)ので、このようにクラスベースで入れていくと、わざわざオブジェクト指向である必要はあるのか、という気もするのだが、これ自体はおそらく、言語の得意・不得意の問題であって、優位性ではない。

Classベースの地獄

さて、上に書いた通り、当初はRubyで書いており、それぞれの構文に対してクラスを発行し、そこに対する規則については、オブジェクトの中で処理してもらおうという風に考えていた。既に設計ミスだと判断し、それらのコードについては素直に全部削除してしまっている。ちなみに、削除に関しては2回ほど行なっている。だからといって、これらの設計に見るべきところが無いといえば、そうではない。そこで、削除されたコードをgitから拾いだして(こういうとき、gitは便利だ)、どういうものがあるのかについて調べる。

  class ML2EBase
    def initialize(e1, e2, env)
      if env.nil?
        @env = Env.new
      else
        @env = env
      end
      @e1 = e1
      @e2 = e2
    end

    def prepare
      @e1 = varize @e1
      @e2 = varize @e2
    end

    def varize e1
      if e1.is_a?(CALL)
        if e1.env.nil?
          env = @env.clone
          e1 = e1.clone
          e1.env = env
        end
        e1 = e1.step
      elsif e1.is_a? String
        return @env.var1 e1 if @env.var1? e1
        return @env.var2 e1 if @env.var2? e1
      end
      return e1
    end

    def prepare_ml2_s e1
      if e1.is_a? Integer
        "  #{@env.ml2_s}#{e1.ml2_s} \n"
      else
        "  #{e1.ml2_s} \n"
      end
    end
  end

  # ...

  class EPLUS < ML2EBase
    def ml2_value
      prepare
      @e1.ml2_value + @e2.ml2_value
    end

    def ml2_s
      prepare
      return "#{@env.ml2_s}#{@e1.ml2_exp} + #{@e2.ml2_exp} evalto #{ml2_value} by E-Plus {\n" +
             prepare_ml2_s(@e1) +
             prepare_ml2_s(@e2) +
             "  #{@e1.ml2_value} plus #{@e2.ml2_value} is #{ml2_value} by B-Plus {};\n" +
             "};\n"
    end

    def ml2_exp
      prepare
      "#{@e1.ml2_exp} + #{@e2.ml2_exp}"
    end
  end

まず、このシステムの要件を考えた場合、少くとも「規則を表示させる」ということが考えられる。なので、まずml2_sで、規則の表示部分を作成する。また、そこから派生して「ある規則は、式としても表現できる」わけなので、それの役割としてml2_expというメソッドを使っている。また、最終的な値を取りだす必要があるので、ml2_valueというメソッドも定義されている。

ml2というプレフィックスは、この規則が「EvalML2」というところから来ている。ちなみに、全削除したコードについては、gistにて別途分けたので、もし興味がある人がいるならば参考にして欲しい。

Ruby実装による失敗の要因

Ruby実装によって何が問題だったかを列挙する。

各クラスにおいてインターフェイスがさだまっておらず、その場しのぎでポコポコとメソッドを生やしてしまったために、処理の統一性が測れなかった。
この「EvalML3」では関数定義などの問題により、スコープを別途用意するなどの方法が必要になるのだが、そのような外部依存に対して上手く対処できなかった。
基本的に監理が配列で処理されているので、オブジェクト同士が参照関係にあり、他のオブジェクトを変更すると、他のオブジェクトに変更が波及する。
無駄にクラスの種類を増やしすぎたために、関係性を把握するのが大変になった。
この式の抽象構文木自体は、はっきり言ってしまえば木構造という単純な仕組みで、その単純な仕組みに対して複雑なことをやろうとしすぎたことが敗因だった。
このような実装においては、再帰的に作りあげていくことが重要になるのだが、そのような再帰的な表現をうまく表現できなかっだ。

Racket(Lisp)による実装の成功

というわけで、Lisp(正確にはRacket)の再実装を行っていたわけだが、上の問題は、ほぼ解決した。まず当初の問題として、木構造の再帰的表現という部分に関してなのだが、これはやはりLisp及び関数型言語が得意とする部分で、これはすんなり書けるようになっていた。ただ、これに関しては、普段再帰的な処理に慣れ親しんでいる側面もあるかもしれない。汚いLispで申しわけないが、雰囲気は察してもらえると思う。

(define (valueto x env)
  (cond
    [(number? x) x]
    [(string? x)
     (let ([next-body (cadr (car (filter (lambda (y) (string=? x (car y))) env)))])
       (if (and (string? next-body) (string=? x next-body))
           (raise "Set invalid Value error.")
           (valueto next-body env)))]
    [(list? x)
     (cond [(list? (car x))
            (let* ([head (valueto (car x) env)]
                   [next-param-name (second head)]
                   [next-body (third head)]
                   [next-local-env (fourth head)])
              (if (symbol=? 'eapp (caar x)) (apply->eapp x)
               (valueto next-body (cons (list next-param-name (second x)) next-local-env))))]
           [(symbol=? 'fun (car x)) (fun->eapp x env)]
           [(symbol=? 'if (car x)) (if->value x env)]
           [else
            (let ([head (car x)]
                  [body (map (lambda (y) (valueto y env)) (cdr x))])
              (cond
                [(list? head) (valueto head env)]
                [(symbol=? '+ head) (apply + body)]
                [(symbol=? '- head) (apply - body)]
                [(symbol=? '* head) (apply * body)]
                [(symbol=? '< head) (apply < body)]
                [else (valueto-userdef x env)]))])]
     [else (raise "Do not know value")]))

ざっくりと見ればわかるかもしれないが、ところどころでvaluetoで再帰させているのがわかる。これはこの規則が最終的にIntegerかBoolean、ついでにいうとFunctionを要求するためである。この三つがvaluetoで再帰的に取得できれば、その式の最終的な値を取得することができる。

Lispが苦手な人には我慢してもらうとして、これを見るとわかるように、この表現は、値がどういうパターンになっていて、どのパターンならどういうパターンを適用するか、というルールブックというようになっている。このように、単純な規則に基づくパターンにマッチしているかを調べたければ、このような関数一つを用意すればいいということになる。

また、メソッド生やしすぎ問題については、関数で責務をまとめたために、かなりクリアとなった。最終的な値を取得するためのvalueto、規則のステップを出力するためのevalto、あるリストや値をML風に書きなおすためのany->valueなど、大局的な責務を一挙に引きうけるように設計したので、どの関数が問題になっているのか、わかりやすくなったりした。

また、環境も同様にペアとしてしているわけだけれども、基本的にその場生成なので、他のところにオブジェクトが波及して死ぬことは無くなったが、これ自体はRuby力の問題ではあるので、ちょっと問題は別かもしれない。

現状は、こんなコードとなっている。動かすとこんな感じになる。

f:id:nisemono_san:20160602081406p:plain

この実装の副作用として、Listの中でLispが動くようになってしまった。

使い方に関しては、問題をS式にすればよく、例としては:

;; x = 1 |- let sq = (fun x -> (x * x)) in ((sq 3) + (sq 4)) evalto 25

(evalto '(let "sq" (fun "x" (* "x" "x")) (+ (sq 3) (sq 4))) '(("x" 1)))

みたいな感じで表現する。

他のコードを参照する

先ほど、はこべさんのブログを参照したと書いた。で、じゃあはこべさんはどういうコードを書いているのかというのを見てみると、次のようになっていた。

class Node
  constructor: (@type, @children, @value) ->

  toString: () ->
    str = switch @type
      when 'DEFVAR'
        "#{ @children[0].value } = #{ @children[1].toString().replace(/(?:^\(|\)$)/g, '') }"
      when 'APPLY'
        "#{ @children[0].toString() } #{ @children[1].toString() }"
      when 'LET'
        "(let #{ @children[0].toString() } in #{ @children[1].toString() })"
      when 'LETREC'
        "(let rec #{ @children[0].toString() } in #{ @children[1].toString() })"
      when 'IF'
        "(if #{ @children[0].toString() } then #{ @children[1].toString() } else #{ @children[2].toString() })"
      when 'LT'
        "(#{ @children[0].toString() } < #{ @children[1].toString() })"
      when 'PLUS'
        "(#{ @children[0].toString() } + #{ @children[1].toString() })"
      when 'MINUS'
        "(#{ @children[0].toString() } - #{ @children[1].toString() })"
      when 'TIMES'
        "(#{ @children[0].toString() } * #{ @children[1].toString() })"
      when 'INT'
        "#{ @value }"
      when 'BOOL'
        "#{ @value }"
      when 'FUN'
        "(fun #{ @children[0].toString() } -> #{ @children[1].toString() })"
      when 'VAR'
        "#{ @value }"
      else
        throw "Illigal Node"

はこべさんの場合、構文解析から出発しているという違いもあるけれども、基本的にはやはりwhen節を使ってパターンを作っていくほうが望ましいということがわかる。今回のRuby実装に関しても、極力クラスを分岐させずに、パターンマッチでゴッドメソッド的に処理していって、もし必要が出てきたら、そのつどクラスに分けて分離したほうが、みとおしが良さそうだ。

まとめ

というわけで、Rubyで2回ほど破棄したコードがLispで一発で書けると「なんだ、そういうことだったのか」という喜びがあると同時に、一度Lispで書きなおすことによって、初期に書いたRubyのコード設計が如何に間違っているかに気がつけるのがとてもよかった。Rubyで2回書きなおして結局破棄したと書いたけれど、もしかしたら、その知見が地味にきいているのかもしれないが。他の言語(特にパラタイムの違う言語)に書きなおすという方法は、自分のアプローチの何処が間違っていたのかが浮きぼりになるので大変面白いし、小さいプログラムならば積極的に試すのは良いことだと思った。

『プログラミング言語の基礎概念』を読むのもいいけど、SICPの第四章はこのあたりのトピックを取りあつかっていた筈だし、any->stringみたいな、色々な型を一挙に引きうける関数についての言及もあった筈だ。何かを勉強すると、他に勉強しなければいけないことがリンクしはじめるので、大変だなあと思いながらも、楽しいなあと思うのであった。