«
»

[LSP42] Standard MLとOCaml

（この記事はLISP Implementation Advent Calendar 13日目のためのエントリです。）

Standard MLとOCamlでLISPを作りました。
https://github.com/zick/SMLisp
https://github.com/zick/OCamLisp

Standard MLもOCamlもML系の言語で非常に良く似ています。が、文法はちょっとずつ違っていてCommon LispとSchemeのような薫りがします。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその20〜21個目です。
私は変数に型が無い言語や、型が緩い言語が好きなんですが、そういった言語を探すのにも疲れてきたし、ついに20言語を突破するということで、思い切って型の強いStandard MLとOCamlを選びました。両方ともほとんど書いたことはありませんでしたが、片方を書けばもう片方を書くのは非常に簡単なはずという打算もありました。

Standard MLの思い出

外観

Standard MLの文法といえば、きっちりとBNFが定義されていることで有名（？）ですが、自分で書いてみるとなかなか面白いことに気付きました。

datatype obj =
    NIL
  | NUM of int
  | SYM of string
  | ERROR of string
  | CONS of ((obj ref) * (obj ref)) ref
  | SUBR of (obj -> obj) ref
  | EXPR of obj * obj * obj

fun safeCar obj =
  case obj of
       CONS(ref(ref a,  ref d)) => a
     | _ => NIL

fun safeCdr obj =
  case obj of
       CONS(ref(ref a,  ref d)) => d
     | _ => NIL

何が面白いかというと、文の区切り目となる記号がないことです。endも無ければ中括弧{}も使いません。上のプログラムだと空行で区切られているように見えますが、実際には続くトークンを見て文が続くか、別の文が始まるか区別しているわけです。文の入れ子がある場合は括弧()を付けて区別します。これはこれできれいな文法だと思うんですが謎なのが let の存在。

fun nreconc lst tail =
  case lst of
       CONS(ref(a, d)) =>
         let val tmp = !d in
           d := tail;
           nreconc tmp lst
         end
     | _ => tail

なぜか let には end が付きます。正直意味が分かりません。ちょっときれいだと思った文法が急に汚く見えてきました。誰かこの end が存在する理由を教えて下さい。

Standard MLのキーワードはfun、val、opなど短いものが多く、私好みなんですが、私はこういった名前を無意識に変数に付けてしまい、コンパイルエラーになるということが多々ありました。それは私が悪いんですが、困ったことにStandard MLのコンパイラ（Standard ML of New Jersey）のエラーメッセージが分かりにくく、必要以上に苦労した覚えがあります。

強い型

ちゃんと代数的データ型を使ってLISPの型を定義しました。本や論文などで散々見てきたんですが、実際に使って100行以上のプログラムを書くのは初めてです。特別簡単だったということもなければ、特別難しかったということもありませんでした。ただ慣れていない言語を使っているため色々と戸惑った、という感じでした。ほとんどのミスはコンパイル時に見つかり、実行時にミスが見つかることはほとんどなかった、というのは型の緩い言語とは違うところでしょうが、LISPの完成までの時間がこれにより縮まったかというとそんなことはありませんでした。慣れのほうが大事ですね。

参照型

Standard MLの変数はすべて immutable で、参照型をもつ値のみ中身を書き換えることが出来ます。今回の場合はコンスセルのcarとcdrに参照型を使えばいいんですが、上のプログラムをよく見てみると、コンスセル全体が参照型になってますし、SUBRも参照型を使っています。これはオブジェクトのアドレス比較の方法が分からず困っていたら「参照型だと間違いなくアドレス比較だろ」という悪知恵が働いてしまったためです。正しいやり方は正しい人に聞いてください。

相互再帰

型を推論する都合上か、相互再帰をする関数は and で繋ぐ必要があります。

fun printObj obj =
  case obj of
       NIL => "nil"
     | NUM n => Int.toString(n)
     | SYM s => s
     | ERROR s => ""
     | CONS _ => "(" ^ (printList obj "" "") ^ ")"
     | SUBR(_) => ""
     | EXPR(_, _, _) => ""
and printList obj delimiter acc =
  case obj of
       CONS(ref(ref a, ref d)) =>
         printList d " " (acc ^ delimiter ^ printObj a)
     | NIL => acc
     | _ => acc ^ " . " ^ printObj obj

2つの関数を and で繋ぐくらいならいいのですが、LISPのevalを愚直に実装すると、複数の関数が相互再帰をするので and が続いてなんだか見苦しい感じになります。これは何とかしたいところ。

短い！

さて、出来上がったソースコードを見てみると、ほぼちょうど300行。かなり短いです。文末の end などがなく、それによる改行がないのが効いているのではないかと思います。ML系の言語は初めて書いたので冗長なコードを書いている可能性が大いにあるため、慣れている人が書いたらより短くなる可能性があります。

OCamlの思い出

「Standard MLのコードの一部を書き換えてやれば動くんじゃないの？」という悪魔のささやきが聞こえてきましたが、聞かなかったことにして一から書きました。

外観

全体的にOCamlの方がStandard MLよりスッキリしているように見えます。

type obj =
  Nil
| Num of int
| Sym of string
| Error of string
| Cons of (obj ref) * obj ref
| Subr of (obj -> obj)
| Expr of obj * obj * obj

let safeCar obj =
  match obj with
    Cons(a, d) -> !a
  | _ -> Nil

let safeCdr obj =
  match obj with
    Cons(a, d) -> !d
  | _ -> Nil

let rec nreconc lst tail =
  match lst with
    Cons(a, d) ->
      let tmp = !d in
        d := tail;
        nreconc tmp lst
  | _ -> tail

let の終りを示す謎の end が消えました。私としてはかなり好感度が高いです。他の細かな違いも嫌いじゃないです。正直なところ、OCamlを自分で書くまでは「MLから派生しておきながら文法をちょっとずつ変えるとはけしからん。ほぼ同じにするかまったく変えるかどっちかにしろ」と思っていたんですが、OCamlを書いてみると、純粋にこっちのほうがいいな、と思いました。ごめんなさい。
Common LispとSchemeを両方書くときに生じる混乱がStandard MLとOCamlでも起きるかとおもいきや、いうほどStandard MLに慣れていなかったので案外平気でした。
あと、Standard MLのときはコンパイルエラーに頻繁に遭遇しましたが、OCamlでは大丈夫でした。ただ、これは文法の差というよりは、慣れの問題な気がします。

参照型とアドレス比較

OCaml には = と == という二種類の演算子があり、 == はアドレス比較を行ってくれるため、無駄に参照型を使うという酷い手を使わずに済みました。OCamlの参照型はStandard MLの参照型とちょっとだけ違いがあり、直接的にパターンマッチの中に書くことが出来ません。両者の safeCar と safaCdr を比べると分かるかと思います。これはOCamlのrefはコンストラクタじゃないからだとかなんだとか。代わりに { contents = x } と書けばいけるとかなんとか。詳しくは詳しい人に聞いてください。

めっちゃ短い！

完成したコードを見てみるとなんと約280行。42個の言語のなかで恐らく最短です。本当に最短かどうかは後日調べます。
Standard MLで書いた時には let の end が6回登場しているので少なくても6行は短くなるとして、他にももう少し短くなっていることのなります。OCamlを書くときには慣れてしまったので短く書けるようになったというのもあるかもしれません。詳しい違いはソースコードを読んでください。

小学生並みの感想

たまには型の強い言語を使うのもそれなりに楽しいな、と思いました。

This entry was posted on 土曜日, 12月 13th, 2014 at 12:00 AM and is filed under プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “[LSP42] Standard MLとOCaml”

  1. よんた より:
    2014年12月13日 1:31 AM

    設計者の思想はわかりませんが、例を上げておきますね。

    let in endはin-end間で括弧なしに複数expをセミコロン区切りで並べられます。
    さらにSMLでは宣言文をセミコロンで区切れます。
    なのでendが無いと以下の式のexp2の束縛先が判定できません。

    val a =
    let
    …
    in
    exp1 ; exp2

    の意味が
    val a = exp1; val it = exp2
    or
    val a = (exp1; exp2) (* exp1を評価してからval a = exp2するの意 *)
    なのか判断できません。

    OCamlは宣言の区切りがダブルセミコロン;;なので大丈夫なのかもしれません。

    ちなみに無名関数fn構文とパターンマッチcase構文は、そもそもLALRパーサでshift/reduceコンフリクトします。なぜこっちにはendをつけなかったのか、設計者を小一時間問い詰めたい。

Leave a Reply