リリカル☆Lisp開発日記

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

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

Rは統計の分野でよく使われる言語で便利な機能を色々持っているらしいです。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその5つ目です。
Rという言語を選んだのは同僚から推薦されたからです。ちょっと調べてみたところ書きやすそうな言語に見えるし、これは簡単だなと思いました。書き始めるまでは。

標準入力の罠

私が知らない言語でLISPを書くときは、まず標準入力から1行読み込みそれをそのまま標準出力に書く、というプログラムを書きます。今回もそれを書こうとしたのですが、いきなりつまずきました。readLineとreadLinesという関数が存在して、それらがまったくの別物だったり、起動オプションを付け加えたらreadLinesの挙動が変わったり初心者には罠が多すぎます。

mutableの罠

Rの変数はmutableです。

x <- 3
x <- x + 4

容易に変数が書き換えられるので、こりゃやりたい放題だと思ったら、LISPのコンスの中身を書き換えようとするところで上手く行かずハマりました。

makeCons <- function(a, d) {
  return(list('tag' = 'cons', 'car' = a, 'cdr' = d))
}
setCar <- function(c, x) {
  c[['car']] = x  # なぜかうまくいかない
}

調べてみたら、なんとRの関数は引数として受け取ったオブジェクトを書き換えることができないようです。書き換えは copy-on-write となり、単にコピーされたオブジェクトが書き換わるだけだとか。もう少し調べてみたところ、クロージャが参照する変数は書き換え放題のようなので、コンスをクロージャを使って表現することで難を逃れました。

遅延評価の罠

mutableの罠を避けるために、最初このようなコードを書きました。

makeCons <- function(a, d) {
  ret <- list('tag' = 'cons')
  ret[['car']] <- function() { return(a) }
  ret[['cdr']] <- function() { return(d) }
  ret[['set_car']] <- function(x) { a <<- x }
  ret[['set_cdr']] <- function(x) { d <<- x }
  return(ret)
}

こりゃ酷い見た目だ、というのは置いておいて、このmakeConsの定義には（初心者には？）気づきにくい罠が潜んでいます。
Rの変数はmutableです。そしてRは引数の評価を可能であれば遅延します。この2つが組み合わされることによって意図せず循環リストが作られる場合があります。

p <- kNil
p <- makeCons(kNil, p)

このようなコードを実行すると何が起こるでしょうか。 makeCons(kNil, p) が呼ばれますが、makeConsのなかで p は直接的には使われないので評価は遅延されます。そして、pには新たに作られたオブジェクトが代入されます。そして、いざ p のcdrを取り出そうとする時初めて引数の p が評価されます。その結果循環リストが生まれてしまうというわけです。マニュアルをろくに読んでいなかった私は、そもそも引数が遅延評価されることすら知らなかったため、これに気づくまでなかなかの時間を要してしまいました。悲しい。遅延評価を避けるため makeCons を次のように書き直しました。

 makeCons <- function(a, d) {
  return(list('tag' = 'cons', 'car' = a, 'cdr' = d))
  car <- a  # Avoid lazy evaluation.
  cdr <- d  # Avoid lazy evaluation.
  ret <- list('tag' = 'cons')
  ret[['car']] <- function() { return(car) }
  ret[['cdr']] <- function() { return(cdr) }
  ret[['set_car']] <- function(x) { car <<- x }
  ret[['set_cdr']] <- function(x) { cdr <<- x }
}

なにこれ？
多分、なにか間違ったことをやっているような気もしますが、これで無事動きました。評価のタイミングとかは厳密には間違っているかもしれませんが、まあ動けばなんでもいいです。あと、Rの比較はなにかと中身まで見てしまうようですが、クロージャはアドレス比較になるようなので eq を作る上では都合がいいかと思います。

小学生並みの感想

簡単そうな言語もマニュアルをしっかり読まなければハマることがあるのが分かりました。

This entry was posted on 水曜日, 12月 3rd, 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.