ログイン
編集不可のページディスカッション情報添付ファイル

2012-07-29 07:27:47時点のリビジョン11

メッセージを消す
alstamber/FunctionalLanguageAndLogicalLanguage

MMA

なにこれ

LISP基礎

関数型言語ってそもそも何

C言語にも関数あるじゃん

関数型言語の関数はいろいろすごい

それができて何が嬉しいの?

副作用って何

副作用は悪

副作用がないとどういう変化が起きるのか

LISPって何

LISPの構文要素

リスト構造

S式

式の評価

評価とは

式の評価の例

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

   1   (+ 1 3)

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

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

評価の順番

   1   (+ (* 1 3) 3)

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

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

number?

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

関数を自分で作りたい

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

   1   (define (square x) (* x x)) ;squareという名前の関数がある。それはxを引数にとる(* x x)というS式のことである。

変数を''束縛''する

局所変数とlet

   1   (let (束縛したい変数とその値のリスト) 束縛した後に評価させたい式)

   1   (let ((x 1)) x) ; xを1で束縛したあとxを評価

   1   (let ((x 1) (y 2)) x) ; xを1で束縛すると同時にyを2で束縛した、そのあとxを評価

大域変数と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を評価

   1 0

   1 0

順番に束縛したい

   1   (let* ((hoge 1) (y hoge)) y) ; hogeを1で束縛したあとyをhogeで束縛した、そのあとyを評価

   1   1 ;hogeを1で束縛した状態で、yをhogeで束縛したので、yを評価すると1が返ってくる

ラムダ式

   1   (define (hoge x) (* x x))
   2   (define (fuga x) (* x x))

   1  (lambda (引数) S式の並び)

   1  (define hoge (lambda (引数) S式の並び)) ;hogeでラムダ式を束縛した

   1  (define (hoge 引数) S式の並び)) ;lambdaを省略した

簡単なラムダ式の評価

   1  ((lambda (x) (*x x)) 5) ; (lambda (x) (*x x))というラムダ式の後ろに引数5をおいた

自由変数と束縛変数

自由変数の求め方

   1  free(x) = {x} ;ぼっちのxは自由

   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)

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が結果

条件分岐

   1  (if 条件 真の時のS式 偽の時のS式)

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

LISP応用

S式のちゃんとした定義

 1. アトムと()をS式と認める。()はなにも入っていないリストで空リストという。nilという風にLISPではかく。
 2. S式aとS式bがあったとする。そのとき(a・b)もS式と認める。(a・b)をドット対という。

リストのまともな定義

   1  (hoge)

   1  (hoge・())

   1  (hoge fuga)

   1  (hoge・(fuga ・()))

ボックス記法

リストを操作する

   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))

   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はリストを引数にとって、その要素を全部くっつけたリストを作る。

リスト操作と再帰

   1 (length nil)⇒0 ; 空リストの時は0
   2 (length (cons a y))⇒(+ 1 (length y)) ; aとリストyをくっつけたリストについては、yの長さに1を足したのが長さ

   1 (define (length x) ; lengthという名前の関数ですよー
   2 (cond ((null? x) 0) ; 空リストなら長さは0ですよ
   3 (else (+ 1 (length (cdr x)))))) ;そうでなければ前1つと後ろのリストに分割して、後ろのリスト(=cdr)の長さと1を足したものが長さですよー

再帰についてもう少し突っ込む

巻き取るときにリストを作る

   1 (define (reverse x z) ;reverseという名前の関数
   2 (cond ((null? x) z) ; xが空ならzを返す
   3 (else (reverse (cdr x) (cons (car x) z))))) ; そうでなければxのcdr, xのcarとzを並べたものを引数にしてrevを呼び出す

巻き戻すときにリストを作る

   1 (define (append x z) ;appendという名前の関数
   2 (cond ((null? x) z) ; xが空ならzを返す
   3 (else (cons (car x) (append (cdr x) z)))))

末尾再帰

   1 (define (reverse x z) ;reverseという名前の関数
   2 (cond ((null? x) z) ; xが空ならzを返す
   3 (else (reverse (cdr x) (cons (car x) z)))))
   4  ; reverseをここで再帰呼び出ししている。reverseの結果がそのまんま関数の結果になってるので末尾再帰。

   1 (define (append x z) ;appendという名前の関数
   2 (cond ((null? x) z) ; xが空ならzを返す
   3 (else (cons (car x) (append (cdr x) z))))) 
   4 ; appendを再帰呼び出ししている。appendの結果がそのまま関数の結果になってないので末尾再帰じゃない。
   5 ; ※appendの結果を更にconsに突っ込んだ結果が関数の結果になっているよね。

高階関数

   1 (define (calc f) (f 2 3))
   2 (calc +)

   1 (calc +)
   2 ((calc (f) (f 2 3)) +) ; calcの定義に従ってcalc関数を展開する。
   3 ((calc (f) (+ 2 3)) +) ;ラムダ式と同じように評価していく(関数はラムダ式に名前をつけただけだって話をしましたね!!)
   4 5

フィルタ関数

   1 (map 関数 リスト)⇒リストの各要素に関数を適用したリスト

   1 (define (square x) (* x x)) ; 2乗する関数を定義
   2 (map square '(1 2 3 4 5)) ; (1 2 3 4 5)というリストの各要素にsquareを定義。

reduce

   1 (reduce 2つの引数を取る関数 リスト 値) ; リストの各要素に対して順番に2つの引数を取る関数を適用したものを返す。
   2 ; 空リストなら3つ目の引数にある値を返す。

   1 (reduce + '(1 2 3 4 5) nil)⇒15 ; 1と2と3と4と5を順番に足したものを返している。

副作用のある関数

クオートとバッククオート

   1 'xx ;'xを評価してもxの値ではなくてxそのものになる。
   2 '(+ 1 2)⇒(+ 1 2) ;"(+ 1 2)を評価しても3ではなくて(+ 1 2)そのものになる。

   1 `(cdr (cdr ,(cdr '(akari kyoko yui))))

   1 `(cdr (cdr , (kyoko yui)))) ; `のカッコのカンマより後ろの式を評価する。
   2 (cdr(cdr(kyoko yui))) ; カンマより後ろの式の評価が終わったので、カンマの前と並べて結果とする。

   1 `(list, @(cdr '(akari kyoko yui)) , @(cdr '(yuruyuri gorakubu)))
   2 ⇒`(list kyoko yui gorakubu) ; @がついているときは評価の後、それらのカッコを'''剥ぎとって'''すべて連結する。

Prolog