88
コメント:
|
29550
|
削除された箇所はこのように表示されます。 | 追加された箇所はこのように表示されます。 |
行 1: | 行 1: |
== なにこれ == | #acl alstamber:read,write,revert,delete,admin All:read = なにこれ = |
行 3: | 行 4: |
== LISP == == Prolog == |
* 間違ってんぞ、とか意味不明だぞ的ツッコミはTwitterの@alstamberまでよろしくお願いします。 * わかりやすさのため、テストに支障が出ない程度に多少正確さを犠牲にしている面はある。 = LISP基礎 = == 関数型言語ってそもそも何 == * '''関数'''がプログラムの主役になっている言語。 * ここでいう関数というのは何かを受け取ってそれをゴニョゴニョして何かを返すもの。 * 数学の関数の定義に数字以外も扱えるように付け足した感じがイメージとしては近い。 == C言語にも関数あるじゃん == * C言語の関数は「これこれしてあれあれしてそれそれしなさい」という命令の列を並べたもの。 * 引数を受け取って返り値を返すので、関数っぽいということから関数と名付けられた。 == 関数型言語の関数はいろいろすごい == * 関数に何か値を渡してゴニョゴニョすると何か値が出てくる(この作業を'''評価'''という)。 * 関数を評価すれば必ず何か値が出てくるので、関数=値と考えちゃってもいい。 * 実際関数型言語では、関数と値は全く等価に扱われてる。 * 関数=値なんだから、関数の引数に関数渡したりもできるよね!!!! * 関数=値なんだから、データ構造(リスト構造)とかに直接関数突っ込んだりもできるよね!!!!! == それができて何が嬉しいの? == * いずれわかる。 == 副作用って何 == * 同じ引数を与えたら必ず同じ結果が返ってくる * 周りの状態(変数とか)に影響を与えない * 上の2つのどちらかでも崩してしまうような操作を'''副作用がある操作'''という。 == 副作用は悪 == * 副作用はいろんな所に溢れてる。 * 入出力は外部に影響を与えるので、副作用がある操作。 * グローバル変数を変更するような関数も、副作用があるといえる。 * しかし副作用はプログラムの見通しを悪くする原因。 * どこで何が起きているのか管理できなくなってしまったり。 * 入出力などどうしても副作用を回避できないもの以外は副作用が出ないようにしたいよねー * 関数型言語だとそれができます。 == 副作用がないとどういう変化が起きるのか == * 同じ引数を渡せば必ず同じ結果が返ってくるようになる * その関数だけにらめっこすればいいことになって、プログラムの見通しが良くなる。 * 周りの環境に不必要な変化を与えないので、周りの環境に気を遣う必要がなくなる。 == LISPって何 == * 関数型言語の一つ。 * '''リスト記法'''と呼ばれる手法を使って、プログラムとデータを全く同じ形でかけるようにした。 * どうやってるのかはあとで。 * 完全に副作用を排除しているわけではない。 * これについてもあとで。 * 今回の講義では多分LISPの変種のSchemeをやった。 == LISPの構文要素 == * '''アトム''' * C言語などでの変数、定数、文字列にあたるもの。 * アトムとアトムはスペースを使って区切る。 * 文字列はC言語と同じでダブルクオートで囲む。 * リスト * これについては後で。 == リスト構造 == * アトムを並べて丸括弧で囲ったものをLISPでは'''リスト構造'''と呼ぶ。 * (a b c) * (a) * ( + 10 5) * リストの中にリストを入れてもいい。 * ((a) b c) * ((((a)))) == S式 == * リストとアトムを併せてS式という。 * S式はLISPのプログラムを書く時の基本の書き方。 == 式の評価 == === 評価とは === * S式に含まれている変数などを考慮して、式が表している値を計算すること。 * 式は評価することで何か一つの値か、なにか一つの式に必ずなる。 * LISPではインタプリタに式を与えて、インタプリタがその式を'''評価'''して返すという形になっている。 === 式の評価の例 === * 変数xがあったとする。その状態でLISPのプログラムにxとかくと、xが'''評価'''されて、xの値が返ってくる。 * S式に'をつけると、評価せずにそのままのものを返す。例えば'(+ 1 3)とかくと、(+ 1 3)が返ってくる。 * 定数や文字列をプログラムに書くと、評価されて、それが表しているものそのものを返す。例えば8901016とかくと、8901016が返ってくる。 == もうちょっと複雑な式の評価 == * LISPに足し算させたい。 * LISPには+という名前の足し算をするための関数が用意されている。 * この+関数を使って1+3を計算したい時は下のように書く。 {{{#!highlight cl (+ 1 3) }}} * リストの先頭に使いたい関数の名前、その後ろにずらずらと引数を書けばいい。 * 評価という言葉を使えば、LISPのインタプリタは(+ 1 3)という式を評価して4という値を返したという言い方もできる。 * リストは入れ子にできるんでこんな書き方もできる。 {{{#!highlight cl (+ (* 1 3) (* 2 -4)) }}} * *は説明してないが、掛け算のための関数。 * LISPではデータとプログラムが同じように扱われているというのはこういうこと。つまり {{{#!highlight cl (+ 1 1) (1 2 3) }}} * 上の式はLISPに計算させているのでプログラムと言えるし、下の式は単に数を並べただけなのでデータの並びと言ってしまえる。 == 評価の順番 == * 次のS式はどういう手順で評価されるのか。 {{{#!highlight cl (+ (* 1 3) 3) }}} * LISPは最内評価という方法を取る。 * 引数を評価してから手続きを評価する。 * だからまずS式はつぎのようになる。 {{{#!highlight cl (+ 3 3) ;(* 1 3)を評価した }}} * さらにこうなる。 {{{#!highlight cl 6 ;(+ 3 3)を評価した }}} == number? == * 引数が数のときにt(真という意味)というアトムを返す関数number?というものがある。 * 次のS式はどういう結果を返すのだろうか。 {{{#!highlight cl (number? (* 12 (+ 8901 -11))) (number? '(* 12 (+ 8901 11))) }}} == 関数を自分で作りたい == * 関数というのはその関数の働きを表す一連のS式に引数と名前をつけたものといえる。 * 関数を自分で作るためにdefineというものをつかう。 * LISP演習ではdefunとやったと思うが、Schemeはdefine。 * 関数は次のように書く。 {{{#!highlight cl (define (関数名 関数の引数) 関数の中身のS式) }}} * こんな関数が例えば考えられる。 {{{#!highlight cl (define (square x) (* x x)) ;squareという名前の関数がある。それはxを引数にとる(* x x)というS式のことである。 }}} == 変数を''束縛''する == * 変数に値を与えることを変数を値で'''束縛'''するという。 * なんでこんな妙な言い方をするのかはあとで。 * 一旦束縛したら基本的に変数と値の対応は変えられないと考える。 * C言語みたいに何度も何度も変数に別の値を入れることはできない。 == 局所変数とlet == * いわゆる局所変数(ローカル変数みたいなもの)の束縛には'''let'''を使う。 * 使い方は {{{#!highlight cl (let (束縛したい変数とその値のリスト) 束縛した後に評価させたい式) }}} * 評価させたい式を一杯並べると、前から順番に評価されて、最後の式の評価結果が値として返ってくる。 {{{#!highlight cl (let ((x 1)) x) ; xを1で束縛したあとxを評価 }}} * 一杯並べることもできる。 * letの束縛は全部が一気に行われる。 {{{#!highlight cl (let ((x 1) (y 2)) x) ; xを1で束縛すると同時にyを2で束縛した、そのあとxを評価 }}} == 大域変数とdefine == * 大域変数(いわゆるグローバル変数)の束縛には関数定義と同じ'''define'''をつかう。 * 例えば {{{#!highlight cl (define hoge 0) }}} == 大域変数と局所変数の違いをみる == * ちょっと実験してみる。 {{{#!highlight cl (define hoge 0) ;大域変数hogeを0で束縛 (let ((hoge 1) (y hoge)) y) ; hogeを1で束縛すると同時にyをhogeで束縛した、そのあとyを評価 hoge ;hogeを評価 }}} * 評価は2回行われるので、2回値が返ってくる。 * 1回目の値は2行目のyが評価された時のやつで {{{#!highlight cl 0 }}} * なぜなら、letでは同時に束縛が行われるのでyをhogeで束縛した時にはhogeを0で束縛した状態になってるから。 * 結局yも0で束縛される * 2回目の値は3行目のhogeが評価された時のやつで {{{#!highlight cl 0 }}} * なぜなら、2行目で出てくるhogeは局所変数なので、letが終わった瞬間に虚空の彼方へ消えていってしまうから。 * 3行目で見てるのは1行目でつくった大域変数のhoge。 == 順番に束縛したい == * letだと全部一気に束縛されちゃうが、順番に束縛する'''let*'''ってのもある。 {{{#!highlight cl (let* ((hoge 1) (y hoge)) y) ; hogeを1で束縛したあとyをhogeで束縛した、そのあとyを評価 }}} * 上のS式からは次の結果が返ってくる。 {{{#!highlight cl 1 ;hogeを1で束縛した状態で、yをhogeで束縛したので、yを評価すると1が返ってくる }}} == ラムダ式 == * 次の2つの関数を見てみよう。 {{{#!highlight cl (define (hoge x) (* x x)) (define (fuga x) (* x x)) }}} * 名前が違うだけでやってることは一緒。 * ⇒関数の名前そのものは関数がどういう仕事をするかには関係がない。 * ⇒名前のない関数というのを考えれば、名前にとらわれず関数の性質だけを考えることができるよね!! * ⇒こういうのを'''ラムダ式'''という。 * ラムダ式は次のような形をしている。 {{{#!highlight cl (lambda (引数) S式の並び) }}} * 関数というのは、実はラムダ式に名前をつけてるだけ。 * 束縛という言葉を使えば、ある名前をラムダ式で束縛してるだけ。 * 値=関数(式)なので、名前を値で束縛できるなら、名前を関数(式)で束縛する事もできる! {{{#!highlight cl (define hoge (lambda (引数) S式の並び)) ;hogeでラムダ式を束縛した }}} * ちょっと前にやった関数定義の書き方は、実はこの書き方からlambdaを省略した書き方だった。 {{{#!highlight cl (define (hoge 引数) S式の並び)) ;lambdaを省略した }}} == 簡単なラムダ式の評価 == * ラムダ式の引数に値を与えたい時はその後ろに引数を並べて書けば良い。 {{{#!highlight cl ((lambda (x) (*x x)) 5) ; (lambda (x) (*x x))というラムダ式の後ろに引数5をおいた }}} * 上の式は評価されて25という値を返すことは何となく分かると思う。 == 自由変数と束縛変数 == * (lambda (x1 x2 ... xn) e1 e2 ... em)というラムダ式を考える。 * 引数がn個あって、評価するS式がm個並んでる。 * この時x1 x2 ... xnはe1 e2 ... emに束縛されているという。 * 束縛されている変数を束縛変数という。 * x1 x2 ... xnはe1 e2 ... emの中で何か(値かもしれないし、変数かもしれない)に対応付けられている。だから束縛されている。 * 変数の名前と値を対応付けることを束縛するといったことを思い出そう。 * e1 e2 ... emの中でx1 x2 ... xnでない変数を自由変数という。 * 対応が決まってないので、束縛されてない⇒自由 == 自由変数の求め方 == * ある式Xの中の自由変数をfree(X)と書いて表すことにする。 * 変数xが単独でいれば、そいつは当たり前だが自由。 {{{#!highlight cl free(x) = {x} ;ぼっちのxは自由 }}} * 式Mと式Nが並んでいる時、それぞれの自由変数の和集合が全体の自由変数。 {{{#!highlight cl free(MN) = free(M)∪free(N) ;式が並んでたら、2つの自由変数の和集合が自由変数 }}} * ラムダ式の自由変数は定義から次のようになる。 {{{#!highlight cl free((lambda(x) M)) = free(M) - {x} ;束縛変数の定義から変数xは束縛変数になっちゃうので、xを引いてあげないといけない }}} == 自由変数の求め方の例 == {{{#!highlight cl free(x y) = {x, y} ;xとyが並んでいる。xは自由変数でyも自由変数だから、結果は2つの和集合。 }}} {{{#!highlight cl free((lambda(x) x) (lambda (y z) (+ y z))) = free((lambda(x) x)) ∪ free((lambda(y z) (+ y z))) ; 並んでる時は和集合 = free(x) - {x} ∪ free(+ y z) - {y,z} ;ラムダ式だから、引数は束縛変数。だからその分引いてあげないといけない = {x} - {x} ∪ {y,z} - {y,z} ;ぼっちの変数は自由変数だからそのまま変換 = φ }}} == もうちっと複雑なラムダ式の評価 == * 入れ子になってるようなラムダ式の評価を考えよう。 * 下のようなラムダ式を考える。 {{{#!highlight cl ((lambda (x1 ... xn) e1 ... em) a1 ... an) }}} * 上のラムダ式は受け取る引数がn個、評価するS式がm個、ラムダ式に渡す引数がn個になってる。 * ラムダ式は次の手順をひたすら繰り返して評価されている。 {{{ 1. k=1とおく。 2. k番目のeを見に行く。その中にxi(i番目のxという意味)が含まれてたら、ai(i番目のa)で置き換える。こうしてできたeをe*とする。 3. e*を評価する。 4. kを1増やして同じ事を繰り返す。kがmに達した(もう評価する式がない)時、その時に評価したe*がラムダ式全体の結果。 }}} * なんかよくわからんので例をあげてみる。 {{{#!highlight cl ((lambda (x) (*x x)) 5) }}} * 上のラムダ式は次のように評価される。 {{{#!highlight cl ((lambda (x) (* 5 5)) 5) ; 1番目のeの中にあるxを後ろの5(上の手順表で言うところのa)で置き換えた ((lambda (x) 25) 5) ; 置き換えた式を評価した。25が出てくる 25 ;これ以上評価する式が残ってないので、25が結果 }}} * もうちょっとややこしい例。 {{{#!highlight cl ((lambda(b) ((lambda (a) (+ a b)) 5)) 7) }}} * 上のラムダ式は次のように評価される。 {{{#!highlight cl ((lambda(b) ((lambda (a) (+ 5 b)) 5)) 7) ;内側から評価する。1番目のeの中にあるaを後ろの5で置き換えた ((lambda(b) ((lambda (a) (+ 5 b)) b)) 7) ;置き換えた式を評価した。計算しようがないのでそのまま。 ((lambda(b) (+ 5 b)) 7) ; これ以上評価する式が残ってないのでラムダ式は(+ 5 b)という式を返す。 ((lambda(b) (+ 5 7)) 7) ; eの中にあるbを後ろの7で置き換えた ((lambda(b) 12) 7) ; 式を評価したら12が出てくる。 12 ;これ以上評価する式が残ってないので、12が結果 }}} * 途中(+ 5 b)という'''式'''を返すところがある。なんか気持ち悪い気がするが、LISPでは式と値は完全にイコールの存在なので何もおかしいことはない。 * C言語では基本的に何かの値しか返せない。LISPは式そのものを返すことができる。 == 条件分岐 == * LISPにも条件分岐のための書き方が用意されている。 * '''if'''と'''cond'''がある。 * ifは次のような書き方をする。 {{{#!highlight cl (if 条件 真の時のS式 偽の時のS式) }}} * condは次のような書き方をする。 {{{#!highlight cl (cond (条件1 条件1の時のS式) (条件2 条件2の時のS式) ... (条件n 条件nの時のS式) ) }}} = LISP応用 = == S式のちゃんとした定義 == * S式のことをリストとアトムを合わせたもんですよーみたいな適当な定義をした。 * 実はもっとまともな定義がある。 {{{ 1. アトムと()をS式と認める。()はなにも入っていないリストで空リストという。nilという風にLISPではかく。 2. S式aとS式bがあったとする。そのとき(a・b)もS式と認める。(a・b)をドット対という。 }}} * こういう再帰的な定義はいかにもLISPらしいよね! * ドット対の前の部分を'''car(かー)'''、後ろの部分を'''cdr(くだー)'''と呼ぶ。 == リストのまともな定義 == * えっ、ドット対ってなんだよ、今まで一回も出てきてねえぞと思った人が多いと思う。 * 実はドット対での書き方を面倒くさいので省略したのがリスト。 * まず1つしか要素がないリストを考える。 {{{#!highlight cl (hoge) }}} * これは実は次のドット対と同じ意味。 {{{#!highlight cl (hoge・()) }}} * 要するに、carがhogeでcdrが空リストになっているようなものを(hoge)って書いてたってことだ。 * いっぱい要素が並ぶとどうなるんだろう。 {{{#!highlight cl (hoge fuga) }}} * このリストは実は次のドット対と同じ意味。 {{{#!highlight cl (hoge・(fuga ・())) }}} * carがhogeで、cdrが(fuga・())になっている。ドット対の入れ子構造になってるってこと。 * つまりリストというのは、ドット対の世界で言うところのドット対を延々入れ子にしたものってことになる。 == ボックス記法 == * 演習でやったやつ。 * ドット対(s1・s2)に対して、2つの箱を左右にくっつけたような箱を書いて、左をcar、右をcdrとみなす。 * s1をcarから、s2をcdrから矢印を引っ張ってその先に書いて対応してるよーということを表現する。 * 入れ子になっているときは箱を矢印で連結すればいい。 * 空リストの時は箱に斜め線を書く。 == リストを操作する == * LISPはS式を弄ることでプログラムを書いていく言語なので、S式の表現方法であるリストを自由にいじれることはめちゃくちゃ大事。 * 基本的なリストを操作する関数を挙げる。 {{{#!highlight scheme (null? nil)⇒#t ;null?は引数が空リストのときに真(#tとかく)を返す関数。 (car '(a b c d))⇒a ;carはリストのcarの部分を返す関数。 (cdr '(akari kyoko yui))⇒(kyoko yui) ;cdrはリストのcdrの部分を返す関数。なぜ結果がこうなるのかはドット対かボックス記法を使えばわかる。 (cons 'a 'x)⇒(a x) ;consは2つの引数をとって、最初の引数をcar、2番めの引数をcdrとするリストを作る。 (cons 'akari '(kyoko yui))⇒(akari kyoko yui) (cons '(akari) '((kyoko yui)))⇒((akari)(kyoko yui)) }}} * 'がついている部分があるが、これは'のついているものを評価しないでね、という意味。 * 上の例だとakariなどというものはLISPでは定義されてないから、評価されるとそんなものねえとエラーになってしまう。 * carとcdrはたくさん並べられる。 {{{#!highlight scheme (cadr '(akari kyoko yui)) ; かだーと読む。 ⇒(car (cdr '(akari kyoko yui))) ⇒kyoko (cddr '(akari kyoko yui)) ; くだだーと読む。 ⇒(cdr (cdr '(akari kyoko yui))) ⇒(yui) }}} * もうちょっと高級なリスト操作用の関数。 {{{#!highlight scheme (list x1 ... xn)⇒(x1 ... xn) ; listは引数からなるリストを作る。いくら並べても良い。 (length '(x1 ... xn))⇒n ; lengthはリストの長さを返す。 (reverse '(x1 ... xn))⇒(xn ... x1) ; reverseはリストを逆にしたものを返す (list-ref '(x1 ... xn) k)⇒k+1番目のx ; list-refはk+1番目の要素を返す。 (member x '(y1 ... yn)) ; memberはxがy1...ynに含まれているときに#t, そうでないときに#f(偽の意味)を返す。 (append x1 ... xn) ; appendはリストを引数にとって、その要素を全部くっつけたリストを作る。 }}} * listとappendの違いが難しいかもしれない。listはリストが引数に来ると、それを直接リストの要素にしてしまう。appendはリストが来たら、それを要素に分解して、それをリストの要素にする。 == リスト操作と再帰 == * みんな大好きな再帰 * length関数を考えよう。 {{{#!highlight scheme (length nil)⇒0 ; 空リストの時は0 (length (cons a y))⇒(+ 1 (length y)) ; aとリストyをくっつけたリストについては、yの長さに1を足したのが長さ }}} * どんなに長いリストでも2行目の式を再帰的に使えばいつかは1行目の式にたどり着いてリストの長さを計算できることがわかる。 * プログラムにするとこんなかんじになる。 {{{#!highlight scheme (define (length x) ; lengthという名前の関数ですよー (cond ((null? x) 0) ; 空リストなら長さは0ですよ (else (+ 1 (length (cdr x)))))) ;そうでなければ前1つと後ろのリストに分割して、後ろのリスト(=cdr)の長さと1を足したものが長さですよー }}} == 再帰についてもう少し突っ込む == * 巻き取り……再帰関数を呼び出す * 巻き戻し……再帰関数から戻ってくる === 巻き取るときにリストを作る === * 次の関数を見てみる。この関数はリストxの順番を反転させたものとリストzをくっつけて返す関数。 {{{#!highlight scheme (define (reverse x z) ;reverseという名前の関数 (cond ((null? x) z) ; xが空ならzを返す (else (reverse (cdr x) (cons (car x) z))))) ; そうでなければxのcdr, xのcarとzを並べたものを引数にしてrevを呼び出す }}} * この関数は再帰呼び出しするときにconsを使ってリストを作っているので、巻き取るときにリストを作っているといえる。 * この関数ではxの頭(=car)を1つずつとってきて、順番にzの頭に入れていくのでzにはxとは逆の順番で入っていくことになる。 === 巻き戻すときにリストを作る === * 次の関数を見てみる。この関数はリストxの順番をそのまま維持したものをとリストzをくっつけて返す関数。 {{{#!highlight scheme (define (append x z) ;appendという名前の関数 (cond ((null? x) z) ; xが空ならzを返す (else (cons (car x) (append (cdr x) z))))) }}} * revとは3行目のcarとcdrが入れ替わってることに注意。こうしないとappend関数の引数のxがリストじゃなくなってしまう。 * ⇒突然のエラー * この関数は再帰呼び出ししてからconsを使ってリストを作っているので、巻き戻すときにリストを作っているといえる。 * この関数ではxをcdrを再帰的にとっていって、最終的にはxのおしりから順番にzに入れていくのでzにはxと同じ順番で入って行く事になる。 == 末尾再帰 == * 巻き取る時にリストを作るか巻き戻す時にリストを作るかで同じ引数の関数でもリストの作り方が変わるので、出来上がるリストが違うことがわかった。 * 再帰呼び出しの結果が関数全体の結果になるような関数を'''末尾再帰'''であるという。 {{{#!highlight scheme (define (reverse x z) ;reverseという名前の関数 (cond ((null? x) z) ; xが空ならzを返す (else (reverse (cdr x) (cons (car x) z))))) ; reverseをここで再帰呼び出ししている。reverseの結果がそのまんま関数の結果になってるので末尾再帰。 }}} {{{#!highlight scheme (define (append x z) ;appendという名前の関数 (cond ((null? x) z) ; xが空ならzを返す (else (cons (car x) (append (cdr x) z))))) ; appendを再帰呼び出ししている。appendの結果がそのまま関数の結果になってないので末尾再帰じゃない。 ; ※appendの結果を更にconsに突っ込んだ結果が関数の結果になっているよね。 }}} * 巻き戻しの時に処理する関数は末尾再帰ではないといえる。 * 関数をいじれば末尾再帰にできる。 == 高階関数 == * 関数を引数に持つ関数。 * 関数(式)=値だっていう話をしましたね! * 高階関数の例を挙げてみる。 {{{#!highlight scheme (define (calc f) (f 2 3)) (calc +) }}} * 上の2行目の式はどうやって評価されるのか……? {{{#!highlight scheme (calc +) ((calc (f) (f 2 3)) +) ; calcの定義に従ってcalc関数を展開する。 ((calc (f) (+ 2 3)) +) ;ラムダ式と同じように評価していく(関数はラムダ式に名前をつけただけだって話をしましたね!!) 5 }}} == フィルタ関数 == * 高階関数をもっといろんな例でみてみりょう。 * 高階関数の一つであるフィルタ関数の例として'''map'''というのを挙げる。 * mapは関数とリストを引数にとって、リストの各要素に関数を適用したリストを返す。 {{{#!highlight scheme (map 関数 リスト)⇒リストの各要素に関数を適用したリスト }}} * mapを使った例を挙げる。 {{{#!highlight scheme (define (square x) (* x x)) ; 2乗する関数を定義 (map square '(1 2 3 4 5)) ; (1 2 3 4 5)というリストの各要素にsquareを定義。 }}} == reduce == * もう一つ'''reduce'''というものを挙げる。 * reduceは次のような書き方をする。 {{{#!highlight cl (reduce 2つの引数を取る関数 リスト 値) ; リストの各要素に対して順番に2つの引数を取る関数を適用したものを返す。 ; 空リストなら3つ目の引数にある値を返す。 }}} * 例えば次のように使う。 {{{#!highlight cl (reduce + '(1 2 3 4 5) nil)⇒15 ; 1と2と3と4と5を順番に足したものを返している。 }}} * ここで衝撃的な話……実はreduceはSchemeには'''存在しない''' * reduceはCommonLispというLISPには存在している。schemeにはfoldという似たような働きをする関数がある。 * なんで今までSchemeの話をしていたのに、いきなりreduceの話が始まったのか、あの講義は理解できない() == 副作用のある関数 == * 副作用は悪だという話をしたが、実際には副作用のある関数がSchemeには存在する。 * 一言で言っちゃえば'''代入'''ができる関数がある。 * set!……第1引数の変数に第2引数を無理やり代入。 * set-car!……第1引数にはリストが来る。第1引数のcarに第2引数を無理やり代入 * set-cdr!……第1引数にはリストが来る。第1引数のcdrに第2引数を無理やり代入 * 前に言った通り、関数型言語では副作用は悪である。なるべく使わない方がいい。というか普通使わなくていい。 * 良くない操作をしているという警告を込めて、これらの関数には必ずビックリマークがついている。 == クオートとバッククオート == * クオートについては今更な気がするが改めてその意味を下に示しておく。 {{{#!highlight scheme 'x⇒x ;'xを評価してもxの値ではなくてxそのものになる。 '(+ 1 2)⇒(+ 1 2) ;"(+ 1 2)を評価しても3ではなくて(+ 1 2)そのものになる。 }}} * もう一つバッククオートというのがある。これは途中までは評価してね、という都合のいい野郎である。 {{{#!highlight scheme `(cdr (cdr ,(cdr '(akari kyoko yui)))) }}} * 上の式を評価すると次のようになる。 {{{#!highlight scheme `(cdr (cdr , (kyoko yui)))) ; `のカッコのカンマより後ろの式を評価する。 (cdr(cdr(kyoko yui))) ; カンマより後ろの式の評価が終わったので、カンマの前と並べて結果とする。 }}} * @とかいう都合のいい輩もいる。 {{{#!highlight scheme `(list, @(cdr '(akari kyoko yui)) , @(cdr '(yuruyuri gorakubu))) ⇒`(list kyoko yui gorakubu) ; @がついているときは評価の後、それらのカッコを'''剥ぎとって'''すべて連結する。 = Prolog = |
なにこれ
- プログラム言語論対策。
- 間違ってんぞ、とか意味不明だぞ的ツッコミはTwitterの@alstamberまでよろしくお願いします。
- わかりやすさのため、テストに支障が出ない程度に多少正確さを犠牲にしている面はある。
LISP基礎
関数型言語ってそもそも何
関数がプログラムの主役になっている言語。
- ここでいう関数というのは何かを受け取ってそれをゴニョゴニョして何かを返すもの。
- 数学の関数の定義に数字以外も扱えるように付け足した感じがイメージとしては近い。
C言語にも関数あるじゃん
- C言語の関数は「これこれしてあれあれしてそれそれしなさい」という命令の列を並べたもの。
- 引数を受け取って返り値を返すので、関数っぽいということから関数と名付けられた。
関数型言語の関数はいろいろすごい
関数に何か値を渡してゴニョゴニョすると何か値が出てくる(この作業を評価という)。
- 関数を評価すれば必ず何か値が出てくるので、関数=値と考えちゃってもいい。
- 実際関数型言語では、関数と値は全く等価に扱われてる。
- 関数=値なんだから、関数の引数に関数渡したりもできるよね!!!!
- 関数=値なんだから、データ構造(リスト構造)とかに直接関数突っ込んだりもできるよね!!!!!
それができて何が嬉しいの?
- いずれわかる。
副作用って何
- 同じ引数を与えたら必ず同じ結果が返ってくる
- 周りの状態(変数とか)に影響を与えない
上の2つのどちらかでも崩してしまうような操作を副作用がある操作という。
副作用は悪
- 副作用はいろんな所に溢れてる。
- 入出力は外部に影響を与えるので、副作用がある操作。
- グローバル変数を変更するような関数も、副作用があるといえる。
- しかし副作用はプログラムの見通しを悪くする原因。
- どこで何が起きているのか管理できなくなってしまったり。
- 入出力などどうしても副作用を回避できないもの以外は副作用が出ないようにしたいよねー
- 関数型言語だとそれができます。
副作用がないとどういう変化が起きるのか
- 同じ引数を渡せば必ず同じ結果が返ってくるようになる
- その関数だけにらめっこすればいいことになって、プログラムの見通しが良くなる。
- 周りの環境に不必要な変化を与えないので、周りの環境に気を遣う必要がなくなる。
LISPって何
- 関数型言語の一つ。
リスト記法と呼ばれる手法を使って、プログラムとデータを全く同じ形でかけるようにした。
- どうやってるのかはあとで。
- 完全に副作用を排除しているわけではない。
- これについてもあとで。
- 今回の講義では多分LISPの変種のSchemeをやった。
LISPの構文要素
アトム
- C言語などでの変数、定数、文字列にあたるもの。
- アトムとアトムはスペースを使って区切る。
- 文字列はC言語と同じでダブルクオートで囲む。
- リスト
- これについては後で。
リスト構造
アトムを並べて丸括弧で囲ったものをLISPではリスト構造と呼ぶ。
- (a b c)
- (a)
- ( + 10 5)
- リストの中にリストを入れてもいい。
- ((a) b c)
- ((((a))))
S式
- リストとアトムを併せてS式という。
- S式はLISPのプログラムを書く時の基本の書き方。
式の評価
評価とは
- S式に含まれている変数などを考慮して、式が表している値を計算すること。
- 式は評価することで何か一つの値か、なにか一つの式に必ずなる。
LISPではインタプリタに式を与えて、インタプリタがその式を評価して返すという形になっている。
式の評価の例
変数xがあったとする。その状態でLISPのプログラムにxとかくと、xが評価されて、xの値が返ってくる。
- S式に'をつけると、評価せずにそのままのものを返す。例えば'(+ 1 3)とかくと、(+ 1 3)が返ってくる。
- 定数や文字列をプログラムに書くと、評価されて、それが表しているものそのものを返す。例えば8901016とかくと、8901016が返ってくる。
もうちょっと複雑な式の評価
- LISPに足し算させたい。
- LISPには+という名前の足し算をするための関数が用意されている。
- この+関数を使って1+3を計算したい時は下のように書く。
1 (+ 1 3)
- リストの先頭に使いたい関数の名前、その後ろにずらずらと引数を書けばいい。
- 評価という言葉を使えば、LISPのインタプリタは(+ 1 3)という式を評価して4という値を返したという言い方もできる。
- リストは入れ子にできるんでこんな書き方もできる。
1 (+ (* 1 3) (* 2 -4))
- *は説明してないが、掛け算のための関数。
- LISPではデータとプログラムが同じように扱われているというのはこういうこと。つまり
- 上の式はLISPに計算させているのでプログラムと言えるし、下の式は単に数を並べただけなのでデータの並びと言ってしまえる。
評価の順番
- 次のS式はどういう手順で評価されるのか。
1 (+ (* 1 3) 3)
- LISPは最内評価という方法を取る。
- 引数を評価してから手続きを評価する。
- だからまずS式はつぎのようになる。
1 (+ 3 3) ;(* 1 3)を評価した
- さらにこうなる。
1 6 ;(+ 3 3)を評価した
number?
- 引数が数のときにt(真という意味)というアトムを返す関数number?というものがある。
- 次のS式はどういう結果を返すのだろうか。
関数を自分で作りたい
- 関数というのはその関数の働きを表す一連のS式に引数と名前をつけたものといえる。
- 関数を自分で作るためにdefineというものをつかう。
- LISP演習ではdefunとやったと思うが、Schemeはdefine。
- 関数は次のように書く。
1 (define (関数名 関数の引数) 関数の中身のS式)
- こんな関数が例えば考えられる。
1 (define (square x) (* x x)) ;squareという名前の関数がある。それはxを引数にとる(* x x)というS式のことである。
変数を''束縛''する
変数に値を与えることを変数を値で束縛するという。
- なんでこんな妙な言い方をするのかはあとで。
- 一旦束縛したら基本的に変数と値の対応は変えられないと考える。
- C言語みたいに何度も何度も変数に別の値を入れることはできない。
局所変数とlet
いわゆる局所変数(ローカル変数みたいなもの)の束縛にはletを使う。
- 使い方は
1 (let (束縛したい変数とその値のリスト) 束縛した後に評価させたい式)
- 評価させたい式を一杯並べると、前から順番に評価されて、最後の式の評価結果が値として返ってくる。
1 (let ((x 1)) x) ; xを1で束縛したあとxを評価
- 一杯並べることもできる。
- letの束縛は全部が一気に行われる。
1 (let ((x 1) (y 2)) x) ; xを1で束縛すると同時にyを2で束縛した、そのあとxを評価
大域変数とdefine
大域変数(いわゆるグローバル変数)の束縛には関数定義と同じdefineをつかう。
- 例えば
1 (define hoge 0)
大域変数と局所変数の違いをみる
- ちょっと実験してみる。
- 評価は2回行われるので、2回値が返ってくる。
- 1回目の値は2行目のyが評価された時のやつで
1 0
- なぜなら、letでは同時に束縛が行われるのでyをhogeで束縛した時にはhogeを0で束縛した状態になってるから。
- 結局yも0で束縛される
- 2回目の値は3行目のhogeが評価された時のやつで
1 0
- なぜなら、2行目で出てくるhogeは局所変数なので、letが終わった瞬間に虚空の彼方へ消えていってしまうから。
- 3行目で見てるのは1行目でつくった大域変数のhoge。
順番に束縛したい
letだと全部一気に束縛されちゃうが、順番に束縛するlet*ってのもある。
1 (let* ((hoge 1) (y hoge)) y) ; hogeを1で束縛したあとyをhogeで束縛した、そのあとyを評価
- 上のS式からは次の結果が返ってくる。
1 1 ;hogeを1で束縛した状態で、yをhogeで束縛したので、yを評価すると1が返ってくる
ラムダ式
- 次の2つの関数を見てみよう。
- 名前が違うだけでやってることは一緒。
- ⇒関数の名前そのものは関数がどういう仕事をするかには関係がない。
- ⇒名前のない関数というのを考えれば、名前にとらわれず関数の性質だけを考えることができるよね!!
⇒こういうのをラムダ式という。
- ラムダ式は次のような形をしている。
1 (lambda (引数) S式の並び)
- 関数というのは、実はラムダ式に名前をつけてるだけ。
- 束縛という言葉を使えば、ある名前をラムダ式で束縛してるだけ。
- 値=関数(式)なので、名前を値で束縛できるなら、名前を関数(式)で束縛する事もできる!
- 束縛という言葉を使えば、ある名前をラムダ式で束縛してるだけ。
1 (define hoge (lambda (引数) S式の並び)) ;hogeでラムダ式を束縛した
- ちょっと前にやった関数定義の書き方は、実はこの書き方からlambdaを省略した書き方だった。
1 (define (hoge 引数) S式の並び)) ;lambdaを省略した
簡単なラムダ式の評価
- ラムダ式の引数に値を与えたい時はその後ろに引数を並べて書けば良い。
1 ((lambda (x) (*x x)) 5) ; (lambda (x) (*x x))というラムダ式の後ろに引数5をおいた
- 上の式は評価されて25という値を返すことは何となく分かると思う。
自由変数と束縛変数
- (lambda (x1 x2 ... xn) e1 e2 ... em)というラムダ式を考える。
- 引数がn個あって、評価するS式がm個並んでる。
- この時x1 x2 ... xnはe1 e2 ... emに束縛されているという。
- 束縛されている変数を束縛変数という。
- x1 x2 ... xnはe1 e2 ... emの中で何か(値かもしれないし、変数かもしれない)に対応付けられている。だから束縛されている。
- 変数の名前と値を対応付けることを束縛するといったことを思い出そう。
- e1 e2 ... emの中でx1 x2 ... xnでない変数を自由変数という。
- 対応が決まってないので、束縛されてない⇒自由
自由変数の求め方
- ある式Xの中の自由変数をfree(X)と書いて表すことにする。
- 変数xが単独でいれば、そいつは当たり前だが自由。
1 free(x) = {x} ;ぼっちのxは自由
- 式Mと式Nが並んでいる時、それぞれの自由変数の和集合が全体の自由変数。
1 free(MN) = free(M)∪free(N) ;式が並んでたら、2つの自由変数の和集合が自由変数
- ラムダ式の自由変数は定義から次のようになる。
1 free((lambda(x) M)) = free(M) - {x} ;束縛変数の定義から変数xは束縛変数になっちゃうので、xを引いてあげないといけない
自由変数の求め方の例
1 free(x y) = {x, y} ;xとyが並んでいる。xは自由変数でyも自由変数だから、結果は2つの和集合。
もうちっと複雑なラムダ式の評価
- 入れ子になってるようなラムダ式の評価を考えよう。
- 下のようなラムダ式を考える。
1 ((lambda (x1 ... xn) e1 ... em) a1 ... an)
- 上のラムダ式は受け取る引数がn個、評価するS式がm個、ラムダ式に渡す引数がn個になってる。
- ラムダ式は次の手順をひたすら繰り返して評価されている。
1. k=1とおく。 2. k番目のeを見に行く。その中にxi(i番目のxという意味)が含まれてたら、ai(i番目のa)で置き換える。こうしてできたeをe*とする。 3. e*を評価する。 4. kを1増やして同じ事を繰り返す。kがmに達した(もう評価する式がない)時、その時に評価したe*がラムダ式全体の結果。
- なんかよくわからんので例をあげてみる。
1 ((lambda (x) (*x x)) 5)
- 上のラムダ式は次のように評価される。
- もうちょっとややこしい例。
1 ((lambda(b) ((lambda (a) (+ a b)) 5)) 7)
- 上のラムダ式は次のように評価される。
1 ((lambda(b) ((lambda (a) (+ 5 b)) 5)) 7) ;内側から評価する。1番目のeの中にあるaを後ろの5で置き換えた
2 ((lambda(b) ((lambda (a) (+ 5 b)) b)) 7) ;置き換えた式を評価した。計算しようがないのでそのまま。
3 ((lambda(b) (+ 5 b)) 7) ; これ以上評価する式が残ってないのでラムダ式は(+ 5 b)という式を返す。
4 ((lambda(b) (+ 5 7)) 7) ; eの中にあるbを後ろの7で置き換えた
5 ((lambda(b) 12) 7) ; 式を評価したら12が出てくる。
6 12 ;これ以上評価する式が残ってないので、12が結果
途中(+ 5 b)という式を返すところがある。なんか気持ち悪い気がするが、LISPでは式と値は完全にイコールの存在なので何もおかしいことはない。
- C言語では基本的に何かの値しか返せない。LISPは式そのものを返すことができる。
条件分岐
- LISPにも条件分岐のための書き方が用意されている。
ifとcondがある。
- ifは次のような書き方をする。
1 (if 条件 真の時のS式 偽の時のS式)
- condは次のような書き方をする。
LISP応用
S式のちゃんとした定義
- S式のことをリストとアトムを合わせたもんですよーみたいな適当な定義をした。
- 実はもっとまともな定義がある。
1. アトムと()をS式と認める。()はなにも入っていないリストで空リストという。nilという風にLISPではかく。 2. S式aとS式bがあったとする。そのとき(a・b)もS式と認める。(a・b)をドット対という。
- こういう再帰的な定義はいかにもLISPらしいよね!
ドット対の前の部分をcar(かー)、後ろの部分をcdr(くだー)と呼ぶ。
リストのまともな定義
- えっ、ドット対ってなんだよ、今まで一回も出てきてねえぞと思った人が多いと思う。
- 実はドット対での書き方を面倒くさいので省略したのがリスト。
- まず1つしか要素がないリストを考える。
1 (hoge)
- これは実は次のドット対と同じ意味。
1 (hoge・())
- 要するに、carがhogeでcdrが空リストになっているようなものを(hoge)って書いてたってことだ。
- いっぱい要素が並ぶとどうなるんだろう。
1 (hoge fuga)
- このリストは実は次のドット対と同じ意味。
1 (hoge・(fuga ・()))
- carがhogeで、cdrが(fuga・())になっている。ドット対の入れ子構造になってるってこと。
- つまりリストというのは、ドット対の世界で言うところのドット対を延々入れ子にしたものってことになる。
ボックス記法
- 演習でやったやつ。
- ドット対(s1・s2)に対して、2つの箱を左右にくっつけたような箱を書いて、左をcar、右をcdrとみなす。
- s1をcarから、s2をcdrから矢印を引っ張ってその先に書いて対応してるよーということを表現する。
- 入れ子になっているときは箱を矢印で連結すればいい。
- 空リストの時は箱に斜め線を書く。
リストを操作する
- LISPはS式を弄ることでプログラムを書いていく言語なので、S式の表現方法であるリストを自由にいじれることはめちゃくちゃ大事。
- 基本的なリストを操作する関数を挙げる。
1 (null? nil)⇒#t ;null?は引数が空リストのときに真(#tとかく)を返す関数。
2 (car '(a b c d))⇒a ;carはリストのcarの部分を返す関数。
3 (cdr '(akari kyoko yui))⇒(kyoko yui) ;cdrはリストのcdrの部分を返す関数。なぜ結果がこうなるのかはドット対かボックス記法を使えばわかる。
4 (cons 'a 'x)⇒(a x) ;consは2つの引数をとって、最初の引数をcar、2番めの引数をcdrとするリストを作る。
5 (cons 'akari '(kyoko yui))⇒(akari kyoko yui)
6 (cons '(akari) '((kyoko yui)))⇒((akari)(kyoko yui))
- 'がついている部分があるが、これは'のついているものを評価しないでね、という意味。
- 上の例だとakariなどというものはLISPでは定義されてないから、評価されるとそんなものねえとエラーになってしまう。
- carとcdrはたくさん並べられる。
- もうちょっと高級なリスト操作用の関数。
1 (list x1 ... xn)⇒(x1 ... xn) ; listは引数からなるリストを作る。いくら並べても良い。
2 (length '(x1 ... xn))⇒n ; lengthはリストの長さを返す。
3 (reverse '(x1 ... xn))⇒(xn ... x1) ; reverseはリストを逆にしたものを返す
4 (list-ref '(x1 ... xn) k)⇒k+1番目のx ; list-refはk+1番目の要素を返す。
5 (member x '(y1 ... yn)) ; memberはxがy1...ynに含まれているときに#t, そうでないときに#f(偽の意味)を返す。
6 (append x1 ... xn) ; appendはリストを引数にとって、その要素を全部くっつけたリストを作る。
- listとappendの違いが難しいかもしれない。listはリストが引数に来ると、それを直接リストの要素にしてしまう。appendはリストが来たら、それを要素に分解して、それをリストの要素にする。
リスト操作と再帰
- みんな大好きな再帰
- length関数を考えよう。
- どんなに長いリストでも2行目の式を再帰的に使えばいつかは1行目の式にたどり着いてリストの長さを計算できることがわかる。
- プログラムにするとこんなかんじになる。
再帰についてもう少し突っ込む
- 巻き取り……再帰関数を呼び出す
- 巻き戻し……再帰関数から戻ってくる
巻き取るときにリストを作る
- 次の関数を見てみる。この関数はリストxの順番を反転させたものとリストzをくっつけて返す関数。
- この関数は再帰呼び出しするときにconsを使ってリストを作っているので、巻き取るときにリストを作っているといえる。
- この関数ではxの頭(=car)を1つずつとってきて、順番にzの頭に入れていくのでzにはxとは逆の順番で入っていくことになる。
巻き戻すときにリストを作る
- 次の関数を見てみる。この関数はリストxの順番をそのまま維持したものをとリストzをくっつけて返す関数。
- revとは3行目のcarとcdrが入れ替わってることに注意。こうしないとappend関数の引数のxがリストじゃなくなってしまう。
- ⇒突然のエラー
- この関数は再帰呼び出ししてからconsを使ってリストを作っているので、巻き戻すときにリストを作っているといえる。
- この関数ではxをcdrを再帰的にとっていって、最終的にはxのおしりから順番にzに入れていくのでzにはxと同じ順番で入って行く事になる。
末尾再帰
- 巻き取る時にリストを作るか巻き戻す時にリストを作るかで同じ引数の関数でもリストの作り方が変わるので、出来上がるリストが違うことがわかった。
再帰呼び出しの結果が関数全体の結果になるような関数を末尾再帰であるという。
- 巻き戻しの時に処理する関数は末尾再帰ではないといえる。
- 関数をいじれば末尾再帰にできる。
高階関数
- 関数を引数に持つ関数。
- 関数(式)=値だっていう話をしましたね!
- 高階関数の例を挙げてみる。
- 上の2行目の式はどうやって評価されるのか……?
フィルタ関数
- 高階関数をもっといろんな例でみてみりょう。
高階関数の一つであるフィルタ関数の例としてmapというのを挙げる。
- mapは関数とリストを引数にとって、リストの各要素に関数を適用したリストを返す。
1 (map 関数 リスト)⇒リストの各要素に関数を適用したリスト
- mapを使った例を挙げる。
reduce
もう一つreduceというものを挙げる。
- reduceは次のような書き方をする。
- 例えば次のように使う。
1 (reduce + '(1 2 3 4 5) nil)⇒15 ; 1と2と3と4と5を順番に足したものを返している。
ここで衝撃的な話……実はreduceはSchemeには存在しない
reduceはCommonLispというLISPには存在している。schemeにはfoldという似たような働きをする関数がある。
- なんで今までSchemeの話をしていたのに、いきなりreduceの話が始まったのか、あの講義は理解できない()
副作用のある関数
- 副作用は悪だという話をしたが、実際には副作用のある関数がSchemeには存在する。
一言で言っちゃえば代入ができる関数がある。
- set!……第1引数の変数に第2引数を無理やり代入。
- set-car!……第1引数にはリストが来る。第1引数のcarに第2引数を無理やり代入
- set-cdr!……第1引数にはリストが来る。第1引数のcdrに第2引数を無理やり代入
- 前に言った通り、関数型言語では副作用は悪である。なるべく使わない方がいい。というか普通使わなくていい。
- 良くない操作をしているという警告を込めて、これらの関数には必ずビックリマークがついている。
クオートとバッククオート
- クオートについては今更な気がするが改めてその意味を下に示しておく。
- もう一つバッククオートというのがある。これは途中までは評価してね、という都合のいい野郎である。
1 `(cdr (cdr ,(cdr '(akari kyoko yui))))
- 上の式を評価すると次のようになる。
- @とかいう都合のいい輩もいる。