練習問題 : ラムダ式

1.

2 引数の関数を受け取り、 カリー化された関数を返す高階関数 curry と、 その逆をおこなう uncurry を定義せよ。

ヒント: ある 2 引数の関数 foo が与えられたとして、 これをカリー化した関数はどう定義すればよいか考えてみましょう。

解答例

2. (lazy evaluation or call by need)

以下のプログラムは、無限の整数列を模したものです。 car, cdr の代りに head, tail を使います。 どうして、これで無限の整数列を表現できているのか説明して下さい。

(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))))

;;; 使用例
;;; 但し、MzScheme Mode で使用すること
> (define tmp (infinite-enumerate 5)) ; 5 から始まる無限数列のつもり
> tmp
(0 . #<procedure>)
> (head (tail (tail tmp)))            ; 2 番目の要素をとると 7
7
> (nth-inf-list 10000 tmp)            ; 10000 番目の要素は 10005
10005

解答例

3. (Object-Oriented の真似事)

以下のような長方形クラスを Java 上につくりました。 box クラスは、 constructor と 対角座標を表す変数 4 つと、面積を返す area という メソッドを持っています。 そのサブクラスである boxWithArea は、 あらかじめ面積を計算しています。 areaVal という field に面積の値が 格納されており、 area method は override されています。

class box {  // 紙面の都合でつめてあります
  int x0,y0, x1,y1;
  box(int x0, int y0, int x1, int y1) { 
    this.x0 = x0;  this.y0 = y0;
    this.x1 = x1;  this.y1 = y1;
  }
  int area () {  return ((x1 - x0) * (y1 - y0)); }
}

class boxWithArea extends box{
  int areaVal;
  boxWithArea(int x0, int y0, int x1, int y1) { 
    super(x0, y0, x1, y1);
    areaVal = (x1 - x0) * (y1 - y0);
  }
  int area () {  return areaVal;  }
}

さて、Scheme でこのプログラムを似せてみようと思い立ちました。 で、下の部分まで作ったので、これを参考に メソッド定義部と constructor を作ってプログラムを完成させて下さい。

;;; Java との対応関係
;;; field access:   Java: obj."field"        今回: (get-"field" obj)
;;; method invoke:  Java: obj."method"(args) 今回: (method-"method" obj args)
;;; constructor:    Java: "classname"(args)  今回: (constructor-"classname" args)

;;; selector 
;;; for members of box class

(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))

(define (method-area box)
  (let ((method-body (list-ref box 4)))
    (method-body box)))

;;; selector 
;;; for members of box class

(define (get-areaVal box-with-area) (list-ref box-with-area 5))

;;; method definition
;;; 
;;; ????????

;;; constructor
;;; 
;;; ????????

解答例

4.

前回 の続きで、 Scheme に似た形をした S式 の中にlambda 式を導入しましょう。

expression      ::= number | variable | #t | #f | primitive-procedure
                  | (if expression expression expression)
		  | (lambda (args) expression)
		  | (procedure expressions)
expressions     ::= null-expression | expression expressions
expressions1    ::= expression | expression expressions
null-expression ::= 
args            ::= 
		  | variable args
procedure       ::= expression
primitive-procedure  ::= + | * | < | = | > | 

lambda 式が導入された影響は、変数が導入された事と、 procedure に式(その値はラムダ式)が導入された事です。 また、変数の導入にともない 変数と値の束縛関係つまり環境が導入されます。 以下のプログラムを参考に評価器を完成させましょう。

;;; variable 関連

(define (eval-variable variable env) (lookup-env variable env))

;;; evaluator 本体の変更
;;; 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"))))

(define (eval-expr-top expr) (eval-expr expr init-env)) ; 初期環境を用いて評価する関数

;;; Apply 関連
;;; ラムダ式に引数を適用する (closure の環境を取り出して使っていることに着目)
;;; (apply-closure だと closure を apply するように聞こえてしまって、済みません)

(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))))

;;; apply-proc 本体の変更
;;; ラムダ式のために拡張 (環境が渡されていないことにも着目)

(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"))))

解答例