ラムダ計算と無限ラムダ多項式(14) - エレファント・ビジュアライザー調査記録

有限ラムダ多項式 Lisp

「平方根の例」を移植するために Common Lisp のサブセットを目指した Lisp を作成します。これを「有限ラムダ多項式 Lisp」と呼ぶことにします。仕様は以下のようになります。

定数・変数

定数には数値、t (真を表す)、nil (偽を表す)があります。数値は任意の桁数の小数を使うことができます。定数と演算子以外の文字列は変数として使うことができます。

( 関数名式式 … 式 )

「式式 … 式」を引数として関数を実行します。「関数名」は

最初から定義されている関数名(car、cdr、cons、first、second、third、atom、null、list、progn、expt、equal、not、and、or など)
演算子(+、-、*、/、=、/=、<、<=、>、>= など)
定義された関数名
評価されると関数になる式
無名関数

のどれかです。

' 式

または (quote 式) とも書きます。式を評価しないものを表します。「'( 式式 … 式 )」と書くとリスト「( 式式 … 式 )」を表します。

(lambda (変数名変数名 … 変数名) 式式 … 式)

無名関数を表します。評価されるとクロージャーに変換されます。正式には #'～、または (function ～) と書くようですが、(Common Lisp では)単にこう書いても変換されるようなのでここでもそうします。

setf 変数名式

(できるだけ Common Lisp に合わせたいのですが Common Lisp の仕様がよくわからないので)ここでは単に変数に式を対応させるものとなっています。setq も同様です。変数は「レキシカルスコープ」とします。これは以前「環境」で定義した変数と同じもので、書いた通りの意味の変数(関数内関数や名前呼びの変数のような)で関数が終了しても使える変数となります。「レキシカルスコープ」の変数が存在すればその変数を変更し、存在しなければ新規作成するとします。

(defun 関数名 (変数名変数名 … 変数名) 式式 … 式)

関数を定義します。再帰的定義もできます。「レキシカルスコープ」で関数名とクロージャーを対応させます。この後関数名を評価するとクロージャーに変換されます。

(if 条件式式1 式2)

条件式を評価した結果が nil でなければ式1を評価、nil ならば式2を評価します。

平方根の例

(defun GetNextDecimalDigitAndNumbers
       (numbers)
       (progn (setf number (first numbers))
              (setf square_difference (second numbers))
              (setf scale (third numbers))
              (defun maxdd (dd)
                           (if (>= dd 0)
                               (progn (setf zd (* dd (expt 10 (- scale))))
                                      (setf number_sq_diff (+ (* (* number zd) 2) (* zd zd)))
                                      (if (<= number_sq_diff square_difference)
                                          (list dd
                                                (list (+ number zd)
                                                      (- square_difference number_sq_diff)
                                                      (+ scale 1)
                                                      )
                                                )
                                          (maxdd (- dd 1))
                                          )
                                      )
                               (list 0 (list 0 0 0))
                               )
                           )
              (maxdd 9)
              )
       )
(defun GenerateDecimal
       ()
       (progn (setf nums (list 0 3 0))
              (setf current_digit 0)
              (defun next
                     ()
                     (progn (setf current_digit (first (GetNextDecimalDigitAndNumbers nums)))
                            (setf nums (second (GetNextDecimalDigitAndNumbers nums)))
                            t
                            )
                     )
              (defun getCurrent () (progn current_digit))
              (defun setCurrent (val) (progn))
              (list next getCurrent setCurrent)
              )
       )

(defun take
       (count gen)
       (if (= count 0)
           ()
           (progn (setf next (first gen))
                  (setf getCurrent (second gen))
                  (setf setCurrent (third gen))
                  (if (next)
                      (cons (getCurrent) (take (- count 1) gen))
                      ()
                      )
                  )
           )
       )
(defun zipn
       (f n list)
       (if (null list)
           ()
           (cons (f (first list) n)
                 (zipn f (+ n 1) (cdr list))
                 )
           )
       )
(defun nlist
       (list)
       (zipn (function (lambda (n e) (* n (expt 10 (- e))))) 0 list)
       )
(defun foldr
       (f n list)
       (if (null list)
           n
           (f (first list) (foldr f n (cdr list)))
           )
       )
(defun number
       (list)
       (foldr (lambda (x y) (+ x y)) 0 (nlist list))
       )

サーバー側で計算し、一桁ずつ取得する例

(setf generator (GenerateDecimal))
(defun GetNextDecimalDigit
       ()
       (progn ((first generator)) ((second generator)))
       )
(defun repeat
       (number e count)
       (if (< e count)
           (repeat (+ number (* (GetNextDecimalDigit) (expt 10 (- e)))) (+ e 1) count)
           number
           )
       )
(setf count 21)
(repeat 0 0 count)

サーバー側で計算し、イテレーターを使う例

(setf count 21)
(number (take count (GenerateDecimal)))

ブラウザー側で計算し、(サーバー側の)データを更新する例

(setf numbers (list 0 3 0))
(defun repeat
       (number e count)
       (if (< e count)
           (progn (setf dd (first (GetNextDecimalDigitAndNumbers numbers)))
                  (setf ns (second (GetNextDecimalDigitAndNumbers numbers)))
                  (setf numbers ns)
                  (repeat (+ number (* dd (expt 10 (- e)))) (+ e 1) count)
                  )
           number
           )
       )
(setf count 21)
(repeat 0 0 count)

ブラウザー側で計算し、(サーバー側の)データを(ジェネレーターで)更新する例

(defun unfoldl
       (next init)
       (progn (setf src init)
              (setf dst 0)
              (defun next_
                     ()
                     (progn (setf dst (first (next src)))
                            (setf src (second (next src)))
                            t
                            )
                     )
              (defun getCurrent () (progn dst))
              (defun setCurrent (val) (progn))
              (list next_ getCurrent setCurrent)
              )
       )
(setf numbers (list 0 3 0))
(setf count 21)
(number (take count (unfoldl GetNextDecimalDigitAndNumbers numbers)))