(define (curried-foo x) (lambda (y) (foo x y)))ということで、カリー化関数は、foo を一般化すれば良いんです。
(define (curry func) (lambda (x) (lambda (y) (func x y))))同様に、uncurry は、以下のようになります。
(define (uncurry func) (lambda (x y) ((func x) y)))
では、問題の解答に移ります。
まずなにが無限のリストに相当するかと言うと、
(infinite-enumerate n) です。
これは、 n, n+1, ... という無限のリストに相当しています。
head, tail をつかってリストの要素にアクセスします。
実は、infinite-enumerate自体は、 n と、
(infinite-enumerate (+ n 1)) を計算する引数なしのラムダ式の pair
として実現されています。つまり、
(infinite-enumerate (+ n 1))自身はこの時点で計算されるわけではありません。
このため、
では、その要素にアクセスするときにどのような挙動をするのか調べてみましょう。
head によって第一要素を取り出すのですが、実はこれは car
そのものです。
もともと (infinite-enumerate n)の car field は、 n だったので、
何の問題もありません。
では、 tail をとったときはどうなるのでしょうか？
tail では、まず rest として (infinite-enumerate n) の
cdr field 、 つまり (lambda () (infinite-enumerate (+ n 1)))
をとりだします。
そして、 (rest) と引数なしでこのラムダ式を評価します。
これは、つまり、 (infinite-enumerate (+ n 1)) を実行すると言うことです。
そうすると (n+1 . (lambda () (infinite-enumerate (+ n+1 1))))
(但し、n+1は (+ n 1) の値とする)という pair が生成されます。
このように、 tail を実行するたびにリストの残りの要素を一つ計算することで、
無限のリストを実現しています。
実は、このような遅延評価は、実際に全てを作ることの出来ないようなリスト構造、
例えば無限リストや、とても大きな探索空間を表現する時に用いられます。
探索問題の例を考えましょう。
遅延評価版の map, flatten, filter を作り、
全ての解の候補のリストを生成してから check するというプログラムを書いたとします。
この場合、
普通のリストの場合、解候補を作る時点でプログラムは破綻してしまうような場合でも、
遅延評価を行っていると、実際には解候補を一つずつ生成しては check して、
ちがったら捨ててしまうという挙動をするわけで、問題無く作動することになります。
まずは、プログラムの解説から始めましょう。
まず、 box class のインスタンス(個々のオブジェクトの事)はリストで表されていて、
始めの 4 つの要素を x0,y0,x1,y1 の為の field に相当します。
このため、(get-x0 box) などが以下の様に定義されているのです。
さて、次はbox-with-areaにだけ存在する field 名は areaValです。
ですから、6番目のリスト要素に areaVal の値を持たせる事とします。
このリスト要素は、ただの box のインスタンスにはありません。
では、constructor に行きましょう。これは、今までの解釈にしたがって、
対応するリストをつくればいいのです。
area-method-box, area-method-box-with-area は、それぞれ、
Java における box とarea-method-box-with-area で定義された
area method に対応するものです。
最後に、メソッド本体、
つまり area-method-box, area-method-box-with-area の定義です。
各々、元々の Java のプログラムを焼き直すだけです。
このオブジェクトの実装法の肝は、親クラスと子クラスが同じ形をしている点です。
ですから、子クラスをそのまま親クラスとして扱っても問題はありませんでした。
実は、こんなに簡単にいったのは親が一人だからで、
親が複数いると話は厄介になります。
(*) 実際の実装では、
class 毎に持っていれば良い値(Java の static variables
や method 名 と関数実体の対応表) は class 毎にもち、
Object 毎に持つ必要があるもの(普通の variables) とは別に持っている事が多いです。
また、データ構造にリストではなく配列を使う事が多いでしょう。
後、コンパイル時に method名と関数の対応がつく場合(Java の final)については、
対応表を使わないでしょう。
問題が難しいと思うので、解説を多めにします。
とは言っても、ソース全てで 200 行に達しないんですが。
まずはプログラムの与えられた部分の解説から。
プログラムに加わった式の形は、ラムダ式と変数です。
変数が導入されたため、変数とその値の束縛関係を示す環境が導入されました。
もう一つの変更点は、関数として primitive なものだけではなくて、
ラムダ式によってつくられた関数が導入されました。
eval-expr の変更点は、式の形として変数とラムダ式が入ったことです。
また、引数として環境 env が導入されました。
変数の評価では、 eval-variable の中で、環境から変数名を探しています
(lookup-env variable env)。
また、ラムダ式の評価では、ラムダ式と現在の環境を組にして
make-lambda-closure したものを値として返しています。
実はすこし考えなくてはいけないのは再帰関数の定義です。
letの機能があれば、関数を定義することは出来そうです。
なぜなら、関数名をラムダ式に束縛すれば良いのですから。
でも、実はこれでは再帰関数は書けません。なぜかというと、
let では、
let で定義する変数名をその式のなかに使うことが出来ないからです。
一方、define では定義する関数名が式の中に出て来ることを許しています。
再帰関数を定義するためには、
define, letrec, fix などと呼ばれるものを導入する必要があります。
これができればほとんど Scheme の完成でしょう。
興味があればやってみると良いでしょう。
実は環境の作り方に気をつけるだけで出来てしまいます。
(define (infinite-enumerate n)
(cons n
(lambda () (infinite-enumerate (+ n 1)))))
(define (head inf-list) (car inf-list))
(define (tail inf-list)
(let ((rest (cdr inf-list)))
(rest)))
(define (nth-inf-list n inf-list)
(if (= n 0)
(head inf-list)
(nth-inf-list (- n 1) (tail inf-list))))
(define (infinite-enumerate-X n)
(cons n
(infinite-enumerate-X (+ n 1))))
のように無限ループに入るわけでは無いのです。
Java でかかれた Object-Oriented(OO) Program を、
Scheme 上で真似ようとした。
残りの部分を埋めてプログラムを完成させて下さい。
(define (get-x0 box) (list-ref box 0))
(define (get-y0 box) (list-ref box 1))
(define (get-x1 box) (list-ref box 2))
(define (get-y1 box) (list-ref box 3))
5 番目(scheme的には 4番目?)のリスト要素は、
area method がどの関数に対応しているかを示しています。
ですから、(method-area box) では、
method-bodyを取り出して、自分自身を引数として渡しています。
他の引数があった場合は、 box 以降に連なることになります。
(define (method-area box)
(let ((method-body (list-ref box 4)))
(method-body box)))
ここで注意して欲しいのは、box-with-area class のインスタンスは
box class のインスタンスでもあると言う点です。
ですから、上の性質は box-with-area のインスタンスにおいても
成り立ちます。つまり、5 番目のリスト要素までは同じ形をしています。
(define (get-area-val box-with-area) (list-ref box-with-area 5))
(define (constructor-box x0 y0 x1 y1)
(list x0 y0 x1 y1 area-method-box))
(define (constructor-box-with-area x0 y0 x1 y1)
(let ((area (* (- x1 x0) (- y1 y0))))
(list x0 y0 x1 y1 area-method-box-with-area area)))
(define (area-method-box box)
(* (- (get-x1 box) (get-x0 box))
(- (get-y1 box) (get-y0 box))))
(define area-method-box-with-area get-areaVal)
前回 の続きで、
Scheme に似た形をした S式 の中にlambda 式を導入しましょう。
与えられたプログラムを参考に評価器を完成させて下さい。(define (eval-variable variable env) (lookup-env variable env))
(define (eval-expr expr env)
(cond ((prim-expr? expr) expr)
((var-expr? expr) (eval-variable expr env))
((if-expr? expr)
(eval-if (cond-expr expr) (then-expr expr) (else-expr expr) env))
((lambda-expr? expr)
(make-lambda-closure expr env))
((application? expr)
(apply-proc (eval-operator (operator expr) env)
(eval-arguments (operands expr) env)))
(else (display expr)
(error "Unknow Expression :: eval-expr"))))
さて、次は関数適用の方を見ましょう。
こちらもユーザ定義の関数の導入のため、
apply-proc で大きく変化しています。
ラムダ式の場合、その値は lambda closure として表されているので、
その場合の処理をしています。
注意してもらいたいのは、 apply-proc に来た時点では
すでに関数部引数部ともに評価され値になっている、という点です。
このため、環境は apply-proc では使われません。
lambda closure だと分かった時点で、 apply-closure を実行します。
この時点で、 closure のラムダ式部分と環境を取り出しています。
その上で、環境にラムダ式の変数と引数の値の関係を付け加えて、
その環境の中で ラムダ式の実体部を評価しています。
この処理により、static scoping が実現されます。
(define (apply-closure procedure arguments)
(let ((lambda-expr (closure-to-lambda-expr procedure))
(env (closure-to-env procedure)))
(eval-expr (lambda-body lambda-expr)
(extend-env (lambda-vars lambda-expr)
arguments
env))))
(define (apply-proc procedure arguments)
(cond ((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((lambda-closure? procedure)
(apply-closure procedure arguments))
(else (display procedure)
(error "Unknow Procedure :: apply-proc"))))
ここまで理解すれば、あとは、足りないものを付け加えるだけです。
以下のようになっています。
;;; 新たに加わった expression にまつわる関数
(define var-expr? symbol?)
(define (lambda-expr? expr)
(and (list? expr)
(eq? (car expr) 'lambda)
(= 3 (length expr))))
(define (lambda-vars expr) (cadr expr))
(define (lambda-body expr) (caddr expr))
;;; lambda closure に関する部分
;;; データ表現は各自好きにしてくれれば良い。
(define (lambda-closure? procedure)
(and (list? procedure)
(eq? (car procedure)
'lambda-closure)))
(define (make-lambda-closure expr env)
(list 'lambda-closure expr env))
(define (closure-to-lambda-expr closure) (cadr closure))
(define (closure-to-env closure) (caddr closure))
;;; primitive procedure も少し変更。 関数名自体が式に格上げされたため
;;;
;;; ということで、primitive procedure もただの変数名のように環境を
;;; 調べることとする。
;;; その値の表現は (primitive #<primitive:+>) という形で表現している。
;;; ということで、apply 側で 関数名からその実体を引き必要は無くなる
(define (make-primitive-procedure x) (list 'primitive x))
(define (primitive-procedure? procedure)
(and (list? procedure)
(eq? (car procedure) 'primitive)))
(define (primitive-procedure-to-scheme-primitive procedure) (cadr procedure))
(define primitive-procedure-names '(+ * - / < = >))
(define primitive-procedure-values
(map make-primitive-procedure (list + * - / < = >)))
;;; 環境の実現
;;; 僕の実装では、一度環境の拡張を frame とし、
;;; frame のリストとして env を実現しています。
(define (make-frame variables values)
(map (lambda (x y) (list x y))
variables values))
(define (var-field pair) (car pair))
(define (value-field pair) (cadr pair))
(define (lookup-frame var frame)
(cond ((null? frame) #f)
((eq? var (var-field (car frame)))
(value-field (car frame)))
(else
(lookup-frame var (cdr frame)))))
(define (extend-env variables values env)
(cons (make-frame variables values)
env))
(define (lookup-env var env)
(if (null? env)
(begin (display var)
(error "Unknow Variables :: var"))
(or (lookup-frame var (car env))
(lookup-env var (cdr env)))))
(define init-env ; 初期環境は、primitive procedure のみ
(extend-env primitive-procedure-names
primitive-procedure-values
'()))
;;; eval 関連について env の拡張
;;;
(define (eval-variable variable env) (lookup-env variable env))
(define (eval-operator operator env) (eval-expr operator env))
(define (eval-arguments operands env) (eval-exprs-inorder operands env))
(define (eval-if cond-expr then-expr else-expr env)
(if (eval-expr cond-expr env)
(eval-expr then-expr env)
(eval-expr else-expr env)))
(define (eval-exprs-inorder exprs env)
(if (null? exprs)
'()
(cons (eval-expr (car exprs) env)
(eval-exprs-inorder (cdr exprs) env))))
----------------------------------------
;;;実行例
> (eval-expr-top '+)
(primitive #
さて、冒頭でこれでほとんど Scheme ができたようなものだと言いました。
実は、これでリスト構造と再帰プログラム以外は大体書けるようになったのです。
let の機能も実は手にいれたようなものです。
というのも、実はlambdaで機能を代行することが出来るからです。
(let ((var-0 expr-0)
....
(var-n expr-n))
body)
<==>
((lambda (var-0 ... var-n) body) expr-0 ... expr-n)
では、足りない機能を見て行きましょう。
まずは、リスト構造について。これについては別に難しくありません。
primitive operation に car, cdr, cons, quote を導入すれば良いだけです。
興味があればやってみましょう。
また、逐次実行を導入することも、簡単です。
99.10.7/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp