数値演算のための基本関数
前章までに演算・述語関数として,+
(和)-
(差)*
(積)eq
(=)lt
(<)が登場しました.fpLISPでは,他に次のふたつが用意されています.
※/
:商を求める
(/ 10 3)
33
※%
:剰余(余り)を求める
(% 10 3)
1
組込関数としては驚くほど少ないと感じると思います.fpLISPの方針が『最低限の基本構文・組込関数のみ』というのもあります[1]が,関数を組み合わせて作成した関数規則が,既にある基本的な関数表現とあまり違いがなく,必要な関数は都度構成・利用しやすいという特徴が影響していると言えます.
述語関数については,基本関数としてand
or
not
に相当するものがありませんが,これらもif
と真偽値を用いたラムダ式で容易に構成できます[2].
((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)
((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)
((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
という構文キーワードを用います.
(quote hoge)
hoge
(cons (quote a) (quote b))
(a . b)
quote
は,リスト構造やペア構造にも使用できます.すなわち,cons
を用いて構成せずとも,評価結果と同じ表記でそれぞれのデータ構造を値として与えることができます.
(cdr (quote (1 2 3 4 5)))
(2 3 4 5)
(cdr (quote (a . 10)))
10
したがって,たとえば,前章の連想リストの検索については,
((a . 10) (b . 20) (c . 30) (d . 40) (e . 50))
から検索キーc
に対応する値を得るという表現ができ,具体的には,前章のmemberを用いて次のようになります.
(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
の関数規則がラムダ式の引数に値として設定され利用していることに注意して下さい.
((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].このような,自己のプログラム記述と完全に一致する記述が,評価・実行結果として得られるプログラムは,『クワイン』と呼ばれています.
((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
と名付けられたラムダ式の引数に渡され,利用されています.
((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)
を評価結果として出力するようにするにはどのように修正すれば良いか考え,解答して下さい.