ふつける 5章 - 遅延評価

遅延評価の解説。スゲーわかりやすいっす。

もしもSchemeを遅延評価にすると、

(define (squere x) (* x x))

(square (+ 1 1))      ; squereを簡約
(* (+ 1 1) (+ 1 1))   ; 前の+を簡約
(* 2 (+ 1 1))         ; 後ろの+を簡約
(* 2 2)               ; かける
4

+を2度やることになるので無駄です。

Haskellの場合、

(* (+ 1 1) (+ 1 1))   ; 一気に簡約
(* 2 2)
4

スゲー。

一気に簡約なんて出来る訳が無いので、ポインタで。

(* P P) > (+ 1 1)     ; ポインタを簡約
(* P P) > 2           ; 簡約
4

スゲー。

たぶん全体的にポインタなんだろうな。

ただし、破壊的な関数があると、このモデルが一気に崩れてしまう訳で・・・SICP読むと書いてあるわけで・・・むにゃむにゃ・・・


ちなみに、Schemeの簡約モデルは、閉じ括弧が来たら評価という感じ。

(* (+ 1 1     ; 読みまくり
(* (+ 1 1)    ; 閉じ括弧だ
(* 2          ; 簡約

簡単です。ハイ。

ifの再定義

ifのサンプルがあったので、true,falseを含めて作ってみる。

true :: a -> a -> a
true a b = a
false :: a -> a -> a
false a b = b

if' :: (a -> a -> a) -> a -> a -> a
if' f a b = f a b

forever = forever

test = if' false forever "false"
-- "false"

forever見てないっす。

すごいっす。すごいっす。

Yコンビネータ

Yコンビネータの定義はY g = g (Y g)です。

Schemeでまんま書いたらg g g g ....となって、爆走します。

Haskellでやってみると。

y g = g (y g)

fact = (\f ->
        (\n ->
         if n == 0 then 1
                   else n * f (n - 1)))

test = (y fact) 10
-- 3628800

スゲー。

いやいや、もっとシンプルに書ける。

y g = g (y g)

fact f 0 = 1
fact f n = n * f (n - 1)

えぇぇぇぇ・・・ふ、ふつうだ。自然すぎるくらい自然。


か・感動した。

Schemeだって負けてられない

じゃ、お兄さんがたらいまわしを早くしちゃうよ。

(define (tarai x y z)
  (if (<= x y)
      y
      (tarai (tarai (- x 1) y (lambda () (z)))
             (tarai (- y 1) (z) (lambda () x))
             (lambda () (tarai (- (z) 1) x (lambda () y))))))

(tarai 20 10 (lambda () 5))

一瞬。


やることは単純。

(tarai x y z)をした時、zを見る必要が必要ない。だから、lambdaで囲っておく。

2番目のたらいが回される時、zが必要になるので、必要になったらzを剥がせばいい。


Schemeだって遅延出来るよ!!


参考:Scheme:たらいまわしべんち