Login
Immutable PageDiscussionInfoAttachments

Please use a more selective search term instead of ""

Clear message
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基礎

論理型言語ってなに

関係と述語

私はニャル子が好きだ。

   1 like(i, nyaruko). /* iとnyarukoが好きという関係であることを示している */

   1 like(i, nyaruko).
   2 like(i, kyoko).
   3 like(i, kuroyukihime).
   4 like(you, kuroyukihime).

質問

   1 like(i, nyaruko).
   2 like(i, kyoko).
   3 like(i, kuroyukihime).
   4 like(you, kuroyukihime).

   1 ?-

   1 ?- like(i, nyaruko).
   2 
   3 yes /* iとnyarukoの間に述語likeの関係があるのでyesと返ってくる。*/

   1 ?- like(i, mahiro).
   2 
   3 no /* iとmahiroの間には述語likeの関係はないのでnoと返ってくる。*/

変数を使ってみる

   1 like(i, nyaruko).
   2 like(i, kyoko).
   3 like(i, kuroyukihime).
   4 like(you, kuroyukihime).

   1 ?- like(i, X).
   2 
   3 X = nyaruko;
   4 
   5 X = kyoko;
   6 
   7 X = kuroyukihime;
   8 
   9 no

   1 ?- like(X, kuroyukihime).
   2 
   3 X = i;
   4 
   5 X = you;
   6 
   7 no

   1 ?- like(X, X).
   2 
   3 no

規則

   1 head :- goal1, goal2, ..., goaln.

規則を使ってみる

   1 mortal(X) :- human(X).
   2 human(i).
   3 human(kyoko).

   1 ?- mortal(i).
   2 
   3 yes
   4 
   5 ?- mortal(kyoko).
   6 
   7 yes
   8 
   9 ?- mortal(nyaruko).
  10 
  11 no

   1 mortal(X) :- human(X).
   2 mortal(X) :- arien(X).
   3 human(i).
   4 human(kyoko).
   5 arien(nyaruko).
   6 arien(nagato).

閉世界仮説

事実は全てプログラムに記述されていなければならない。
事実としてプログラムに記述されておらず、yesであることが示せないものは、すべてnoである。

単一化(ユニフィケーション)

   1 like(i, nyaruko).
   2 like(i, kyoko).
   3 like(i, kuroyukihime).
   4 like(you, kuroyukihime).
   5 
   6 ?- like(you, X).
   7 
   8 X = kuroyukihime; /*プログラムに書かれた規則の中から当てはまるものを抜き出してきている。 */
   9 
  10 no

   1 mortal(X) :- human(X).
   2 human(i).
   3 human(kyoko).
   4 
   5 ?- mortal(kyoko).
   6 
   7 yes
   8 /* まず規則のHeadであるmortal(X)のXに具体的な名前kyokoを入れる。
   9 BodyのXはHeadのXと一緒なので、Bodyはhuman(kyoko)になる。
  10 human(kyoko)はプログラムに規則として書かれているので、成立している。
  11 Bodyが全て成立しているので、mortal(kyoko)も成立している。 */

mortal(kyoko)とmortal(X)は単一化できる。
color(yellow, blue)とcolor(X, X)は単一化できない。
 color(X, X)なのでcolor(yellow, yellow)のように同じ物が来ないと単一化できない。

単一化演算子

   1 ?- X = 2+3.
   2 X = 2+3
   3 yes
   4 
   5 ?- X+5 = 3+5.
   6 X = 3.
   7 yes
   8 
   9 ?- 5+X = 3+5.
  10 no /* Xに何を入れても共通の具体的な名前を持たせることができない */

is

   1 ?- X is 3+5.
   2 X = 8.
   3 yes

Prolog応用

リスト

   1 [kyoko, nyaruko, kuroyukihime]

リストの単一化

   1 ?- [kyoko, nyaruko, kuroyukihime] = [X, nyaruko, kuroyukihime].
   2 
   3 X = kyoko.
   4 
   5 no

リストの表記法についてもう少し詳しく

   1 ?- [kyoko, nyaruko, kuroyukihime] = [X|Y].
   2 X = kyoko,
   3 Y = [nyaruko, kuroyukihime].
   4 
   5 no

リストを処理すること

append

   1 append([], Y, Y).
   2 append([H|X], Y, [H|Z]) :- append(X, Y, Z).

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]になる。
こうしてめでたくリストへの追加ができる。

   1 ?- append([a,b], [c,d], Z).
   2 Z = [a,b,c,d].
   3 
   4 ?- append(X, [c,d], [a,b,c,d]).
   5 X = [a,b]. /* リストを分解することもできる!! */

member

   1 member(X, [X|_]).
   2 member(X, [_|Y]) :- member(X, Y).

   1 ?- member(kyoko, [kyoko, nyaruko]).
   2 yes
   3 
   4 ?- member(X, [kyoko, nyaruko]).
   5 X = kyoko.
   6 X = nyaruko.
   7 no
   8 
   9 ?- member(r, [p,q,X]).
  10 X = r. /* リストを順番に調べていって、Xの部分にrを入れても矛盾が起きないのでこういう結果が出てくる */

last

   1 last(X, [X]).
   2 last(X, [_|Y]) :- last(X,Y).

reverse

   1 reverse(L1, L2) :- reverse2(L1, [], L2).
   2 reverse2([], L, L).
   3 reverse2([X|L], L2, L3) :- reverse2(L, [X|L2], L3).

delete

   1 delete(_, [], []).
   2 delete(X, [X|L], M) :- delete(X, L, M).
   3 delete(X, [Y|L1], [Y|L2]) :- delete(X, L1, L2).

リストの順列

   1 perm([], []).
   2 perm([X|L], P) :- perm(L, L1), ins(X, L1, P).

   1 ins(X, L1, L2) :- del(X, L2, L1).
   2 del(X,[X|L],L).
   3 del(X,[Y|L],[Y|T]) :- del(X,L,T).

LISP演習

   1 '(*10 (+ 2 1)) ⇒ (*10 (+ 2 1))
   2 (+ (* 2 1) (* 3 2)) ⇒ 8
   3 ((lambda (x y) (if (> x y) x y)) 40 19) ⇒ 40
   4 ((lambda (f x) (f x)) odd? 33) ⇒ #t
   5 (cond ((odd? 3) 'odd) ((even? 3) 'even)) ⇒ odd

   1 (define foo '(a b c d))
   2 (define bar (lambda (x) (if (and (number? x) (even? x)) (+ x 1) x)))
   3 (bar 20) ⇒ 21
   4 (bar foo) ⇒ (a b c d)
   5 (set! foo (if (number? foo) 10 7))
   6 (bar foo) ⇒ 7

   1 (car '(a b c d e)) ⇒ a
   2 (cadr '(a b c d e)) ⇒ b
   3 (caddr '(a b c d e)) ⇒ c
   4 (cadddr '(a b c d e)) ⇒ d
   5 (length (reverse (list 'a 'b 'c 'd 'e))) ⇒ 5
   6 (list-ref '((a b) (c d) (e)) 2) ⇒ (e)
   7 (append '(foo bar) (member 'baz '(foo bar baz boo))) ⇒ (foo bar baz boo)
   8 ; memberは要素が見つかると、その要素以降全部のリストを返す。

   1 (reduce append (map list '(a b c) '(1 2 3)) nil) ⇒ (a 1 b 2 c 3)
   2 ; mapによって(a b c)と(1 2 3)から1要素ずつ取り出してリストを作るという作業が行われるので、((a 1)(b 2)(c 3))というリストが出来る。
   3 ; この要素に対して順番にappendを実行していくので、こうなる。

   1 (define a '(a list of symbols))
   2 (define b 'one-symbol)
   3 (define c '(another list))
   4 `(,a ,b ,c) ⇒ ((a list of symbols) one-symbol (another list))
   5 `(this is ,a) ⇒ (this is (a list of symbols))
   6 `(this is ,@a) ⇒ (this is a list of symbols) ; カッコが解かれる
   7 `(,@a and ,c) ⇒ (a list of symbols and (another list))

   1 (define mapl2 (f x y)
   2 (if (or (null? x)(null y)) nil
   3 (cons (f (car x)(car y))(mapl2 f (cdr x) (cdr y)))))

Prolog演習

   1 third([_,_,X|_], X). /*リストの3番目を取り出す */
   2 
   3 last(Xs, [Y]) :- append(_, [Y], Xs). /*リストの最後の要素を調べる */
   4 
   5 last([X], [X]).
   6 last([_|X], Y) :- last(X,Y). /* 別解 */
   7 
   8 rmlast(Xs, Ys) :- append(Ys, [_], Xs). /* 最後の要素を取り除く */
   9 
  10 aa(A,X,Y) :- append(L1, [A|L2], Y), append(L1, L2, X). /* XのどこかにAを入れるとYになるかどうかを調べる */