Chapter 05

数値処理と記号処理

TAKIZAWA Yozo
TAKIZAWA Yozo
2021.12.19に更新

数値演算のための基本関数

前章までに演算・述語関数として,+(和)-(差)*(積)eq(=)lt(<)が登場しました.fpLISPでは,他に次のふたつが用意されています.
/ :商を求める

fpLISP
(/ 10 3)
33

%:剰余(余り)を求める

fpLISP
(% 10 3)
1

組込関数としては驚くほど少ないと感じると思います.fpLISPの方針が『最低限の基本構文・組込関数のみ』というのもあります[1]が,関数を組み合わせて作成した関数規則が,既にある基本的な関数表現とあまり違いがなく,必要な関数は都度構成・利用しやすいという特徴が影響していると言えます.

述語関数については,基本関数としてand or notに相当するものがありませんが,これらもifと真偽値を用いたラムダ式で容易に構成できます[2]

fpLISP
((lambda (and)
   (cons (and (eq 0 0) (eq 0 0))
   (cons (and (eq 0 1) (eq 0 0))
   (cons (and (eq 0 0) (eq 0 1))
   (cons (and (eq 0 1) (eq 0 1)) nil)))))
 (lambda (a b) (if a b nil)))
(t nil nil nil)
fpLISP
((lambda (or)
   (cons (or (eq 0 0) (eq 0 0))
   (cons (or (eq 0 1) (eq 0 0))
   (cons (or (eq 0 0) (eq 0 1))
   (cons (or (eq 0 1) (eq 0 1)) nil)))))
 (lambda (a b) (if a t b)))
(t t t nil)
fpLISP
((lambda (not)
   (cons (not (eq 0 0))
   (cons (not (eq 0 1)) nil)))
 (lambda (a) (if a nil t)))
(nil t)

記号における名前と値の違い

これまで,名前としての変数をラムダ式で用いてきましたが,この変数に,数値を使うことはできません[3].なぜなら,数値はそれだけでとして認識され,別の値の名前にすることを想定していないためです.一方,数値以外の記号の列,特に,英語アルファベットで構成される単語は通常,何も指定がなければ,プログラム中で変数(名前)として扱われます.もし,このような記号列を値として扱いたい場合は,特別な指定が必要となります.

多くのプログラミング言語では,値としての記号列は『文字列』として扱い,ダブルクォーテーションやシングルクォーテーションで常に括る表記が広く使われています.ですが,本書のfpLISPを始めとするLISP系言語では,関数の引数として与える時のみ,値であることを指定する方法をとっており,quoteという構文キーワードを用います.

fpLISP
(quote hoge)
hoge
fpLISP
(cons (quote a) (quote b))
(a . b)

quoteは,リスト構造やペア構造にも使用できます.すなわち,consを用いて構成せずとも,評価結果と同じ表記でそれぞれのデータ構造を値として与えることができます.

fpLISP
(cdr (quote (1 2 3 4 5)))
(2 3 4 5)
fpLISP
(cdr (quote (a . 10)))
10

したがって,たとえば,前章の連想リストの検索については,

fpLISP
((a . 10) (b . 20) (c . 30) (d . 40) (e . 50))

から検索キーcに対応する値を得るという表現ができ,具体的には,前章のmemberを用いて次のようになります.

fpLISP
(cdr (car
  (((lambda (u) (u u))
    (lambda (u)
      (lambda (f v)
        (if (eq v nil) nil
            (if (f v) v
                ((u u) f (cdr v)))))))
 (lambda (x) (eq (quote c) (car (car x))))
 (quote ((a . 10) (b . 20) (c . 30) (d . 40) (e . 50))))))
30

記号処理を組み合わせた例

次は,プログラミングの世界ではおなじみの『FizzBuzz問題』を,前章のunfoldで構成・評価した例です.unfoldの関数規則がラムダ式の引数に値として設定され利用していることに注意して下さい.

fpLISP
((lambda (unfold)
   (unfold (lambda (x)
             (if (lt 30 x) nil
                 (cons
                   (if (eq (% x 15) 0) 'FizzBuzz
                   (if (eq (% x  3) 0) 'Fizz
                   (if (eq (% x  5) 0) 'Buzz x)))
                   (+ x 1))))
           1))
 ((lambda (u) (u u))
  (lambda (u)
    (lambda (f x)
      ((lambda (r)
         (if (eq r nil) nil
             (cons (car r) ((u u) f (cdr r)))))
       (f x))))))
(1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz)

次は,ラムダ式として評価すると,全く同じラムダ式が評価結果となって終了する関数規則です[4].このような,自己のプログラム記述と完全に一致する記述が,評価・実行結果として得られるプログラムは,『クワイン』と呼ばれています.

fpLISP
((lambda (x) (cons x (cons (cons (quote quote) (cons x (quote nil))) (quote nil)))) (quote (lambda (x) (cons x (cons (cons (quote quote) (cons x (quote nil))) (quote nil))))))
((lambda (x) (cons x (cons (cons (quote quote) (cons x (quote nil))) (quote nil)))) (quote (lambda (x) (cons x (cons (cons (quote quote) (cons x (quote nil))) (quote nil))))))

練習問題

次のラムダ式は,連想リスト検索を応用したプログラムです.先に登場した連想リスト検索のラムダ式にassocという名前を付け,新しく定義したsublis1と名付けられたラムダ式の引数に渡され,利用されています.

fpLISP
((lambda (assoc sublis1)
   (sublis1
     (quote ((a . alpha) (r . gamma) (d . delta)))
     (quote (a b c d e))
     assoc))
 ((lambda (u) (u u))
  (lambda (u)
    (lambda (k v)
      (if (eq v nil) nil
          (if (eq k (car (car v)))
              (cdr (car v))
              ((u u) k (cdr v)))))))
 ((lambda (u) (u u))
  (lambda (u)
    (lambda (al L assoc)
      (if (eq L nil) nil
          (cons
            ((lambda (r) (if (eq r nil) (car L) r))
             (assoc (car L) al))
            ((u u) al (cdr L) assoc)))))))

処理内容は,sublis1の引数のひとつとして指定した連結リスト

(a b c d e)

のそれぞれの要素について,もうひとつの引数である連想リスト

((a . alpha) (r . gamma) (d . delta))

を検索した結果に置き換える,というものです.検索した結果がなかった場合の要素は,置き換えずにそのままとするため,最終的な実行結果は次の通りとなります.

(alpha b c delta e)

このラムダ式について,連想リストはそのままに,連結リストとして

(alpha beta gamma delta epsilon)

を引数として与えると,逆の処理,すなわち,

(a beta r d epsilon)

を評価結果として出力するようにするにはどのように修正すれば良いか考え,解答して下さい.

脚注
  1. 基本構文に至っては,括弧と空白区切りおよびドットを用いるS式,既出のlambdaif,後述のquoteしかありません. ↩︎

  2. ifは関数ではなく構文ですが,関数と同じく,最終的な評価結果を返すであることに注意して下さい. ↩︎

  3. 処理系によってはできなくはないのですが,少なくともfpLISPではできません. ↩︎

  4. 第3章のループ式と異なり,評価・実行を終了することに注意して下さい. ↩︎