vallog: 9LISP - 003 までの宿題

（なんで背景黒くなっちゃうの？）

9LISPは毎回宿題が出るので取り合えずかいつまんでやってみます。（今のところ私が適当に見繕って出してるわけですが・・・）

;; 次のコードの評価を考えてみる
(((lambda (x)(lambda (x)(+ x 1))) 2) 4)

評価順序とスコープについて考えさせられます。目が慣れないと面食らいそうです。評価すると5が返ります。

インデントを付けてみます。

(((lambda (x)
    ;; x = 2
    (lambda (x)
      ;; x = 4
      (+ x 1)))
2)
4)
; -> 5

次のlet式と等価と言ってよさそうです。

(let ((x 2))
(let ((x 4))
(+ x 1)))
; -> 5

これも上記と等価。

(let* ((x 2)
(x 4))
(+ x 1))

let式は初期値式が先に全て評価された後、変数名に束縛されるため下記のコードはエラーとなります。つまりbの位置からaは見えない。

(let ((a 10)
(b (+ a 10)))
(+ a b))
; -> error

letrec

初期値式が評価される時に同一レベルの束縛されていない変数名（値不定）も見えている。

(letrec ((a 10)
(b (+ a 10)))
(+ a b))
; -> 30

無名関数でスコープを作ったり真偽値を定義したり条件分岐してみたり、無名関数で再帰してみたりということについてはラムダ計算について調べるとおもしろそうです。

Schemeでラムダ計算

組み込みの特殊形式ifと同じ動作をするnew-if手続きを定義してみる

ifがなぜ特殊形式であるか考えてみる（SICPより）

(define new-if
(lambda (pred then-exp else-exp)
    (cond
     (pred then-exp)
     (else else-exp))))

(new-if #t 1 2)

; -> 1
(new-if #f 1 2)

; -> 2
(new-if #t (print 10)(print 20))

; -> 10
20
#<undef>

(new-if #t (print 10)(print 20)) を見るとわかる通り、引数が両方とも評価されています。組み込みのifはpredicateによってちゃんとどちらか一方が評価されます。このnew-ifで再帰を書くと大変なことになりますね。

こうしちゃえばどうかな・・・。

((new-if #t (lambda ()(print 10))(lambda ()(print 20))))

引数がatomであるか判定するatom?手続きを定義してみる（The Little Schemerより）

(define atom?
(lambda (x)
(and (not (pair? x)) ;; 対でない
(not (null? x))))) ;; かつ空リストでもない

これでも良いのか？

(define atom?
(lambda (x)
(not (list? x))))

あーダメか、ベクタとか。でもそれだと上のもダメか・・・。どうしたらいいんだ。取り合えずこれで。

引数のリストの要素がすべてatomであるか判定するlat?手続きを定義してみる（The Little Schemerより）

(define lat?
(lambda (l)
    (cond
     ((null? l) #t)
     ((atom? (car l))
      (lat? (cdr l)))
     (else #f))))

引数で指定されたatomが引数のリスト内に存在するか判定するmember?手続きを定義してみる（The Little Schemerより）

(define member?
(lambda (a lat)
    (cond
     ((null? lat) #f)
     ((eq? a (car lat)) #t)
     (else (member? a (cdr lat))))))

またはこんなの。

(define member?
(lambda (a lat)
    (cond
     ((null? lat) #f)
     (else (or (eq? a (car lat))
               (member? a (cdr lat)))))))

FizzBuzz

(use srfi-1)
(define fizzbuzz
(lambda (x)
    (map (lambda (n)
           (cond
            ((zero? (modulo n 15)) "FizzBuzz")
            ((zero? (modulo n 5)) "Buzz")
            ((zero? (modulo n 3)) "Fizz")
            (else n)))
         (iota x 1))))
(print (fizzbuzz 100))

これはプログラミングGaucheで見かけたコードが印象に残ってる。

こんなのもありかな。

(((lambda (f)
    (f f))
(lambda (f)
    (lambda (n)
      (if (<= n 100)
          (begin
            (print (cond
                    ((zero? (modulo n 15)) "FizzBuzz")
                    ((zero? (modulo n 5)) "Buzz")
                    ((zero? (modulo n 3)) "Fizz")
                    (else n)))
            ((f f)(+ n 1))))))) 1)

流行っていると聞いて - ループを使わずに1から10までの総和を表示するプログラム

階乗

(define fact
(lambda (n)
    (if (zero? n)
        1
        (* n (fact (- n 1))))))
(fact 5)

またはこんなのもありかな。

(use srfi-1)
(define fact
(lambda (n)
(apply * (iota n 1))))
(fact 5)

他にもfoldとか・・・。

(use srfi-1)
(define fact
(lambda (n)
(fold * 1 (iota n 1))))
(fact 10)

継続渡しスタイルだとこう？

(define fact/cps
(lambda (n cont)
    (if (zero? n)
        (cont 1)
        (fact/cps (- n 1)(lambda (x)
                           (cont (* x n)))))))
(fact/cps 5 (lambda (x) x))

フィボナッチ数

(define fib
(lambda (n)
    (if (or (zero? n)(= 1 n))
        n
        (+ (fib (- n 1))(fib (- n 2))))))
(fib 10)
; -> 55

コラッツの問題

(define collatz
(lambda (n)
    (cons n
          (cond
           ((< n 0) #f)
           ((= n 1) '())
           ((even? n)(collatz (/ n 2)))
           ((odd? n)(collatz (+ (* n 3) 1)))
           (else #f)))))
(collatz 10)

アッカーマン関数

(define Ackerman
(lambda (m n)
    (cond
     ((zero? m)
      (+ n 1))
     ((zero? n)
      (Ackerman (- m 1) 1))
     (else (Ackerman (- m 1)(Ackerman m (- n 1)))))))
(Ackerman 2 3)

引数を大きくすると大変です。

階乗 - 末尾再帰

(define tail-call-fact
(lambda (n)
    (letrec ((iter (lambda (m r)
                     (if (zero? m)
                         r
                         (iter (- m 1)(* r m))))))
      (iter n 1))))
(tail-call-fact 5)

フィボナッチ数を末尾再帰で書く、というところでギブ。おやすみなさい。