独習 scheme 三週間 (3)
大掃除適当に終了。(早
Chapter.6
末尾再起が繰り返しになる理屈は理解できてるんですが、末尾再起な書き方が微妙。
で、6.1 letrec ですが何故に let* で NG なの??と思ったら後方参照 (って言うのか??) があるんですな。local-odd? の中の local-even? は解決できるが、local-even? の中の local-odd? は未定義なナニになるのか。で、それを解決するためのフォームが letrec である、とゆー理解で良いのかな。
で、色々試験してみた。
まず、let で再帰呼び出し。
guile> (define (xxx n) (let ((func (lambda (m) (if (zero? m) 0 (+ m (func (- m 1))))))) (func n))) guile> (xxx 5) standard input:69:30: In expression (func (- m 1)): standard input:69:30: Unbound variable: func ABORT: (unbound-variable) guile>
func は Unbound variable だそうな。letrec を使ってみる。
guile> (define (yyy n) (letrec ((func (lambda (m) (if (zero? m) 0 (+ m (func (- m 1))))))) (func n))) guile> (yyy 5) 15 guile>
うーむ。成程ねー、としか言いようがないなぁ。trace とゆーヤツを見つけたんで色々試してみる。リストの長さをソレな関数を。
guile> (define length (lambda (ls) (if (null? ls) 0 (+ 1 (length (cdr ls)))))) guile> (trace length) (length) guile> (length '(1 2 3)) [length (1 2 3)] | [length (2 3)] | | [length (3)] | | | [length ()] | | | 0 | | 1 | 2 3 3 guile>
びっくりだったのですが、同様の手続きを letrec 使って定義して trace してみたらこーなりました。(ってーか、リストが読みにくいぞ
guile> (define (length lst) (letrec ((f (lambda (l) (if (null? l) 0 (+ (f (cdr l)) 1))))) (f lst))) guile> (length '(1 2 3)) 3 guile> (trace length) (length) guile> (length '(1 2 3)) [length (1 2 3)] 3 3 guile>
上記二つの手続きはほぼ同じ、に見えるんですが、letrec 使ったら末尾再帰になるんですか??もしかして trace の見方が違うんかのぅ。いきなり 3 って微妙だなぁ。
トップレベルな関数定義だと末尾再帰にはならない、という理解でよいのか??ちょっと調べてみる必要ありそげ。
類推
トップレベルに定義された_関数_だと正に関数として処理されるんだろな。逆に letrec でローカルに定義された手続きは最適化できる、という解釈でビンゴっぽい。
つづき
名前付き let はスルー。短く記述できるから良いのかなぁ。
と、言いつつ 6.3 反復 のサンプルを letrec で書き直してみた。
(define list-position
(lambda (o l)
(let loop ((i 0) (l l))
(if (null? l) #f
(if (eqv? (car l) o) i
(loop (+ i 1) (cdr l)))))))
(define (list-position-2 o l)
(letrec ((loop (lambda (i o l)
(if (null? l)
#f
(if (eqv? (car l) o)
i
(loop (+ i 1) o (cdr l)))))))
(loop 0 o l)))(だんだん長めになってきたのでコードの書き方を改めてみる)
で guile なコンソールにコピペして trace かけてみました、の図が以下。
guile> (list-position 5 '(1 2 3)) [list-position 5 (1 2 3)] #f #f guile> (list-position-2 5 '(1 2 3)) #f guile> (trace list-position-2) (list-position-2) guile> (list-position-2 5 '(1 2 3)) [list-position-2 5 (1 2 3)] #f #f guile> (list-position 2 '(1 2 3)) [list-position 2 (1 2 3)] 1 1 guile> (list-position-2 2 '(1 2 3)) [list-position-2 2 (1 2 3)] 1 1 guile>
一応末尾再帰になってそげ、には見える。
しかしこうやって見るに名前付き let の方が簡潔で可読性は良さげだなぁ。
もう一つサンプルあり。
(define reverse!
(lambda (s)
(let loop ((s s) (r '()))
(if (null? s) r
(let ((d (cdr s)))
(set-cdr! s r)
(loop d s))))))
動かしてみる。
guile> (reverse! '(1 2 3 4 5)) (5 4 3 2 1) guile>
手続きの名前に感嘆符 (!) が付いてるとゆー事は副作用あり??
guile> (define list '(1 2 3 4 5)) guile> (reverse! list) (5 4 3 2 1) guile> list (1) guile>
やはりか。こんなコトできるのかな??
guile> (set! list '(1 2 3 4 5)) guile> list (1 2 3 4 5) guile> (set! list (reverse! list)) guile> list (5 4 3 2 1) guile>
を、できた。なんか子供がオモチャをいぢくり回してる感満載だな。
では letrec 版を。
(define (reverse-2! s)
(letrec ((loop (lambda (s r)
(if (null? s)
r
(let ((d (cdr s)))
(set-cdr! s r)
(loop d s))))))
(loop s '())))試験。
guile> (reverse-2! '(1 2 3 4 5)) (5 4 3 2 1) guile> (set! list (reverse-2! list)) guile> list (1 2 3 4 5) guile>
一応 trace で確認してみる。
guile> (trace reverse!) (reverse!) guile> (set! list (reverse! list)) [reverse! (1 2 3 4 5)] (5 4 3 2 1) guile> list (5 4 3 2 1) guile> (trace reverse-2!) (reverse-2!) guile> (set! list (reverse-2! list)) [reverse-2! (5 4 3 2 1)] (1 2 3 4 5) guile> list (1 2 3 4 5) guile>
map もスルーかな。あと、ざくっと見たトコでは Chapter.7 から Chapter.12 までスルーかも。一応マクロ (Chapter.8) は確認しなければならなくなるっぽい。いきなりハードルがばくっと上がるなぁ。
# ってーかスルー多い。
