エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

ラムダ計算と無限ラムダ多項式(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)))