遅延評価のお勉強

Scheme

遅延評価のお勉強に、SchemeでHaskellライクなインタプリタを作ってみる。

足し算とifしかない。

(define (skell src)
  (define (forever) (forever))
  (define (reader src)
    (fold
      (lambda (m cont)
        (cont
          (cond ((integer? m) (lambda (x) m))
                ((pair? m) (lambda (x) ((reader m) x)))
                (else
                  (case m
                        ('+ (lambda (a)
                              (lambda (b)
                                (lambda (x) (+ (a x) (b x))))))
                        ('true (lambda (a)
                                 (lambda (b)
                                   a)))
                        ('false (lambda (a)
                                  (lambda (b)
                                    b)))
                        ('if (lambda (b)
                               (lambda (t)
                                 (lambda (f)
                                   ((b t) f)))))
                        ('forever (lambda (x)
                                    (forever))))))))
      (lambda (x) x)
      src))
  ((reader src) 'real-world))

lambdaだらけ。

テストぉ。

(skell '(+ 1 2)) ; 3

(skell '(+ (+ 1 2) (+ 3 4))) ; 10

(skell '(if true (+ 1) (+ 2) 3)) ; 4

(skell '(if false
            (+ 1 2)
            (+ 3 4))) ; 7

(skell '(+ (if true
               (+ 1 2)
               forever)
           (if false
               (+ 3 4)
               (+ 5 6)))) ; ; 14


まだグラフ簡約は出来てない。どう実装するのか考えてみる。

以下メモ。

  • foldでガンガン前から展開してるだけなんだけど、どうやら遅延してるみたい。必要なところしか計算しない。
  • 括弧の処理がむずかったので、数字とか文字とかそういうのは無い関数だけな世界を作り出しておいて、実際の値は必要な時に取り出す感じにしてみた。
  • パターンマッチは案外簡単かもしれない。実装できそうな気分がしてきた。

わからないところだらけだ・・・。

$

$付けた

(skell '(+ 1 $ + 2 $ if true + - 3 $ 4)) ; 10

Haskellっぺぇっす。

解析すると、

(skell '(+ 1 (+ 2 (if true + - 3 (4)))))

こうなるらしい。継続の処理がちと違うのでスゲー邪魔。

ちゃんと構文解析して、括弧に直してから処理したほうが楽そうだ。

演算子の優先順位もあるんだよな・・・。