なにこれ

• プログラム言語論対策。
• 間違ってんぞ、とか意味不明だぞ的ツッコミは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のプログラムを書く時の基本の書き方。

式の評価

• LISPではインタプリタに式を与えて、インタプリタがその式を評価して返すという形になっている。

式の評価の例

• 変数xがあったとする。その状態でLISPのプログラムにxとかくと、xが評価されて、xの値が返ってくる。

• S式に'をつけると、評価せずにそのままのものを返す。例えば'(+ 1 3)とかくと、(+ 1 3)が返ってくる。
• 定数や文字列をプログラムに書くと、評価されて、それが表しているものそのものを返す。例えば8901016とかくと、8901016が返ってくる。

もうちょっと複雑な式の評価

• LISPに足し算させたい。
• LISPには+という名前の足し算をするための関数が用意されている。
• この+関数を使って1+3を計算したい時は下のように書く。

   1   (+ 1 3)

• リストの先頭に使いたい関数の名前、その後ろにずらずらと引数を書けばいい。
• リストは入れ子にできるんでこんな書き方もできる。　

   1   (+ (* 1 3) (* 2 -4))

• *は説明してないが、掛け算のための関数。
• LISPではデータとプログラムが同じように扱われているというのはこういうこと。つまり

   1   (+ 1 1)
   2   (1 2 3)

• 上の式はLISPに計算させているのでプログラムと言えるし、下の式は単に数を並べただけなのでデータの並びと言ってしまえる。

評価の順番

• 次のS式はどういう手順で評価されるのか。

   1   (+ (* 1 3) 3)

• LISPは最内評価という方法を取る。
  • 引数を評価してから手続きを評価する。
• だからまずS式はつぎのようになる。

   1   (+ 3 3) ;(* 1 3)を評価した

• さらにこうなる。

   1   6 ;(+ 3 3)を評価した

number?

• 引数が数のときにt(真という意味)というアトムを返す関数number?というものがある。
• 次のS式はどういう結果を返すのだろうか。

   1   (number? (* 12 (+ 8901 -11)))
   2   (number? '(* 12 (+ 8901 11)))

関数を自分で作りたい

• 関数を自分で作るためにdefineというものをつかう。
  • LISP演習ではdefunとやったと思うが、Schemeはdefine。
• 関数は次のように書く。

   1   (define (関数名 関数の引数) 関数の中身のS式)

• こんな関数が例えば考えられる。

   1   (define (square x) (* x x))

変数を''束縛''する

• 変数に値を与えることを変数を値で束縛するという。

  • なんでこんな妙な言い方をするのかはあとで。
• 一旦束縛したら基本的に変数と値の対応は変えられないと考える。
  • 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)

大域変数と局所変数の違いをみる

• ちょっと実験してみる。

   1   (define hoge 0) ;大域変数hogeを0で束縛
   2   (let ((hoge 1) (y hoge)) y) ; hogeを1で束縛すると同時にyをhogeで束縛した、そのあとyを評価
   3   hoge ;hogeを評価

• 評価は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   (define (hoge x) (* x x))
   2   (define (fuga x) (* x x))

• 名前が違うだけでやってることは一緒。
  • ⇒関数の名前そのものは関数がどういう仕事をするかには関係がない。
  • ⇒名前のない関数というのを考えれば、名前にとらわれず関数の性質だけを考えることができるよね！！

    • ⇒こういうのをラムダ式という。

• ラムダ式は次のような形をしている。

   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  free((lambda(x) x) (lambda (y z) (+ y z)))
   2  = free((lambda(x) x)) ∪ free((lambda(y z) (+ y z))) ; 並んでる時は和集合
   3  = free(x) - {x} ∪ free(+ y z) - {y,z} ;ラムダ式だから、引数は束縛変数。だからその分引いてあげないといけない
   4  = {x} - {x} ∪ {y,z} - {y,z} ;ぼっちの変数は自由変数だからそのまま変換
   5  = φ

もうちっと複雑なラムダ式の評価

• 入れ子になってるようなラムダ式の評価を考えよう。
• 下のようなラムダ式を考える。

   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 (x) (* 5 5)) 5) ; 1番目のeの中にあるxを後ろの5(上の手順表で言うところのa)で置き換えた
   2  ((lambda (x) 25) 5) ; 置き換えた式を評価した。25が出てくる
   3  25 ;これ以上評価する式が残ってないので、25が結果

• もうちょっとややこしい例。

   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は次のような書き方をする。

   1  (cond (条件1 条件1の時のS式)
   2            (条件2 条件2の時のS式)
   3            ...
   4            (条件n 条件nの時のS式)
   5 )

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  (cadr '(akari kyoko yui)) ; かだーと読む。
   2 ⇒(car (cdr '(akari kyoko yui)))
   3 ⇒kyoko
   4 
   5  (cddr '(akari kyoko yui)) ; くだだーと読む。
   6 ⇒(cdr (cdr '(akari kyoko yui)))
   7 ⇒(yui)

• もうちょっと高級なリスト操作用の関数。

   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はリストが来たら、それを要素に分解して、それをリストの要素にする。

Prolog