Gaucheで正規表現を使う

LLなら正規表現でパターンマッチや置換ができるのは当たり前だと思ってたら、Schemeの言語仕様に正規表現は含まれていないそうな。ただ、Schemeの一実装であるGaucheでは正規表現を使える。網羅は本家リファレンスに任せて、とりあえず使いそうな部分を適当に抜き出し。

正規表現オブジェクトは

#/〜/

と正規表現リテラルで記述するか、

(string->regexp "〜")

と文字列からの変換することで作成できる。

パターンマッチは

(rxmatch 正規表現 文字列)

または

(正規表現 文字列)

でテストできる。マッチしたら<regmatch>オブジェクト、しなかったら#f。
<regmatch>オブジェクトから一致した部分文字列等を取り出すにはrxmatch-*系の関数が使えるが、正規表現オブジェクトと同様に、<regmatch>オブジェクトも関数のように使用可能。
Rubyでいうところの以下のような処理は

if /(\w+)=(\w+)/ ~= string
  name = $1
  value = $2
end

Gaucheでは以下のように書ける。

(let
  ((match (#/(\w+)=(\w+)/ string)))
  (if match (begin
    (set! name (match 1))
    (set! value (match 2)))))

置換は

(regexp-replace 正規表現 元の文字列 置換文字列)
(regexp-replace-all 正規表現 元の文字列 置換文字列)

でできる。regexp-replaceは最初にマッチした部分のみを置換。regexp-replace-allは全てのマッチした部分を置換。置換文字列の代わりに1引数のプロシージャを与えると、マッチした部分を単純に文字列で置換する代わりに、<regmatch>オブジェクトを引数としてそのプロシージャを呼び出した結果で置換する。

Scheme第20歩

遅延評価の話その3。

まずは前回の訂正。
遅延リストを使った方のバージョンなら実際に大きなリストが作られることはないと書いたけど、大きなリストのようなものはできてしまう。…と言うのも、遅延リストを変数に取っておいているので、使用済みプロミスがGCに回収してもらえない。評価済みプロミスは値をキャッシュしているので、結局読み終えた行でも最後まで残ってしまう。ああ失敗。

さて、Scheme学習シリーズの最後は、遅延リストの発明済み車輪である、Gaucheのutil.streamを軽く転がしてみよう。Let's

(use util.stream)

まず名前。これまで遅延リストと呼んでいたものは、util.streamライブラリではストリーム(stream)と呼ばれている。そして、このライブラリが提供する名前にはstream-というプリフィックスが付けられている。

ストリームを操作する関数は、リストを操作する関数のストリーム版が大体用意されているので、mapやfilterを使う感覚でstream-mapやstream-filterを使えばよい。

ストリームを作成する関数も色々用意されている。ファイル読み出しにはport->streamを使えばよい。前回のlazy-read-linesに相当することは

(port->stream i read-line)

これだけで実現できる。ちなみにread-lineを省略すると、read-charを用いて1文字ずつ読み出すストリームになる。
簡単な等差数列ならstream-iotaで作成可能。

(stream-iota 5) ; 0, 1, 2, 3, 4
(stream-iota -1) ; 0, 1, 2, 3, 4, ...
(stream-iota -1 10) ; 0, 10, 20, 30, 40, ...
(stream-iota -1 1 2) ; 1, 3, 5, 7, 9, ...

第1引数がストリームの長さで、負の値を指定すると無限長となる。第2引数は初期値で、省略すると0。第3引数がステップで、省略すると1。
stream-tabulateを使えば、もう少し複雑なものも作れる。

(stream-tabulate 5 sqrt)) ; 0, 1, 1.414, 1.732, 2
(stream-tabulate -1 (lambda (x) (* x x))) ; 0, 1, 4, 9, 16, ...

第1引数がストリームの長さで、負の値を指定すると無限長。第2引数がストリームの値を生成する関数で、引数は0, 1, 2, ...とストリームを読み進めるに連れてインクリメントされていく。

util.streamの実装は*load-path*のどこかにutil/stream.scmとして置いてあるので、眺めてみると参考になる。

Scheme第19歩

遅延評価の話その2。

せっかく関数型言語を使うからには、カッコよく高階関数を使いたい。特にmapのようなリストを操作する関数を上手く使うと、実に簡潔に記述できることが多い。その一方で、問題の規模が大きくなると、大量のデータをリストで丸抱えするのは性能面で望ましくない。

そんな理想と現実の狭間に立たされたとき、仕方なく理想を捨てるしかないのだろうか？ いやいや、遅延評価が理想と現実の架け橋となってくれるのだ。

例えば、入力ポートiから読み込んだ各行を()で括って出力ポートoへ書き出すことを考えてみよう。まずは遅延評価を使わないバージョン。

(define (read-lines i)
  (let ((lines '()) (tail '()))
    (let loop ((line (read-line i)))
      (cond
        ((eof-object? line)
          lines)
        ((null? lines)
          (set! lines (cons line '()))
          (set! tail lines)
          (loop (read-line i)))
        (else
          (set-cdr! tail (cons line '()))
          (set! tail (cdr tail))
          (loop (read-line i)))))))
; main
(define all-lines (read-lines i))
(for-each
  (lambda (line) (display line o) (newline o))
  (map
    (lambda (line) (string-append “(“ line “)”))
    all-lines))

read-linesは読み込んだ全ての行をリストの形で返す関数。それを使って取得したall-linesに対して、mapを使って()で括ってからfor-eachで出力しているのだが、このコードの問題は入力を読み尽してから文字列操作や出力を行う点。入力が100万行あれば100万行の入力と100万行のmap結果を蓄えるメモリが必要になるし、入力元がユーザーのキーボードであれば、CTRL-D等で入力を止めるまでレスポンスが見えない。

それではいよいよ、遅延評価を使ってみよう。

(define (lazy-read-lines i)
  (delay
    (let ((line (read-line i)))
      (if (eof-object? line)
        '()
        (cons line (lazy-read-lines i))))))
(define (lazy-null? p) (null? (force p)))
(define (lazy-car p) (car (force p)))
(define (lazy-cdr p) (cdr (force p)))
(define (lazy-map f ls)
  (delay
    (if (lazy-null? ls)
      '()
      (cons (f (lazy-car ls)) (lazy-map f (lazy-cdr ls))))))
(define (lazy-for-each f ls)
  (let loop ((p ls))
    (unless (lazy-null? p)
      (f (lazy-car p))
      (loop (lazy-cdr p)))))
; main
(define all-lines (lazy-read-lines i))
(lazy-for-each
  (lambda (line) (display line o) (newline o))
  (lazy-map
    (lambda (line) (string-append "(" line ")"))
    all-lines))

メインの処理は、記述上は遅延評価版の関数(lazy-xx)を使うよう変更しただけに見えるが、実際には大きく異なる。lazy-xxでは単純なリストの代わりに、forceするとリストのように見えるプロミスを扱うのだ。以下、このプロミスを便宜上、遅延リストと呼ぶ。

遅延リストは、forceすると空リストかドット対になるプロミスである。ドット対だった場合、そのcarはリストの要素、cdrは残りの要素を表す遅延リストである。この遅延リストを使えば、forceしてリストの要素を参照してみるまで、その要素の評価を後回しにすることができる。今回の例では

1. displayするために、map結果の要素が1つ必要になる
2. map結果の要素を1つ求めるために、all-linesの要素が1つ必要になる
3. all-linesの要素を1つ求めるために、read-lineを1回実行する
4. read-line結果を()で括る
5. ()で括ったread-line結果をdisplayする

と、実際に大きなリストが作られることはなく、1行ずつ処理されるのだ。Marvelous!

当たり前の話ではあるが、本質的に後回しにできない処理は遅延評価でも改善できない。例えば全ての入力行をクイックソートして出力する場合、どう足掻いても、まずは全ての行を読むしかない。

Scheme第18歩

さて、Scheme学習シリーズもそろそろ延べ3週間なので、ぼちぼち締めに入ろう。最後は遅延評価の話。

多くのプログラミング言語は、基本的に前から順にプログラムを実行していく。Schemeも例外ではなく、例えば

(clip x (+ y 10) z))

という記述があったら(そしてclipがスペシャルフォームではない通常の関数であったら)、

1. xを評価
2. yを評価
3. 10を評価
4. y, 10を引数として+を呼び出し((+ y 10)を評価)
5. zを評価
6. x, (+ y 10), zを引数としてclipを呼び出し((clip x (+ y 10) z)を評価)

という順番で評価していく。

ここで、例えばclipが以下のように定義されているとする。

(define clip (lambda (min max v)
  (cond
    ((<= v min) min)
    ((>= v max) max)
    (else v)
  )
))

まあ、何の変哲もないクリッピングなのだが、ここで前出の

(clip x (+ y 10) z))

をx=0, y=100, z=-10として評価することを考えてみる。すると、condの最初の条件が早々に満たされるので、maxの値(+ y 10)は折角計算したにも関わらず、結果的には使われない。

こんなとき、値が必要になるまで式の評価を後回しにしようというのが遅延評価の考え方。必要にならなければ無期限後回しとなるので、結果として無駄な計算を行わずに済むというわけ。

Schemeで遅延評価を行うには、delayとforceを使う。

(define x 100)
(define p (delay (+ x 1))
(set! x 1000)
(print (force p)) ; 1001

上の例では(+ x 1)の評価をdelayで後回しにして、printする際にforceで評価させている。この例のpのようにdelayで遅らせた式を表現するオブジェクトのことを、Schemeではプロミスと呼ぶ。
注意すべきは、プロミスは評価値をキャッシュしている点。上記のコードに続いて

(set! x 2000)
(print (force p)) ; 1001

と実行しても、既に1度forceされているプロミスpは、自身の評価値が1001であると記憶しているので、改めて(+ x 1)を評価して2001となることはない。

なお、プロミスではない式をforceすると、単純にその場でその式を評価したのと同じ値となる。よって、

(let ((p xx)) (if (promiss? p) (force p) p))

のようにプロミスかどうかを判定せずとも

(force xx)

でよい。

…締め切れてないので、もうちょっと続く。

Scheme第17歩

モジュールの話。
今更言うまでもなくモジュール化はコードの再利用に有効だが、Gaucheにもその機能は備わっている。…と言うか、実は全ての定義は何かしらのモジュールに属していて、基本的には同じモジュールに属するもの同士が互いに見える。今までグローバルな定義として扱ってきた

(define var 10)

等は、厳密にはuserという名前のモジュールに属する。

モジュールの定義は

(define-module モジュール名 モジュール本体...)

とする。
定義したからには当然使いたいところだが、モジュール使い方は大きく分けて2種類ある。1つはカレントモジュールの変更。もう1つは外部モジュールの参照。

カレントモジュールを変更する。すなわち、使いたいモジュールの中に入ってしまえば、これまで居たモジュールの内部が見えなくなる代わりに、新たに入るモジュールの内部が見えるようになる。

(select-module モジュール名)

とすると、それ以降(からファイル終端まで)のフォームは指定したモジュール内で評価される。また、

(with-module モジュール名 フォーム...)

とすると、カレントモジュールを一時的に変更して、指定したフォームを評価する。

カレントモジュールを変更することなく参照できる外部モジュールを参照する方法の1つにimportがある。

(define-module foo
  (export visible1 visible2)
  (define visible1 100)
  (define visible2 200)
  (define invisible 300)
)
(import foo)
(print visible1 visible2)
(print invisible) ; エラー

このようにモジュールをimportすると、exportされているシンボルのみがカレントモジュールから見えるようになる。importにオプションを与えれば、細かい見え方の制御も可能。
なお、モジュールの定義を同名のファイルに記述しておけば

(require “foo”)
(import foo)

とする代わりに、useマクロを利用して

(use foo)

と簡潔に記述できる。

exportを使うと、外部モジュールをより密接にカレントモジュールに取り込む。

(define-module bar
  (export exported)
  (define exported 1000)
  (define not-exported 2000)
)
(define-module baz
  (extend bar)
  (export disp)
  (define disp (lambda () (print exported not-exported)))
)
(import baz)
(print exported)
(disp)
(print not-exported) ; エラー

例えば上記の例では、barをextendしたbazの中では、barのexportedとnot-exportedの両方が見える。またbazもexportedをexportしたことになる。しかし、not-exportedはexportされていないので、bazをimportしただけのカレントモジュールからは見えない。
exportするモジュールは複数指定可能。また、exportはuseと同様、指定したモジュールのファイルがまだロードされていなかったらロードする。

Scheme第16歩

別ファイルにあるコードを利用する話。

誰かが書いたコードを利用して新しいプログラムを作りたいとき、

(load ファイル名)

が最も基本的な手段。これで、指定したファイルからSchemeのコードを読み出して評価する。サフィックス.scmは省略可能。

loadより高級なのがrequire。

(require フィーチャー名)

とすると、指定されたフィーチャーがまだロードされていなければロードする。フィーチャー名というのは、ファイル名からサフィックスを取り除いたもの。

Gaucheでロード時の探索先ディレクトリは

• 環境変数GAUCHE_LOAD_PATH
• goshの-Iオプション
• (add-load-path ディレクトリ名)

で追加できる。また、現在の探索ディレクトリは変数*load-path*で確認できる。

Scheme第15歩

だらだらやってるうちに3週目に入ってしまったので、そろそろ実用的なところへの着地を考える。コマンドライン引数の話。

ちょいとしたスクリプトを書くにあたって、コマンドライン引数を使いたい場合は多い。そこで、Gaucheで引数を取得する例。

#/usr/bin/env gosh
(define main
  (lambda (args)
    (let loop
      ((as args))
      (unless (null? as)
        (print (car as))
        (loop (cdr as))
      )
    )
  )
)

mainという名前のプロシージャは特別で、存在すればコマンドライン引数のリストとともに呼び出される。上のスクリプトを適当なファイルに保存して、実行可能属性を付けて実行すると、goshのコマンドライン引数。すなわち、スクリプトファイル名と(存在すれば)その引数が1行ずつ表示される。
なお、mainの評価値が整数なら、それがgosh自身の終了ステータスとなる。

インデントの付け方に、未だに迷ってる…。

Scheme第14歩

継続の話その2。

C言語等のスタックに慣れていると、ぎょっとするようなことができてしまう。

(define cont 0)
(let loop
  ((i 0) (sum 0))
  (if (> sum 1000)
    (begin (call/cc (lambda (c) (set! cont c))) (print "i=" i ", sum=" sum))
    (loop (+ i 1) (+ sum i))
  )
)

このコード。call/ccを除くと、0+1+2+3+...と1000を越えるまで足し込んでいるだけ。また、call/ccで実行されるプロシージャの中では、渡された継続cを変数contに取っておいてるだけで、継続自体の呼び出しはしていない。したがって、このコードを実行してもcall/cc部では特に何も起きずに、

i=47, sum=1035

と表示される。まあ、ここまではいいとして、問題はここから。
上のコードを実行すると、変数contにはprintする直前の継続が収められる。そこで

(cont)

と継続を呼び出すと、 何と再び

i=47, sum=1035

と表示されてしまう。

…物心ついたときからクロージャがあるような世代には当たり前かもしれないが、古い言語の場合、ある変数のスコープから抜けたとき、その変数のために割り当てていたメモリはさっさと明け渡される。例えばC言語でsetjmp/longjmpを使って同じようなことをやろうとしても、iやsumはループを抜けた時点で電子の藻屑になっている可能性がある。そのため、仮にlongjmpで戻っても同じ値が表示される保証が全くない。

1度スコープを抜けても変数が消滅しないからこそ、Schemeでは継続を使って縦横無尽に飛び回れるのだ。

Scheme第13歩

継続の話その1。
call-with-current-continuation、略してcall/ccの基本的な使い方。

(call/cc プロシージャ)

こうすると、引数として与えられたプロシージャが実行される。…だけなら話は簡単なのだが、それではwith-current-continuationが黙っちゃいない。プロシージャを実行するとき、その引数としてその時点での継続というものが渡される。

継続とは、ある瞬間の実行環境のスナップショットのようなもの。大雑把な言い方をすると、C言語のsetjmpで取得する情報をもうちょっとリッチにしたようなもの。Cの場合、setjmpで取得した情報を使うにはlongjmpという専用の関数を使うけれど、Schemeの場合は継続そのものが関数の形で得られる。そしてその継続を普通の関数のように呼び出すと、longjmpのように行ったきり戻らない。

一例として、リストlsの中から最初に見つけた3の倍数をprintするコードを、無理矢理call/ccを使って書いたもの。

(define ls '(11 17 5 6 21 31 33))
(print (call/cc (lambda (c)
  (let loop ((l ls))
    (cond
      ((eq? ls '()) #\x)
      ((= 0 (mod (car l) 3)) (c (car l)))
      (else (loop (cdr l)))
    )
  )
)))

実行時、call/ccの引数の無名プロシージャの仮引数cには継続が入っている。なのでこのcを実行すると、どんなにループやらなにやらがネストしていようともcall/ccの呼び出し箇所、今回の例では何かprintしようとしているところに飛んでいく。

Scheme第12歩

OOPの話。
まずはクラスの定義。

(define-class クラス名 (スーパークラス名 ...)  (スロット定義 ...))

クラス名とスーパークラス名はそのまんまの意味だからいいとして、スロットという見慣れない言葉の正体は、他の言語で言うところのクラスメンバのようなもの。オプション次第でインスタンス変数になったり、クラス変数になったりする。
クラスのインスタンスを作成するには

(make クラス名)

とする。また、インスタンスのスロットにアクセスするには

(slot-ref インスタンス スロット名)
(slot-set! インスタンス スロット名 値)

とする。

例えば、このように使う。

(define-class <animal> () (name (age :init-value 0)))
(define an-animal (make <animal>))
(slot-set! an-animal 'name "Nanashi")
(print (slot-ref an-animal 'age))

スロット定義は、名前だけ指定すれば単なるインスタンス変数となる。(名前 オプション ...)の形で定義すると、初期値やらgetterやらsetterやらを指定できる。が、他の言語にあるようなアクセス権はないので、カプセル化に関しては使う側の良識に依存している。
なお、クラス名を<>で括っているのは単なる慣例であって、文法上必要なわけではない。

ちょいと継承も使ってみよう。

(define-class <fish> (<animal>) ((in-saltwater? :init-value #f)))
(define-class <bird> (<animal>) ((fly? :init-value #t :init-keyword :fly? :getter is-able-to-fly?)))
(define carp (make <fish>))
(define a-penguin (make <bird> :fly #f))
(print (slot-ref carp 'age))
(print (is-able-to-fly? a-penguin))

スーパークラスのスロットも、サブクラスで追加したスロットも、同じように使える。

問題は多態性。Schemeの場合、他の多くの言語のようにメソッドがクラスに含まれるわけではなく、名前は同じだが引数のタイプや数が異なる関数の多重定義によって、多態性を実現する。ジェネリック関数と呼ばれるこのタイプの関数は

(define-method 関数名 (引数 ...) 処理内容 ...)

と定義する。例えば

(define-method bark ((a <dog>)) (print "bow"))
(define-method bark ((a <cat>)) (print "mew"))

とすると、引数が<dog>クラスのインスタンスなら"bow"と吠え、<cat>クラスのインスタンスなら"mew"と鳴く、bark関数が定義される。
大事なことなので2度書くが、ジェネリック関数はクラスの中にある特別な関数ではない。なので、特別に名前のみでスロットにアクセスできたりするようなことはない。

Scheme第11歩

ベクタと連想リストの話。

まずは、序盤にさらりと触れたっきりだったベクタについて。ベクタとは固定長の配列。作成するには#()リテラルか

(vector 要素 ...)
(make-vector 要素数)
(make-vector 要素数 各要素の初期値)

を使う。make-vector初期値を省略すると#<undef>になる模様。
こうして作成したベクタの長さは

(vector-length ベクタ)

で得られる、要素の取得と設定は

(vector-ref ベクタ インデックス)
(vector-set! ベクタ インデックス 設定したい値)

とする。ベクタのインデックスは0オリジン。例えば、長さが10なら有効なインデックスは0～9。vector-refもvector-set!も、無効なインデックスの値を指定するとエラーとなる。
ベクタの複製は

(vector-copy ベクタ)
(vector-copy ベクタ 先頭インデックス)
(vector-copy ベクタ 先頭インデックス 末尾インデックス)

で行う。先頭インデックスは省略すると0、末尾インデックスは省略すると(長さ-1)となる。インデックスが範囲外を指し示した場合、無効なインデックスに対応する要素は#<undef>。
ベクタからリストへ、リストからベクタへの変換は

(vector->list ベクタ)
(list->vector リスト)

とする。

ベクタとリストの使い分けは、まあ適材適所か。処理系の実装依存ではあるだろうけれど、大量のデータをランダムアクセスする場合はベクタが向いているだろう。一方、 伸ばしたり縮めたり、千切ったり繋げたりするのはリストの得意技。

連想リストはドット対のリスト。ベクタのように専用の型があるわけでなく、あくまでリストの一種。他のリストとの違いは、連想リスト専用の探索関数が用意されていること。例えば

(define al '((foo . 123) (bar . 456) (baz . 7890)))

という連想リストに対して

(assq 'bar al)

とすると、

(bar . 456)

という値が得られる。要するに、他の言語で言うところの連想配列と同じようなもの。ただし実装はあくまで連結リストなので、探索時間はO(n)。
連想リストの探索関数にはassq, assv, assocがある。これらの違いはキーの比較方法。前から順にeq?, eqv?, equal?で比較する。

Scheme第10歩

マクロの話ファイナル。
これまでのマクロの話は、low-levelとかtraditionalとか言われているタイプのマクロに関するもので、今では新しいマクロ定義の方法がある。今回は新しい方のマクロについて。

もう1つの新しいマクロはhygienic macroと呼ばれているもの。日本語だと衛生的マクロとか健全なマクロと訳されているみたい。新しいとは言ったものの、1998年の規格(R5RS)で定まったものらしいので、実はそんなに新しくもない。

前置きはこのくらいにして、早速使ってみる。

(define-syntax for   (syntax-rules (in to)
    ((_ x in xs body ...)
      (for-each (lambda (x) body ...) xs))
    ((_ i a to b body ...)
      (if (<= a b)
        (let loop ((i a)) (when (<= i b) body ... (loop (+ i 1))))
        (let loop ((i a)) (when (>= i b) body ... (loop (- i 1))))
      )
    )
  )
)

ここで定義したはforというマクロは、以下のように使用する。

(for v in '(foo bar baz) (print v))
(for c 1 to 10 print c)
(for n 100 to 10 print n)

上から順にfoo, bar, bazと表示。1, 2, ..., 10と表示。100, 99, ..., 10と表示する。

さて、いよいよマクロ定義の中身を見てみよう。
最初のdefine-syntaxは、define-macroの新型みたいなもの。次のforが定義したいマクロの名前。ここまではいいとして、問題はその次のsyntax-rules。
syntax-rulesの第1引数は、シンボルのリスト。ここで列挙したシンボルは、第2引数以降のパターンマッチの際、予約語として扱われる。
syntax-rulesの第2引数は、((パターン) 置換テンプレート)の形。指定したパターンにマッチしたら置換テンプレートを適用して得られたフォームに置換することを意味する。
パターンの中では、予約語は予約語そのものにマッチする。また、'...'は 0個以上の可変個数のフォームにマッチする。そしてそれ以外は、任意の1つのフォームにマッチする。
上記の例ではパターンの先頭に'_'があるが、これも単なる変数の1つでしかない。しかも、結局はマクロ名forにしかマッチしないので、 '_'から得られる情報は実質ゼロ。そんなどうでもいい変数の名前として '_'を使用する習慣があるようなので、今回はそれに倣ってみた。
置換テンプレートの中身は、ほとんど見た目通り。パターンの中で使用した変数は対応するマクロの実引数に置き換えられ、それ以外はそのまんま。これまでのlistやquoteを駆使してきたマクロと比べると、格段に見やすい。
syntax-rulesの第3引数以降は、 第2引数と同じ書式。要するに、複数の置換ルールを定義できるのだ。上記のforの例では、inを使う形式とtoを使う形式をまとめて定義している。

ちなみに、hygienicと呼ばれるからには単なる便利なラッパーというわけではない。新しい方法で定義したマクロでは、明示的にgensymを使わなくても自動的に名前の衝突を避けてくれる。

Scheme第9歩

マクロの話その3。
マクロの中でローカル変数を使いたい場合。例えば２つの変数の値を入れ替えるマクロを、単純にletを使って書くとこうなる。

(define-macro
  swap (lambda (a b)
    `(let ((tmp ,a)) (set! ,a ,b) (set! ,b tmp))
  )
)

これを

(define x 10)
(define y 20)
(swap x y)
(print "x=" x ", y=" y)

このように使用すれば、期待通りxとyが入れ替わってくれるのだが、

(define foo 100)
(define tmp 200)
(swap foo tmp)
(print "foo=" foo ", tmp=" tmp)

このように使用すると、fooとtmpが入れ替わってくれない。何が起こったかは、マクロを手動で展開してみると一目瞭然。

(let ((tmp foo)) (set! foo tmp) (set! tmp foo))

fooはローカル変数tmpに保存した値を書き戻しただけだし、letの外のtmpは参照すらされていない。

要するに、マクロの引数とローカル変数の名前がかぶると、引数が内側から見えなくなる問題が起こる。ならば、引数とは絶対にかぶらない名前をローカル変数に付けてやればよい。そこで出てくるのがgensym。gensymは評価するたびにユニークなシンボルを返すので、これをローカル変数名として使ってやればよい。

(define-macro
  swap2 (lambda (a b)
    (let ((tmp (gensym)))
      `(let ((,tmp ,a)) (set! ,a ,b) (set! ,b ,tmp))
    )
  )
)

ぱっと見、最初のswapと似てはいるが、ローカル変数tmpの役割がまるで違うことに注意。gensym使用版swap2のtmpは、マクロ展開時に使用するローカル変数。そしてtmpが保持するのはaの値ではなく、aの値を保持する変数の名前。tmpはunquoteされているので、マクロの展開結果にtmpは現れない。

Scheme第8歩

マクロの話その2。
マクロはそのプロシージャの実行結果で置換されるのだが、実行結果が所望のS式になるようにあちこちquoteして周るのは、なかなか面倒かつややこしい。それを多少は改善してくれるのがquasiquote。

quasiquoteは、ほとんど全部quoteしたいのだけれど、部分的にquoteしたくない要素もあるリストを構築するとき、便利なもの。quasiquoteの中で例外的にquoteしたくない部分をunquoteする。リストの展開まで行うunquote-splicingも使える。

手っ取り早く使用例。第2引数のリストの合計に第1匹数を掛けるマクロを、まずはquasiquoteを使わずに定義してみる。

(define-macro
  gained-sum
  (lambda (a xs) (list '* a (apply list '+ xs)))
)

このマクロを

(gained-sum 10 (1 2 3 4 5))

のように使用すると、

(* 10 (+ 1 2 3 4 5))

と展開されるのだが、まあ、はっきり言ってマクロ定義は分かりにくい。そこでquasiquoteを使うと、

(define-macro
  gained-sum-qq
  (lambda (a xs) `(* ,a (+ ,@xs)))
)

マクロ定義が、マクロ展開結果にだいぶ近付いて見える。
ちなみに`xは(quasiquote x)、,xは(unquote x)、,@xは(unquote-splicing x)の略記法。専ら略記法しか使わなさそうだが。

マクロ内で使用するローカル変数の話は、次回に持ち越し。

Scheme第7歩

マクロの話その1。
Schemeのマクロはややこしい。しかも、ややこしい点が複数あるから、余計にややこしい。しかしまあ、ややこしいと繰り返してもややこしいだけなので、1つずつややこしい点を解消していこう。

まずはマクロの定義。

(define-macro マクロ名 プロシージャ)

これだけ見れば、別にグローバルな名前付きプロシージャの定義とほとんど同じように見えるが、問題はその展開。
C言語のマクロは、マクロの定義に従って参照個所を機械的に置換するだけだが、Schemeのマクロはdefine-macroで定義したプロシージャの中身で置換する、…わけではない。プロシージャの実行結果で置換するのだ！

例えば、以下のコードについて考えてみよう。

(define foo ‘bar)
(define bar “bar is bar”)
(define-macro foo-macro1 (lambda() ‘foo))
(define-macro foo-macro2 (lambda() foo))
(print “foo-macro1 = ” (foo-macro1))
(print “foo-macro2 = ” (foo-macro2))

foo-macro1のプロシージャの実行結果はfooというシンボル。foo-macro2のプロシージャの実行結果はfooの評価値、すなわちbarというシンボルである。これをふまえて手動でマクロ展開すると

(print “foo-macro1 = “ foo)
(print “foo-macro2 = “ bar)

となる。
…と、ここまではあくまで前処理で、この展開結果を実行するのが本番。したがって、最終的には

foo-macro1 = bar
foo-macro2 = bar is bar

と、fooの評価値とbarの評価値が表示される。

次に引数付きマクロの例。

(define-macro p (lambda (x) (list ‘print x)))
(let loop ((i 1))
  (when (<= i 10)
    (p i)
    (loop (+ i 1))
  )
)

マクロが展開されるとき、マクロの仮引数の値は(quote 実引数)である模様。なので、上記の例を手動で展開すると

(let loop ((i 1))
  (when (<= i 10)
    (print i)
    (loop (+ i 1))
  )
)

となり、めでたく1〜10が表示される。ここでもし、マクロ定義のクォート等を怠るとどうなるか。

(define-macro p2 (lambda (x) (print x)))
(let loop ((i 1))
  (when (<= i 10)
    (p2 i)
    (loop (+ i 1))
  )
)

このマクロp2は(print ‘i)の実行結果、すなわち#<undef>に展開されるので、実行しても10回#<undef>が評価されるだけ。こうならないためにも、マクロは基本的に実行結果がS式になるように定義するのだ。

…とはいえ、listやquoteを使って巧い具合にS式になるようにマクロを定義するのは、結構面倒。そこで出てくるのがquasiquoteなのだが、長くなってきたので次回に続く。

Scheme第6歩

I/Oの話。
まずはポート(port)について。他の言語ではファイルハンドルとかストリームとか呼ばれているものを、Schemeではポートと呼ぶ。ポートの扱いは他の言語のファイルと同様、オープン→読み/書き→クローズという流れ。

入力ファイルのオープンは

(open-input-file "filename")

出力ファイルのオープンは

(open-output-file "filename")

で行う。これらは第2引数以降に細かいオプションを指定可能。

文字列をポートとして扱うことも可能。

(open-input-string "string")

で取得した入力ポートからは、第1引数に指定した文字列が読みだされる。また

(open-output-string)

で取得した出力ポートに書き込んだデータは、

(get-output-string)

で文字列として取得することができる。なお、get-output-stringは副作用がない。

読み書きの前にクローズ。入力ポートiのクローズは

(close-input-port i)

出力ポートoのクローズは

(close-output-port o)

とする。

さて、いよいよ読み書き。まずは主だったプロシージャを列挙する。

read-char i	入力ポートiから1文字読み込み
read-line i	入力ポートiから1行読み込み
read-byte i	入力ポートiから1バイト読み込み
read-block n i	入力ポートiからnバイト読み込み
read i	入力ポートiからフォームを1つ読み込み
write-char c o	出力ポートoへ文字cを書き出し
write-byte b o	出力ポートoへバイトデータbを書き出し
write f o	出力ポートoへフォームfを書き出し
display f o	出力ポートoへフォームfを人間が読みやすい形で書き出し
newline o	出力ポートoへ改行文字を書き出し

いずれも、入力ポートの指定を省略すれば標準入力(standard-input-port)が、出力ポートの指定を省略すれば標準出力(standard-output-port)が使用される。ついでに、標準エラー出力は(standard-error-port)。

write, readについて補足。writeはフォームをSchemeの処理系が解釈できる形の文字列にして書き込む。readはその逆で、処理系が解釈できるようなフォームの文字列表現を読み出す。

ポートのクローズの面倒を見てくれる、Rubyでいうブロック付きIO.openのようなものがSchemeにもある。

(call-with-input-file "filename" (lambda (i) ...))
(call-with-input-string "string" (lambda (i) ...))
(call-with-output-file "filename" (lambda (o) ...))
(call-with-output-string "string" (lambda (o) ...))

いずれも第1引数に従ってポートをオープンし、そのポートを引数とする第2引数のプロシージャを呼び出した後、ポートをクローズする。

Scheme第5歩

ループと再帰の話。
まず、他の言語によくあるforやwhileのようなものはSchemeにはない。なので、ループに相当するコードは再帰で書く。それだと10000回ループしたらどんだけスタックを食い潰すんだ？ …と、手続き型言語に慣れたプログラマなら心配するところけれど、Schemeは末尾再帰をループにすることを言語仕様で定めているそうな。

再帰であろうとなかろうと、プロシージャの呼び出し方には違いはないが、問題はプロシージャの定義の仕方。

(define sum (lambda (x) (if (= x 0) 0 (+ x (sum (- x 1))))))

このようにグローバルなら別に問題ないのだが、問題はローカルな再帰プロシージャを定義したい場合。letにしてもlet*にしても、ローカル変数の初期値を評価するところからは、そのローカル変数自信が見えない。そこでletrecを使う。

(letrec
  ((sum (lambda (x) (if (= x 0) 0 (+ x (sum (- x 1)))))))
  (display (sum 10))
  (newline)
)

letrecの第1引数はletと同じフォーマットに見えるが、そこで導入されたローカル変数を評価するときは、letと違ってローカル変数を参照できる。

(letrec ((c (+ b 1)) (b (+a 1)) (a 1)) (display c))

この例ではc, b, aという定義の順番にとらわれることなく

a = 1
b = 2
c = 3

となる。

ややこしいのが名前付きlet。

(let loop ((i 10) ...)

は

(letrec ((loop (lambda (i) ...))) (loop 10))

と同じ。例えば1から10まで表示する場合、名前付きletを使うと

(let disp ((i 1)) (display i) (newline) (unless (= i 10) (disp (+ i 1))))

と書ける。

改めてletを見てみると、letの中でのみ有効な名前付きのプロシージャを定義して呼び出すことこそ、letの本質のように思えてきた。そう考えると、ローカル変数はあくまでプロシージャの仮引数機能で作っているだけのように見える。

Scheme第4歩

変数のスコープの話。

まず、これまで使って来た

(define global-variable 100)

はグローバル変数の定義。そして、プロシージャの話のところでさらりと書いたけれど、lambdaの仮引数はその中でのみ有効なローカル変数。

さて、(今のところ)ブロックスコープの無いJavaScriptだと、ブロックの代わりに

js> (function() {...})();

みたいなことをやるけれど、Schemeもlambdaを使わないと新たなスコープを導入できないのか？ というと、そんなことはない。

(let
  ((a 1) (b 2) (c 3))
  (display (+ a b)) (newline)
  (display (+ b c)) (newline)
  (display (+ c a)) (newline)
)

このようにletを使うと、最初の引数に従って

a = 1
b = 2
c = 3

という3つのローカル変数が作られた上で、2番目以降の引数のフォームが評価される。

ここで、このローカル変数の初期値を評価するときのスコープはletの外側のものであることに注意。

(let

  ((a 1))

  (let

    ((a 2) (b a))

    (display b) (newline)

  )

)

この内側のletのローカル変数bを初期化するときのaは、あくまで外側のa。従って、これを評価すると2ではなく1と表示される。もし内側のbを初期化するとき、直前に初期化された内側のaの値を使いたければ、let*を使う。

(let*  ((a 1) (b (+ a 1)) (c (+ b 1))) ...)

は

(let ((a 1))
  (let ((b (+ a 1)))
    (let ((c (+ b 1))) ...)
  )
)

と等価。

さて、ここまではグローバル変数やローカル変数を定義してばかりだったが、変数なので値を変更することも当然できる。その方法は、グローバルかローカルかには依存せず

(set! 変数名 新しい値)

とする。set!はあくまで値の再設定なので、新しい変数の導入にset!は使えない。

ここで、なぜ変数の定義には初期値が必要なのか？ setではなくset!なのか？ おそらく、あまり変数の再設定はするなという思想を反映しているんじゃないかな。

…とは言え、今でこそ変数の再利用は保守性を下げる悪癖でしかなくなったけれど、コンパイラが賢くない時代においてはメモリ節約のテクニックだった。Schemeはかなり歴史のある言語のようだけど、昔からあえて再設定を醜くしていたのなら、慧眼だなぁ。

後発のHaskellですら、変数を再設定させない仕様は冒険だったと思う。嫌いじゃないけど。

Scheme第3歩

制御構文について。まずはif。

(if 条件フォーム 真のとき評価されるフォーム 偽のとき評価されるフォーム)

これは、C言語で言うところの3項演算子。いちいちフォームと書いたのは、いずれもS式である必要がないから。偽のとき評価されるフォームは省略可能。なお
(if #f "never evaluated")
をGaucheで評価すると、#<undef>という値が返ってくる。

whenとunlessはifの亜種。

(when 条件フォーム フォーム1 フォーム2 フォーム3 ...)

は

(if  条件フォーム (begin フォーム1 フォーム2 フォーム3 ...))

と等価。unlessはwhenの真偽反転版で、

(unless 条件フォーム フォーム1 フォーム2 フォーム3 ...)

は

(when (not 条件フォーム) フォーム1 フォーム2 フォーム3 ...)

と等価。

次はcond。これはifのネストの略記版で、

(cond
  (条件フォーム1 フォーム1-1 フォーム1-2 ...)
  (条件フォーム2 フォーム2-1 フォーム2-2 ...)
  (else フォーム3-1 フォーム3-2 ...)
)

は

(if 条件フォーム1 (begin フォーム1-1 フォーム1-2 ...)
  (if 条件フォーム2 (begin フォーム2-1 フォーム2-2 ...)
    (begin フォーム3-1 フォーム3-2 ...)
  )
)

と等価。

最後にcase。これはC言語で言うところのswitchのようなもの(Cの場合、switchは式ではないので値を持たないが)。

(case 対象フォーム
  ((一致条件フォーム1-1 一致条件フォーム1-2 ...)
     フォーム1-1 フォーム1-2 ...
  )
  ((一致条件フォーム2-1 一致条件フォーム2-2 ...)
     フォーム2-1 フォーム2-2 ...
  )
  (else フォーム3-1 フォーム3-2 ...)
)

無理矢理condで書くと

(cond
  ((or
    (equal? 対象フォーム 一致条件フォーム1-1)
    (equal? 対象フォーム 一致条件フォーム1-1) ...)
      フォーム1-1 フォーム1-2 ...
  )
  ((or
    (equal? 対象フォーム 一致条件フォーム2-1)
    (equal? 対象フォーム 一致条件フォーム2-1) ...)
      フォーム2-1 フォーム2-2 ...
  )
  (else フォーム3-1 フォーム3-2 ...)
)

となる。ただし、手元のGaucheで試してみた限り、caseだと対象フォームは一度しか評価されない。なので、対象フォームの評価に副作用がある場合は、condで書いた結果と一致する保証は無い模様。

Scheme第2歩

自分の言葉でちびちびまとめていくとは書いたものの、さすがに用語はScheme界隈のものにあわせておこう。

S式(s-expression)

前回の説明は不正確で、とにかく0個以上の要素を()で括ればS式。

フォーム(form)

Schemeのプログラムの断片。S式もフォームだが、S式の中の1つ1つの要素もフォーム。

リスナー(listener)

フォームを評価するもの。

手続き、プロシージャ(procedure)

実行可能なフォーム。他の言語で言うところの関数のようなもの。

さて、ここからはこのプロシージャの話。
まずは作成。

(lambda (x) (display (string-append "Hello " x)))

これはJavaScriptに例えると

js> function (x) { alert("Hello " + x); }

のように無名の関数オブジェクトを作成しているだけ。JavaScriptでいうところの

js> hello = function (x) { alert("Hello " + x); };

のように、何らかの名前を付けてやりたければこうする。

(define hello (lambda (x) (display (string-append "Hello " x))))

これで

(hello "World")

のように呼び出せる。引数のスコープは、普通にプロシージャの中のみ。

プロシージャの引数に付いて補足。
引数を1個取りたければ

(lambda (a) (display a))

2個取りたければ

(lambda (a b) (display (+ a b)))

3個取りたければ

(lambda (a b c) (display (+ a b c)))

4個取りたければ…(以下略)。

問題は可変引数。2個以上取りたければ

(lambda (a b . c) (display (apply + a b c)))

1個以上取りたければ

(lambda (a . b) (display (apply + a b)))

0個以上取りたければ

(lambda a (display (apply + a)))

とする。

あるかどうか分からない残りの引数が可変長のリストの形で渡されるというのは、まあよくある話だからいい。が、その表記は分かりづらいので、実例を挙げて頭の中を整理する。

(define foo (lambda (a b . c)) (略)))

この引数リストをドット対で表現すると

(a . (b . c))

となる。一方、このプロシージャを

(foo 1 2 3 4)

と呼ぶときの引数リストをドット対で表現すると

(1 . (2 . (3 . (4 . ()))))

となる。よって、その対応付けは

a = 1
b = 2
c = (3 . (4 . ())) = (3 4)

となるわけか。

0個以上の可変引数に()が無いのは決して付け忘れでない。例えば

(define bar (lambda a (略)))

これを

(bar 1 2 3)

と呼ぶときは

a = (1 2 3)

となり、

(bar)

と引数無しで呼ぶときは

a = ()

となる。

なぜ0個以上の可変引数を()で括ると駄目なのかは、やはり引数リストをドット対表記で考えてみれば分かる。

(define baz (lambda (a) (略)))

の引数は

(a . ())

なので、引数が0個。すなわち引数リストが

()

に対して、引数を対応付けようがない。