2016-06-10

Scheme手習い(21) eval、またはvalue、またはmeaning(2)

いよいよ関数適用に入ります

(define function-of car)
(define arguments-of cdr)
(define *application
  (lambda (e table)
    (ls-apply (meaning (function-of e) table)
           (evlis (arguments-of e) table))))

(define evlis
  (lambda (args table)
    (cond ((null? args) (quote ()))
          (else (cons (meaning (car args) table) 
                      (evlis (cdr args) table))))))

リストのcarを評価して返された関数を、リストのcdrを評価して返された引数リストに適用します
applyという関数はすでに存在してて定義できないのでls-applyという名前にしてます

(define primitive?
  (lambda (l) (eq? (first l) (quote primitive))))
(define non-primitive?
  (lambda (l) (eq? (first l) (quote non-primitive))))
(define ls-apply
  (lambda (fun vals)
    (cond ((primitive? fun) (apply-primitive (second fun) vals))
          ((non-primitive? fun) (apply-closure (second fun) vals)))))

primitiveな関数だったらapply-primitiveを、
non-primitiveな関数であればapply-closureを呼びます
(second fun)は適用しようとしている関数、valsは引数リストです

まずはprimitiveな関数の処理から

(define apply-primitive
  (lambda (name vals)
    (cond ((eq? name (quote cons)) (cons (first vals) (second vals)))
          ((eq? name (quote car)) (car (first vals)))
          ((eq? name (quote cdr)) (cdr (first vals)))
          ((eq? name (quote null?)) (null? (first vals)))
          ((eq? name (quote eq?)) (eq? (first vals) (second vals)))
          ((eq? name (quote atom?)) (:atom? (first vals)))
          ((eq? name (quote zero?)) (zero? (first vals)))
          ((eq? name (quote add1)) (add1 (first vals)))
          ((eq? name (quote sub1)) (sub1 (first vals)))
          ((eq? name (quote number?)) (number? (first vals))))))

ほとんどの関数は対応する関数を呼んでいるだけです
atom?の処理だけ別の関数を呼んでいます

(define :atom?
  (lambda (x)
    (cond ((atom? x) #t)
          ((null? x) #f)
          ((eq? (car x) (quote primitive)) #t)
          ((eq? (car x) (quote non-primitive)) #f)
          (else #f))))

atomなはずのprimitiveな関数は、*constで(primitive <関数>)というリストに
置き換えられてしまっているためその場合分けをしています
non-primitiveな関数の判定はどう見ても不要ですがなにかを暗示しているんでしょうか
primitiveを判定したんだからnon-primitiveも、くらいの話？

> (value '(cons 1 (quote ())))
(1)
> (value '(add1 1))
2

動きました
condの例ももうちょっとそれっぽくすることができます

> (value '(cond ((null? (quote (a))) #f)
                (else #t)))
#t

ここからが本丸（自分がやりたい順に進めてます）
変数とλ式とクロージャを一気に導入します
ほぼ三位一体
まずは*lambdaから

(define *lambda
  (lambda (e table)
    (build (quote non-primitive)
           (cons table (cdr e)))))

なにかごたいそうなことをするのかと思ったらこれだけ
現時点のテーブルとλ式のcdrをリストにして取っておくだけです

だから(mk-length mk-length)を評価すると無限に評価が終わらないときでも
(lambda (x) ((mk-length mk-length) x))はすぐに評価が終わる、というわけです

> (value '(lambda (n) (add1 n)))
(non-primitive (() (n) (add1 n)))
> (value '(lambda (hoge) (hage hige)))
(non-primitive (() (hoge) (hage hige)))
> (value '(lambda (x) ((mk-length mk-length) x)))
(non-primitive (() (x) ((mk-length mk-length) x)))

mk-lengthが定義されている必要すらありません

ここで保存した、現時点のテーブルとλ式のcdr、つまり引数リストと関数本体を
まとめてクロージャと呼びます
(lambda ...)を評価するとクロージャが返されることになります

クロージャからテーブル、引数リスト、関数本体を取り出す関数を定義します

(define table-of first)
(define formals-of second)
(define body-of third)

（ここで使うためにthirdを定義してたのか）

次に、クロージャを評価する関数を用意します

(define apply-closure
  (lambda (closure vals)
    (meaning (body-of closure)
             (extend-table (new-entry (formals-of closure) vals)
                           (table-of closure)))))

クロージャを評価するには、以下のような処理を行います

クロージャの引数リストと、引数の値のリストからエントリを作る
作ったエントリをクロージャのテーブルに追加する
追加してできたテーブルを利用してクロージャの本体部分を評価する

これでやっと識別子と値が結び付けられるようになりました
なぜテーブルでは名前と値のペアのリストを持つのではなく
名前のリストと値のリストのペアを持つようにするのか少し疑問でしたが
引数リストをそのまま使いたいからということのようです

識別子を評価するには単にテーブルを名前で検索するだけ
lookup-in-tableの出番です

(define *identifier
  (lambda (e table)
    (lookup-in-table e table initial-table)))

initial-tableは次のとおりです。

(define initial-table
  (lambda (name)
    (car (quote ()))))

どう見てもエラーです
ありがとうございました

いつ、これは使われますか。

テーブルを最後まで検索したけれども名前が見つからなかったときですね

使われないことを祈りましょう。どうしてだと思いますか？

valueで評価している式が誤っているから、ってことでいいんでしょうか

あえてエラーを起こすくらいしか評価を途中で止める方法がないので
何かエラーを起こす式を書いただけで
式には別に意味はない？

> (value '((lambda (n) (add1 x)) 1))
mcar: contract violation

たぶんエラーメッセージはRacket特有

さてそれはともかく、これで関数適用も動くようになりました
動きを追ってみます

  (value '((lambda (n) (add1 n)) 1))
= (meaning '((lambda (n) (add1 n)) 1) '())
= (*application '((lambda (n) (add1 n)) 1) '())
= (ls-apply (meaning '(lambda (n) (add1 n)) '()) (evlis '(1) '()))
= (ls-apply (meaning '(lambda (n) (add1 n)) '()) '(1))
= (ls-apply (*lambda '(lambda (n) (add1 n)) '()) '(1))
= (ls-apply '(non-primitive (() (n) (add1 n))) '(1))
= (apply-closure '(() (n) (add1 n)) '(1))
= (meaning '(add1 n) (extend-table '((n) (1)) '()))
= (meaning '(add1 n) '(((n) (1))))
= (*application '(add1 n) '(((n) (1))))
= (ls-apply (meaning 'add1 '(((n) (1)))) (evlis '(n) '(((n) (1)))))
= (ls-apply '(primitive add1) (evlis '(n) '(((n) (1)))))
= (ls-apply '(primitive add1) (cons (meaning 'n '(((n) (1)))) '()))
= (ls-apply '(primitive add1) (cons (*identifier 'n '(((n) (1)))) '()))
= (ls-apply '(primitive add1) (cons (lookup-in-table 'n '(((n) (1))) initial-table) '()))
= (ls-apply '(primitive add1) '(1))
= (apply-primitive 'add1 '(1))
= 2

もう少しテーブルを育ててみます

  (value '((lambda (x) ((lambda (y) (cons x y)) (quote ()))) 1))
= (meaning '((lambda (x) ((lambda (y) (cons x y)) (quote ()))) 1) '())
= (ls-apply (meaning '(lambda (x) ((lambda (y) (cons x y)) (quote ()))) '())
            (evlis '(1) '()))
= (ls-apply '(non-primitive (() (x) ((lambda (y) (cons x y)) (quote ()))))
            '(1))
= (meaning '((lambda (y) (cons x y)) (quote ())) '(((x) (1))))
= (ls-apply (meaning '(lambda (y) (cons x y)) '(((x) (1))))
            (evlis '((quote ())) '(((x) (1)))))
= (ls-apply '(non-primitive ((((x) (1))) (y) (cons x y))) '(()))
= (meaning '(cons x y) '(((y) (())) ((x) (1))))
= (ls-apply (meaning 'cons '(((y) (())) ((x) (1))))
            (evlis '(x y) '(((y) (())) ((x) (1)))))
= (ls-apply '(primitive cons) '(1 ()))
= (cons 1 '())
= '(1)

クロージャの説明抜きで出てきたコレも今なら説明がつくでしょうか

(define eq?-c
  (lambda (a)
    (lambda (x)
      (eq? x a))))
(define eq?-salad (eq?-c 'salad))

> (eq?-salad 'salad)
#t
> ((eq?-c 'salad) 'salad)
#t

ただしdefineがないので例によってlambdaで名前をつけます
eq-2?というのは、ふたつの要素が等しいかどうかを返す関数の引数のひとつに2を入れたもの
つまり引数が2と等しいかどうかを返す関数です

((lambda (eq-c?)
   ((lambda (eq-2?) 
     (eq-2? 2))
   (eq-c? 2)))
 (lambda (a)
   (lambda (x)
     (eq? x a))))

追いかけます

  (value '((lambda (eq-c?) ((lambda (eq-2?) (eq-2? 2)) (eq-c? 2)))
           (lambda (a) (lambda (x) (eq? x a)))))
= (meaning '((lambda (eq-c?) ((lambda (eq-2?) (eq-2? 2)) (eq-c? 2)))
             (lambda (a) (lambda (x) (eq? x a))))
           '())
= (meaning '((lambda (eq-2?) (eq-2? 2)) (eq-c? 2))
           '(((eq-c?) ((non-primitive (() (a) (lambda (x) (eq? x a))))))))
= (meaning '(eq-2? 2)
           '(((eq-2?) ((non-primitive ((((a) (2))) (x) (eq? x a)))))
             ((eq-c?) ((non-primitive (() (a) (lambda (x) (eq? x a))))))))
= (meaning '(eq? x a) '(((x) (2)) ((a) (2))))
= #t

eq-2?は(eq? x a)のaに2を入れたものであるということがそのまま表現されています
defineでいったんひとくぎり付くところはちょっと表現できてません
説明がついたかというと微妙

これで終わりですか。

はい。疲れました。

疲れました

でも、(define ...)はどうなのでしょう。

再帰はYコンビネータによって得られるので、必要はありません。

> (value
   '(((lambda (le)
        ((lambda (mk-length)
           (mk-length mk-length))
         (lambda (mk-length)
           (le (lambda (x)
                 ((mk-length mk-length) x))))))
      (lambda (length)
        (lambda (l)
          (cond ((null? l) 0)
                (else (add1 (length (cdr l))))))))
     '(1 2 3)))
⇛ 3

Yコンビネータによる変形を行うと、インタプリタ上でインタプリタを走らせることが可能であるということですか。

はい。でもそんなに悩まないでください。

やれっていってるんでしょうか

else

はい。もう宴会の時間です。

2016-06-05

Scheme手習い(20) eval、またはvalue、またはmeaning

littleschemer

ついに最終章、ラスボス2です
小さいschemeの核にあたるもの、いわゆる？evalを作ります
でもこの本ではvalueっていう名前になってます
でもvalueは空っぽの環境を作るだけで実際の仕事の中心はmeaningという関数がやってます

ラスボス2と言っても、Yコンビネータみたいに何がなんだかわからないようなものではなく
ひとつひとつの関数はとてもシンプルで難しくはありません
そのかわり、たくさんの関数があるのでそれらの関連を理解する必要があります
あと、環境と呼ばれるデータ構造も

この本ではこれまでクロージャとか関数の評価方法とか説明が省かれていた部分がありますが
この章を理解すればあそこはそういうことだったのか、と納得できます
「この本では形式的な定義はしない」ので代わりにソース見ろということですね
「この本を2回以下で読み切ろうとしないこと」というのは
この章をクリアしたら２周目に突入してもう１回読め、ということを言っているのではないかと

いつもどおりなんの説明もなく始まります

エントリ(entry)とはリストのペアであり、その第1のリストが集合であるものです。

これがインタプリタの作り始めだと誰が思うでしょうかいや思いません
（知ってる人は別として）

エントリを扱うための関数を定義します

(define new-entry build)
(define lookup-in-entry
  (lambda (name entry entry-f)
    (lookup-in-entry-help name (first entry) (second entry) entry-f)))
(define lookup-in-entry-help
  (lambda (name names values entry-f)
    (cond ((null? names) (entry-f name))
          ((eq? (car names) name) (car values))
          (else (lookup-in-entry-help name (cdr names) (cdr values) entry-f)))))

buildは名前の集合と値のリストからエントリを作る関数、
lookup-in-entryはエントリ内で名前に対応する値を得る関数です
entry-fは名前を引数に取る関数で、名前が見つからない場合に呼ばれます
こういうのも継続っていうんでしょうか
違う気がしますけど何が違うかというとわかりません
やっぱり継続かもしれません

名前と値の対応をつけるなら、名前と値のペアを作ってそれをリストにするほうが
自然な気がしますが理由はあとでわかります
そもそもまだ何を作っているのかわかってませんし

テーブル（table、環境ともいう）とはエントリのリストだとします。

テーブルを扱うための関数を定義します

(define extend-table cons)
(define lookup-in-table
  (lambda (name table table-f)
    (cond ((null? table) (table-f name))
          (else (lookup-in-entry 
                 name (car table) 
                 (lambda (name) 
                   (lookup-in-table name (cdr table) table-f)))))))

extend-tableはテーブルにエントリを追加する関数、
lookup-in-tableはテーブルから名前に対応する値を得る関数です

extend-tableのシンプルさには度肝を抜かれる思いです
本気で言語書くときはもっといろいろくっつくのかな
エラー処理とか

table-fはやはり名前を引数に取る関数で、名前が見つからない場合に呼ばれます
entry-fはここで、テーブル内の次のエントリから名前を探すために使われています
そうやって使うのかー

知らないで「テーブルから値を探す関数を書け」と言われたら
そこをパラメータにしようとは考えず直接書いてしまいそうですけど

(define lookup-in-table2
  (lambda (name table)
    (cond ((null? table) #f)
          ((lookup-in-entry2 name (car table)))
          (else (lookup-in-table2 name (cdr table))))))
(define lookup-in-entry2
  (lambda (name entry)
    (lookup-in-entry-help2 name (first entry) (second entry))))
(define lookup-in-entry-help2
  (lambda (name names values)
    (cond ((null? names) #f)
          ((eq? (car names) name) (car values))
          (else (lookup-in-entry-help2 name (cdr names) (cdr values))))))

実は大きなごまかしをしてて、失敗すると#fを返すんですが、
ということは値が#fの場合と区別がつかなくなっています
見つかった値と成功／失敗と両方返せるとか、
例外があるとかならちゃんとしたものにできるんですけど

そういう方法がないから仕方なく失敗したときに呼ぶ関数を渡してます、ってことでしょうか？
それだけではなくて、何かもっといいことがあるような気がするんですが
パラメータにしておくと柔軟ではありそうですが柔軟性が役に立っているかな？

しばらくの間、ゴシック体で書いてあるところはプログラムそっくりだけど
valueという関数が扱うデータだよっていう話
ゲーデルの証明みたい

続いて、式のタイプを考えます。

定数 *const ※組み込みの関数も含まれます
quote *quote
識別子 *identifier
ラムダ式 *lambda
cond *cond
関数適用 *application

式のタイプを返すexpression-to-actionを作ります
単にcondが並んでいるだけで難しくはありません
consとかcarとかの組み込み関数が*constとして扱われるのがちょっと意外でした
関数というくくりで見れば*lambdaにも近いような気がするんですが
関数へのポインタみたいなものと思えば確かに定数

タイプはそのタイプの式を評価する関数を兼ねていますので
式をexpression-to-actionに渡せば評価できます
(quote ())というのは環境です
最初はまだ覚えておくべき変数がないので環境はからっぽです

(define value
  (lambda (e) (meaning e (quote ()))))
(define meaning
  (lambda (e table)
    ((expression-to-action e) e table)))

環境を扱う関数を定義して、
タイプを判別する関数を定義して、
式を評価する関数を定義するというトップダウンともボトムアップともとれない
不思議な順番には何か意味があるんでしょうか
わかりません

とりあえずガワができたので、少しずつ作っては動かすことができます
定義してない関数があっても、呼び出すまではエラーになりません
こういうときはありがたいです

(define *const
  (lambda (e table)
    (cond ((number? e) e)
          ((eq? e #t) #t)
          ((eq? e #f) #f)
          (else (build (quote primitive) e)))))

さっき気になった組み込み関数はここで(primitive hoge)という形になって
ちょっと別扱いになります
じゃあ*primitiveみたいなタイプ作ってもいいんじゃないかと

さて

> (value 1)
1
> (value #t)
#t
> (value 'cons)
(primitive cons)

やったー！
・・・という感じはまだしませんけどとりあえずインタプリタ動きました

(define *quote
  (lambda (e table)
    (text-of e)))
(define text-of second)

eを見てほげほげすればいいんだな、ということがちょっと見えてきました

> (value '(quote abc))
abc

本文だとこの後*identifierと*lambdaを定義してから*condなんですが
*identifierと*lambdaだけあってもつまらないので先に*condやります

これまでより複雑ですが、ただリストをいじってるだけです

(define else?
  (lambda (x)
    (cond ((atom? x) (eq? x (quote else)))
          (else #f))))
(define question-of first)
(define answer-of second)
(define evcon
  (lambda (lines table)
    (cond
      ((else? (question-of (car lines)))
       (meaning (answer-of (car lines)) table))
      ((meaning (question-of (car lines)) table)
       (meaning (answer-of (car lines)) table))
      (else (evcon (cdr lines) table)))))
(define cond-lines-of cdr)
(define *cond
  (lambda (e table)
    (evcon (cond-lines-of e) table)))

(else #f)あたりにちょっと不自然さを感じます
(and (atom? x) (eq? x (quote else)))で済むはずですが
セルフで実行できるようにってことかな
（ここで定義するインタプリタはandを実装していないことからして）

> (value '(cond (#t 1)))
1
> (value '(cond (#f 1) (#t 2)))
2
> (value '(cond (#f 1) (else 2)))
2

動いてます
変数も関数もないのでかなり不自然なcondですが

2016-06-01

Scheme手習い(19) Yコンビネータ(4)

littleschemer

Yコンビネータでいろいろな関数を動かしてみます

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

再帰しない関数を渡しても動くかな

((Y (lambda (add2) (lambda (n) (add1 (add1 n))))) 1)
⇛ 3

動いた！

じゃあ、2引数の関数は？

((Y
  (lambda (member?) 
    (lambda (a lat)
      (cond ((null? lat) #f)
            ((eq? (car lat) a) #t)
            (else (member? a (cdr lat)))))))
 'c '(a b c))
⇛ エラー

(f f)は引数をひとつしか取らないもんなあ
頭使わずに解決してみます

(define Y2
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x y) ((f f) x y)))))))

((Y2
  (lambda (member?) 
    (lambda (a lat)
      (cond ((null? lat) #f)
            ((eq? (car lat) a) #t)
            (else (member? a (cdr lat)))))))
 'c '(a b c))
⇛ #t

動きました
でも引数の数ごとにY作んなきゃいけないとか頭使わなさすぎです

じゃあ、カリー化したら？

(((Y
   (lambda (member?) 
     (lambda (a)
       (lambda (lat)
         (cond ((null? lat) #f)
               ((eq? (car lat) a) #t)
               (else ((member? a) (cdr lat))))))))
  'c) '(a b c))
⇛ #t

動きました
リストの中にcを含むかどうかを判定する関数を作り、その関数を(a b c)に適用しています
細かく考えだすと頭がパンク気味です

カリー化って、引数の順番どうなんですかね
並んだ引数のなかで特別扱いがひとつだけ

(((Y
   (lambda (member?) 
     (lambda (lat)
       (lambda (a)
         (cond ((null? lat) #f)
               ((eq? (car lat) a) #t)
               (else ((member? (cdr lat)) a)))))))
  '(a b c)) 'c)
⇛ #t

当然ながらこれでも動きます
引数の順番は考えて決めましょう

3引数は？
2回カリー化するのかな？
いや1回だけでよさそうです

(((Y
   (lambda (insertR)
     (lambda (lat)
       (lambda (old new)
         (cond ((null? lat) (quote ()))
               ((eq? (car lat) old) (cons old (cons new (cdr lat))))
               (else (cons (car lat) ((insertR (cdr lat)) old new))))))))
  '(a b c)) 'b 'd)
⇛ (a b d c)

oldとnew・latの組に分けるのはブサイクな気がしたのでlatを外に出しました

*関数も動きました

(((Y
   (lambda (rember*)
     (lambda (a)
       (lambda (l)
         (cond ((null? l) (quote ()))
               ((atom? (car l))
                (cond ((eq? (car l) a) ((rember* a) (cdr l)))
                      (else (cons (car l) ((rember* a) (cdr l))))))
               (else (cons ((rember* a) (car l)) ((rember* a) (cdr l)))))))))
  'b) '((a b c) a b c))
⇛ ((a c) a c)

入れ子になった再帰はどうでしょうか？

(((Y
   (lambda (o*)
     (lambda (n)
       (lambda (m)
         (cond ((zero? m) 0)
               (else (((Y
                        (lambda (o+)
                          (lambda (m)
                            (lambda (n)
                              (cond ((zero? n) m)
                                    (else ((o+ (add1 m)) (sub1 n)))))))) 
                       n) ((o* n) (sub1 m)))))))))
  2) 3)
⇛ 6

動きました

o+に名前をつけてやれば見やすいかな？

((((lambda (o+)
     (Y
      (lambda (o*)
        (lambda (n)
          (lambda (m)
            (cond ((zero? m) 0)
                  (else ((o+ n) ((o* n) (sub1 m))))))))))
   (Y
    (lambda (o+)
      (lambda (n)
        (lambda (m)
          (cond ((zero? m) n)
                (else (add1 ((o+ n) (sub1 m))))))))))
  2) 3)

o*にも名前をつけてやってもいいですね

((lambda (o+)
   ((lambda (o*)
      ((o* 2) 3))
    (Y
     (lambda (o*)
       (lambda (n)
         (lambda (m)
           (cond ((zero? m) 0)
                 (else ((o+ n) ((o* n) (sub1 m)))))))))))
 (Y
  (lambda (o+)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) n)
              (else (add1 ((o+ n) (sub1 m))))))))))

じー

名前をつけて呼び出す・・・だと・・・？

(define ...)は何ですか。

もしかして、これがdefineってこと？

(define ... )は正しく動作するといえますか。

defineは実はlambdaだから正しく動作する？

確かに。いまや再帰とは何かを知っています。

再帰だけちょっと心配だったけど、Yがあれば書けるし？

そういうことなんでしょうか？

defineにしちゃちょっとスコープ的にうるさい感じがしますが
というのは、こういう書き方ではうまくいかなかったので

((lambda (o* o+)
   ((o* 2) 3))
 (Y
  (lambda (o*)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) 0)
              (else ((o+ n) ((o* n) (sub1 m)))))))))
 (Y
  (lambda (o+)
    (lambda (n)
      (lambda (m)
        (cond ((zero? m) n)
              (else (add1 ((o+ n) (sub1 m))))))))))

o*からo+が見えてないんです
見た目はきれいなだけに残念
入れ子にして書けばいいんですが
ちょっと書き方変えるぐらいでうまくいかないかなあ

入れ子にして書かなきゃいけないとすると相互に呼び合う関数は大丈夫かと気になります
こういうのとか

(define ev?
  (lambda (n)
    (cond ((zero? n) #t)
          (else (od? (sub1 n))))))

(define od?
  (lambda (n)
    (cond ((zero? n) #f)
          (else (ev? (sub1 n))))))

どうやって書きましょう
od?を埋め込んじゃいましょうか

((Y
  (lambda (ev?)
    (lambda (n)
      (cond ((zero? n) #t)
            (else ((lambda (n)
                     (cond ((zero? n) #f)
                           (else (ev? (sub1 n)))))
                   (sub1 n)))))))
 3)

これはこれで動きますが、od?を作ろうと思ったらほとんど同じコードをもう一度書かないといけません
かなり癪に障ります

こんなふうに書いて動かないかなーと思いましたが無理でした
やっぱりev?からはod?が、od?からはev?が見えません

((lambda (ev? od?)
   (od? 3))
 (lambda (n)
   (cond ((zero? n) #t)
         (else (od? (sub1 n)))))
 (lambda (n)
   (cond ((zero? n) #f)
         (else (ev? (sub1 n))))))

さて。

ev?からod?が呼べる必要があり、od?からev?が呼べる必要がある、というのは
lengthからlengthを呼び出す必要がある、というのと似ています
Yコンビネータを作るときのやり方で1から作ってみます

まずは呼びたい関数を引数に取るようにします
ev?に当たる関数からはod?を呼び出しますのでev?ではなくod?を引数に取るというのが
今までと違います

;ev?に似た関数
(lambda (od?)
  (lambda (n)
    (cond ((zero? n) #t)
          (else (od? (sub1 n))))))
;od?に似た関数
(lambda (ev?)
  (lambda (n)
    (cond ((zero? n) #f)
          (else (ev? (sub1 n))))))

次に、今作った関数に名前をつけます。

((lambda (e? o?)
   'ここはあとで考える)
 ;ev?に似た関数
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 ;od?に似た関数
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

ev?に似た関数、od?に似た関数から、mk-ev?、mk-ed?を作ります
mk-ev?はmk-ev?もmk-od?も使いますので、2引数を取る関数になります
ちょっとめんどくさい

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      'ここはあとで考える)
    ;mk-ev?
    (lambda (mk-od? mk-ev?)
      (e? (mk-od? mk-ev? mk-od?)))
    ;mk-od?
    (lambda (mk-ev? mk-od?)
      (o? (mk-ev? mk-od? mk-ev?)))))
 ;ev?に似た関数
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 ;od?に似た関数
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

このままだとやっぱり止まらないのでlambdaで囲みます

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      'ここはあとで考える)
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

関数を返してできあがり・・・なんですが関数を2つ返すことができません
(mk-ev? mk-od? mk-ev?)を返せばev?に
(mk-od? mk-ev? mk-od?)を返せばod?になります

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      (mk-od? mk-ev? mk-od?))
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))

ev?、od?に名前を付けて両方使えるようにするにはどうするといいでしょう？
関数をふたつ返すことはできませんから中で使う？

((lambda (e? o?)
   ((lambda (mk-ev? mk-od?)
      ((lambda (ev? od?)
         (display (ev? 2)) (newline)
         (display (ev? 3)) (newline)
         (display (od? 2)) (newline)
         (display (od? 3)) (newline))
       (mk-ev? mk-od? mk-ev?)
       (mk-od? mk-ev? mk-od?)))
    (lambda (mk-od? mk-ev?)
      (e? (lambda (n) ((mk-od? mk-ev? mk-od?) n))))
    (lambda (mk-ev? mk-od?)
      (o? (lambda (n) ((mk-ev? mk-od? mk-ev?) n))))))
 (lambda (od?)
   (lambda (n)
     (cond ((zero? n) #t)
           (else (od? (sub1 n))))))
 (lambda (ev?)
   (lambda (n)
     (cond ((zero? n) #f)
           (else (ev? (sub1 n)))))))
⇛ #t
  #f
  #f
  #t

動きました
動いたんですけどここまでしないといけないかとちょっと疑問
ちょっと変えるだけとか、せめてYを2回使うくらいでできないもんですかね

2016-05-29

Scheme手習い(18) Yコンビネータ(3)

littleschemer

関数を再帰させることができればYコンビネータも峠を越えたんじゃないでしょうか
あとは、形を整えてやるだけのはずですから

defineなしで再帰できるようになったlengthがこれ

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((mk-length mk-length) (cdr l))))))))

先回りして目指す形はこれ

((lambda (le)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (le (lambda (x)
            ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (length (cdr l))))))))

↓の、「lengthに似た関数」（なんか名前ないのかな）を与えれば再帰する関数になる
便利な関数を取り出したいってことです

(lambda (length)
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (length (cdr l)))))))

元の形と目指す形を見比べると、(lambda (l) ...)の部分が
「lengthに似た関数」の中身に似てますね
元の形の(mk-length mk-length)がlengthに相当してるので
(mk-length mk-length)にlengthと名前をつけてやります

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   ((lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))
    (mk-length mk-length))))

これで、「lengthに似た関数」の形が作れました
めでたしめでたし、ではなくて

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      ((lambda (length)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))
       (mk-length mk-length))))
   '(1 2 3))
(応答なし)

帰ってきません
しばらくすると「このプログラムはメモリを使いきりました」

何がおかしかったのか追ってみます
評価するには関数と引数を評価してやる必要がありますが
引数はこれ以上評価することはできませんので放置し関数部分に着目します

関数部分がまた(関数引数)という形ですので上のlambdaのmk-lengthに
下のlambdaを入れてやります

((lambda (mk-length)
   ((lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))
    (mk-length mk-length)))
 (lambda (mk-length)
   ((lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))
    (mk-length mk-length))))

わかりづらくなってきましたが前回で初めて再帰したバージョンの形に似ています
全体を見るとやはり(関数引数)という形ですので上のlambdaのmk-lengthに
下のlambdaを入れてやります

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 ((lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond
           ((null? l) 0)
           (else (add1 (length (cdr l)))))))
     (mk-length mk-length)))
  (lambda (mk-length)
    ((lambda (length)
       (lambda (l)
         (cond
           ((null? l) 0)
           (else (add1 (length (cdr l)))))))
     (mk-length mk-length)))))

引数のほうが、一つ前に出てきた関数とそっくりの形になりました
引数自体が(関数引数)という形ですのでこれを評価しようとすると
また同じ形が出てきて再現がありません

mk-lengthを自分自身に何度も何度も適用し続けているからです

そのとおりですね
なにせ

再帰とはどんなものですか。
任意の関数へのmk-lengthの適用が無限に連鎖しているようなものです。

というくらいですから
まさしく文字通りにできあがりました

実際は無限に続けなくても、リストの長さを出すのに十分なだけ繰り返したら
やめてしまっていいんですが
完全に関数の形が確定するまで続き、途中でやめちゃうことはできないってことなんでしょうね

(mk-length mk-length)に名前をつける前はなぜうまくいっていたかというと
elseの中に入っていたので必要なときにしか評価されなかったからということでしょう

一見無限に評価が続いてしまいそうだけど必要な分だけ評価すればいい、っていうと
Haskellで書けば解決しそうな気もしますが軽く検索してみたところでは
別の問題があって簡単じゃないようです

lengthを作る関数から
(mk-length mk-length)
を抽出した以上、それはそれ以上関数を返してはいません。

意味がわかりません
それって何
誰かおしえてください

でどうするかっていうと、ここが山場2かと思いますけど、

(mk-length mk-length)が1引数の関数を返すとすると、
(lambda (x) ((mk-length mk-length) x))も1引数の関数を返しますか。

返しますね
それが何か？

それでは、以上のことをmk-lengthの自分自身への適用に対して行ってみましょう。

本ではなぜか(mk-length mk-length)をくくりだす前に戻ってコレやってから
あらためてくくり出し直してますが理由は読み取れてません
くくりだした形のほうで(mk-length mk-length)をlambdaに入れてやっても
同じ形ができあがります

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   ((lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l)))))))
    (lambda (x) ((mk-length mk-length) x)))))

これでまた動くようになってます

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      ((lambda (length)
         (lambda (l)
           (cond
             ((null? l) 0)
             (else (add1 (length (cdr l)))))))
       (lambda (x) ((mk-length mk-length) x)))))
   '(1 2 3))
3

(mk-length mk-length)を(lambda (x) ((mk-length mk-length) x))に
書き換えたら何が起こって動くようになったんでしょうか

さっきと同じように評価していくと、同じようなステップをたどってこうなります

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 (lambda (x)
   (((lambda (mk-length)
       ((lambda (length)
          (lambda (l)
            (cond
              ((null? l) 0)
              (else (add1 (length (cdr l)))))))
        (lambda (x) ((mk-length mk-length) x))))
     (lambda (mk-length)
       ((lambda (length)
          (lambda (l)
            (cond
              ((null? l) 0)
              (else (add1 (length (cdr l)))))))
        (lambda (x) ((mk-length mk-length) x))))) x)))

これも(関数引数)の形ですが、引数の方がさっきは(関数引数)の形だったものが
今度は(lambda (x) ((関数引数) x))になってます
これは関数適用ではなくてひとつのラムダ式なのでそのままで関数を適用できます
ここがミソかな

適用するとこうです

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 ((lambda (x)
                   (((lambda (mk-length)
                       ((lambda (length)
                          (lambda (l)
                            (cond
                              ((null? l) 0)
                              (else (add1 (length (cdr l)))))))
                        (lambda (x) ((mk-length mk-length) x))))
                     (lambda (mk-length)
                       ((lambda (length)
                          (lambda (l)
                            (cond
                              ((null? l) 0)
                              (else (add1 (length (cdr l)))))))
                        (lambda (x) ((mk-length mk-length) x))))) x))
                 (cdr l))))))

こんどは全体がひとつのラムダ式になりました
((lambda (x) ((mk-length mk-length) x)) (cdr l))を評価することになるのは
(null? l)が偽のときだけ
つまり必要な時しか評価しない、が実現されています
ここもミソだな

なのでこれでいったん評価が終わったことになって
この関数を(1 2 3)に適用してやると想定どおり3が返されるというわけです

ふう

いよいよ「lengthに似た関数」に名前をつけて外に出してやります
「lengthに似た関数」は一番外に出してやりたいので、全体をlambdaで囲みます
「lengthに似た関数」にはleという名前をつけます

((lambda (le)
   ((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (le (lambda (x) ((mk-length mk-length) x))))))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

動きます

> (((lambda (le)
      ((lambda (mk-length)
         (mk-length mk-length))
       (lambda (mk-length)
         (le (lambda (x) ((mk-length mk-length) x))))))
    (lambda (length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 (length (cdr l))))))))
   '(1 2 3))
3

コレが完成版で上半分が適用順Yコンビネータと呼ばれてるそうです

たぶん(mk-length mk-length)が裸のままの形が素のYコンビネータ

なんで「適用順」Yコンビネータっていう名前なんでしょうね？
適用順に何かする、というより適用順に評価する処理系でも動くよ、っていう感じですが

(define ... )は正しく動作するといえますか。

言えるんですか？

確かに。いまや再帰とは何かを知っています。

再帰が何かを知っているのとdefineの動作とどういう関係があるんでしょうか
Yコンビネータの話のとっかかりは

(define ...)は何ですか
興味深い質問です。(define ...)はwill-stop?に対しては
うまく働かないことを見たばかりです。

でしたが何か解決したんでしょうか
わかりません

(Y Y)は何ですか。

想像もつきません

(lambda (length)
  (lambda (l)
    (cond
      ((null? l) 0)
      (else (add1 (length (cdr l)))))))

と

(lambda (le)
  ((lambda (f) (f f))
   (lambda (f) (le (lambda (x) ((f f) x))))))

ってなんとなく形は似てますけどね

何ともいえませんが一生懸命に動きます。

とにかくメモリを使いきってくれることはわかりました

2016-05-21

Scheme手習い(17) Yコンビネータ(2)

littleschemer

defineなしで再帰を実現できたものの、わかった感が薄くて今ひとつ

eternityの唐突感
(mk-length mk-length)の手品感

このあたりを解決しないと眠れそうにありません
いえ寝ます
いえ自分なりに納得感のある道を探してみます
厳密さよりも感覚的に納得できるような方向で

まずはlengthからスタート
defineを使わずに同じことを書けたら勝ち

(define length
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (length (cdr l)))))))

defineが使えないので取ります

(lambda (l)
  (cond ((null? l) 0)
        (else (add1 (length (cdr l))))))

が残っていてはいけないので、仮にselfという名前を入れておきます

(lambda (l)
  (cond ((null? l) 0)
    (else (add1 (self (cdr l))))))

このままではselfが定義されてないよと怒られてしまうので、lambdaの仮引数にしてしまいましょう

(lambda (self)
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (self (cdr l)))))))

これで一応ちゃんとした関数になりました
あとはselfに元の関数を入れてやれば再帰するんじゃ？
正確には自分自身じゃないけど、同じコードならいいよね？
同一人物じゃないけど双子の弟みたいな

((lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (self (cdr l)))))))
 (lambda (l)
   (cond ((null? l) 0)
         (else (add1 (self (cdr l)))))))

ほらほらほら
もうできちゃったんじゃないの？

> (((lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 (self (cdr l)))))))
    (lambda (l)
      (cond ((null? l) 0)
            (else (add1 (self (cdr l)))))))
   '(1 2 3))
self: undefined;

あーそうですねー外側のselfは定義されてないですねー
馬鹿ですねー
外側のselfがエラーにならないようにするにはどうすればいいでしょう？

じー

そうか、外側の関数も引数でself自身を受け取るようにすればいいですね！
こう

((lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (self (cdr l)))))))
 (lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 (self (cdr l))))))))

おっといけない
このselfは自分自身を引数に取って、つまり(self self)となって初めて
さっきまでのselfになるのでいじってやらないと

((lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 ((self self) (cdr l)))))))
 (lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 ((self self) (cdr l))))))))

これでもう動かない理由はないはず

> (((lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((self self) (cdr l)))))))
    (lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((self self) (cdr l))))))))
   '(1 2 3))
3

動きました

(lambda (self) ...)が2箇所あります
これはself自身なのでselfと名前をつけましょう

((lambda (self)
   (self self))
 (lambda (self)
   (lambda (l)
     (cond ((null? l) 0)
           (else (add1 ((self self) (cdr l))))))))

できましたね

> (((lambda (self)
      (self self))
    (lambda (self)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((self self) (cdr l))))))))
   '(1 2 3))
3

(self self)が(self self)を呼び続ける、ってことですね
selfがself自身を呼び出せればいいんだけど
selfはself自身のことを知らないからselfを渡してやる、と
いったところでしょうか

あれこれ考えてるうちにこの関数も普通に再帰に見えてきましたよ

2016-05-18

Scheme手習い(16) Yコンビネータ

littleschemer

ラスボス１来ました

Yコンビネータってのはこれ
正確には適用順Yコンビネータって言うらしいです

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

何がなんだかわかりません
こんなの読んでふむふむとかわかっちゃう人がいるんでしょうか
恐ろしいです

順番に見ていくしかありません

(define ...)は何ですか。

何でしょうか

では、再帰的定義とは何ですか。

何でしょう
哲学でしょうか

これはあのlength関数ですか。

(define length
  (lambda (l)
    (cond ((null? l) 0)
          (else (add1 (length (cdr l)))))))

そうですね

次の関数は何をするものでしょう。
(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 (eternity (cdr l))))))

なんでしょうか
lengthとそっくりですけど、eternityってあの無限ループするやつでしょうか

空リストの長さを決めますが、ほかには何も決めません。

確かにおっしゃるとおりです
「決める」より「求める」と書いたほうが馴染みがある感じ

> ((lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (eternity (cdr l))))))
   '())
0
> ((lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (eternity (cdr l))))))
   '(1))
(応答なし)

eternityの次くらいに部分的な関数ですね

この関数は便宜上length0と呼びます
eternityのところをlength0自身に置き換えてやると
判定できる要素数がひとつ増えて空リストまたは1要素のリストの長さを求める関数になります

(lambda (l)
  (cond
    ((null? l) 0)
    (else (add1 ((lambda (l)
                   (cond
                     ((null? l) 0)
                     (else (add1 (eternity (cdr l))))))
                 (cdr l))))))

これはlength1
この調子でlength2、length3とどんどん置き換えてやれば
任意の数までの要素を含むリストの数が数えられるようになります

でも無限の関数は書くことはできません。

そうですね

これらのプログラムにはすべてlengthに似た関数があります。おそらくこの関数を抽象化する必要があるのでしょう。

どんどん置き換えるかわりに関数呼び出しにするってことですね
DRY原則で

lengthと似ているけれども(lambda (length) ...)で始まる関数が必要です。

なにがしたいんでしょうか

このことでしょうか。

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 eternity)

ははーん
defineで名前を付けられないからlambdaの引数にして名前を付けるってわけですね
どうやらここがひとつのミソ

これはlength0を生成します。

たしかに、lengthをeternityに置き換えてやればlength0そのものです
length1は以下のようになります
length0のeternityの部分をlength0に置き換えてやればできあがり

((lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))
 ((lambda (length)
    (lambda (l)
      (cond
        ((null? l) 0)
        (else (add1 (length (cdr l)))))))
  eternity))

引数を置き換えてやればlength1になることはすぐ確認できます
length2から先も同様
でもなにかよくなったんでしょうか？
eternityのあたりでひとひねりしたらいいことありそうな予感はします

近いですが、まだ繰り返しがあります。

そうですね。コピペコーディングはよくないです

lengthを引数として取り、lengthに似た関数を返す関数に名前をつけましょう。

「lengthを引数として取り、lengthに似た関数を返す関数」っていうのはこれですね

(lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l)))))))

名前をつけるにはlambdaの引数にすればいいんでした

((lambda (mk-length)
   ...)
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

これで、...のところでは「lengthを引数として取り、lengthに似た関数を返す関数」を
mk-lengthと書けるようになりました
「lengthを引数として取り、lengthに似た関数を返す関数」にeternityを渡したものが
length0でしたので、length0はこうなります

((lambda (mk-length)
   (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

length0のeternityのところをlength0自身に置き換えるとlength1になるんでした

((lambda (mk-length)
   (mk-length
    (mk-length eternity)))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

おお、重複が消えました
D・R・Y! D・R・Y!
これでたくさん書いても平気です

((lambda (mk-length)
   (mk-length
    (mk-length
     (mk-length
      (mk-length eternity)))))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

あとは無限に書けばできあがり！

再帰とはどんなものですか。

任意の関数へのmk-lengthの適用が無限に連鎖しているようなものです。

任意の関数？
ってeternityのこと？

実際に無限の連鎖が必要ですか。

もちろん、そんなことはありません。

長さを調べたいリストは有限ですもんね

何回必要かを推測することはできるでしょうか。

長くても100個まで、とか仕様書に書いてあればいいんですけどそうでなければ無理
たぶん100個くらいで充分なんで、とか言ったら品証の人が怒るんじゃないですかね

十分に大きな数を推測しなかったことはいつわかりますか。

最も内側のmk-lengthに渡されたeternityを実行するときです。

eternityを呼んじゃったら負けですね

この時点でeternityに対してmk-lengthをもう一回実行するように書くとどうなりますか。

言ってる意味がわかりません

どんな関数がmk-lengthに渡されるのか誰も気にしないので、

どうせeternityは呼ばれちゃいけないので、何を渡しても同じ
だからさっき「任意の関数」って言ってたんですね

最初にmk-lengthを渡すこともできますね。

まあいいんじゃないですかね
なんで渡したいのか知りませんけど

そうすれば、eternityに対してmk-lengthを適用した結果をcdrに対して
適用することで、連鎖をもう一段先に進めることができます。

ええとどういうことですか
ええとええと

長過ぎるリストを引数にとったとき、これまで(eternity (cdr l))ってなってた呼び出しが
((mk-length eternity) (cdr l))になってくれるってことですかね

最初にeternityを渡すのをやめてmk-lengthを渡すってことは、

((lambda (mk-length)
   (mk-length eternity))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

のeternityをmk-lengthに変えるってことですね

((lambda (mk-length)
   (mk-length mk-length))
 (lambda (length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (length (cdr l))))))))

eternityがどっかいっちゃいました
さっき思ってたことと違いますね
わかりません！

脳内で動かしてみます
空リストを渡せば0が返ります

空でないリストを渡すとlength0は無限ループに入りましたがこれはどうなるでしょう
連鎖がもう一段先に進むでしょうか？
(1)を渡してみます
lがnull?ではないので、(length (cdr l)) つまり(mk-length '())が呼ばれます
ここでmk-lengthは(lambda (length) ...)でlengthには'()が渡されます
なんかおかしいです

さらにlengthをmk-lengthという名前に変更することさえできます。
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 (mk-length (cdr l))))))))

どういうリファクタリングでしょうか
間違いじゃないのはわかるんですけど

なぜ、こんなことをしたいのでしょうか。

気になりますね

すべての名前は同等ですが、ある名前はほかのものよりさらに同等なのです。

何を言っているんでしょうか

そうです。名前は一貫性を持って使えば、それでよいのです。

いややっぱ目的が見えてないと

そしてmk-lengthはlengthよりさらに同等な名前なのです。

そう言われてもわかりませんが、今や渡されてるのはmk-lengthですからね
そういうことでしょうか

mk-lengthがmk-lengthに渡される今となっては、この引数をさらなる再帰を
生成するのに使えますか。

はい。mk-lengthを1回適用すればlength1が得られます。
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((mk-length eternity) (cdr l))))))))

mk-lengthが(mk-length eternity)になりました
(mk-length eternity)はまんまlength0ですので
さっきと違って再帰呼び出しがエラーになりません
全体としてはlength1になります

(((lambda (mk-length)
    (mk-length mk-length))
  (lambda (mk-length)
    (lambda (l)
      (cond ((null? l) 0)
            (else (add1 ((mk-length eternity) (cdr l))))))))
 l)

の値はなんですか。ここでlは(apples)です。

ここは練習

  (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apples))

スタート
全体を見ると1〜6行目が関数で、7行目が引数
引数はこのままでいいので関数の方を変形します
1〜6行目の中では、1〜2行目が関数で、3〜6行目が引数
(mk-length mk-length)のmk-lengthを3〜6行目のコードで置き換えます

= (((lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l)))))))
    (lambda (mk-length)
      (lambda (l)
        (cond ((null? l) 0)
              (else (add1 ((mk-length eternity) (cdr l))))))))
   '(apples))

今度は、1〜4行目の関数に、5〜8行目の関数を引数として与えます

= ((lambda (l)
     (cond ((null? l) 0)
           (else (add1 (((lambda (mk-length)
                           (lambda (l)
                             (cond ((null? l) 0)
                                   (else (add1 ((mk-length eternity) (cdr l))))))) 
                         eternity) (cdr l))))))
   '(apples))

1〜7行目の関数に、(apples)を引数として与えます
内側のlは内側のlambdaの引数なので置き換えません

= (cond ((null? '(apples)) 0)
        (else (add1 (((lambda (mk-length)
                        (lambda (l)
                          (cond ((null? l) 0)
                                (else (add1 ((mk-length eternity) (cdr l))))))) 
                      eternity) (cdr '(apples))))))

(null? '(apples))ではないので、

= (add1 (((lambda (mk-length)
            (lambda (l)
              (cond ((null? l) 0)
                    (else (add1 ((mk-length eternity) (cdr l))))))) 
          eternity)
         '()))

1〜4行目の関数に、eternityを引数として与えます
あとはもういいかな

= (add1 ((lambda (l)
           (cond ((null? l) 0)
                 (else (add1 ((eternity eternity) (cdr l)))))) 
         '()))
= (add1 (cond ((null? '()) 0)
              (else (add1 ((eternity eternity) (cdr '()))))))
= (add1 0)
= 1

できました
複雑な形でどこから手をつければいいか悩みますが、感覚でなんとか

これは2回以上できますか。

はい。mk-lengthを自分自身に渡し続ければ、必要なだけ実行することができます。

次の関数はなんと呼ぶのがよいでしょう。
((lambda (mk-length)
   (mk-length mk-length))
 (lambda (mk-length)
   (lambda (l)
     (cond
       ((null? l) 0)
       (else (add1 ((mk-length mk-length) (cdr l))))))))
もちろん、lengthです。

ああそうですね
理屈上はね

ってこれ動くの！

> (((lambda (mk-length)
      (mk-length mk-length))
    (lambda (mk-length)
      (lambda (l)
        (cond
          ((null? l) 0)
          (else (add1 ((mk-length mk-length) (cdr l))))))))
   '(1 2 3))
3

てっきりYコンビネータが完成するまで動かないものだと思ってました
動くと思ってみればたしかに動かない理由はないですね
(mk-length mk-length)がつまりlengthそのものって感じ

2016-05-15

Scheme手習い(15) 部分関数と全関数(2)

littleschemer

部分関数と全関数の話その２

コラッツの関数と呼ばれるやつ

1なら終わり
偶数なら2で割る
奇数なら3を掛けて1を足す

たったこれだけの関数なのに、必ず終わるかどうか、つまり全関数かどうかは証明されていません
きっと全関数だろうとは思われてるみたい

(define C
  (lambda (n)
    (cond ((one? n) 1)
          (else (cond ((even? n) (C (o/ n 2)))
                      (else (C (add1 (o* 3 n)))))))))

終わるときはいつも1を返すんですけどさすがに面白くないので
何回再帰呼び出ししたかを返すようにしてみました

(define C2
  (lambda (n c)
    (cond ((one? n) c)
          (else (cond ((even? n) (C2 (/ n 2) (add1 c)))
                      (else (C2 (add1 (* 3 n)) (add1 c))))))))

(define C2list
  (lambda (n to)
    (display (format "~a " (C2 n 0)))
    (cond ((= (modulo n 10) 0) (newline)))
    (cond ((< n to) (C2list (add1 n) to)))))

1から100までの値を表示させてみました

0 1 7 2 5 8 16 3 19 6 
14 9 9 17 17 4 12 20 20 7 
7 15 15 10 23 10 111 18 18 18 
106 5 26 13 13 21 21 21 34 8 
109 8 29 16 16 16 104 11 24 24 
24 11 11 112 112 19 32 19 32 19 
19 107 107 6 27 27 27 14 14 14 
102 22 115 22 14 22 22 35 35 9 
22 110 110 9 9 30 30 17 30 17 
92 17 17 105 105 12 118 25 25 25

わかりません

突然100を超えることがあるんでコンピュータが計算してくれるのでなければ確かめる気がしません
n = 31で106になりますがその後そんなに増えていってる感じはしません
100000までやってみたら350が最高でした
コンピュータさまさまです
100000までの値で最大値を更新したところだけプロットしてみました

f:id:kb84tkhr:20160515130512p:plain

なんか対数っぽいのでX軸を対数目盛に

f:id:kb84tkhr:20160515130628p:plain

これはよく乗ってると言っていいんでしょうか
ガウスの素数定理みたいな？
まあでも素数と「3を掛けて1を足す」とかじゃ格が違う感じ

あと2回、3回と同じ数字が続くことが多いですね
これはかなり不思議
となりあった数のコラッツ数（って言うのかな）が同じになりやすい理由って特に思いつかないんですが

次
アッカーマン関数

(define A
  (lambda (n m)
    (cond
      ((zero? n) (add1 m))
      ((zero? m) (A (sub1 n) 1))
      (else (A (sub1 n) (A n (sub1 m)))))))

今度は

Aは常に答えを返しますか。

はい、全関数です。

だそうなので安心して(？)ちょっと計算させて、一般項を予想してみました

(A 0 n) = n + 1
(A 1 n) = n + 2
(A 2 n) = 2n + 1
(A 3 n) = 2^(n+3) - 3

増え方の増え方が激しいです

(A 4 0) = 13 = 2^2 - 3
(A 4 1) = 65533 = 2^2^2^2 - 3

(A 4 2)は計算が終わらないのであきらめました

手がかりが少なすぎてわかりませんけれども2乗を2(n+1)回繰り返す、であっても大変
ヘタして2乗を2^(n+1)回繰り返す、だったらとんでもない増え方です
足す1と引く1と再帰呼び出ししか使ってないのに

(A 5 n)なんて想像するだに恐ろしい

アッカーマン関数はものすごい増え方をする関数ですが
巨大数マニアにとってはまだまだ入り口にすぎないようです
面白いかも？と思われた方はこちらをどうぞ

「寿司虚空編」(不条理系巨大数マンガ) https://comic.pixiv.net/works/1505
「巨大数論」(上のマンガの元ネタのようなもの) http://gyafun.jp/ln/

(A 4 3)は何ですか。

現実的な問題として、答えは得られないでしょう。

どういう意味ですか。

(A 4 3)の値が求まるずっと前に、今読んでいるページは朽ち果ててしまうでしょう。

全関数だからといって油断してると大変なことになるよというお話

そこで
ある関数が停止するかを判定してくれるwill-stop?という関数があるといいなあ
と話が続きますが残念ながらそうは問屋がおろしてくれません
関数自身を処理するプログラムなんてLispっぽいですけどね

will-stop?があると仮定する
関数を引数に取り、will-stop?で判定して、真ならば無限ループ、偽ならば真を返して停止する関数last-tryを作る
last-tryにlast-try自身を渡すとどうなるか
last-tryが停止するとすると、will-stop?は真なので無限ループする。おかしい
last-tryが停止しないとすると、will-stop?は偽なので停止する。おかしい
そもそもwill-stop?があると仮定したのがおかしい

残念

これは異常なことですか。

はい。そうです。will-stop?は正確に記述できるけれども我々の言語では定義できない最初の関数です。

この問題に関してほかの方法はありますか。

いいえ。ありがとう Alan M. Turing(1912〜1954) と Kurt Godel(1906〜1978)。

Godelは有名な「ゲーデルの不完全定理」というやつでぱっと見は違うけれども
実は同じことを言ってます
上記はTuringがいわゆるチューリング・マシンを使って示したときのあらすじ
に違いないと想像
あとアロンゾ・チャーチという人もラムダ計算で同じ結果を出しています
たぶんそのはず

チューリングとゲーデルは一般向けの書籍もたくさん出てるんですが
チャーチに関する本は見かけたことがありません
業績としては負けてないような気がするんですが

チューリングとゲーデルみたいな波瀾万丈の人生じゃないんですかね
ブルーバックスくらいのレベルで出してくれるといいんですけど

kb84tkhrのブログ

何を書こうか考え中ですあ、あと組織とは関係ないってやつです個人的なやつ

Scheme手習い(21) eval、またはvalue、またはmeaning(2)

Scheme手習い(20) eval、またはvalue、またはmeaning

Scheme手習い(19) Yコンビネータ(4)

Scheme手習い(18) Yコンビネータ(3)

Scheme手習い(17) Yコンビネータ(2)

Scheme手習い(16) Yコンビネータ

Scheme手習い(15) 部分関数と全関数(2)