読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

『アンダースタンディング・コンピュテーション』第二章を読みながら、Lispのことを考えてみる

そういえば、AmazonのWishlistから『アンダースタンディング・コンピュテーション』を頂いて、少しずつRubyで本書のコードを書いたりしていたのだけど、自分の理解を書いておいたほうがいいかなと思って、セーブがてら、自分の理解をメモしておこうと思う。

『アンダースタンディング・コンピュテーション』について

ポイントとしては、この本が基本的に「コンピューターがプログラミング言語を理解すること」というものを作る上に置いての簡略的な技術的トピックを、実際にRubyを使いながら動かしてみるということに主眼を置いていることがポイントだと思う。たぶん、そういう「何かを動かしながら理解する」という方法については、色々あると思うし、実際にそのトピックについては幅広いものがあって、それらを全て300ページで解説することは大変なことではあるし、実際、読者にとっても興味のトピックは様々あるだろうから、「そんなこと興味ないよ」ということも出てくるだろうことは間違いないと思う。

なので、本書では、それらをある程度網羅しておくことで、それらの手引きになっていていいと思う。もちろん、必要なロードマップは敷かれているんだけど、詳しすぎず、また簡略しすぎずというところがいいと思うし、何よりある程度構成として興味が持てるように組み立てていることだと思う。例えば、抽象構文木の話で、ある程度言語について勘のある人なら、「ああ、トークナイズとかその辺りの話なんだろうな」ということがわかるし、自分はそういう風に感じたりしていた (ちなみに、そのあたりについては、4章において、字句解析と構文解析の話に繋がってくる)。

第二章について

第二章の場合は、簡単な抽象構文木を扱えるための解釈機械を作ることになる。このとき、これらの抽象構文機がツリーを操作するのか、について「スモールステップ意味論」と「ビックステップ意味論」があるということを教えてくれる。実際のそれらの内容については、本書を買って読んでもらうとして、この「スモールステップ意味論」について、ちょっといじっていて面白いなと思ったのでメモしておこうと思う。

本書では、「表示的意味論」という言葉が出てくる。これを本書の言葉で直すとすると、「言語を実際の振る舞いに変えるのではなく、ある言語を別の言語に置き換える」というアプローチを取るものとして説明している。この文章で思い浮かぶことは、CoffeeScriptがJavaScriptのトランスレーターとして機能しているということだった。もちろん、CoffeeScriptの目的は、別に「新しい言語を説明すること」ではないけれど、しかしある部分においては、このような方法を利用しているのだなあと思ったりした。

で、少し思ったのは、このような「表示的意味論」、つまり「ある言語を別の言語で説明すること」というアプローチを使えば、この本書でやっていることの一部が理解できるのではないかと思ったりした。どういうことかというと、要するにこの抽象構文木を「Lisp」によって置き換えることによって、もっと具体的に、本書がやっていることとを説明できるのではないか、ということを考えたのだった(もちろん、本書にはLispの文字はあまりでてこない)。

全体のコードとしては、Gistにアップロードしているので、それを参考にしてほしい。

なぜLisp

そこで、たぶん「なんでLispなの?」という話が出てくると思う。例えば、本書では「スモールステップ意味論」の際に、「簡約(reduce)」という方法を使う。どういうことかといえば、例えば「1 + 1」は「2」に変換できるわけだけど、そういうのを連鎖して、上記の抽象構文木を圧縮していこうとする考え方である。このとき、「簡約できるもの」と「簡約できないもの」の二つに分けることができる。なので、以下のように定義することが可能になる(本書ではこのようなやり方は推奨していないことに注意してほしい)。

module BaseInspect
  def inspect
    "<<#{self}>>"
  end
end
 
module ValueInspect
  def inspect
    " value <<#{self}>> "
  end
 
end

module Reducible
  def reducible?
    true
  end

  def reduce(environment)
    if left.reducible?
      self.alias(left.reduce(environment), right)
    elsif right.reducible?
      self.alias(left, right.reduce(environment))
    else
      num(self.calc(left.value, right.value))
    end
  end
end

module Unreducible
  def reducible?
    false
  end
end

class BaseValue < Struct.new(:value)
  include Unreducible
  include ValueInspect

  def to_s
    value.to_s
  end
end

class Number < BaseValue
end

class Add < Struct.new(:left, :right)
  include BaseInspect
  include Reducible

  def to_s
    "#{left} + #{right}"
  end

  def alias(left, right)
    add(left, right)
  end

  def calc(left, right) 
    left + right
  end
end

class Multiply < Struct.new(:left, :right) 
  include BaseInspect
  include Reducible
  
  def to_s
    "#{left} * #{right}"
  end
 
  def alias(left, right)
    mul(left, right)
  end
 
  def calc(left, right)
    left * right
  end 
end

本書における抽象構文木は、そこから元の式を取り出すことが可能である。例えば、以下のような構文:

Add.new(
  Multiply.new(Number.new(1), Number.new(2))
  Multiply.new(Number.new(3), Number.new(4)))

は、1 * 2 + 3 * 4にすることが可能である。しかし、この式をそのまま扱うのには、二つの意味でちょっとした困難がある。どういうことかというと:

  • 式に変換したときに、どういう境界でreduceされるのかわからない
  • 第2章の簡略的なマシーンだと上とは違った計算式も同じような式として取り出せてしまう

この二つは、本書を一読した感想だと、どうもシームレスに繋がっているように感じる。普通、計算式といった場合に、我々は計算式に内包されているメタ的なルールを理解している。上記の例でいうならば、私たちは既に『「1 * 2」と「3 * 4」は先に計算する』ということを理解し、それを計算機に期待している。しかし、計算機自体はこのことについては、式を渡されただけでは分からない(というより、それを教えるのが大切で、このような式の優先順位を決めて解決することは、割と言語実装の初歩的な問題になっているように思う)。

従って、このようなトランスレートをする際に、下のような構文は、そのようなメタルールみたいなのを考慮してやらないと、式との行き来が出来なくなる(ようするに互換性が無くなる)。

Multiply.new(
  Number.new(1),
  Multiply.new(Add.new(Number.new(2), Number.new(3)),
  Number.new(4)))

これは、1 * ((2 + 3) * 4)の式を表しているわけだが、二章の段階では、この問題についての解決策はない。もちろん、機械としては上で動作するのだが、コードに直すときに、上記の式のメタルールをちゃんと教えてあげないといけないはずだ。

そこで、このことを、いわば関数っぽく書き換えるとわかりやすい。上の構文は、つまり下のような関数として、機械が解釈するとスムーズということは言えると思う:

+(*(1, 2), *(3, 4))

このとき、関数のカッコの内部が、その関数によってreduceされることの説明にもなっている。上の例でいうならば、「1 * 2 + 3 * 4」の+は、あくまでも1 * 23 * 4がreduceされた数値、すなわち212をさらにreduceすることを示しているわけだ。言い換えると上の式というのは

(+ (* 1 2) (* 3 4))

という風に、Lisp風にかける。このとき、Lispにおける、ある種の特徴が明確になる。すなわち:

  • reduceする範囲というのが明確である
  • 抽象構文木との行き来が比較的楽であること
  • 式における「順序」のようなものの不明確さを比較的人間によって制御できる

という形になると思う。実はもう一つ面白いことがあって、上記のような単純な計算ならば、「reduceできるもの」と「reduceできないもの」というのが明確になる。例えば、カッコに入っているものは基本的にはreduceできるものだ。すなわち(+ 1 1)という式はreduceできて、2はreduceできない。なので、

1 * 2 + 3 * 4
-> reduce -> 2 + 12
-> reduce -> 14

というよりも、

(+ (* 1 2) (* 3 4))
-> reduce -> (+ 2 12)
-> reduce -> 14

といったように、reduce過程がわかりやすくなる。そして、このような変換自体が(ただし、ちゃんと説明しておくと、これがスモールステップ意味論であるかは少し曖昧なところがある、というのは正直に述べておく)、Lispの多少なりとものわかりやすさを含んでいると言えると思う。

実際に、上のコードのto_sの部分を下のように書きなおすと:

class Number < BaseValue
end

class Add < Struct.new(:left, :right)
  def to_s
    "(+ #{left} #{right})"
  end
end

class Multiply < Struct.new(:left, :right)
  def to_s
    "(* #{left} #{right})"
  end
end

しかし、この種の「混乱」は言語にとって悪なのか?

本書では確かにLispは出てこない。もちろんもう一つの言語を持ち出すことは不用意だし、Rubyにおいて完結させるなら完結させるべきだろう。

事実、このような抽象構文木を利用したRubyへのトランスレートを書くことが、本書の一つの目的である。とはいえ、しかし上記のような「わかりやすさ」は確かに美徳ではあるものの、しかし、人は大抵「1 * 2 + 3 * 4」を、14として計算してくれるような順序を期待している。そして、それを期待して困る場面というのは、殆ど無いのではないか、ということができる。もちろん、たまには結合順序が違うために混乱を生じることはわかっているけれど、しかしそれはそういうものだとして理解すればいいだけの話なのではないか、と考えることができる。

とはいえ、こういう風に考えることによって、プログラミング言語というのはなんなのか、ということについての手がかりがつかめたような気がしている。

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで