- esehara shigeo
- プログラミング言語オタク
- 近況については悲しいことがあり、飛ばします(現時点では無職です)
- プログラミングについて知るためには、実際に作ってみるのが早い
- 一番簡単な構文はLispなので、Lisp処理系を作る
- ただ、そのまま作ると余りにも重いので、一日でできるくらいミニマムな奴を考える
- できたのでUnLispと名づけた次第
- 字句解析
- 構文解析
- 意味解析
- カッコの対応関係を調べるのが面倒であること
- このような実装の方針を取っている奴はいくつかある
- 最低限ということを考えた場合、テキストからリストを作るのは余技であると判断
miniMALと、Rubyの書籍について紹介
使うともっと楽になるけれども、文字列をトークンにしなおす部分はやっておくと良さそう(字句解析の関係上)。
Ansibleというツールでは、設定ファイルをYamlで書くようになっているけれども、殆んどプログラム(処理したい内容を順番に並べて書いていく)→配列をプログラムのように扱っている→Lispでいうところの「データはコード」
現実問題として、データをどう処理するか、ということを通じてチューリング完全になってしまう典型的な例としてTeXが挙げられる。
このようにして考えた場合、「データが何であるか」という問いに意味はない。現在の著者の意見では、データに意味を与えているのは、「データをどのように処理するか」という処理系の側である。望みがあれば、Yamlも、Jsonも、同様にUnLispとして実装は可能である。(というか、そういうものはあった記憶があるので、ちゃんと調べる)
とするならば、「実装を最低限にはするが、プログラミング言語処理のトピックを拾いあげる」とする目的において、その言語における配列を使うという方法は、それなりの合理性があると考える。
愚直に考えるならば、オートマトンからはじめてもよいし、例えばYaccみたいな字句や構文を定義するツールを使ってもいい。興味ある人であるならば、PEGであったり、RAGEL、Rubyに限っていうなら、TreeTopなどがある。
ただ、大抵の言語にあるものといえば正規表現となるので、手っ取り早さを選ぶなら正規表現を利用する。
→以前にGoで書かれたLispの処理系について調べていたら、字句については正規表現で書かれていたので、それに従う(紹介を入れる)。
まず、文字列が文字列のままだと、それがいったいなんなのかが機械にはわからない。私達は「100」という文字列のパターンが出てきたら、数字だと認識し、「1ux32」と来たら「なんだかわからないが少なくとも数字ではない」と認識する。
同様に、このような分類を機械にも与える必要がある。「こういうパターンが出てきたらこういうものですよ」と定義して分類してもらう。これによって、実際に構文を解析するときに、非常に便利になる。
「900円」→「(900)(円)」「(900 => 数字) (円 => 単位)」
このように、文字の種類を先に分類しておくことで、「数字 + 円」という並びの場合には「値段」として処理をする、みたいに定義することができる。また、「円900」といったような並びについては構文としての解釈が存在しないならば、それは構文エラーとして処理できる。ただし、構文については非常に難しい問題がはらんでいる。それを後出する。
身近な例で言うと、?>←こいつもトークン
トークンの実装自体は比較的簡単だ。今回は次のような実装をしている。いろいろとヘルパーメソッドも定義されているが、重要なのは以下の通り:
module Unlisp
class Token
attr_accessor :type, :value, :env
# Token types
INTEGER = 1
# STRING = 2
ATOM = 3
LIST = 4
FUNCTION = 5
ERROR = 6
# ...
end
endポイントは、それが何なのかtypeということと、そしてパースした元の値というのはどういうものなのかvalueということだ。envに関しては、後出することにする。ただ、これに関してはあまり綺麗な実装とは呼べない。
ここで一つ疑問に当たる点として、なぜBooleanとStringが無いのか、というところだ。
まず、Unlispが実用目的ではなく、あくまで実装特化でミニマムに作りたいという基本方針があった。
これを前提にすると、まずStringは、単純に考えてもサポートするべきものが、増えてしまうという問題がある。また、Unlispにおいては、Stringのリストであるという前提である。Stringの中にStringを書くのは非常にだるい、という怠惰な理由により、これは思いきって捨てた。
ただ、この弊害としてHello, World.ができなくなってしまった。これはプログラミング言語としては非常にまずいので、putchrみたいな関数が必要だろうとは思う。
Booleanを捨てた理由は至極簡単で、真偽値自体は、Booleanという特別なクラスを用意しなくても表現はできる。
例えば典型的なところだと、C言語がそれにあたるだろうし、またPythonも0と1を実質真偽として使える。つまり、BooleanはIntegerに吸収ができる。Pythonの例を示そう:
def true_or_false(x):
if x:
print("This is True.")
else:
print("This is False.")
true_or_fales(0)
true_or_false(1)ただし、ヘルパーメソッドはあったほうがよいので、そうしている:
def integer?
type == INTEGER
end
def false?
integer? && value == 0
end
def true?
integer? && value != 0
endさて、各文字列が何を現しているのか、分類ができたところで、今度は構文について考えてみよう。
構文といったときに考える必要のある要素がいろいろある。典型的なのは結合優先問題。
sqrt 10.0 +. sqrt 10.0;;
(* - : float = 6.32455532033675905 *)
関数の結合のほうが先の為、正しく解釈される
Math.sqrt 10 + Math.sqrt 10
# SyntaxError: unexpected tINTEGER, expecting end-of-inputこの場合、Math.sqrt(10 + Math.sqrt) 10といったような、オペレータの結合優先度が高いため、エラーとなる。実際に、Math.sqrt 10 + 10だとエラーは起きない。だが、このときMath.sqrt(10 + 10)なのか、それともMath.sqrt(10) + 10なのかは判断が付かない。答えは前者。
ただし、これは例であって、実際にこういうコードを書くとリーダブルコードという本の角で思いっきり殴られる可能性は出てくる。
3 * 4 + 5 * 6
=> 42
3 * 4 + 5 * 6.
"102"
Smalltalkの場合、Integerのメソッドとしてオペレーターは定義されているので、容赦なく左に結合していく。(わかりやすく言うと(((3 * 4) + 5) * 6)に結合していく)
「人間がこのように規則を適用するのが自然である」ということを実装するのは、結構問題がある。例として考えるならば、計算式の順序としては「式 = { (式), *, / , +, - } 」という順序が作れる。計算式ならば、それほど難しくはないが、このような構文の適用順番というのは常に考えないといけなくなる。
Lispの構文の場合、先頭に関数、後者に引数ということのみ考えればいいので、上記の問題は発生しない(そういう意味では、Smalltalkの場合も同様のことが言えるかもしれない。ただ、Smalltalkの場合、オブジェクト指向という別の問題が出てくる)
hoge('fuga')
(hoge 'fuga')
になっただけ。
ここは著者の意見。
オペレータの優先順を決めることにおいてすら、そのプログラミング言語自体の設計思想において演繹されるものである。
確かに、Lispの方法は冗長過ぎるし、Smalltalkの方法はいわゆる「慣習」とは反する印象を持つ。しかし、両者はそれを捨てることによって、一貫性という強い力を得ている。
確かに、「3 * 4 + 5 * 6」を、いわば「(3 * 4) + (5 * 6)」、あるいは「(+ (* 3 4) (* 5 6))」とするのは、人間の慣習というよりは、機械への歩みよりということができる。
蛇足ではあるけれども、逆に一貫性を捨てて、現実的に作ろうとしているのがPHPという言語の印象がある。例えば、"1"というString型を、わざわざIntegerにするのはまどろっこしいという怠惰がある場合、PHPでは"1" + "1"とし、2として計算できる。これは、人間にとって「1」というのは、文字列でもあり、数字でもあるというところから考えれば、解らなくもない理屈である。
ただ、このような不用意なキャストを行うということは、逆に機械側の負担を大きくし、バグを引きよせる原因となる。最近のトピックであるタイプヒンティングや、あるいは型が厳密な言語が望まれている理由には、このあたりが関係しているといってもいいだろう。
このように見ていくと、「プログラミングされたコードをどのように解釈させるか」という部分を人間に追わせているという部分が、LispやSmalltalkの構文においては強い印象を与える。
だが、「明示的に計算順位を記述すること」と、「暗黙的に処理系が計算順位を決定して欲しい」とする問題は、一種のトレードオフと言えるわけで、後者の場合においては、人間が「その処理系の気持ちになって考える」という側面が出てきてしまう。ただ、通常使う場合においては、後者のほうが支持される傾向にありそうである。
だた、今回はそのような部分は、実装面でおいては余計なコストの割には、あまりリターンがなさそうだ、という直感的な理由によって割愛している。ただし、これを理解するのは重要なので、もし理解したい場合には、簡単に電卓を実装すると良い。
Lispの場合、このカッコの奴をformと呼ぶわけだけれども、通常のformの他に、special formというのが存在している。その典型例としてifがある。ところで、どうしてこのような区別をする必要がるのだろう。
Haskellのような言語では無い限り、関数に引数を与えた場合、引数の内容が処理されたのちに、関数にわたってくる。以下はPythonの事例である:
def my_if(predicate, true_case, false_case):
if predicate:
return true_case
else:
return false_case
def counter(n):
return my_if(n == 10, n, counter(n + 1))この場合、false_caseに渡されたcounter(n + 1)が評価され、さらにその呼び出されたcounter(n + 1)でさらに……という無限ループに陥いってしまう。そこで、これを避ける方法の一つに無名関数を使うと解決する。
def my_if(predicate, true_case, false_case):
if predicate:
return true_case
else:
return false_case()
def counter(n):
return my_if(n == 10, n, lambda: counter(n + 1))このとき、falseになって初めて関数が呼び出されるので、無限ループになることはない。実は似たような発想をしているのがSmalltalkである。
Smalltalkといってもいろいろあるので、ここではPharoという処理系に即すると、Smalltalkでは、ifもTrueあるいはFalseのクラスで定義されている。素朴にFizzBuzzを書くと次のようになる:
((1 to: 100) collect:
[ :i |
(i % 15 == 0)
ifTrue:'FizzBuzz'
ifFalse:
[(i % 5 == 0)
ifTrue: 'Buzz'
ifFalse:
[(i % 3 == 0)
ifTrue: 'Fizz'
ifFalse: i asString ]]])
do: [:i | Transcript show: i asString; cr]. ここで注目したいのは[]で囲まれた部分で、これは「ブロック」と呼ばれ、そこに入るまで、この[]の部分は評価されない。
恐らく、このトークを聞いている人にはRubyのほうがわかりやすいと思うので、Rubyでifを再実装してみることにする。
class TrueClass
def ifTrue
yield
end
def ifFalse
self
end
end
class FalseClass
def ifTrue
self
end
def ifFalse
yield
end
end
class Object
def ifTrue
self
end
def ifFalse
self
end
endコードは次のようになる。
1.upto(100).each do |n|
(n % 15 == 0)
.ifTrue { puts "FizzBuzz" }
.ifFalse {
(n % 3 == 0 )
.ifTrue { puts "Fizz"}
.ifFalse {
(n % 5 == 0)
.ifTrue { puts "Buzz" }
.ifFalse { puts n}
}
}
endもう一つ実例。Smalltalkではwhile を書くためには、次のようにする:
|i|
i:=5.
[i >0] whileTrue:[
Transcript show: ((i*2) asString) ; cr.
i:=i-1.
].ここで注目したいのは、whileはブロック節にバインドされているということである。これは、先ほどの()で括ってしまった場合、True、あるいはFalseというインスタンスに変換されてしまう。そうすると、その場で評価が定まってしまう。そうしないために、その都度評価していく必要がある。
これをRubyで再現すると、下のように書ける。
class Proc
def while(&block)
result = self[]
if result
block.call
self.while &block
end
end
end
i = 0
->(){i < 10}.while { puts i ; i += 1 }長々と書いてしまったけれども、ポイントはifなどの条件式の場合には、何らかの形で、trueやfalseだった場合の評価をあとから行なう必要が出てくるということになる。このような考慮が必要になる。
ちなみに、when節みたいなものが欲しくなる気もするのだけれども、基本的にネストさえ気にしなければ、ifだけで代用が可能なので、実装だけに特化するという意味で、whenやcond(複数の条件式)は作らないようにする。
この部分に関しては、SICPの「超循環評価器」の部分に詳しい。ここにおいて、condによる場合分けは、if式の入れ子に変換してから評価する、としている。
また、あえてこのようなメソッドが一見みあたらないSmalltalkでは、whenで重ねていくスタイルはバッドなものなのかもしれない(識者によるフィートバックが必要)
Unlispの実装コード自体はそれほど面白くないから、ここでは省くけれども、要は["if", ["<", "3", "2"], ["+", "x", "x"], ["+", "2", "2"]]というコードが入ってきた場合、評価自体は2番目のformが定まるまで保留し、trueであった場合は3番目を評価メソッドで評価し、falseである場合は、4番目を評価するといった流れになっている。このように、分岐する場合においては、処理を保留しなくてはならない。
というわけで、構文のことを長々と話したわけだけれども、実際のところ、関数が定義できないと、おもちゃとして面白くない。
従って、関数を定義できるようにするわけだけれども、Unlispにおいては、変数を定義する defと、無名関数を定義するfnしか用意していない。またfnに関しても、一引数しか使えないようになっている。
これは簡単な話で、そもそも「名前付き変数」自体が、変数に無名関数を代入したものの糖衣構文だと考えることができる。
具体的にそのような挙動をする言語を挙げるとするならば、JavaScript、Python、Scheme、OCamlとなる。例えば、SICPの「3.2 評価の環境モデル」の部分で説明されている。例えば、Schemeにおいては、以下のように定義がされる。
(define (square x) (* x x))同様に、以下でも宣言ができる。
(define square (lambda (x) (* x x)))このように考えた場合、そもそも前者のスタイルは後者の糖衣構文であるということができる。同様に、OCamlの場合:
let square = fun x -> x * xと宣言することができる。
また、このスタイルを最も多様しているのはJavaScriptでもあるだろう。
var hoo = function() { console.log("hoge") }さて、このように考えた場合、関数定義を直接行うという方針については、実際のところ、なんらかの変数に対して、無名関数を束縛するという考え方で代用が可能である。
もっと言ってしまうならば、変数に対して無名関数をオブジェクトとして代入(あるいは束縛する)ということこそが、関数宣言であると、乱暴にまとめてしまうことが可能である。
UnLispでも同様の発想として、このような方針を取っている。
n引数関数は、実際のところ、1引数関数として表すことが可能である。あるn引数関数を1引数関数として表現することをCurry化と呼ぶ。
Curry化を持ちいると、2引数関数、3引数関数……n引数関数は、1引数関数の入れ子構造になる。『論理と計算のしくみ』によれば(p192)、「関数の計算に関して純粋な理論を展開するには、関数はすべて1引数であると仮定してよいように思われる」としている。
このトークは、いわゆる純粋な理論の問題を扱っているというわけではない。だが、「n引数関数を表現するのに、1引数関数で十分である」とする知見は、仕様をミニマムにするのには十分である。
理論はわかった。では、いわゆる標準でCurry化されていないようなプログラミング言語で素朴にやってみると、次のようになるだろう。次のはJavaScriptで書く場合である:
var noncurry = function(x, y) { return x + y }
noncurry(1, 2);
var curry = function(x) { return function(y){ return x + y } }
curry(1)(2);確かにこれは冗長であるわけだけれど、ただ素朴に「実装に特化する」という意味では、利便性より、前者の「n引数関数は1引数関数であらわすことができる」という方向にフォーカスを置いている。
ちなみに、Rubyにはcurryというメソッドが用意されている。
curried = ->(x, y){ x + y }.curry
curried[1][2]プログラムには環境というのが存在している。
簡単に言ってしまえば、大域環境はグローバル、つまり何処からでも参照できる環境である。例えば、普通に関数を定義した場合、大域環境に、その関数の情報が作られる。
その一方で、関数に対して入ってくる引数を一時的に格納する変数が存在している。例えば、Pythonでいうならば:
def echo(x):
print(x)といった場合のxもまた変数ではあるのだが、しかしこのxの値は、この関数を抜けた場合には無効である必要がある。なぜならば、このxは関数の内部において、利用するために一時的に付けられている名前に過ぎないからである。とすると、大域環境とは別に、このような一時的に利用される関数の環境も用意しなければならない。これを、小域関数と呼ぶ。
例えば、その文脈について、Unlispを利用して説明すると次のようになる:
[["fn", "x", ["+", "x", "1"]], "6"]このとき、引数に6が渡さているわけだが、このとき、"6"という数字をxに適用する。すると、この段階での環境として、["+", "x", "1"]を評価するさいに、小域環境として、x = 6という、ローカルな環境が新しく作られ、それに従って評価される。
実際の環境の実装は、変数名と値(あるいは関数宣言のコード)を一緒に渡すかたちになっている。
例えば、上の関数の場合は、[["x", 6]]という形で、環境に対して入ってくる。このとき、この式が評価される場合には、"x"が入ってきたときには、環境に保存されたペアを検索し、その値を起きかえる。
実装自体は非常に簡単なものである。要は、関数呼び出しがあれば、新しい環境を渡してあげて、具体的な値が定まった場合、元のenvに差し戻すようになっている。
def call lst, env
# ...
head = lst[0]
head.env = head.env.next [head.value[0], next_val(lst)]
if head.value[1].list?
result_lst, _ = list_eval(head.value[1], head.env)
elsif head.value[1].atom?
result_lst, _ = apply_atom(head.value[1], head.value, head.env)
end
return result_lst, env
endさて、このように考えた場合、クロージャの考え方がわかりやすくなる。クロージャにおいて、その関数オブジェクトが返された小域環境をそのまま関数の中に保持する。Unlispの文脈で語ると次のようになる:
[[["fn", "x", ["fn", "y", ["+", "x", "y"]]], "2"], "3"]このとき、最初の無名関数は、「xを引数として『yを引数として、yとxの合計を足す関数』を返す関数」といえるのだが、このとき、最初の関数は、x = 2という小域環境を持つことを次の関数の前提としている。
ちょっと話を整理するならば、小域環境の中の小域環境においては、それ以前の小域環境で宣言された環境を参照できるようにしておく必要がある。
先ほどのコードに即して言うと、既に["fn", "y", ["+", "x", "y"]]の部分では、x = 2という小域関数を受けついでいるため、のちに出てくる["+", "x", "y"]では、ちゃんと["+", "x" (x = 6), "y"]として解釈できるようになっている。
このような小域環境は、関数が実行されるたびに生成される。さて、ここで小域関数は一つでいいのではないか?という疑問が出てくる。要点は、大域領域、つまりどこからでも参照できるコードと、小域領域、つまり一時的に格納される変数の部分だけ切りわけておけばいいのではないか、という疑問が出てくる。
しかし、ここでちょっと乱暴なコードを書いてみよう。
var closure = function(x) {
return (function(x){ return x + x })(3) + x
}
closure(4);このような宣言において、function内で定義されているxと、functionの中でさらに宣言されているfunctionは宣言されている文脈が違う。function内functionの中ではxは3であることが期待されると思うのだが、その前のfunction内においては、関数の引数が適用されるのが望ましいと考えるはずだ。
とするならば、小域環境を一つにしておいて、そこで仮に変数の環境を保管しておいて、変数を上書きしていくモデルについては、あまり望ましくないことがわかる(もしかしたら、そのようなモデルがあるのかもしれないけれど、具体的には知らない)。そこで小域環境については、変数と値のペアをスタックしていく方針を取っている。
ではこのような環境を上手く作るためには何をするかというと、一番てっとり早い構築方法としては、このような引数に対して変数が束縛されるたびに、変数の束縛を追加していく方法だろう。上記の場合ならば、[["x", 4], ["x", 3]]とし、新しい変数が現れるたびにスタックしていく 。そして、その環境の中で一番新しく出てくる変数(この場合ならば、最後の"x")とのペアを採用する。そして、関数から抜けるときには、そのスタックを破棄する(具体的に述べるなら、[["x", 4]]に差し戻す)。
そのようにして考えていくと、再帰関数も同様に、変数のスタックをどんどんと詰みあげていくという方針が素朴な環境の実装であると言える。
厳密に考えるならば、 evalとapplyは分けて考えたほうがよい。何度も引用しているSICPによれば、evalは引数として、式と環境を取り、そして、applyは手続きと手続きを作用させる引数のリストを取るものとしている。
ただ、今回のRubyによるプロトタイプにおいては、この分離を行なっていないため、多少泥臭いコードになっている。このあたりについては、著者も勉強不足が露呈する形になっている。
さて、ほぼUnlisp自体の話は出てこなかったけれども、おおざっぱにUnlispについての話題は紹介できたと思う。最初にも述べたように、はっきり言ってしまうならば、Unlispは全く実用性を考慮していない。あくまでプログラミング言語を実装しようとしたときに、どういうトピックがあるか、ということを語ってみたものだ。
しかし、とはいえ、これが「最低限」であるという気はあまりない。もう少し現実的かつ軽量な方法で、もっとプログラミングについて実装しながら学べる方法があるかもしれない。それらについては、今後の課題でもある。
[WIP]