EOPL 第3章の Exercise 3.23 と 3.24

Exercise 3.23 は「レキシカル変数について名前は重要ではなく、レベルと位置で識別できる」という第1章で学んだことをいま作っている処理系に適用して lexical-address 関数のこの言語版を作る。このためにヴァリアント型に lexvar-exp を追加した。3.24 は apply-env を改造して変数が確かに lexical-address で予測された位置に現れるということの答えあわせができるようにする。

続きを読む

EOPL 第3章の Exercise 3.19 から 3.22: proc の追加

EOPL の続きでファーストクラスの関数の追加。プリミティブの適用とユーザ定義関数の適用が全然違う構文になるので気持ち悪いけど…

練習問題 3.20 は引数の数のチェック機能の追加。練習問題 3.21 と 3.22 は letrec を導入しなくてもここまでで作った言語で再帰が書けるよって話。このテクニックは面白いな。型付き言語だとどういう型にすればいいんだろう？

ちなみに私はいままで SLLGEN での文法定義と define-datatype による構文木のヴァリアント型定義は別個にしなければいけないと思っていて構文を追加するごとに2箇所（eval を入れて3箇所）に手を入れるのは面倒くさいと感じていたんだけど、実は sllgen:make-define-datatypes は define-datatype するところも自動でやってくれていたらしい。

続きを読む

EOPL 第3章の Exercise 3.16 から 3.18: let の追加

EOPL の続き。今回は let 式を追加。Exercise では eq? 関数とリストを変数に展開する unpack 式を追加した。

gosh> (read-eval-print)
let x = 1 in x
-->1
let x = list(1,2,3) in unpack x y z = x in +(1,+(2,3))
-->6
let x = list(1,2,3) in let y = x in eq?(x,y)
-->#t

続きを読む

EOPL 第3章の Exercise 3.10 から 3.15

3.3 節ではインタプリタに条件式を追加した。

最初は真偽値を使わずにゼロ/非ゼロで代用するんだけど、練習問題の 3.14 では扱う値に Bool を追加してさらに if の条件節に Bool が来なかった場合はエラーとするように改造する。
その一方で 3.15 では <bool-exp> という新しい nonterminal を追加する。

練習問題 3.15 は何をやったことになるんだろうか。これだと if の条件節に <bool-exp> がこなかった場合は実行時でなくパース時のエラーになるというところがよい？出来上がったものを見るとなんかもやっとしたものを感じるけど。

続きを読む

EOPL 第3章の Exercise 3.1 から 3.9 答案

第3章ではインタプリタの製作を開始する。SLLGEN という Scheme 用のパーサジェネレータによるフロントエンドの作り方も導入される。この本は構文解析については SLLGEN の使い方を教えるだけで、「もし使っている言語にパーサジェネレータが無ければパーサを手書きする方法もある。やり方は大抵のコンパイラのテキストに書いてあるから」で済ませている。

練習問題 3.1 と 3.3 は前章でもやっていたような構文木のリスト化とその逆。3.5 から 3.8 は簡単なインタプリタに新しいプリミティブを追加する問題。3.9 は引数の数のチェック機能を付け加える問題。まだそんなに面白くなるところではない感じ。

練習問題 3.7 と 3.8 で問われている expressed value と denoted value という用語の使い方が良く分からなかった。 expressed value は "the possible values of expresions" で、denoted value は "the values bound to variables" だと言っていて、最初の版のインタプリタでは Expressed Value = Denoted Value = Number である。練習問題 3.7 で cons などなどを追加するとたぶん Expressed Value = Denoted Value = Number + List of Values(?) になる。練習問題 3.8 で setcar （リストの car の破壊的変更）を追加すると…まだ変わらない、でいいのかな？

続きを読む

Scheme の letcc を使う

Seasoned Schemer をちょろっと読んで letcc の使い方について少し知恵を付けたので EOPL の練習問題 1.17 の答案 [1] を書き直してみることにしました。以下に再掲します。これは二分探索木内の指定要素に辿り着くまでの道順を返す関数。

(define path
  (lambda (n bst)
    (cond
      ((null? bst) '(fail))
      ((= n (car bst)) '())
      ((< n (car bst)) (cons 'left (path n (cadr bst))))
      (else (cons 'right (path n (caddr bst)))))))

これを使うと

gosh> (define bst '(14 (7 () (12 () ()))
                       (26 (20 (17 () ())
                               ())
                           (31 () ()))))
bst
gosh> (path 17 bst)
(right left left)
gosh> (path 7 bst)
(left)
gosh> (path 14 bst)
()
gosh> (path 12 bst)
(left right)

こんな風に目的ノードまでの道順を返してくれます。しかし最終的にゴールが見つからないと

gosh> (path 19 bst)
(right left left right fail)

こんな風になんとも中途半端な結果になります。この練習問題は見つからなかった場合の処理について何も言っていないので別にこれでいいのですが、たとえば「ゴールが見つかった場合は道順、見つからなかった場合は #f を返す」という動作にするにはどうしたらいいか。例えばこれ。

(define path
  (lambda (n bst)
    (cond
      ((null? bst) #f)
      ((= n (car bst)) '())
      ((< n (car bst))
       (let ((result (path n (cadr bst))))
         (and result (cons 'left result))))
      (else
        (let ((result (path n (caddr bst))))
          (and result (cons 'right result)))))))

いったん result で受けて…というのを段々上に浸透させていく部分がなんか嫌で、せめて例外使いたいなあと思うわけです。しかし、ここで letcc （Gauche では let/cc という名前。これって Scheme の標準じゃない？）の登場です。

(define path
  (lambda (n bst)
    (let/cc hop
      (letrec
        ((P (lambda (bst)
              (cond
                ((null? bst) (hop #f))
                ((= n (car bst)) '())
                ((< n (car bst)) (cons 'left (P (cadr bst))))
                (else (cons 'right (P (caddr bst))))))))
        (P bst)))))

(let/cc hop ...)　の部分の値は通常 ... を全部計算し終わった結果の値になるのですが、中で (hop #f) が呼ばれるとそれまでのことをすべて忘れて #f がその値になります。これにより行き止まりに辿り着いたところでいきなり戻って #f を返すということができます。このくらいの使い方なら継続もそんなに大げさなものではないかな。

[1] http://blog.so-net.ne.jp/rainyday/2007-08-18

EOPL 第2章の Exercise 2.11 から 2.26 答案

引き続き Essentials of Programming Languages の練習問題。

2.12 と 2.22 は問題の文意がよく読み取れなかったのでひとまず保留した。どちらも星1つなので簡単なことを言っているはずなんだけど…。2.12 はα変換とかβ変換とかη変換とか重要そうなことを言っているので後で立ち戻ってくるかもしれない。この本の Exercise はこういう新奇な概念も説明少なめにさらっと問題に出してくる感があるので基本的には教師がついて授業で使う的な想定であまり独習向けな感じではないのかもという気もしてきた。

ともかく第2章が終わったのでようやく第3章に入れる。ここでついにインタプリタの実装が出てくるはずである。

以下は Exercise 2.11 から 2.26 までの私の答案です。長いので注意。

続きを読む

EOPL 第2章の Exercise 2.1 から 2.10 答案

EOPL 第2章はデータ抽象について。また、著者らが用意したマクロ（Scheme でヴァリアント型定義やそれに対するパターンマッチを可能にする）が導入されて AST を定義/操作したり、AST から情報を抽出したりする練習問題も出てくる。こうした練習が後の章への準備になるのかと思われる。

ところで本筋と離れたところでこの章の Exercise 2.5 が非常に苦労した問題だった。難易度は星2つなので特に難しい問題として用意されたわけではないと思うのだけど…

問題は

<bintree> ::= <number> | <symbol> <bintree> <bintree>

という定義の二分木が与えられたときに葉の合計がもっとも大きくなるような（葉ではない）ノードのシンボルを返す関数 max-interior を書けというもの。葉の数字は負の数でもよいのでルートが最も大きいとは限らない。

なお、Scheme + EOPL のマクロではこの2分木は

(define-datatype bintree bintree?
  (leaf-node
    (datum number?))
  (interior-node
    (key symbol?)
    (left bintree?)
    (right bintree?)))

と定義することが出来て、たとえば全ての葉ノードの合計は

(define leaf-sum
  (lambda (tree)
    (cases bintree tree
      (leaf-node (datum) datum)
      (interior-node (key left right)
        (+ (leaf-sum left) (leaf-sum right))))))

というようにパターンマッチを使って書ける。パターンのネストはできない（と思う）。

この問題をできれば「副作用なし」「効率」「コードがわかりやすい」を満たすように書きたかったのだけど、コードをあれこれいじり倒したあげく結局効率は捨てた回答にしました。

以下は練習問題2.1から2.10の私の答案です。2.5への回答は真ん中辺です。

続きを読む

EOPL 第1章の Exercise 答案

Essentials of Programming Languages [1] の練習問題をかなり地道に一つ一つやっていた（なんか修行してるみたいな気分）。

そして第1章の練習問題のうちプログラムを書かせる問題は全部できたので（EOPL の Exercise を普通に Scheme でやって公開している人とかは世界中にたくさんいそうなので特に新奇性というか見る価値はないと思いますが）、一応この記事の最後に付けます。おそらく errorf 関数を使っている部分のみ Gauche 依存です。

しかし私が cond と let の開き括弧の数に確信を持てる日はくるのだろうか。

[1] http://www.cs.indiana.edu/eopl/

続きを読む

Common Lisp の multiple value

「岩波コンピュータサイエンス Common Lisp 入門」という本が本屋にあったので買ってみた。3ページ目くらいでいきなり驚いたんだけど Lisp にも Lua と同様 multiple value があるらしい。

> (floor 11 3)
3
2

それと振る舞いも良く似ている。

一つの値が期待される文脈では2つめ以降の値は単純に捨てられる。

Lua:

> function floor(x,y) return math.floor(x/y),x%y end
> a = floor(11,3)
> print(a)
3

Lisp:

> (setq a floor 11 3))
3
> a
3

値が足りない分は nil で埋められる。

Lua:

> x,y,z=floor(11,3)
> print(x,y,z)
3       2       nil

Lisp:

> (multiple-value-setq (x y z) (floor 11 3))
3
> x
3
> y
2
> z
NIL

タプルのようなデータ構造ではない形で multiple value を持ってる言語って相当特異だと思ってたんだけど Lua のそれは Common Lisp の影響だったのかな。