リリカル☆Lisp開発日記

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

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

Factorはいわゆるスタック指向型のプログラミング言語です。Factorの開発元は concatenative programming という言葉を好んで使っているようですが、この言葉はあまりメジャーではない気がします。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその7つ目です。
Factorを選んだ理由はよく覚えていないのですが、確かWikipediaを眺めてテキトーに決めたんだと思います。Lua、Python、Ruby、R、Perlといった有名な（少なくても私が名前を知っていた）言語が続いていたので変わったものをやりたいという気持ちもあったかもしれません。

スタック

Factorでは 1 2 + とか書いたら1+2 が実行されます。1と2がスタックに積まれて可算が実行されるわけです。スタック特有の操作として最低限、スタックトップを捨てる drop, スタックトップをコピーする dup, スタックトップとその1つ下を入れ替える swap あたりを知っておくと便利です。階乗は次のように書けます。

: fact ( n -- m )
  dup 0 = [
    drop 1 
  ] [
    dup 1 - fact *
  ] if ;

最初のコロンはこれからワード（関数みたいなもの）の定義が始まりますよという印で、 fact はそのワードの名前。その後の括弧はコメントで実行結果には何も影響を与えません。 dup 以降の残りの部分は読者の練習問題とします。
さて、この括弧が面白いので解説すると ( n -- m ) は「スタックから1つものを消費して、スタックに1つものを置く」ということを表しています。例えば drop は ( x -- ), dup は ( x -- x x), swapは ( x y -- y x) という記法で表せます。前述のとおり、これらはコメントで実行結果には影響しませんが、Factorはコンパイル時にワードが実際にこのコメントと合致しているか確かめます。 if のようにコードが分岐する場合もスタックに置かれるものの数が変わらないかチェックしてくれるわけです。非常に親切です。

例えば

: wrong-fact ( n -- m )
  dup 0 = [
    drop 1
  ] [
    1 - wrong-fact *
  ] if ;

こんなコードをコンパイルすると

The input quotations to “if” don't match their expected effects
Input                Expected       Got
[ drop 1 ]           ( ..a -- ..b ) ( x -- x )
[ 1 - wrong-fact * ] ( ..a -- ..b ) ( x x -- x )

といった具合に非常に分かりやすいエラーメッセージを出してくれるわけです。

オブジェクト

Factorはオブジェクト指向言語でもあります。総称関数（正確には generic word ）を作れたり、色々と凄いんです。これでLISPのデータを定義してやれば色々と凄そうなわけです。でもまあ、LISPを作るくらいだとそんな高度な機能も必要ありませんが。

TUPLE: lobj tag data ;
C: <lobj> lobj
TUPLE: cell car cdr ;
C: <cell> cell

: make-cons ( car cdr -- lobj )
  <cell> "cons" swap <lobj> ;

: safe-car ( lobj -- lobj )
  dup tag>> "cons" = [
    data>> car>>
  ] [
    drop kNil get-global
  ] if ;

これが何をしているかは明らかなのでコードの解説は読者の練習問題とします。

quotation と stack checker

FactorはLispの quote のようにコードをオブジェクトとして扱うことが出来ます。上記コードの if といっしょに現れる大括弧 [] で囲まれた部分がそれです。このようなオブジェクトを quotation と呼びます。 quotation があるおかげで、 if や while といったプリミティブが自然な形で使えるし、高階ワードを作ることもできるわけです。しかし、これには制約があります。

The stack checker cannot guarantee that a literal quotation is still literal if it is passed on the data stack to an inlined recursive combinator such as each or map

Combinator stack effects – Factor Documentation

データスタック経由でリテラルの quotation を inlined recursive combinator に渡すと、それがリテラルであるかどうか stack checker は保証できないとか何とか。まあ、なんとなく言っていることが分かるような分からないような感じですが、要は下手に quotation を使うとコンパイルエラーになるということです。詳しくは、詳しい人に聞いてください。私は「よーし、高階ワードを作って抽象化しちゃうぞ！」と気軽な気持ちで quotation を使ったら数時間この制約に悩まされ、結局 quotation を使わない方向に逃げることになって後悔しました。

『3』 – スタックについての究極の疑問の答え

Factorのマニュアルには「変数に名前をつける機能とかあるから、別にすべてをスタックでやらなくてもいいよ」と書いてありましたが、今回はあえてすべてをスタックの上でやりきりました。色々と試行錯誤しているうちに一つのことに気付きました。

一度に触るのがスタックトップから3つまでだと非常に簡単にプログラムが書けるのに対して、スタックトップから4つ目以降を触わろうとすると非常にぎこちないプログラムになる。

こうなった原因の一つとして、Factorが提供する組み込みのワードはスタックトップから3つ目までを操作するものが多い、ということもあるでしょうが、そもそも4つを超えたあたりで人間には色々と辛い、というのがでかい気がします。Factorの元となったForthに対して偉い人が

The words PICK and ROLL are mainly useful for dealing with deep stacks. But the current trend in Forth programming is to avoid making the stack deeper than 3 or 4 elements.

A Beginner’s Guide to Forth by J.V. Noble

と言っているので世の中の真理ではないのかと勝手に思っておきます。

スタックは熱いうちに打て

一日で「ドリャ」っとFactorのプログラムを書き上げる場合は、スタックの状態がどうなってるか、ある程度頭のなかに残っているからいいんですが、数日、数カ月と経ってから再度プログラムを編集しようとすると、スタックがどうなっているのか頭から完全に抜けているので辛いです。回避策は、長いワードを作らないことと、やはり1度に3つまでしかスタックに積まないことでしょうか。この辺りは誰か詳しい人にでも聞いてください。

小学生並みの感想

スタックは楽しい。そして辛い。

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

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

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその6つ目です。
Perlという言語を選んだのは同僚からRを推薦された時に、私がPerlと聞き間違えたのがきっかけだったような気がします。

まるでCのような安心感

私はPerlをほとんど書いたことがなかったのですが、ウェブサイトのカウンタや掲示板を書くのによく使われていた、だれでも気軽に書ける「チャラチャラした言語の筆頭格」と認識していました。でもいざ触ってみたら、変数は宣言するし、セミコロンをちゃんと書かないといけないし、ifやforのあとの括弧も省略できないし、意外とチャラチャラしていませんでした。むしろCのような安心感がありました。
一番驚いたのは「参照」の存在です。Perlと言えばなんでも無駄にコピーされるという認識だったのに、参照のおかげで安心してプログラムが書けます。あと、Perlといえば変数の前に $ を付けますが、配列だと @ で ハッシュだと % を付けるという面倒なルールがありますが、参照を使うと、常に $ しか使わなくていいというのも良かったです。参照の dereference にも $ を使うので、非常にお金の臭がするプログラムが書けます。

sub makeCons {
    my ($a, $d) = @_;
    # 中括弧{}を使えるとハッシュの参照が得られる
    return { tag => 'cons', car => $a, cdr => $d };
}

sub pairlis {
    my ($lst1, $lst2) = @_;
    my $ret = $kNil;
    while ($$lst1{tag} eq 'cons' && $$lst2{tag} eq 'cons') {  # dereference してから tag にアクセス
        $ret = makeCons(makeCons($$lst1{car}, $$lst2{car}), $ret);
        $lst1 = $$lst1{cdr};  # cdr にも参照が入っているはずなので参照がコピーされる
        $lst2 = $$lst2{cdr};  # 実体はコピーされない
    }
    return nreverse($ret)
}

まるでCと違う不安感

Perlを高級なC言語と思うと、悪くないんじゃないかと思いましたが、サブルーチンの引数の文法だけは意味が分かりません。

sub makeNumOrSym {
    my ($str) = @_;  # なにこれ......
    if ($str =~ /^[+-]?\d+$/) {  # これはまあいいや
        return makeNum($str + 0);
    }
    return makeSym($str);
}

なんなんですか。 @_ というのは。Perl好きの人に文句を言ったら「shiftとか$_[0]とかもあるよ」と言われましたが、引数には名前がないとあとで読めなくなるじゃないですか。まあ、私はそう主張しながら x という名前の引数を作ったりするのですが。

小学生並みの感想

楽しかったです。でも、Perl好きの人から「ぜんぜんPerlっぽくない」と言われたので、私が書いたのはいわゆるPerlとは違う何かである可能性が高いです。

（この記事は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 を作る上では都合がいいかと思います。

小学生並みの感想

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

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

LuaとPythonとRubyでLISPを作りました。
https://github.com/zick/LuaLisp
https://github.com/zick/PyLisp
https://github.com/zick/RbLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその2〜4つ目です。
Lua、Python、Rubyという言語を選んだのは簡単そうだったからです。1つ目のScratchで苦労したので楽がしたかったんです。どの言語もほとんど書いたことがありませんでしたが、実際に簡単だったため、1日で3つの言語でLISPを実装することが出来ました。しかし、その半面、LISPを書き終えてもこれらの言語がどんな言語なのかさっぱり分からないままでした。自分が使った機能のことさえよく分かっていません。

Luaの思い出

イマドキの言語にもかかわらず、複合データ型はテーブル（連想配列）しかないようです。ひょっとしたら配列はテーブルとは別の扱いかもしれませんが、よく調べてないので分かりません。いずれにせよ、よく調べずに書けてしまうのですから素晴らしいことです。LISPのデータはタグとデータを1つのテーブルに入れることで表現しました。

function makeCons(a, d)
  return { tag = 'cons', car = a, cdr = d }
end

Luaはブロックを(小/中/大)括弧ではなく、 if X then Y end のようにendを使って表現します。基本的に私はこのbegin/endの文化があまり好きでなく避けてきたため、begin/end系の言語を100行以上書いたのはこれが初めてかもしれません。
begin/endのネストが無駄に深くならないようにelseifというキーワードも準備されています。しかし、私はこのelseifというものがあまり好きではありません。Cの else if のように単なるifとelseだけで表現できる方がシンプルで好きです。もっともCのelse ifは文法に曖昧さを招いてしまうのですが、それがまた好きです。
Luaは文法に関して個人的に好みでない点もありましたが、全体を通してみると書きやすく、サクサク動いた感じでした。

Pythonの思い出

PythonはLuaと違い、クラスを作ることが出来るのですが、Luaで作ったLISPを単純に移植したのでテーブル（Pythonの言葉だと辞書？）を使ってLISPのデータを表現しました。

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

単純な移植なので悩むこともなくさらっと書けたと思います。
Pythonと言えばブロックをインデントを使って表す言語で、これまた私の好みではないのですが、Luaで山ほどendを書いた直後だったので、endを書かずにすんだのは正直うれしかったです。
あと、Pythonはelseifではなくelifです。紛らわしい。

もんだい

クラスがあるのになんでもテーブルで書くのはあんまりだと思ったzickくんは、クラスを使ってLISPを書き直しました。

class Cons:
    def __init__(self, a, d):
        self.car = a
        self.cdr = d
...
if isinstance(x, Cons):
  ....

しかし、zickくんの予想に反し、実行速度は大幅に遅くなってしまいました（3.44sec -> 19.37sec）。
速度が低下した理由を答えなさい。なお処理系はPython 2.7.5とする。

Rubyの思い出

Rubyにクラスがあるのは言うまでもないのですが、またもや単純にLuaで書いたものを移植したのでテーブル（Rubyの言葉だとハッシュ？）を使ってLISPのデータを表現しました。

def makeCons(a, d)
  return { 'tag' => 'cons', 'car' => a, 'cdr' => d }
end

RubyもLuaと同じくbegin/end系の言語です。また山ほどendを書かないといけないのかとちょっとうんざりしました。
あと、Rubyはelseifやelifではなくelsifです。いい加減にして欲しい。
Rubyで一番驚いたのは高階関数が素直に書けないことでした。 def myFunction ... end と関数を定義した後に myFunction と書いても関数を参照できないようです。しかたがないので、SUBRは非常に遺憾ながらオブジェクト指向言語らしく、クラスとメソッドを使って作ることになってしまいました。後日「RubyはLISP2であり、CLの#'fはmethod(:f)、CLの(funcall f arg)はf[arg]と書ける」という話を人から聞き、コードはシンプルになりました。何か色々と間違っているような気もしますが気のせいだということにしておきます。

もんだいない

クラスがあるのになんでもテーブルで書くのはあんまりだと思ったzickくんは、クラスを使ってLISPを書き直しました。

class Cons
  def initialize(a, d)
    @car = a
    @cdr = d
  end
  attr_accessor :car, :cdr
end

zickくんの予想通り、実行速度は大幅に改善されました（10.09sec -> 2.02sec）。めでたしめでたし。

小学生並みの感想

高級なデータ構造が使え、ごみ集めがある言語でLISPを作るのは非常に簡単でよかったです。

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

ScratchでLISPを作りました。
ScratchLisp on Scratch

Scratchとはマウスを使い、ブロックを並べることでプログラムの作成ができる教育用プログラミング言語/開発環境です。詳しい説明はWikipediaなどに譲るとして、ScratchでLISPを作った時の思い出話を始めようと思います。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその1つ目です。
Scratchという言語を選んだのは同僚から推薦されたからです。「ただの奇妙な言語だと、どうせトランスレータを書くことになるだけだから面白く無い。もっと手を動かして苦労してもらいたい」という慈悲の心に溢れた素晴らしいコメントも頂きました。

変数

Scratchの変数はいくつか種類があるのですが大事な点は「実質的にグローバル変数しか存在しない」ということです。
そして、変数に対する何らかの操作をするたびに、変数一覧の中から適切な変数をマウスで選ぶという苦行が待ち受けています。

型と変数

Scratchは基本型として真偽値、浮動小数点数、文字列を持ちます。また複合型としてリストを持ちます。リストは可変長で任意の値を挿入/参照することができます。また、整数のインデックスを使って任意の箇所にアクセスが出来ます。
Scratchでは値を格納するための「変数」と値の列を格納するための「リスト」は別物として扱われます。

変数に対しては値の代入と参照ができます。リストに対しては値の挿入、削除、参照ができます。無駄に複雑な話ですが、リストは値として扱うことが出来るため、変数にリストそのものを代入することもできます。しかし、リスト操作は値に対して行うことができません。つまり、リストを値として扱える仕様には恐らく意味がありません。なぜこのような仕様になっているかは謎です。

手続き

素晴らしいことに、Scratchはユーザが手続き（Scratchの言葉だとブロック）を作り、任意の箇所からそれを呼び出すことが出来ます。任意個の引数を受け取ることも出来ます。さらに素晴らしいことに手続きの再帰呼び出しも可能です。問題点は、手続きは戻り値を持たないということです。しかたがないのでグローバル変数(＝普通の変数)を1つ用意して、そこに戻り値を入れることにしました。

そしてさらなる問題はローカル変数がないということです。引数はimmutableなのでローカル変数代わりにすることは出来ません。ローカル変数を書き換えるために再帰呼び出しをするという関数型言語原理主義者の真似をしたくなるのをぐっとこらえて、リストを1つ用意してそれをスタックとして使用することで（mutableな）ローカル変数を実現しました。

LISPのデータ型

今回作るLISPはコンス、シンボル、整数、SUBR、EXPR、エラーの6種類の型を持つことにしました。Scratchには新たなデータ型を作る機能はないので、これら6つのデータ型はすべて数にエンコードしました。Scratchの数は恐らくIEEE 754の倍精度浮動小数点数で仮数部は32bit以上あるという仮定のもと、以下のような形でデータを表現しました（ちなみにScratchにビット演算は無いので四則演算を用いてビット操作を行います）。

MSB                                        LSB
| GC (1 bit) | TAG (3 bits) | DATA (28 bits) |

Mark and sweepのごみ集めを実装するために1bit用意し、6種類の型を表現するために3bit。残りを型に応じて使い分けます。整数は28bitに押しこめばいいとして、その他のデータ型はもうひと頑張り必要です。

LISPのメモリモデル

コンスを表現するためにCAR用、CDR用の2つのリストを用意しました。コンスを作成すると2つのリストの同じ位置にデータが置かれるという仕組みです。シンボルを表現するためには1つのリストを用意し、そこに文字列を入れました。これで最大で2^28個のコンスと2^28種類のシンボルを作ることが出来ます。EXPRはコンスを使って表現し、エラーはシンボルを使って表現しました（タグだけは変えますが）。SUBRは整数を格納し、Scratch側でその値によって呼び出す手続きを決めるコードを書きました。

LISPのリーダ

Scratchの文字列に対する処理は貧弱で「文字列の長さを取得する」「n文字目を取り出す」「2つの文字列を連結する」という3つの命令しかありません。しかし、LISPのリーダを作るにはこれで十分です。素直に先頭から1文字ずつ読むプログラムを作るだけです。ただしマウスで。

LISPのプリンタ

逆にLISPのデータ型を文字列に変換する必要もありますが、扱いやすいLISPのデータ型の操作ですし、Scratchには文字列の連結という超便利な命令もあります。ただ作るだけです。ただしマウスで。

LISPの評価器

評価器は完全にLISPのデータ型の世界で完結するので簡単に作れます。手続きの再帰呼び出しもできるので、普通の評価器を作るだけです。ただしマウスで。

LISPのごみ集め

一通り動くLISPが出来上がった後、ごみ集めを実装するか思い悩んだんですが、思い切って作ることにしました。単純なmark and sweepですし、GC用のbitも用意してある、スタックも自分で管理している。これなら簡単にできるはずと思って。確かに、だいたい動作するものが出来るまでにはそれほど時間がかからなかったのですが、何度かごみ集めが動くとそのうち動作がおかしくなるという一番嫌なバグに出会いまして、結局ごみ集めの実装には約3時間を要することとなってしまいました。Scratch上でのデバッグは非常に困難なので皆さん一度体験するとよいでしょう。

小学生並みの感想

マウスでプログラムを作るのは大変だと思いました。