#acl alstamber:read,write,revert,delete,admin All:read
= なにこれ =
 * プログラム言語論対策。
 * 間違ってんぞ、とか意味不明だぞ的ツッコミはTwitterの@alstamberまでよろしくお願いします。
  * わかりやすさのため、テストに支障が出ない程度に多少正確さを犠牲にしている面はある。

 * 今年の言語論の試験問題を解いてみました。
  * [[alstamber/FunctionalLanguageAndLogicalLanguage/ProgramLanguages2012|ProgramLanguages2012]]

= 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?というものがある。
 * 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基礎 =
== 論理型言語ってなに ==
 * 関数というのはXからYが導かれるという関係を表したものだった。
 * 関数ではX→Yと方向が限定されているが、別に方向を限定する必要はないんじゃねと考えた人がいた。
  * ⇒方向を限定しない'''関係'''という概念を導入した言語を作った。これが論理型言語。
  * 論理型言語で一番有名なのがProlog。

== 関係と述語 ==
 * たとえば次のような文を考えてみる。
{{{
私はニャル子が好きだ。
}}}
 * この文は「私」と「ニャル子」が「好き」という概念で結びついていることを表している。
  * 「好き」を日本語の文法用語で述語といいますね。
 * Prologは'''述語'''を中心とした言語。実際先ほどのふざけた文も述語likeを使えば次のようにPrologで表せる。
{{{#!highlight prolog
like(i, nyaruko).　/* iとnyarukoが好きという関係であることを示している */
}}}
 * もちろんたくさん並べることもできる。
{{{#!highlight prolog
like(i, nyaruko).
like(i, kyoko).
like(i, kuroyukihime).
like(you, kuroyukihime).
}}}
 * こうして述語を使って表された関係をPrologでは'''事実'''とよんでいる。Prologでは事実を定義していくことがまずプログラムを書く第一歩である。

== 質問 ==
 * 述語で事実を定義したら、次に質問と呼ばれることをする。
  * Prologでは事実を定義した後、Prologインタプリタに対して質問を繰り返すことでコンピュータに考えさせプログラムを動かしていくという方法を取る。
 * 次のようなプログラムを使って質問をしてみよう。
{{{#!highlight prolog
like(i, nyaruko).
like(i, kyoko).
like(i, kuroyukihime).
like(you, kuroyukihime).
}}}
 * gprologの場合、プログラムをインタプリタ上で入力するには[user].と入力して、端末入力モードに移行する。
  * 終わったらCtrl-Dを押す。うまく行けばコンパイルされて元の状態に戻る。
 * Prologインタプリタには次のようなプロンプトが表示されているだろう。
{{{#!highlight prolog
?-
}}}
 * これは質問を待っているという状態である。
 * では質問してみよう。質問するにはやはり述語の形を使って関係を記述すれば良い。
{{{#!highlight prolog
?- like(i, nyaruko).

yes /* iとnyarukoの間に述語likeの関係があるのでyesと返ってくる。*/
}}}
 * もういっちょ。
{{{#!highlight prolog
?- like(i, mahiro).

no /* iとmahiroの間には述語likeの関係はないのでnoと返ってくる。*/
}}}

== 変数を使ってみる ==
 * 一般的なPrologの処理系では大文字英字から始まるものを変数とみなす。
 * Prologの変数というのは「ここには何が来てもいいよ」という意味。
  * もちろん同じ名前の変数なら、同じ物が来なければいけない。
  * 数学のxとかyとかの変数の概念に近いかも。
 * 論より証拠試してみよう。次のプログラムを動かしてみる。
{{{#!highlight prolog
like(i, nyaruko).
like(i, kyoko).
like(i, kuroyukihime).
like(you, kuroyukihime).
}}}
 * まずはこんなかんじで。
{{{#!highlight prolog
?- like(i, X).

X = nyaruko;

X = kyoko;

X = kuroyukihime;

no
}}}
 * このように変数を含んだ質問をすると、その変数に該当する答えをずらずらと表示することがわかる。
  * 普通は1つずつしかでないので次の答えを探すときはセミコロンキーを押してやる必要がある。
  * 最後まで行くと、当てはまる答えがないのでnoとだけ出力して終了する。
 * もういっちょ例。
{{{#!highlight prolog
?- like(X, kuroyukihime).

X = i;

X = you;

no
}}}
 * 更にもう一つ。
{{{#!highlight prolog
?- like(X, X).

no
}}}
 * Xが2つ並んでいるので、例えばlike(nyaruko, nyaruko).のように同じ物が並んでいないと答えとしてヒットしない。よってnoとだけ出力して終了する。

== 規則 ==
 * 今まで説明した内容では大したことができない。
  * もう少し複雑なことをするために'''規則'''というものを導入する。
 * 規則は次のように書く。
{{{#!highlight prolog
head :- goal1, goal2, ..., goaln.
}}}
 * 上の文は、goal1からgoalnのすべてが成立しているときに、headが成立しますよという意味。
  * 成立しているというのはさっき示した「事実」であるということ。
 * さっき示した事実は:-から後ろがない規則という言い方もできる(無条件で成立するということ)。
 * :-より前をHead, 後ろをBodyという。

== 規則を使ってみる ==
 * 次のようなプログラムを書いてみよう。
{{{#!highlight prolog
mortal(X) :- human(X).
human(i).
human(kyoko).
}}}
 * その上でこのような質問をしてみる。
{{{#!highlight prolog
?- mortal(i).

yes

?- mortal(kyoko).

yes

?- mortal(nyaruko).

no
}}}
 * プログラムの1行目は、もしXがhumanなら、Xはmortal(死を免れない)という意味である。
 * 2行目と3行目は、iとkyokoがhumanであることを表している。
 * さてプログラムをもう少し変えてみる事にする。ニャル子は宇宙人で人間より寿命は遥に長いだろうが死は免れないだろう。そこで次のようにしてみる。
{{{#!highlight prolog
mortal(X) :- human(X).
mortal(X) :- arien(X).
human(i).
human(kyoko).
arien(nyaruko).
arien(nagato).
}}}
 * 次の質問をするとプログラムはどのように動くだろうか？
  * mortal(nyaruko).
  * mortal(nagato).
  * mortal(darthvader). 

== 閉世界仮説 ==
 * 次のような考え方。
{{{
事実は全てプログラムに記述されていなければならない。
事実としてプログラムに記述されておらず、yesであることが示せないものは、すべてnoである。
}}}

== 単一化(ユニフィケーション) ==
 * Prologは質問に含まれる変数も、プログラム(規則)に含まれる変数もなるべくそこに当てはめられる具体的なものに変換しようと頑張る。
  * 変数を含んだ質問の時は、変数に該当する答えをすべて表示しようとする。
{{{#!highlight prolog
like(i, nyaruko).
like(i, kyoko).
like(i, kuroyukihime).
like(you, kuroyukihime).

?- like(you, X).

X = kuroyukihime; /*プログラムに書かれた規則の中から当てはまるものを抜き出してきている。 */

no
}}}
  * 変数を含んだ規則に対しては、そこにプログラムの実行時に与えられた具体的な物の名前を当てはめてプログラムを実行しようとする。
{{{#!highlight prolog
mortal(X) :- human(X).
human(i).
human(kyoko).

?- mortal(kyoko).

yes
/* まず規則のHeadであるmortal(X)のXに具体的な名前kyokoを入れる。
BodyのXはHeadのXと一緒なので、Bodyはhuman(kyoko)になる。
human(kyoko)はプログラムに規則として書かれているので、成立している。
Bodyが全て成立しているので、mortal(kyoko)も成立している。 */
}}}

 * 2つのものがあって、それらが共通の具体的な名前を持てる時'''単一化'''できるという。
 * 例を挙げる。
{{{
mortal(kyoko)とmortal(X)は単一化できる。
color(yellow, blue)とcolor(X, X)は単一化できない。
　color(X, X)なのでcolor(yellow, yellow)のように同じ物が来ないと単一化できない。
}}}

== 単一化演算子 ==
 * あるものとあるものが単一化できるかどうかを調べるためのものが'''単一化演算子'''。
  * 単一化演算子の記号は=。
 * 単一化できるときはyes, できないときはnoと表示する。
 * 例を挙げる。なお例の中に+が出てくるが、これは足し算の意味と考えて良い。
{{{#!highlight prolog
?- X = 2+3.
X = 2+3
yes

?- X+5 = 3+5.
X = 3.
yes

?- 5+X = 3+5.
no /* Xに何を入れても共通の具体的な名前を持たせることができない */
}}}

== is ==
 * =は単一化演算子に使われてしまっている。
  * 普通に計算式を計算したい時は'''is'''を使う。
{{{#!highlight prolog
?- X is 3+5.
X = 8.
yes
}}}

= Prolog応用 =
== リスト ==
 * PrologにもLISPと同じようにリスト構造が存在する。
  * この講義は本当にリストと二分木が好きだよね……
 * リストは[]で囲み、カンマで区切る。
{{{#!highlight prolog
[kyoko, nyaruko, kuroyukihime]
}}}

== リストの単一化 ==
 * リストにも単一化演算子が使える。
{{{#!highlight prolog
?- [kyoko, nyaruko, kuroyukihime] = [X, nyaruko, kuroyukihime].

X = kyoko.

no
}}}

== リストの表記法についてもう少し詳しく ==
 * [X|Y]と表記すると、Xは先頭の要素一つ、Yはその後ろ全部を意味する。
{{{#!highlight prolog
?- [kyoko, nyaruko, kuroyukihime] = [X|Y].
X = kyoko,
Y = [nyaruko, kuroyukihime].

no
}}}
 * Xをhead, Yをtailと呼ぶことにする。

== リストを処理すること ==
 * リスト構造があるので、それにいろいろ足したり削除したりという操作をしてみたくなる。
  * Prologではすべてのプログラムを規則を使って書くので、リストの操作も規則を使って書くことになる。
=== append ===
 * リストに追加する。
  * append(X, Y, Z)の形で、Xの後ろにYをくっつけたものをZに入れる。
 * appendの定義を下に示す。
{{{#!highlight prolog
append([], Y, Y).
append([H|X], Y, [H|Z]) :- append(X, Y, Z).
}}}
 * 1行目の[]は、空のリストという意味。
 * 1行目は、Xが空のリストのときの規則。2番めのリストと3番目のリストは等しくないといけないという意味。
  * Xが空なのだから、XとYをくっつけたものはYそのものだよね！
 * 2行目はXが空のリストではない時の規則。
  * :-の後ろが条件を表すものだったということを思い出そう。
  * 第1引数のheadは第3引数のheadと同じ。第1引数のtailと第2引数をくっつけたものが第3引数のtailに等しいという意味。
{{{
append([a,b], [c,d], Z). を実行してみる。

Xは空じゃないので2番目の規則が適用される。
第1引数のheadと第3引数のheadは同じなので、Zは[a]となる。
第1引数のtail(すなわち[b])と第3引数のtail(すなわち[])をそれぞれXとZにセットしなおす。

するとXは空じゃないので、再帰的に2番めの規則が適用される。
第1引数のheadと第3引数のheadは同じなので、Zは[b]となる。
第1引数のtail(すなわち[])と第3引数のtail(すなわち[])をXとZにそれぞれセットし直す。

今度はXが空なので、1番目の規則が適用される。
1番目の規則によると第2引数と第3引数は同じ物になるので、第3引数は[c,d]である。
ここで再帰が終わるので、再帰から順番に戻ってくる。
するとheadに[b]と[a]が戻ってくるときに付け加えられて、第3引数は[a,b,c,d]になる。
こうしてめでたくリストへの追加ができる。
}}}
 * Prologの特徴として、規則はただの物と物の関係を表しているだけだということがいえる。
  * どういうことかというと、XとYがくっついてZになるという関係は、ZはXとYに分解できるという関係と等しいということ。
  * 逆も成り立つってことだな。
{{{#!highlight prolog
?- append([a,b], [c,d], Z).
Z = [a,b,c,d].

?- append(X, [c,d], [a,b,c,d]).
X = [a,b]. /* リストを分解することもできる！！ */
}}}

=== member ===
 * リストの中にあるものが入っているかどうかを調べたい。
 * member(X, Y)の形で、XがYに入っているかどうかを調べる。
 * memberの定義を下に示す。
{{{#!highlight prolog
member(X, [X|_]).
member(X, [_|Y]) :- member(X, Y).
}}}
 * 1つ目の規則は、Xは第2引数のheadと同じという規則。アンダーバーはなんでもいいという意味である。
 * 2つ目の規則は、1つ目の規則に該当しないときに使われる。XというものとYというものがあった時、tailの部分を新しくYと置き直してmemberを再帰的に呼び出すという意味。
{{{#!highlight prolog
?- member(kyoko, [kyoko, nyaruko]).
yes

?- member(X, [kyoko, nyaruko]).
X = kyoko.
X = nyaruko.
no

?- member(r, [p,q,X]).
X = r. /* リストを順番に調べていって、Xの部分にrを入れても矛盾が起きないのでこういう結果が出てくる */
}}}

=== last ===
 * リストの最後の要素を調べる
 * last(X, Y)とかくと、Yの最後尾の要素がXになるような関係を意味する。
 * lastの定義を下に示す。
{{{#!highlight prolog
last(X, [X]).
last(X, [_|Y]) :- last(X,Y).
}}}
 * 1番目の規則は、リストに1つしか要素がない時の話である。その時はリストの唯一の要素そのものが最後尾。
 * 2番めの規則はそれ以外の一般の時の話である。リストのheadは何でもよくて、tailを新たにYとして再帰的にlastを適用する。

=== reverse ===
 * リストL2の内容を反転させたものをリストL1に対応させる。
 * reverse(L1, L2)と使う。
 * reverseの定義を下に示す。
{{{#!highlight prolog
reverse(L1, L2) :- reverse2(L1, [], L2).
reverse2([], L, L).
reverse2([X|L], L2, L3) :- reverse2(L, [X|L2], L3).
}}}
 * 1番目の規則はreverse2(L1, [], L2)というものがあれば、reverse(L1, L2)というのもあるよということを表している。
  * reverse2が存在するのかどうかは、2番目以降の規則で定義されているので保証されている。だからreverseという関係も絶対に存在する。
 * 2番めの規則は第1引数が空っぽの時の規則である。その場合は第2引数と第3引数は同じ物になるよということを示している。
 * 3番目の規則はそれ以外の一般の状態の時の規則である。第1引数をL、第2引数のheadをX、tailをL2、第3引数をL3とみなすと、第2引数のheadを第1引数のheadに移したものを引数としてまたreverse2が適用されている。これによってリストが反転する。

=== delete ===
 * リストから要素を削除する。
 * delete(X, Y, Z)の書式で、リストYからXをあるだけ消去したものをZに対応させる。
 * deleteの定義を下に示す。
{{{#!highlight prolog
delete(_, [], []).
delete(X, [X|L], M) :- delete(X, L, M).
delete(X, [Y|L1], [Y|L2]) :- delete(X, L1, L2).
}}}
 * 1番目の規則は、第2引数か第3引数が空のリストであれば、もう一方も空のリストになりますよという意味(空リストからは削除のしようがない)。
 * 2番めの規則は、第2引数のheadがXと等しい時の話。tailを新しく第2引数としてdeleteを再帰的に適用。
 * 3番目の規則は、そうではない時の話。第2引数のheadと第3引数のheadが等しくなるようにしなさいという意味。つまり第2引数のheadが第3引数のheadにくっつけられる。
  * そうしてtailを新しく引数としてdeleteを再帰的に適用。

=== リストの順列 ===
 * permという規則を作る。
 * perm(X, Y)の形で、Xの順列をYに対応させる。
 * permの定義を下に示す。
{{{#!highlight prolog
perm([], []).
perm([X|L], P) :- perm(L, L1), ins(X, L1, P).
}}}
 * ここでinsとは次のようなものである。
{{{#!highlight prolog
ins(X, L1, L2) :- del(X, L2, L1).
del(X,[X|L],L).
del(X,[Y|L],[Y|T]) :- del(X,L,T).
}}}
 * delはdeleteとよく似たリストから要素を削除する規則だが、deleteと違って同じ要素がいくつあってもひとつ消したらそれで終わりという規則である。
 * delとinsは1番目の規則を見れば分かる通り、真逆の関係になっている事がわかる。
  * L2からXを取ったものがL1なら、L1にXを足したものがL2。
  * つまりinsはins(X,Y,Z)の形で、YにXをたしたものがZになるような関係を表している。
 * ここまでわかったところで、permを見直す。
  * 1番目の規則は第1引数が空リストであるとき。もちろん第2引数は空リスト。
  * 2番めの規則はそうではないとき。第1引数のリストをheadとtailに分割している。そしてperm(L, L1)としてtailに対して再帰的に順列を求めている。
  * そうしてもとまった順列に対して、insを使って第1引数のheadを挿入したものとpermの第2引数が同じですよーと言っている。

= LISP演習 =
 * プリントに出ているもの中心に。
{{{#!highlight scheme
'(*10 (+ 2 1)) ⇒ (*10 (+ 2 1))
(+ (* 2 1) (* 3 2)) ⇒ 8
((lambda (x y) (if (> x y) x y)) 40 19) ⇒ 40
((lambda (f x) (f x)) odd? 33) ⇒ #t
(cond ((odd? 3) 'odd) ((even? 3) 'even)) ⇒ odd
}}}
{{{#!highlight scheme
(define foo '(a b c d))
(define bar (lambda (x) (if (and (number? x) (even? x)) (+ x 1) x)))
(bar 20) ⇒ 21
(bar foo) ⇒ (a b c d)
(set! foo (if (number? foo) 10 7))
(bar foo) ⇒ 7
}}}
{{{#!highlight scheme
(car '(a b c d e)) ⇒ a
(cadr '(a b c d e)) ⇒ b
(caddr '(a b c d e)) ⇒ c
(cadddr '(a b c d e)) ⇒ d
(length (reverse (list 'a 'b 'c 'd 'e))) ⇒ 5
(list-ref '((a b) (c d) (e)) 2) ⇒ (e)
(append '(foo bar) (member 'baz '(foo bar baz boo))) ⇒ (foo bar baz boo)
; memberは要素が見つかると、その要素以降全部のリストを返す。
}}}
{{{#!highlight scheme 
(reduce append (map list '(a b c) '(1 2 3)) nil) ⇒ (a 1 b 2 c 3)
; mapによって(a b c)と(1 2 3)から1要素ずつ取り出してリストを作るという作業が行われるので、((a 1)(b 2)(c 3))というリストが出来る。
; この要素に対して順番にappendを実行していくので、こうなる。
}}}
{{{#!highlight scheme
(define a '(a list of symbols))
(define b 'one-symbol)
(define c '(another list))
`(,a ,b ,c) ⇒ ((a list of symbols) one-symbol (another list))
`(this is ,a) ⇒ (this is (a list of symbols))
`(this is ,@a) ⇒ (this is a list of symbols) ; カッコが解かれる
`(,@a and ,c) ⇒ (a list of symbols and (another list))
}}}
{{{#!highlight scheme
(define mapl2 (f x y)
(if (or (null? x)(null y)) nil
(cons (f (car x)(car y))(mapl2 f (cdr x) (cdr y)))))
}}}

= Prolog演習 =
{{{#!highlight prolog
third([_,_,X|_], X). /*リストの3番目を取り出す */

last(Xs, [Y]) :- append(_, [Y], Xs). /*リストの最後の要素を調べる */

last([X], [X]).
last([_|X], Y) :- last(X,Y). /* 別解 */

rmlast(Xs, Ys) :- append(Ys, [_], Xs). /* 最後の要素を取り除く */

aa(A,X,Y) :- append(L1, [A|L2], Y), append(L1, L2, X). /* XのどこかにAを入れるとYになるかどうかを調べる */
}}}