関数型言語について議論するときの用語集（未完）

Haskell

プログラミング言語やプログラミングパラダイムについて議論するとき，用語の定義を共有しないと議論が噛み合わなくなります．それで以下に私が日頃関数型言語について議論したり考えたりするときに暗黙で使っている定義（ここでは厳密なものではなく，このよように私は考えているという程度のもの）を挙げておくことにします．関数型言語に関連する議論をするときにこの定義をそのまま利用する必要は当然ありません．議論の際に共有するべき概念や用語のチェックリスト，あるいはズレを確認するのに利用できればと思います．

私個人としては用語の使い方としては妥当であると思っていますが，あやまった理解，あやまった使い方であると感じられる（確信される）部分がありましたらご指摘下さい．また，説明すべき用語が抜けている場合にもそれをご指摘いただけると幸いです．

命令プログラミングあるいは命令型言語，とくにオブジェクト指向プログラミングとそれを支援するオブジェクト指向プログラミング言語との対比を意識しています．

プログラミング言語（Programming Language）
プログラムを記述するための文法（syntax）と記述された意味（semantics）を定める規定とを指すものとして使う．単に「言語」とだけ表示することもある．
言語処理系（Programming Language Processing System）
特定の言語で書かれたプログラムで表現された計算を実際のコンピュータ上で実施するための仕組み．コンパイラ，インタプリタ，ランタイムを含む．

N.B. 処理系の性質とプログラミング言語の性質とは別物として分けて考えている．

関数型言語（Functional Programming Language）
広義には関数プログラミングというプログラミングスタイルでプログラムを記述するための言語という意味で使う．少くとも関数を計算対象として記述できる（＝高階関数を扱える or ＝関数が第一級市民である）ことを仮定する．（ただし，できるだけ例外なく単純に思考を表現したいので，理想とする関数型言語にはさらに別の抽象化能力を暗に要求する．）プログラムの意味は値によって表現されるものとする．
関数プログラミング（Functional Programming）
関数適用によって計算を表すプログラミング手法．（気分としては関数適用指向プログラミング．）関数適用の結果としての値を構成することが目的．
関数適用（Function Application）
関数を引数に適用すること．関数に対して変換元の要素を実際に指定して変換先となる値を示すこと．
関数（Function）
指定した集合の元から指定した集合の元への変換操作をあらわす値

オブジェクト指向言語やオブジェクト指向プログラミングについては以下のように考えている．（オブジェクト指向プログラミングについて誤解していた．）

オブジェクト指向言語（Object Oriented Programming Language）
広義には（広義にしか使わない）オブジェクト指向プログラミングを支援するためのプログラミング言語と考えている．少くとも生存中不変のIDと生存中可変の内部状態との両方をもつオブジェクトを記述できることを仮定する．プログラムの意味はオブジェクトの内部状態によって表現されるものとする．
オブジェクト指向プログラミング（Objectl Oriented Programming）
オブジェクトという計算対象の相互作用として計算を表す手法．相互作用後の（特定の）オブジェクトの内部状態を知ることが計算の目的．になにか仕事させてその結果をえることが計算の目的．

追記

純粋関数型言語（Purely Functional Programming Language）
「純粋に関数的な」言語とは，式は値を表す（denote）するだけで，すべての式は「参照透明性（referential transparency）」であるような言語．
参照透明性
言語の性質（not 言語処理系の性質ではない）で式の値はそれを構成する部分式の値でのみ決まり，部分式は同じ値であれば別の式で置き換えても全体の値は変らないという性質をもつこと．

BuzzFib

Haskell

ナイーブ．ちょっと書き換えた．FibBuzzだとおもったら、BuzzFibというらしい。

module Main where

import Data.List
import System.Environment

buzzfib :: [String]
buzzfib = "FibBuzz" : unfoldr phi (1,1,1,tail $ cycle $ take 5 $"Buzz":repeat "")
  where phi (a,b,c,z:zs) | b == c    = Just ("Fib"  ++  z,(b,a+b,c+1,zs))
                         | otherwise = Just (z <+> show c,(a,b  ,c+1,zs))
        "" <+> s = s
        s  <+> _ = s

main :: IO ()
main = putStr . unlines . flip take buzzfib . read . head =<< getArgs

% buzzfib 40
FibBuzz
Fib
Fib
Fib
4
FibBuzz
6
7
Fib
9
Buzz
11
12
Fib
14
Buzz
16
17
18
19
Buzz
Fib
22
23
24
Buzz
26
27
28
29
Buzz
31
32
33
Fib
Buzz
36
37
38
39

tailDropWhile

Haskell

複数行からなるテキストデータを処理するとき，行末の空白を除去したいときがある．

rmTailSpaces :: String -> String
rmTailSpaces = unlines . map chop . lines

1行分の文字列を末尾の空白を取り除いた文字列に変換する関数chopの実装を考えてみよう．素朴に実装するなら

chop :: String -> String
chop = reverse . dropWhile isSpace . reverse

この実装は単純で，正しいことが一目でわかる．さてこれを一般化すると「指定した条件を満す要素をリストの末尾から除去する」ということになる．Preludeには「指定した条件を満す要素をリストの先頭から除去する」dropWhileという関数がある．これに因んでid:kazu_yamamotoさんがtailDropWhileと命名したようなのでここでもそれを採用しよう．

tailDropWhile :: (a -> Bool) -> [a] -> [a]
tailDropWhile p = reverse . dropWhile p . reverse

tailDropWhileを使ってchopを書きなおすと

chop :: String -> String
chop = tailDropWhile isSpace

となる．さて，上のtailDropWhileの定義では前後にreverseが使われているが．これは「あんまりな」気がする．reverseの実装は左畳み込み（foldl）で定義されているので，元のリストをすべて辿りおわった後でないと結果の値（WHNF）が得られない．したがって他の計算と組み合せたときに遅延評価と恩恵や，融合変換による最適化の恩恵が得られない．そこで reverse版のtailDropWhileを右畳み込みfoldrを使った版に書き換えてみよう．

畳み込み第3双対定理

なんか，かっこよくないですか．

閑話休題．Bird先生のIntroduction To Functional Programming, 2nd Edition (Prentice Hall Series in Computer Science)によれば，リスト上の畳み込み演算には3つの双対定理があるが，その3つめがこれ．

  foldr f e = foldl (flip f) e . reverse

ということは，reverse . dropWhile p を foldl f で表現できれば，
tailDropWhile p = foldl f . reverse なので，
tailDropWhile p = foldr (flip f) [] と定義できる．

reverse . dropWhile p の意味は全部を反転の対象にせず，先頭からいくつか落してから反転という意味である．reverse は foldl で定義されており，リストを先頭から辿ってそれを FILO つまりスタックに積んでいって（蓄積して），積むものがなくなれば，積んだものそれが答である．したがって，これを融合すると，リストを辿って，スタックが空状態のときに，条件を満す要素が来たら捨てて，スタックにすでに何か積まれているかまたは条件を満す要素がこなかったらそのままスタックに積むとやればよいのである．したがって，

tailDropWhile p = foldl f [] . reverse
  where
    f a x | null a && p x = a
          | otherwise     = x:a

と定義できるから

tailDropWhile p = foldr g []
  where
    g x a | p x && null a = a
          | otherwise     = x:a

g の局所定義でガード部 && のオペランドを入れ換えたのは g が第2引数に対して「常に正格」にはならないようにするためである．

Haskellerのための命令プログラミング用語講座

Haskell

本記事が読者として想定しているのは純粋非正格静的型付けプログラミングしかできない純粋培養ハスケラ（Haskeller）のみなさんです．

だれがなんといおうとマイノリティである純粋培養ハスケラは，だれがなんといおうとマジョリティであるシャー（C er），プラプラー（C++er），じゃばー（Javaar），ぱーらー（Perler），ぺちぱぁ（PHPer），ルビーィスト（Rubyist）．．．のみなさまが語られるプログラミング（言語）にまつわる苦労話についていくための最低限の基礎知識を身につけなければなりません．もちろん，個々の命令プログラミング言語の詳細が理解できればいいのですが，実際にはそれ以前のわかってない幼気な純粋培養ハスケラがなんと多い!?ことでしょうか．命令プログラミング言語界の掟，常識が解っていないことが多いのです．関数プログラミング界にはない概念を関数プログラミング界の言葉で語ろうとしたり，関数プログラミング界でまかりとおる非常識な用語の解釈，使用をそれが非常識であることに気づくことなく使っていることが多いのです．KYの極み，タトしまくりでは，イジメられても文句はいえません．まずはReal World（浮世）の常識を学び，自らの非常識を知ることが大切です．

変数

「変数は値に付けられた名前」とかいって簡単にすませようとしてはいけません．そんな非常識は命令プログラミングの世界では通用しません．大人の世界はそんな単純ではないのです．
変数は出現位置によって解釈が違います．代入演算子の左辺ではデータの記憶領域を指すものですが，右辺ではその記憶領域に書き込まれているデータを指すものです．

変数は値に束縛されるものではありません．もっと自由です．変数はデータを代入するもの（対象）です．変数は束縛されたときに表す値が決まるから，同一の有効範囲なら同じ値を表すけれど，有効範囲が違えば束縛も違うので表す値も違う，だから「変数」というのだ，なんて勘違いですよ．変数は有効範囲にかかわらず，代入によって，指す値が変るから変数というのです．有効範囲というのは左辺値としての有効範囲であって，右辺値の有効範囲ではないですからね．同一有効範囲で同じ値を指すならそれは，定数といいます．

定数

そうです．もうわかりましたね．定数はデータ構成子（値構成子）のことではないですよ．それはリテラルというのが普通です．δ簡約とかを持ち出してはいけませんよ．リテラルの事を定数と言うこともないわけではないようですが，まれなようですよ．同一有効範囲内で再代入できない変数を定数というのです．

代入

同一有効範囲にある変数を別の式に置き換えることではありませんよ．代入といえば，変数の左辺値で表される記憶領域にデータを配置することです．代入演算子は = と書かれることが多いのですが，これは束縛じゃないですからね．

代入は同じ変数に対して何度でもできることが重要です．記憶領域という大切な資源を少しでも効率良く使わなければならないからです．

同じ有効範囲で変数の右辺値がころころ変わるから虫が入りやすいですって!?プロならそんなことを言ってはいけません．虫退治こそがプログラマの仕事ですよ．素人が手を出さない世界こそがプログラマとしての生業がなりたつところですよ．そんな面倒なことはコンピュータにやらせてもっとクリエイティブな仕事がしたいって!?そんな青臭いこといってはいけませんよ．それに非力なコンピュータの仕事を増やしてどうするんですか．

あれっ．用語解説じゃなかったの？お説教？

副作用

これはもっとも注意しなければいけない用語です．そもそも副作用のふの字もない世界にいるものが，副作用とそうでないものとが混在している世界の複雑さを理解できるわけはないのです．プログラミング言語Haskellには副作用がないの？などと問われたら，副作用って何ですかと素直に尋ねて教えてもらいましょう．副作用を気にしたことはないと言おうとして，いきなり「Haskellにはは一切ありません」などと口走ってはいけません．副作用のない言語などI/Oもできずに全く実用的じゃありませんからね．

だいたい，プログラムの意味とは値のことなんて極端な単純化で複雑な浮世が理解できるわけないでしょ．浮世は時間とともに変化する状態が本質だっていうのに，状態（という概念）のない言語でまともに扱えるわけないということを自覚しましょう．えっ．状態が実在するわけじゃなく，それは1つのモデルだって!?そんな空想をしているからだめなんですよ．時間が本質的だって，SICPにも書いてあるでしょ．なに2章までと3章の関数プログラミングのところしか読んでないだって．は〜ぁ．状態なんぞを考えるから時間という概念が生まれて，いたづらに複雑になるんだだと．君ねぇ．世界は実際複雑なんだからね．

ヌルポを発明したホーア先生だって言っているでしょ．明かにバグがないように単純にするか，明らかなバグがないように複雑にするかでは前者の方がはるかに難しい．って．チューリング賞受賞者が言うんだから．単純にするなんてのは理想論の絵空事だからね．

...これ以上解説してもらえなさそうですね．orz

とある使い捨てコード

Haskell 
module Main where

main :: IO ()
main = interact ruby

ruby :: String -> String
ruby "" = ""
ruby s = case break ('('==) s of
  (_,[])    -> s
  (xs,_:ys) -> "<ruby><rb>"++xs++"</rb><rp>(</rp><rt>"
               ++ case break (')'==) ys of
                    (_,[])     -> error $ "invalid input: "++s
                    (ys',_:zs) -> ys'++"</rt><rp>)</rp></ruby>" ++ ruby zs