リリカル☆Lisp開発日記

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

HaxeとF#でLISPを作りました。
https://github.com/zick/HaxeLisp
https://github.com/zick/FSharpLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその25〜26個目です。
両方とも名前を思いついたから選んだといった感じです。HaxeはNekoを使った時に、NekoVM上で動く言語として紹介されているのを見て知りました。F#は前回C#をやったから選んだといった感じです。

Haxeの思い出

代数的データ型

Haxeには代数的データ型があります。私は特に代数的データ型が好きなわけではないんですが、少し前にSMLとOCamlを使って少し慣れたので、使ってみることにしました。

enum LObj {
  Nil;
  Num(num : Int);
  Sym(name : String);
  Error(msg : String);
  Cons(cell : Cell);
  Subr(fn : LObj -> LObj);
  Expr(args : LObj, body : LObj, env : LObj);
}

パターンマッチはswitchで行います。

public static function print(obj) {
  return switch (obj) {
    case Nil: "nil";
    case Num(num): Std.string(num);
    case Sym(name): name;
    case Error(msg): "";
    case Cons(cell): printList(obj);
    case Subr(fn): "";
    case Expr(args, body, env): "";
    default: "";
  }
}

ただ、このswitch、各節にcaseと書かなければならないので、タイプ数がわりと多くなるのがあまり好きじゃありません。

型推論

Haxeは型を書かなくてもコンパイラが型推論を行ってくれるのですが、たまに型推論に失敗してエラーが出ます。

private static function skipSpaces(str: String) {
  var i = 0;
  while (i < str.length) {
    if (!isSpace(str.charAt(i))) {
      break;
    }
    i++;
  }
  return str.substring(i);
}

この skipSpaces の引数 str には型を明記しないとコンパイルエラーが出ます。

HaxeLisp.hx:169: characters 21-24 : String should be { substring : Int -> Unknown<0>, length : Int, charAt : Int -> String }
HaxeLisp.hx:169: characters 21-24 : Invalid type for field substring :
HaxeLisp.hx:169: characters 21-24 : startIndex : Int -> ?endIndex : Int -> String should be Int -> Unknown<0>
HaxeLisp.hx:169: characters 21-24 : For function argument 'str'
HaxeLisp.hx:188: characters 23-26 : String should be { substring : Int -> Unknown<0>, length : Int, charAt : Int -> String }
HaxeLisp.hx:188: characters 23-26 : Invalid type for field substring :
HaxeLisp.hx:188: characters 23-26 : startIndex : Int -> ?endIndex : Int -> String should be Int -> Unknown<0>
HaxeLisp.hx:188: characters 23-26 : For function argument 'str'

エラーメッセージを眺めた限り「strはlengthとcharAtとsubstringというメソッドを持つ」というところまでは推論できるものの「substringの型がわからない」という理由でエラーになっているように見えます。でもまあ、なぜ型推論に失敗するかを考えるより、型を書いた方が早いという最低な理由で型を書くことにしました。

F#の思い出

F#はOCamlによく似ていて、慣れている人がやれば10行もいじればOCamlで書いたLISPをF#に移植できるらしいのですが、私はF#もOCamlも慣れていないので一から書き直すことになりました。

アドレス比較

OCamlには中身の比較を行う = と アドレスの比較を行う == という2種類の演算子があります。F#にも同様のものがあるので使おうとしたら、なんと、 == が代数的データ型に使えないという悲しい事実が分かりました^(*)。
F#にはクラスもあるので、LISPのオブジェクトはクラスを使って表現することにしました。

実際には1行追加したら使えるようになったみたいだよ、お兄ちゃん！

クラス

という訳でこんなクラスを定義しました。

type LObj(tag : String) =
  member this.tag = tag
type Nil() =
  inherit LObj("nil")
type Num(n : Int32) =
  inherit LObj("num")
  member this.num = n
type Sym(s : String) =
  inherit LObj("sym")
  member this.str = s
type Error(s : String) =
  inherit LObj("error")
  member this.str = s
type Cons(a : LObj, d : LObj) =
  inherit LObj("cons")
  member val car = a with get, set
  member val cdr = d with get, set
type Subr(fn : LObj -> LObj) =
  inherit LObj("subr")
  member this.fn = fn
type Expr(args : LObj, body : LObj, env : LObj) =
  inherit LObj("expr")
  member this.args = args
  member this.body = body
  member this.env = env

なんか tag とかいうものが出てきますが、実際には使っていません。メンバのないクラスの書き方がよくわからなかったので取り敢えず書いただけです。それを除くと（私の目には）それなりにまっとうに見えます。しかし、ここからどんどん雲行きが怪しくなっていきます。

let o obj = obj :> LObj

let makeNum n = o(Num n)
let makeError s = o(Error s)
let makeCons a d = o(Cons (a, d))
let makeSubr fn = o(Subr fn)
let makeExpr args env = o(Expr (safeCar args, safeCdr args, env))

この :> という演算子はキャストです。サブクラスのまま扱われたら困るので、何をするにもベースクラスにキャストしてやらないといけないわけです。

let rec nreconc (lst : LObj) (tail : LObj) =
  match lst with
  | :? Cons as c ->
      let tmp = c.cdr in
        c.cdr <- tail;
        nreconc tmp lst
  | _ -> tail

さて、このnreconcの定義、何か変だと思いませんか？ そう。引数の型を明記しています。どうやらクラスを使うと型をうまく推論してくれないみたいです。もはやOCamlに似ている言語を使っているのだかよく分からなくなってきました。

オフサイドルール

F#の良かった点はインデントでブロックを表現するオフサイドルールを使っていることでした。個人的にはオフサイドルールはそれほど好きではないのですが、ML系言語の微妙なところ（入れ子の式には括弧を付けないといけない、まれにセミコロンを書かないといけない）といったところを避けれるのはわりとありだと思いました。

小学生並みの感想

型推論があるから型を書かなくてもいいと期待している時に型を書かされるとショックが大きかったです。

This entry was posted on 月曜日, 12月 15th, 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.