レコードもどきを作る

プログラミング言語 Scheme にはレコードという機能がある。 他の言語で構造体などと呼ばれるようなものに似ている。 単に複数のオブジェクトの集合体ということであればリストやベクタで出来てしまうし、 SICP でレコードは用いられない (SICP が書かれた時代は R5RS までしかなく、 R5RS にはレコードはない) ということもあってか、レコードが軽視されている印象があるのだが、コードのわかりやすさにかなり貢献すると私は考えている。

レコードが欲しいとき

ではレコードがどんなときに欲しいか SICP の中からキューを例にとってみよう。

http://sicp.iijlab.net/fulltext/x332.html

SICP の 3.3.2 で定義されているキューはリスト、そしてそのリストの先頭要素と末尾要素を指すペアから成る。 キューのオブジェクトを生成する手続きはこうなっている。

(define (make-queue) (cons '() '()))

make-queue の生成するペアの car フィールドが先頭要素を、 cdr フィールドが末尾要素を指しているのだが、コンストラクタだけを見てもそれを読み取ることは出来ない。 更にアクセサを見て初めてそれぞれが意味するところがわかる。

(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))

データのそれぞれが意味するところはデータを操作しているところを見るまでわからないので、データ構造をコードだけ見て理解しづらい。 データ構造やその要素に名前を付け、また同時にアクセサと関連付けたいと考えるのは自然なことではないだろうか。 データ構造とアクセサ、モディファイアは不可分なものだろう。

レコードを使ってみる

上で引用したコードについて R7RS の define-record-type を用いて書くなら以下のようになる。

(define-record-type <queue> (%make-queue front rear) queue?
  (front front-ptr set-front-ptr!)
  (rear  rear-ptr  set-rear-ptr!))

(define (make-queue) (%make-queue '() '()))

コンストラクタ、アクセサ、モディファイアが一度に定義され、関係がより明白だ。

ちなみに、残念ながら R7RS の define-record-type はデフォルト値を指定して要素を初期化する機能がないのでここでは二段階に分けたが、 R6RS の define-record-type はより高度な機能を持っていてこれを解決できる。

レコードの使い難さ

Scheme では、取り扱えるオブジェクトの一部をデータ値 (datum value) と呼んでいる。 仕様の中でこの用語を定義しているのは R6RS だけのようだが、概念的には R5RS や R7RS でも同じような考え方があるのでここではデータ値という用語を使うことにする。

データ値とは、 write 手続きで書出して read 手続きで読出したオブジェクトが書出し前の値と等しいことが保証されているオブジェクトである。 リテラル表記が可能な値と考えてもよいだろう。

具体的には

• 真偽値
• 数値
• 文字
• シンボル
• 文字列
• 以上を要素とするようなリストやベクタ

といったようなものだ。

Scheme の仕様上はレコードはデータ値ではない。 read で復元できないだけで、処理系によっては write で要素まで表示してくれることもあるが何も保証はないので移植性のある形でレコードを表示したいのであれば各要素を取出して表示する必要がある。

例えばこのようなコードを実行してみよう。

(import (scheme base) (scheme write))

(define-record-type alt-pair (kons x y) kons?
  (x kar set-kar!)
  (y kdr set-kdr!))

(write (kons 1 2))

Gauche はこのように表示する。

#<alt-pair 032a4660>

オブジェクトを一意に識別するアドレスを表示するだけでその内容までは表示してくれない。 Sagittarius でも同様である。

Foment は要素まで表示してくれる。

#<(alt-pair: #x9e0730 x: 1 y: 2)>

プログラムの完成段階であればともかく、試行錯誤の段階ではデータ構造を write ひとつで書出せると実に楽なので、レコードよりもリストを使ってしまいがちになる。

マクロで作るレコードもどき

データ値にレコードの構文をかぶせるマクロを作るという方法を私は考えた。

以下の実装による define-record-type は R7RS の define-record-type と同じ構文であるが、コンストラクタが生成するオブジェクトの実態はベクタである。 ベクタはもちろんデータ値なので write で内容を表示することが出来る。

レコード型を区別するためにベクタの最初の要素にリストを入れているが、これはレコード型を定義するときに生成するリストと eq? 的に等しいか否かで区別するので一旦 write で書き出しだものを read しても元と同じではないということには注意する必要がある。 あくまでレコードを簡単に表示できるので便利だというだけのものだ。

(define-library (vrecord)
  (export define-record-type)
  (import (except (scheme base) define-record-type))

  (begin

    (define (make-accessor tag count)
      (lambda(record)
        (if (and (vector? record)
                 (< 0 (vector-length record))
                 (eq? (vector-ref record 0) tag))
            (vector-ref record count))))

    (define (make-modifier tag count)
      (lambda(record obj)
        (if (and (vector? record)
                 (< 0 (vector-length record))
                 (eq? (vector-ref record 0) tag))
            (vector-set! record count obj))))

    (define (make-predicate tag)
      (lambda(record)
        (and (vector? record)
             (< 0 (vector-length record))
             (eq? (vector-ref record 0) tag))))

    (define-syntax duplicate-check
      (syntax-rules ()
        ((_) #f)
        ((_ p r ...)
         (letrec-syntax
             ((foo (syntax-rules (r ...)
                     ((_  r) (syntax-error "duplicated field-name" p))
                     ...
                     ((_  x) (duplicate-check r ...)))))
           (foo p)))))

    (define-syntax contained-in-fields?
      (syntax-rules ()
        ((_ fs (f ...)) #f)
        ((_ fs (f ...) i . is)
         (let-syntax ((foo (syntax-rules (f ...)
                             ((_ f) (contained-in-fields? fs fs . is))
                             ...
                             ((_ g) (syntax-error "unrecognized field-name" i)))))
           (foo i)))))

    (define-syntax make-constructor
      (syntax-rules ()
        ((_ tag (a ...) (i ...) ())
         (lambda(i ...) (vector tag a ...)))
        ((_ tag (a ...) (i ...) (f fr ...))
         (let-syntax ((foo (syntax-rules (i ...)
                             ((_ tag t e i is r) (make-constructor tag t is r))
                             ...
                             ((_ tag t e j is r) (make-constructor tag e is r)))))
           (foo tag (a ... f) (a ... (if #f #t)) f (i ...) (fr ...))))))

    (define-syntax foo
      (syntax-rules ()
        ((_ n tag (pn ...) (pb ...) idx)
         (define-values (pn ...)
           (let ((tag (list 'record 'n)))
             (values pb ...))))
        ((_ n tag (pn ...) (pb ...) idx (fx ax) r ...)
         (foo n tag (pn ... ax) (pb ... (make-accessor tag idx)) (+ 1 idx) r ...))
        ((_ n tag (pn ...) (pb ...) idx (fx ax mx) r ...)
         (foo n tag (pn ... ax mx)
              (pb ... (make-accessor tag idx) (make-modifier tag idx))
              (+ 1 idx)
              r ...))))

    (define-syntax define-record-type
      (syntax-rules ()
        ((_ n (c i ...) p (f a m ...) ...)
         (begin
           (duplicate-check f ...)
           (duplicate-check i ...)
           (contained-in-fields? (f ...) (f ...) i ...)
           (foo n tag (c p)
                ((make-constructor tag () (i ...) (f ...))
                 (make-predicate tag))
                1 (f a m ...) ...)))))
    ))

レコードもどきを使ってみる

では作ってみたレコードもどきを使ってみる。

(import (except (scheme base) define-record-type)
        (scheme write)
        (vrecord))

(define-record-type alt-pair (kons x y) kons?
  (x kar set-kar!)
  (y kdr set-kdr!))

(let ((k (kons 1 2)))
  (write k)
  (newline)
  (write (kons? k))
  (write (kons? (cons 1 2)))
  (write (kar k))
  (write (kdr k))
  (set-kar! k 3)
  (write (kar k))
  (newline)
  (write k))

この実行例を実行した結果は以下のように表示されるはずだ。

#((record alt-pair) 1 2)
#t#f123
#((record alt-pair) 3 2)

R7RS の define-record-type と干渉しないように import のときに except を指定することを忘れないように気を付けて欲しい。

ちなみに、ほんの少しだけ修正すれば R5RS でも使えるはずなので R7RS 用のコードを R5RS に移植するような場合にも利用できるだろう。

Document ID: 42a50ddec93f9d61b6d6e6736487d0b0

破壊!

プログラミング言語 Scheme は多くの LISP 系言語がそうであるようにリスト操作を多用する。 SRFI-1 では便利なリスト操作手続きが定義されていているのだが、 RnRS の考え方とは異なる部分があり、そこで初心者がつまづくことがあるようだ。 以下のような事例で (C B A) が出力されることを期待してしまうといったようなことだ。

(import (scheme base)
        (scheme write)
        (srfi 1))

(define x (list 'A 'B 'C))
(reverse! x)
(write x)

実際には SRFI-1 によればこのコードの出力結果は規定されない。 参照実装通りの実装であれば (A) になるだろう。

Scheme の一般的な習慣としては名前の末尾にエクスクラメーションマークが付いている構文や手続きは破壊的な操作を行うのだが、 SRFI-1 においては破壊という言葉を使わずに線形更新 (linear update) という言葉を定義して当て嵌めている。 これは入力されたオブジェクトを壊して再利用する可能性があることを示すもので、どのように再利用されるか、あるいは再利用されないのかは規定されていない。 reverse! の結果はあくまで返却値であり、入力したオブジェクトはもはや利用してはならないということを意味する。

R5RS や R7RS ではそれぞれ以下のような命名規約が示されている。

規約により、割り当て済みの場所 (3.4 節参照) に値を格納する手続き名は通常の場合“!”で 終了している。 こういった手続きを変異手続き （mutation procedure）と呼ぶ。規約上、変異手続きの返す値は未規定である。

! は，以前に割り当てられた場所の中へ値を格納する手続き (3.4 節参照) の名前の最後の文字である。このような手続きは変異手続き (mutation procedure) と呼ばれる。 変異手続きが返す値は未規定である。

これらの規約に従うなら、名前の末尾がエクスクラメーションマークであるような手続きは破壊的な操作を行い、返却値が規定されない以上はその破壊的な操作こそが期待する動作であることを意味する。 この意味で考えていると reverse! の挙動につまづいてしまう。

このように SRFI のいくつかは RnRS と、あるいは他の SRFI と一貫していないこともあるので注意が必要だ。

Document ID: 81b51a480de15de54c3ce139310dcca6

万能な HTML

文章を記述するために HTML は万能の選択肢だ。 必要であれば JavaScript を用いることでかなり複雑な描画も可能であるし、動きのある画像も作ることが出来る。 数式を記述するための語彙群である MathML に対応したブラウザが一向に出てこないが JavaScript で書かれたライブラリ MathJax を導入することで MathML を利用することが出来るどころか TeX 風の記法も可能になる。 (というより数式は MathML よりも TeX 風記法で書かれることの方が多いようだ。)

しかしブラウザを通さないで見たとき、視覚的にマークアップは邪魔だ。 HTML タグを使う記法は冗長なので書くのが面倒くさいという欠点もある。 そのために簡易的な記法 (軽量マークアップ言語) がいくつも生み出された。 今では Markdown が最も有名だが ReStructuredText, Textile, AsciiDoc, Creole といった記法がよく知られており、各種ブログやウィキのサービスはこれらの他に独自の記法を持っている場合もよくある。

さて、軽量マークアップ言語は軽量というだけあって HTML のような万能を目指さないかわりに記法が簡易的になるようにするというのが基本的な理念だろう。 たとえば行頭に # を入れて見出しにする記法などは、それをレンダリングしなくても見出しらしく見えて視覚的にも自然である。

高度な機能を捨てることで簡易さを目指したはずなのに、やはり物足りなくなってくるのか拡張仕様が現れてもいる。 軽量にすると決めたのならある一定以上はサポートすべき範囲のものではないとして捨てればよいのだ。 後付けでこれもいる、あれもいると加えてしまったばかりに不格好になってしまっている。 そんなわけで、近頃の私は、いっそ最初から HTML で書くのが好ましいと思っている。

Document ID: 7645b5a12c5982e78505b1ae87b4313d

気付いてなくても存在するもの

新興のプログラミング言語として Rust がある。 この言語は Ownership と Lifetime という概念を導入することで不用意なメモリ操作を無くそうとするところに特徴がある。 しかし、 C などでプログラミングするときはオブジェクトの所有権や寿命は管理していなかったのかというとそんなことはない。 どのポインタがオブジェクトに対して責任を持つのか、オブジェクトを解体するのはいつか、プログラマの頭の中では管理していたはずだ。 概念として切り出して言語処理系で辻褄を確認することが可能だという気付きが Rust の設計に反映されているのである。

そんな事例は他にもある。 Scheme で言語仕様に現れる「継続」だって Scheme 特有のものではない。 Scheme で継続が特別なのは第一級のものとして言語仕様に盛り込まれてプログラマが陽に扱えるようにしたというところが特徴的なのであって、表には出てこなくても他の言語でも継続は存在している。 (私が Scheme の言語機能としての継続をいうとき「継続」ではなく「第一級継続」と呼んでいるのはそういう理由からだ。)

一方で、言語処理系が確認する部分を減らしているものもある。 動的型の言語を使っていても想定していなかった型を受取ればエラーになるわけで、しかしプログラムが動作するのはプログラマの脳内で型を管理しているからだ。 大抵の場合には実行時に最低限の確認は入るが型を陽に記述することはない。 これらは何を自動化するかの問題であって正解があるわけではない。 プログラマが自分の能力で管理可能なものであれば言語処理系の支援は邪魔になりうるし、プログラマの能力では管理しきれず自動化して欲しいところであれば言語処理系に頑張って欲しい。

プログラムは書いた人以外の人が読むこともあるので、言語処理系としては無くてよくても書いて欲しい情報というものはある。 Haskell のような強力な型推論機能で型を特定できるのであっても型を明記することがあるのはその方が読みやすいからだ。

そんなわけで、あるプログラミング言語が「簡潔な文法」だとか「アルゴリズムを表現するのに集中できる」といったことを利点として挙げていてもそれが利点とは限らない。 というより利点には違いないだろうがそのために他の利点を捨てていることもあるし、文法が複雑だと思ってもそれが必ずしも不利には働かない。 自分が気付いてなかった概念がそこに「有る」と気付かせてくれるのは無駄なことではない。

Document ID: 120e39dbdb463b05448c14d9a01cfb53

Haskell で TL/1 構文解析器を書いた

古いプログラミング言語 TL/1 の構文解析器を Haskell で書いてみた。

https://github.com/SaitoAtsushi/TL1hs

以前に Scheme で書いた TL/1 から C への変換器は仕様が曖昧なところを寛容な方向に解釈して実装したが、今回は自然に考えて、あるいは自然に実装するとこうなるという感覚を優先した。 TL/1 が実際に使われていた当時の処理系に近い解釈になっていると思う。 (貧弱な演算資源しかない環境では先読みが少なくなるように設計されていたに違いないと決め付けている。)

しかし、意図的に変えている箇所もある。 TL/1 の変数の大きさは 1 バイトであるが、その範囲で扱えないはずの大きな数値リテラルを許容するといった挙動にしている。 変数の大きさを 2 バイト以上に拡張した処理系にすることを考えているので構文解析の段階では大きさの判断をせず、もしエラーにするにしても後の工程にまかせるという意図だ。

既存の処理系、そして既存の処理系が動作する環境を私は持っていないので実際に動作を確かめて合わせるということも出来ない。 いくつかある TL/1 はそれぞれかなり違う部分もあるようなので、私のこれもそうした変種のひとつと考えて昔の処理系に対する再現性には期待すべきではないことには留意して欲しい。

Document ID: 4ee6938b5cc436a0720e06ce8eb0f0a9

分配エラー

プログラムというものは想定する使い方できちんと使えるようにすることは当然としても、使えてはいけないときにはエラーにすることも重要であるということを以前に書いたことがある。

エラーにしたいとき - 主題のない日記

しかし、 Scheme ではそれは少しばかり難しい。 R7RS では「エラーである」と表現されていても処理系の裁量で適当に無難な結果を返してもよいことになっている。 (エラーを検出して通知しなければならない場合については別の表現で書かれている。) そうした状況では処理系がエラーにすることを期待せずにプログラマが陽に書かなければ思わぬ事態になるかもしれないのである。

そのひとつが省略子付きのパターン変数にマッチしたものの分配だ。

例として以下のようなものが挙げられる。

(import (scheme base) (scheme write))

(define-syntax zipm
  (syntax-rules ()
    ((_ (x ...) (y ...))
     (list (list x y) ...))))

(display (zipm (1 2) (1 2 3)))

このときパターン変数 x にマッチするのは (1 2) であり y にマッチするのは (1 2 3) なので (x y) ... は数が合わずエラーである。 しかし、それを通知せずに短い方に長さを合わせる処理系は多い。 そうした処理系でも確実にエラーにすることを考えると以下のような書き方が思い付く。

(import (scheme base) (scheme write))

(define-syntax %zipm
  (syntax-rules ()
    ((_ (tx ...) (ty ...) () (y ys ...))
     (syntax-error "invalid input"))
    ((_ (tx ...) (ty ...) (x xs ...) ())
     (syntax-error "invalid input"))
    ((_ (tx ...) (ty ...) () ())
     (list (list tx ty) ...))
    ((_ (tx ...) (ty ...) (x xs ...) (y ys ...))
     (%zipm (tx ... x) (ty ... y) (xs ...) (ys ...)))))

(define-syntax zipm
  (syntax-rules ()
    ((_ (x ...) (y ...))
     (%zipm () () (x ...) (y ...)))))

(display (zipm (1 2 3) (1 2 3 4)))

事前に全てを想定できるわけではないにしても、特に汎用性の高い部品については入力を信用しないということを意識するのは重要であるとあらためて思う次第である。

Document ID: b3f37dd8178a9063779cf788e179efea

フィード

ブログ、またはその他のウェブサイトの更新を通知する仕組みとして RSS が知られている。 複数の版が異なる思想で設計されているので統一されずに混在してはいるのだが、 RSS が更新通知の標準としての地位を確立しているといえるだろう。

RSS を「更新通知」と考えるか「情報配信」と考えるかで利用形態、運用に差が生じる。 私は主に配信の意味で利用している。 つまり、ブログの全文を RSS リーダで読むという使い方をしている。 しかし、サイトによっては更新されたという情報のみしか含めていないという場合もあって、ブラウザでサイトを見にいかなければいけないということもしばしばある。 結局は面倒くさくなって全文配信していないサイトは見なくなってしまったりもする。

複数の RSS を集約してひとつにまとめてくれるサービスもある。 たとえばはてなブログの「購読」の仕組みだ。 はてなブログのユーザははてなブログがホストしている他のブログの更新を知ることが出来て、集約された RSS を RSS リーダで見ることも出来る。

しかし、はてなブログが集約した RSS には各ブログの最新記事しか含んでいないのだ。 一度に (私が RSS を巡回するする間隔より短かい間隔で) 複数の記事が投稿された場合には記事を取り零してしまう。 RSS を利用する各ウェブサービスが更新通知を意図したものなのか、内容の配信を意図したものなのか、自分の用途に合ったものを選択する必要があるということは意識しなければならない。

Document ID: 9f93377b8efe23a44555361ff105eac7