Software Engineering Lecture s03
Menu Menu
関数型言語
関数とは、
入力から決まった出力を出す処理
のこと。
C でも関数って言うよね? C は関数型言語?
「やさしい Haskell 入門 (バージョン98)」 がお勧め。
関数型言語の特徴
理論がある
Operational Semantics ( 操作的意味論 )
C/Java だと メモリモデルとか byte code とか
関数型言語の場合は、式に対して決まる
λ計算、項書換え、π計算
型がある
型推論がある
Closure ( 関数と値の組 ) を持つ
lambda 式が、データ構造として使える
さらに Haskell だと
関数が状態をもたない (同じ入力には、常に同じ値が返る)
遅延評価
Outer most な引数評価順序
この反対を関数が副作用あるいは状態をもつと言う。
これらを、もっている場合もあるし、もってない場合もある。
どんなものがあるの?
Lisp () を多用する副作用のある言語、型推論はない (Scheme , Emacs Lisp , Common LISP)
ML 型推論をもつ副作用のある言語 (OCaml / SML, SML#)
Haskell 型推論をもつ副作用のない言語
項書換え
Cはメモリに整数や浮動小数点あるいは文字列を割り当て、それをCのstatementで変更することにより計算が進む。
Haskell ではプログラムどデータは項(term)と呼ばれる木構造になっていて、これを書き換えて計算が進む。
Haskell
haskell.org から取得して Haskell をinstallする。ghci
:help をまずやろう
:l プログラムの読み込み
:m moudle の読み込み
型を見れるようにする
:set +t
ghci の簡単な使い方
Prelude> 1+1
2
Prelude> 10/3
3.3333333333333335
変数への代入
Prelude> a = 1
<interactive>:1:2: parse error on input `='
let を使う (新しい変数の定義)
Prelude> let a = 1
Prelude> a
1
複数の変数を定義
Prelude> let a=1;b=2
Prelude> b
2
Prelude> a
1
Prelude> let a=3
Prelude> a
3
新しい変数 a が繰り返し作られる
Prelude> let a=3;a=5
<interactive>:1:4:
Conflicting definitions for `a'
Bound at: <interactive>:1:4
<interactive>:1:8
同じ変数に異なる値を代入すると怒られる。(単一代入、single assignment)
代入というよりは名前付けみたいなもの。
Indent
Haskell では、プログラムの構造、特にブロックなどの単位を表すのに段付け(Indent)を用いる。Indent は Interactive な入力では使えない。(なので、; を使う)
let と where を調べてみよう。
a = let c = 1 in c
b = let c = 1+d
d = 2
in c + d
b' = let c = 1+d ; d = 2; in c + d
c = f + g where
f = 3
g = f+1
ファイルの中の定義では let を使わない。let は、そのブロックの中で新しい変数を定義するということ。
自分でいろいろ indent を変更して動かしてみる。
問題3.1
関数の定義λ式
λ( lambda ) は、引数を持つ関数を定義する。Haskell ではλの代わりに \ を使う。
*Main> let m2 = \x -> 2 * x
*Main> m2
<interactive>:14:1:
No instance for (Show (a0 -> a0)) arising from a use of ‘print’
In a stmt of an interactive GHCi command: print it
*Main> m2 2
4
*Main>
関数呼び出しは、関数と引数を並べる単純な構文である。
m2 2
引数の数が違う場合に、どんなエラーが出るかを調べよう。
複数の引数がある場合は、
let mul = \x y -> x * yとする。
ファイルの中では、引数をパターンで書くことができる。
m2' = \x -> 2 * x
mul' = \x y -> x * y
m2 x = 2 * x
mul x y = x * y
test2.hs
高階関数
複数の引数がある時には、
mul'' = \x -> \y -> x * yとしても良い。この時に、
mul'' = \x -> ( \y -> x * y )となるように Haskell の構文は定義されている。つまり、
a -> b -> c
とあったら、
a -> ( b -> c )
という意味である。
すると、
mul'' 2
は、
\y -> 2 * y
を返すことになる。
実際、
let m2'' = mul'' 2
とすると、
m2'' 3
は 6 になる。これはパターンで関数を定義しても同じことができる。
let m2' = mul' 2
ここで、m2'' は値として、\y -> 2 * y という関数を持つ。関数を返す関数なので、mul'' 2 は高階関数と呼ばれる。
これは、実装的には、
mul'' と x が 2 であるという情報
の組を持っているということになる。こういう関数と、その関数の中に出てくる変数の値(環境 evnironment あるいはinterpretation) の組を
closure
という。
引数を複数持つ関数は、逆に、引数を一つ持つ関数の組合せと考えて良い。このように複数の引数を、1引数の高階関数の合成で表すことを curry 化という。
問題3.2
高階関数と複数引数Haskell の型
Haskellの項(term)は型(type)を持つ。型は項の集合の名前だとする立場もある。その場合は型は集合となる。:t というコマンドで Haskell の型を確認することができる。
Prelude> let id x = x
Prelude> :t id
id :: t -> t
名前の後に :: があり、t -> t というのが
id x = x
の型になっている。これは、何か t という型があり、それを受けとって t を返す型という意味である。
Prelude> let apply f x = f x
Prelude> :t apply
apply :: (t1 -> t) -> t1 -> t
f x は f という関数をx を引数として呼び出している。f は何かの型 t1 を受けとって型 t を返す関数と考える。
f : t1 -> t
これが第一引数の型になっている。第二引数の型は t1 である必要がある。そして、f x を返すので、型 t を返すことになる。
Prelude> let third arg1 arg2 arg3 = arg3
Prelude> :t third
third :: t -> t1 -> t2 -> t2
これは、t -> ( t1 -> ( t2 -> t2 ) ) であることを思い出そう。