Little Lazy Lisp 6.1 in Ruby

2008.4.18 (鈴)

1. 変更点について

Ruby による L2Lisp 6.0 版 に対し, assoc 関数本体のつづり間違いを訂正し,let マクロ本体などの整理をしたほか, 下記の3点を改訂した。

  1. 遅延評価用の「約束」オブジェクトの文字列表現を変更した (スクリプトの第 418-420 行)。
        def inspect
          (@link == NONE) ? @exp.inspect : "#<promise:%x>" % object_id
        end
    
    果たされていない約束に対し,果たすべき Lisp 式にかえて約束オブジェクト自体のオブジェクト ID を表示するようにした。 約束オブジェクトを含んだ式を print したときの煩雑さが軽減されるとともに, デバッグ時,約束オブジェクトがどのように伝播していくのか追跡することが容易になると期待される。
    > (setq a ~(+ 1 2))
    #<promise:286fea>
    > (+ a 3)
    6
    > a
    3
    > 
    
  2. インタープリタ自身のバージョンを大域変数 *version* として参照できるようにした。 (スクリプトの第 579 行)。
          @symbol[:'*version*'] = LL.list(6.1, "Ruby")
    
    この変数は版数とプラットフォームの2要素のリストを値とする。 ruby-eval など特定の実装に固有な機能を条件付きで実行するために利用できる。
    > *version*
    (6.1 "Ruby")
    >
    
  3. 主に遅延評価の便宜のために定義済み関数を追加した (スクリプトの第 1177-1215 行)。
    (defun some (f x)
      (cond ((null x) nil)
            ((f (car x)))
            (t (some f (cdr x)))))
    
    (defun take (n x)                       ; Haskell
      (if (or (= 0 n) (null x))
          nil
        (cons (car x) (take (- n 1) (cdr x)))))
    
    (defun drop (n x)                       ; Haskell
      (if (or (= 0 n) (null x))
          x
        (drop (- n 1) (cdr x))))
    
    (defun _zip (x)
      (if (some null x)
          nil
        (let ((cars (mapcar car x))
              (cdrs (mapcar cdr x)))
          (cons cars ~(_zip cdrs)))))
    (defun zip (&rest x) (_zip x))          ; Python 3.0 & Haskell
    
    (defun range (m n)                      ; Python 3.0
      (cond ((< m n) (cons m ~(range (+ m 1) n)))))
    
    (defun map (f x)                        ; Haskell
      (cond (x (cons ~(f (car x)) ~(map f (cdr x))))))
    
    (defun mapf (f x)                       ; map force
      (cond (x (cons (f (car x)) ~(map f (cdr x))))))
    
    (defun scanl (f q x)                    ; Haskell
      (cons q ~(cond (x (scanl f (f q (car x)) (cdr x))))))
    
    (defun filter (f x)                     ; Haskell & Python 3.0
      (cond ((null x) nil)
            ((f (car x)) (cons (car x) ~(filter f (cdr x))))
            (t (filter f (cdr x)))))
    
    some は引数が関数と1本のリストに限られていることを除き, Common Lisp (および Emacs Lisp の "cl" ライブラリ) の同名の関数と同様である。takedrop は Haskell に由来する。 take はリスト x の先頭の n 個からなる新しいリストを作る。 drop は先頭の n 個を削いだリストを返す。 この3者には特に遅延評価的なところはない。
    > (setq s '(a b c nil d e))
    (a b c nil d e)
    > (some null s)
    t
    > (take 3 s)
    (a b c)
    > (drop 3 s)
    (nil d e)
    > 
    
    zip は Python 3.0 のジェネレータ化された zip 関数と似ており,遅延評価的に結果のリストを生成する。 Haskell の同名の関数を非カリー化し,2引数以上を取れるようにしたものともいえる。 range に実質的な変更はないが同類の関数としてここに挙げた。 mapfilter は Haskell の同名の関数を非カリー化したものである。 Python 3.0 のジェネレータ化された mapfilter と似ているが, 引数は2引数に限られる。
    > (zip '(1 2 3) '(a b c d))
    ((1 a) . #<promise:2b8e50>)
    > (mapcar identity (zip '(1 2 3) '(a b c d)))
    ((1 a) (2 b) (3 c))
    > (mapcar + (map - (range 1 10)))
    (-1 -2 -3 -4 -5 -6 -7 -8 -9)
    > (mapcar + (filter (lambda (n) (= 0 (% n 3))) (range 1 50)))
    (3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48)
    > 
    
    scanl も Haskell の同名の関数を非カリー化したものである。 mapf は,結果のリストを生成するとき cdr 部だけを遅延評価する点を除き,map と同じである。

Common Lisp (および Emacs Lisp の "cl" ライブラリ) にも map があるが, こちらは3引数以上をとるから,将来,これらと map の仕様を共通化する余地がある。

Mac OS X 10.4.11 上の ruby 1.8.2, 1.8.6, 1.9.0-1 および jruby 1.0.3, 1.1 などで動作を確認した。 現行のすべての Ruby 処理系で動作すると期待される。

2. 前回の付録について

前回の付録のプログラム例はすべて同様に動作する。 さらに,フィボナッチ数列を下記のように追加の関数定義なしに与えることもできる (fibs1.l)。

(setq fibs
      (cons 1 (cons 1 ~(mapf (lambda (x) (apply + x))
                             (zip fibs (cdr fibs))))))

(print (nth 33 fibs))                   ; => 5702887

あるいは scanl を使って,次のように定義することもできる (fibs2.l)。

(setq fibs ~(scanl + 1 (cons 0 fibs)))

(print (nth 33 fibs))                   ; => 5702887

また,農夫と狼と山羊とキャベツの問題を解くプログラムを 下記のように書くことができる (farmer-and-wolf-etc1.l)。

;; "農夫と狼と山羊とキャベツ"
;; 猪股・益崎「Schemeによる記号処理入門」森北出版 1994年
;; §8「状態空間の探索」からヒントを得て

;; 農夫と狼と山羊とキャベツが川の南北どちらの岸に位置するかを
;; n か s を要素とする長さ 4 のリストで表現する。
;; 初期状態はすべて北岸に位置する: (n n n n)。
;; すべて南岸に位置する状態 (s s s s) へ到達する経路を探索する。

;; (moves '(s s n n)) => ((n n n n) (n s n n))
(defun moves (state)
  (let ((f (car state))                 ; farmer
        (w (cadr state))                ; wolf
        (g (caddr state))               ; goat
        (c (caddr (cdr state))))        ; cabbage
    (append
     (if (eq f w) `((,(opposite f) ,(opposite w) ,g ,c)))
     (if (eq f g) `((,(opposite f) ,w ,(opposite g) ,c)))
     (if (eq f c) `((,(opposite f) ,w ,g ,(opposite c))))
     `((,(opposite f) ,w ,g ,c)))))

(defun opposite (x)
  (if (eq x 'n) 's 'n))

;; (safe? '(s n s n)) => t
(defun safe? (state)
  (let ((f (car state))
        (w (cadr state))
        (g (caddr state))
        (c (caddr (cdr state))))
    (not (or (and (eq w g) (not (eq f w)))
             (and (eq g c) (not (eq f g)))))))

(defun goal? (state)
  (equal state '(s s s s)))

(defun make-tree (init-state)
  (cons init-state
        ~(map make-tree (moves init-state))))

;; 解となる状態の列をどれか一つ深さ優先探索する。
(defun search (tree)
  (nreverse (_search tree nil)))

(defun _search (tree path)
  (let ((STATE (car tree))
        (SUBTREES (cdr tree)))
    (let ((PATH (cons STATE path)))
      (if (goal? STATE)
          PATH
        (car (filter consp
                     (map (lambda (subtree)
                            (let ((state (car subtree)))
                              (and (safe? state)
                                   (not (member state PATH))
                                   (_search subtree PATH))))
                          SUBTREES)))))))

(setq whole-tree (make-tree '(n n n n)))
(print (search whole-tree))
;; => ((n n n n) (s n s n) (n n s n) (s s s n) (n s n n) 
;;     (s s n s) (n s n s) (s s s s))

;;(load "ruby-hack.l")
;;(terpri)
;;(print whole-tree)

探索後の状態空間も含め,元のプログラムと振舞は同一である。 ここで注目すべきは,元のプログラムで Common Lisp の同名の関数を実装した (find-if f list) 関数

;; from Common Lisp
(defun find-if (f list)
  (cond ((null list) nil)
        ((f (car list)) (car list))
        (t (find-if f (cdr list)))))

(car (filter f list)) で代用した点である。 これは,list の要素のうち述語関数 f を満たすものからなるリストの先頭 (car) を取り出す。 もしも遅延評価を使わなければ大変に非効率な方法だが, 実際には遅延評価的だから,find-if のようにはじめから述語関数 f を満たす最初の list の要素を探す場合と効率に大差はない。


次回へつづく


Copyright (c) 2008 OKI Software Co., Ltd.