Archive for the ‘letex’ Tag
projecteuler11．．．または、関数を作る関数
Filed under: Projecteuler | タグ: clean, dotimes, flat, for-all, letex, transpose
コメントを残す projecteuler の問題11 は、20 行 20 列の数値から縦、横、対角方向で連続する四つの数値の積の最大値を求めるの。
まずは、一行から四つの数値の積を求める関数を考えます。
(define (make_product-n n)
(letex (n n)
(fn (lst)
(let (res)
(dotimes (i (- (length lst) n 1))
(if (for-all number? (i n lst))
(push (apply * (i n lst)) res -1)))
res))))
これは、いわゆる関数を作る関数です。マクロでも良かったのですが（笑）。
引数の n に 4 を与えれば、リスト中の連続する四つの数値の積を計算してリストで返してくれます。組込 letex を使って、戻り値の関数（ラムダ式）に引数の n の評価値を渡すのがポイント。戻り値の関数に即値を渡すなら、マクロによりも引数が評価される関数の方が都合が良かったりします。組込 letex は、newLISP のマクロ（fexpr）作成の要。いずれ、詳細に紹介したいところですが、、、
さて、戻り値の関数は、渡された n の評価値を使って、slice 的な暗黙な要素指定で取り出される要素の積を変数 res に入れていきます。
繰り返し関数 dotimes は指定した回数分だけ繰り返し動作を行います。for-all も組込関数で、引数の述語に対してリストの中身が全て true になる時、true を返します。
さて、動作例は、
> ((make_product-n 4) (sequence 1 10)) (24 120 360 840 1680) >
こんな感じ。
後は、与えられた行列数値文字を数値に直して、計算するだけ。
> [cmd]
(let (product-n (make_product-n 4)
matrix
(map (fn(x) (map (fn (y) (int y nil 10)) (parse x " ")))
(clean null?
(parse [text]
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
[/text] {\r|\n} 0))))
(let (res (map product-n matrix))
(push (map product-n (transpose matrix)) res -1)
(let (len (length matrix) tmp1 nil tmp2 nil)
(dolist (x matrix)
(push (append (dup nil (- len 1 $idx)) x (dup nil $idx)) tmp1 -1)
(push (append (dup nil $idx) x (dup nil (- len 1 $idx))) tmp2 -1))
(push (map product-n (transpose tmp1)) res -1)
(push (map product-n (transpose tmp2)) res -1))
(apply max (clean nil? (flat res)))))
[/cmd]
70600674
>
説明するまでもないかもしれませんが、最初に行ごとに四つの積を求め、
(map product-n matrix)
次に関数 transpose 使って行と列を入れ替え、列の値も求めます。
(map product-n (transpose matrix))
transpose は組込関数で、転置行列を返します。
残りは対角方向。対角方向が一列になるよう、各行に対応した nil を追加します。対角方向は二つあるので、
(dolist (x matrix)
(push (append (dup nil (- len 1 $idx)) x (dup nil $idx)) tmp1 -1)
(push (append (dup nil $idx) x (dup nil (- len 1 $idx))) tmp2 -1))
両方作成し、関数 transpose 使って行と列を入れ替え、行にして計算します。
計算結果は全て、変数 res に入れておき、最後に、
(apply max (clean nil? (flat res)))
で、求める値を出すわけです。
flat は組込関数で、リスト内の余分な括弧を全て取り払ってくれます。v.10.5 からは取り去る括弧の階層も指定できるようになり、さらに便利に（笑）。
関数 product-n は計算対象に nil が入っているものには nil を返すので、組込関数 clean で nil を片付けから、組込関数 max に引渡します。
と、こんなところ。
以上、如何でしょうか？
newLISP で On Lisp する．．．第７章（その１）
（この blog は、“short short story または 晴耕雨読な日々”からの引越してきたもの。スクリプトは、newLISP V10.2.1 以降で動作するように書き直しています。
defun 等の newLISP組込関数に無い関数は、特に断らない限り、newlisp-utility.lsp に定義してあります。）
第７章 マクロ 。“On Lisp”本書によれば、ここから第１０章までが、マクロの基礎講座。
最初は、マクロはどのように動作するか です。 newLISP のマクロは、CommonLisp のマクロと異なりますが、まずは、同じ点から
- 引数は、評価されずに展開される。
newLISP と Common Lisp 共に、これが、関数とマクロの最大の違いでしょう。
そして、newLISP と CommonLisp のマクロの違いです。
- CommonLisp のマクロは、マクロ本体で評価したもの（通常は式）を返し、マクロが呼び出された場所で、再び評価される。（つまり、マクロ内とマクロ外とで、評価が２回ある。）
- newLISP のマクロは、マクロ内で評価されたものを返す。
ここで言う Common Lisp のマクロ内の評価は、引数として与えられた（評価されていない）式を変形するという意味です。マクロ外の評価は、変形された式を文字通り評価することです。私は、この違いを認識するまで、Common Lisp のマクロの理解にてこずりました。
そして、newLISP には、Common Lisp でいうの２回目の評価が無いということ。この違いを例で見てみましょう。
(define-macro (nil! var)
(list 'setq var nil)) これは、“On Lisp”本書の例をそのまま、newLISPに当てはめたものです。
動作は、
> (setq x 1) 1 > x 1 > (nil! x) (setq x nil) > x 1 > (eval (nil! x)) nil
となります。newLISP では、全ての変数が、初期値に nil を割り当てられ、設定されたのかどうかわからないので、動作を確認する前に、変数に初期値を入れています。
さて、結果は、マクロnil! の本体で評価された結果出来た式が現れています。Common Lisp であれば、最初の例では、この式が評価されて、変数 x に nil が入りますが、newLISP では、式のままです。マクロで展開された式に eval を使って評価すると、変数 x に nil が入ります。
ということで、本書のマクロ例を newLISP で書くと、次のようになります。
(define-macro (nil! var)
(set var nil))
動作は、
> (setq x 2) 2 > x 2 > (nil! x) nil > x nil
という具合に、所望の動作をします。
Common Lisp 風に setq を使うなら、
(define-macro (nil! var)
(setq (eval var) nil)) といったところ。newLISP のマクロでは、文字通り、引数が本体に、評価されずに渡されます。つまり、引数は、クォートされて本体に渡されるのです。そのため、setq を使ったマクロnil! では、eval が必要だったのです。
こんな、newLISP のマクロですが、Commno Lisp並みのマクロ表現ができるのか？ 結論から言えば、出来ます（たぶん、笑）。その回答が、次の項になります。
今回のメイン、バック･クォート です。 Common Lisp では、マクロが呼び出された場所で評価される式を作るために、マクロを組みます。そして、式を作るのに、組込の list と同じ働きをする `（バック･クォート）を多用します。その際、 ` 内で使われる、 ,（カンマ）と ,@（カンマ・アット） との組み合わせは、必須みたいなものでしょう。
newLISP には、バック･クォートがありません。記述した式がそのまま、展開されます。そして、 ` 内で使われる ,（カンマ）と ,@（カンマ・アット）に取って代わるのが、newLISP組込の letex です。“On Lisp”本書では、バック･クォートを使う・使わない例が記述されていますが、newLISP では、letex を使う例だけ示します。
(define-macro (nif expr pos zero neg)
(letex (_expr expr
_pos pos
_zero zero
_neg neg)
(case (sgn _expr)
(1 _pos)
(0 _zero)
(-1 _neg))))引数名を明示する書き方と、そうでない方です。動作は、本書にある CommonLisp でバック･クォートを使う・使わない例の動作と全く一緒です。
> (map (fn (x) (nif x 'p 'z 'n)) '(0 2.5 -8)) (z p n)
さて、letex の役割は、let と同じように見えますが、違いを前述の nil! で見てみましょう。次の四つは全て同じ動作です。
(define-macro (nil! var)
(letex (_var var)
(setq _var nil)))
(define-macro (nil! var)
(let (_var var)
(setq (eval _var) nil)))
(define-macro (nil! var)
(letex (_var var)
(set '_var nil)))
(define-macro (nil! var)
(let (_var var)
(set _var nil)))如何でしょうか？ let では、引数がそのまま評価されずに本体の展開式に渡されますが、letex では、クォートが外されて、本体に渡されています。つまり、letex 内で引数が評価されたわけです。
(define-macro (test var)
(let (_var var)
(letex (_var2 var)
(list _var _var2))))というマクロを定義して、
> (setq x 1) 1 > (test x) (x 1) > (list 'x x) (x 1)
newLISP では、マクロが呼び出された場所での（２回目の）評価がありません。そこで必要となるのが、letex なのです。letex には、引数が評価されずに（クォート付きで）わたされますので、それを評価して、変数に入れます。上記例では、変形してませんが、ここで変形もできます。定義された変数は、letex に続く本体の中に展開され、評価されます。この評価の際、変数は変形された式となっているわけですから、Common Lisp の２回目の評価に相当する評価になるわけです。ですから、newLISPでのマクロには、letex が、ほぼ必須といってよいでしょう。もちろん、使わなくても、定義できます、例えば、defun の定義とか。
次に、マクロour-when を例に、CommonLispの `（バック･クォート）、 ,（カンマ）と ,@（カンマ・アット）と newLISP の letex の関係を見ていきましょう。
(define-macro (our-when test)
(letex (_test test
_body (cons 'begin (args)))
(if _test
_body)))Common Lisp で ,test となるところは、そのまま、letex で _test に設定しています。問題は、,@（カンマ・アット）の部分です。本書の CommonLisp の例で、body となっている部分と (args) は、同じ内容です。CommonLisp の ,@（カンマ・アット）は、リストの要素を展開してくれます。しかし、newLISP には、それに相当するものがありません。そこで、,@（カンマ・アット）を適用したい場所を括っている括弧までを letex で設定します。それが、３行目です。 begin は、CommonLisp の progn に相当する newLISP の組込です。 begin と (args) を cons することで、(progn ,@body) に相当する部分を用意しています。 Common Lisp で newLISP風に書くとこうなります。
(defmacro our-when (test &body body)
(let ((_test test)
(_body (cons 'progn body)))
`(if ,_test
,_body)))
Common Lispのマクロをこの状態に変形して、let を letex に変え、バック･クォートとカンマを削除すれば、newLISP用マクロの完成です（笑）。
もちろん、letex は、関数でも使えます。第５章で散々使いましたので、例は省略します。
次の 単純なマクロの定義 からは、our-while の定義だけで十分でしょう。
(define-macro (our-while)
(letex (_test (args 0)
_body (cons 'begin (1 (args))))
(do ()
((not _test))
_body)))引数の test は _test に再定義しているだけですから、(args) から直接取っています。_body は、begin を cons することで、本書の例で ,@body が展開するものと同等になるようにしています。newLISPには、do はありません。第３章（その１）で使ったマクロです（使用には、newlisp-utility.lsp が必要）。マクロの展開にマクロを使っても動作します。
> (let (i 0) (our-while (< i 2) (print i) (++ i)) i) 012
マクロ展開の確認 からは、次回に。
以上、如何でしょうか？
新リスプな日々 