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

[LSP42] CofeeScriptとTypeScriptとDart

月曜日, 12月 8th, 2014

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

CoffeeScriptTypeScriptDartでLISPを作りました。
https://github.com/zick/CoffeeLisp
https://github.com/zick/TypeLisp
https://github.com/zick/DartLisp

どれもJavaScriptに変換可能でブラウザで実行できる言語です。ただし、Dartは独自のVMも持っています。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその11〜13つ目です。
CoffeeScript、TypeScript、Dartという言語を選んだのはJavaScriptの派生(?)言語ということで非常に簡単そうだったからです。正直これらJavaScript系言語は簡単すぎるので敬遠していたのですが、42個中10個の言語で実装するだけで既に7週間程度を費やしていたため、これはもう少しスピードアップしようと思い、久しぶりに一日で3つの言語でLISPを実装しました。

CoffeeScriptの思い出


PythonとJavaScriptを混ぜたような感じです。インデントでブロックを表し、タイプ数が少なくてすむような文法です。例によってテーブル(JavaScript系の言語なので恐らくオブジェクト?)を使ってLISPのデータ構造を表しました。

makeCons = (a, d) ->
  { tag: 'cons', car: a, cdr: d }

TypeScriptの思い出

CoffeeScriptが独自の文法なのに対し、TypeScriptはJavaScriptのスーパーセットとなっています。名前が表す通り、変数や関数に型をつけることができます。型は optional なのですが、型をつけなければ完全にJavaScriptになってしまうため、頑張って型をつけました。

// tag は必須、後のデータはあってもなくてもいい
interface LObj {
  tag: string;
  str?: string;
  num?: number;
  car?: LObj;
  cdr?: LObj;
  fn?: (args: LObj) => LObj;
  args?: LObj;
  body?: LObj;
  env?: LObj;
}

function makeCons(a: LObj, d: LObj) {
  return { tag: 'cons', car: a, cdr: d };
}

ひたすらに色んな所に LObj と書くだけの簡単なお仕事でした。実質的に型付けの恩恵を受けれない上に、やたらとタイプ数が増えるだけの悲しい思いをしました。CoffeeScriptの後だったので、 function と書くだけでも面倒だったのに。あとコンパイル時間が長いのもいただけない。

Dartの思い出

DartはCoffeeScriptと同様に独自の文法を持っています。ブロックは中括弧{}で表し、セミコロンも必要なため、CoffeeScriptと比べるとタイプ数は多くなりますが、それでもイマドキの言語らしく、少ないタイプ数で色々できます。例によってテーブル(Dartの言葉だとmap)を使ってLISPのデータ構造を表現しました。

makeCons(a, d) => {
  'tag': 'cons',
  'car': a,
  'cdr': d
};

が、完成品を走らせてみるとCoffeeScriptとTypeScriptと比べびっくりするくらい遅い。ちょっと遅いというレベルではなく圧倒的に遅い。「なんでこんなに遅いの?」と疑問を書いたらDartの中の人から「クラスを使うんだ!」というメッセージとともにパッチが送られてきました。

class Cons {
  var car;
  var cdr;
  Cons(this.car, this.cdr);
}

makeCons(a, d) => new Cons(a, d);

こんどはDartが圧倒的に速いという結果に。でも中の人にアドバイスを貰ったのはちょっと反則気味な気も。

小学生並みの感想

みんなちがって、みんないい、わけでもない。

[LSP42] NekoとTcl

日曜日, 12月 7th, 2014

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

NekoTclでLISPを作りました。
https://github.com/zick/NekoLisp
https://github.com/zick/TcLisp

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその9〜10個目です。
Nekoを選んだ理由はよく覚えていませんが、たしかWikipediaを眺めていて名前が可愛かったから選んだという感じだったかと思います。
Tclを選んだ理由は簡単な予感がしたのと、このマンガがいい感じだったからです。

Nekoの思い出

外観

見るからにイマドキの言語ですぐ書けそうです。

var makeCons = function(a, d) {
  return { tag => "cons", car => a, cdr => d }
}

こりゃどう考えても簡単だ。

マニュアル分からん

でもライブラリ関数を使おうとしたところでいきなりつまづきました。たぶん、何かを import やらなんやらしないといけない、というのはすぐに予想がついたんですが、いくらマニュアルを探しても分からない。仕方がないからぐぐってみたものの、マイナー言語故にあまり資料が見つかりませんでした。頑張って色々調べた末に、

var buffer_add = $loader.loadprim("std@buffer_add", 2);

こんなふうに書けばいいと分かりました。この 2 は引数の数。なんでマニュアルに載ってる関数使うために、FFIを使うみたいな真似をしないといけないとは。いや、それはいいとして、せめてマニュアルの分かりやすいところに書いてください。

謎の『$』

Nekoの一部の組み込み関数は $print という風に先頭に $ が付きます。すべての関数に $ が付くのなら分かりやすいのですが、一部にのみ付くので、頻繁に付け忘れました。なんとかして欲しいです。

スクリプト言語?

Nekoのマニュアルをいくら探しても標準入力から1行とってくる、という関数が見つかりませんでした。しかたがないので自分で実装するはめに。

var readline = function() {
  var stdin = file_stdin()
  var buf = buffer_new()
  try {
    while (true) {
      var c = file_read_char(stdin)
      if (c == 0x0a) {
        break;
      }
      buffer_add_char(buf, c)
    }
  } catch e {
    return false
  }
  return buffer_string(buf)
}

なんでスクリプト言語で readline なんつーものを自分で実装しないといけないんですか。やめてください。

再帰不能

Nekoでは素直に関数の再帰呼び出しを行うことができないようです。

var fact = function(n) {
  if (n == 0) {
    return 1
  }
  return n * fact(n - 1)  // Uncaught exception - Invalid call
}

なんと例外を投げます。どうやら function の内側からは fact が見えないようです。

var fact = null
fact = function(n) {
  if (n == 0) {
    return 1
  }
  return n * fact(n - 1)  // Uncaught exception - Invalid call
}

こんな風に書きなおしても駄目。内側の fact は null になってしまいます。関数を定義し終えた後に変数を書き換えても元の値が使われてしまうようです。
では変数を書き換えなければいいのだろうということで、オブジェクトを作ってそのフィールドに関数を入れることで解決。

var fact = $new(null)
fact.call = function(n) {
  if (n == 0) {
    return 1
  }
  return n * fact.call(n - 1)
}

またどこかで聞いたような解決策に。

Tclの思い出

外観

パッと見たところ、割と普通の言語に見えます。

proc skipSpaces {str} {
    set i 0
    while {$i < [string length $str]} {
        if {![isSpace $str $i]} {
            break
        }
        incr i
    }
    return [string range $str $i [string length $str]]
}

でもよく見てみると、やたらと大括弧[]が多いことに気付きます。これこそがTclの(私にとって)面白いところです。

コマンド

Tclのプログラムは「コマンド」と引数の並びです。コマンドとは先程のプログラムだと set とか while とかです(実は proc もコマンドですが)。大事なルールは「引数は基本的に評価されない」ということです。 set i 0 の i は評価されずに名前のまま残るからこそ、 変数iに 0 が代入されるわけです。 incr i も同様に変数iがインクリメントされるわけです。
引数に現れる変数を評価したければ変数名の前に $ を付けます。しかし、これは変数のみを評価するのであって、引数全体を評価するものではありません。例えば string length $str というプログラムは $str の部分は変数の値に評価されますが、 length という部分はそのまま名前として残ります。結果として、 string というコマンドに length という名前と変数strの値が渡されます。実行結果は変数strの値である文字列の長さになります。lengthはコマンドstringのサブコマンドとでもいったところでしょうか。

コマンド置換

引数を評価したければ、大括弧を使います。例えば set i [string length $str] とすると、iに文字列の長さが代入されます。大括弧で囲まれた部分はコマンドとみなされ、それが先に実行されて、その実行結果で引数が置き換えられるので「コマンド置換」などと言うらしいです。シェルスクリプトのバックスラッシュみたいなものと考えれば分かりやすいかもしれませんが、なんだか品がありませんし、何よりも面白くありません。
ここで考え方を変えて、「Tclのプログラムは全体が quote されていて、大括弧で unquote される」と考えてみてください。Tclのプログラムが急に美しい世界に見えてきます。初めてLISPのquoteを知った時のような興奮が押し寄せてきます。何を評価して何を評価しないかは人に委ねるのではなく自分で決めるんだと考えると興奮のあまり鼻血が出てきそうになってきます。

リスト

Tclにはリストがあります。「そりゃリストくらいあるだろ」とお思いかも知れませんが、「リストは中括弧{}で表す」と聞くと、なにか大変なことに気付きませんか。そうです。ifやwhileの後に現れる中括弧、さらにはprocの後に現れる中括弧はなんとリストだったのです。Tclはすべてが quote されているのですから、リストもquoteされたリストです。つまり、リストで「その場では実行されないプログラム」を表現できるわけです。procやifやwhileはその引数を必要な場合に適切に評価するわけです。つまりスペシャルフォームです。もはやTclのプログラムは美しい花畑に見えてきて、その世界にいるだけで幸せな気分になってきます。「そもそもスペシャルフォームの存在が美しくない」という純粋すぎる方は専門の医師の診断を受けたほうがいいかもしれません。

expr

前述のプログラムをしっかりと読んだ人は $i < [string length $str]![isSpace $str $i] という箇所はコマンド+引数の形になっていないと気づいたかもしれません。「美しい世界など幻想。所詮は汚いスクリプト言語だ。」と思ったら大間違いです。
Tclには expr というコマンドがあります。これは引数を式とみなしてその値を求めるものです。

expr 1 + 2  # => 3
set i [expr 1 + 2]  # iに3が代入される
string length "abcd"  # => 4
expr $i < [string length "abcd"]  # => 1 (Tclで1は真の扱い)

もうお分かりですね。ifやwhileの第一引数として受け取ったリストは expr に渡されるわけです。スペシャルフォームの枠組みからは出ておらず、十分に美しい世界の中の話といえるでしょう。興奮冷め止まない感じです。

TclでLISP

さて、そろそろLISPを作った話をします。普段ならその言語にどんなデータ構造があってどうやったら楽に書けそうかを考えるんですが、すっかり興奮しきったは私はLISPを書きたい欲求を抑えきれず「もう整数だけあればいいや」とまるでCで書くようなLISPを書いてごみ集めも自分で書いてしまいました。

# <Object>
#   MSB              LSB
#   gc(1) data(28) tag(3)

proc getTag {x} {
    return [expr {$x & 0x7}]
}

proc setData {x data} {
    return [expr {($x & ~0x7ffffff8) | (($data << 3) & 0x7fffffff)}]
}

基本的にScratchのときと同じ実装です。ただ、マウスではなくキーボードでプログラムを書けるのであまりにも簡単でした。キーボードの神様に感謝。

小学生並みの感想

キーボードでプログラムを書けるって素晴らしい。

[LSP42] Io

土曜日, 12月 6th, 2014

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

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

Ioは prototype-based のオブジェクト指向言語でSmalltalkの影響を強く受けています。多分。でも私はSmalltalkのことをよく知らないのでなんとも言えません。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその8つ目です。
Ioを選んだ理由は同僚に「なかなか面白そうな言語だから」と推薦されたからです。触れば触るほど面白さが伝わってくる言語でしたが、面白さが全部伝わる前にLISPが完成してしまいました。

文法

Ioの文法は初めて見るとちょっとだけ不思議な感じがします。

fact := method(n,
  if ( n == 0,
    1,
    n * fact(n - 1)))

注目すべきは method(引数, 本体)if (condition, then, else) という部分です。LISPとCを折衷したような独特な文法です。少々風変わりですが慣れてしまえば書きやすいです。たまにカンマを書き忘れて、それで挙動が変わってしまうことがあるのがちょっと困りモノです。

オブジェクト

Ioはいわゆる prototype-base のオブジェクト指向言語なのでクラスは存在しません。

LObj := Object clone
makeCons := method(a, d,
  cell := LObj clone
  cell tag := "cons"
  cell car := a
  cell cdr := d
  cell)

既存のオブジェクトのクローンを作って新しいオブジェクトを作っていくわけです。「俺はオブジェクト指向言語だ! プログラムを書きたかったらまずクラスを作れ! クラスを作るたびにファイルを作れ! ヒャッハー!!!」などといった横暴な言語と違って、穏やかな優しい印象を受けます。「なんで tag とか作ってるの? 別にいらないでしょ?」とか思った人は後で職員室に来るように。

高階関数

SUBRを作るために高階関数を作ろうとしたら少し困りました。

f1 := method(arg, body)
f2 := f1

などと書いても f2 には nil が代入されてしまいます。こうなる理由は調べた気がするんですがもう忘れてしまいました。回避策としてオブジェクトのスロットにメソッドを代入して、そのオブジェクトを持ちまわることにしました。少し考えてみたらまったく同じことを過去にもやったことを思い出しました。RubyでLISPを実装した時です。さらに考えてみると、RubyもSmalltalkの影響を受けている言語です。これを踏まえてマニュアルを読み直してみると、SmalltalkにもRubyにもIoにも block という概念があるのに気付きました。

「そうか、わかったぞ!」

と、思ったところまでは覚えているのですが何を分かったのか忘れてしまいました。誰か思い出させてください。

職員室

Ioの オブジェクトは hasProto というメソッドを持ち、これでオブジェクトがどのオブジェクトを元に作られたが調べられるので、わざわざ tag などといったものを付けなくても実行時に型を調べられるわけです。

Cons := LObj clone
makeCons := method(a, d,
  cell := Cons clone
  cell car := a
  cell cdr := d
  cell)
...
if (obj hasProto(Cons), ...)

しかし、これを使ってLISPを書くと速度が低下しました(6.2sec -> 6.6sec)。恐らく、 prototype のチェーンをたどるより文字列を比較するほうが速いのが要因でしょうが、原因の究明は読者の練習問題とします。

小学生並みの感想

やっぱり書きやすい言語はいいと思いました。

[LSP42] Factor

金曜日, 12月 5th, 2014

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

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

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

動機

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

スタック

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つまでしかスタックに積まないことでしょうか。この辺りは誰か詳しい人にでも聞いてください。

小学生並みの感想

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

[LSP42] Perl

木曜日, 12月 4th, 2014

(この記事は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とは違う何かである可能性が高いです。

[LSP42] R

水曜日, 12月 3rd, 2014

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

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

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

動機

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

標準入力の罠

私が知らない言語でLISPを書くときは、まず標準入力から1行読み込みそれをそのまま標準出力に書く、というプログラムを書きます。今回もそれを書こうとしたのですが、いきなりつまずきました。readLinereadLinesという関数が存在して、それらがまったくの別物だったり、起動オプションを付け加えたら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 を作る上では都合がいいかと思います。

小学生並みの感想

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

[LSP42] LuaとPythonとRuby

火曜日, 12月 2nd, 2014

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

LuaPythonRubyで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の#'fmethod(: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を作るのは非常に簡単でよかったです。

[LSP42] Scratch

月曜日, 12月 1st, 2014

(この記事は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上でのデバッグは非常に困難なので皆さん一度体験するとよいでしょう。

小学生並みの感想

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

ScratchでLisp作った

土曜日, 3月 15th, 2014

突然ですが問題です。この画像は何でしょうか。

答え: Lispインタプリタのソースコード

「なんちゅうソースコードだ」と思った方はぜひこちらからお試しください。

「中を見る (See inside)」を押すことでソースコードが読め、その場で書き換えることも出来ます。

というわけでScratchでLispインタプリタを作りました。ScratchとはSmalltalkを元に作られたSqueak、を元に作られた教育用のプログラミング言語/開発環境だそうです。キーボートで文字を打ち込むのではなく、マウスでブロックを並べることによってプログラムを作ります。子供でも簡単にプログラムを作成することができるらしいので、つまり子供でも簡単にLispインタプリタが作成できるということですね。

一見、非常に低機能な言語のように見えますが、一通りの機能は揃っているので、足らない部分は努力で補えます。

  • ビット演算がない -> 四則演算で代用
  • ユーザ定義ブロック(手続き)に戻り値の概念がない -> 戻り値を入れる変数を自分で作る
  • ユーザ定義ブロックの引数はimmutableでmutableなローカル変数が作れない -> 自分でスタックを作る

どれもNScripterで使ったテクニックなのでさほど苦労しませんでした。

一番の問題は、プログラムを書きにくい/修正しにくいということです。マウス操作を少し失敗すると、簡単にプログラムを破壊してしまいますし、redo, undoといった機能も存在しません。一つ一つの操作を集中して行わなければなりません。この苦労は言葉では言い表しにくいので、是非みなさんも体験してください。

意外と良かったと思ったのは、ユーザ定義ブロックにearly returnの機能がないということです。途中に条件分岐があっても必ず合流します。このせいで書きにくかったところも多数ありましたが、スタックを自分で作って管理するという観点では、必ず合流する方がミス(popし忘れ、popしすぎ)を犯しにくいという利点がありました。

作り終えて一番ショックだったのは、完成したプログラムが想像以上に小さかったということです。頑張ってごみ集めまで書いたのにこの小ささはなんだ、と思ってしまいました。悔しくて色々と無駄な機能を付けました。

  • りこさんをクリックするとなにかしゃべります。
  • クリックし過ぎると踊ります。
  • しばらく放置するとりこさんが寝ます。
  • 評価に時間がかかりすぎてもりこさんが寝ます。
  • ごみ集めが起こるとりこさんが着替えます。
  • それでもメモリが足りないとブルースクリーンっぽい画面が出ます。
  • といってもメモリの上限は kCellLimit という変数で設定してるので書き換えたらもっとメモリが使えます。

是非お試しください。

今日は観鈴ちんがゴールした日なのでBiwaSchemeでゲーム作った

水曜日, 8月 14th, 2013

という訳で、頑張ってゲームらしいゲームを作りました。

遊ぶ

まあ、過去(8年ほど前?)にDoCoMoの505i向けのiアプリとして書いたゲームの移植なんですが。