=begin = プログラミング言語論レポート - プログラミング言語Haskell 学籍番号 70103970 総合政策学部2年 酒井政裕 == (1) その言語の特徴を、他の言語と比較して解説せよ 関数型プログラミング言語 Haskell (参考文献[1])を選択した。 Haskellは The Haskell 98 Report (参考文献[5]) では以下のように語られて いるので、以下では主にこれらの特徴について取りあげる。 Haskell は汎用の純粋関数型プログラミング言語で、プログラミング言語設計 の分野での最近の革新の多くが取入れられている。Haskell が提供するのは、 高階関数、非正格の意味論、静的多相型付け、利用者定義の代数的データ型、 パターン照合、リストの内包表記、モジュールシステム、モナド I/O システ ムである。 また、さらに次のような豊かなプリミティブデータ型が用意され ている。リスト、配列、任意倍長整数、固定倍長整数、浮動小数点数。 Haskell は遅延評価型関数型言語に関する長年の研究を凝縮したものであり、 また、その頂点にたつものである。 == 非正格性(non-striceness) / 遅延評価(lazy evaluation) HaskellはML等の多くの言語と異なり非正格(non-srict)であり遅延評価を行う。 他の非正格な言語にはMiranda(参考文献[9])やLazy-Tiger等がある。 Haskellでは呼び出しは、「call by name」の効率を改善した「call by need」 (参考文献[20])と呼ばれる方法で行われる。引数の式はサンク(thunk)の形で 関数に渡されるが、サンクが一度評価された結果を記憶し、同じ式の値が必要 になった場合にはそれを使うので、同じ引数式を複数回評価することはない。 また、Haskellは部分的な正格評価を行うための仕組みも持っている。これは、 merd(参考文献[12])が、デフォルトでは正格評価で、部分的な非正格評価を行 う仕組みも持っているのと対照的である。 == 型 HaskellはML同様に強く型づけされた言語であり、全ての式は型推論によって 静的に型が決定される。 型システムとしては、MLやMiranda等の多くの言語で使われている Hindley-Milnerの型システムを拡張したものを用いており、陽に型指定をせず に多相プログラムを書くことができる。そして型推論によって、陽に型づけさ れたプログラムに変換される。 また、Haskellはパラメトリック多相だけではなく、アドホック多相もサポー トする。オーバーロードされた関数は、型クラスの概念を用いることによって 型ごとに異なった振舞いが定義される。 同じ関数型言語でも、オーバーローディングをいっさい禁止しているOcaml (参考文献[10])では、整数用の加算の演算氏「+」と浮動小数点数用の加算の 演算子「+.」が別であったり、リストの長さを求める関数「List.length」と 「Array.length」が別であったりし、曖昧性が無い代わりにとても煩雑であっ た。 型クラスは名前通り型をインスタンスとし、オブジェクト指向言語でいうとこ ろの「クラス」とは別の概念である。 標準で定義されているクラスの例としては、同値性が定義された型のクラスで あるEqクラスや、全順序が定義された型のクラスであるOrdクラス、上限と下 限を持つ型のクラスであるBoundedクラス、値を列挙できる型のクラスである Enumクラス等がある。 関手(functor)としてふるまう事の出来る(多相)型のクラスであるFunctorクラ スとリストと2分木を使ってオーバーローディングの例を以下に示す。 ([] がリストの型構築子としても、空リストとしても用いられているので注意) class Functor f where fmap :: (a -> b) -> f a -> f b instance Functor [] where fmap f [] = [] fmap f (x:xs) = f x : fmap f xs -- 「:」はリストのデータ構築子。 data Tree a = Leaf a | Branch (Tree a) (Tree a) instance Functor Tree where fmap f (Leaf x) = Leaf (f x) fmap f (Branch t1 t2) = Branch (fmap f t1) (fmap f t2) fmap (\x->x+1) [1..10] -- => [2,3,4,5,6,7,8,9,10,11] -- Haskellではバックスラッシュがλ記号の代わりに使われている。 fmap (\x->x++" World!") (Branch (Leaf "Hello") (Leaf "Goodby")) -- => Branch (Leaf "Hello World!") (Leaf "Goodby World!") == パターン・マッチング 上の例を見ても分かるように、Haskellは(MLやmerd等の他の多くの関数型言語 と同様に)関数の引数のパターンマッチングを行うことが出来る。 ただし、Prolog等の論理型言語とは異なり、パターンマッチングは双方向では ないので、以下のようなプログラムはHaskellでは正しくない。 eq :: a -> a -> Bool eq x x = True eq _ _ = False == Monadic I/O Monadは元々は圏論における概念であり、E.Moggiによって非決定性や副作用を 含み得る一般化されたλ計算に対する統一的な意味論を与えるために使われ、 コンピュータサイエンスに紹介された。 そして、Haskellは入出力等の「副作用」を伴う機構を関数型言語の原理を侵 すことなく導入するための手段としてmonadを使用している。 (詳しくは参考文献[16],[17]を参照) 参照透明性を維持したまま入出力等を扱う方法としては Monad の他に Linear Type 等があるが、Linear Type がタイプシステムの拡張を必要とするのに対し て、Monadはそのような変更を必要としない。 スペースと筆者の能力の関係から、ここでMonadの詳細について書くことは出 来ないが、HaskellのMonadクラスは多相型mの上に以下のようなインターフェー スを定義している。 class Monad m where (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b return :: a -> m a fail :: String -> m a m >> k = m >>= \_ -> k fail s = error s MonadクラスのインスタンスとしてIO型があり、Haskellではこれを使って入出 力を行う。例えば、一行読み込んで表示するだけのプログラムは次のようにな る。 main :: IO () main = getLine >>= \line -> putStr line ちなみに、部分式の型はここでは次のようになっている。 getLine :: IO String putStr :: String -> IO () >>= :: IO String -> (String -> IO ()) -> IO () シンタックスシュガーとして、do記法が用意されており、これを使うことで、 あたかも手続き型言語であるかのようなプログラミングを行うことも出来る。 先ほどの例をdo記法を用いて書き直すと以下のようになる。 main :: IO () main = do line <- getLine putStr line また、Monadは入出力の他にも例外処理や状態を扱う方法としても使われている。 == リスト/配列の内包表記(list/array comprehension)と数列表記 要素をすべて羅列することなく、その性質を用いることによって、リストや配 列を簡潔に記述することが可能である。例えば、1 から100 までの奇数の2 乗 の集合 {x^2 |x ∈{1, ... , 100}, odd(x)} は、リストの内包表記/数列表記を 用いると [ x*x | x<-[1..100], odd x] のように直接的に記述することが可能である。 == インデントによるグループ化 merdやPython等と同様に、インデントによってグルーピングを示すことが出来 る。この仕組みはレイアウトと呼ばれる。HaskellはPython とは異なり、明示 的にセミコロンなどを使ったグルーピングも許されている。 余談だが、merdではHaskell的なレイアウトに加え、さらに horizontal layout という概念が導入されている。これはスペースを水平方向のグルーピ ングに使うもので、例えば「x+y * z」は「(x+y) * z」とパーズされる。 = (2) その言語の特徴をよく表していると思うサンプルプログラムを挙げよ Haskellの処理系の一つであるHugs(参考文献[2])にデモとして付属している Queens.hsを選択した。このプログラムはN-Queen問題の解を列挙するプログラ ムである。 以下に引用するソースは読み易さのため若干書き換えてある。 (注: 「--」で始まる行はコメントである。) -- This N-Queens program is based on a small variation of the 8-queens -- program from Bird and Wadler's book. -- -- Be warned: printing out the complete list of solutions (all 92 of them) -- by evaluating "q 8" takes well over 1 million reductions and uses nearly -- 2.5 million cells... it may take some time to execute on slower systems! :-) import Gofer queens :: Int -> [[Int]] queens number_of_queens = qu number_of_queens where qu 0 = [[]] qu (m+1) = [ p++[n] | p<-qu m, n<-[1..number_of_queens], safe p n ] --- [α] は要素が型αであるようなリストの型 --- 「++」はリストの結合演算子 safe :: [Int] -> Int -> Bool safe p n = all not [ check (i,j) (m,n) | (i,j) <- zip [1..] p ] where m = 1 + length p --- o allは「(a->Bool) -> [a] -> Bool」という型を持ち、 --- 「all p l」はlの要素が全て述語pを満たすときに真となる。 --- o zipは引数の二つのリストの要素をお互いにペアにしたリストを返す関数。 --- zip (x:xs) (y:ys) = (x,y) : zip xs ys --- zip _ _ = [] check :: (Int,Int) -> (Int,Int) -> Bool check (i,j) (m,n) = j==n || (i+j==m+n) || (i-j==m-n) -- Use q 5 to see the list of solutions for 5 queens. -- Use q 8 to see the list of solutions for 8 queens .... q :: Int -> IO () q = putStr . layn . map show . queens -- 「.」は関数の結合演算子 また、ここで使われているGoferモジュール(Gofer.hs)の一部を以下に抜粋する。 このモジュールも同じくHugsにデモとして含まれている。 ----------------------------------------------------------------------------- -- Utility functions, for compatibility with Gofer prelude & Bird and Wadler: -- -- Suitable for use with Hugs 98. ----------------------------------------------------------------------------- module Gofer where -- String formatting: ------------------------------------------------------- rjustify :: Int -> String -> String rjustify n s = space (n - length s) ++ s space :: Int -> String space n = copy n ' ' layn :: [String] -> String layn = lay 1 where lay _ [] = [] lay n (x:xs) = rjustify 4 (show n) ++ ") " ++ x ++ "\n" ++ lay (n+1) xs -- show x はxの文字列による表現を得る関数で、多重定義されている。 -- Misc. list utilities: ---------------------------------------------------- copy :: Int -> a -> [a] copy n x = take n (repeat x) -- takeは先頭n個の要素をリストから切り出す関数 -- repeatは要素xの無限リストを作る関数 === このプログラムの実行結果 Haskellの主な実行環境には、インタプリタのHugs(参考文献[2])と コンパイラのGHC(Grasgow Haskell Compiler)(参考文献[3])がある。 ここでは、Hugsでの実行結果を以下に示す。 % hugs Queens.hs __ __ __ __ ____ ___ _________________________________________ || || || || || || ||__ Hugs 98: Based on the Haskell 98 standard ||___|| ||__|| ||__|| __|| Copyright (c) 1994-2001 ||---|| ___|| World Wide Web: http://haskell.org/hugs || || Report bugs to: hugs-bugs@haskell.org || || Version: December 2001 _________________________________________ Haskell 98 mode: Restart with command line option -98 to enable extensions Reading file "/usr/share/hugs/lib/Prelude.hs": Hugs session for: /usr/share/hugs/lib/Prelude.hs Gofer.hs Queens.hs Queens> q 5 1) [1,3,5,2,4] 2) [1,4,2,5,3] 3) [2,4,1,3,5] 4) [2,5,3,1,4] 5) [3,1,4,2,5] 6) [3,5,2,4,1] 7) [4,1,3,5,2] 8) [4,2,5,3,1] 9) [5,2,4,1,3] 10) [5,3,1,4,2] 例えば、この実行結果の「1) [1,3,5,2,4]」は次のような配置を表している。 ┌─┬─┬─┬─┬─┐ │●│ │ │ │ │ ├─┼─┼─┼─┼─┤ │ │ │ │●│ │ ├─┼─┼─┼─┼─┤ │ │●│ │ │ │ ├─┼─┼─┼─┼─┤ │ │ │ │ │●│ ├─┼─┼─┼─┼─┤ │ │ │●│ │ │ └─┴─┴─┴─┴─┘ = (3) 上のサンプルプログラムを選んだ理由を説明せよ． このプログラムは * 高階関数 * パターンマッチング * リストの内包表記/数列表記 * オーバーローディング * 関数の結合 * 入出力 といった機能が使われている短いプログラムであり Haskellの特徴を伝えるのに適当と考えた。 == 謝辞 向井国昭氏には圏論を紹介していただくと共に「圏論における natural transformation は polymorphism になっている」という示唆を受けた。これ らはこのレポートには直接書かれてはいないが、これらが無ければ、このレポー トをHaskellで書こうという気にはならなかっただろう。ここに感謝する。 == 参考文献 (1) haskell.org (()) (2) Hugs (()) (3) Grasgow Haskell Compiler (GHC) (()) (4) A Gentle Introduction to Haskell 98 (()) 山下伸夫氏による日本語訳「やさしい Haskell 入門」 (()) (5) The Haskell 98 Report (()) 山下伸夫氏による日本語訳「Haskell 98 レポート」 (()) (6) The Haskell 98 Library Report (()) 山下伸夫氏による日本語訳「Haskell 98 ライブラリレポート」 (()) (7) John Hughes "Why Functional Programming does matter" (()) 山下伸夫氏による日本語訳「なぜ関数プログラミングは重要か」 (()) (8) P. Wadler and S. Blott. "How to make ad hoc polymorphism less ad hoc". (()) (9) The Miranda Programming Language (()) (10) Objective Caml (()) (11) Python (()) (12) merd (()) (13) F. William Lawvere, Stephen H. Shanuel "Conceptual Mathematics -- A first introduction to categories" (14) Saunders Mac Lane "Categories for the Working Mathematician" Second Edition (15) Tatsuya Hagino "A categorical programming language" (16) Philip Wadler "Monads for functional programming" (()) (17) Philip Wadler "The essence of functional programming" (()) (18) Noel Winstanley "What the hell are Monads?" (()) (19) Theodore Norvell "Monads for the Working Haskell Programmer -- a short tutorial." (()) (20) Philip Wadler "Call-by-need and call-by-value" (()) =end