Archive for the ‘プログラミング’ Category

[LSP42] Eiffel

木曜日, 12月 18th, 2014

(この記事はLISP Implementation Advent Calendar 18日目のためのエントリです。)

EiffelでLISPを作りました。
https://github.com/zick/EiffeLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその31個目です。
Eiffelは名前を知っているので選んだという感じです。Eiffelのことはほとんど知りませんでしたが、スクリプト言語のように気軽に書けるものではないと考えていたのでずっと後回しにしてきました。しかし、実装に使った言語がいよいよ30を突破して、言語を選ぶのが非常に難しくなってきたので名前を知ってる言語はなんでも使ってしまおうと思いました。

外観

まずはこのプログラムをご覧ください。

class CONS

inherit
  LOBJ

create
  make_cons

feature
  car: LOBJ assign set_car
  cdr: LOBJ assign set_cdr

  set_car(x: LOBJ)
    do
      car := x
    end

  set_cdr(x: LOBJ)
    do
      cdr := x
    end

  make_cons(a: LOBJ; d: LOBJ)
    do
      car := a
      cdr := d
    end

end

「あ、この文法、教科書で見たやつだ!」と私は思いました。なんというか、ドキュメントをそのままプログラムにしたような感じといいますか、簡潔に言うと「古臭い」です。クラス名がすべて大文字なのも古臭くていい感じです。

オブジェクト指向

Eiffelはずばり、
「俺はオブジェクト指向言語だ! プログラムを書きたかったらまずクラスを作れ! クラスを作るたびにファイルを作れ! ヒャッハー!!!」
が完全に当てはまってしまいました。上記 CONS クラスのために新たなファイルを作る必要がありますし、 CONS のベースクラスである LOBJ クラスのためにも新たなファイルを作る必要があります。

class LOBJ
end

この2行だけで1つのファイルです。正直どうかと思います。でも、この文法とは妙にマッチしているような気もしました。

Void-safety

まずは次のプログラムをごらんください。

  nreverse(l: LOBJ): LOBJ
    local
      lst: LOBJ
      tmp: LOBJ
    do
      Result := kNil
      from
        lst := l
      until
        lst = kNil
      loop
        if attached {CONS} lst as c then
          tmp := c.cdr
          c.cdr := Result
          Result := lst
          lst := tmp
        else
          lst := kNil  -- break
        end
      end
    end

「うわっ、この文法、パパの枕の臭いがする!」という話ではなく、見るべくは if attached {CONS} lst as c then のところです。型がCONSか確認しているのですが、同時に Void (他の言語で言うNULL) でないことも確認しています。Eiffelは値がVoidになり得るかどうかをコンパイル時に確認しており、Voidの可能性がある場合にチェックなしで中身にアクセスしようとするとコンパイルエラーになります。見た目はともかくよく出来てます。
ちなみに、この attached は昔のEiffelには無かったようで、古い資料には載っていません。具体的には日本語版Wikipediaとそのリンク先。資料のとおりに書いたのにコンパイルエラーになったときは非常に悲しかったです。

コンパイル時の型チェック

上のVoid-safetyの話からも分かる通り、Eiffelはコンパイル時に色々なチェックをします。未初期化の変数の使用もちゃんと関数を超えてチェックします。ただ、配列の境界などはチェックしてくれません。「そのためには依存型を云々……」などという難しい話ではなく、配列の index が1-originなのにリテラルの 0 を書いてもコンパイルエラーにならないのはちょっと。

TUPLE

Eiffelにはタプルがあって、["ABC", 123] と書くと TUPLE [STRING, INTEGER] という型になるようです。しかし、タプルから要素を取り出す item という関数の型は問答無用で ANY (すべてのベースとなる型) になります。型はどうした。マニュアルでTUPLEを調べてみると integer_item とか boolean_item という関数があり、それぞれ INTEGER, BOOLEAN を返すようです。正直意味が分かりません。なんなんだ、これ。

契約

Eiffelといえば契約による設計ですね。(私を含め)Eiffelがどんな言語なのかほとんど知らない人も「Eiffelといえば契約による設計」と呪文のように覚えている人は多いのではないでしょうか。しかし、私にとっての目的は「なるべく早く42個の言語でLISPを実装する」ことだけなので、LISPを作るのに不要な機能は積極的にスルーしたので、契約による設計を意識することは一切ありませんでした。マニュアルを読んでる時に invariant とか ensure とか書いてるあたりがきっとそうなんだろうなーと思ったり、それっぽいコンパイルエラーをみって、きっとこれがそうなんだろうと思いつつ全てスルーしました。

小学生並みの感想

もっと勉強しないといけないと思いました。

[LSP42] LiveScript

水曜日, 12月 17th, 2014

(この記事はLISP Implementation Advent Calendar 17日目のためのエントリです。)

LiveScriptでLISPを作りました。
https://github.com/zick/LiveLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその30個目です。
JavaScript系の言語(*)はだいたいやり尽くしたと思っていたのですが、調べてみたらLiveScriptという言語がまだ残っているのに気づいたのので使うことにしました。

(*) ここでは、JavaScriptに変換できたりJavaScriptの代わりに使えるような言語のことだよ、お兄ちゃん!

禁断の項目

LiveScriptのマニュアルを上から順に読んで、そろそろLISPを作るのに十分な知識が得られたかなと思ったところで、マニュアルにCoffeeScript to LiveScript Conversion Guideという項目があることに気付きました。

これだけ

CoffeeScriptで書いたLISPを、LiveScriptとして動かしてみたら、途中まで動いてエラーを吐いて止まりました。エラーメッセジを見て修正、というのを3回ほどしたら完全に動いてしまいました。

% cat lisp.coffee \
| sed -e 's/str\[\([^.]*\)\.\.\.\]/str\.substring\(\1\)/g' \
| sed -e 's/str\[\.\.\.\([^]]*\)\]/str\.substring\(0, \1\)/g'  \
| sed -e 's/\.\.\./ til /g' > livelisp.ls

CoffeeScriptの [from...end] というrangeの構文を [from til end] に変えたのと、CoffeeScriptで部分文字列の取得にrangeの構文を使っていたのをsubstringというメソッドを呼ぶように変えただけです。

小学生並みの感想

これは酷いと思いました。

[LSP42] KotlinとJuliaとScala

火曜日, 12月 16th, 2014

(この記事はLISP Implementation Advent Calendar 16日目のためのエントリです。)

KotlinJuliaScalaでLISPを作りました。
https://github.com/zick/KotlinLisp
https://github.com/zick/JuliaLisp
https://github.com/zick/ScalaLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその27〜29個目です。
Kotlinは例によって「JVMで動く(Java以外の)言語は(それなりの確率で)簡潔で簡単なはず」という私の脳内で成り立つ法則に基いて選びました。
JuliaはWikipediaを眺めている時に見つけて簡単そうだったので選んだような記憶があります。
Scalaも「JVMで(以下略)」で選びました。

Kotlinの思い出

I・D・E!! I・D・E!!

マニュアルを読みながらKotlinの処理系をインストールしていると「次にIDEの設定をします」という説明が出てきました。数百行のプログラムを書くだけなのでIDEは使わなくていいや、と思ったものの、いくら探してもコマンドラインからKotlinを使う方法が見つかりませんでした。色々と検索してもなかなか見つからず、かなり時間を書けて頑張った末にコマンドラインからの実行方法が分かりました。

% kotlinc-jvm -src kotlinlisp.kt -jar lisp.jar -includeRuntime && java -cp lisp.jar lisp.LispPackage

IDEが使えることは素晴らしいことだとは思いますが、マニュアルには是非ともIDE以外からの使い方も載せて欲しいです。

外観

今どきっぽい感じで嫌いじゃありません。トップレベルに関数が定義できるのも良いです。

class Nil {
}
val kNil = Nil()

class Cons(a : Any, d : Any) {
  var car = a
  var cdr = d
}

fun nreverse(l : Any) : Any {
  var lst = l
  var ret : Any = kNil
  while (true) {
    val elm = lst
    if (elm is Cons) {
      val tmp = elm.cdr
      elm.cdr = ret
      ret = lst
      lst = tmp
    } else {
      break
    }
  }
  return ret
}

型をそれなりに書かないといけないのは少々面倒ですが、某言語の function 名前(引数) : 型 という非常に冗長な構文を見た後だと、fun の3文字が非常に短く見えて幸せな感じです。

エラーメッセージ

Kotlinのコンパイラのエラーメッセージは一昔前のC++コンパイラ並にくどいです。例えば上のプログラムの Cons のコンストラクタの引数の型を省略してみると、次のようなエラーが出ます。

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (42, 13) Parameters must have type annotation
ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (42, 16) Parameters must have type annotation
ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (231, 26) Overload resolution ambiguity:
internal final var car: [ERROR : Type annotation was missing] defined in lisp.Cons
internal open var : [ERROR : ] defined in root package

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (232, 23) Overload resolution ambiguity:
internal final var car: [ERROR : Type annotation was missing] defined in lisp.Cons
internal open var : [ERROR : ] defined in root package

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (234, 22) Overload resolution ambiguity:
internal final var cdr: [ERROR : Type annotation was missing] defined in lisp.Cons
internal open var : [ERROR : ] defined in root package

ERROR: /Users/zick/prog/lsp42/kotlinlisp/kotlinlisp.kt: (397, 27) Overload resolution ambiguity:
internal final val data: jet.Int defined in lisp.Num
internal open var : [ERROR : ] defined in root package

exec() finished with COMPILATION_ERROR return code

長い。長すぎる。いくらなんでも長過ぎる。一番上の行を見れば「パラメータにタイプアノテーションをつけろ」と言ってるので何を間違えたかは明らかなんですが、なにもこんなに長いエラーメッセージを出さなくていいじゃないですか。

Juliaの思い出

外観

Juliaは変数や関数に型を書きません。私にとって大事なのはその一点です。

type Cons
  car
  cdr
end

function nreverse(lst)
  ret = kNil
  while isa(lst, Cons)
    tmp = lst.cdr
    lst.cdr = ret
    ret = lst
    lst = tmp
  end
  ret
end

function pairlis(lst1, lst2)
  ret = kNil
  while isa(lst1, Cons) && isa(lst2, Cons)
    ret = Cons(Cons(lst1.car, lst2.car), ret)
    lst1 = lst1.cdr
    lst2 = lst2.cdr
  end
  nreverse(ret)
end

このところ型を書く必要がある言語がずっと続いていたので型を書かない言語の素晴らしさを改めて再発見しました。型を書く必要がないという事実を前にしたら、あまり好きでないbegin/endの構文も、冗長なキーワードfunctionも大した問題ではありません。もう最高。とにかく最高。素晴らしい。

多分良い言語です

マニュアルを流し読みしたところ、Juliaはかなりいい言語のように見えました。ただ、あまりにも気軽かけるので1時間ちょっとでLISPが完成してしまったためあれこれ試す間もなく終わってしまったのが残念です。

Scalaの思い出

Scalaは実のところ使うのを避けていたんですよ。というのも、それなりに有名でカッコよく使っている人が多い言語なので、不勉強な状態でカッコ悪いLISPを書くのも嫌じゃないですか。LISPなのに。でも名前が思い浮かぶ言語がどんどん減ってきたので仕方なく使うことに。

外観

Scalaはそれなりに型を書かなければなりません。でも、型推論のおかげでかなりの箇所で型を省略できます。

def nreverse(lst: LObj) = {
  def doit(lst: LObj, ret: LObj): LObj = {
    lst match {
      case Cons(c) => {
        val tmp = c.cdr
        c.cdr = ret
        doit(tmp, lst)
      }
      case _ => ret
    }
  }
  doit(lst, kNil)
}

関数型言語らしく末尾再帰の形で書いています。これは趣味の問題ではなく、Scalaにはwhileというループ用の構文があるものの、いわゆるbreak相当のものがないので、ちょっと凝ったループをしようと思った場合は末尾再帰を使わないとかえって難しくなります。

case class

Scalaにはcase classというものがあり、これを使うとpretty printerが作られたり、型のパターンマッチができるようになったり、色々と便利なメソッドが自動で定義されるようです。こりゃ使わざるを得ないな、と思ったら、自動で比較関数まで作ってくれるらしく、これが内容比較なので、アドレス比較をしたい私にとっては邪魔でしかありません。そこで、case classのフィールドに直接値を入れるのではなく、フィールドにclass instanceを入れることで実質的にアドレス比較を行うようにしました。

abstract class LObj

class Nil0 {
}

class Cons0(a: LObj, d: LObj) {
  var car = a
  var cdr = d
}

case class Nil(obj: Nil0) extends LObj
val kNil = Nil(new Nil0)

case class Cons(obj: Cons0) extends LObj
def makeCons(a: LObj, d: LObj) = Cons(new Cons0(a, d))

このやり方が普通なのか異常なのかは知りませんが、少なくても今回に限ってはそれなりにうまくいきました。行数が増えるという問題を除いては。

再帰と相互再帰

OCamlは再帰をする関数を定義するときには rec というキーワードを付けました。Scalaはといいますと、再帰をする関数は戻り値の型を明記します。上のnreverseの内部で定義してあるdoitがそうなってますね。

さて、相互再帰の場合はStandard MLとOCamlは型推論の都合上、相互再帰をする関数を and で繋ぐ必要がありました。Scalaは通常の再帰と同様に戻り値の型を明記します。

def printObj(obj: LObj): String = {
  obj match {
    case Nil(_) => "nil"
    case Num(n) => n.data.toString
    case Sym(s) => s.data
    case Error(e) => ""
    case Cons(_) => printList(obj)
    case Subr(_) => ""
    case Expr(_) => ""
  }
}

def printList(obj: LObj): String = {
  def doit(obj: LObj, first: Boolean, ret: String): String = {
    obj match {
      case Cons(c) =>
        doit(c.cdr, false, ret + (if (first) "" else " ") + printObj(c.car))
      case Nil(_) => "(" + ret + ")"
      case _ => "(" + ret + " . " + printObj(obj) + ")"
    }
  }
  doit(obj, true, "")
}

複数の関数を and で繋ぐよりはこっちのほうが個人的に好きです。

小学生並みの感想

やはり簡単に書ける言語は素晴らしいと思います。

[LSP42] HaxeとF#

月曜日, 12月 15th, 2014

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

HaxeF#で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系言語の微妙なところ(入れ子の式には括弧を付けないといけない、まれにセミコロンを書かないといけない)といったところを避けれるのはわりとありだと思いました。

小学生並みの感想

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

[LSP42] DとJavaとC#

日曜日, 12月 14th, 2014

(この記事はLISP Implementation Advent Calendar 14日目のためのエントリです。)

DJavaC#でLISPを作りました。
https://github.com/zick/DLisp
https://github.com/zick/JavaLisp
https://github.com/zick/CSharpLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその22〜24個目です。
JavaとC#は明らかにメジャーな言語ですし、Dは少なくても名前は知っている人は多いでしょう。こういった言語を使ってもあまり喜ぶ人も少ないのですが、42個のうち半分を超えたのでいまのうちにこっそり使っておこうという発想で選びました。42個目の言語がJavaだったりするとあまりにも残念な感じになってしまいますから。

Dの思い出

Dはまったく見たことも書いたこともなかったのですが、Cを知ってたらほとんど新しいことを勉強しなくても書けてしまいました。コンパイラのエラーメッセージも読みやすいので楽ちんです。

外観

だいたいCみたいな感じです。

LObj nreverse(LObj lst) {
  LObj ret = kNil;
  while (lst.tag == Type.Cons) {
    LObj tmp = lst.data.cons.cdr;
    lst.data.cons.cdr = ret;
    ret = lst;
    lst = tmp;
  }
  return ret;
}

便利な機能を使う時以外はCと思って書けば書けます。私にとっては非常に楽でした。

データ構造

例によってクラスを1つだけ作るというインチキを使いました。

enum Type {
  Nil, Num, Sym, Error, Cons, Subr, Expr
}

class LObj {
  struct Cons {
    LObj car;
    LObj cdr;
  }
  ...
  union Data {
    int num;
    string str;
    Cons cons;
    Expr expr;
    Subr subr;
  }

  this(Type type) {
    tag = type;
  }
  ...
  this(Type type, LObj a, LObj d) {
    tag = type;
    data.cons.car = a;
    data.cons.cdr = d;
  }
  ...

  Type tag;
  Data data;
}

今回はtagにenumを使っているので、少なくても文字列よりは間違いが起きないでしょう。Fantomのような名前付きコンストラクタはないので、コンストラクタの第一引数にはtagを付けるようにしました。あとは特筆すべき点はないかと思います。

SUBR

まるでCの関数ポインタのようなことができるのでSUBRも楽に作れます。

LObj subrCons(LObj args) {
  return makeCons(safeCar(args), safeCar(safeCdr(args)));
}
...
addToEnv(makeSym("cons"), new LObj(Type.Subr, &subrCons), g_env);

ただ、「クロージャのポインタを取得するには delegate を使って云々……」みたいなことがマニュアルに書いてあったのですが、面倒そうなのでクロージャは使わないという方向で逃げました。

Javaの思い出

Javaは一応書いたことはあるのですが、Javaアプレットやiアプリ、それをMIDP用に書き直したもの、などの簡単なゲームをちょっと書いたことがある程度です。特にiアプリではメモリや速度の関係で「staticおじさん」にならざるを得ない感じでしたし、それどころか else を削ることでバイトコードを節約するなど、通常のJavaとは違う何かを書いただけのような気もします。あと、大学生に「iアプリって何ですか」と先日言われたのがなんだかショックで仕方ありません。

外観

Dと比べると冗長な感じがします。

public static LObj nreverse(LObj lst) {
    LObj ret = kNil;
    while (lst.tag() == Type.CONS) {
        LObj tmp = lst.cons().cdr;
        lst.cons().cdr = ret;
        ret = lst;
        lst = tmp;
    }
    return ret;
}

さっそくstaticおじさんになっております。

データ構造

クラスを1つしか作らないのはDのときと同じですが、Javaには共用体がありません。

enum Type {
    NIL, NUM, SYM, ERROR, CONS, SUBR, EXPR,
}

class LObj {
    public Type tag() { return tag_; }
    public LObj(Type type, Object obj) {
        tag_ = type;
        data_ = obj;
    }
    public Integer num() {
        return (Integer)data_;
    }
    ...
    public Cons cons() {
        return (Cons)data_;
    }

    ...

    private Type tag_;
    private Object data_;
}

class Cons {
    public Cons(LObj a, LObj d) {
        car = a;
        cdr = d;
    }
    public LObj car;
    public LObj cdr;
}

しかし、 Object というすべてのベースとなるクラスがあるので、キャストするだけです。型安全とか知りません。

SUBR

ちらっと人のコードを見たところ、Javaはインスタンスを作るときにクラスの一部分をオーバライドできるらしいじゃないですか。気になったのでこれを使ってSUBRを作りました。

Subr subrCons = new Subr() {
        @Override public LObj call(LObj args) {
            return Util.makeCons(Util.safeCar(args),
                                 Util.safeCar(Util.safeCdr(args)));
        }
};

実際にはinner-classが作られているんでしょうか。内部的なことは分かりません。
あと、最近のJavaにはクロージャがあるとかないとかいう話は知りません。

C#の思い出

C#は書いたことがなかったのですが、それよりもいくら探してもC#のロゴらしきものが見当たらなかった方が問題です。だれかC#のロゴが何なのか教えてください。

外観

Javaと同程度の冗長さでしょうか。

public static LObj nreverse(LObj lst) {
  LObj ret = kNil;
  while (lst.tag() == Type.Cons) {
    LObj tmp = lst.cons().cdr;
    lst.cons().cdr = ret;
    ret = lst;
    lst = tmp;
  }
  return ret;
}

といより、ほぼJavaと同じに見えます。

データ構造

Javaのときと完全に同じ戦略です。データはすべて object というすべてのベースとなるクラスにキャストします。型安全とか知りません。

enum Type { Nil, Num, Sym, Error, Cons, Subr, Expr };

class LObj {
  public Type tag() { return tag_; }

  public LObj(Type type, object obj) {
    tag_ = type;
    data_ = obj;
  }

  public Int32 num() {
    return (Int32)data_;
  }
  ...
  public Cons cons() {
    return (Cons)data_;
  }
  ...

  private Type tag_;
  private object data_;
}

class Cons {
  public Cons(LObj a, LObj d) {
    car = a;
    cdr = d;
  }
  public LObj car;
  public LObj cdr;
}

SUBR

よく分かりませんが、delegateというのを使えばクロージャが作れるらしいです。Dのときに同じ話を聞いた気もします。

delegate LObj Subr(LObj ags);

Subr subrCar = delegate(LObj args) {
  return Util.safeCar(Util.safeCar(args));
};

何をやってるのかよく分かりませんが、こんなんで動きました。

小学生並みの感想

「よく分からないけど動く」というのはある意味非常に大事なことだと思います。

[LSP42] Standard MLとOCaml

土曜日, 12月 13th, 2014

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

Standard MLOCamlで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を書くときには慣れてしまったので短く書けるようになったというのもあるかもしれません。詳しい違いはソースコードを読んでください。

小学生並みの感想

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

[LSP42] FantomとCeylon

金曜日, 12月 12th, 2014

(この記事はLISP Implementation Advent Calendar 12日目のためのエントリです。)

FantomCeylonでLISPを作りました。
https://github.com/zick/FantomLisp
https://github.com/zick/CeylonLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその18〜19個目です。
Fantomという言語を選んだ理由はよく覚えていませんが、Wikipediaを眺めて見つけ、簡単そうなので選んだという感じだったかと思います。
Ceylonを選んだ理由もよく覚えていませんが、「JVMで動く(Java以外の)言語は簡潔で簡単なはず」という私の脳内で成り立つ法則に基づいて、JVMで動く言語を探して選んだような気がします。

Fantomの思い出

Fantomはなんといいいますか、フツーのイマドキの言語だったような気がします。正直なところ、非常に印象が薄いです。42個の言語のなかでも印象の薄さはトップクラスかと思います。良い見方をするなら不満に思う点がほとんどなかったのだと思います。

オブジェクト指向

Fantomはオブジェクト指向言語です。オブジェクト指向言語のなかでも「俺はオブジェクト指向言語だ! プログラムを書きたかったらまずクラスを作れ! ヒャッハー!!!」という私の好みじゃないやつです。これまで使った言語の中で言語の機能としてクラスを作ることができる言語はPython、Ruby、R、Factor、CoffeeScript、TypeScript、Dart、Falcon、Groovy、JSXと非常にたくさんありますが、このなかでLISPの1つの型と実装側の1つのクラスを対応させたのはRubyとDartとJSXの3つのみです。このなかでもJSXは1つの大きいクラスを作ってサブクラスはちょっといじるだけというインチキな手法を使いました。基本的に私はクラスというものがそれほど好きではなく、小さなLISPを作るだけならクラスを使わないほうが楽に作れると考えているくらいです。しかし、Fantomはクラスを作ることを強制される(トップレベルに関数を定義できない)言語なのでクラスを作らざるを得ません。

class LObj {
  Str tag
  Int? num
  Str? str
  LObj? car
  LObj? cdr
  LObj? args
  LObj? body
  LObj? env
  |LObj->LObj|? fn

  new makeNil() {
    this.tag = "nil"
    this.str = "nil"
  }
  new makeError(Str s) {
    this.tag = "error"
    this.str = s
  }
  new makeNum(Int n) {
    this.tag = "num"
    this.num = n
  }
  new makeSym(Str s) {
    this.tag = "sym"
    this.str = s
  }
  new makeCons(LObj a, LObj d) {
    this.tag = "cons"
    this.car = a
    this.cdr = d
  }
  ...
}

お察しの通り、1つしかクラスを作っていません。注目すべきは makeNil から makeCons までの部分です。一見メソッドの定義のように見えますが、すべて new というキーワードが付いています。実は、これらは「名前付きコンストラクタ」です。Fantomはコンストラクタに名前をつけることができるため、 makeError と makeSym のように同じ引数のコンストラクタも名前で区別することができるわけです。そう、今回はこの名前付きコンストラクタの機能を堪能するために1つしか(*)クラスを作りませんでした。名前付きコンストラクタの機能を堪能するために仕方なく1つしか作らなかったわけで、決して面倒だったわけではありませんよ。

(*) LISPのオブジェクトのために、という意味で他の目的はいくつかクラスを作ったよ、お兄ちゃん!

簡潔さ

Fantomはイマドキの言語故に、多くのものを簡潔に記述できます。文末にセミコロンなどのデリミタを付ける必要はありませんし、関数の型という複雑なものも |ArgType->RetType| のように簡潔に書けます。クラスのメンバにアクセスするときも this は省略可能ですし、右辺から方が分かる場合は ret := kNil のように型をつけなくても変数を作ることが出来ます。関数の戻り値の型は書く必要がありますが、無駄にコロンを書いたり、ましてや function などの長いキーワードを書く必要はないのでそれほど負担は感じません。やはり簡潔に記述できる言語は素晴らしいです。

Numeric tower?

Fantomには Int と Float というクラスがあって、どちらも Num というクラスを継承している。私はLISP感覚で「それじゃあ、Numを使っておけば整数も浮動小数点数も適切に扱えるな」と思っていたんですが、なんとびっくり。Numに対しては四則演算が出来ませんでした。何のためのNum型だよ。Fantom作った奴は何考えてるんだ、と憤りましたが、後で調べたところ、Javaも同じ仕様みたいです。流行っているんでしょうか。私は納得いきません。

Ceylonの思い出

Fantomとは逆に非常に印象深いのがこのCeylonです。Wikipediaをチラッと見た時から強烈な印象でした。

業界のアナリストからは同プロジェクトはJavaを抹殺するためのものだと言われている

Ceylon – Wikipedia

これを読んだときは何言ってるんだこいつ、と思ったんですが、LISPを作り終えることには、「ああ、『業界のアナリスト』らしい発想だなぁ」と思いました。

source/lisp/lisp.ceylon

GitHubのリポジトリを見れば分かるのですが、ファイルの概念のないScratchを除く、これまでの17個の言語はすべてリポジトリのトップレベルに単一のソースファイルをおいてきました。どれも400行前後のプログラムですから単一のファイルの方が分かりやすいでしょう。しかし、Ceylonはソースファイルを source というディレクトリの中に置かなければいけません。さらにその下にモジュール名に対応したディレクトリを作らなければいけません。Ceylonでプログラムを作るには最低でも1つはモジュールを作る必要があるので、要するに、最低でも2つはディレクトリを作らなければいけないということです。この時点で私はやる気を大幅に失ってしまいました。
一応言っておきますが、私はソースファイルを階層的に管理することを否定しているわけではありません。大きなモノをつくり上げるうえではどのように階層化するか、どうやってルールを守らせるかといったことが非常に大事になるのは分かります。でもそれを言語が強要するというのが嫌いなんです。helloworldのような数行で済むプログラムを作るのにもファイルの置き場を強要するような仕様が非常に嫌いです。

同名

Ceylonは多くのライブラリクラスを提供します。これ自体は非常に素晴らしいことですが、異なるパッケージに同名のクラスがあったり、パッケージと同名のフィールドがあったりします。例えば、 ceylon.file.Reader と ceylon.io.Reader 他にも ceylon.process と ceylon.language.process など。ドキュメントがこれらの名前を省略せずに書いてあれば困ることもありませんが、Ceylonのドキュメントは平気で Reader や process などという表記をしていて、どちらか区別できません。コード片を見て真似をしても動かず。クラスを調べたら使いたいメソッドがない。色々と調べた末に同名のクラスを見つける、という酷いハマりどころを用意しています。嫌がらせ以外のなにものでもないと思います。

Nullable

Ceylonは null を許す型(nullable)と許さない型(non-nullable)を区別します。これ自体は近代的で非常に素晴らしいことだと思います。が、 process.readLine を見て考えを改めました。この標準入力から1行取得する関数の型は String で、つまり null を許さないのですが、EOFを読み込むと null を返します。非常に基本的なライブラリの関数が基本的なルールを守っていないのです。あんまりだ。幸いなことに、 non-nullable な型を nullable な型に変換することはできるので、 wrapper をかませることで難を逃れました。

String? readLine() => process.readLine();

...

  // HACK: The return type of process.readLine is String but it can return
  // null when it reads EOF. I verified this code works on ceylon 1.0.0.
  if (exists line = readLine()) {
    ...
  }

numeric tower? 再び

Ceylonも Number というクラスがあるんですが、これも四則演算を実装していません。Fantomと同じです。まあ、JVMの上で動く言語なのでJavaと同じ仕様にするのは非常に自然なのでこれは仕方ないでしょう。

template classとunion type

Ceylonは非常に嫌な思い出が多いのですが、唯一楽しかったのがtemplate classとunion typeです。これについてはごちゃごちゃ書くよりコードを見たほうが早いと思うのでコードを載せます。

class ConsT<T>(T a, T d) {
  shared variable T car = a;
  shared variable T cdr = d;
}
alias SubrT<T> => Callable<T, [T]>;
alias ExprT<T> => [T, T, T];
alias DataT<T> => Integer|String|ConsT<T>|SubrT<T>|ExprT<T>;

class LObj(String t, DataT<LObj> d) {
  shared String tag = t;
  shared DataT<LObj> data = d;
}

alias Cons => ConsT<LObj>;
alias Subr => SubrT<LObj>;
alias Expr => ExprT<LObj>;
alias Data => DataT<LObj>;

ConsやSubrはLObjに依存するけど、LObjはConsやSubrに依存する。このような相互再帰的な型をtemplate classを使うことで表現できるわけです。さらにunion typeを使うことでLObjが持ちうるデータを明確に定義。この部分だけは書いてて面白かった記憶があります。 data の型は is というキーワードを使って確認できます。

LObj nreverse(variable LObj lst) {
  variable LObj ret = kNil;
  while (is Cons cons = lst.data) {
    LObj tmp = cons.cdr;
    cons.cdr = ret;
    ret = lst;
    lst = tmp;
  }
  return ret;
}

そのため、 tag は必要ないはずなんですが、なんで私が tag を付けたかは忘れてしまいました。恐らく消せるとは思うんですが、直そうという意欲はあまり湧きません。

※これは実装者の感覚によるもので速度を保証するものではありません

私がCeylonでLISPを書いた時に記したメモがあるんですが、非常に興味深い記述がありました。

型に関してはそれなりに楽しかったと思って実行してみたら想像を絶するくらい遅い。ヘタしたらScratchより遅い。

小学生並みの感想

不満がない言語より不満がある言語の方が印象に残るものなんだなぁ。

[LSP42] JSX

木曜日, 12月 11th, 2014

(この記事はLISP Implementation Advent Calendar 11日目のためのエントリです。)

JSXでLISPを作りました。
https://github.com/zick/JSXLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその17個目です。
JSXという言語を選んだのは、やはり楽そうだったからです。以前、JavaScript系(*)の言語を使ったとき非常に楽な思いができ、もう一度あの時くらい楽が出来ないかなと考えていたら、JSXというJavaScript系の言語を見つけたので使わざるを得なかった訳です。

(*) ここでは、JavaScriptに変換できたりJavaScriptの代わりに使えるような言語のことだよ、お兄ちゃん!

外観

JavaScript系の言語だからきっと楽に書けるだろと思っていたらJSXのプログラムを見て度肝を抜かれました。

class Bar {
  function baz(str : string) : string {
    return  str + '!!!';
  }
  function qux() : string {
    return this.baz('foo');
  }
}
class Foo extends Bar {
  var field_ : string;
  function constructor(field : string) {
    this.field_ = field;
  }
  override function qux() : string {
    return this.baz(this.field_);
  }
}

class _Main {
  static function main(args : string[]) : void {
    var foo = new Foo('woohoo!');
    log foo.qux();
  }
}

工工工エエェェ(´д`)ェェエエ工工工
なんですか、このJavaに勝るとも劣らない冗長な記述は。関数には型を必ず付けないといけないのに function という非常に長いキーワードも書かなければならないというのがあまりにも理不尽です。 return がなければ戻り値の型が void なのは明らかなのに、それでもvoidと書かなければなりません。 function constructor というのもいい味を出しています。mainに着目してみると、かの有名なJavaの
public static void main(String[] args)
と、JSXの
static function main(args : string[])
が非常にいい勝負をしているのが印象的です。あとJSXはJavaと異なり this を必ず書かなければなりません。もしかすると、JSXはJavaよりも冗長なコードを書ける可能性を秘めた数少ない言語の1つなのかもしれません。

JavaScriptとの連携

JSXのマニュアルを読んでも標準入力から文字列を取ってくる関数が見当たりませんでした。まあ、JavaScriptに変換される言語なんだから仕方ありません。JSXはNode.jsで動くので、JavaScriptの関数を直接呼んでやれば解決だろうと思ったら、なんと、JSXがJavaScriptのデータを正しく扱えずにエラーになります。マニュアルをいくら読んでも回避策が分かりません。色々と検索してようやくやり方が分かりました。

// setEncoding と on をもつJavaScriptのオブジェクトを扱うための型
native __fake__ class Stdin {
  function setEncoding(str : string) : void;
  function on(str : string, fn : variant) : void;
}

JavaScriptのデータをうまく扱うために自分でインタフェースを定義してやらないといけないようです。まったく違う言語と連携するときには分かるんですが、なんでJavaScriptに変換される言語なのに、こんな面倒なものを記述しないといけないんですか。まあ、この記述は型安全のために我慢するとして、このやり方がマニュアルに載っていないというのはどういうことなんですか。いくらなんでもあんまりだと思います。

オブジェクト

文句ばかり書いてしまいましたが、ちゃんとLISPを作りました。今回はテーブルではなく、ちゃんとクラスを使ってLISPのデータ型を表現しました。

class LObj {
  var tag : string = 'NO TAG';
  function str() : string { return ""; }
  function num() : number { return 0; }
  function car() : LObj { return new LObj; }
  function cdr() : LObj { return new LObj; }
  function set_car(obj : LObj) : void {}
  function set_cdr(obj : LObj) : void {}
  function args() : LObj { return new LObj; }
  function body() : LObj { return new LObj; }
  function env() : LObj { return new LObj; }
  function fn() : function (:LObj) : LObj { return (args : LObj) -> args; }
}

class Nil extends LObj {
  static var nil : Nil = new Nil;
  function constructor() { this.tag = 'nil'; }
  override function str() : string { return "nil"; }
}

class Num extends LObj {
  var num_ : number;
  function constructor(num : number) {
    this.tag = 'num';
    this.num_ = num;
  }
  override function num() : number { return this.num_; }
}

すべてのベースとなるLObjにすべての型のためのアクセッサが定義されているというおちゃめな実装です。クラスの種類ではなく文字列の tag でデータ型を区別します。「このクラスは食べられないよ。明日もう一度この場所にきてください。本当のオブジェクト指向を見せてあげましょう。」という方のために、もう少し普通っぽい実装も試してみました。

class LObj {}

class Nil extends LObj {
  static var nil : Nil = new Nil;
}

class Num extends LObj {
  var num_ : number;
  function constructor(num : number) {
    this.num_ = num;
  }
  function num() : number { return this.num_; }
}

...

  if (obj instanceof Cons) { ... }

...

  var num_obj = obj as Num;
  return num_obj.num();

はい。クラスはずいぶんスッキリしました。型の比較は文字列でなくなったので、型名のtypoなどはコンパイルで弾けます。さて、これを実行してみると、なんと驚きの結果。本のプログラムより1.5倍ほど遅くなります。細かい要因などは調べていませんが、どうも instanceof が特に遅いように見えます。詳しくは詳しい人に聞いてください。

小学生並みの感想

細かいところはともかく、マニュアルはしっかり書いて欲しいです。

[LSP42] Groovy

水曜日, 12月 10th, 2014

(この記事はLISP Implementation Advent Calendar 10日目のためのエントリです。)

GroovyでLISPを作りました。
https://github.com/zick/GroovyLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその16個目です。
Groovyという言語を選んだのは、ずばり楽そうだったからです。毎週末頑張ってLISPを書いていたのにまだ全体の3分の1を超えた程度という事実に疲れたら、ふと「JVM上で動くJava以外の言語はみんな『Javaと較べてこんなに簡潔です』と言ってるし簡単に書けるに違いない」という(根拠の無い)発想にいたり、名前とJVMで動くということしか知らないGroovyを選びました。

外観

さて、実際にはどれくらい簡潔だったかと言いますと、

def makeCons(a, d) {
  return [tag: 'cons', car: a, cdr: d]
}

こりゃ簡潔だ。何よりも型を書かないのがいいですね。

rangeの罠

イマドキの言語にはよく部分配列や部分文字列を取り出すための構文があります。Pythonだと str[start:end] だとかRubyだと str[start...end] といった具合です。Groovyにも同様に str[start..end] という構文があります(ただし、 end は inclusive)。また、 start から終端までの部分配列/文字列を取得する場合は str[start..-1] と書けるのですが、これにはPythonやRubyにはない罠がありました。

if (str[0] == kLPar) {  // 先頭の文字が括弧なら
  return readList(str[1..-1])  // 残りの文字列をリストとして読み込む
}

一見正しそうなコードですが、 str の長さが1の場合、なんと out of range 扱いで例外を投げます。これはおかしい。 「だってstr[1]は取れないでしょ」と思った人は「部分」という言葉についてもっと考えるべきです。この仕様は不自然ですし何よりもメリットを感じません。誰かこの仕様の意味を教えて下さい。

スコープの罠

Groovyはその見た目からいってどう見てもイマドキの言語。PythonやRubyみたいなものだと思って書いていました。そうしたら見事罠に引っかかりました。

def foo() {
  bar = 1
  ...
}

こんなコードを書いていたのですが、Groovyではこの場合 bar はグローバル変数として扱われます。ローカル変数として扱いたければ def を付けて

def foo() {
  def bar = 1
  ...
}

と書きます。知っていればそれだけの話で、「JavaScriptのvarと同じだろ」と言ったところなのですが、マニュアルをよく読んでいなかった私は見事にしてやられました。言い訳をしておくと、Groovyのマニュアルが読みにくいのが悪いです。あと、スコープという大事な話を下の方に書いているのもいただけない。そんな下の方読みませんよ。

小学生並みの感想

普通に使いやすかったので言いがかり的な文句くらいしか書くことがありませんでした。

[LSP42] FalconとEuphoria

火曜日, 12月 9th, 2014

(この記事はLISP Implementation Advent Calendar 9日目のためのエントリです。)

FalconEuphoriaでLISPを作りました。
https://github.com/zick/FalconLisp
https://github.com/zick/EuphoriaLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその14〜15個目です。
FalconとEuphoriaという言語は、Wikipediaを眺めているときに見つけ、簡単そうだったので選びました。今回の企画でLISPを作った言語は10を超え、過去にLISPを作った言語も合わせると既に20を超えており、正直、使う言語を探すほうがLISPを作るのよりも疲れるようになってきました。

Falconの思い出

久々のbegin/end系の言語です。相変わらず好きになれません。でもFalconには1行で書く場合に end を省略できるという素敵な文法があるのでいい感じです。例によってテーブル(Falconの言葉だとdictionary?)でLISPのデータ構造を表現しようとしたのですが、テーブルを比較すると、内容比較になってしまいます。これでは eq を作ることが出来ません。色々と試行錯誤したところ、一度クラスで包んでやればアドレス比較になるようなので、その方法で逃げました。

class L(tag, dict)
  tag_ = tag
  dict_ = dict
  function __getIndex(index)  // 演算子オーバーロードだよ、お兄ちゃん!
    return self.dict_[index]
  end
  function __setIndex(index, value)  // これもだよ!
    self.dict_[index] = value
  end
  function tag()
    return self.tag_
  end
end

function makeCons(a, d): return L('cons', ['car' => a, 'cdr' => d])

function safeCar(obj)
  if obj.tag() == 'cons': return obj['car']
  return kNil
end

努力の方向が間違っているような気もしますが気のせいです。全部クラスで作れという苦情は受け付けておりません。

Euphoriaの思い出

好きになれないとはいえ、endと書くことはある程度慣れてきました。しかし、そんな私の気持ちを打ち砕いたのがこのEuphoria。

function safeCar(object obj)
  if TagEq(obj, "cons") then
    return Car(obj)
  end if
  return kNil
end function

なんですか、この end function というやつは。関数を書くたびに function と2回もタイプするとか正気の沙汰とは思えません。そんな時間があったらどれだけの括弧が書けると思っているんですか。
お察しの通り、またテーブル(Euphoriaの言葉だとmap)でLISPのデータ構造を表現したんですが、mapの操作も冗長だったので、取り敢えず wrapper を書いて逃げました。

function L(sequence tag, object data)
  map obj = new()
  put(obj, "tag", tag)
  put(obj, "data", data)
  return obj
end function

function Tag(object obj)
  return get(obj, "tag")
end function

function TagEq(object obj, sequence str)
  return equal(Tag(obj), str)
end function

function makeCons(object a, object d)
  return L("cons", {a, d})
end function

努力の方向性(冗長性の除去のため以下略)。
あと、一部のオブジェクトは copy-on-write みたいなので注意が必要です。

function SetCar(object obj, object val)
  object data = Data(obj)
  data[1] = val
  put(obj, "data", data)
  return val
end function

うーん、冗長。マニュアルをしっかり読んだわけではないのでなにが copy-on-write なのかはよく分かりません。

小学生並みの感想

タイプ数が少なくてすむ言語は正義だと思いました。